A gramática é ainda melhor se você pode adicionar (algumas) semânticas de acordo com as regras. Em particular, para o analisador Python que estou desenvolvendo, preciso retornar o nó AST de cada alternativa, pois quero manter a implementação atual do AST no CPython.
Conteúdo da série Ps Parser Python Muitas gramáticas usam uma convenção que permite adicionar ações às regras - geralmente um bloco de código dentro de {colchetes}. Mais precisamente, eles estão ligados a alternativas. O código neste bloco é escrito no mesmo idioma que o resto do compilador, por exemplo, em C, complementado por alguma capacidade de se referir a elementos na alternativa. Na pgen original Python, não adicionei essa funcionalidade, mas para um novo projeto eu gostaria de implementá-la.
Veja como fazemos isso para o gerador simplificado de analisador que estou desenvolvendo como parte desta série de postagens.
A sintaxe para ações é geralmente esta:
rule: item item item { action 1 } | item item { action 2 }
Como isso torna a gramática mais detalhada, os geradores de analisadores geralmente permitem regras de várias linhas, por exemplo:
rule: item item item { action 1 } | item item { action 2}
Isso torna o analisador um pouco mais complicado, mas é importante para facilitar a leitura, por isso vou apoiar esse registro.
A eterna questão é quando executar esse bloco. No Yacc / Bison, isso é feito imediatamente após o analisador reconhecer a regra, pois não há reversão na lista de tokens. Executar cada ação exatamente uma vez significa que pode haver efeitos colaterais globais (como atualizar a tabela de símbolos ou outra estrutura de dados do compilador).
Nos analisadores PEG com retorno ilimitado à lista de tokens, temos várias opções:
- Não execute nenhuma ação até que tudo tenha sido analisado. Não vou considerar isso, porque quero criar um AST certo durante a análise.
- Execute sempre que sua alternativa for reconhecida. É necessário que seu código seja idempotente (ou seja, tenha o mesmo efeito, não importa quantas vezes ele tenha sido executado). Isso significa que a ação pode ser executada, mas seu resultado pode ser descartado.
- Coloque em cache o resultado e execute a ação apenas pela primeira vez - quando sua alternativa for reconhecida nesta posição.
Eu escolhi a terceira opção - em qualquer caso, armazenamos em cache o resultado do método usando o algoritmo packrat, para que também possamos armazenar em cache os resultados.
Quanto ao conteúdo em {curlies}, por tradição, ele usa o código C com um contrato baseado em $ para se referir a elementos em uma alternativa reconhecida (por exemplo, $1 para se referir ao primeiro elemento) e a atribuição $$ para indicar o resultado da ação. Parece muito antiquado (tenho lembranças de usar a atribuição de funções no Algol-60 para indicar o valor de retorno), então tornarei mais Python: dentro dos colchetes, você precisará colocar uma expressão, cujo resultado será o resultado da ação e os links para os elementos serão nomes simples dando o texto do elemento. Como exemplo, aqui está uma calculadora simples que pode adicionar e subtrair números:
start: expr NEWLINE { expr } expr: expr '+' term { expr + term } | expr '-' term { expr - term } | term { term } term: NUMBER { float(number.string) }
Vamos executá-lo no exemplo de 100 + 50 - 38 - 70 . Ele calculará a resposta, porque ele reconhece as partes calculando ((100 + 50) - 38) - 70 , que obviamente é 42 .
Um pequeno detalhe: na ação do term number term variável contém um objeto TokenInfo ; portanto, você precisa usar o atributo .string para obter o token no formato de string.
O que fazemos quando uma alternativa tem várias ocorrências com o mesmo nome de regra? O gerador do analisador atribui a cada ocorrência um nome exclusivo, adicionando 1 , 2 etc. Para ocorrências subsequentes dentro da mesma alternativa. Por exemplo:
factor: atom '**' atom { atom ** atom1 } | atom { atom }
A implementação completa é bastante entediante, então eu não gostaria de insistir nela. Convido você a olhar para o meu repositório e brincar com o código :
python3.8 -m story5.driver story5/calc.txt -g story5.calc.CalcParser
A visualização agora permite que você se mova para frente e para trás usando as teclas de seta esquerda e direita!
Licença para este artigo e código citado: CC BY-NC-SA 4.0