Pratt parsing

[Vinícius dos Santos Oliveira]

Desde o ano passado tenho usado Pratt parsing extensivamente. É uma
técnica de parsing de 1973 largamente ignorada que tem uma abordagem
diferente ao problema (ex.: em vez de amarrar ações semânticas a
regras de produção que são não-terminais por definição, você amarra
aos terminais em si) que simplifica muito a criação de parsers pra
linguagens de programação reais do dia-a-dia (ou seja, linguagens
difíceis que fogem dos exemplos de bê-á-bá).

Tem pelo menos o Thiago Adams aqui no grupo que também está brincando
com compiladores, então fica aí minha dica pra quem estiver envolvido
em projetos similares: aprendam Pratt parsing.

Nas últimas semanas iniciei um novo blog pessoal e todos os posts até
então são sobre Pratt parsing. O mais recente:
https://vinipsmaker.github.io/blog/blog/pratt-parsing-is-a-black-box/

Tenho conseguido pars'ear minha linguagem cuja sintaxe é pesadamente
inspirada por Rust, então há no mínimo essa evidência do poder de
Pratt parsing. Porém não para aí, minha linguagem tem suporte a
macros... algo assim:

macro my_macro(@expr, ctx) { return $(1); }
fn foo() { my_macro! }

Que — na própria fase de parsing — expande para[1]:

fn foo() { 1 }

O mecanismo pode ocorrer em situações bem mais complicadas (macro no
nível global definida após uso, macros locais, ...), e a macro na
verdade é uma função. Ou seja, a macro precisa de um interpretador
para a linguagem sendo parse'ada para expandir o próprio código
fazendo uso da macro. Mesmo linguagens de investimento pesado como
Rust são permeadas de limitações (macros procedurais precisam ser
movidas para um crate externo) porque isso é difícil. Bom, eu fiz
sozinho, e é bem mais poderoso que Rust (as macros procedurais de Rust
só trabalham a nível de token-stream, enquanto Pratt macros permitem
intercalar livremente entre tokenizer e parser). Então sim, Pratt
parsing é poderoso pra caramba (não é só pra brinquedo, é pra competir
com grandes, e mesmo assim é extremamente barato de adotar mesmo se o
seu time seja só você mesmo).

Ah, e o interpretador que fiz pra minha linguagem pra poder
implementar macros... não é um tree-walk interpreter, mas um
Pratt-walk interpreter. Pratt de novo. Interpretar direto do código
sem passar para a AST é análogo a otimizações que visam minimizar
“wram-up times”. No caso de macros, acaba habilitando umas coisas
interessantes que eu jamais vi em outras linguagens, como macros
co-dependentes, mas isso vai ser assunto de discussão pra outro dia
porque ainda não tenho exemplos (nem implementação) pra demonstrar o
conceito.

Então, de novo, fica minha forte indicação para que aprendam Pratt.
Mesmo em C++ em uma implementação feita pra produção, o resultado
final ficou só em 14 linhas (vai ser ainda menor em linguagens de alto
nível): https://gitlab.com/emilua/asiobg/-/blob/942561418c0950648a2449478a080939721ed7da/src/syntax/parser.cpp#L312

[1] https://gitlab.com/emilua/asiobg/-/blob/942561418c0950648a2449478a080939721ed7da/test/macros.cpp#L182