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
Last updated
