Análise Léxica e Sintática
Teoria e Implementação de Linguagens
Computacionais - IF688 – 2007.1
Luiz Carlos d´Oleron – [email protected]
Roteiro








Fases da compilação
Analise Lexica
Tokens, lexemas,
expressões regulares e
autômatos finitos
Analise Sintática
Gramáticas e parsers
Parser trees
Derivações
Gramáticas ambíguas










Ambigüidade
aritméticas
Parser recursive
descendent
Recursão à esquerda
Gramáticas LL(k)
Gramáticas LR(k)
Outras gramáticas
Dangling else
Parsing LR de
gramáticas ambíguas
AST
Referências
Luiz Carlos d´Oleron – [email protected]
Atenção!
Este material não substitui a leitura
da bibliografia
 Sugerimos pesquisar a leitura
referenciada no final deste trabalho e
no site da disciplina

Luiz Carlos d´Oleron – [email protected]
Processo de Compilação
begin
if x = 5 then
...
output
+ params
Código Fonte
Compilador
Luiz Carlos d´Oleron – [email protected]
1100111
0011100011
Programa
Fases da compilação
Análise Léxica
tokens e
lexemas
Análise Sintática
Árvore
sintática
abstrata
Análise Semântica
AST
decorada
Geração de Código
Código
Máquina
Luiz Carlos d´Oleron – [email protected]
implementação
abstração
Código
fonte
Background Acadêmico - CIn
Luiz Carlos d´Oleron – [email protected]
Análise Léxica
O analisador léxico é responsável por
traduzir o arquivo fonte em lexemas e
tokens
if (n == 0) {
return 1;
} else {
...
}
if
LPAR
id
"n"
assign
intLit
"0"
RPAR
LCUR
return
intLit
"1"
comm
RCUR
else
Luiz Carlos d´Oleron – [email protected]
...
Reconhecendo tokens
Expressões regulares (implementadas
como Autômatos Finitos) são
comumente utilizadas
Exemplos:
if
[a-z][a-z0-9]*
[0-9]+
IF
ID
NUM
Luiz Carlos d´Oleron – [email protected]
Reconhecendo tokens
ID
a-z
1
a-z
2
0-9
IF
i
1
f
2
Luiz Carlos d´Oleron – [email protected]
3
Análise Sintática
“syn-tax: the way in wich words are
put together to form phrases, clauses
or setences.”
Webster´s Dictionary
A seguinte construção é válida?
int y = 0,k = 0;
int x = y+++k;
Luiz Carlos d´Oleron – [email protected]
Análise Sintática
O Analisador Sintático é responsável por
verificar quando uma sentença faz parte da
gramática da linguagem.
Entrada: lexemas e tokens gerados pelo
analisador léxico
Luiz Carlos d´Oleron – [email protected]
Gramáticas
– descrevendo linguagens
Gramáticas livres de contexto são
utilizadas para descrever linguagens
de programação
Produções
 Símbolos terminais
 Símbolos não-terminais
 Símbolo inicial

Luiz Carlos d´Oleron – [email protected]
Exemplo
S→S;S
S → id := E
S → print (L)
E → id
E → num
E→E+E
E → ( S , E)
L→E
L→L,E





Terminais: id print , + ; := ( )
Não terminas: S E L
Símbolo inicial: S
→ é utilizado na notação de
produções
A cadeia seguinte pertence à
gramática?
a := 7;
b := c + (d := 5 + 6, d)
Luiz Carlos d´Oleron – [email protected]
Derivações
Para determinar se uma cadeia pertence à gramática pode
ser utilizado o processo de Derivação:
S
S ; S
S ; id :=
id := E ;
id := num
id := num
id := num
id := num
id := num
id := num
id := num
id := num
id := num
E
id := E
; id :=
; id :=
; id :=
; id :=
; id :=
; id :=
; id :=
; id :=
; id :=
E
E + E
E + (S, E)
id + (S, E)
id + (id :=
id + (id :=
id + (id :=
id + (id :=
id + (id :=
E, E)
E + E, E)
E + E, id)
num + E, id)
num + num, id)
Luiz Carlos d´Oleron – [email protected]
Parse tree
S
S
S
id
:=
E
;
id
num
+
E
A Parse Tree é construída
conectando cada derivação a
sua origem.
Na prática não é implementada
pelos compiladores.
E
:=
E
S
(
id
id
:=
E
E
+
num
Luiz Carlos d´Oleron – [email protected]
E
,
id
E
num
)
Gramáticas ambíguas

Uma gramática é ambígua se a partir dela
uma sentença pode dar origem a duas
arvores de parsing diferentes

Indeterminismo é problemático para a
compilação

Eliminação de ambigüidade é quase
sempre possível

Refatoração da gramática
Luiz Carlos d´Oleron – [email protected]
Gramáticas ambíguas
x := 1 + 2 + 3;
S
id
S
E
:=
E
E
num
+
+
E
num
id
E
num
E
:=
E
num
+
E
num
Luiz Carlos d´Oleron – [email protected]
E
+
E
num
Gramática refatorada
S→S;S
S → id := E
S → print (L)
E → id
E → num
E→E+E
E → ( S , E)
L→E
L→L,E
S→S;S
S → id := E
S → print (L)
E → id
E → num
E→E+T
E→T
E → (S , E)
L→E
L→L,E
Luiz Carlos d´Oleron – [email protected]
Parsers
Utilizados para avaliar uma entrada
quanto à sintaxe
 Podem ser

 Top-down

