Qu'est-ce qu'un analyseur d'arbre dans ANTLR et je suis obligé d'écrire un?

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

Question

J'écris un lexer / parser pour un petit sous-ensemble de C dans ANTLR qui sera exécuté dans un environnement Java. Je suis nouveau dans le monde des grammaires de langue et dans la plupart des tutoriels ANTLR, ils créent un AST - arbre de syntaxe abstraite, suis-je obligé de créer et pourquoi

?
Était-ce utile?

La solution 2

J'ai trouvé cette réponse à la question sur jGuru écrit par Terence Parr, qui a créé ANTLR. Je copiais cette explication du site lié :

Seulement simple, traductions dites directives de syntaxe peut être fait avec des actions au sein de l'analyseur. Ces types de traductions ne peuvent cracher des constructions qui sont des fonctions d'information déjà vu à ce moment-là dans l'analyse syntaxique. Arbres parseurs vous permettent de marcher une forme intermédiaire et de manipuler cet arbre, il morphing progressivement sur plusieurs phases de traduction à une forme finale qui peut être facilement imprimé en arrière comme la nouvelle traduction.

Imaginez un simple problème de traduction où vous voulez imprimer une page html dont le titre est « Il y a des éléments n » où n est le nombre d'identifiants que vous avez trouvé dans le flux d'entrée. Les ids doivent être imprimés après le titre comme celui-ci: 

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

de l'entrée 

Dog
Cat
Velociraptor

Donc, avec des actions simples dans votre grammaire comment pouvez-vous calculer le titre? Vous ne pouvez pas lire sans l'entrée entière. Ok, donc maintenant nous savons que nous devons une forme intermédiaire. Le meilleur est habituellement un AST que j'ai trouvé puisqu'il enregistre la structure d'entrée. Dans ce cas, il est juste une liste, mais il montre mon point.

Ok, maintenant vous savez qu'un arbre est une bonne chose pour quoi que ce soit, mais de simples traductions. Compte tenu de l'AST, comment obtenez-vous la sortie de celui-ci? Imaginez des arbres simples d'expression. Une façon est de faire les nœuds dans les classes spécifiques d'arbres comme PlusNode, IntegerNode et ainsi de suite. Ensuite, vous venez de demander chaque nœud à s'imprimer. Pour l'entrée, 3 + 4 vous auriez arbre:

+ | 3 - 4

et les 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();
  }
}

Étant donné un arbre d'expression, vous pouvez le traduire retour au texte avec t.toString (). Alors, quel est le problème? Semble excellent travail, non? Il semble bien fonctionner dans ce cas parce qu'il est simple, mais je soutiens que, même pour cet exemple simple, grammaires d'arbres sont plus lisibles et les descriptions sont formalisées de précision ce que vous Codé dans le PlusNode.toString (). 

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

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

Notez que la classe spécifique ( « AST hétérogène ») approche code en fait un analyseur récursif-descente complète pour # (+ INT INT) à la main dans toString (). Comme les gens du générateur d'analyseur, cela devrait vous faire grincer des dents. ;)

La principale faiblesse de l'approche hétérogène AST est qu'il ne peut pas accéder facilement à des informations contextuelles. Dans un analyseur récursif-descente, votre contexte est facilement accessible car il peut être transmis en tant que paramètre. Vous savez aussi précisément quelle règle peut invoquer la règle qui d'autre (par exemple, est cette expression une condition du while ou une condition SI?) En regardant la grammaire. La classe PlusNode existe au-dessus dans un monde détaché, isolé où il n'a aucune idée de qui est l'invoquer toString (). Pire encore, le programmeur ne peut pas dire dans quel contexte il sera appelé par la lecture.

En résumé, l'ajout d'actions à votre analyseur d'entrée fonctionne pour les traductions très simples où:

  1. l'ordre des produits d'assemblage de sortie est le même que l'ordre d'entrée
  2. toutes les constructions peuvent être générées à partir des informations analysées jusqu'au point où vous avez besoin de les recracher

Au-delà de cela, vous avez besoin d'une forme intermédiaire - l'AST est la meilleure forme habituellement. En utilisant une grammaire pour décrire la structure de l'AST est analogue à l'aide d'une grammaire pour analyser votre texte d'entrée. descriptions formalisées dans un langage de haut niveau spécifique à un domaine comme ANTLR sont mieux que la main parseurs codées. Actions dans une grammaire d'arbres ont contexte très clair et peuvent accéder facilement à l'information est passé de rlues invoquant. Les traductions qui manipulent l'arbre pour les traductions sont multipass aussi beaucoup plus facile en utilisant une grammaire de l'arbre.

Autres conseils

Création d'un AST avec ANTLR est incorporé dans la grammaire. Vous ne devez pas le faire, mais il est un très bon outil pour les besoins plus complexes. Ceci est un tutoriel sur la construction d'arbres que vous pouvez utiliser.

En fait, avec ANTLR lorsque la source est obtenir analysé, vous avez quelques options. Vous pouvez générer un code ou un AST en utilisant les règles de réécriture dans votre grammaire. AST est essentiellement une représentation de la mémoire de votre source. A partir de là, il y a beaucoup que vous pouvez faire.

Il y a beaucoup à Antlr. Si vous n'êtes pas déjà, je vous recommande de prendre le livre .

Je pense que la création du AST est facultative. arbre de syntaxe abstraite est utile pour un traitement ultérieur comme l'analyse sémantique du programme analysé.

Vous seul pouvez décider si vous devez en créer un. Si votre seul objectif est la validation syntaxique, alors vous n'avez pas besoin de générer un. javacc (similaire à ANTLR) il y a un utilitaire appelé JJTree qui permet la génération de l'AST. Donc, je pense que c'est facultatif dans ANTLR ainsi.

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top