Um Tradutor Dirigido por
Sintaxe Simples
• Apresenta de forma resumida boa parte do
assunto que veremos em detalhes no
restante do curso
• Dá uma visão geral do processo de
compilação
Um compilador simples
• Objetivo: traduzir expressões infixas em
posfixas
9–5+295–2+
• Aplicabilidade: computação baseda em
pilha (por exemplo, gerador de código para
.NET e JVM)
Front-end de um compilador
Programa fonte
Analisador léxico
tokens
Parser
árvore sintática
Ger. de código intermediário
Three-address code
Tabela de
Símbolos
Definição de uma linguagem
• Linguagem = sintaxe + semântica
• Sintaxe = forma
• Semântica = significado
Definição de uma linguagem
• Especificação da sintaxe:
– gramática livre de contexto, BNF
(Backus-Naur Form)
• Especificação da Semântica:
– normalmente informal (textual)
– formal: uso de semântica operacional,
denotacional, de ações, etc.
Exemplo: if-else
if ( expression ) statement else statement
Exemplo: if-else
if ( expression ) statement else statement
stmt g if ( expr ) stmt else stmt
Gramática Livre de Contexto
• Um conjunto de tokens, símbolos terminais
• Um conjunto de símbolos não-terminais
• Um conjunto de produções, cada produção
consiste de um não-terminal, uma seta, e
uma sequencia de tokens e/ou não terminais
• Um não terminal designado como símbolo
inicial
Exemplo 1
list g list + digit
list g list - digit
list g digit
digit g 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
Exemplo 1a
list g list + digit | list - digit | digit
digit g 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
Exemplo 2
call g id ( optparams )
optparams g params | 
params g params , param | param
Derivações
• Uma gramática deriva strings a partir do seu
símbolo inicial e repetidamente substituindo
não-terminais pelo corpo de sua produção
• As sequencias de terminais produzidas desta
forma formam a linguagem definida pela
gramática
• Exemplos: 9, 9 - 5, 9 - 5 + 2
Parsing
• Problema de pegar uma string de terminais
e verificar como derivá-la a partir do
símbolo inicial da gramática; caso não seja
possível, reportar erros de sintaxe.
• Processo de procurar uma parse-tree para
uma dada sequencia de terminais.
Parse Trees
• Mostra graficamente como o símbolo inicial
de uma gramática deriva uma string da
linguagem.
• Para uma produção A g XYZ
A
X
Y
Z
Parse Trees
•
•
•
•
A raiz é o símbolo inicial
Cada folha é um terminal ou 
Cada nó interior é um não-terminal
Se A é um não-terminal e X1, X2,...,Xn são
labels de filhos deste nó, tem que haver uma
produção A g X1 X2 ... Xn
Exemplo
•9 – 5 + 2
list
list
digit
digit
list
digit
9
-
5
+
2
Ambiguidade
• Parse-tree gera uma string, mas uma string
pode possuir várias parse-trees, se a
gramática for ambígua.
• Solução: usar sempre gramáticas nãoambíguas, ou gramáticas ambíguas com
informações adicionais sobre como resolver
ambiguidades.
Ambiguidade - Exemplo
• string g string + string
| string - string
|0|1|2|3|4|5|6|7|8|9
Exemplo: Duas parse trees
•9 – 5 + 2
string
string
string
9
-
string
+ string
string
5
2
string
-
string
string
+ string
9
5
2
Associatividade de Operadores
• +, –, * e / são associativos à esquerda, na
maioria das linguagens de programação:
9 – 5 + 2 é equivalente a (9-5)+2
• Atribuição em C e exponenciação são
associativos à direita:
a=b=c
2**3**4
Associatividade à direita
right g letter = right | letter
letter g a | b | … | z
Precedência de operadores
• 9+5*2
• * tem maior precedência do que +
• Usaremos dois não-terminais para
representar os dois níveis de precedência
em expressões e um outro para gerar as
unidades básicas de expressões.
Precedência de operadores
• expr g expr + term | expr – term | term
term g term * factor | term / factor | factor
factor g digit | ( expr )
digit g 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
Exemplo
• stmt g id = expression ;
| if ( expression ) stmt
| if ( expression ) stmt else stmt
| while ( expression ) stmt
| do stmt while ( expression ) ;
| { stmt }
stmts g stmts stmt
|
Tradução dirigida por sintaxe
• Tradução dirigida associa regras ou trechos
de programa às produções de uma
gramática.
Exemplo
expr g expr1 + term
traduza expr1;
traduza term;
trate + ;
Conceito: Atributo
• Um valor associado a um construtor do
programa.
• Exemplos:
– Tipo em uma expressão;
– Número de instruções geradas;
– Localização da primeira instrução gerada por
um construtor;
Conceito: Esquema de tradução
(dirigida pela sintaxe)
• Notação para associar trechos de programa
a produções de uma gramática
• Os trechos de programa são executados
quando a produção é usada durante a análise
sintática
• O resultado da execução desses trechos de
programa, na ordem criada pela análise
sintática, produz a tradução desejada do
programa fonte
Notação pós-fixada
• Se E é uma variável ou constante, sua
notação pós-fixada é ela mesma;
• Se E é uma expressão da forma E1 op E2,
então sua notação pós fixada é E1’ E2’ op,
onde E1’ e E2’ são as notações pós-fixadas
de E1 e E2 respectivamente;
• Se E é uma expressão com parênteses ( E ),
então sua notação pós-fixada é a mesma
notação pós-fixada de E1.
Exemplo
• (9-5)+2
95-2+
• 9-(5+2)
952+-
• 9-(5+2)*3
952+-3*
Definição dirigida por sintaxe
• Definição dirigida por sintaxe associa a
cada símbolo um conjunto de atributos;
• e a cada produção, regras semânticas para
computar os valores dos atributos
(Gramática de atributos)
Definição dirigida por sintaxe
1 Dada uma string x, construa uma parse tree
para ela;
2 Aplique as regras semânticas para avaliar
os atributos em cada nó.
Exemplo – valores dos atributos
nos nós de uma parse tree
expr.t = 95-2+
expr.t = 95expr.t = 9
term.t = 2
term.t = 5
term.t = 9
9
-
5
+
2
Tipos de Atributos
• Atributos sintetizados: seus valores são
obtidos a partir dos filhos de um
determinado nó;
Podem ser calculados através de uma
travessia bottom-up;
• Atributos herdados: têm seus valores
definidos a partir do próprio nó, de seus
pais ou seus irmãos.
Exemplo – Definição dirigida por
sintaxe
• Produção
expr g expr1 + term
expr g expr1 – term
expr g term
term g 0
term g 1
…
term g 9
Regra semântica
expr.t = expr1.t ||
term.t || ‘+’
expr.t = expr1.t ||
term.t || ‘-’
expr.t = term.t
term.t = ‘0’
term.t = ‘1’
term.t = ‘9’
Travessias
• Travessia em profundidade (depth-first)
• procedure visit (node N) {
for (each child C of N, from left to right) {
visit(C);
}
evaluate semantic rules at node N;
}
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 1
• rest g + term {print (‘+’) } rest1
rest
+
term
{print(‘+’)}
rest1
Exemplo 2
• expr g expr + term { print (‘+’) }
expr g expr - term { print (‘-’) }
expr g term
term g 0
{ print (‘0’) }
term g 1
{ print (‘1’) }
…
term g 9
{ print (‘9’) }
Exemplo 2
expr
expr
expr
-
+
term
term
2
term
5
9
Ações traduzindo 9=5+2 em 95-2+
expr
expr
expr
+
term
term {print(‘-’)}
-
2
term
5
9
{print(‘+’)}
{print(‘9’)}
{print(‘5’)}
{print(‘2’)}
Parsing
• Processo de determinar como uma string de
terminais pode ser gerada por uma
gramática
• Conceitualmente é a construção da parse
tree
• Mas a parse tree pode não ser efetivamente
construída durante a compilação.
Parsing
• Para gramáticas livres de contexto sempre é
possível construir um parser com
complexidade O(n3) para fazer o parsing de
n tokens.
• Na prática, o parsing de linguagens de
programação normalmente pode ser feito
linearmente.
• Travessia linear da esquerda para a direita,
olhando um token de cada vez.
Top-down ou bottom-up parsers
• Refere-se à ordem em que os nós da parse
tree são criados.
• Top-down: mais fáceis de escrever “à mão”
• Bottom-up: suportam uma classe maior de
gramáticas e de esquemas de tradução;
são frequentemente usados/gerados pelas
ferramentas de geração automática de
parsers.
Exemplo
• stmt g expr ;
| if (expr ) stmt
| for ( optexpr ; optexpr ; optexpr ) stmt
| other
optexpr g expr
|
Exemplo
stmt
for
(
optexpr ; optexpr ;

expr
optexpr
expr
for ( ; expr ; expr ) other
)
other
stmt
Construindo um parser top-down
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.
Construindo um parser top-down
•
•
•
Para algumas gramáticas basta uma única
travessia da esquerda para a direita da
string de entrada.
Token corrente é chamado de lookahead
symbol.
Exemplo:
for ( ; expr ; expr ) other
Backtracking
•
•
A escolha de uma produção pode exigir
tentativa-e-erro, voltando para tentar
novas alternativas possíveis.
Predictive-parsing: parsing em que não
ocorre backtracking.
Recursive descent parsing
• Método de análise sintática top-down em que um
conjunto de procedimentos recursivos é usado
para processar a entrada.
• Cada procedimento está associado a um símbolo
não-terminal da gramática.
• Predictive parsing é um caso especial de recursive
descent parsing em que o símbolo lookahead
determina sem ambiguidades o procedimento a ser
chamado para cada não-terminal.
Exemplo – predictive parsing
stmt g for ( optexpr ; optexpr ; optexpr ) stmt
match (for); match (‘(‘);
optexpr (); match (‘;‘);
optexpr (); match (‘;‘);
optexpr (); match (‘)‘); stmt ();
Exemplo – predictive parsing
void match (terminal t) {
if (lookahead == t) lookahead = nextTerminal
else report (“syntax error”);
}
Exemplo – predictive parsing (cont.)
void optexpr( ) {
if (lookahead == expr) match (expr) ;
}
Exemplo – predictive parsing (cont.)
void stmt( ) {
switch (lookahead) {
case expr: match(expr); match(‘;’); break;
case if: match(if); match(‘(‘);
match(expr);match(‘)’); stmt(); break;
case for: match(for); match(‘(‘);
optexpr(); match(‘;‘);
optexpr(); match(‘;‘); optexpr();
match(‘)‘); stmt(); break;
case other: match(other); break;
default: report(“syntax error”);
}
}
Predictive parsing - Problema
• Recursão à esquerda leva a loop em
predictive parsers:
expr g expr + term | term
A g Aa | 
Predictive parsing - Solução
• Reescrever produções tornando-as
recursivas à direita:
A g Aa | b
reescrever para
A g bR
R g aR | 
• Exemplo: expressão “baaaa”
Sintaxe abstrata x Sintaxe
concreta
• Sintaxe abstrata: ignora distinções
superficiais de forma, irrelevantes para o
processo de tradução.
list
list
list
+
digit
9
digit
9
-
-
digit
5 +
2
2
5
Sintaxe abstrata x Sintaxe
concreta (cont.)
• Na árvore sintática abstrata os nós são
construções do programa, enquanto que na
parse tree os nós são não-terminais.
• Idealmente as duas árvores devem ser
próximas.
Reescrevendo a gramática de
expressões
• expr g expr + term
expr g expr - term
expr g term
term g 0
…
term g 9
{print (‘+’) }
{print (‘-’) }
{print (‘0’) }
{print (‘9’) }
Reescrevendo a gramática de
expressões
A g Aa | Ab | c
A g cR
R g aR | bR | 
Reescrevendo a gramática de
expressões (cont.)
A = expr
a = + term {print(‘+’)}
b = - term {print(‘-’)}
c = term
Reescrevendo a gramática de
expressões (cont.)
expr g term rest
rest g + term {print (‘+’) } rest
| - term {print (‘-’) } rest
|
term g 0
…
term g 9
{print (‘0’) }
{print (‘9’) }
Tradutor em C
void expr () {
term(); rest();
}
Tradutor em C
void term () {
if (isdigit(lookahead)) {
t = lookahead; match(lookahead); print(t);
}
else report(“syntax error”);
}
Tradutor em C (cont.)
void rest()
{ if (lookahead == ‘+’) {
match(‘+’); term(); print(‘+’); rest();
}
else if (lookahead ==‘-’) {
match(‘-’); term(); print(‘-’); rest();
}
else { };
}
Otimizações
void rest ()
{ while (true) {
if (lookahead == ‘+’) {
match(‘+’); term(); print(‘+’); continue;
}
else if (lookahead ==‘-’) {
match(‘-’); term(); print(‘-’); continue;
}
break;
}
}
Usando um analisador léxico
• Facilita o tratamento de lexemas ao invés de
caracteres:
– Tratamento de espaços em branco
– Tratamento de número maiores que 9
(constantes)
– Reconhecimento de identificadores e palavraschave.
Estendendo para identificadore e
números maiores que 9
expr g expr + term {print (‘+’) }
| expr – term {print (‘-’) }
| term
term g term * factor {print (‘*’) }
| term / factor {print (‘/’) }
| factor
factor g ( expr )
| num
{print (num.value) }
| id
{print (id.lexeme) }
Class Token
class Token
int tag
class Num
class Word
int value
string lexeme
Código do analisador léxico
• token scan()
{ char t;
while(true) {
t = getchar();
if (t == ‘ ’ || t ==‘\t’) { } ;
else if (t ==‘\n’) line++;
else if (isdigit(t))
{ tokenval = t – ‘0’; t = getchar();
while (isdigit(t)) {
{ tokenval = tokenval * 10 + t – ‘0’; t = getchar(); }
ungetc(t,stdin);
return token<num,tokenval>;
}
else …
A tabela de símbolos
• Interface:
– insert(s,t)
– lookup(s)
• Palavras reservadas:
insert(“div”,div)
insert(“mod”, mod)
Geração de código intermediário
• Árvores:
e.g. parse trees ou (abstract) syntax trees
• Representações lineares:
e.g. three-address code
Construção da Syntax tree
• Classes para representar a hierarquia de
construções da Linguagem:
Statements, IfStatements, WhileStatements;
Expressions, BinaryExpressions, etc.
class AST
class Statement
class IfStmt
Expr E;
Stmt S;
class AssignmentStmt
Identifier I;
Expr E;
class Expression
class WhileStmt
Expr E;
Stmt;
class AST
class Statement
class IntLiteral
Int IL;
class BinaryExpr
Operator Op;
Expr E1, E2;
class Expression
class UnaryExpr
Operator Op;
Expr E;
Exemplo
stmt g expr ;
{stmt.n = new Eval(expr.n); }
| if (expr ) stmt {stmt.n = new If(expr.n, stmt.n}
Fluxo de controle
• Desvios condicionais ou incondicionais
• o destino pode ser especificado
– pelo operando da instrução
– o operando pode especificar um desvio relativo
– o destino pode ser especificado simbolicamente, através
de labels
Fluxo de controle - instruções
• ifFalse x goto L
• ifTrue x goto L
• goto L
Fluxo de controle – exemplo 1
class IfStmt extends Stmt {
Expr E; Stmt S;
public If (Expr x, Stmt y)
{ E = x; S = y; after = newlabel(); }
public void gen() {
Expr n = E.rvalue();
emit(“ifFalse ”+n.toString()+“goto ”+after);
S.gen()
emit(after +”:“);
}
}
ifFalse x goto after
Código para calcular
expr em x
ifFalse x goto after
Código para stmt1
after
Resumo
If ( peek == ‘\n’ ) line = line + 1;
Lexical Analyser
<if> <(> <id,”peek”> <eq> <const,’\n’> <)>
<id,”line”> <assign> <id,”line”> <+> <num,1> <;>
Syntax Directed Translator
1: t1 = (int) ‘\n’
2: ifFalse peek == t1 goto 4
3: line = line + 1
4:
if
eq
peek
assign
(int)
‘\n’
line
line
+
1