Análise léxica e sintática
Teoria e Implementação de Linguagens
Computacionais - IF688
Allan J. Souza
{ajss}@cin.ufpe.br
Roteiro
Processo de compilação
 Análise léxica

◦ Reconhecimento de tokens
Análise sintática
 Gramáticas
 Representações de um programa

Processo de compilação
begin
if x = 5 then
...
input
Código Fonte
output
Compilador
1100111
0011100011
Programa
Fases da compilação
Código
fonte
Análise Léxica
abstração
Análise Sintática
Árvore
sintática
abstrata
Análise Semântica
AST
decorada
Geração de Código
Código
Máquina
implementação
tokens e
lexemas
ANÁLISE LÉXICA
Análise Léxica
Responsável por traduzir o arquivo fonte
em lexemas e tokens.
if (n == 0) {
return 1;
} else {
...
}
if
LPAR
id
"n"
intLit
"0"
RPAR
LCUR
intLit
"1"
comm
RCUR
equals
return
else ...
Reconhecendo tokens

Expressões regulares
if
[a-z][a-z0-9]*
[0-9]+
IF
ID
NUM
a-z
IF
i
1
ID
f
2
a-z
1
2
3
0-9
ANÁLISE SINTÁTICA
Análise Sintática
“the way in wich words are put together to
form phrases, clauses or sentences.”
Webster´s Dictionary
 A seguinte construção é válida?
int y = 0,k = 0;
int x = y+++k;
 Responsável por verificar quando uma
sentença faz parte da gramática da
linguagem.
GRAMÁTICAS
Descrevendo linguagens

Gramáticas livres de contexto são
utilizadas para descrever linguagens de
programação
◦
◦
◦
◦
Símbolo inicial
Produções
Símbolos terminais
Símbolos não-terminais
Exemplo
E → E + E | T
T → T * T | F
F → ( E ) | a
Simbolo inicial: E
 → é utilizado na
notação de produção
 Terminais: + * ( ) a
 Não terminais: E T F

A cadeia a + (a + a * a) pertence à gramática?
Derivações
Determinar se uma cadeia pertence à gramática
E
E
T
F
a
a
a
a
a
+
+
+
+
+
+
+
+
E
E
E
E
T
F
( E )
( E + E )
a
a
a
a
a
a
a
a
a
+
+
+
+
+
+
+
+
+
(
(
(
(
(
(
(
(
(
T
F
a
a
a
a
a
a
a
+
+
+
+
+
+
+
+
+
E
E
E
T
T
F
a
a
a
)
)
)
)
*
*
*
*
*
T
T
T
F
a
)
)
)
)
)
Parse tree
E
E
E

A Parse Tree é
construída
conectando cada
derivação a sua
origem.

Na prática não é
implementada
pelos
compiladores.
T
T
F
F
E
E
E
T
T
T
F
F
a +
(
a
+
a
*
a
)
Gramáticas ambíguas
a + a + a
E
E
E
E
T
E
E
T
F
+
a
E
T
F
a
E
F
+
a
T
E
T
T
F
a
E
F
F
+
a
+
a
Refatoração
E → E + E | F
F → ( E ) | a
E → E + A | F
A → E
F → ( E ) | a
E
A
E
E
F
a
A
E
E
F
F
+
a
+
a
Gramáticas LL(1)
a cadeia de entrada é examinada da esquerda para a
direita
 o analisador procura construir uma derivação
esquerda
 exatamente 1 símbolo do resto da entrada é
examinado

LL(1)
Left-to-right
Leftmost-derivation
1-symbol lookahead
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´ →
Fatoração
E → F + F | F
F → ( E ) | a
E → F A
A → + F | F
F → ( E ) | a
E → F + F
E → F
não é possível decidir, olhando apenas o primeiro
símbolo
REPRESENTAÇÕES
Representação do programa

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
Abstract Syntax Tree (AST)
IfThenElse ::= 'if' expr 'then' comm1 'else' comm2
return new IfThenElse(expr, comm1, comm2);
Abstract Syntax Tree (AST)
Análise léxica e sintática
Teoria e Implementação de Linguagens
Computacionais - IF688
Allan J. Souza
{ajss}@cin.ufpe.br