Tópicos
Análise ascendente LR(0) e SLR(1). Items LR(0).
Exercício 1
Considere a gramática seguinte, onde
?,
:,
# e
id são símbolos terminais.
E |
-> |
E
? T
: E | T |
T |
-> |
# T
id |
id |
- Construa a gramática aumentada G', obtida a partir da gramática G. Determine os conjuntos FIRST e FOLLOW da gramática G'.
- Construa os estados do analisador SLR(1) explicitando por extenso a lista de configurações de cada estado. Construa a tabela de análise SLR(1) da gramática.
Nota: existem 11 estados.
- Compacte a tabela de análise que obteve, eliminando as reduções unitárias e quase unitárias, bem como propagar as reduções que permitam compactar a tabela.
- Realize a análise da sequência
id ? # id id : id indicando o conteúdo da pilha, da sequência de entrada e as acções efectuadas em cada passo.
Exercício 2
Considere a gramática seguinte:
S |
-> |
B B |
B |
-> |
d E |
E |
-> |
d E |
a |
- Indique o conjunto de estados SLR(1) desta gramática.
- Construa a tabela de análise SLR(1).
- A gramática tem conflitos? Se sim, de que tipo são? Justifique.
- Realize a análise da sequência
ddada, mostrando em cada passo o conteúdo da pilha, da memória de entrada e das acções utilizadas.
Exercício 3
Considere a gramática seguinte:
S |
-> |
A
a A
b | B
b B
a |
A |
-> |
ε
|
B |
-> |
ε
|
Demonstre que esta gramática é LL(1), mas não LR(0).