Construction D'un arbre de syntaxe abstrait avec une liste de Tokens

l'astuce fondamentale est de reconnaître que l'analyse, quelle que soit la façon dont elle est effectuée, se fait par étapes progressives, y compris la lecture des jetons un par un.

à chaque étape, il est possible de construire une partie de L'AST en combinant des fragments AST construits par d'autres étapes. C'est une idée récursive, et il Bast out dans la construction de noeuds de feuilles AST pour les jetons comme ils sont balayés. Cette idée de base se produit dans à peu près tous les AST-construction parsers.

si on construit un analyseur de descente récursif, on construit en fait un système coopératif de procédures récursives, dont chacune reconnaît un nonterminal dans la grammaire mise en œuvre. Pour l'analyse pure, chaque procédure renvoie simplement un booléen pour "nonterminal (not) recognized".

pour construire un AST avec un parser de descente récursif, on conçoit ces procédures pour retourner deux valeurs: le booléen "reconnu", et, si reconnu, un AST construit (en quelque sorte) pour le non-criminel. (Un hack commun est un pointeur de retour, qui est vide pour "non reconnu", ou des points à l'AST construit si "reconnu"). La façon dont L'AST résultant pour une procédure simple est construit, est en combinant les AST des sous-procédures qu'il invoque. C'est assez trivial à faire pour les procédures leaf, qui lisent un jeton d'entrée et peuvent immédiatement construire un arbre.

l'inconvénient de tout cela est qu'il faut coder manuellement la récursive la descente, et l'augmenter avec les étapes de construction de l'arbre. Dans le grand ordre des choses, c'est en fait assez facile à coder pour les petits grammaires.

par exemple OP, supposons que nous ayons cette grammaire:

GOAL = ASSIGNMENT 
ASSIGNMENT = LHS '=' RHS ';' 
LHS = IDENTIFIER 
RHS = IDENTIFIER | NUMBER

OK, notre parser de descente récursive:

boolean parse_Goal()
{  if parse_Assignement()
   then return true
   else return false
}

boolean parse_Assignment()
{  if not Parse_LHS()
   then return false
   if not Parse_equalsign()
   then throw SyntaxError // because there are no viable alternatives from here
   if not Parse_RHS()
   then throw SyntaxError
   if not Parse_semicolon()
   the throw SyntaxError
   return true
}

boolean parse_LHS()
{  if parse_IDENTIFIER()
   then return true
   else return false
}

boolean parse_RHS()
{  if parse_IDENTIFIER()
   then return true
   if parse_NUMBER()
   then return true
   else return false
}

boolean parse_equalsign()
{  if TestInputAndAdvance("=")  // this can check for token instead
   then return true
   else return false
}

boolean parse_semicolon()
{  if TestInputAndAdvance(";")
   then return true
   else return false
}

boolean parse_IDENTIFIER()
{  if TestInputForIdentifier()
   then return true
   else return false
}

boolean parse_NUMBER()
{  if TestInputForNumber()
   then return true
   else return false
}

maintenant, révisons-le construisons un arbre de syntaxe abstrait:

AST* parse_Goal() // note: we choose to return a null pointer for "false"
{  node = parse_Assignment()
   if node != NULL
   then return node
   else return NULL
}

AST* parse_Assignment()
{  LHSnode = Parse_LHS()
   if LHSnode == NULL
   then return NULL
   EqualNode = Parse_equalsign()
   if EqualNode == NULL
   then throw SyntaxError // because there are no viable alternatives from here
   RHSnode = Parse_RHS()
   if RHSnode == NULL
   then throw SyntaxError
   SemicolonNode = Parse_semicolon()
   if SemicolonNode == NULL
   the throw SyntaxError
   return makeASTNode(ASSIGNMENT,LHSNode,RHSNode)
}

AST* parse_LHS()
{  IdentifierNode = parse_IDENTIFIER()
   if node != NULL
   then return IdentifierNode
   else return NULL
}

AST* parse_RHS()
{  RHSnode = parse_IDENTIFIER()
   if RHSnode != null
   then return RHSnode
   RHSnode = parse_NUMBER()
   if RHSnode != null
   then return RHSnode
   else return NULL
}

AST* parse_equalsign()
{  if TestInputAndAdvance("=")  // this can check for token instead
   then return makeASTNode("=")
   else return NULL
}

AST* parse_semicolon()
{  if TestInputAndAdvance(";")
   then return makeASTNode(";")
   else return NULL
}

AST* parse_IDENTIFIER()
{  text = TestInputForIdentifier()
   if text != NULL
   then return makeASTNode("IDENTIFIER",text)
   else return NULL
}

AST* parse_NUMBER()
{  text = TestInputForNumber()
   if text != NULL
   then return makeASTNode("NUMBER",text)
   else return NULL
}

j'ai évidemment glissé sur certains détails, mais je suppose que le lecteur sera n'ont aucune difficulté à les remplir.

Parser les outils générateurs comme JavaCC et ANTLR génèrent essentiellement des parseurs de descente récursifs, et ont des installations pour construire des arbres qui fonctionnent beaucoup comme ceci.

Analyseur générateur outils de construire bottom-up analyseurs (YACC, le Bison, le GLR ...) construisent aussi des noeuds AST dans le même style. Cependant, il n'y a pas d'ensemble de fonctions récursives; au lieu de cela, une pile de tokens Vus et réduits-à des non-terminaux est gérée par ces outils. Les noeuds AST sont construits sur une pile parallèle; lorsqu'une réduction se produit, les noeuds AST de la partie de la pile couverte par la réduction sont combinés pour produire un noeud AST non terminal pour les remplacer. Cela se produit avec des segments de pile "de taille zéro" pour des règles de grammaire qui sont trop vides faisant apparaître des noeuds AST (généralement pour 'liste vide' ou 'option manquante') de nulle part.

avec des langues légères, écrivant des parseurs de descendance récursive qui construisent des arbres est assez pratique.

un problème avec les langues réelles (qu'elles soient anciennes et bruyantes comme COBOL ou chaudes et brillantes comme Scala) est que le nombre de règles grammaticales est assez grand, compliqué par la sophistication du langage et l'insistance sur n'importe quel comité de langue est en charge de celui-ci à perpétuellement ajouter de nouvelles bonnes choses offertes par d'autres langues ("envie de langue", voir la course évolutive entre Java, C# et C++). Maintenant, écrire un analyseur de descente récursif main et on a tendance à utiliser des générateurs d'analyseurs. Mais même avec un générateur d'analyseur, écrire tout le code personnalisé pour construire des noeuds AST est aussi une grosse bataille (et nous n'avons pas discuté de ce qu'il faut pour concevoir une bonne syntaxe "abstraite" par rapport à la première chose qui vient à l'esprit). Le maintien des règles grammaticales et la construction AST devient de plus en plus difficile avec l'échelle et l'évolution continue. (Si votre langue a du succès, vous voudrez la changer d'ici un an). Donc même écrire les règles de construction AST obtient maladroit.

idéalement, on voudrait juste écrire une grammaire, et obtenir un analyseur et un arbre. Vous pouvez le faire avec quelques générateurs d'analyseur récents: notre logiciel DMS Reengineering Toolkit accepte les grammaires libres de contexte, et construit automatiquement un AST , aucun travail de la part de l'ingénieur de grammaire; il fait cela depuis 1995. Les gars D'ANTLR ont finalement compris cela en 2014, et ANTLR4 offre maintenant une option comme celle-ci.

Dernier point: avoir un analyseur (même avec un AST) n'est guère une solution au problème réel que vous avez cherché à résoudre, quel qu'il soit. C'est juste un morceau de fondation, et beaucoup au choc pour la plupart parser-newbies, il est le plus petit partie à un outil qui manipule le code. Google mon essai sur la vie après Parsing (ou vérifier ma bio) pour plus de détails.