Agora que esbocei o básico de um analisador proprietário, passemos a gerar seus métodos a partir da gramática, como prometi. Também mostrarei como implementar um analisador de @memoize usando o decorador @memoize .
Conteúdo da série Ps Parser Python Na última vez, vimos alguns métodos de análise. Com algumas restrições que removeremos um pouco mais tarde, elas são fáceis de gerar automaticamente a partir da gramática.
Precisamos de duas coisas: algo que leia a gramática e construa uma estrutura de dados apropriada; e algo que pega essa estrutura de dados e gera um analisador. Também precisamos de outros métodos auxiliares, mas eles não são interessantes, então eu os omitirei.
Então, estamos criando um compilador simples. Vou simplificar um pouco a notação gramatical na medida em que só temos regras e alternativas; isso é suficiente para a gramática de brinquedos que usei nas partes anteriores:
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
Usando a notação completa, podemos descrever a gramática como:
grammar: rule+ ENDMARKER rule: NAME ':' alternative ('|' alternative)* NEWLINE alternative: item+ item: NAME | STRING
Esta é a nossa primeira meta-gramática (gramática para gramáticas) e nosso gerador de analisador será um meta-compilador (um compilador é um programa que traduz programas de um idioma para outro; um meta-compilador é um compilador em que a entrada é uma gramática e a saída é um analisador)
Uma maneira fácil de descrever uma meta-gramática é usar apenas os tipos de dados internos: a parte certa da regra é uma lista de listas de elementos, cada um dos quais pode ser apenas uma sequência. A propósito, podemos separar NAME e STRING verificando se o primeiro caractere é entre aspas.
Para regras, eu uso a classe Rule simples, e a gramática inteira é uma lista desses objetos. Aqui está a classe Rule , excluindo __repr__ e __eq__ :
class Rule: def __init__(self, name, alts): self.name = name self.alts = alts
E aqui está a classe GrammarParser que a usa:
class GrammarParser(Parser): def grammar(self): pos = self.mark() if rule := self.rule(): rules = [rule] while rule := self.rule(): rules.append(rule) if self.expect(ENDMARKER): return rules
Preste atenção ao uso do ENDMARKER . Lá, garanto que nada resta após a última regra (e isso pode acontecer se houver um erro de digitação na gramática). Também apontei para o local em que o método grammar() retorna uma lista de regras. Todo o resto é muito parecido com a classe ToyParser do último artigo, por isso não vou insistir nisso. Observe que item() retorna uma string, alternative() retorna uma lista de strings e a variável é alts dentro de rule() coleta uma lista de strings. Em seguida, o método rule() combina o nome da regra (string) e o converte em um objeto Rule .
Se aplicarmos esse algoritmo à nossa gramática de brinquedos, o método grammar() retornará a seguinte lista de regras:
[ Rule('statement', [['assignment'], ['expr'], ['if_statement']]), Rule('expr', [['term', "'+'", 'expr'], ['term', "'-'", 'term'], ['term']]), Rule('term', [['atom', "'*'", 'term'], ['atom', "'/'", 'atom'], ['atom']]), Rule('atom', [['NAME'], ['NUMBER'], ["'('", 'expr', "')'"]]), Rule('assignment', [['target', "'='", 'expr']]), Rule('target', [['NAME']]), Rule('if_statement', [["'if'", 'expr', "':'", 'statement']]), ]
Agora que temos a parte de análise do nosso meta compilador, vamos criar um gerador de código. Juntos, eles formam um meta compilador elementar:
def generate_parser_class(rules): print(f"class ToyParser(Parser):") for rule in rules: print() print(f" @memoize") print(f" def {rule.name}(self):") print(f" pos = self.mark()") for alt in rule.alts: items = [] print(f" if (True") for item in alt: if item[0] in ('"', "'"): print(f" and self.expect({item})") else: var = item.lower() if var in items: var += str(len(items)) items.append(var) if item.isupper(): print(" " + f"and ({var} := self.expect({item}))") else: print(f" " + f"and ({var} := self.{item}())") print(f" ):") print(f" " + f"return Node({rule.name!r}, [{', '.join(items)}])") print(f" self.reset(pos)") print(f" return None")
Esse código é muito feio, mas funciona (mais ou menos), e no futuro eu o reescreverei de qualquer maneira.
Algumas linhas dentro do for alt in rule.alts podem exigir explicação: para cada elemento na alternativa, escolhemos uma das 3 opções:
- se o elemento for uma string literal, por exemplo
'+' , geramos self.expect('+') - se o elemento estiver totalmente em maiúsculas, por exemplo,
NAME , geraremos (name := self.expect(NAME)) - caso contrário, por exemplo, se for
expr , geramos (expr := self.expr())
Se houver vários elementos com o mesmo nome em uma variante (por exemplo, term '-' term ), adicionamos um dígito ao segundo. Há também um pequeno erro aqui que eu corrigirei no próximo episódio.
Aqui está um pequeno resultado de seu trabalho (toda a classe seria muito chata). Não se preocupe com o código redundante if (True and ... ) necessário para que cada condição gerada possa começar com and . O compilador de bytes Python otimiza isso.
class ToyParser(Parser): @memoize def statement(self): pos = self.mark() if (True and (assignment := self.assignment()) ): return Node('statement', [assignment]) self.reset(pos) if (True and (expr := self.expr()) ): return Node('statement', [expr]) self.reset(pos) if (True and (if_statement := self.if_statement()) ): return Node('statement', [if_statement]) self.reset(pos) return None ...
Preste atenção ao decorador @memoize : eu a apresentei para passar para outro tópico: usando a memorização para tornar o analisador gerado rápido o suficiente.
Aqui está a função memoize() que implementa este decorador:
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
Como em outros decoradores, ele contém uma função aninhada que substitui (ou envolve) uma função decorada, por exemplo, o método statement() da classe ToyParser . Como a função que está sendo quebrada é um método, o wrapper também é realmente um método: seu primeiro argumento é chamado de self e refere-se à instância ToyParser para a qual o método decorado é chamado.
O wrapper armazena em cache o resultado da chamada do método para cada posição de entrada - é por isso que é chamado de analisador de pacotes! [aprox. trans. packrat é um "ladrão", mas esse termo não é traduzido em fontes no idioma russo.] Cache é um dicionário de dicionários, armazenado em uma instância do Parser . A chave do dicionário externo é a posição no fluxo de dados de entrada; Também adicionei self.memos = {} ao Parser .__ init__() para inicializá-lo. Dicionários internos são adicionados conforme necessário; suas chaves consistem em um método e seus argumentos. (Não há argumentos no design atual, mas podemos memorizar a função expect() que possui uma, o que é bastante trivial)
O resultado do método do analisador é apresentado na forma de uma tupla, porque existem realmente dois valores: o resultado em si (para nossos métodos gerados, este é o Node para a regra de correspondência) e um ponteiro para a posição atual no fluxo de entrada, que obtemos de self.mark() . Assim, armazenamos em cache o valor de retorno ( res ) e a nova posição ( endpos ) no dicionário interno com valores memorizados. Nas chamadas subseqüentes ao mesmo método de análise com os mesmos argumentos na mesma posição de entrada, nós as retiraremos do cache. Para fazer isso, basta mover o ponteiro para a posição de entrada usando self.reset() e procure no cache.
Também é importante armazenar em cache resultados negativos - na verdade, a maioria das chamadas será negativa. Nesse caso, o valor de retorno é None e a posição de entrada não muda. Você pode adicionar assert para verificar isso.
Nota No Python, é habitual implementar um cache em uma variável local na função memoize() . No nosso caso, isso não funcionará: como descobri no final da depuração, cada instância do Parser deve ter seu próprio cache. No entanto, você pode se livrar de dicionários aninhados usando ( pos , func , args ) como chave.
Na próxima semana, prepararei código e rastreios para mostrar como tudo isso é realmente montado e executado ao analisar um programa de exemplo. Ainda estou em busca de uma maneira melhor de visualizar a colaboração do buffer de tokenização, analisador e cache. Talvez eu consiga criar um gif animado em ASCII em vez de apenas exibir as listagens de rastreamento como texto.
Licença para este artigo e código citado: CC BY-NC-SA 4.0