u1e2 Estrutura de um compilador

Prévia do material em texto

16/08/2017
1
Estrutura de um compilador
Emerson Henrique da Silva
Compiladores
Ciência da computação
A construção de uma linguagem
• Linguagem
• É constituída através da definição de uma Sintaxe e uma semântica;
• Especificação da sintaxe: através de gramáticas livre de contexto
ou BNF (Backus-Naur Form).
• Especificação Semântica: informal (textual), operacional,
denotacional, e de ações.
• Tarefas do compilador:
• Análise: o texto de entrada (na linguagem fonte) é examinado,
verificado e compreendido;
• Síntese: Ou geração de código, em que o texto de saída (na linguagem
objeto) é gerado, de forma a corresponder ao texto de entrada.
16/08/2017
2
Um compilador de uma passagem
• Exemplo:
• Suponha um compilador que deve traduzir 
expressões de notação infixa para posfixa.
• 9 – 5 + 2 → 9 5 – 2 + 
• Aplicação: computação baseada em pilha. 
• Demonstra o princípio para construção mais gerais 
das linguagens.
Retaguarda do compilador
Fluxo de 
caracteres 
de entrada
Analisador 
léxico
Fluxo de 
tokens
Tradução 
dirigida pela 
sintaxe
Representação 
intermediária
16/08/2017
3
Gramática
Gramática livre de contexto
• Uma GLC é definida por uma quádrupla, onde:
• Tokens: é um conjunto de símbolos terminais.
• Não-terminais: é um conjunto de símbolos intermediários,
usados para representar as expansões das regras de produção.
• Regras de produção: conjunto de produções onde cada
produção consiste de um não-terminal, uma seta, e uma
sequência de tokens e/ou não-terminais.
• Símbolo de partida: é um não-terminal designado como
símbolo inicial (ou de partida).
16/08/2017
4
Gramática livre de contexto
• Especificação de gramáticas 
• É a definição de produções (regras) compostas 
por terminais e não-terminais. 
• Terminais são, por exemplo: 
• Dígitos
• Sinais 
• Cadeias de caracteres em negrito 
• Não-terminais: 
• Indicação do nome em itálico (para destaque).
Gramática livre de contexto
Exemplo 1:
lista → lista + dígito
lista → lista – dígito
lista → dígito
dígito → 0|1|2|3|4|5|6|7|8|9
• Ou ainda
lista → lista + dígito |
lista – dígito | 
dígito
dígito → 0|1|2|3|4|5|6|7|8|9
• Cada nó da árvore é um símbolo da gramática.
• Nó interior e seus filhos : são produções.
• Nó interior: Composto de nós com lado esquerdo, direito e filhos
Lista
Lista Dígito
Lista Dígito
Dígito
9 - 5 + 2
16/08/2017
5
Gramática livre de contexto
Exemplo 2:
bloco → { cmds_opcs } 
cmds_opcs → lista_cmds | ε
lista_cmds → lista_cmds cmd; | cmd;
cmd → if expr then cmd
| if expr then cmd else cmd
| ...
• Exercício: Definir uma árvore gramatical para uma entrada da linguagem
Parsing (análise)
• Processo de procurar uma árvore gramatical para uma
dada string de tokens
• Análise gramatical ou análise sintática.
• A sintaxe de uma linguagem de programação:
• Deve descrever todos os aspectos relativos à forma de construção de
programas corretos na linguagem.
• Toda a análise está relacionada com sintaxe.
• Um bom compilador deve ser capaz de indicar e se recuperar de
eventuais erros:
• O tratamento de erros deve incluir mensagens informativas e um reparo.
• A recuperação serve para que a análise possa ser continuada e outros erros
sinalizados.
16/08/2017
6
Ambiguidade
• O analisador sintático gera uma string de tokens
• Uma string pode possuir várias árvores sintáticas (parse
trees)
• Isso ocorre quando a gramática é ambígua.
• Solução:
• Usar sempre gramáticas não-ambíguas, ou gramáticas
ambíguas com informações adicionais sobre como resolver
ambiguidades.
• Como demonstrar a ambiguidade:
• Construindo das ou mais árvores para uma mesma entrada
de símbolos.
Ambiguidade
• Exemplo:
String → String + String
| string - string
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
• Dada a entrada 9 – 5 + 2:
String
String String
String String
9 - 5
+
2 -
String
String
9
String
String String
5 + 2
Derivação mais à esquerda Derivação mais à direita
16/08/2017
7
Ambiguidade
• Exercício:
• Dada a gramática
• cmd→ if expr then cmd else cmd
• Demonstre que a linguagem seguinte é ambuigua:
if E1 then S1
else
if E2 then S2
else
S3
Associatividade de operadores
• Operações como +, –, * e / são associativos à esquerda na
maioria das linguagens de programação:
• 9 + 5 + 2
• Atribuição em C e exponenciação são associativos à direita:
• a = b = c
• Exemplo de uma gramática associativa:
• Direita → Letra = Direita | Letra
• Letra→ a | b | … | z
16/08/2017
8
Precedência de operadores
• Considere a expressão: 9 + 5 * 2
• Qual operação tem precedência?
• * sobre +
• Gramática geradora da expressão:
• E→ E + E | E – E | E * E | E / E | (E) | num
• Para uma pequena classe de gramáticas é possível aplicar uma forma
especial de análise empilhar-reduzir: a de precedência de operadores.
• Assim é determinado do caminho a ser tomado a cada ação da análise sintática a
partir de uma tabela de precedência.
• A essência do processo consiste separar os handles dos operadores.
• Um handle é uma forma sentencial que possibilite a correta sequencia de
substituições no processo de reconhecimento.
Análise léxica
16/08/2017
9
Analisadores Léxicos
• Lê e converte a entrada para um fluxo de tokens.
• Uma sequência de caracteres de entrada compõem um
único token
 ⇒ lexema.
