Construção de compiladores

Prévia do material em texto

PDF gerado usando o pacote de ferramentas em código aberto mwlib. Veja http://code.pediapress.com/ para mais informações.
PDF generated at: Fri, 06 Dec 2013 10:27:13 UTC
Construção de compiladores
Conteúdo
Páginas
Capa 1
O que é um compilador 1
Fases de um compilador 2
Teoria das linguagens formais 2
Linguagens regulares e autômatos finitos 3
Linguagens livres de contexto 4
Análise léxica 6
Análise sintática 10
Tradução dirigida por sintaxe 18
Análise semântica 19
Geração de código intermediário 21
Otimização de código 26
Nomes dos colaboradores 29
Referências
Fontes e Editores da Página 30
Fontes, Licenças e Editores da Imagem 31
Licenças das páginas
Licença 32
Capa 1
Capa
. . Construção de compiladores
Ir para o índice
O que é um compilador
Um compilador é um tipo de tradutor que lê um programa escrito numa linguagem, a linguagem fonte, e
transforma-o em um outro programa equivalente escrito em outra linguagem, a linguagem objeto.
Existem outros tipos de tradutores sendo um deles o interpretador que, obtém um programa escrito em alguma
linguagem e o converte para código executável. A principal diferença entre um compilador e um interpretador é que
os compiladores geram códigos que podem ser executados diretamente pelo computador, enquanto que, no
interpretador o programa fonte precisa ser traduzido toda vez que for executado. Linguagem como Pascal, COBOL,
C e C++ são compiladas enquanto que linguagens como PHP, Perl, Javascript e Python são interpretadas.
Abaixo um exemplo de um programa em linguagem de alto nível e seu equivalente em linguagem de baixo nível, ou
seja, depois do processo de compilação.
Linguagem de alto nível
c = a + b;
Linguagem de baixo nível
mov ax, $a
add ax, $b
mov $c, ax
É importante notar que o programa fonte e o programa objeto são completamente diferentes, porém possuem o
mesmo significado. Além da tradução é importante destacar a tarefa do compilador na detecção de erros feitos pelo
programador, caso isso ocorra o programa objeto não é gerado e uma ou mais mensagens de erro são exibidas.
Fases de um compilador 2
Fases de um compilador
Um compilador possui várias fases que podem ser divididas em dois grupos, análise e síntese.
A análise é constituída geralmente de três fases que são, análise léxica, análise sintática e análise semântica,
enquanto que a fase de síntese é composta por módulos de geração e otimização de código.
Esta página é um esboço de informática. Ampliando-a você ajudará a melhorar o Wikilivros.
Teoria das linguagens formais
Teoria das Linguagens Formais e dos autômatos é o estudo de modelos matemáticos que possibilitam a
especificação e o reconhecimento de linguagens (no sentido amplo da palavra), suas classificações, estruturas,
propriedades, características e inter-relacionamentos.
Uma linguagem formal é um conjunto de palavras,isto é, um conjunto finito de letras ou símbolos com um conjunto
de regras para combinar estes elementos. O inventário destas letras é chamado de alfabeto na qual esta linguagem é
definida. O modo formal como uma linguagem é definida é chamada de gramática formal.
Assim, podemos dizer que "Linguagens formais" são mecanismos formais para representação e especificação de
linguagens, baseados na chamada "Teoria da Computação". As representações podem ser feitas por reconhecedores e
geradores. Os reconhecedores são dispositivos formais que servem para verificar se uma sentença pertence ou não à
determinada linguagem. São os autômatos: autômatos finitos, autômatos de pilha e Máquina de Turing. Os sistemas
geradores são dispositivos formais que permitem a geração sistemática de todas as sentenças de uma linguagem. Os
principais sistemas geradores disponíveis são as gramáticas, onde se destacam as gramáticas de Chomsky. Então,
linguagens formais podem ser representadas de maneira finita e precisa através de sistemas com sustentação
matemática.
Importância na Computação
A importância dessa teoria na Ciência da Computação é dupla: ela tanto apóia outros aspectos teóricos da Ciência da
Computação (Decibilidade, computabilidade, complexidade computacional, por exemplo), como fundamenta
diversas aplicações computacionais tais como processamento de linguagens, reconhecimento de padrões, modelagem
de sistemas.
Linguagens regulares e autômatos finitos 3
Linguagens regulares e autômatos finitos
A linguagem regular pode ser descrita por [1][2][3]:
•• Autômatos finitos
•• Gramáticas regulares
•• Expressões regulares
Autômatos Finitos
Paradigma reconhecedor. Descrevem uma expressão regular. Podem ser classificados em:
Autômato Finito Determinístico: Representado pela quintupla ( ,Q, ,q,F) que consite em:
• : Alfabeto - Conjunto finito de símbolos de entrada
• Q: Conjunto finito de estados
• : Função de transição ( : Q x Q)
• q: Estado inicial
• F: Conjunto de estados finais
Um autômato finito determinístico aceita uma cadeia de símbolos se após um estado inicial, mudando de estados por
meio da função (que determina precisamente o próximo estado), consegue chegar à um estado final.
Regras:
•• Todo estado deve conter uma e somente uma transição para cada símbolo do alfabeto.
Autômato Finito Não-Determinístico: Representado pela quintupla ( ,Q, ,q,F), onde a função de transição 
pode conduzir à múltiplos estados ou até mesmo nenhum.
Regras:
•• Não é necessário uma transição para cada símbolo do alfabeto;
•• Podem haver várias transições partindo de um mesmo estado na leitura de um mesmo símbolo;
•• Não é necessário mapear todas as possibilidades, mas, somente o que valida a cadeia.
Gramáticas Regulares
Conhecida também como Tipo 3 da Hierarquia de Chomsky. Pode ser definida como gramática linear.
As gramáticas regulares caracterizam as linguagens regulares:
•• Toda linguagem gerada por uma gramática regular é regular.
•• Toda linguagem regular pode ser caracterizada por uma gramática linear a direita, e por uma gramática linear a
esquerda.
Teorema 1: Se a linguagem L pode ser gerada por uma gramática regular, então L é regular.
Teorema 2: Se a linguagem L é regular, então L pode ser gerada por uma gramática linear a esquerda e por uma
gramática linear a direita.
Linguagens regulares e autômatos finitos 4
Expressões Regulares
Definição:
Trata-se de um paradigma gerador. Um modelo que denota qualquer linguagem regular de forma mais simples,
verificando o conjunto de cadeias de símbolos permitidos na linguagem.
Aplicação:
•• Sistemas de pesquisa de texto, geradores de analisadores léxicos.
•• Algoritmos de reconhecimento de pouca complexidade, grande eficiência e de fácil implementação.
•• Sistemas operacionais, protocolos, editores, compiladores.
Referências
[1] Roberto Claudino da Silva - http:/ / www. claudino. unifei. edu. br/
[2] José Lucas Rangel - http:/ / www. inf. puc-rio. br/ ~inf1302/
[3] http:/ / teia. inf. ufrgs. br/ cgi-bin/ moore. pl?curso=LivroAnimado& estado=281
Linguagens livres de contexto
Na teoria de linguagens formais, uma linguagem livre de contexto é uma linguagem gerada por alguma gramática
livre de contexto. O conjunto de todas as linguagens livres de contexto é idêntico ao conjunto de linguagens aceitas
por um autômato de pilha. De acordo com a Hierarquia de Chomsky, linguagens livres de contexto são Tipo-2.
As gramáticas livres de contexto são da seguinte forma:
V -> w
de modo que V é um símbolo não-terminal e w é uma cadeia composta de terminais e/ou de não-terminais. O termo
'livre de contexto' vem da idéia de que um não-terminal V sempre pode ser trocado por w, sem precisar entender seu
contexto.
Um exemplo que facilita a compreensão do que são linguagens livres de contexto é a frase:
•• 1. "Fui à biblioteca hoje."
a palavra "biblioteca" independente da frase indica todo espaço (concreto, virtual ou híbrido) destinado a uma
coleção de informações de quaisquer tipos, sejamescritas em folhas de papel (monografias, enciclopédias,
dicionários, manuais, etc) ou ainda digitalizadas e armazenadas em outros tipos de materiais, tais como CD, fitas,
VHS, DVD e bancos de dados.
Por sua vez, na frase:
•• 2. "Fui à sede beber água porque estava com sede."
a palavra "sede" em sua segunda ocorrência indica uma sensação de caráter geral, iniciada por estímulos originados
dentro do próprio organismo e não do meio ambiente. Na primeira aparição, a palavra "sede" é um centro
administrativo.
Dessa forma, na frase 1 a palavra biblioteca é livre de contexto, e a palavra sede da frase 2 é dependente de
contexto.
Define-se uma linguagem formal como livre-de-contexto se existe uma gramática livre-de-contexto que a produz.
As gramáticas livres-de-contexto são bastante potentes para descrever a sintaxe da maioria das linguagens de
programação, necessitando as vezes algumas extensões ; a sintaxe da maioria das linguagens de programação são na
verdade especificadas usando gramáticas livres-de-contexto. Essas gramáticas são no entanto bastante simples para
permitir a criação de analisadores eficientes, os quais, por uma cadeia definida, determinam como elas podem ser
geradas a partir da gramática.
Linguagens livres de contexto 5
La BNF (Backus Naur form) é a notação usada com mais frenqüência para descrever uma gramática
livre-de-contexto.
Aplicações
Tais linguagens são importantes para definir linguagens de programação. Por exemplo, as linguagens que requerem o
balanceamento de parênteses são geradas pela gramática . Da mesma forma, a maioria das
expressões aritméticas é gerada por gramáticas livres de contexto.
Exemplos
Uma linguagem livre de contexto é , a linguagem de todas as cadeias de caracteres não
vazias de tamanho par, as primeiras metades sempre preenchidas com " s" e as segundas metades sempre
preenchidas com " "s. é gerada pela gramática , e é aceita pelo autômato de pilha
, em que é definido da seguinte forma:
Em que z é a pilha de símbolos inicial e x significa desempilhar.
Propriedades de fechamento
Linguagens livres de contexto são fechadas nas seguintes operações. Se L e P são linguagens livres de contexto e D é
uma linguagem regular, as seguintes linguagens também são livres de contexto:
• o fecho de Kleene de L
• a imagem φ(L) de L sob um homorfismo φ
• a concatenação de L e P
• a união de L e P
• a interseção (com uma linguagem regular) de L e D
Linguagens livres de contexto não são fechadas em complemento, interseção ou diferença.
Propriedades de decisão
Os seguintes problemas são indecidíveis para quaisquer gramáticas livres de contexto A e B:
• ?
• ?
• ?
• ?
Os seguintes problemas são decidíveis para quaisquer linguagens livres de contexto:
• ?
• é finito?
• Dada a palavra w, ?
Análise léxica 6
Análise léxica
Análise léxica é o processo de analisar a entrada de linhas de caracteres (tal como o código-fonte de um programa de
computador) e produzir uma seqüência de símbolos chamado "símbolos léxicos" (lexical tokens), ou somente
"símbolos" (tokens), que podem ser manipulados mais facilmente por um parser (leitor de saída). O componente do
compilador responsável pela execução desse processo é conhecido como Analisador léxico.
O analisador léxico, ou scanner como também é chamado, faz a varredura do programa fonte caractere por caractere
e, traduz em uma seqüência de símbolos léxicos ou tokens. É nessa fase que são reconhecidas as palavras reservadas,
constantes, identificadores e outras palavras que pertencem a linguagem de programação. O analisador léxico
executas outras tarefas como por exemplo o tratamento de espaços, eliminação de comentários, contagem do número
de linhas que o programa possui e etc.
A análise léxica é a forma de verificar determinado alfabeto. Quando analisamos uma palavra, podemos definir
através da análise léxica se existe ou não algum caractere que não faz parte do nosso alfabeto, ou um alfabeto
inventado por nós.
É a primeira etapa do processo de compilação e seu objetivo é dividir o código fonte em símbolos, preparado-o para
a Análise Sintática. Neste processo pode-se destacar três atividades como fundamentais:
•• Extração e classificação dos tokens;
•• Eliminação de delimitadores e comentários;
•• Recuperação de Erros.
O analisador léxico funciona de duas maneiras:
• Primeiro estado da análise: A primeira etapa lê a entrada de caracteres, um de cada vez, mudando o estado em
que os caracteres se encontram. Quando o analisador encontra um caracter que ele não identifica como correto,
ele o chama de "estado morto" então, ele volta à última análise que foi aceita e assim tem o tipo e comprimento do
léxico válido.
Um léxico, entretanto, é uma única lista de caracteres conhecidas de ser um tipo correto. Para construir um símbolo,
o analisador léxico necessita de um segundo estado.
• Segundo estado da análise: Nesta etapa são repassados os caracteres do léxico para produzir um valor. O tipo do
léxico combinado com seu valor é o que adequadamente constitui um símbolo, que pode ser dado a um parser.
(Alguns símbolos tais como parênteses não têm valores, e então a função da análise pode retornar nada).
A análise léxica escreve um parser muito mais fácil. Em vez de ter que acumular, renomeia seus caracteres
individualmente. O parser não mais se preocupa com símbolos e passa a preocupar-se só com questões de sintática.
Isto leva a eficiência de programação, e não eficiência de execução. Entretanto, desde que o analisador léxico é o
subsistema que deve examinar cada caracter único de entrada, podem ser passos intensivos e o desempenhos se torna
crítico, pode estar usando um compilador.
As desvantagens da Análise Léxica são o tratamento de dados em branco, formato fixo de entrada e a inexistência de
palavras reservadas, em determinadas linguagens.
Análise léxica 7
Analisador Léxico
A implementação de um analisador léxico requer uma descrição do autômato que reconhece as sentenças da
gramática ou expressão regular de interesse com os seguintes procedimentos auxiliares:
• Estado-Inicial: Recebe como argumento a referência para o autômato e retorna o seu estado inicial;
• Estado-final: Recebe como argumentos a referência para o autômato e a referência para o estado corrente. O
procedimento retorna true (verdadeiro) se o estado especificado é elemento do conjunto de estados finais do
autômato, ou false (falso) caso contrário; e
• Próximo-Estado: Recebe como argumento a referência para o autômato, para o estado corrente e para o símbolo
sendo analisado. O procedimento consulta a tabela de transições e retorna o próximo estado do autômato, ou o
valor nulo se não houver transição possível.
Nesta fase do processo de compilação, uma sequência de caracteres do código do programa é lida e agrupada em
uma sequência de tokens.
Erros léxicos
•• Poucos erros podem ser detectados durante a análise léxica dada a visão restrita desta fase,
como mostra o exemplo: fi(a== f(x)) outro_and;
•• fi é a palavra chave if grafada incorretamente?
• fi é um identificador de função que não foi declarada faltando assim um separador (‘;’)
entre a chamada da função fi e o comando seguinte (outro_and)?
•• Ainda assim o analisador léxico pode não conseguir prosseguir dado que a cadeia encontrada não se enquadra em
nenhum dos padrões conhecidos.
•• Para permitir que o trabalho desta fase prossiga mesmo com a ocorrência de erros deve ser implementada uma
estratégia de recuperação de erros
Recuperação de erros
Ações possíveis:
•• remoção de sucessivos caracteres até o reconhecimento de um token válido (modalidade Pânico).
•• inserção de um caractere ausente.
•• substituição de um caractere incorreto por outro correto.
•• transposição de caracteres adjacentes.
Tais estratégias poderiam ser aplicadas dentro de um escopo limitado(denominado erros de distância mínima).
While(a<100) {fi(a==b) break else a++;} ...
Estas transformações seriam computadas na tentativa de obtenção de um programa sintaticamente correto (o que não
significa um programa correto, daí o limitado número de compiladores experimentais que usam tais técnicas).
Análise léxica 8
Tokens
O objetivo principal da análise léxica é identificar sequências de caracteres que constituem unidades léxicas
("tokens"). O analisador léxico lê, caractere a caractere, o texto fonte, verificando se os caracteres lidos pertencem
ao alfabeto da linguagem, identificando tokens, e desprezando comentários e brancos desnecessários.
Os tokens constituem classes de símbolos tais como palavras reservadas, delimitadores, identificadores, etc., e
podem ser representados, internamente, através do próprio símbolo (como no caso dos delimitadores e das palavras
reservadas) ou por um par ordenado, no qual o primeiro elemento indica a classe do símbolo, e o segundo, um índice
para uma área onde o próprio símbolo foi armazenado (por exemplo, um identificador e sua entrada numa tabela de
identifidadores).
Além da identificação de tokens, o Analisador Léxico, em geral, inicia a construção da Tabela de Símbolos e envia
mensagens de erro caso identifique unidades léxicas não aceitas pela linguagem em questão. A saída do Analisador
Léxico é uma cadeia de tokens que é passada para a próxima fase, a Análise Sintática. Em geral, o Analisador
Léxico é implementado como uma subrotina que funciona sob o comando do Analisador Sintático.
O analisador léxico tem a função de ler uma sequência de caracteres que constitui um programa fonte e coleta, dessa
sequência, os tokens que constituem esse programa.
Os tokens (símbolos léxicos) são unidades básicas de texto do programa. Eles são representados internamente por
três informações: classe do token, valor do token e posição do token.
Classe do token – representa o tipo do token conhecido.
Valor do token – dependente da classe; podem ser divididos em dois grupos: tokens simples e tokens com
argumento.
Posição do token – indica o local do texto fonte (linha e coluna) onde ocorreu o token.
Tokens simples – não tem um valor associado, por exemplo como as palavras reservadas.
Tokens com argumento – possuem um valor associado, por exemplo como os identificadores e as constantes.
As classes para palavras reservadas constituem-se em abreviações dessas, não sendo necessário passar seus valores
para o analisador sintático.
É usual que os compiladores representem a classe de um token por um número inteiro para tornar a representação
mais compacta.
Especificação
Os analisadores léxicos são, usualmente, especificados através de notações para a descrição de linguagens regulares
tais como autômatos finitos, expressões regulares ou gramáticas regulares.
A especificação descreve o conjunto de tokens que formam a linguagem. Fazem parte dessa especificação sequências
de caracteres que podem aparecer entre tokens e devem ser ignoradas tais como espaços em branco e comentários.
Na grande maioria das linguagens de programação, as palavras reservadas da linguagem são casos particulares dos
identificadores e seguem a mesma notação desses.
As especificações de analisadores léxicos, usualmente, não expressam, explicitamente, o reconhecimento de palavras
reservadas. Todas essas palavras então são armazenadas em uma tabela interna, que é examinada cada vez que um
identificador é reconhecido. Se esse identificador ocorre na tabela, então trata-se de uma palavra reservada, caso
contrário, trata-se de um identificador.
Em geral, o analisador léxico e o analisador sintático formam um único passo, porém, o analisador léxico pode
constituir um passo individual do compilador. Quando atuam em um único passo, o analisador léxico atua como uma
subrotina que é chamada pelo analisador sintático sempre que este necessita de mais um token.
Existem motivos que levam a dividir (conceitualmente) a análise do programa em análise léxica e sintática:
Análise léxica 9
1) Simplificação e modularização do projeto do compilador;
2) Os tokens podem ser descritos utilizando-se notações simples (como expressões regulares), enquanto a estrutura
sintática de comandos e expressões das linguagens de programação requer uma notação mais expressiva, como as
gramáticas livres do contexto;
3) Os reconhecedores construídos a partir da descrição dos tokens (através de gramáticas regulares, expressões
regulares ou autômatos finitos) são mais eficientes e compactos do que os reconhecedores construídos a partir das
gramáticas livres de contexto.
Implementação
A implementação de analisadores léxicos é feita, em geral, através de uma tabela de transição, a qual indica a
passagem de um estado a outro pela leitura de um determinado caractere. Através do uso de um gerador de
analisadores léxicos, podem ser gerados a tabela e o correspondente programa de controle. No caso do gerador, o
próprio projetista especifica os tokens a serem reconhecidos através de expressões regulares e a partir dessas
expressões, o gerador gera um programa que implementa o analisador léxico correspondente.
Existe outra forma (alternativa) para se implementar um analisador léxico que é através da construção de um
programa que simule o funcionmento do autômato correspondente.
Tabela de Símbolos
É uma estrutura de dados gerada pelo compilador com o objetivo de armazenar informações sobre os nomes
(identificadores de variáveis, de parâmetros, de funções, de procedimentos, etc) definidos no programa fonte. Essa
tabela associa atributos (tipo, escopo, limites no caso de vetores e número de parâmetros no caso de funções) aos
nomes que foram definidos pelo programador. A construção dessa tabela, em geral, se dá durante a análise léxica,
quando os identificadores são reconhecidos.
Quando um identificador é encontrado pela primeira vez, o analisador léxico armazena-o na tabela sem condições
ainda de associar atributos a esse identificador. Geralmente essa tarefa é executada durante as fases de análise
sintática e semântica.
Existem vários modos de se organizar e acessar as tabelas de símbolos sendo, os mais comuns:
1) Listas lineares - é o mecanismo mais simples, mas seu desempenho é pobre quando o número de consultas é
elevado.
2) Árvores binárias
3) Tabelas hash - têm melhor desempenho, mas exigem mais memória e esforço de programação.
Análise sintática 10
Análise sintática
Exemplo da análise sintática de uma expressão matemática. O
resultado é uma árvore da expressão
Análise sintática (também conhecido pelo termo em
inglês parsing) é o processo de analisar uma sequência
de entrada (lida de um arquivo de computador ou do
teclado, por exemplo) para determinar sua estrutura
gramatical segundo uma determinada gramática formal.
Essa análise faz parte de um compilador, junto com a
análise léxica e análise semântica. A análise sintática,
ou análise gramatical é o processo de se determinar se
uma cadeia de símbolos léxicos pode ser gerada por
uma gramática.
A análise sintática transforma um texto na entrada em uma estrutura de dados, em geral uma árvore, o que é
conveniente para processamento posterior e captura a hierarquia implícita desta entrada. Através da análise léxica é
obtido um grupo de tokens, para que o analisador sintático use um conjunto de regras para construir uma árvore
sintática da estrutura.
Em termos práticos, pode também ser usada para decompor um texto em unidades estruturais para serem organizadas
dentro de um bloco, por exemplo.
A vasta maioria dos analisadores sintáticos implementados em compiladores aceitam alguma linguagem livres de
contexto para fazer a análise. Estes analisadores podem ser de vários tipos, como o LL, LR e SLR.
Tipos de analisadores sintáticos
A tarefa do analisador sintático (um algoritmo, programa de computador ou componente de software que se preze a
realizar uma análise sintática) é essencialmente a de determinar se uma entradade dados pode ser derivada de um
símbolo inicial com as regras de uma gramática formal. Isso pode ser feito de duas maneiras:
• Descendente (top-down) - um analisador pode iniciar com o símbolo inicial e tentar transformá-lo na entrada de
dados. Intuitivamente, o analisador inicia dos maiores elementos e os quebra em elementos menores. Exemplo:
analisador sintático LL.
• Ascendente (bottom-up) - um analisador pode iniciar com um entrada de dados e tentar reescrevê-la até o símbolo
inicial. Intuitivamente, o analisador tentar localizar os elementos mais básicos, e então elementos maiores que
contêm os elementos mais básicos, e assim por diante. Exemplo: analisador sintático LR.
Determinismo
Analisadores sintáticos são determinísticos se sempre souberem que ação tomar independentemente da entrada de
texto. Este comportamento é desejado e esperado na compilação de uma linguagem de programação. No campo de
processamento de linguagem natural, pensava-se que essa a análise sintática determinística era impossível devido à
ambiguidade inerente das linguagens naturais, em que diversas sentenças possuem mais de uma possível
interpretação. Entretanto, Mitch Marcus propôs em 1978 o analisador sintático Parsifal, que consegue lidar com
ambiguidades ainda que mantendo o comportamento determinístico.
Análise sintática 11
Funcionamento
Um analisador sintático para uma gramática G é um programa que aceita como entrada uma sentença (uma lista de
símbolos S) e constrói para a sentença sua árvore gramatical (ou equivalentemente uma seqüência de derivação) ou,
caso a sentença não pertença à linguagem descrita por G, uma indicação de erro.
Duas técnicas básicas para a construção de analisadores sintáticos são a construção ascendente ou a construção
descendente. Na construção ascendente (bottom-up), o analisador sintático varre a sentença buscando aplicar
produções que permitam substituir seqüências de símbolos da sentença pelo lado esquerdo das produções, até
alcançar como único símbolo restante o símbolo inicial da gramática.
O Algoritmo a seguir ilustra a estratégia de reconhecimento de sentença baseado em construção ascendente da árvore
sintática. Esse algoritmo recebe como entrada uma representação da gramática G e a lista S de símbolos terminais
que compõem a sentença. A saída é uma indicação se a sentença S pertence (true) ou não (false) à gramática G. Para
a descrição desse algoritmo, as seguintes funções são definidas:
que recebe uma gramática G como argumento e retorna o seu símbolo sentencial; e
MATCH(G, ) retorna uma nova lista de símbolos gerada a partir da aplicação de alguma regra de G à sentença S.
Para tanto, esse procedimento analisa se para a sentença S, composta pela seqüência de símbolos x1x2...xn 
(onde eventualmente e podem ser a cadeia vazia), há na gramática alguma produção aplicável 
x1x2...xn. Se houver, o valor de retorno do procedimento é a lista ; caso contrário, o procedimento retorna
uma lista vazia.
Na construção descendente (top-down), o objetivo é iniciar a análise com uma lista que contém inicialmente apenas
o símbolo sentencial; a partir da análise dos símbolos presentes na sentença, busca-se aplicar regras que permitam
expandir os símbolos na lista até alcançar a sentença desejada.
Na construção descendente, o objetivo é obter uma derivação mais à esquerda para uma sentença. Em termos de
árvores gramaticais, a construção descendente busca a construção de uma árvore a partir da raiz usando pré-ordem
para definir o próximo símbolo não-terminal que deve ser considerado para análise e expansão.
Pela forma como a técnica de construção descendente opera, ela não pode ser aplicada a gramáticas com produções
recursivas à esquerda, ou seja, que contenham regras da forma:
A A 
A limitação é que a análise descendente de tal tipo de produção poderia levar a uma recursão infinita na análise pela
tentativa de expandir sempre a mesma regra sem consumir símbolo algum da entrada.
É possível transformar uma produção recursiva à esquerda em uma recursiva à direita que descreve as mesmas
sentenças através da seguinte técnica. Sejam e duas seqüências de símbolos que não sejam iniciadas pelo
símbolo não-terminal A e sejam as produções para A:
A A A 
Através da introdução de um novo símbolo não-terminal A’, as mesmas sentenças descritas pelas produções acima
podem ser descritas pelas produções recursivas à direita:
A A’
A’ A’
A’ 
Nos dois casos, as sentenças são formadas por uma ocorrência de no início seguida por zero ou mais ocorrências
de .
Os primeiros compiladores usavam essencialmente dois tipos de analisadores sintáticos. Analisadores baseados em
precedência de operadores utilizam a técnica de construção ascendente combinada com informação sobre a
precedência e associatividade de operadores da linguagem para guiar suas ações, sendo adequados à análise de
Análise sintática 12
expressões aritméticas. Analisadores do tipo descendentes recursivos implementam a técnica de construção
descendente através de um conjunto de rotinas mutuamente recursivas para realizar a análise, sendo normalmente
utilizados para outros comandos que não expressões aritméticas.
Analisador sintático preditivo
Esta seção descreve a construção de um analisador sintático baseado na técnica de construção descendente. Este
programa, que realiza a análise sintática preditiva não recursiva, recebe como argumentos uma descrição da
gramática G e a sentença S, expressa na forma de uma lista de símbolos terminada com um símbolo delimitador $,
não-pertencente aos símbolos da gramática.
O ponto crítico nesse procedimento é saber escolher, dado um símbolo não-terminal que pode ser expandido e os
próximos símbolos da sentença, qual deve ser a produção da gramática que deve ser aplicada na expansão. A tabela
sintática para a gramática, cuja construção é descrita na seqüência, contém essa informação essencial à execução do
algoritmo.
Construção da tabela sintática
A tabela sintática é a estrutura de apoio ao reconhecimento de sentenças pela técnica de construção descendente que
tem como chave um par de símbolos. O primeiro componente da chave é um símbolo não-terminal, que corresponde
ao símbolo que estará sendo analisado pelo algoritmo de reconhecimento da sentença. O segundo componente da
chave é um símbolo da sentença, ou seja, um símbolo terminal ou o delimitador de fim de seqüência $. O valor
associado a esse par de símbolos é a produção da gramática a ser aplicada para prosseguir com o reconhecimento da
sentença.
Para construir a tabela sintática para uma gramática qualquer G, deve-se analisar cada uma das produções A 
de G. Inicialmente, deve-se obter o conjunto de símbolos terminais que podem iniciar uma cadeia a partir de S. Se S
for um símbolo terminal, então esse conjunto é composto apenas por esse próprio símbolo. Caso contrário, as
possíveis expansões de S devem ser analisadas até que os símbolos terminais ou a string vazia sejam alcançados.
Caso símbolos terminais sejam alcançados, a tabela sintática recebe a entrada com o valor A para cada chave
A,t onde t é cada um dos símbolos terminais que podem ser alcançados desde S. Caso a string vazia seja um dos
resultados possíveis para a expansão de S, é preciso analisar também as possíveis expansões dos símbolos à direita
do símbolo corrente na produção.
O cômputo de STF pode também ser aplicado a uma cadeia de símbolos, sendo que neste caso o valor resultante é o
primeiro cômputo de STF aplicado a cada símbolo da seqüência tal que o resultado não tenha sido . Caso o
cômputo de STF para todos os símbolos da cadeia resulte em , este também será o resultado final.
O outro procedimento auxiliar deve computar, para cada símbolo não-terminal da gramática G, o conjunto de
símbolos terminais que podem estar imediatamente à direita do símbolo especificado em alguma forma sentencial.
Essa informação é mantida em uma lista seguinte( ), onde S é osímbolo de interesse. Para construir essas listas,
as seguintes regras devem ser aplicadas até que se esgotem as possibilidades de acrescentar algo às listas:
Regra 1: O símbolo sentencial da gramática pode ter como próximo símbolo o delimitador de fim de sentença; insira
o símbolo $ na lista seguinte( (G)).
Regra 2: Se existir uma produção em G da forma A B , então todos os símbolos terminais que podem
iniciar a expansão de podem aparecer após B; insira em seguinte(B) o conteúdo de STF( ) sem incluir , se
estiver presente.
Regra 3: Se existir uma produção em G da forma A B, então B termina a expansão de A. O mesmo pode
ocorrer para uma produção da forma A B onde a expansão de pode levar à string vazia . Em
qualquer um desses casos, tudo que está em seguinte(A) deve ser incluído em seguinte(B).
Análise sintática 13
Com esses procedimentos, a construção da tabela sintática para uma gramática G procede como se segue. Para cada
produção A em G:
1. Compute STF(G, ). Para cada símbolo x dessa lista, acrescente a produção A como o valor da tabela para
o par de chaves [A,x].
2. Caso STF(G, ) contenha , acrescente a produção A à tabela para o par de chaves [A,y] para cada y em
seguinte(A).
Como exemplo, considere a construção do analisador sintático preditivo para a gramática vista anteriormente. Como
essa gramática é recursiva à esquerda, o primeiro passo nessa construção é construir a gramática equivalente sem
esse tipo de recursão. O resultado da aplicação da técnica para eliminar a recursão à esquerda resulta na seguinte
gramática:
E TE'
E' +TE'
E' 
T FT'
T' xFT'
T' 
F (E)
F id
Para esta gramática, o cômputo de STF() para cada um dos símbolos não-terminais resulta em:
STF(E) = STF (T) = STF (F) = (,ID
STF (E') = +, 
STF (T') = $, 
Como STF() para um símbolo terminal é o próprio símbolo, esses valores não são aqui apresentados.
A aplicação das regras para a construção das listas seguinte() resulta, para cada símbolo não-terminal:
seguinte(E) = seguinte(E') =$,)
seguinte(T) = seguinte(T') = +,$,)
seguinte(F) = x,+,$,)
A construção da tabela sintática para essa gramática analisa cada uma das suas produções:
P1. E TE'
Para essa produção, STF(TE')= STF(T), que resulta na lista com os símbolos ( e id. Portanto, na tabela sintática as
entradas [E,(] e [E,id] farão referência à produção P1.
P2. E' +TE'
O cômputo de STF(+TE') resulta em +, ou seja, haverá uma referência para P2 na entrada [E',+] da tabela sintática.
P3. E' 
STF( )= ; portanto, a segunda regra para a construção da tabela deve ser aplicada. Como seguinte(E')=$,), as
entradas correspondentes à [E',$] e [E',)] farão referência à produção P3.
P4. T FT'
Como STF(FT')= STF(F)=(,id, as entradas para [T,(] e [T,id] farão referência à P4.
P5. T' xFT'
Neste caso, STF(xFT')=x. Portanto, a entrada [T',x] terá a referência para P5.
P6. T' 
Análise sintática 14
Novamente a segunda regra deve ser aplicada. Como seguinte(T')=+,$,), as entradas com referência à P6 na tabela
serão [T',+], [T',$] e [T',)].
P7. F (E)
Apenas a entrada [F,(] fará referência a esta produção, pois STF((E))= (.
P8. F id
Apenas a entrada [F,id] fará referência a esta produção, pois STF(id)= id.
Para algumas gramáticas, pode ser que a tabela sintática apresente mais que uma produção por chave, o que reduz a
aplicabilidade desse tipo de analisador –– seria necessário manter um registro do estado do analisador em pontos de
múltipla escolha para eventualmente retornar a esse estado e tentar a outra alternativa, em caso de insucesso na
escolha anterior. Gramáticas ambíguas e gramáticas recursivas à esquerda são exemplos de gramáticas que
produziriam tabelas sintáticas com múltiplas produções para uma chave de par de símbolos.
Gramáticas com tabelas sintáticas sem múltiplas definições são denominadas gramáticas LL(1), indicando que a
varredura da sentença ocorre da esquerda para a direita (Left-to-right) e que é utilizada a derivação canônica mais à
esquerda (Leftmost derivation). O número entre parênteses indica quantos símbolos da sentença precisam ser
analisados (lookahead) para a tomada de decisão no processo de reconhecimento.
Uma gramática com duas produções A e A é LL(1) se apresentar as seguintes propriedades:
1. S e não podem derivar ao mesmo tempo seqüências que tenham início pelo mesmo símbolo terminal; 2.
Apenas um dos dois, S ou , podem derivar ; e 3. Se uma das produções deriva , a outra não pode derivar
qualquer seqüência de símbolos que tenha início com um símbolo presente em seguinte(A).
Geradores de analisadores sintáticos
Como ocorre na construção de analisadores léxicos, a construção de programas analisadores sintáticos é usualmente
suportada por ferramentas para a geração automática de programas a partir de uma especificação.
Uma tradicional ferramenta de criação de analisadores sintáticos é o yacc (Yet Another Compiler-Compiler), oriunda
do ambiente de desenvolvimento de software do sistema operacional Unix. Assim como a ferramenta lex, yacc
recebe como entrada um arquivo de especificação de uma gramática e gera como saída um módulo com código-fonte
em C contendo uma rotina que realiza o reconhecimento de sentenças segundo essa gramática.
Especificação da gramática
O arquivo de entrada para o yacc, que por convenção recebe a extensão .y, é estruturado em três seções. Como na
definição de arquivos lex, essas três seções –– definições, regras da gramática e código do usuário –– são separadas
pelos símbolos %%.
A especificação das regras da gramática utiliza uma notação próxima de BNF. A notação BNF (Backus-Naur Form)
introduz uma forma de representação textual para descrever gramáticas livres de contexto. BNF foi inicialmente
desenvolvida para especificar a linguagem Algol 60.
O principal operador dessa linguagem é o operador binário ::=, que permite descrever as produções da gramática. O
operando do lado esquerdo do operador é o símbolo não-terminal; do lado direito, a sua expansão, que pode conter
símbolos terminais e não-terminais.
Na notação BNF, os símbolos não-terminais são delimitados por colchetes angulares, < e >. Por exemplo, a regra
<expr> ::= (<expr>)
define que uma expressão entre parênteses (o lado direito do operador) pode ser reduzido simplesmente a uma
expressão (o símbolo não-terminal do lado esquerdo).
Análise sintática 15
A notação BNF também introduz um conjunto de operadores destinados a simplificar a representação das regras da
gramática, assim como lex introduz operadores para facilitar a especificação de expressões regulares.
O operador | (ou) permite expressar em uma mesma regra produções alternativas. Por exemplo, a regra
(S) ::= A|B
equivale às duas regras
(S) ::= A (S) ::= B
O operador [ ] (opcional) permite expressar zero ou uma ocorrência do símbolo especificado. Por exemplo, a regra
(S) ::= [a]
equivale a
(S) ::= (S) ::= a
O operador ( | ) (fatoração) permite expressar a combinação de símbolos alternativos, como em
(S) ::= a(b|c)d
que equivale a
(S) ::= abd (S) ::= acd
O operador * (repetição), assim como para expressões regulares, expressa 0 ou mais ocorrências do símbolo. Por
exemplo, a regra
(S) ::= a*
equivale a
(S) ::= (S) ::= a(S)
Assim, a ocorrência do padrão no lado direito de uma produção equivale a
|a|aa|aaa|aaaa|..... O operador {||}* (concatenação) permite expressar a repetição múltipla de símbolos
concatenados. Por exemplo, a regra
(S) ::= {A||B}*
equivale a
(S) ::= A(t) (t) ::= (t) ::= BA(t)
Cada produção no yacc é expressa na forma:
simb : exp ;
onde simb é um símbolo não terminal e exp é a sua expansão em termos de outros símbolos da gramática. A
expansão pode conter símbolos terminais e não-terminais, que por convenção são representados usando letras
maiúsculas e minúsculas, respectivamente.
Pelas características de gramáticas livres de contexto, a expansão pode ser recursiva, isto é, conter o próprio símbolo
que está sendo definido, como em
expr : expr '+'expr ;
Porém, pelo menos uma expansão para esse símbolo deve ser não-recursiva:
expr : IDENT ;
Em caso de definição recursiva, pelas características do analisador gerado (LR(1)) recomenda-se optar quando
possível pela recursão à esquerda.
Produções para um mesmo símbolo podem ser agrupadas usando o símbolo '|',
 expr : expr + expr
 | IDENT
 ;
Análise sintática 16
Expansões para a cadeia vazia podem ser definidas; por convenção e para tornar mais clara a definição, essa
expansão é destacada na forma de um comentário C:
 retv : /* empty */
 | expr
 ;
O símbolo sentencial da gramática pode ser estabelecido na seção de definições através da declaração start, como em
 %start expr
Na ausência dessa declaração, o símbolo não-terminal cuja expansão é definida na primeira produção da seção de
regras da gramática é assumido ser o símbolo sentencial.
Outros tipos de declaração que podem estar presentes na primeira seção são declarações em C, colocadas entre os
símbolos %{ e %}, e a definição dos nomes de tipos de tokens, os quais serão usados posteriormente nas expansões
das produções.
Tokens que são representados por um único caractere, como '+' ou ';', não precisam ser declarados e podem ser
usados dessa forma (como constantes do tipo caractere em C) nas expansões; os demais tokens precisam ser
explicitamente declarados. Para tanto, a declaração token pode ser utilizada, como em
 %token IDENT
Alternativamente, tokens para operadores podem ser definidos com uma especificação de associatividade usando, ao
invés de token, as declarações left, right ou nonassoc. Uma declaração
 %left OP
determina que uma expressão A OP B OP C será interpretada como (A OP B) OP C, enquanto que se a declaração
tivesse sido
 %right OP
a interpretação seria A OP (B OP C). A declaração
 %nonassoc OP
determinaria que a expressão A OP B OP C estaria incorreta, pois o operador não é associativo.
A precedência dos operadores também é definida através dessas declarações. Operadores definidos através da mesma
linha de declaração, como
 %left OP1 OP2 
têm a mesma precedência. Para aqueles definidos em linhas distintas, as últimas declarações têm maior precedência.
O símbolo terminal error é pré-definido, podendo ser utilizado como a última expansão de um símbolo caso a
aplicação deseje determinar um curso de ação específico em uma situação de não-reconhecimento de uma sentença a
partir das expansõbix previamente definidas para o símbolo.
Análise sintática 17
Manipulação das sentenças reconhecidas
Reconhecer que uma seqüência de símbolos é uma sentença válida em uma gramática, é parte essencial do processo
de compilação, porém pouco uso seria se simplesmente uma indicação de validade fosse retornada sem nenhuma
possibilidade de manipulação adicional das expressões. No caso do yacc, essa possibilidade está associada à
definição de ações semânticas.
Uma ação semântica em yacc é definida através de um bloco de expressões em C associado à definição de produções
para um símbolo não-terminal:
 symb : expansão { ação } ;
A definição do corpo da ação pode conter referências aos valores semânticos de cada um dos símbolos da produção.
O valor semântico de um token está associado a um valor associado ao símbolo, que pode ser por exemplo um valor
numérico de uma constante ou a string associada a um identificador.
O valor semântico do token pode ser referenciado na expressão C através de pseudo-variáveis com nome $i, onde i
determina a posição do token na expansão. A variável $$ referencia o valor semântico resultante para o símbolo
sendo definido. Por exemplo:
 expr : expr '+' expr
 { $$ = $1 + $3 }
 ;
atribui à expressão reduzida o valor semântico que é a soma dos valores semânticos do primeiro e do terceiro
componente da expansão, que estão separados pelo segundo componente, '+'.
Se nenhuma ação for definida para uma produção, a ação semântica padrão -- { $$ = $1; } é assumida.
O tipo associado a valores semânticos é definido pela macro YYSTYPE, que é inicialmente definida como int. Para
modificar esse padrão, pode-se modificar essa definição através de uma declaração C na primeira seção do arquivo
que define a gramática. Por exemplo:
 %{
 #define YYSTYPE double
 %}
Em aplicações que necessitem manipular tokens com diferentes tipos de valores semânticos, a declaração union deve
ser utilizada para definir quais são os tipos de valores possíveis. Por exemplo, em uma aplicação que manipula
valores inteiros e reais a seguinte declaração estaria presente:
 %union {
 int ival;
 double fval;
 }
Essa declaração determina que a coleção de tipos de valores permitidos é composta por valores com nome ival ou
fval, respectivamente para valores inteiros e reais –– no código C, uma união será criada. Esses mesmos nomes são
utilizados para qualificar a definição de tokens da gramática, como em
 %token <ival> INTEGER
 %token <fval> REAL
Quando uma coleção de tipos de valores é utilizada, é preciso determinar também qual o tipo para o símbolo
não-terminal para o qual a expressão está sendo reduzida. Para esse fim, yacc define a declaração type:
 %type <fval> expr
Tradução dirigida por sintaxe 18
Tradução dirigida por sintaxe
Tradução dirigida por sintaxe é uma técnica de especificação de compiladores tradutores que permite associar
ações semânticas às regras da gramática. Essa técnica é utilizada em quase todos os compiladores modernos.
Nesta tradução do código de alto nível para o do processador está a associação para traduzir para a linguagem-alvo,
obtida para as diversas expressões do program, a representação da árvore Gramatical.
Embora tal atividade possa ser realizada ao fim da análise sintática para toda árvore, ela é realmente concluída com
as ações semânticas, numa associação à aplicação das regras de reconhecimento do analisador sintático.
Para se gerar o código, não é necessário ir diretamente para a linguagem assembly do processador-alvo, pois o
analisador sintático gera o mesmo com uma linguagem próxima para uma máquina abstrata, isso independente de
processadores específicos. Depois esse código produzido traduz para a linguagem assembly desejada que se deseja.
Ganha-se que grande parte do compilador é liberada para ser reaproveitada em trabalhos de tipos de processadores
díspares.
Na tradução dirigida pela sintaxe assume-se que os terminais tenham somente atributos sintetizados quando as
definições não apresentam nenhuma regra semântica . Esses atributos são bastante usados na prática, onde uma
sintaxe com os mesmos é chamada de definição S-atribuída.
Os valores para os atributos dos terminais geralmente são fornecidos por este léxico:
F ->dígito F.val= dígito.lexval
Eles costumam ser avaliados de baixo para cima, das folhas para a raiz.
Em resumo:
> É uma tradução de linguagens guiada por gramáticas livres de contexto;
> faz uma amarração de atributos, que representam valores (tipo, endereço, etc.), aos símbolos gramaticais de regras
de produção, onde são representada as construções de linguagens;
> Faz associação de regras semânticas às produções, a fim de realizar cálculos dos valores de atributos amarrados.
Definições Dirigidas pela Sintaxe
São definições que usam uma gramática livre, onde cada símbolo gramatical possui um conjunto associado de
atributos.
Atributos do Símbolo
•• Sintetizados: O valor é computado a partir dos valores dos atributos dos filhos do nó.
•• Herdados: O valor é computado a partir dos valores dos atributos do pai e dos irmãos do nó.
Formas de Representação Intermediária
Normalmente a tradução do programa fonte no programa objeto é feita em dois passos, e uma representação
intermediária do programa fonte deve ser construída. Tipicamente, essa representação intermediária assume uma de
duas formas: uma árvore (árvore sintática) ou umaseqüência de comandos em uma linguagem intermediária, cuja
forma mais comum é a de quádruplas, ou seja, de comandos compostos de um operador e de três operandos, que
quase sempre são endereços. Por exemplo, o comando de atribuição:
x: = (a+b) * c
Tradução dirigida por sintaxe 19
Árvores Sintáticas
A primeira árvore que se poderia usar como base para uma representação intermediária é a árvore de derivação
correspondente ao programa fonte, de acordo com a gramática da linguagem fonte usada na construção do analisador
sintático. Entretanto, essa árvore de derivação em geral não é conveniente, uma vez que inclui muitos detalhes
desnecessários, que foram incluídos na sintaxe da linguagem fonte para resolver problemas de ambigüidade,
precedência, pontuação, clareza, legibilidade, etc. Por essa razão, em alguns casos é conveniente a definição de uma
segunda sintaxe, chamada sintaxe abstrata, que ignora todos os aspectos não essenciais da sintaxe original, conhecida
como sintaxe concreta.
Análise semântica
Chama-se análise semântica a terceira fase da compilação, onde se verificam os erros de semântica no código fonte
e se faz a coleta das informações necessárias para a próxima fase da compilação, a geração de código objeto. O
objetivo da análise semântica é trabalhar no nível de inter-relacionamento entre partes distintas do programa[1].
Objetivo da Análise Semântica
A análise sintática verifica e aponta as expressões que quebram qualquer regra determinada pela gramática. Mas o
nível de complexidade aumenta quando tratamos de liguagens dependentes de contexto. A análise semântica busca
apontar (não resolver) este tipo de erros (dependentes de contexto).
O objetivo da análise semântica é, assim, criar, a partir de um texto-fonte, uma interpretação expressa em alguma
notação adequada - geralmente uma linguagem intermediária do compilador. Isto é feito com base nas informações
das tabelas e nas saídas dos outros analisadores. Denomina-se semântica de uma sentença o significado por ela
assumido dentro do contexto em que se encontra. Semântica de uma linguagem é a interpretação que se pode atribuir
ao conjunto de todas as suas sentenças.
A análise semântica utiliza-se da verificação de tipos para verificar se um determinado operando recebe outro
operando de mesmo tipo. Um exemplo comum nas linguagens de programação é a análise semântica retornar um
erro quando uma variável do tipo numérica (real ou inteira) receber um valor tipo texto (string).
Um compilador usa uma tabela de símbolos (TS) para guardar informações sobre os nomes declarados em um
programa. A TS é pesquisada cada vez que um nome é encontrado no programa fonte. Alterações são feitas na TS
sempre que um novo nome ou nova informação sobre um nome já existente é obtida. A gerência da TS de um
compilador deve ser implementada de forma a permitir inserções e consultas da forma mais eficiente possível, além
de permitir o crescimento dinâmico da mesma.Cada entrada na ts é a declaração de um nome. Cada entrada na ts
pode ser implementada como um registro ( record ou struct) contendo campos (nome, tipo, classe, tamanho, escopo,
etc.) que a qualificam.
Exemplos típicos de erros semânticos são:
•• Uma variável não declarada
•• Uma multiplicação entre tipos de dados diferentes
•• Atribuição de um literal para outro tipo, como um inteiro em uma string ou vice-versa.
Análise semântica 20
Checagem de Tipo
O processo de verificação dos tipos ocorre em tempo de compilação (checagem estática) ou em tempo de execução
(checagem dinâmica). As linguagens de programação conforme a especificação da linguagem podem ser referidas
como de tipagem forte e tipagem fraca, influenciando o processo de checagem de tipo.
Tipagem estática
É quando acontece durante a copilação, pode ser por meio de alocação, desalocação de variaveis locais ou descoberta
de tipos em expressões numericas.
Tipagem dinâmica
É quando acontece durante a execução, pode ser por meio de alocação na heap com malloc (em C), verificação de
cast de classe (em java), ou verificação de limites de arrays (em java).
Bibliografia e referências
Referências
[1] http:/ / www. dca. fee. unicamp. br/ cursos/ EA876/ apostila/ HTML/ node71. html
Bibliografia
• Análise semântica- Programação de Sistemas- Ivan Luiz Marques Ricarte (http:/ / www. dca. fee. unicamp. br/
cursos/ EA876/ apostila/ HTML/ node71. html)
• Uso de Prolog no Desenvolvimento de Compiladores - Arquiteturas Especiais de Computadores - André Luis
Martinotto (http:/ / www. inf. ufrgs. br/ procpar/ disc/ cmp135/ trabs/ martinotto/ trabII/ semantica. htm)
Esta página é somente um esboço.
Ampliando-a você ajudará a melhorar o Wikilivros.
Geração de código intermediário 21
Geração de código intermediário
Tomando um compilador como um modelo de análise-e-síntese, podemos considerar que seus módulos iniciais
("front-end modules") traduzem um programa fonte em uma representação (linguagem) intermediária, a partir da
qual seus módulos finais ("back-end modules") geram o código objeto final.
A geração de um código intermediário requer um passo a mais para a tradução, tornando o processo um pouco mais
lento. Embora um programa fonte possa ser traduzido diretamente para a linguagem objeto, o uso de uma
representação intermediária, independente de máquina, tem as seguintes vantagens:
1.1. Reaproveitamento de código, facilitando o transporte de um compilador para diversas plataformas de hardware;
somente os módulos finais precisam ser refeitos a cada transporte.
2.2. Um otimizador de código independente de máquina pode ser usado no código intermediário.
Pode-se pensar nessa representação intermediária como um programa para uma máquina abstrata. A representação
intermediária deve possuir duas propriedades importantes: ser fácil de produzir e fácil de traduzir no programa alvo.
A diferença básica entre o código intermediário e o código objeto final é que não são especificados detalhes da
máquina alvo, tais como quais registradores serão usados, quais endereços de memória serão referenciados, etc.
Tipos de código intermediário
• HIR – High Intermediate Representation
•• Usada nos primeiros estágios do compilador
•• Simplificação de construções gramaticais para somente o essencial para otimização/geração de código
• MIR – Medium Intermediate Representation
•• Boa base para geração de código eficiente
•• Pode expressar todas características de linguagens de programação de forma independente da linguagem
•• Representação de variáveis, temporários, registradores
• LIR – Low Intermediate Representation
•• Quase 1-1 para linguagem de máquina
•• Dependente da arquitetura
Representação
As formas de representação mais comuns dos tipos de códigos intermediários são:
•• HIR
•• Árvore e grafo de sintaxe
•• Notações Pós-fixada e Pré-fixada
•• Representações linearizadas
•• MIR
•• Árvore e grafo de sintaxe
•• Notações Pós-fixada e Pré-fixada:
•• Representações linearizadas
•• Código de três endereços:
•• Quádruplas
•• Triplas
•• Grafos acíclicos dirigidos (DAG)
•• LIR
Geração de código intermediário 22
•• Instruções assembler
Geração de código
A tradução do código de alto nível para o código do processador está associada a traduzir para a linguagem-alvo a
representação da árvore gramatical obtida para as diversas expressões do programa. Embora tal atividade possa ser
realizada para a árvore completa após a conclusão da análise sintática, em geral ela é efetivada através das ações
semânticas associadas à aplicação das regras de reconhecimento do analisador sintático. Este procedimento é
denominado tradução dirigida pela sintaxe.
Em geral, a geração de código não se dá diretamente para a linguagem assembly do processador-alvo. Por
conveniência, o analisador sintático gera código para uma máquina abstrata, com uma linguagem próxima ao
assembly, porém independente de processadoresespecíficos. Em uma segunda etapa da geração de código, esse
código intermediário é traduzido para a linguagem assembly desejada. Dessa forma, grande parte do compilador é
reaproveitada para trabalhar com diferentes tipos de processadores.
Várias técnicas e várias tarefas se reúnem sob o nome de Otimização. Alguns autores da literatura consideram que,
para qualquer critério de qualidade razoável, é impossível construir um programa “otimizador”, isto é, um programa
que recebe como entrada um programa P e constrói um programa P’ equivalente que é o melhor possível, segundo o
critério considerado. O que se pode construir são programas que melhoram outros programas, de maneira que o
programa P’ é, na maioria das vezes, melhor, segundo o critério especificado do que o programa P original. A razão
para essa impossibilidade é a mesma que se encontra quando se estuda, por exemplo em LFA (Linguagens Formais e
Autômatos), o “problema da parada”: um programa (procedimento, máquina de Turing, etc.) não pode obter
informação suficiente sobre todas as possíveis formas de execução de outro programa (procedimento, máquina de
Turing, etc.).
Normalmente, é muito fácil fazer uma otimização em um programa, ou seja, uma transformação que o transforma
em outro melhor. O difícil é sempre obter a informação necessária que garante que a otimização pode realmente ser
aplicada, sem modificar em nenhum caso o funcionamento do programa.
Não é prático tentar otimizar um programa tentando sucessivamente eliminar todos os seus comandos, um de cada
vez. Note que as condições para cada eliminação dependem do comando, de sua posição, e, de certa maneira, de
todos os comandos restantes do programa. Para construir um otimizador de utilidade na prática, faz-se necessário
identificar oportunidades para otimização que sejam produtivas em situações correntes.
Outro exemplo de otimização que é citado freqüentemente é a retirada de comandos de um comando de repetição
(um loop). Por exemplo, um comando cujo efeito é independente do loop, pode valer a pena retirá-lo do loop, para
que ele seja executado apenas uma vez, em vez das muitas vezes que se presume que será executado o código de
dentro do loop.
Depende muito da finalidade de um compilador o conjunto de otimizações que ele deve oferecer. Um compilador
usado em um curso introdutório de programação não precisa de otimização, porque os programas são executados
quase sempre apenas uma vez. (Em vez de otimização, este compilador deveria dar boas mensagens de erro, que
pudessem auxiliar os principiantes na linguagem.) Por outro lado, um programa que vai ser compilado uma vez e
executado muitas vezes deve ser otimizado tanto quanto possível. Neste caso estão programas de simulação, de
previsão do tempo, e a maioria das aplicações numéricas.
Um outro problema na otimização de código para um compilador é a quantidade de informação que se deseja
manipular. Pode-se examinar otimizações locais (em trechos pequenos de programas, por exemplo trechos sem
desvios, ou seja, trechos em linha reta), otimizações em um nível intermediário (as otimizações são consideradas
apenas em funções, módulos, ou classes, dependendo da linguagem) e otimizações globais (que consideram as
inter-relações de todas as partes de um programa). A maioria dos compiladores oferece algumas otimizações do
primeiro tipo, possivelmente combinadas com a fase de geração de código, e quando muito algumas otimizações de
Geração de código intermediário 23
nível intermediário.
A maneira de tratar a otimização pode ser extremamente pragmática. Em um programa grande, a execução gasta
90% em 10% do código, e 10% do tempo nos 90% do código restantes (A literatura menciona valores de 90%-10%
até 70%-30%.). Isto acontece porque em geral um programa é constituído de inicializações e finalizações, entre as
quais se encontra um conjunto de vários loops aninhados. O tempo maior de execução (“os 90%”) é gasto no loop
mais interno (“os 10%”). Existem ferramentas que registram o perfil de execução do programa (profilers), permitindo
a identificação dos trechos mais executados, e a otimização pode se concentrar nestes trechos, ignorando para fins de
otimização o restante do programa. Por essa razão muitos compiladores oferecem opções de compilação que podem
ser ligadas e desligadas no código fonte, indicando para o compilador os trechos que o programador considera
importantes o suficiente para serem otimizados. Por estas razões, muito do trabalho no desenvolvimento de técnicas
de otimização é dedicado aos loops.
Código intermediário
A linguagem utilizada para a geração de um código em formato intermediário entre a linguagem de alto nível e a
linguagem assembly deve representar, de forma independente do processador para o qual o programa será gerado,
todas as expressões do programa original. Duas formas usuais para esse tipo de representação são a notação posfixa e
o código de três endereços.
Código de três endereços
O código de três endereços é composto por uma seqüência de instruções envolvendo operações binárias ou unárias e
uma atribuição. O nome "três endereços está associado à especificação, em uma instrução, de no máximo três
variáveis: duas para os operadores binários e uma para o resultado. Assim, expressões envolvendo diversas
operações são decompostas nesse código em uma série de instruções, eventualmente com a utilização de variáveis
temporárias introduzidas na tradução. Dessa forma, obtém-se um código mais próximo da estrutura da linguagem
assembly e, conseqüentemente, de mais fácil conversão para a linguagem-alvo.
Uma possível especificação de uma linguagem de três endereços envolve quatro tipos básicos de instruções:
expressões com atribuição, desvios, invocação de rotinas e acesso indexado e indireto.
Instruções de atribuição são aquelas nas quais o resultado de uma operação é armazenado na variável especificada à
esquerda do operador de atribuição, aqui denotado por :=. Há três formas para esse tipo de instrução. Na primeira, a
variável recebe o resultado de uma operação binária:
 x := y op z
O resultado pode ser também obtido a partir da aplicação de um operador unário:
 x := op y
Na terceira forma, pode ocorrer uma simples cópia de valores de uma variável para outra:
 x := y
Por exemplo, a expressão em C
a = b + c * d;
seria traduzida nesse formato para as instruções:
 _t1 := c * d
 a := b + _t1
As instruções de desvio podem assumir duas formas básicas. Uma instrução de desvio incondicional tem o formato
Geração de código intermediário 24
 goto L
onde L é um rótulo simbólico que identifica uma linha do código. A outra forma de desvio é o desvio condicional,
com o formato
 if x opr y goto L
onde opr é um operador relacional de comparação e L é o rótulo da linha que deve ser executada se o resultado da
aplicação do operador relacional for verdadeiro; caso contrário, a linha seguinte é executada.
Por exemplo, a seguinte iteração em C
while (i++ <= k) 
 x[i] = 0;
x[0] = 0;
poderia ser traduzida para
_L1: if i > k goto _L2
 i := i + 1
 x[i] := 0 
 goto _L1
_L2: x[0] := 0
A invocação de rotinas ocorre em duas etapas. Inicialmente, os argumentos do procedimento são "registrados com a
instrução param; após a definição dos argumentos, a instrução call completa a invocação da rotina. A instrução
return indica o fim de execução de uma rotina. Opcionalmente, esta instrução pode especificar um valor de retorno,
que pode ser atribuído na linguagem intermediária a uma variável como resultado de call.
Por exemplo, considere a chamada de uma função f que recebe três argumentos e retorna um valor:
f(a, b, c);
Neste exemplo em C, esse valor de retorno não é utilizado. De qualquer modo, a expressão acima seria traduzida
para
 param a
 param b
 param c
 _t1 := call f,3
onde o número após a vírgula indica o número deargumentos utilizados pelo procedimento f. Com o uso desse
argumento adicional é possível expressar sem dificuldades as chamadas aninhadas de procedimentos.
O último tipo de instrução para códigos de três endereços refere-se aos modos de endereçamento indexado e indireto.
Para atribuições indexadas, as duas formas básicas são
 x := y[i]
 x[i] := y
As atribuições associadas ao modo indireto permitem a manipulação de endereços e seus conteúdos. As instruções
em formato intermediário também utilizam um formato próximo àquele da linguagem C:
 x := &y
 w := *x
 *x := z
Geração de código intermediário 25
A representação interna das instruções em códigos de três endereços dá-se na forma de armazenamento em tabelas
com quatro ou três colunas. Na abordagem que utiliza quádruplas (as tabelas com quatro colunas), cada instrução é
representada por uma linha na tabela com a especificação do operador, do primeiro argumento, do segundo
argumento e do resultado
Para algumas instruções, como aquelas envolvendo operadores unários ou desvio incondicional, algumas das colunas
estariam vazias.
Na outra forma de representação, por triplas, evita a necessidade de manter nomes de variáveis temporárias ao fazer
referência às linhas da própria tabela no lugar dos argumentos. Nesse caso, apenas três colunas são necessárias, uma
vez que o resultado está sempre implicitamente associado à linha da tabela.
Notação posfixa
A notação tradicional para expressões aritméticas, que representa uma operação binária na forma x+y, ou seja, com o
operador entre seus dois operandos, é conhecida como notação infixa. Uma notação alternativa para esse tipo de
expressão é a notação posfixa, também conhecida como notação polonesa, na qual o operador é expresso após seus
operandos.
O atrativo da notação posfixa é que ela dispensa o uso de parênteses. Por exemplo, as expressões
 a*b+c;
 a*(b+c);
 (a+b)*c;
 (a+b)*(c+d);
seriam representadas nesse tipo de notação respectivamente como
 a b * c +
 a b c + *
 a b + c *
 a b + c d + *
Instruções de desvio em código intermediário usando a notação posfixa assumem a forma
 L jump
 x y L jcc
para desvios incondicionais e condicionais, respectivamente. No caso de um desvio condicional, a condição a ser
avaliada envolvendo x e y é expressa na parte cc da própria instrução. Assim, jcc pode ser uma instrução entre jeq
(desvio ocorre se x e y forem iguais), jne (se diferentes), jlt (se x menor que y), jle (se x menor ou igual a y), jgt (se x
maior que y) ou jge (se x maior ou igual a y).
Expressões em formato intermediário usando a notação posfixa podem ser eficientemente avaliadas em máquinas
baseadas em pilhas, também conhecidas como máquinas de zero endereços. Nesse tipo de máquinas, operandos são
explicitamente introduzidos e retirados do topo da pilha por instruções push e pop, respectivamente. Além disso, a
aplicação de um operador retira do topo da pilha seus operandos e retorna ao topo da pilha o resultado de sua
aplicação.
Por exemplo, a avaliação da expressão a*(b+c) em uma máquina baseada em pilha poderia ser traduzida para o
código
 push a
 push b
 push c
Geração de código intermediário 26
 add
 mult
Otimização de código
A etapa final na geração de código pelo compilador é a fase de otimização. Como o código gerado através da
tradução orientada pela sintaxe contempla expressões independentes, diversas situações contendo seqüências de
código ineficiente podem ocorrer. O objeto da etapa de otimização de código é aplicar um conjunto de heurísticas
para detectar tais seqüências e substituí-las por outras que removam as situações de ineficiência.
As técnicas de otimização que são usadas em compiladores devem, além de manter o significado do programa
original, ser capazes de capturar a maior parte das possibilidades de melhoria do código dentro de limites razoáveis
de esforço gasto para tal fim. Em geral, os compiladores usualmente permitem especificar qual o grau de esforço
desejado no processo de otimização. Por exemplo, em gcc há opções na forma -O... que dão essa indicação, desde
O0 (nenhuma otimização) até -O3 (máxima otimização, aumentando o tempo de compilação), incluindo também
uma opção -Os, indicando que o objetivo é reduzir a ocupação de espaço em memória.
Algumas heurísticas de otimização são sempre aplicadas pelos compiladores. Por exemplo, se a concatenação de
código gerado por duas expressões no programa original gerou uma situação de desvio incondicional para a linha
seguinte, como em
(a)
 goto _L1
_L1: (b)
esse código pode ser seguramente reduzido com a aplicação da técnica de eliminação de desvios desnecessários,
resultando em
 (a)
_L1: (b)
Outra estratégia de otimização elimina os rótulos não referenciados por outras instruções do programa. Assim, se o
rótulo _L1 estivesse sendo referenciado exclusivamente por essa instrução de desvio, ele poderia ser eliminado em
uma próxima aplicação das estratégias de otimização.
As técnicas de otimização podem ser classificadas como independentes de máquina, quando podem ser aplicadas
antes da geração do código na linguagem assembly, ou dependentes de máquina, quando aplicadas na geração do
código assembly.
A otimização independente de máquina tem como requisito o levantamento dos blocos de comandos que compõem o
programa. Essa etapa da otimização é conhecida como a análise de fluxo, que por sua vez contempla a análise de
fluxo de controle e a análise de fluxo de dados. Estratégias que podem ser aplicadas, analisando um único bloco de
comandos são denominadas estratégias de otimização local, enquanto aquelas que envolvem a análise simultânea de
dois ou mais blocos são denominadas estratégias de otimização global.
Algumas estratégias básicas de otimização, além da já apresentada eliminação de desvios desnecessários, são
apresentadas a seguir.
A estratégia de eliminação de código redundante busca detectar situações onde a tradução de duas expressões gera
instruções cuja execução repetida não tem efeito. Por exemplo, em
x := y
 ...
Otimização de código 27
 x := y
se não há nenhuma mudança no valor de y entre as duas instruções, então a segunda instrução poderia ser eliminada.
O mesmo aconteceria se a segunda instrução fosse
y := x
e o valor de x não fosse alterado entre as duas instruções.
Outra estratégia básica é a eliminação de código não-alcançável, ou “código morto”. Por exemplo, se a seguinte
seqüência de código fosse gerada por um conjunto de expressões
...
 goto _L1
 x := y
_L1: ...
a instrução contendo a atribuição de y a x nunca poderia ser executada, pois é precedida de um desvio incondicional
e não é o destino de nenhum desvio, pois não contém um rótulo na linha. Assim, essa linha poderia ser eliminada e
provocar posteriormente a aplicação da estratégia de eliminação de desvios desnecessários.
O uso de propriedades algébricas é outra estratégia de otimização usualmente aplicada. Nesse caso, quando o
compilador identifica que uma expressão aritmética foi reduzida a x=0 ou 0=x ou x-0 ou x*1 ou 1*x ou x/1, então
ele substitui a expressão simplesmente por x. Outra classe de propriedades algébricas que é utilizada tem por
objetivo substituir operações de alto custo de execução por operações mais simples, como
2.0*x = x+x
x2 = x*x
x/2 = 0.5*x
Particularmente no último caso, se x for uma variável inteira a divisão por dois pode ser substituída por um
deslocamento da representação binária à direita de um bit. Genericamente, a divisão inteira por 2n equivale ao
deslocamento à direita de n bits na representação binária do dividendo. Da mesma forma, a multiplicação inteira por
potências de dois pode ser substituída por deslocamento de bits à esquerda.
A utilização de propriedades algébricas permite também o reuso de subexpressões já computadas. Por exemplo, a
traduçãodireta das expressões
 a = b + c;
 e = c + d + b;
geraria o seguinte código intermediário:
 a := b + c
 _t1 := c + d
 e := _t1 + b
No entanto, o uso da comutatividade e associatividade da adição permite que o código gerado seja reduzido usando a
eliminação de expressões comuns, resultando em
 a := b + c
 e := a + d
Diversas oportunidades de otimização estão associadas à análise de comandos iterativos. Uma estratégia é a
movimentação de código, aplicado quando um cálculo realizado dentro do laço na verdade envolve valores
invariantes na iteração. Por exemplo, o comando
Otimização de código 28
 while (i < 10*j) {
 a[i] = i + 2*j;
 ++i;
 }
estaria gerando um código intermediário equivalente a
 _L1: _t1 := 10 * j
 if i >= _t1 goto _L2
 _t2 := 2 * j
 a[i] := i + _t2
 i := i + 1
 goto _L1
 _L2: ...
No entanto, a análise de fluxo de dados mostra que o valor de j não varia entre iterações. Assim, o compilador
poderia mover as expressões que envolvem exclusivamente constantes na iteração para fora do laço, substituindo
esse código por
_t1 := 10 * j
 _t2 := 2 * j
 _L1: if i >= _t1 goto _L2
 a[i] := i + _t2
 i := i + 1
 goto _L1
 _L2: ...
Um exemplo de otimização dependente de máquina pode ser apresentado para a expressão
 x := y + K
onde K é alguma constante inteira. Na tradução para o código assembly de um processador da família 68K, a forma
genérica poderia ser algo como
 MOVE.L y,D0
 ADDI.L #K,D0
 MOVE.L D0,x
No entanto, se o compilador verificasse que o valor de K fosse uma constante entre 1 e 8, então a segunda instrução
assembly poderia ser substituída por ADDQ.L, que utilizaria em sua codificação apenas dois bytes ao invés dos seis
bytes que seriam requeridos pela instrução ADDI.L.
Nomes dos colaboradores 29
Nomes dos colaboradores
Nome dos colaboradores deste wikilivro
Lsd76
Fontes e Editores da Página 30
Fontes e Editores da Página
Capa  Fonte: http://pt.wikibooks.org/w/index.php?oldid=137915  Contribuidores: Jorge Morais, Lsd76, Marcos Antônio Nunes de Moura, 2 edições anónimas
O que é um compilador  Fonte: http://pt.wikibooks.org/w/index.php?oldid=204283  Contribuidores: Jorge Morais, Thiago, 4 edições anónimas
Fases de um compilador  Fonte: http://pt.wikibooks.org/w/index.php?oldid=204280  Contribuidores: Jorge Morais, Thiago, 2 edições anónimas
Teoria das linguagens formais  Fonte: http://pt.wikibooks.org/w/index.php?oldid=244176  Contribuidores: Abacaxi
Linguagens regulares e autômatos finitos  Fonte: http://pt.wikibooks.org/w/index.php?oldid=247646  Contribuidores: Abacaxi, 1 edições anónimas
Linguagens livres de contexto  Fonte: http://pt.wikibooks.org/w/index.php?oldid=244177  Contribuidores: Abacaxi
Análise léxica  Fonte: http://pt.wikibooks.org/w/index.php?oldid=265322  Contribuidores: Abacaxi, 1 edições anónimas
Análise sintática  Fonte: http://pt.wikibooks.org/w/index.php?oldid=244172  Contribuidores: Abacaxi
Tradução dirigida por sintaxe  Fonte: http://pt.wikibooks.org/w/index.php?oldid=244175  Contribuidores: Abacaxi
Análise semântica  Fonte: http://pt.wikibooks.org/w/index.php?oldid=244167  Contribuidores: Abacaxi
Geração de código intermediário  Fonte: http://pt.wikibooks.org/w/index.php?oldid=244171  Contribuidores: Abacaxi
Otimização de código  Fonte: http://pt.wikibooks.org/w/index.php?oldid=244170  Contribuidores: Abacaxi
Nomes dos colaboradores  Fonte: http://pt.wikibooks.org/w/index.php?oldid=204282  Contribuidores: Jorge Morais, Lsd76, Thiago, 1 edições anónimas
Fontes, Licenças e Editores da Imagem 31
Fontes, Licenças e Editores da Imagem
Image:Nt-compilador.png  Fonte: http://pt.wikibooks.org/w/index.php?title=Ficheiro:Nt-compilador.png  Licença: Creative Commons Attribution-Sharealike 2.5  Contribuidores: User:Nuno
Tavares
Image:Nuvola apps konsole.png  Fonte: http://pt.wikibooks.org/w/index.php?title=Ficheiro:Nuvola_apps_konsole.png  Licença: GNU Lesser General Public License  Contribuidores: Alno,
Alphax
Imagem:Parsing-example.png  Fonte: http://pt.wikibooks.org/w/index.php?title=Ficheiro:Parsing-example.png  Licença: GNU Free Documentation License  Contribuidores:
en:User:Nathanfulk
Imagem:Rekopis chopin.jpg  Fonte: http://pt.wikibooks.org/w/index.php?title=Ficheiro:Rekopis_chopin.jpg  Licença: Public Domain  Contribuidores: Andreagrossmann, Kevyn, Maire, Man
vyi, Niki K, Subitosera, Tsca
Licença 32
Licença
Creative Commons Attribution-Share Alike 3.0
//creativecommons.org/licenses/by-sa/3.0/