Nesta semana, estamos tornando o gerador de analisador "independente", ou seja, ele gera seu próprio analisador.
Conteúdo da série Ps Parser Python Portanto, já temos um gerador de analisador, parte do qual é um analisador de gramática. Poderíamos chamá-lo de um meta-analisador. O meta-analisador funciona de maneira semelhante à gerada: GrammarParser herda do Parser e usa o mesmo mecanismo de mark() / reset() / hope() . No entanto, lá estava tudo escrito à mão. Mas isso está certo?
Ao projetar um compilador, é habitual que o compilador seja escrito na linguagem que compila. Lembro com amor que o compilador Pascal que usei quando aprendi a programar foi escrito no próprio Pascal, o GCC está escrito em C e o compilador Rust está escrito em Rust.
Como fazer isso? No início, implemente um compilador para um subconjunto ou versão anterior de um idioma em outro idioma. (Deixe-me lembrá-lo de que o compilador Pascal original foi escrito em FORTRAN!) Em seguida, o novo compilador é escrito no idioma de destino e compilado usando o compilador de auto-inicialização implementado no início. Assim que o novo compilador começa a funcionar bem o suficiente, o compilador de inicialização é removido e cada versão subsequente do idioma ou compilador é limitada ao que pode ser compilado usando a versão anterior do compilador.
Vamos fazer isso para o nosso meta-analisador. Escreveremos uma gramática para as gramáticas (meta-gramática) e, em seguida, geraremos um novo meta-analisador a partir disso. Felizmente, planejei essa mudança desde o início, por isso será bem simples. As ações que adicionamos no episódio anterior são um componente importante porque não precisamos alterar o gerador, portanto, precisamos criar uma estrutura de dados compatível.
Aqui está uma versão simplificada do metagrama sem ações:
start: rules ENDMARKER rules: rule rules | rule rule: NAME ":" alts NEWLINE alts: alt "|" alts | alt alt: items items: item items | item item: NAME | STRING
Vou mostrar como adicionar ação de baixo para cima. Lembre-se da Parte 3 que existem objetos Rule que possuem os alts name e alts . Inicialmente, alts era apenas uma lista de listas de linhas (uma lista externa para alternativas e uma lista interna para cada elemento da alternativa), mas para implementar as ações, mudei para que as alternativas fossem representadas por objetos Alt com items e atributos de action . Os elementos ainda são representados como cadeias simples. Para o item , obtemos:
item: NAME { name.string } | STRING { string.string }
Isso requer uma pequena explicação: quando o analisador processa o token, ele retorna um objeto TokenInfo que possui type , string e outros atributos. Não queremos que o gerador lide com objetos TokenInfo , portanto, as ações aqui extraem a string do token. Observe que, para todos os tokens maiúsculos, como NAME , o analisador gerado usa a versão da string (aqui name ) como o nome da variável.
A seguir, são items que devem retornar uma lista de cadeias de caracteres:
items: item items { [item] + items } | item { [item] }
Aqui eu uso regras de recursividade à direita, para que não dependamos do processamento da recursão à esquerda, adicionada na Parte 5. (Por que não? É sempre bom manter as coisas o mais simples possível, e essa gramática não se beneficiará muito de uma alteração na recursão à esquerda). item listado, mas recursivamente os items não estão, pois já é uma lista.
Regra alt para criar um objeto Alt :
alt: items { Alt(items) }
Vou omitir as ações para rules e start , como elas são definidas dessa maneira.
No entanto, existem duas questões em aberto. Primeiro, como encontro a definição das classes Rule e Alt ? Para fazer isso, precisamos adicionar várias instruções de import ao código gerado. A maneira mais simples seria passar a bandeira para o gerador, que diz “isso é uma meta-gramática”, e deixar o gerador inserir uma import adicional no início do programa gerado. Mas agora que temos as ações, muitos outros analisadores também quererão personalizar sua importação. Por que não ver se podemos implementar uma abordagem mais geral.
Existem muitas maneiras de implementá-lo. Um mecanismo simples e geral é adicionar uma seção de "definições de variáveis" na parte superior da gramática e permitir que o gerador use essas variáveis para controlar vários aspectos do código gerado. Decidi usar o símbolo @ para começar a definir a variável, seguida pelo nome da variável ( NAME ) e valor ( STRING ). Por exemplo, podemos colocar o seguinte bloco de código na parte superior da meta-gramática:
@subheader "from grammar import Rule, Alt"
O gerador do analisador imprimirá o valor da variável do subheader após a importação padrão, que é adicionada por padrão (por exemplo, para importar memoize ). Se você desejar vários elementos de import , poderá usar uma sequência com aspas triplas, por exemplo,
@subheader """ from token import OP from grammar import Rule, Alt """
É fácil adicionar isso à meta-gramática: quebraremos a regra de start do seguinte modo:
start: metas rules ENDMARKER | rules ENDMARKER metas: meta metas | meta meta: "@" NAME STRING NEWLINE
(Não me lembro por que o chamei de "meta", mas escolhi esse nome quando escrevi o código, e continuarei com ele. :-)
Nós devemos adicionar isso ao metaparser de auto-inicialização. Agora que a gramática não é apenas uma lista de regras, vamos adicionar um objeto de gramática com os atributos metas e rules . Podemos definir as seguintes ações:
start: metas rules ENDMARKER { Grammar(rules, metas) } | rules ENDMARKER { Grammar(rules, []) } metas: meta metas { [meta] + metas } | meta { [meta] } meta: "@" NAME STRING { (name.string, eval(string.string)) }
(Observe que meta retorna uma tupla; e também usa eval() para processar aspas de seqüência de caracteres.)
Não mencionei a implementação de ações nas regras do alt ! A razão é que eles saem um pouco bagunçados. Mas não faz sentido adiar ainda mais, então aqui:
alt: items action { Alt(items, action) } | items { Alt(items, None) } action: "{" stuffs "}" { stuffs } stuffs: stuff stuffs { stuff + " " + stuffs } | stuff { stuff } stuff: "{" stuffs "}" { "{" + stuffs + "}" } | NAME { name.string } | NUMBER { number.string } | STRING { string.string } | OP { None if op.string in ("{", "}") else op.string }
A sujeira na definição é causada pelo meu desejo de validar o código arbitrário do Python entre colchetes de ação, incluindo aninhados em mais um colchete. Para esse propósito, usamos um token OP especial que gera nosso tokenizer para toda pontuação reconhecida pelo Python (retornando um único token com o tipo OP para operadores com vários caracteres, como <= ou ** ). Os únicos outros tokens que podem ocorrer nas expressões Python são nomes, números e seqüências de caracteres. Assim, o código entre os colchetes externos da ação, ao que parece, pode ser expresso através de repetições de NAME | NUMBER | STRING | OP NAME | NUMBER | STRING | OP NAME | NUMBER | STRING | OP .
Infelizmente, isso não funcionará porque o OP também corresponde a chaves, e como o analisador PEG é sempre ganancioso, isso captura o suporte de fechamento e nunca veremos o final da ação. Portanto, adicionamos um pequeno ajuste, permitindo que a ação gere um erro de escolha alternativo, retornando Nenhum. Não sei se essa é uma ocorrência padrão em outros analisadores de PEG - eu vim com isso imediatamente quando tive que resolver o problema de reconhecer os parênteses de fechamento (mesmo sem pares aninhados). Isso parece funcionar bem e acho que se encaixa na filosofia geral da análise PEG. Isso pode ser considerado como uma forma especial de previsão (que discutirei abaixo).
Usando esse pequeno truque, podemos fazer a comparação no OP cair em uma chave. Então uma comparação de stuff e action será possível.
Com essas coisas, uma meta-gramática pode ser analisada por um metaparser de autoinicialização e o gerador pode transformá-lo em um novo meta-analisador que pode se analisar. E, o mais importante, o novo meta-analisador ainda pode analisar a mesma meta-gramática. Se compilarmos a meta-gramática com o novo meta-compilador, o resultado será o mesmo: isso prova que o meta-analisador gerado está funcionando corretamente.
Aqui está a meta gramática de ação completa. Ele pode se analisar, pois sabe combinar linhas longas:
@subheader """ from grammar import Grammar, Rule, Alt from token import OP """ start: metas rules ENDMARKER { Grammar(rules, metas) } | rules ENDMARKER { Grammar(rules, []) } metas: meta metas { [meta] + metas } | meta { [meta] } meta: "@" NAME STRING NEWLINE { (name.string, eval(string.string)) } rules: rule rules { [rule] + rules } | rule { [rule] } rule: NAME ":" alts NEWLINE { Rule(name.string, alts) } alts: alt "|" alts { [alt] + alts } | alt { [alt] } alt: items action { Alt(items, action) } | items { Alt(items, None) } items: item items { [item] + items } | item { [item] } item: NAME { name.string } | STRING { string.string } action: "{" stuffs "}" { stuffs } stuffs: stuff stuffs { stuff + " " + stuffs } | stuff { stuff } stuff: "{" stuffs "}" { "{" + stuffs + "}" } | NAME { name.string } | NUMBER { number.string } | STRING { string.string } | OP { None if op.string in ("{", "}") else op.string }
Agora que temos uma meta-gramática funcional, estamos quase prontos para fazer algumas melhorias.
Mas primeiro você precisa pensar um pouco: linhas vazias! Acontece que o módulo stdlib tokenize cria tokens adicionais para rastrear tokenize linha insignificantes (token NL ) e comentários (token COMMENT ). Em vez de incluí-los na gramática (tentei, não há muita diversão!), Existe um pedaço de código muito simples que podemos adicionar à nossa classe de tokenizer para filtrá-los. Aqui está o método peek_token aprimorado:
def peek_token(self): if self.pos == len(self.tokens): while True: token = next(self.tokengen) if token.type in (NL, COMMENT): continue break self.tokens.append(token) self.report() return self.tokens[self.pos]
Isso remove completamente os tokens NL e COMMENT , portanto, não precisamos mais nos preocupar com eles na gramática.
Finalmente, vamos fazer melhorias na meta-gramática! Eles serão puramente cosméticos: não gosto quando sou forçado a escrever todas as alternativas em uma linha. A meta gramática que mostrei acima, na verdade, não se analisa devido a essas coisas:
start: metas rules ENDMARKER { Grammar(rules, metas) } | rules ENDMARKER { Grammar(rules, []) }
Isso ocorre porque o tokenizer cria um token NEWLINE no final da primeira linha e, neste momento, o meta-analisador considerará que este é o fim da regra. Além disso, esta NEWLINE será seguida pelo token INDENT , porque a próxima linha é recuada. Até o início da próxima regra, um token DEDENT também estará presente.
Veja como lidar com isso. Para entender o comportamento do módulo tokenize , podemos observar a sequência de tokens gerados para blocos recuados, executando o módulo tokenize como um script e passando algum texto:
$ python -m tokenize foo bar baz dah dum ^D
Vemos que isso produz a seguinte sequência de tokens (simplifiquei um pouco a saída do código acima):
NAME 'foo' NAME 'bar' NEWLINE INDENT NAME 'baz' NEWLINE NAME 'dah' NEWLINE DEDENT NAME 'dum' NEWLINE
Assim, um grupo selecionado de strings é indicado pelos DEDENT e DEDENT . Agora podemos reescrever a rule meta-gramática para rule seguinte maneira:
rule: NAME ":" alts NEWLINE INDENT more_alts DEDENT { Rule(name.string, alts + more_alts) } | NAME ":" alts NEWLINE { Rule(name.string, alts) } | NAME ":" NEWLINE INDENT more_alts DEDENT { Rule(name.string, more_alts) } more_alts: "|" alts NEWLINE more_alts { alts + more_alts } | "|" alts NEWLINE { alts }
(Divido as ações em linhas para que elas sejam lidas normalmente em uma coluna estreita de texto. Isso é possível porque o tokenizador ignora quebras de linha dentro dos chavetas correspondentes.)
A vantagem disso é que nem precisamos alterar o gerador: a estrutura de dados criada por essa meta-gramática aprimorada é a mesma de antes. Preste atenção também à terceira opção de rule : isso nos permite escrever:
start: | metas rules ENDMARKER { Grammar(rules, metas) } | rules ENDMARKER { Grammar(rules, []) }
que alguns podem achar mais limpo que a versão que mostrei anteriormente. Ambos os formulários são fáceis de resolver, por isso não precisamos discutir sobre estilo.
No próximo post, mostrarei como implementei várias funções do PEG, como elementos opcionais, repetições e dicas de ferramentas. (Para ser sincero, planejei falar sobre eles neste artigo, mas ele já é muito grande. Por isso, vou dividi-lo em duas partes.)
Licença para este artigo e código citado: CC BY-NC-SA 4.0