Atualmente estou aprendendo sobre análise, mas estou um pouco confuso sobre como gerar um AST. Eu escrevi um analisador que verifica corretamente se uma expressão está de acordo com uma gramática (ela é silenciosa quando a expressão está em conformidade e gera uma exceção quando não está). Onde eu vou daqui para construir um AST? Eu encontrei muitas informações sobre como construir meu interpretador LL (1), mas muito pouco sobre como construir o AST.

Meu código atual (escrito em Ruby muito simples e incluindo um lexer e um parser) é encontrado aqui no github:https://gist.github.com/e9d4081b7d3409e30a57

Alguém pode explicar como eu vou do que eu tenho atualmente para um AST?

Alternativamente, se você não estiver familiarizado com Ruby, mas sabe C, você poderia me dizer como eu construir um AST para o código C noanálise de descendência recursiva artigo da wikipedia.

Por favor note, eu não quero usar um gerador de analisador como yacc ou antlr para fazer o trabalho para mim, eu quero fazer tudo do zero.

Obrigado!