Análise Sintática de Gramática G3

Prévia do material em texto

“iIntrComp” — 2008/10/6 — 15:46 — page 148 — #160
148 · Introdução à Compilação ELSEVIER
preciso obter as relações de Wirth-Weber, verificar se não há conflitos entre as
relações para nenhum par de símbolos e, para as produções que terminam com
o mesmo símbolo, verificar se não há ambigüidade entre o símbolo anterior e
uma possível redução do símbolo.
Para obter as relações de Wirth-Weber, é preciso obter os conjuntos ESQ e
DIR para cada símbolo não-terminal de G3:
ESQ(E) = {E, M, P, (, v} DIR(E) = {M, P, ), v}
ESQ(M) = {M, P, (, v} DIR(M) = {P, ), v}
ESQ(P ) = {(, v} DIR(P ) = {), v}
A primeira relação,≈, é obtida por inspeção das produções. Para G3 obtêm-
se:
E ≈ + + ≈ M
M ≈ × × ≈ P
( ≈ E E ≈ )
Para a segunda relação,≺, é preciso analisar as relações≈ que têm símbolos
não-terminais do lado direito e os elementos do conjunto ESQ desses símbolos.
Como + ≈ M e ESQ(M) = {P, (, v}, então + ≺ P , + ≺ ( e + ≺ v. Do
mesmo modo obtêm-se novas relações a partir de × ≈ P e de ( ≈ E. Portanto,
todas as relações ≺ são:
+ ≺ M + ≺ P
+ ≺ ( + ≺ v
× ≺ ( × ≺ v
( ≺ E ( ≺ M
( ≺ P ( ≺ (
( ≺ v
A terceira relação, �, é obtida a partir da análise das relações ≈ entre
um símbolo não-terminal e um símbolo terminal ou entre dois símbolos não-
terminais. Há três relações no primeiro caso: E ≈ +, M ≈ × e E ≈ ), das
quais são derivadas as relações:
M � + P � +
) � + v � +
P � × ) � ×
v � × M � )
P � ) ) � )
v � )
“iIntrComp” — 2008/10/6 — 15:46 — page 149 — #161
ELSEVIER Análise sintática · 149
Como não há nenhuma relação ≈ entre dois símbolos não-terminais, este é o
conjunto completo de relações � para G3.
A Tabela 4.4 apresenta o conjunto completo das relações de Wirth-Weber
entre os símbolos da gramática G3.
Tabela 4.4 Relações de Wirth-Weber para a gramática G3
E M P + × ( ) v
E ≈ ≈
M � ≈ �
P � � �
+ ≈≺ ≺ ≺ ≺
× ≈ ≺ ≺
( ≈≺ ≺ ≺ ≺ ≺
) � � �
v � � �
Como não há nenhum par de símbolos que esteja relacionado simultanea-
mente pela relação � e por alguma outra relação, a primeira condição para que
a gramática seja de precedência fraca é satisfeita.
A segunda condição demanda a análise das produções que terminam com
o mesmo símbolo. O primeiro par de produções que precisa ser analisado é
E → E + M e E → M , pois ambas terminam com o símbolo M . A condição
que precisa ser analisada é se há alguma relação entre o símbolo que precede
M na primeira produção, nesse caso +, e o lado esquerdo da segunda produção,
nesse caso E. Como pode ser observado pela entrada vazia na linha + com
coluna E, não há nenhuma relação entre + e E. Então, pela análise desse par
de produções, a gramática é de precedência fraca.
A mesma análise deve ser realizada para o par de produções M → M × P
e M → P . Da mesma forma, é possível observar que não há relação entre o
símbolo que precede P na primeira produção, ×, e o símbolo não-terminal do
lado esquerdo da segunda produção, M , pois a entrada na linha × e coluna M
está vazia. Como todas as regras que terminam com o mesmo símbolo foram
analisadas e não resultaram em conflitos, a gramática G3 é de precedência fraca.
Para a construção da tabela DR, é preciso incluir as relações envolvendo o
símbolo terminador de sentença $ e os símbolos que pertencem aos conjuntos
ESQ e DIR do símbolo sentencial E. Como ESQ(E) = {E, M, P, (, v},
“iIntrComp” — 2008/10/6 — 15:46 — page 150 — #162
150 · Introdução à Compilação ELSEVIER
então
$ ≺ E
$ ≺ M
$ ≺ P
$ ≺ (
$ ≺ v
Do mesmo modo, como DIR(E) = {M, P, ), v}, então
M � $
P � $
) � $
v � $
Assim, a Tabela 4.5 apresenta a tabela DR para G3.
Tabela 4.5 Tabela DR para a gramática G3
+ × ( ) v $
E D D
M R D R R
P R R R R
+ D D
× D D
( D D
) R R R R R
v R R R R R
$ D D
Considere como a tabela é utilizada no procedimento de reconhecimento da
sentença v + v × v. No estado inicial, a pilha contém apenas o símbolo delimi-
“iIntrComp” — 2008/10/6 — 15:46 — page 151 — #163
ELSEVIER Análise sintática · 151
tador de sentença e a lista contém todos os tokens da sentença e o delimitador
de sentença ao final:
Pilha:
$
Lista de tokens:
v + v × v $
A primeira ação indica deslocamento, portanto o próximo estado é
Pilha:
v
$
Lista de tokens:
+ v × v $
Essa ação tem um efeito na construção da árvore sintática, que é a criação
de um nó folha para a árvore com o token v.
Para esse estado, com v no topo da pilha e + como próximo token, a ação
indicada é redução, nesse caso pela produção 6, P → v, a única aplicável.
Assim, o símbolo v no topo da pilha (o lado direito da produção) é substituído
pelo símbolo não-terminal P , o lado esquerdo da produção:
Pilha:
P
$
Lista de tokens:
+ v × v $
Na construção da árvore sintática, essa ação corresponde à criação do nó pai
para o nó que havia sido criado pela ação anterior:
P
v
Com o símbolo P no topo da pilha e + como primeiro elemento da lista, a
próxima ação é novamente redução. A produção 4, M → P , é a única aplicável
e o novo estado das estruturas de dados é:
Pilha:
M
$
Lista de tokens:
+ v × v $
Árvore: M
P
v