Tópicos

Gramáticas. Conjuntos FIRST e FOLLOW. Análise sintáctica descendente LL(1).

Exercício 1

Considere a gramática:

bexpr	->	bexpr or bexpr | bterm
bterm	->	bterm and bterm | bfactor
bfactor	->	not bfactor | ( bexpr ) | true | false

1. Identifique os símbolos terminais e não terminais da gramática.
2. Demonstre que a gramática é ambígua derivando 2 árvores de análise diferentes para a mesma sequência de entrada.
3. Construa uma gramática não ambígua equivalente.
4. Construa a árvore de análise para a entrada:
   not ( true or false and true )

Exercício 2

Considere a seguinte gramática:

E	->	E + T | E - T | T
T	->	T * F | T / F | F
F	->	( E ) | id

1. Transforme a gramática por forma a poder ser analisada por um analisador sintáctico preditivo.
2. Calcule os conjuntos FIRST e FOLLOW para os símbolos não terminais.
3. Elabore a tabela de análise do analisador sintáctico preditivo para esta gramática.
4. Apresente uma tabela com o conteúdo da pilha, a entrada e a acção realizada em cada passo da análise quando a sequência de entrada é: a*(b+c).

Exercício 3

Considere a seguinte gramática, onde S é o símbolo inicial e { d, e, f, g, h } é o conjunto de símbolos terminais:

S	->	A B d | C d
A	->	C d h | S e
C	->	g B | h f
B	->	g | ε

1. Examine a gramática e transforme-a por forma a poder construir um analisador sintáctico preditivo para a linguagem correspondente.
2. Construa os conjuntos FIRST e FOLLOW dos símbolos não terminais da gramática obtida na pergunta anterior.
3. Construa a tabela de análise do analisador sintáctico preditivo.
4. Apresente uma tabela com o conteúdo da pilha, a entrada e a acção realizada em cada passo da análise quando a sequência de entrada é: hfded.

Resolução

Soluções dos exercícios no wiki da disciplina.