Em termos leigos, o que resta de recursão?

De acordo com uma página no code.google.com, "recursão à esquerda" é definida da seguinte forma:

A recursão à esquerda refere-se apenas a qualquer termo-terminal recursivo que, quando produz uma forma sentencial que se contenha, essa nova cópia de si mesma aparece à esquerda da regra de produção.

A Wikipedia oferece duas definições diferentes:

1. Em termos de gramática livre de contexto, um r não terminal é recursivo à esquerda se o símbolo mais à esquerda em qualquer uma das produções de r ('alternativas') seja imediatamente (recursivo à esquerda direto / imediato) ou através de algum outro tipo não terminal definições (indiretas / ocultas à esquerda recursivas) reescrevem para r novamente.

2. "Uma gramática é recursiva à esquerda se pudermos encontrar alguma A não terminal que, eventualmente, derivará uma forma sentencial como o símbolo da esquerda".

Estou apenas começando com a criação da linguagem aqui, e estou fazendo isso no meu tempo livre. No entanto, quando se trata de selecionar um analisador de idioma, se a recursão esquerda é suportada por esse analisador ou se esse analisador é um problema que aparece imediatamente na frente e no centro. Procurar termos como "forma sentencial" apenas leva a outras listas de jargões, mas a distinção de recursão "esquerda" quase tem que ser algo muito simples. Tradução por favor?

Uma regra Ré recursiva à esquerda se, para descobrir se há Rcorrespondências, você precisa primeiro descobrir se Rcorresponde. Isso acontece quando Raparece, direta ou indiretamente, como o primeiro termo em alguma produção em si.

Imagine uma versão em brinquedo da gramática para expressões matemáticas, com apenas adição e multiplicação para evitar distrações:

Expression ::= Multiplication '+' Expression
            || Multiplication

Multiplication ::= Term '*' Term
                 || Term

Term ::= Number | Variable

Como está escrito, não há recursão à esquerda aqui - poderíamos passar essa gramática para um analisador de descida recursiva.

Mas suponha que você tenha tentado escrever desta maneira:

Expression ::= Expression '*' Expression
            || Expression '+' Expression
            || Term

Term ::= Number | Variable

Essa é uma gramática, e alguns analisadores podem lidar com ela, mas os analisadores de descida recursiva e LL não podem - porque a regra para Expressioncomeça com Expressionela mesma. Deveria ser óbvio porque, em um analisador de descida recursiva, isso leva à recursão ilimitada sem realmente consumir qualquer entrada.

Não importa se a regra se refere direta ou indiretamente a si mesma; se Atem uma alternativa que começa com B, e Btem uma alternativa que começa com A, então Ae Bsão indiretamente recursivos à esquerda e, em um analisador de descida recursiva, suas funções correspondentes levarão a uma recursão mútua interminável.

Vou dar uma facada em colocá-lo nos termos dos leigos.

Se você pensa em termos da árvore de análise (não da AST, mas da visitação e expansão da entrada do analisador), a recursão à esquerda resulta em uma árvore que cresce para a esquerda e para baixo. A recursão correta é exatamente o oposto.

Como exemplo, uma gramática comum em um compilador é uma lista de itens. Vamos pegar uma lista de strings ("vermelho", "verde", "azul") e analisá-la. Eu poderia escrever a gramática de algumas maneiras. Os seguintes exemplos são diretamente à esquerda ou à direita recursivos, respectivamente:

arg_list:                           arg_list:
      STRING                              STRING
    | arg_list ',' STRING               | STRING ',' arg_list 

As árvores para estas analisam:

         (arg_list)                       (arg_list)
          /      \                         /      \
      (arg_list)  BLUE                  RED     (arg_list)
       /       \                                 /      \
   (arg_list) GREEN                          GREEN    (arg_list)
    /                                                  /
 RED                                                BLUE

Observe como cresce na direção da recursão.

Isso não é realmente um problema, não há problema em escrever uma gramática recursiva esquerda ... se a sua ferramenta de análise puder lidar com isso. Os analisadores de baixo para cima lidam perfeitamente com isso. O mesmo acontece com os analisadores LL mais modernos. O problema com gramáticas recursivas não é recursão, é recursão sem avançar o analisador ou recorrendo sem consumir um token. Se sempre consumimos pelo menos 1 token quando recursamos, chegamos ao final da análise. A recursão esquerda é definida como recorrente sem consumir, que é um loop infinito.

Essa limitação é puramente um detalhe de implementação da implementação de uma gramática com um analisador de LL de cima para baixo ingênuo (analisador de descida recursiva). Se você deseja manter as gramáticas recursivas esquerdas, pode lidar com isso reescrevendo a produção para consumir pelo menos 1 token antes da recorrência, para garantir que nunca fiquemos presos no loop improdutivo. Para qualquer regra gramatical que seja recursiva à esquerda, podemos reescrevê-la adicionando uma regra intermediária que aplique a gramática a apenas um nível de aparência, consumindo um token entre as produções recursivas. (OBSERVAÇÃO: não estou dizendo que essa é a única maneira ou a maneira preferida de reescrever a gramática, apenas apontando a regra generalizada. Neste exemplo simples, a melhor opção é usar a forma recursiva correta). Como essa abordagem é generalizada, um gerador de analisador pode implementá-lo sem envolver o programador (teoricamente). Na prática, acredito que o ANTLR 4 agora faz exatamente isso.

Para a gramática acima, a implementação LL exibindo recursão à esquerda ficaria assim. O analisador começaria com a previsão de uma lista ...

bool match_list()
{
    if(lookahead-predicts-something-besides-comma) {
       match_STRING();
    } else if(lookahead-is-comma) {
       match_list();   // left-recursion, infinite loop/stack overflow
       match(',');
       match_STRING();
    } else {
       throw new ParseException();
    }
}

Na realidade, estamos realmente lidando com "implementação ingênua", ie. inicialmente predicamos uma determinada sentença e, em seguida, recursivamente denominamos a função dessa predição, e essa função ingenuamente chama a mesma predição novamente.

Os analisadores de baixo para cima não têm o problema de regras recursivas em nenhuma direção, porque não reanalisam o início de uma frase, trabalham trabalhando colocando a frase novamente.

A recursão na gramática é apenas um problema se produzirmos de cima para baixo, ou seja. nosso analisador funciona "expandindo" nossas previsões à medida que consumimos tokens. Se, em vez de expandir, colapsarmos (as produções forem "reduzidas"), como em um analisador ascendente LALR (Yacc / Bison), a recursão de ambos os lados não será um problema.