Compiladores

Anlise Sinttica

Luana Barreto da Silva

 Anlise Sinttica
Gramtica Livre de Contexto
Reconhecimento de Sentenas
rvores de Derivao
Gramticas Ambguas
Eliminao de Recurso Esquerda
Fatorao Esquerda
Primeiros e Seguintes

LUANA BARRETO 2
 Segunda fase do compilador;
Verificar se as construes usadas no
programa esto gramaticalmente corretas;
As estruturas sintticas so especificadas
atravs de gramticas livres de contexto
(GLC);
As gramtica livre de contexto so adequadas
para representar as caractersticas de
sentenas em linguagens de programao;

LUANA BARRETO 3
 As Gramticas Livres de Contexto formam a
base para a anlise sinttica das linguagens
de programao, pois permite descrever a
linguagens de programao.

Expresso Regulares -> Jlex

Gramticas Livres de Contexto -> YACC

LUANA BARRETO 4
 Uma GLC um conjunto de produes,
composta por smbolos terminais e no-
terminais;

Ex: E -> E + E
| E*E
| num
| (E)

LUANA BARRETO 5
 o procedimento que verifica se uma dada
sentena pertence linguagem gerada por
uma gramtica livre de contexto.

A sentena vlida numa dada gramtica

apenas quando existe pelo menos uma
sequncia de aplicao de produes que
permita obter a sentena a partir do smbolo
sentencial.

LUANA BARRETO 6
 H duas formas possveis de derivar uma
seqncia de produes para validar uma
dada sentena.
Reconhecimento descendente, tambm conhecido
como top-down, o ponto de partida o smbolo
sentencial.

Reconhecimento ascendente ou bottom-up, o

ponto de partida a sentena, que ser vlida se
for possvel obter como resultado o smbolo
sentencial.

LUANA BARRETO 7
 Ex: Dada a sentena : (v + v) * v
Dada a gramtica:
E -> E + E
E -> E * E
E -> (E)
E -> v

LUANA BARRETO 8
 Ex: Dada a sentena : (v + v) * v
Dada a gramtica: ASCENDENTE
1- E -> E + E (v+v) * v
2- E -> E * E (E+v) * v
3- E -> (E) (E + E) * v
4- E -> v (E) * v
(E) * E
E*E
E

LUANA BARRETO 9
 uma representao grfica de uma
derivao de sentena;
uma estrutura de dados que contm um
conjunto finito de elementos, denominados
de ns;
Nessa estrutura as folhas das rvores so os
smbolos terminais e os ns intermedirios
correspondem aos smbolos no-terminais.

LUANA BARRETO 10
 Exemplo (v + v) * v

LUANA BARRETO 11
 Uma gramtica ambgua aquela que permite
que uma mesma sentena tenha mais de uma
rvore sinttica

LUANA BARRETO 12
 Para tratar o problema de ambigidade em
gramtica so utilizados os conceitos de
precedncia e associatividade.
Operadores com maior precedncia so avaliados
primeiro.

Operadores com igual precedncia so avaliados de

acordo com a associatividade esquerdadireita.

LUANA BARRETO 13
 Como remover a ambiguidade?

Colando uma precedncia de acordo com a

linguagem - maior para * em relao ou + e
Determinar que cada operador seja associativo
esquerda, ou seja:
(1-2)-3 e no 1-(2-3)

Isso ser possvel introduzindo novos no-

terminais

LUANA BARRETO 14
 Para tratar a precedncia dos operadores:
1-Dividese os operadores em grupos de igual
precedncia

2-Para cada nvel de precedncia, introduzse um

no terminal e uma regra gramatical

Para tratar a associatividade dos operadores:

3-Criase regras gramaticais recursivas direita ou
esquerda.

LUANA BARRETO 15
 A precedncia menor est associada
operao que est mais prxima raiz da
rvore.
As produes com maior precedncia so
aquelas associadas expanso do token e s
expresses entre parnteses. 2- Adiciona-se
um smbolo no terminal para essas duas
produes.
P -> (E)
P -> v

LUANA BARRETO 16
 A prxima maior precedncia est associada
a operao de multiplicao. 2 - Adiciona-se
um smbolo no terminal a esta operao.
M -> M * P
Neste caso,para anular a recursividade,
adiciona-se uma produo do tipo:
M -> P
Para a operao de soma acrescenta-se um
par de produes similares:
E -> E + M
E -> M
LUANA BARRETO 17
 Removendo-se a ambigidade:

1) P-> (E)
P-> v

2) M -> M * P
M -> P

3) E -> E + M
E -> M

LUANA BARRETO 18
 Exemplo:

E E*E EE+T
EET
E E/E ET
E E+E TT*F
E EE TT/F
E (E) TF
F id
E id F num
E num F (E)

