Por que a recursão esquerda é ruim?

20

No design do compilador, por que a recursão à esquerda deve ser eliminada nas gramáticas? Estou lendo que é porque pode causar uma recursão infinita, mas também não é verdade para uma gramática recursiva correta?

Rafael
fonte
2
Normalmente, os compiladores usam a análise de cima para baixo. Se você tiver recursão à esquerda, o analisador entrará em uma recursão infinita. No entanto, na recursão à direita, o analisador pode ver o prefixo da string que possui até o momento. Assim, ele pode verificar se a derivação foi "longe demais". Obviamente, é possível trocar as funções e interpretar expressões da direita, tornando a recursão à direita ruim e a recursão à esquerda.
Shaull
6
A recursão à esquerda é ruim, porque antigamente, quando os computadores tinham 16 KB de RAM, o gerador de analisador mais usado não conseguia lidar com isso.
21313 Andrej Bauer

Respostas:

15

Gramáticas recursivas à esquerda não são necessariamente uma coisa ruim. Essas gramáticas são facilmente analisadas usando uma pilha para acompanhar as frases já analisadas, como é o caso do analisador LR .

Lembre-se de que uma regra recursiva esquerda de uma gramática CF tem a forma:G=(V,Σ,R,S)

ααβ

αVβVΣ(V,Σ,R,S)

βαα

Sempre que um novo terminal está sendo recebido pelo analisador de gramática (do lexer), esse terminal é empurrado para o topo da pilha: essa operação é chamada de shift .

Cada vez que o lado direito de uma regra é correspondido por um grupo de elementos consecutivos no topo da pilha, esse grupo é substituído por um único elemento que representa a frase recém correspondida. Essa substituição é chamada de redução .

Com gramáticas recursivas corretas, a pilha pode crescer indefinidamente até que ocorra uma redução, limitando bastante as possibilidades de análise. No entanto, as recursivas à esquerda permitirão que o compilador gere reduções mais cedo (na verdade, o mais rápido possível). Veja a entrada da Wikipedia para mais informações.

didierc
fonte
Ajudaria se você definisse suas variáveis.
Andrew S
12

Considere esta regra:

example : 'a' | example 'b' ;

Agora considere um analisador LL tentando corresponder a uma sequência não correspondente, como 'b'esta regra. Como 'a'não corresponde, ele tentará corresponder example 'b'. Mas, para fazer isso, tem que corresponder example... o que estava tentando fazer em primeiro lugar. Poderia ficar parado tentando para sempre ver se ele pode corresponder, porque está sempre tentando corresponder o mesmo fluxo de tokens à mesma regra.

Para evitar isso, você teria que analisar da direita (o que é bastante incomum, até onde eu vi, e faria com que a recursão fosse correta), limite artificialmente a quantidade de aninhamento permitida ou faça a correspondência um token antes do início da recursão, para que haja sempre um caso base (ou seja, onde todos os tokens foram consumidos e ainda não há correspondência completa). Como uma regra recursiva à direita já faz a terceira, ela não tem o mesmo problema.

cHao
fonte
3
Você está presumindo cegamente que a análise é necessariamente uma análise de cima para baixo ingênua.
Reinierpost
Estou destacando uma armadilha de um método bastante comum de análise - um problema que pode ser facilmente evitado. Certamente é possível lidar com a recursão à esquerda, mas mantê-la cria uma limitação quase sempre desnecessária no tipo de analisador que pode usá-la.
cHao 21/02
Sim, é uma maneira mais construtiva e útil de colocá-lo.
Reinierpost
4

(Eu sei que essa pergunta já está bastante antiga, mas no caso de outras pessoas terem a mesma pergunta ...)

Você está perguntando no contexto de analisadores de descida recursiva? Por exemplo, para a gramática expr:: = expr + term | term, por que algo como isto (recursivo à esquerda):

// expr:: = expr + term
expr() {
   expr();
   if (token == '+') {
      getNextToken();
   }
   term();
}

é problemático, mas não é isso (certo recursivo)?

// expr:: = term + expr
expr() {
   term();
   if (token == '+') {
      getNextToken();
      expr();
   }
}

Parece que as duas versões expr()se chamam. Mas a diferença importante é o contexto - ou seja, o token atual quando essa chamada recursiva é feita.

No caso recursivo esquerdo, expr()chama-se continuamente com o mesmo token e nenhum progresso é feito. No caso recursivo correto, ele consome parte da entrada na chamada term()e no token PLUS antes de chegar à chamada expr(). Portanto, neste ponto, a chamada recursiva pode chamar termo e terminar antes de atingir o teste se novamente.

Por exemplo, considere analisar 2 + 3 + 4. O analisador recursivo esquerdo chama expr()infinitamente enquanto está preso no primeiro token, enquanto o analisador recursivo direito consome "2 +" antes de chamar expr()novamente. A segunda chamada expr()corresponde a "3 +" e chama expr()apenas os 4 restantes. Os 4 correspondem a um termo e a análise termina sem mais chamadas para expr().

user65808
fonte
2

Do manual do Bison:

"Qualquer tipo de sequência pode ser definida usando a recursão esquerda ou direita, mas você deve sempre usar a recursão esquerda , porque pode analisar uma sequência de qualquer número de elementos com espaço de pilha limitado. A recursão direita consome espaço na pilha de Bison em proporcional ao número de elementos na sequência, porque todos os elementos devem ser deslocados para a pilha antes que a regra possa ser aplicada uma única vez. Consulte O algoritmo do analisador de bisonte, para obter mais explicações sobre isso. "

http://www.gnu.org/software/bison/manual/html_node/Recursion.html

Portanto, depende do algoritmo do analisador, mas, como afirmado em outras respostas, alguns analisadores podem simplesmente não funcionar com recursão à esquerda

Eduardo Wada
fonte