Análises léxica e sintática
Teoria e Implementação de Linguagens
Computacionais - IF688
Mauro La-Salette C. L. de Araújo
Centro de Informática – CIn
Universidade Federal de Pernambuco – UFPE
[email protected]
Roteiro
 Visão geral
 Análise léxica
 Definição
 Especificação
 Implementação
 Correspondência
 Análise sintática
 Definição
 Especificação
 Implementação
 Algoritmos de parsing e gramáticas
 Gramáticas ambíguas
 Sintaxe abstrata
Visão Geral
Código fonte
Análise
léxica
Análise
sintática
Tokens
Análise
semântica
AST
Geração de
código
AST decorada
executável
Análise Léxica
Definição
 Fase da compilação responsável por
extrair os tokens do código fonte de um
programa.
if (n == 0) {
return 1;
} else {
...
}
if
LPAR
id
"n"
assign
intLit
"0"
RPAR
LCUR
return
intLit
"1"
comm
RCUR
else
...
Especificação
Os tokens de uma linguagem
comumente são especificados
através de Expressões Regulares
[a-z][a-z0-9]*
identifier
[0-9]+
intLiteral
Implementação
 Autômatos finitos
ID
a-z
IF
a-z
i
1
2
1
0-9
f
2
3
Análise Sintática
Definição
 Fase da compilação responsável por
determinar se uma dada cadeia de
entrada pertence ou não à linguagem
definida por uma gramática
 Tem como entrada os tokens processados
pela análise léxica
 Produz uma estrutura comumente
denominada AST – abstract syntax tree
Especificação
S
A
B
C
D
::=
::=
::=
::=
::=
A | B
C | D
bba
ab
dab
Produções
 BNF - Backus-Naur form
S, A, B, C, D : não-terminais
a,b,d: terminais
Implementação
Algoritmos de parsing e gramáticas
Classificação
Top-down
• Recursive-descent / LL(1)
Bottom-up
• LR, SLR, LALR, LR(k)
Recursive descent
Algoritmo baseado em previsões
Funções mutuamente recursivas
Uma função para cada não-terminal
Uma cláusula para cada produção
Recursive descent
Desenvolvendo um recursive descent
parser
Cada não terminal 'X' dará origem a um
método/função parseX();
Produções do tipo 'A | B' darão origem a
cláusulas cases
Recursive descent
parseA() {
accept(‘a’);
parseB();
accept(‘c’);
parseC();
}
parseB() {
case (d):
parseC();
parseB();
case (c):
accept(‘c’);
parseC();
}
A ::= aBcC
B ::= CB | cC
parseC() {
C ::= da
accept(‘d’);
accept(‘a’);
}
Recursive descent
 Na prática constrói uma tabela de
produções indexadas por não-terminais e
terminais
a
A ::= aBcC
A
B ::= CB | cC
C ::= da
c
d
A::=
aBcC
B
B::= cC B::= CB
C
C::= da
Recursive descent
parseA() {
accept(‘a’);
parseB();
accept(‘c’);
parseC();
}
parseB() {
case (d):
parseC();
parseB();
case (d):
parseC();
parseA();
}
A ::= aBcC
B ::= CB | CA
parseC() {
C ::= da
accept(‘d’);
accept(‘a’);
}
Recursive descent
 Na prática constrói uma tabela de
produções indexadas por não-terminais e
terminais
a
A ::= aBcC
A
B ::= CB | CA
c
d
A::= aBC
B
B::= CB
B::= CA
C
C::= da
C ::= da
Recursive descent
Vantagens
Fácil de implementar
Desvantagens
Performance
Gramática reconhecida possui restrições
Sem recursão à esquerda
Deve estar fatorada
...
Recursive descent
A ::= aBC
A ::= aBC
B ::= CX
B ::= CB | CA
X ::= B | A
C ::= da
C ::= da
a
A
c
d
A::= aBC
B
B::= CX
C
C::= da
X
X::=A
X::=B
Gramática
LL(1)
Gramáticas LL(1)
Left-to-right parse
Leftmost-derivation
1-symbol-lookahead
Algoritmos bottom-up
Algoritmos LL(k) precisam decidir
que produção usar tendo visto
apenas k tokens da entrada
Algoritmos bottom-up são baseados
em técnicas LR(k)
Left-to-right parse, Right-most
derivation, k-symbol-lookahead
Algoritmos bottom-up
Baseados no conceito de autômato a
pilha
Pilha + lookahead
Duas tipos de ações
Shift:
• Coloca o primeiro token da entrada no topo da
pilha
Reduce:
• Escolhe a regra X::= A B C
• Retira C, B, A da pilha
• Coloca X na pilha
Gramáticas LR
 LR(0)