Recursive-descent / LL(k)
 Bottom-up

SRL, LR(k)
Luiz Carlos d´Oleron – [email protected]
Parser Recursive descent
Algoritmo baseado em previsões
 Também conhecido como Predictive

Parsing
Funções mutuamente recursivas
 Simples implementação
 Uma função para cada não-terminal
 Uma cláusula para cada produção
 Verifica o primeiro símbolo terminal
para decidir qual função usar

Luiz Carlos d´Oleron – [email protected]
Parser 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
Luiz Carlos d´Oleron – [email protected]
Parser Recursive descent
A ::= aBcC
parseA() {
accept(‘a’);
parseB();
accept(‘c’);
parseC();
}
parseB() {
case (d):
parseC();
parseB();
case (c):
accept(‘c’);
parseC();
}
B ::= CB | cC
C ::= da
parseC() {
accept(‘d’);
accept(‘a’);
}
Luiz Carlos d´Oleron – [email protected]
Recursive descent

Na prática constrói uma tabela de
produções indexadas por não-terminais e
terminais
a
A
A ::= aBcC
c
d
A::= aBcC
B
B::= CB
B::= CA
C
C::= da
B ::= CB | CA
C ::= da
Luiz Carlos d´Oleron – [email protected]
Recursive descent

Vantagens
Fácil de implementar
 Fácil de entender


Desvantagens
Performance deficiente
 Gramática reconhecida possui restrições

 Sem
recursão à esquerda
 Deve estar fatorada
Luiz Carlos d´Oleron – [email protected]
Recursive descent
A ::= aBcC
A ::= aBcC
B ::= CX
B ::= CB | CA
Gramática
LL(1)
X ::= B | A
C ::= da
C ::= da
a
A
c
d
A::= aBcC
B
B::= CX
C
C::= da
X
X::=A
X::=B
Luiz Carlos d´Oleron – [email protected]
Gramáticas e Parsers LL(1)







Gramáticas SEM entradas duplicadas na tabela são
conhecidas como LL(1)
LL(1) - Left-to-right, leftmost-derivation, 1symbol lookahead
Left-to-right – direção na qual os símbolos serão
examinados
Leftmost-derivation – ordem pela qual os
símbolos não-terminais serão expandidos
1-symbol lookahead– não mais que um símbolo
será avaliado por vez
Existem LL(2), LL(3),...
Toda LL(1) é LL(2), toda LL(2) é LL(3),... LL(k)
Luiz Carlos d´Oleron – [email protected]
LL(1) na prática - Applet
http://ag-kastens.uni-paderborn.de/lehre/material/uebi/parsdemo/LL1Parser.html
Luiz Carlos d´Oleron – [email protected]
Recursão à esquerda
Gramáticas LL(1) são vulneráveis às entradas
duplicadas. Por exemplo, o fragmento a seguir:
E→E+T
E→T
O fato de E aparecer no início do lado direito da produção é
a causa do problema. Isso é conhecido como Recursão à
Esquerda. Para corrigir isso, vamos refatorar a gramática,
com Recursão à Direita:
E → T E´
E´ → +T E´
E´ →
Luiz Carlos d´Oleron – [email protected]
Gramáticas e Parsers LR(1)






As fraquezas de LL(k) são superadas pela
técnica LR(k)
LR(1) - Left-to-right, rightmostderivation, 1-symbol lookahead
Uso de uma pilha para armazenar símbolos de
forma temporária
Possui duas operações, shift e reduce
shift: Move o primeiro símbolo para o topo da
pilha
reduce: escolhe uma regra da gramática do
tipo X→A B C. push X da pilha e pop C B A.
Luiz Carlos d´Oleron – [email protected]
Outros Parsers LR

LR(0)


SLR


Melhoramento sobre o LR(0)
LR(1)



Olham apenas para a pilha
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
Luiz Carlos d´Oleron – [email protected]
shift-reduce na prática Applet
http://ag-kastens.uni-paderborn.de/lehre/material/uebi/parsdemo/SRParser.html
Luiz Carlos d´Oleron – [email protected]
Parsing LR de Gramáticas
Ambíguas

Gramáticas ambíguas ocasionam
conflitos em parsers LR

Shift-reduce conflict
parser não consegue decidir se empilha o
próximo símbolo da entrada, ou se reduz
O
para uma regra já disponível

Reduce-reduce conflict
O
parser pode realizar uma redução para
duas regras distintas
Luiz Carlos d´Oleron – [email protected]
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 ::= ...
Luiz Carlos d´Oleron – [email protected]
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 }
Luiz Carlos d´Oleron – [email protected]
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
Luiz Carlos d´Oleron – [email protected]
Gramáticas não-ambíguas
LL(k)
LR(k)
LL(1)
LR(1)
Gramáticas
ambíguas
LALR(1)
SLR
LL(0)
LR(0)
Luiz Carlos d´Oleron – [email protected]
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
Luiz Carlos d´Oleron – [email protected]
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
Luiz Carlos d´Oleron – [email protected]
AST – Abstract Syntax Tree
IfThenElse ::= 'if' expr 'then' comm1 'else' comm2
return new IfThenElse(expr, comm1, comm2);
Luiz Carlos d´Oleron – [email protected]
Luiz Carlos d´Oleron – [email protected]
Referências

Análises léxica e sintática, Mauro LaSalette C. L. de Araújo

Modern Compiler implementation in
Java, Andrew W. Appel
Luiz Carlos d´Oleron – [email protected]