Bottom-Up Parsing/Exercise 6: LALR(1)

Problema

Considere a seguinte gramática, onde A é o símbolo inicial e { w, x, y, z } é o conjunto de símbolos terminais.

H → A | B | w
A → B x | z H y
B → A x | y H z

1. Construa a tabela de análise para um analisador sintáctico ascendente LALR(1) para esta gramática, indicando o conjunto de estados do analisador e os símbolos de antevisão. A gramática é SLR(1)? Justifique.
2. Tal como apresentada, a gramática pode ser processada por um analisador LL(1)? Justifique.
3. Compacte a tabela de análise (de 1.), eliminando reduções unitárias e quase unitárias, bem como propagando reduções que permitam compactar a tabela.
4. Apresente a tabela com o conteúdo da pilha do analisador, a entrada e a acção realizada em cada passo da análise, para a sequência de entrada z y w z y. Em caso de conflitos, assuma o comportamento da ferramenta YACC.

Solution

Note-se que algumas das reduções na tabela apenas contêm o número (problema de digitalização).

Solução completa