Olham apenas para a pilha
 SLR
Melhoramento sobre o LR(0)
 LR(1)
Lookahead de 1 símbolo
Consegue descrever a maioria das linguagens de
programação
 LALR(1)
Melhoramento sobre o LR(1)
 Diminuí o tamanho da tabela de parsing
Gramáticas Ambíguas
 Uma gramática é ambígua se a partir dela
uma sentença pode dar origem a duas
arvores de parsing
 Problemáticas para a compilação
 Eliminação de ambigüidade é quase
sempre possível
Transformações na gramática
Gramáticas Ambíguas
 Caso clássico: gramática para expressões
aritméticas
E ::= intLiteral
| E '*' E
| E '/' E
| E '+' E
| E '-' E
|'(' E ')'
Gramáticas Ambíguas
1 + 2 * 3
E
1
E
E
*
+
E
E
E
E
+
3
1
*
E
E
2
2
E
3
Gramáticas Ambíguas
 Solução:
Transformar a gramática
 * e / com maior precedência que + ou  Operadores associativos a esquerda
E ::= intLiteral
| E '*' E
| E '/' E
| E '+' E
| E '-' E
|'(' E ')'
E ::= E '+' T
| E '–' T
| T
T ::= T '*' F
| T '/' F
| F
F ::= intLiteral
|'(' E ')'
Parsing LR de Gramáticas Ambíguas
Gramáticas ambíguas ocasionam
conflitos em parsers LR
Shift-reduce conflict
O parser não consegue decidir se empilha o
próximo símbolo da entrada, ou se reduz para
uma regra já disponível
Reduce-reduce conflict
O parser pode realizar uma redução para duas
regras distintas
Parsing LR de Gramáticas Ambíguas
 Caso clássico: dangling-else
S ::= 'if' E 'then' S 'else' S
S ::= 'if' E 'then' S
S ::= ...
Parsing LR de Gramáticas Ambíguas
if a then { if b then s1 } else s2
if a then if b then s1 else s2
?
if a then { if b then s1 else s2 }
Parsing LR de Gramáticas Ambíguas
Input:
if a then if b then s1 else s2
Stack:
if
a
s2
then St
if else
b then
s1
reduce St ?
shift else ?
Optando pelo reduce...
Parsing LR de Gramáticas Ambíguas
Input:
if a then if b then s1 else s2
Stack:
if
a
then
if
St
b
then
s1
reduce St ?
shift else ?
Optando pelo shift...
else
s2
Parsing LR de Gramáticas Ambíguas
 Solução:
Transformar a gramática
 Introdução dos conceitos de matched e unmatched
S ::= 'if' E 'then' S 'else' S
S ::= 'if' E 'then' S
S ::= ...
S ::= M
| U
M ::= 'if' E 'then' M 'else' M
| ...
U ::= 'if' E 'then' S
| 'if' E 'then' M 'else' U
Gramáticas não-ambíguas
LL(k)
LR(k)
LL(1)
LR(1)
LALR(1)
SLR
LL(0)
LR(0)
Gramáticas
ambíguas
Sintaxe abstrata
 Apenas reconhecer se uma sentença
pertence ou não a linguagem especificada
por uma gramática não é o suficiente
 É necessário produzir uma estrutura que
sirva de base para a próxima fase do
processo de compilação
Parse trees nunca são montadas na prática
AST – Abstract Syntax Tree
 Capturam a essência da estrutura de uma
gramática abstraindo não-terminais
 Representação possível
Java: Classes que possam se relacionar a fim de
montar uma árvore
 Pode ser produzida através da inserção de
ações semânticas no parser
AST – Abstract Syntax Tree
IfThenElse ::= 'if' expr 'then' comm1 'else' comm2
return new IfThenElse(expr, comm1, comm2);
Análises léxica e sintática
Teoria e Implementação de Linguagens
Computacionais - IF688
Mauro La-Salette C. L. de Araújo
Centro de Informática – CIn
Universidade Federal de Pernambuco – UFPE
[email protected]