Analisador (parser) Recursivo-Descendente Preditivo

Exemplo 1

Sobre o alfabeto {a,b}, considere linguagem

• L = {a^n * b^n : n >= 0}

descrita pela gramática

• S -> a S b | end

Construa-se um programa com lookahead de 1, em que o símbolo não terminal S seja uma função recursiva, que reconheça a linguagem L

Análise

No programa anterior:

• lookahead é uma variável que representa o próximo à entrada.

• adv() é uma função que avança na entrada, colocando em lookahead o próximo símbolo.

• eat(c) é uma função que verifica se no lookahead está o símblo c, gerando erro se não estiver, e avança para o próximo.

• Há duas produções da gramática com cabeça S, sendo a decisão central do programa a escolha de qual usar face ao valor do lookahead.

  • deve escolher-se S -> a S b se o lookahead for a.

  • e S -> end se o lookahead for $ ou b

No programa anterior, o símbolo $, marcador de fim de entrada, corresponde ao \n

• Uma palavra é aceite pelo programa se e só se

  • S(); eat($), não der erro.

Exemplo 2

Sobre o alfabeto {a; b}, considere linguagem

• 

descrita pela gramática

• S -> end | a B S | b A S A -> a | b A A B -> a B B | b

Construa um programa em que os símbolos não terminais sejas funções recursivas que reconheça a linguagem L.

• O programa terá 3 funções recursivas, A, B, S, semelhantes à função S do exemplo anterior.

• Em A, deve escolher-se A -> a se lookahead for a e A -> b AA se for b.

• Em B, deve escolher-se B -> b se lookahead for b e B -> a B B se for a.

• Em S, deve escolher-se S -> a B S se lookahead for a, S -> b A S se for b e S -> end se for $ (este último, mais tarde saber-se-á porquê).

Exemplo 2a

Sobre o alfabeto {a; b}, considere linguagem

• 

descrita pela gramática

• S -> end | a B | b A A -> a S | b A A B -> a B B | b S

Construa um programa em que os símbolos não terminais sejas funções recursivas que reconheça a linguagem L.

• O programa terá 3 funções recursivas, A, B e S, semelhantes á funcão S do exemplo anterior, exceto no critério de escolha da produção S -> end.

• Escolhar S -> end quando lookahead for $ pode não resolver.

• Por exemplo, com o lookahead igual a a, há situações em que se tem de escolher S -> a B e outras S -> end.

• É o que acontece com a entrada bbaa

  • S => b A => bb AA => bba S A => ... momento em que o S tem de ser expandido para o end e o lookahead é a.

Exemplo 2b

Sobre o alfabeto {a; b}, considere linguagem

• 

descrita pela gramática

• S -> end | a B | b A A -> a S | b A A B -> a B B | b S

Construa um programa em que os símbolos não terminais sejas funções recursivas que reconheça a linguagem L.

• Tal como no caso anterior, escolher S -> end quando lookahead for $ pode não resolver.

Exemplo 3

Sobre o alfabeto {a,b}, considere linguagem

• 

descrita pela gramática

• S -> a S b | a b

Construa um programa em que o símbolo não terminal S seja uma função recursiva que reconheça a linguagem L.

• Como escolher entre as duas produções se ambas começam pelo mesmo símbolo ?

• Há duas abordagens:

  • Pôr em evidência o a à esquerda, transformando a gramática para

    • S -> a X X -> S b | b

  • Aumentar o número do símbolos de lookahead para 2

    • se for aa, escolhe-se S -> a S b

    • se for ab, escolhe-se S -> a b

Exemplo 3

Sobre o alfabeto {a, b}, considere linguagem

• 

descrita pela gramática

• S -> a S b | a b

Construa um programa em que o símbolo não terminal S seja uma função recursiva quem reconheça a linguagem L.

• Há duas abordagens:

  • Pôr em evidência o a à esquerda, transformando a gramática para

    • S -> a X X -> S b | b

  • Aumentar o número de símbolo de lookahead para 2

    • se for aa, escolhe-se S -> a S b

    • se for aa, escolhe-se S -> a b

Exemplo 4

Sobre o alfabeto {a, b}, considere linguagem

• 

descrita pela gramática

• S -> S a b | a b

Construa um programa em que o símbolo não terminal S seja uma função recursiva que reconheça a linguagem L.

• Escolher a primeira produção cria um ciclo infinito, por causa da recursividade à esquerda

  • O ANTLR consegue lidar com este tipo (simples) de recursividade à esquerda, mas falha com outros tipos.

  • Mas, em geral os reconhecedores descendetes não lidam com recursividades à esquerda.

Solução geral: eliminar a recursividade à esquerda