Alguns anos atrás, alguém me perguntou se faz sentido converter Python em um analisador PEG (ou em uma gramática PEG; não me lembro exatamente quem e quando era). Então olhei para ele um pouco, mas não cheguei a nenhuma conclusão e, portanto, abandonei este tópico. Recentemente, aprendi mais sobre PEG (análise de expressões de análise de gramática, análise de expressão de análise de análise) e agora acho que essa é uma alternativa interessante ao gerador de analisador auto-escrito que foi desenvolvido há 30 anos, quando eu estava apenas começando a trabalhar em Python. Eu chamei de “pgen”, e esse foi provavelmente o primeiro pedaço de código que escrevi para o Python.
Conteúdo da série Ps Parser Python Atualmente, estou interessado no analisador PEG porque estou um pouco irritado com as limitações do pgen. Ele é construído sobre sua própria implementação do LL (1), que possui várias suposições. Por exemplo, eu não gostava de regras gramaticais que pudessem gerar linhas vazias, então as proibi. E, assim, simplificou o algoritmo para criar tabelas de análise. Também inventei minha própria notação gramatical do tipo EBNF, da qual ainda gosto muito.
Aqui estão alguns problemas com o pgen que me incomodam. O "1" no nome LL (1) implica que ele apenas analise o próximo token, e isso limita nossa capacidade de criar boas regras gramaticais. Por exemplo, uma instrução Python pode ser uma expressão ou atribuição (ou outra coisa, mas todas elas começam com uma palavra-chave destacada, como if ou def ). Gostaria de descrever a sintaxe usando a notação pgen. Observe que este é apenas um exemplo simplificado, que é um subconjunto do Python, como geralmente é feito ao descrever o design da linguagem. Essa será uma gramática de brinquedo que será útil para mais demonstrações.
statement: assignment | expr | if_statement expr: expr '+' term | expr '-' term | term term: term '*' atom | term '/' atom | atom atom: NAME | NUMBER | '(' expr ')' assignment: target '=' expr target: NAME if_statement: 'if' expr ':' statement
Algumas palavras sobre notação: NAME e NUMBER são tokens e são predefinidos fora da gramática. Seqüências de caracteres entre aspas do tipo '+' ou 'if' também são tokens. (Adiamos falar sobre eles da próxima vez). As regras gramaticais começam com o nome da regra, seguido por : e, em seguida, uma ou mais alternativas, separadas por | .
O problema é que, se você descrever a gramática dessa maneira, o pgen não funcionará. Isso se deve ao fato de algumas regras ( expr e term ) serem recursivas, e ele não é inteligente o suficiente para lidar corretamente com essas situações. Geralmente, isso é resolvido reescrevendo apenas essas regras, mantendo as outras regras inalteradas. Por exemplo:
expr: term ('+' term | '-' term)* term: atom ('*' atom | '/' atom)*
Isso revela várias possibilidades de EBNF na pgen: você pode aninhar alternativas entre parênteses e criar repetições colocando * após o elemento. Portanto, a regra para a expressão expr aqui significa "é um termo seguido por zero ou mais repetições da sequência <termo mais ou menos, seguido pelo termo>". Essa gramática usa o mesmo idioma da primeira versão, mas, novamente, não reflete a intenção de design do idioma. Em particular, isso não mostra que os operadores estão ligados à esquerda, e isso é importante quando você está tentando gerar código.
Mas há outro problema irritante neste exemplo (e também no Python). Devido à análise de apenas um token, o analisador não pode determinar para o que está olhando - o início de uma expressão ou atribuição. No início do processamento do operador, o analisador deve decidir apenas o primeiro token, qual alternativa ele analisa. (Por quê? É assim que a implementação da análise na pgen funciona) Digamos que nosso programa seja o seguinte:
answer = 42
Este programa é representado por três tokens: NAME (com valor de answer ), = e NUMBER (com valor 42 ). A única coisa que sabemos no início da análise é o primeiro token NAME . A regra que estamos tentando analisar nesse estágio é statement (o caractere inicial da gramática). Três alternativas são definidas para ele: expr , assignment e if_statement . Podemos excluir imediatamente if_statement , porque o token anterior não é if . Mas tanto a expr quanto a assignment podem começar com o token NAME e, por isso, a pgen rejeita nossa gramática como ambígua.
Isso não está totalmente correto, já que tecnicamente a própria gramática não está; Não consigo encontrar uma formulação mais precisa, então vamos nos debruçar sobre essa. E como a pgen resolve isso? Ele calcula algo chamado PRIMEIRO conjunto para cada regra gramatical e, se eles se cruzam, gera uma exceção.
Portanto, não podemos resolver esse problema fornecendo ao analisador um buffer de visualização maior? Para o nosso exemplo, um segundo token de visualização é suficiente, pois nesta gramática o segundo token de atribuição deve ser = . Mas em uma linguagem mais realista como Python, você pode precisar de um buffer ilimitado, pois o conteúdo à esquerda do = token = pode ser arbitrariamente complexo, por exemplo:
table[index + 1].name.first = 'Steven'
Nesse caso, você terá que analisar dez tokens antes de nos encontrarmos. Mas garanto-lhe, pode haver expressões mais longas. Para resolver esse problema na pgen, alteramos o analisador de gramática para aceitar algumas expressões incorretas, adicionando uma verificação adicional em uma passagem subsequente. Irá gerar um erro SyntaxError se não puder corresponder aos lados esquerdo e direito. Para nossa linguagem de brinquedos, tudo se resume a escrever o seguinte:
statement: assignment_or_expr | if_statement assignment_or_expr: expr ['=' expr]
Os colchetes indicam uma parte opcional. E então, na próxima passagem do compilador (digamos, ao gerar o bytecode), verificamos se = ou não e, nesse caso, verificamos se o lado esquerdo corresponde à sintaxe de target .
Há um problema semelhante para argumentos de chamada de função. Gostaríamos de escrever algo assim (novamente, em uma versão simplificada da sintaxe do Python):
call: atom '(' arguments ')' arguments: arg (',' arg) * arg: posarg | kwarg posarg: expr kwarg: NAME '=' expr
Mas o algoritmo de análise, que levaria em consideração apenas o próximo token, não pode dizer ao analisador se NAME no início dos argumentos é o início de posarg (já que expr pode começar com NAME ) ou o início de kwarg . Novamente, o analisador Python atual resolve esse problema determinando:
arg: expr ['=' expr]
e, em seguida, conclui a alternativa em uma passagem subsequente do compilador. (Nós até cometemos um pequeno erro e analisamos foo((a) = 1) como foo(a = 1) . Isso foi corrigido apenas no Python 3.8)
Então, como um analisador PEG resolve esses problemas? Usando um buffer de backup infinito! Sua implementação típica usa o chamado analisador de packrat, que não apenas carrega o programa inteiro na memória antes de analisá-lo, mas também permite que o analisador seja revertido para um número arbitrário de tokens. Embora o termo PEG se refira principalmente à notação gramatical, os analisadores gerados a partir de gramáticas PEG são tipicamente analisadores com descendência recursiva e retorno ilimitado. O analisador de packrat torna o ego eficiente lembrando as regras que já foram analisadas para posições específicas.
Isso simplifica o algoritmo, mas é claro que há um preço: memória. Trinta anos atrás, eu tinha um bom motivo para usar o LL (1): a memória era cara. Ele (como outras tecnologias, como a LALR (1), famosa pela YACC), usa uma máquina de estado e uma pilha para construir com eficiência uma árvore de análise.
Felizmente, os computadores que executam o CPython possuem muito mais memória do que há 30 anos, e armazenar o arquivo inteiro na memória não é mais um problema. Por exemplo, o maior arquivo sem teste no stdlib que eu pude encontrar é _pydecimal.py , que leva cerca de 223kb. No mundo dos gigabytes, isso não é essencialmente nada, o que me fez dar uma olhada diferente nos analisadores.
Mas há mais uma coisa no analisador CPython atual que me incomoda. Compiladores são coisas complexas, e a implementação do CPython não é uma exceção. Embora o resultado do analisador pgen seja uma árvore de análise, ele não é usado diretamente como entrada para o gerador de bytecode: ele é primeiro convertido em uma árvore de sintaxe abstrata (AST) e somente então esse AST é compilado no bytecode. (Na verdade, é ainda mais complicado lá, mas por enquanto não entraremos em detalhes)
Por que não compilar imediatamente a partir de uma árvore de análise? Era exatamente assim, mas há cerca de 15 anos descobrimos que o compilador era muito complicado. Então, isolamos o AST e a fase de transformação do AST da árvore de análise separadamente. À medida que o Python evoluiu, o AST permaneceu mais estável que a análise, o que reduziu a probabilidade de erros no compilador.
O AST também é mais fácil de trabalhar com bibliotecas de terceiros que desejam testar o código Python. Pode ser obtido usando o popular módulo ast . Também permite criar nós a partir do zero e modificar os existentes, além de compilar peças no bytecode. Este último permitiu a criação de toda uma indústria de extensões de linguagem para Python. (A árvore de análise também é acessível aos usuários do Python através do módulo de análise, mas trabalhar com ela é muito mais difícil; portanto, não é tão popular)
Agora, quero combinar essas coisas e ver se podemos criar um novo analisador para o CPython, que usa o PEG e o packrat para criar o AST diretamente durante a análise. Assim, será possível omitir a geração da árvore intermediária de análise, o que pode economizar memória, mesmo com o uso de um buffer infinito para tokens. Ainda estou no processo de implementação, mas já tenho um protótipo que pode compilar um subconjunto do Python no AST na mesma velocidade do analisador atual do CPython. No entanto, ele usa mais memória e parece-me que expandir o subconjunto para o idioma completo desacelerará o analisador PEG. Mas até agora não pensei em nenhuma otimização, por isso continuarei trabalhando.
A última vantagem de mudar para o PEG é que ele oferece mais flexibilidade para a evolução adicional do idioma. No passado, dizia-se que as restrições LL (1) no pgen mantinham a gramática Python simples. Isso pode muito bem ser verdade, mas temos muitos outros processos para impedir o crescimento descontrolado de idiomas (principalmente o processo PEP, que é auxiliado por requisitos muito rigorosos de compatibilidade com versões anteriores e uma nova estrutura de gerenciamento). Então, eu não estou preocupado com isso.
Eu gostaria de falar muito mais sobre o PEG e minha implementação, mas ele estará nos próximos posts depois que eu limpar o código.
Licença para este artigo e código citado: CC BY-NC-SA 4.0