O que é um analisador de árvore em ANTLR e eu estou forçado a escrever um?

StackOverflow https://stackoverflow.com/questions/697755

Pergunta

Eu estou escrevendo um lexer / analisador para um pequeno subconjunto de C no ANTLR que será executado em um ambiente Java. Eu sou novo para o mundo de gramáticas de língua e em muitos dos tutoriais ANTLR, eles criam um AST - Abstract árvore de sintaxe, eu sou forçado a criar um e por

?
Foi útil?

Solução 2

esta resposta à pergunta sobre jGuru escrito por Terence Parr, que criou ANTLR. Copiei esta explicação do site vinculado aqui :

Apenas simples chamados de sintaxe dirigido traduções, pode ser feito com ações dentro do analisador. Esses tipos de traduções só pode cuspir construções que são funções de informações já visto nesse ponto na análise. analisadores de árvores permitir que você ande uma forma intermediária e manipular essa árvore, transformando-o gradualmente ao longo de várias fases de tradução a uma forma final que pode ser facilmente impressa de volta como a nova tradução.

Imagine um problema de tradução simples, onde você pretende imprimir uma página html cujo título é "Existem n itens", onde n é o número de identificadores que você encontrou no fluxo de entrada. Os ids devem ser impressos após o título como este: 

<html>
<head>
<title>There are 3 items</title>
</head>
<body>
<ol>
<li>Dog</li>
<li>Cat</li>
<li>Velociraptor</li>
</body>
</html>

a partir da entrada 

Dog
Cat
Velociraptor

Assim, com ações simples em sua gramática como você pode calcular o título? Você não pode sem ler a entrada inteira. Ok, então agora nós sabemos que precisamos uma forma intermediária. O melhor é geralmente um AST eu encontrei uma vez que registra a estrutura de entrada. Neste caso, é apenas uma lista, mas ele demonstra o meu ponto.

Ok, agora você sabe que uma árvore é uma coisa boa para nada, mas traduções simples. Dado um AST, como você começa a saída dele? Imaginem árvores de expressão simples. Uma maneira é fazer com que os nós nas classes específicas árvore como PlusNode, IntegerNode e assim por diante. Então você acabou de pedir a cada nó para imprimir a si mesmo. Para entrada, 3 + 4 você teria árvore:

+ | 3-4

e classes 

class PlusNode extends CommonAST {
  public String toString() {
    AST left = getFirstChild();
    AST right = left.getNextSibling();
    return left + " + " + right;
  }
}

class IntNode extends CommonAST {
  public String toString() {
    return getText();
  }
}

Dada uma árvore de expressão, você pode traduzi-lo de volta ao texto com t.toString (). Então, o que há de errado com isso? Parece grande trabalho, certo? Parece funcionar bem neste caso porque é simples, mas argumentam que, mesmo para este exemplo simples, gramáticas de árvores são mais legíveis e são formalizados descrições de exatamente o que você codificados no PlusNode.toString (). 

expr returns [String r]
{
    String left=null, right=null;
}

: #("+" left=expr right=expr) {r=left + " + " + right;}
| i:INT                       {r=i.getText();}
;

Note que a classe específica ( "AST heterogêneo") se aproxima realmente codifica um analisador descendente recursivo completa para # (+ INT INT) à mão em toString (). Como pessoas gerador de analisador, isso deve fazer você se encolher. ;)

A principal fraqueza da abordagem AST heterogêneo é que ele não pode convenientemente informações de contexto de acesso. Em um analisador descendente recursivo, o seu contexto é de fácil acesso, pois pode ser passado como um parâmetro. Você também sabe exatamente qual regra pode invocar que outra regra (por exemplo, é a expressão de uma condição de tempo ou uma condição IF?), Olhando para a gramática. A classe PlusNode acima existe em um mundo individual, isolado, onde ele não tem idéia de quem vai chamá-lo de método toString (). Pior, o programador não pode dizer em que contexto ele será chamado por lê-lo.

Em resumo, acrescentando ações para o seu analisador de entrada funciona para traduções muito simples em que:

  1. a fim de construções de saída é a mesma que a ordem de entrada
  2. todas as construções podem ser gerados a partir de informações analisado até o ponto em que você precisa para cuspi-los

Além disso, você precisará de uma forma intermediária - a AST é a melhor forma normalmente. Usando uma gramática para descrever a estrutura da AST é análogo ao uso de uma gramática para analisar o texto de entrada. descrições formalizados em uma linguagem de alto nível de domínio específico como ANTLR são melhores do que codificadas manualmente analisadores. Ações dentro de uma gramática árvore tem contexto muito claro e pode informações convenientemente o acesso passou de rlues invocando. Traduções que manipulam a árvore para traduções multipass também são muito mais fácil usando uma gramática árvore.

Outras dicas

Criar uma AST com ANTLR é incorporado na gramática. Você não tem que fazer isso, mas é uma ferramenta muito boa para as necessidades mais complicado. Esta é uma tutorial na construção da árvore você pode usar.

Basicamente, com ANTLR quando a fonte está sendo analisado, você tem algumas opções. Você pode gerar o código ou um AST usando regras de reescrita em sua gramática. Um AST é basicamente uma representação em memória de sua fonte. De lá, há muita coisa que você pode fazer.

Há muito para ANTLR. Se você não tiver, eu recomendaria começar o livro .

Eu acho que a criação do AST é opcional. A Abstract Tree Sintaxe é útil para processamento posterior como análise semântica do programa analisado.

Só você pode decidir se você precisa criar um. Se o seu único objetivo é a validação sintática, então você não precisa gerar um. Em javacc (semelhante ao ANTLR) há um utilitário chamado JJTree que permite a geração da AST. Então eu imagino que isto é opcional em ANTLR também.

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top