Como transformar um fluxo de token em uma árvore de análise [fechado]

Question

Eu tenho um lexer construído, que flui para fora fichas de na entrada, mas não tenho certeza como construir o próximo passo no processo - a árvore de análise. Alguém tem alguma bons recursos ou exemplos sobre como fazer isso?

Answer 1

Eu realmente recomendo http://www.antlr.org/ e, claro, o Dragão clássico compiladores livro.

Para uma linguagem fácil como JavaScript, não é difícil de rolo mão de um analisador descendente recursivo, mas é quase sempre mais fácil de usar uma ferramenta como yacc ou antlr.

Eu acho que a etapa de volta para o básico de sua pergunta, você realmente quer estudar-se sobre sintaxe gramática BNF-esque e escolher uma sintaxe para o seu alvo. Se você tem isso, a árvore de análise deve tipo de cair, sendo a manifestação 'exemplo' de que a gramática.

Além disso, não tentar transformar a criação de sua árvore de análise em sua solução final (como o código de geração, ou o que-não). Pode parecer do-capazes e mais pesca; mas, invariavelmente, vai chegar um momento em que você realmente deseja que você teve que árvore de análise 'como é', que ao redor.

Answer 2

Você deve investigar ferramentas gerador de analisador para sua plataforma. Um gerador de analisador permite especificar uma gramática livre de contexto para o seu idioma. A linguagem consiste de uma série de regras que "reduzir" uma série de símbolos em um novo símbolo. Normalmente você pode também especificar precedência e associatividade de regras diferentes para eliminar a ambiguidade na língua. Por exemplo, uma linguagem de calculadora muito simples poderia ser algo como isto:

%left PLUS, MINUS           # low precedence, evaluated left-to-right
%left TIMES, DIV            # high precedence, left-to-right

expr ::= INT
| expr PLUS expr
| expr MINUS expr
| expr TIMES expr
| expr DIV expr
| LEFT_PAREN expr RIGHT_PAREN

Normalmente, você pode associar um pouco de código com cada regra para a construção de um novo valor (neste caso uma expressão) dos outros símbolos em que regra. O gerador de analisador terá na gramática e produzir código na sua linguagem que traduz um fluxo de token para uma árvore de análise.

A maioria dos geradores de analisador são específicas da linguagem. ANTLR é bem conhecida e suporta C, C ++, Objective C, Java, e o Python. Ouvi dizer que é difícil de usar embora. Eu tenho bisonte utilizado para C / C ++, CUP para Java, e ocamlyacc para OCaml, e eles estão todos muito bom. Se você já está usando um gerador de lexer, você deve procurar um gerador de analisador que é especificamente compatível com ele.

Answer 3

Eu acredito que um comum uma abordagem é usar um State Machine Finite . Por exemplo, se você ler um operando você entrar em um estado onde você próxima esperam um operador, e você costuma usar o operador como o nó de raiz para os operandos e assim por diante.

Answer 4

Como descrito acima por Marcos Marin, uma máquina de estado que usa suas regras de linguagem em BNF para analisar sua lista de tokens irá fazer o truque se você quiser fazê-lo sozinho. Só que, como disse no comentário acima por Paul Hollingsworth, a maneira mais fácil é usar um Pushdown-Automaton que tem uma pilha de memória FiFo simples. Cada classe de token possui uma próxima esperado sinal em sua gramática, que também é representada em seu estado-máquina. A pilha é usada para "lembrar" o que era a classe de token anterior, para reduzir os estados requeridos (poderia ser feito sem pilha, mas você precisaria de um novo estado para cada classe e subclasse de divisão na árvore de gramática). O estado de aceitação (s) seria (em línguas naturais ea maioria das linguagens de programação também) o estado inicial, e talvez algum outro estado em casos particulares.

Antlr seria a minha sugestão, se você quiser usar uma ferramenta (muuuito mais rápido e menos extenso). Boa sorte!