• Um scanner isola o parser do lexema dos tokens.
• Quando um lexema é examinado, algum
mecanismo é necessário para verificação.
Analisadores léxicos
• Funções:
• Tratamento de 
• espaços em branco:
• tabulações 
• avanço de linha 
• Tratamento de números maiores que 9 (constantes).
• Reconhecimento de identificadores e palavras-chave.
Entrada Analisador léxico
Fluxo de 
tokens
Analisador 
Gramatical
16/08/2017
10
Um algoritmo léxico
int lex_parser ( )
{ int t;
while(TRUE) {
t = getchar( );
if (t == ‘ ’ || t ==‘\t’) ;
else if (t ==‘\n’) count_line++;
else if (isdigit(t)) {
tokenval = t – ‘0’; 
t = getchar();
while (isdigit(t)) {
tokenval = tokenval * 10 + t – ‘0’; 
t = getchar(); 
}
ungetc(t,stdin);
return NUM;
}
else …
}
}
Análise sintática
16/08/2017
11
Análise sintática
• Processo de se determinar se uma cadeia de tokens pode ser gerada por
uma gramática.
• Método de análise gramatical para construir tradutores dirigidos pela sintaxe.
• Na prática, o analisador sintático pode ser feito por algoritmos lineares.
• Travessia linear da esquerda para a direita, observando um token por cada vez.
• Dois modelos possíveis:
• Top-down: mais fáceis de escrever “à mão”. Leitura do símbolo de partir e a
construção da árvore por tentativa-erro.
• Bottom-up: suportam uma classe maior de gramáticas e de esquemas de
tradução, e é usado pelas ferramentas de geração de parsers.
Analisadores Top-Down
• Suponha a gramática
tipo → tipo_simples | -id | array [ tipo_simples ] of tipo
tipo_simples → integer | char | num pontoponto num
• Algoritmo geral:
1. Para cada nó n, com um não-terminal A, selecione uma das
produções de A e construa os filhos de n para os símbolos à
direita da produção.
2. Encontre o próximo nó para o qual uma subárvore deve ser
construída.
16/08/2017
12
Analisadores Top-Down
• Exercício
• Utilizar o método tentativa-erro para construir a 
árvore sintática da seguinte linguagem:
Array [1 .. 5] of integer
Um algoritmo preditivo
void tipo ( )
{ if (lookahead está em { integer, char, num })
tipo_simples ( );
else if (lookahead == ‘-’) {
reconhecer (‘-’); reconhecer (id); 
}
else if (lookahead == array){
reconhecer (array); reconhecer (‘[’);
tipo_simples ( ); reconhecer (‘]’);
reconhecer (of); tipo (); 
}
else error ( );
}
16/08/2017
13
Um algoritmo preditivo
void tipo_simples ( )
{ if (lookahead = = integer)
reconhecer (integer)
else if (lookahead = = char)
reconhecer (char)
else if (lookahead = = num){ 
reconhecer (num); reconhecer (pontoponto);
reconhecer (num); 
}
else error ( );
}
Análise semântica
16/08/2017
14
Tradução dirigida pela sintaxe
• Usa uma gramática livre de contexto para
especificar a estrutura sintática da entrada.
• Associa a cada símbolo um conjunto de atributos e
a cada produção associa regras semânticas para
computar os valores dos atributos.
• Gramática e regras semânticas constituem a
definição dirigida pela sintaxe.
Tradução dirigida pela sintaxe
N Produção Regra semântica
1 expr → expr1 + termo expr.t = expr1 .t || termo.t || ‘+’
2 expr → expr1 – termo expr.t = expr1 .t || termo.t || ‘–’
3 expr → termo expr.t = termo.t
4 termo → 0 termo.t = ‘0’
.. ... ...
14 termo → 9 termo.t = ‘9’ 
• 1. Se Expr for uma variável ou uma constante, então a notação posfixa para Expr será o próprio Expr.
• 2. Se Expr for uma expressão da forma Expr1 OP Expr2 , onde OP é qualquer operador binário, então a
forma posfixa para Expr será Expr1Expr2OP.
• 3 Se a Expr for uma expressão que deriva para um termo final, então a notação será a expansão do
termo.
16/08/2017
15
Tradução dirigida pela sintaxe
expr.t = 9 5 – 2 +
expr.t = 9 5 – termo.t = 2
expr.t = 9 termo.t = 5
9
-
5
+
2
termo.t = 9
Esquemas de tradução
• Gramática livre de contexto com fragmentos de programas (ações 
semânticas) embutidos no lado direito das produções.
• Semelhante à definição dirigida por sintaxe, mas com a ordem de 
avaliação das regras semânticas explicitada.
• Exemplo:
expr → expr + termo {imprimir(‘+’) } 
expr → expr - termo {imprimir(‘–’) } 
expr → termo 
termo → 0 {imprimir(‘0’) } 
termo → 1 {imprimir(‘1’) } 
… 
termo → 9 {imprimir(‘9’) }
16/08/2017
16
Esquemas de tradução
Expr
Expr Termo
Expr Termo
9 - 5
+
2
Termo
{imprimir (‘+’)}
{imprimir (‘2’)}
{imprimir (‘5’)}
{imprimir (‘-’)}
{imprimir (‘9’)}
Geração de código
16/08/2017
17
Geração de código
• Antes de produzir o código final, uma representação intermediária
do programa fonte deve ser construída durante a fase de análise.
• Usada como base para a geração do programa objeto.
• Suponha uma máquina qualquer:
• Tem apenas um registrador (acumulador) em que as operações
aritméticas são realizadas,
• Apenas uma instrução para realizar cada operação (uma instrução para
soma, uma para subtração)
• Considere o comando de atribuição
• X:= 9 – 5 + 2
Geração de código
• A primeira operação a ser realizada é a subtração 9 –
5.
• Esse valor deve ser guardado numa variável temporária, que
chamaremos de t1.
• Em seguida realizar a soma com 2 onde guardaremos o
resultado no temporário t2.
• E finalmente guardamos em X o valor do temporário t2.
• t1 = 9 – 5
• t2 = t1 + 2
• X = t2
16/08/2017
18
Geração de código
• Um gerador de código simples pode ser construído com regras como:
• 1. Toda operação aritmética binária, gera 3 instruções:
Instrução Exemplo: 9 – 5
Carrega o primeiro operando no acumulador MOV R1, 9
Usa a instrução correspondente a operação com o segundo 
operando, deixando o resultado no acumulador
SUB R1, 5
Armazena o resultado do acumulador em uma temporária 
nova.
MOV t1, R1
• 2. Um comando de atribuição sempre gera duas instruções:
Instrução Exemplo: x=t2
Carrega o valor da expressão no acumulador LOAD R1,t2
Armazena o resultado na variável MOV X, R1
Geração de código
• Assim a instrução X = 9 – 5 + 2:
1. MOV R1, 9 {t1 = 9 – 5}
2. SUB R1, 5
3. MOV t1, R1
4. MOV R1, 2 {t2 = t1 + 2}
5. ADD R1, t1
6. MOV R1,t2 
7. MOV t2,R1 {X = t2}
8. MOV X,R1
16/08/2017
19
Resumo da aula
• O contexto hoje foi conhecer o processo para 
construção de um compilador, usando uma expressão 
simples.
• Foram vistos:
• Linguagem
• Gramática
• Retaguarda de um compilador
• Problemas de linguagens
• Analisadores: léxico, sintático, semântico
• Árvores sintáticas
• Regras gramaticais e regras semânticas
• Tradução dirigida pela sintaxe
• Geração de código