LUANA BARRETO 19
 Uma GLC possui recurso esquerda, se h
pelo menos uma produo da forma A -> A.
Para eliminar as recurses diretas esquerda
nas produes:
A -> A1 | A2 | ... | An | ... | 1 | 2 | ... | m
onde nenhum i comea com A, deve-se
substituir estas produes pelas seguintes:
A -> 1A | 2A | ... | mA
A-> 1A | 2A | ... | nA |
onde A um novo no-terminal.

LUANA BARRETO 20
 Ex: E -> E+T | T
T -> T * F | F
F -> (E) | id

LUANA BARRETO 21
LUANA BARRETO 22
 Uma GLC est fatorada se ela
determinstica, ou seja, se ela no possui
produes para um mesmo no-terminal no
lado esquerdo cujo lado direito inicie com a
mesma cadeia de smbolos ou com smbolos
que derivam seqncias que iniciem com a
mesma cadeia de smbolos. A seguinte
gramtica no-determinstica:

LUANA BARRETO 23
 A idia bsica est em, quando no tiver claro
por qual das produes seguir para expandir
um no-terminal A, reescreve-se as
produes de forma a postergar a deciso at
que se tenha visto o suficiente da entrada
para realizar a escolha certa.

LUANA BARRETO 24
 Para fatorar uma GLC, deve-se alterar as
produes envolvidas no no-determinismo
da seguinte forma:

As produes com no-determinismo direto da

forma A -> | sero substitudas por:
A -> A
A-> |

LUANA BARRETO 25
 Na gramtica acima, temos = aS, assim,
com a eliminao do no-determinismo,
teramos a seguinte gramtica:
S -> aSS
S-> B | A
A -> a
B -> b

LUANA BARRETO 26
 Exemplo

LUANA BARRETO 27
 O no-determinismo indireto retirado
atravs de sua transformao em no-
determinismo direto (atravs de derivaes
sucessivas).
S -> AC | BC
A -> aD | cC
B -> aB | dD
C -> eC | eA
D -> fD | AB
O no-determinismo indireto se d pelo fato
de que A e B podem iniciar com o terminal a.

LUANA BARRETO 28
 Transforma-se primeiro o no-determinismo
indireto em no-determinismo direto,
substituindo os no-terminais A e B pelas
suas produes em S
S -> AC | BC S -> cCC | aDC | aBC | dDC
A -> aD | cC A -> aD | cB
B -> aB | dD B -> aB | dD
C -> eC | eA
C -> eC | eA D -> fD | AB
D -> fD | AB

LUANA BARRETO 29
 um programa construdo para uma
gramtica G que recebe como entrada uma
seqncia de smbolos terminais. Se a
seqncia de smbolos for uma sentena
vlida ele constri o analisador sinttico; caso
a sentena no pertena a linguagem descrita
por G, ele dever apresentar uma mensagem
de erro.

LUANA BARRETO 30
 Um autmato de pilha a estrutura formal
para efetuar o reconhecimento de sentenas.

LUANA BARRETO 31
 Aplica-se as regras abaixo para determinarmos Primeiros:
1. Inicialmente, para todos os no terminais X da gramtica G,
todos os conjuntos Primeiro(X) esto vazios
2. Se X no-terminal e X->a uma produo, ento se
acrescenta a ao Primeiro(X)
3. Se X no-terminal e X-> uma produo, ento se
acrescenta ao Primeiro(X)
4. Se X e B so no-terminais e X -> B uma produo, ento se
acrescenta Primeiro(B) ao Primeiro(X)
5. Se X->Y1Y2Y3...Yk uma produo e, para algum i, todos Y1,
Y2,...Yi-1 so no-terminais e derivam , ento Primeiro(Yi) est
em Primeiro(X), juntamente com todos os smbolos no-vazio de
Primeiro(Y1), Primeiro(Y2), ..., Primeiro(Yi-1). O smbolo vazio ser
adicionado a Primeiro(X) se todo Yj (j = 1, 2, .., k) derivar
6. Aplique as regras 2-5 enquanto houver modificao em algum
dos conjuntos

LUANA BARRETO 32


LUANA BARRETO 33
LUANA BARRETO 34
LUANA BARRETO 35
 Dada a gramtica abaixo:
S XYZ
X aXb |
Y cYZcX | d
Z eZYe | f

Primeiros(X) = {a, } Seguintes(X) = {c, d, b, e, f}

Primeiros(Y) = {c, d} Seguintes(Y) = {e, f}
Primeiros(Z) = {e, f} Seguintes(Z) = {$, c, d}
Primeiros(S) = {a, c, d, } Seguintes(S) = {$}

LUANA BARRETO 36