Depois de reunir todas as partes do gerador de analisador PEG na postagem anterior, estou pronto para mostrar como implementar algumas outras coisas interessantes.
Conteúdo da série Ps Parser Python Vamos considerar os seguintes recursos do PEG:
- Itens nomeados:
NAME=item (o nome pode ser usado na ação) - Lookaheads:
&item (positivo) e !item (negativo) - Agrupando itens entre parênteses: (
item item ... ) - Itens opcionais:
[item item ...] e item? - Itens duplicados:
item* (zero ou mais) e item+ (um ou mais)
Argumentos nomeados
Vamos começar com elementos nomeados. Isso é conveniente quando temos vários deles em uma alternativa para a mesma regra, por exemplo:
expr: term '+' term
Podemos nos referir ao segundo term adicionando o número 1 ao nome da variável, para que na ação ocorra assim:
expr: term '+' term { term + term1 }
Mas nem todo mundo gosta e, pessoalmente, prefiro escrever algo assim:
expr: left=term '+' right=term { left + right }
Isso é facilmente suportado na meta-gramática, alterando a regra do item seguinte maneira:
item: | NAME = atom { NamedItem(name.string, atom) } | atom { atom } atom: | NAME { name.string } | STRING { string.string }
(Onde atom é apenas um item antigo)
Isso exige que adicionemos uma definição de classe ao NamedItem em NamedItem . É uma dessas classes de dados que mencionei anteriormente - também possui os atributos name e item .
Também precisamos fazer pequenas alterações no gerador de código, que deixarei como um exercício para o leitor (ou você pode olhar no meu repositório :-). O código gerado agora atribuirá o resultado da correspondência de cada elemento a uma variável com o nome especificado, e não com o nome obtido do nome da regra do elemento. Isso também funcionará para elementos que são tokens (no formato NAME ou em cadeias literais como ':=' ).
Lookahead
Seguido por lookahead. Você provavelmente já encontrou esse conceito em expressões regulares. No processo de visualização direta (lookahead), uma alternativa analisada pode ser imediatamente rejeitada ou aceita, sem mudar o ponteiro do tokenizer.
De fato, o lookahead pode ser usado como uma maneira mais elegante de eliminar a confusão com as exceções do analisador, sobre as quais escrevi em um artigo anterior. Em vez de permitir que as ações rejeitem uma alternativa já aceita retornando None, podemos adicionar uma instrução antes do OP para excluir "}" . A regra antiga era assim:
| OP { None if op.string in ("{", "}") else op.string }
A nova versão fica assim:
| !"}" OP { op.string }
Isso transfere o processamento de colchete da ação para a gramática, onde ele pertence. Não precisamos marcar "{" , pois corresponde a uma alternativa anterior (na verdade, isso também é verdade para a versão antiga, mas eu esqueci :-).
Adicionamos gramática para lookaheads à regra do item seguinte maneira:
item: | NAME = atom { NamedItem(name.string, atom) } | atom { atom } | "&" atom { Lookahead(atom, True) } | "!" atom { Lookahead(atom, False) }
Mais uma vez, precisamos adicionar a Lookahead de dados Lookahead a Lookahead (e importá-la para @subheader !) E modificar um pouco o gerador adicionando o seguinte método auxiliar:
def lookahead(self, positive, func, *args): mark = self.mark() ok = func(*args) is not None self.reset(mark) return ok == positive
No nosso caso, o código gerado para essa alternativa se parece com o seguinte:
if (True and self.lookahead(False, self.expect, "}") and (op := self.expect(OP)) ): return op . string
Como você pode ver no fragmento gramatical acima, o lookahead não pode obter nomes próprios. Isso é fácil de corrigir, mas ainda não tenho idéia de quão útil seria. Além disso, para previsões negativas, o valor será sempre None .
Agrupamento entre parênteses
Agora vamos implementar grupos com colchetes. O melhor lugar para adicioná-los ao metagrama é a regra do atom :
atom: | NAME { name.string } | STRING { string.string } | "(" alts ")" { self.synthetic_rule(alts) }
As duas primeiras alternativas não foram alteradas. A ação para a nova alternativa usa um hack (cuja implementação permanece inexplicável), que permite ao meta-analisador adicionar novas regras à gramática em tempo real. Essa função auxiliar (definida no meta-analisador) retorna o nome do novo objeto de regra. Ele consistirá em um prefixo fixo seguido por um número, o que o torna único, por exemplo, _synthetic_rule_1 .
Você pode perguntar o que acontece se a regra sintética for eventualmente descartada. Não sei como evitar isso, mas não deve haver problemas - na pior das hipóteses, haverá uma regra não utilizada na gramática. E, graças à memorização, a mesma ação nunca será executada duas vezes para a mesma posição de entrada, portanto, isso também não é um problema (mas, mesmo que fosse esse o caso, no pior caso, teríamos uma regra morta).
Usar alts entre colchetes significa que podemos definir uma barra vertical como um delimitador dentro de um grupo. Por exemplo, que nossa nova solução de ação não corresponderia acidentalmente { , poderíamos mudar a negação para isso:
| !("{" | "}") OP { op.string }
Além disso, os grupos também podem conter ações! Isso não ajudaria a resolver o problema com as ações, mas em outras situações pode muito bem ser útil. E como, de qualquer forma, geramos uma regra sintética, ela não requer nenhum trabalho adicional para implementá-la (exceto a implementação de synthetic_rule :-).
Itens opcionais
Como na pgen antiga, uso colchetes para indicar um grupo de tokens opcionais. É aqui que acaba sendo útil. Por exemplo, uma regra gramatical que descreve um loop for Python pode usá-la para indicar que uma extensão de else pode existir. E, novamente, podemos expandir a gramática para atom seguinte maneira:
atom: | NAME { name.string } | STRING { string.string } | "(" alts ")" { self.synthetic_rule(alts) } | "[" alts "]" { Maybe(self.synthetic_rule(alts)) }
Aqui Maybe há outra classe de dados, com um único atributo de item . Modificamos o gerador de código para que o resultado da função sintética não falhe se esse valor for None . Para fazer isso, você pode adicionar or True na implementação. Por exemplo, para [term] :
if (True and ((term := self.term()) or True) ): return term
Itens duplicados
Mudar para repetição é outra função PEG útil (a notação é emprestada de expressões regulares e também é usada na pgen). Existem duas formas: adicionar * a um átomo significa "zero ou mais repetições", enquanto adicionar + significa "uma ou mais repetições". Por outras razões, tive que reescrever as regras gramaticais para item e atom , adicionando uma regra intermediária, que chamei de molecule :
item: | NAME '=' molecule { NamedItem(name.string, molecule) } | "&" atom { Lookahead(atom) } | "!" atom { Lookahead(atom, False) } | molecule { molecule } molecule: | atom "?" { Maybe(atom) } | atom "*" { Loop(atom, False) } | atom "+" { Loop(atom, True) } | atom { atom } | "[" alts "]" { Maybe(self.synthetic_rule(alts)) } atom: | NAME { name.string } | STRING {string.string } | "(" alts ")" { self.synthetic_rule(alts) }
Observe que isso introduz uma sintaxe alternativa para elementos opcionais ( atom? ). Não requer esforços adicionais de implementação, pois essa é apenas outra maneira de criar um nó Maybe .
A refatoração dessas regras foi necessária porque não quero validar determinadas situações:
- repetições opcionais (já que isso é apenas uma repetição de zero ou mais);
- repetições (interno capturaria todas as correspondências, pois o PEG sempre usa um algoritmo ganancioso)
- valores opcionais repetidos (que interromperiam a análise se o elemento opcional não corresponder).
No entanto, essa ainda não é uma solução ideal, pois você pode escrever algo como (foo?)* . Será necessário adicionar uma verificação a essa situação no gerador do analisador, mas farei isso fora do artigo.
A classe de dados Loop tem dois atributos: item e nonempty . O código gerado usará o método auxiliar do analisador loop() . É muito semelhante ao método lookahead() mostrado anteriormente:
def loop(self, nonempty, func, *args): mark = self.mark() nodes = [] while node := func(*args) is not None: nodes.append(node) if len(nodes) >= nonempty: return nodes self.reset(mark) return None
Se nonempty for False (no sentido em que a gramática era * ), isso não levará a um erro. Nenhuma entrada será encontrada e uma lista vazia será retornada. Para que isso aconteça, implementamos o gerador do analisador para que is not None adicionado is not None . Uma verificação mais suave de uma postagem anterior retornaria False no caso de uma lista vazia.
Isso é tudo por hoje! Eu ia discutir o operador "cut" ( ~ ) presente no TatSu, mas até agora não tive a chance de encontrá-lo. Ainda não estou pronto para discuti-lo - a documentação do TatSu fornece apenas um exemplo simples que me interessa um pouco. Eu não o encontrei em outros geradores de analisadores PEG; talvez esse recurso seja apenas o TatSu. Talvez um dia eu conte sobre ele. (Enquanto isso, eu implementei para o caso, você nunca sabe. :-)
Acho que o próximo artigo será sobre minha experiência na escrita de uma gramática PEG que pode analisar a gramática Python. Vou contar como ocorreu o sprint dos desenvolvedores do kernel do Python, que foi realizado em Londres nesta semana com suporte logístico da Bloomberg e suporte financeiro do PSF e de algumas outras empresas (por exemplo, o Dropbox me pagou o hotel e o voo). Agradecimentos especiais a Emily Morhouse e Pablo Galindo Salgado, que ajudaram muito na implementação das ferramentas e testes. Em seguida, escreveremos testes de desempenho e adicionaremos ações a esta gramática para que ele possa criar árvores AST que possam ser compiladas pelo compilador de código de bytes CPython. Há muito mais coisas interessantes pela frente!
Licença para este artigo e código citado: CC BY-NC-SA 4.0