Mencionei a recursão esquerda como uma pedra de tropeço várias vezes, e é hora de descobrir isso. O principal problema é que um analisador com uma descida recursiva esquerda falha instantaneamente devido a um estouro de pilha.
Conteúdo da série Ps Parser Python Considere esta regra gramatical hipotética:
expr: expr '+' term | term
Se implementássemos esse pedaço de gramática no método analisador recursivo esquerdo, obteríamos algo como o seguinte:
def expr(): if expr() and expect('+') and term(): return True if term(): return True return False
Assim, expr() começa com uma chamada para expr() , que começa com uma chamada para expr() , que começa com uma chamada ... Isso só pode terminar com um estouro de pilha, expresso como uma exceção RecursionError .
A solução tradicional é reescrever a gramática. Nas partes anteriores, fiz exatamente isso. De fato, a regra gramatical acima pode ser reescrita da seguinte maneira:
expr: term '+' expr | term
No entanto, na etapa de construção da árvore de análise, sua forma seria diferente. Isso pode arruinar a situação se adicionarmos o operador '-' à gramática (já que a - (b - c) não a - (b - c) o mesmo que (a - b) - c ). Isso geralmente é resolvido com funções PEG mais poderosas, como agrupamento e iteração, e podemos reescrever a regra acima como:
expr: term ('+' term)*
Na verdade, é assim que a gramática Python atual é escrita para o analisador pgen (que tem os mesmos problemas com as regras recursivas à esquerda).
No entanto, há um pequeno problema: como operadores como '+' e '-' (em Python) são na maioria binários, quando analisamos algo como a + b + c , temos que passar pelo resultado da análise (que essencialmente uma lista de ['a', '+', 'b', '+', 'c'] ) para criar uma árvore de análise recursiva esquerda (que seria algo parecido com isto [['a', '+', 'b'] , '+', 'c'] ).
A gramática recursiva esquerda original já sugere a associatividade desejada, portanto seria bom gerar um analisador diretamente desse formulário. E nós podemos! Um leitor apontou um bom truque com provas matemáticas fáceis de implementar. Agora vou tentar explicar.
Vejamos um exemplo de entrada foo + bar + baz . A árvore de análise que gostaríamos de obter corresponde a (foo + bar) + baz . Isso requer três chamadas recursivas à esquerda para a função expr() : uma corresponde ao operador de nível superior '+' (ou seja, o segundo); mais um - para o operador interno '+' (ou seja, o primeiro); e a terceira é a escolha da segunda alternativa (isto é, term ).
Como não sou bom em desenhar diagramas reais usando ferramentas especiais, mostrarei isso aqui usando arte ASCII:
expr------------+------+ | \ \ expr--+------+ '+' term | \ \ | expr '+' term | | | | term | | | | | 'foo' 'bar' 'baz'
A idéia é que, na função expr() , precisamos de um “oráculo” que nos diga se deve escolher a primeira alternativa (ou seja, a chamada recursiva para expr() ) ou a segunda (ou seja, o term() chamada). Na primeira chamada para expr() oráculo deve nos dizer para seguir a primeira alternativa ( expr() ); na segunda chamada (recursiva) - da mesma forma, mas na terceira deve nos solicitar a chamada term() . No código, ficará assim:
def expr(): if oracle() and expr() and expect('+') and term(): return True if term(): return True return False
Como escrever tal oráculo? Vamos ver ... Podemos tentar rastrear o número de chamadas expr() esquerda (recursivas) na pilha de chamadas e compará-lo com o número de operadores '+' na expressão a seguir. Se a pilha de chamadas for mais profunda que o número de instruções, o oráculo deve retornar falso (forçar-nos a selecionar o term() ). Mal posso esperar para implementar isso com sys._getframe() , mas existe uma maneira melhor: vamos virar a pilha de chamadas!
A idéia é que começemos com uma chamada em que o oráculo retorne falso e salve o resultado. Isso nos dá a sequência expr() -> term() -> 'foo' . (Ele deve retornar uma árvore de análise para o term inicial, ou seja, 'foo' . O código acima retorna True , mas na segunda parte da série de artigos eu já mostrei como retornar a árvore de análise.) Esse oráculo é fácil de implementar, pois deveria basta retornar False na primeira chamada - não é necessário verificar ou espiar no futuro.
Então chamamos expr() novamente, e desta vez o oráculo retorna True , mas, em vez da chamada recursiva esquerda para expr() , substituímos o resultado salvo pela chamada anterior. E como o operador esperado '+' e o próximo token adequado também estão presentes, isso nos dará uma árvore de análise para foo + bar .
Mais uma vez, repetimos o algoritmo e, novamente, tudo acontece: desta vez, obtemos uma árvore de análise para a expressão completa, e é realmente recursiva à esquerda ( (foo + bar) + baz ).
Em seguida, repetimos o algoritmo novamente. Mas desta vez, embora o Oracle retorne True e o resultado salvo da chamada anterior também esteja disponível, não há mais operador '+' e a primeira alternativa falha. Assim, tentamos a segunda opção, que obtém sucesso, e encontra apenas o termo inicial ( 'foo' ). Esse resultado é pior que o obtido na primeira alternativa, portanto, nesta etapa, paramos e salvamos a análise mais longa (ou seja, (foo + bar) + baz ).
Para transformar isso em código funcional, modifiquei um pouco o algoritmo para combinar a chamada oracle() com a chamada recursiva esquerda para expr() . Vamos chamá-lo de oracle_expr() . Código:
def expr(): if oracle_expr() and expect('+') and term(): return True if term(): return True return False
A seguir, escreveremos um wrapper que implementa a lógica descrita acima. Ele usa uma variável global (não se preocupe, vou me livrar dela mais tarde). A função oracle_expr() lê a variável global e o wrapper a controla:
saved_result = None def oracle_expr(): if saved_result is None: return False return saved_result def expr_wrapper(): global saved_result saved_result = None parsed_length = 0 while True: new_result = expr() if not new_result: break new_parsed_length = <calculate size of new_result> if new_parsed_length <= parsed_length: break saved_result = new_result parsed_length = new_parsed_length return saved_result
O código, é claro, é terrível, mas pelo menos transmite a essência do algoritmo. Vamos refatorá-lo para que possamos nos orgulhar disso.
O entendimento mais importante (que me pertence, embora provavelmente não seja o primeiro a perceber isso) é que podemos usar o cache de memorização em vez de uma variável global. Nele, armazenaremos o resultado de uma chamada para outra. Então nos livramos de uma função separada oracle_expr() , porque podemos gerar uma chamada padrão para expr() independentemente de estar em uma posição recursiva à esquerda ou à direita.
Portanto, precisamos de um decorador @memoize_left_rec separado, usado apenas para regras recursivas à esquerda. Ele chama a função oracle_expr() , puxando o valor armazenado do cache de memorização e contém um loop que chama a função expr() várias vezes, até que cada novo resultado seja comparável a uma porção cada vez maior dos dados de entrada que o anterior. E, é claro, uma vez que cada posição de entrada e cada método de análise são armazenados em cache separadamente, não se preocupa com o retorno ou algumas regras recursivas (por exemplo, na gramática de brinquedos que usei, tanto expr quanto term são deixados recursivos).
Outra das vantagens do protótipo que criei na terceira parte é que facilita verificar se o novo resultado é maior que o antigo: o método mark() retorna o índice na matriz de tokens de entrada, para que possamos usá-lo em vez de parsed_length .
Omiti a prova de por que esse algoritmo sempre funciona, por mais insana que seja a gramática. Na verdade, eu nem li. Vejo que isso funciona para casos simples, como expr na minha gramática de brinquedos, bem como para casos um pouco mais complexos (por exemplo, usando a recursão esquerda oculta por trás de elementos opcionais em uma alternativa ou usando a recursão mútua entre várias regras). A situação mais difícil que me lembro na gramática Python ainda é resolvida por esse algoritmo, então confio apenas no teorema e nas pessoas que o provaram.
Vamos escrever o código de batalha.
Primeiro, o gerador do analisador deve determinar quais regras são deixadas recursivas. Este é um problema resolvido na teoria dos grafos. Não vou mostrar o algoritmo aqui e, de fato, quero simplificá-lo ainda mais. Suponho que as únicas regras recursivas à esquerda na gramática são diretamente recursivas à esquerda, como expr em nossa gramática de brinquedos. Em seguida, para verificar a recursividade à esquerda, basta procurar uma alternativa que comece com o nome da regra atual:
def is_left_recursive(rule): for alt in rule.alts: if alt[0] == rule.name: return True return False
Agora vamos mudar o gerador do analisador para que, para regras recursivas à esquerda, gere outro decorador. Lembre-se de que na terceira parte, @memoize todos os métodos do analisador no @memoize . Agora faremos uma pequena alteração no gerador para que, para as regras recursivas à esquerda, usemos @memoize_left_rec e, em seguida, implementaremos a mágica no decorador memoize_left_rec . O restante do gerador e outros códigos não precisam ser alterados! (Embora eu tenha que mexer no código de visualização)
Para referência, aqui está o decorador original @memoize , copiado da parte 3. Lembre-se de que self é uma instância do Parser que possui um atributo de memo (inicializado com um dicionário vazio) e os métodos mark() e reset() que obtêm e definem a posição atual tokenizer:
def memoize(func): def memoize_wrapper(self, *args): pos = self.mark() memo = self.memos.get(pos) if memo is None: memo = self.memos[pos] = {} key = (func, args) if key in memo: res, endpos = memo[key] self.reset(endpos) else: res = func(self, *args) endpos = self.mark() memo[key] = res, endpos return res return memoize_wrapper
O decorador @memoize lembra as chamadas anteriores para cada posição no fluxo de entrada - para cada posição na matriz (lenta) de tokens de entrada, há um dicionário de memo separado. As quatro primeiras linhas de memoize_wrapper dedicadas a obter o dicionário de memo correto.
E aqui está @memoize_left_rec . Somente o ramo else é um pouco diferente da implementação em @memoize acima:
def memoize_left_rec(func): def memoize_left_rec_wrapper(self, *args): pos = self.mark() memo = self.memos.get(pos) if memo is None: memo = self.memos[pos] = {} key = (func, args) if key in memo: res, endpos = memo[key] self.reset(endpos) else:
Provavelmente é interessante como isso funciona para o método expr() . Vamos ver como o seguinte código será executado:
@memoize_left_rec def expr(self): pos = self.mark() if ((expr := self.expr()) and self.expect('+') and (term := self.term())): return Node('expr', [expr, term]) self.reset(pos) if term := self.term(): return Node('term', [term]) self.reset(pos) return None
No exemplo de análise foo + bar + baz .
Sempre que você chama a função expr() , a chamada é "conectada" pelo decorador que está procurando a chamada anterior na posição atual. Na primeira chamada, chegamos ao ramo else , onde chamamos repetidamente a função decorada expr() . Obviamente, voltaremos ao decorador primeiro, mas desta vez já existe algum valor no cache, portanto a recursão é interrompida.
O que acontece depois? O valor inicial do cache é calculado nesta linha:
Isso leva ao fato de que expr() decorado retorna None , após o qual o primeiro if em expr() cai (quando expr: = self.expr() ). Ou seja, passamos para o segundo if , que reconhece com sucesso o term (em nosso exemplo, 'foo' ) e expr retorna uma instância de Node . De onde estamos voltando? Para o while no decorador. Atualizamos o cache de memorização com um novo resultado (a instância do Node ) e, em seguida, executamos a próxima iteração.
expr() é chamado novamente e, desta vez, a chamada recursiva interceptada retorna a instância em cache do Node (term) e prossegue para a chamada em expect('+') . Está tudo em ordem, pois agora estamos no primeiro operador '+' . Depois disso, procuramos um termo que também seja bem-sucedido (encontrado 'bar' ).
Portanto, agora expr() , já tendo reconhecido foo + bar , retorna while , que executa as mesmas ações: atualiza o cache de memorização com um novo resultado (mais longo) e inicia a próxima iteração.
Este jogo é repetido novamente. Novamente, a chamada recursiva interceptada expr() recupera um novo resultado (desta vez foo + bar ) do cache, e esperamos ver outro '+' (segundo) e outro term ( 'baz' ). Criamos um Node representa (foo + bar) + baz e o retornamos while , que o coloca no cache e se repete novamente.
Mas agora vamos seguir outro ramo do algoritmo. Esperamos encontrar outro '+' , mas não o encontramos! Portanto, essa chamada para expr() retorna para sua segunda alternativa e retorna apenas term . Quando isso ocorre antes do while , esse resultado é mais curto que o anterior. Portanto, ele interrompe e retorna um resultado mais longo ( (foo + bar) + baz ) para quem iniciou a chamada expr() (por exemplo, a chamada de statement() não é mostrada aqui).
Portanto, é aqui que a história de hoje termina: implementamos com sucesso a recursão esquerda em um analisador PEG. Na próxima semana, pretendo discutir a adição de “ações” à gramática, o que nos permitirá personalizar o resultado retornado pelo método analisador para essa alternativa (em vez de sempre retornar uma instância do Node ).
Se você quiser brincar com o código, confira o repositório do GitHub . Também adicionei um código de visualização para recursão à esquerda, mas não estou muito satisfeito com isso, então não fornecerei um link para ele aqui.
Licença para este artigo e código citado: CC BY-NC-SA 4.0