Inspirado apenas por uma compreensão parcial do PEG, decidi tentar implementá-lo. O resultado pode não ser o melhor entre os analisadores de PEG de uso geral - já existem muitos deles (por exemplo, o TatSu é escrito em Python e gera código Python) - mas essa é uma boa maneira de entender o PEG. No futuro, quero substituí-lo pela implementação atual do analisador no CPython.
Conteúdo da série Ps Parser Python Nesta seção, lancei as bases para entender o trabalho do analisador, usando um exemplo de uma implementação auto-escrita simples da gramática de brinquedos de um artigo anterior.
(A propósito, como experimento, não coloco links no meu texto. Se você não entende alguma coisa, basta pesquisar no Google. :-)
Normalmente, um PEG usa um analisador de descida recursiva com um buffer ilimitado para retornar. Aqui está uma gramática de brinquedo de um artigo anterior:
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
O analisador super-abstrato da descida recursiva para esse idioma definirá sua função para cada regra na qual as alternativas serão entendidas. Por exemplo, para statement , teríamos esta função:
def statement(): if assignment(): return True if expr(): return True if if_statement(): return True return False
Obviamente, este é um exemplo simplista demais: omite detalhes importantes, por exemplo, o que é fornecido à entrada dessa função e qual será o resultado de sua execução.
Vamos começar com os argumentos. Os analisadores clássicos usam um tokenizador separado, que divide a entrada (arquivo ou linha de texto) em uma série de tokens, como palavras-chave, identificadores (nomes), números e operadores. Os analisadores PEG (como outros analisadores modernos como o ANTLR) geralmente combinam tokenização e análise, mas, para o meu projeto, decidi deixar um tokenizador separado.
A tokenização de Python é bastante complicada, por isso não quero implementá-la nas regras do PEG. Por exemplo, você deve acompanhar o recuo (isso requer uma pilha dentro do tokenizer); O processamento de novas linhas em Python também é interessante (elas são significativas, exceto aquelas incluídas entre colchetes). Muitos tipos de cadeias também causam alguma complexidade. Em resumo, não tenho queixas sobre o tokenizer Python existente, então quero deixá-lo como está. A propósito, o CPython possui dois tokenizadores: o interno, que é usado pelo analisador, é escrito em C, e a biblioteca padrão, que é uma cópia exata implementada em Python puro. Isso será útil no meu projeto.
Um tokenizer clássico geralmente possui uma interface simples que consiste em uma única função get_token() . Cada vez, ele retorna o próximo token na sequência de entrada, analisando um grupo de caracteres. O módulo de tokenize do CPython não é exceção: sua API principal é um gerador que emite um token de cada vez. Cada token é um objeto do tipo TypeInfo , que possui vários campos, o mais importante dos quais é o tipo de token (por exemplo, NAME , NUMBER , STRING ) e seu valor de string é o conjunto de caracteres em que consiste (por exemplo, abc , 42 ou "Hello, world" ). Existem também campos adicionais. Por exemplo, para o índice de token no fluxo de entrada, que é útil em mensagens de erro.
Um tipo especial de token é ENDMARKER , que indica que o final do arquivo de entrada foi atingido. O gerador cairá se você o ignorar e tentar obter o próximo token.
Mas eu estava distraído. Como realizamos retornos ilimitados? A reversão da lista de tokens exige que você se lembre da posição no código-fonte e reanalise a partir desse ponto. A API do tokenizer não nos permite mover o ponteiro, mas você pode capturar o fluxo de tokens em uma matriz e reproduzi-lo a partir daí, o que faremos. Você também pode repetir isso com itertools.tee() , mas isso provavelmente é menos eficaz em nosso caso, se você observar os avisos na documentação.
Suponho que você possa simplesmente tokenizar todas as entradas da lista primeiro e depois usá-las como entradas para o analisador. Mas se houver um token inválido no final do arquivo (por exemplo, uma linha com uma cotação de fechamento ausente) e também houver um erro de sintaxe no arquivo, você receberá uma mensagem de erro do tokenizer. Acredito que isso seja ruim para o usuário, pois um erro de sintaxe pode ser a principal causa de uma linha inválida. Portanto, tenho requisitos ligeiramente diferentes para o tokenizer, em particular, ele deve ser implementado como uma lista lenta.
A API principal é muito simples. O objeto Tokenizer encapsula uma matriz de tokens e posição nessa matriz. Ele tem três métodos principais:
get_token() retorna o próximo token, movendo o ponteiro (ou lê o próximo token da fonte, se estivermos no final do buffer do token);mark() retorna a posição atual no buffer;reset(pos) define a posição no buffer (o argumento deve ser obtido da mark() ).
Adicionamos uma função auxiliar peek_token() , que retorna o próximo token sem alterar a posição no buffer.
É assim que a base da classe Tokenizer parece:
class Tokenizer: def __init__(self, tokengen): """Call with tokenize.generate_tokens(...).""" self.tokengen = tokengen self.tokens = [] self.pos = 0 def mark(self): return self.pos def reset(self, pos): self.pos = pos def get_token(self): token = self.peek_token() self.pos += 1 return token def peek_token(self): if self.pos == len(self.tokens): self.tokens.append(next(self.tokengen)) return self.tokens[self.pos]
Aqui, algo é omitido por simplicidade (por exemplo, os nomes dos métodos e variáveis da instância devem começar com um sublinhado), mas esse é apenas um protótipo da API do Tokenizer .
O analisador também deve se tornar uma classe para que statement() , expr() etc. poderia ser implementado como métodos. O tokenizer se tornará uma variável de instância, mas não quero que os métodos do analisador chame diretamente get_token() . Em vez disso, implementamos o método wait() na classe Parser , que pode ser bem-sucedido ou falhar, assim como o método do analisador. O argumento para a função wait() é o token esperado: uma sequência de caracteres (por exemplo, + ) ou um tipo de token (por exemplo, NAME ). O tipo do valor de retorno ainda não é importante, voltarei a ele depois de discutir o resultado do trabalho do analisador.
Deixe que as funções da regra gramatical retornem apenas True ou False . Isso é bom para a ciência da computação teórica (aí o analisador responde à pergunta " Essa é uma string válida na linguagem?"), Mas não para nós. Nossa tarefa é criar um AST. Então, vamos reescrever esse código para que cada método de análise retorne um objeto Node em caso de sucesso ou None em caso de falha.
A classe Node pode ser muito simples:
class Node: def __init__(self, type, children): self.type = type self.children = children
Aqui, type determina o tipo do nó AST (por exemplo, add ou if ) e os descendentes são uma lista de nós e tokens (instâncias TokenInfo ). Isso é suficiente para o compilador gerar código ou executar outras análises, como verificação de tipo estático ou fiapos. Embora, no futuro, eu gostaria de mudar a forma como a AST é apresentada.
Para se encaixar nesse esquema, o método expect() deve retornar um objeto TokenInfo em caso de sucesso e None em caso de falha. Para poder reverter para tokens anteriores, envolvo as chamadas para os métodos mark() e reset() do tokenizer (aqui a API não muda). Aqui está o que aconteceu:
class Parser: def __init__(self, tokenizer): self.tokenizer = tokenizer def mark(self): return self.tokenizer.mark() def reset(self, pos): self.tokenizer.reset(pos) def expect(self, arg): token = self.tokenizer.peek_token() if token.type == arg or token.string == arg: return self.tokenizer.get_token() return None
Mais uma vez: omiti alguns detalhes, mas isso já está funcionando.
Agora, preciso introduzir um requisito importante para os métodos do analisador. Todos devem retornar o Node , colocando o tokenizer após o último token da regra gramatical que reconheceram; None e deixe a posição do tokenizer inalterada. Se o método do analisador ler vários tokens e depois cair, deverá restaurar a posição do tokenizer. Para isso, mark() e reset() são destinados. Observe que expect() também obedece a esta regra.
Então, aqui está um esboço do analisador real. Aqui eu uso o operador morsa do Python 3.8 ( := ):
class ToyParser(Parser): def statement(self): if a := self.assignment(): return a if e := self.expr(): return e if i := self.if_statement(): return i return None def expr(self): if t := self.term(): pos = self.mark() if op := self.expect("+"): if e := self.expr(): return Node("add", [t, e]) self.reset(pos) if op := self.expect("-"): if e := self.expr(): return Node("sub", [t, e]) self.reset(pos) return t return None def term(self):
Omiti a implementação de alguns métodos para que o leitor tivesse a oportunidade de praticar a si próprio. Isso é realmente melhor do que apenas ler sobre como esse analisador é implementado. No final, geraremos esse código automaticamente a partir da gramática. Constantes como NAME e NUMBER são importadas do módulo de token da biblioteca padrão. Isso nos vincula ainda mais à implementação atual do tokenizer Python. Se queremos criar um analisador PEG generalizado, precisamos encontrar maneiras de evitar isso.
Observe também que estou um pouco enganado. O método expr deve ser recursivo à esquerda, mas tornei o analisador recursivo à direita, porque o analisador de descida recursiva não funciona com regras gramaticais recursivas à esquerda. Isso pode ser corrigido, mas ainda é o tema de algumas pesquisas científicas, e eu gostaria de falar sobre isso separadamente. Lembre-se de que essa implementação não é 100% consistente com nossa gramática simplificada.
As principais coisas que eu quero que você entenda até agora:
- As regras gramaticais correspondem aos métodos do analisador e, quando uma regra gramatical se refere a outra, chama um método de outra regra.
- Quando uma sequência de tokens pode ser interpretada de maneira diferente, os métodos correspondentes do analisador são chamados um após o outro.
- Quando uma regra gramatical se refere a um token, o método chama a função
expect() . - Se o analisador reconhecer com êxito sua regra gramatical na posição atual, ele retornará o nó AST correspondente; se ele não conseguir reconhecer sua regra gramatical, ele retornará
None . - Os métodos do analisador devem redefinir explicitamente a posição do tokenizer quando parar de analisar depois de usar um ou mais tokens (direta ou indiretamente, invocar outro método de análise bem-sucedido). Isso é aplicável não apenas quando uma das opções é rejeitada para prosseguir para a próxima, mas também quando a análise é rejeitada como um todo.
Se todos os métodos de análise obedecerem a essas regras, não será necessário agrupar cada uma nas chamadas mark() e reset() . Isso pode ser provado por indução.
Além disso, é tentador tentar se livrar de chamadas explícitas para mark() e reset() usando o gerenciador de contexto e a instrução with , mas não funcionará: você não deve chamar reset() se tiver êxito! Como uma correção adicional, você pode tentar usar exceções para o fluxo de controle para que o gerenciador de contexto saiba se o tokenizer deve ser redefinido (acho que o TatSu está fazendo algo semelhante). Por exemplo, algo como isto:
def statement(self): with self.alt(): return self.assignment() with self.alt(): return self.expr() with self.alt(): return self.if_statement() raise ParsingFailure
Em particular, uma pequena escada de if em atom() para reconhecer uma expressão entre colchetes pode ser escrita como:
with self.alt(): self.expect("(") e = self.expr() self.expect(")") return e
Mas me parece muito "mágico" - ao ler esse código, você deve se lembrar de que cada método de análise (incluindo wait() ) pode gerar uma exceção. E que essa exceção é capturada e ignorada pelo gerenciador de contexto na instrução with . Isso é bastante incomum, embora realizável (retornando True de __exit__ ). No entanto, meu objetivo final é gerar código em C, não em Python, e em C não há nenhuma instrução with para alterar o fluxo de controle.
De qualquer forma, aqui estão alguns tópicos para as seguintes partes:
- geração de métodos analisadores a partir da gramática;
- análise de pacotes (memorização);
- Recursos de EBNF como
(x | y) , [xy ...] , x* , x+ ; - rastreamento (para depurar um analisador ou gramática);
- Recursos de PEG como lookahead e cut;
- como lidar com regras recursivas à esquerda;
- Geração de código C
Licença para este artigo e código citado: CC BY-NC-SA 4.0