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.

Soluções

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