Un arbre de syntaxe abstraite doit-il être un arbre?

La sortie d'un analyseur doit-elle être un arbre ou pourrait-elle également être un graphique général?

De plus, existe-t-il un langage existant ou un langage plausible qui utilise une représentation graphique générale au lieu d'arbres pour leur syntaxe?

La sortie d'un analyseur n'a pas besoin d'être un arbre. En effet, lorsque vous considérez des éléments tels que les références de l’UTILISATION d’une variable à sa DEFinition superposée à l’arbre de syntaxe abstraite, vous disposez immédiatement d’un graphique.

Le fait est que l'analyse est généralement conçue pour avoir lieu en une seule passe - cela importait pour des raisons historiques, telles que le manque d'espace et de vitesse du processeur, mais aussi parce qu'il est plus simple de raisonner. Ensuite, les phases suivantes décorent l'arbre d'analyse avec des informations supplémentaires.

Il y a des choses comme les grammaires des graphes, mais je ne sais pas si elles sont utilisées pour analyser les langages de programmation.

La question du PO est un peu rétrograde. Bien sûr, un algorithme d'analyse peut produire tout ce qu'il veut. La question est davantage de comprendre à quoi sert l'analyse et si l'analyseur produit un résultat qui répond à cet objectif. On peut alors se demander quelle est la représentation appropriée pour cela, par exemple un arbre ou un graphique.

Eh bien, je suppose qu'un analyseur est un algorithme qui vous donnera la structure syntaxique d'une phrase donnée en entrée, selon une définition formelle donnée de la syntaxe du langage.

Notez que les gens peuvent être en désaccord sur ce qui constitue la syntaxe du langage. Certains peuvent limiter cela à une épine dorsale de langage formel pur, tandis que d'autres peuvent introduire des considérations légèrement plus sémantiques telles que le type, le genre, le nombre ou d'autres plus complexes (je ne distingue pas la PNL ou les langages de programmation). La plupart des langages ont des fonctionnalités qui nécessitent la représentation des graphes, mais c'est à "l'implémenteur" (faute d'un meilleur mot) de décider s'il veut inclure cela dans la syntaxe.

Ainsi, selon la définition de la syntaxe, vous devrez peut-être générer un autre type de structure formelle.

Dans le cas simple d'une analyse sans contexte pure, un arbre d'analyse peut le faire, sauf pour le problème d'ambiguïté abordé ci-dessous, ou pour le fait que vous souhaitiez peut-être le modifier un peu pour obtenir un AST (voir ci-dessous).

Cependant, dans des cas plus complexes, vous pouvez avoir besoin de différentes structures, souvent représentées par des liens dans l'arborescence, conduisant ainsi à une structure graphique. Cela dépend beaucoup de votre définition de la syntaxe du langage.

De plus, quel arbre vous devez sortir n'est pas évident. Si vous prenez le cas des grammaires adjacentes à l'arbre (TAG), elles fonctionnent de telle manière que l'arbre de syntaxe n'est pas le même que l'arbre de dérivation, bien que le premier puisse être dérivé du second. La question que vous souhaitez afficher peut être une question pertinente.

Il y a également un autre problème concernant l'ambiguïté. Une phrase donnée, bien qu'appartenant à votre langue, peut le faire de différentes manières, peut se voir attribuer une structure syntaxique de différentes manières.

Ensuite, vous pouvez choisir de sortir une seule de ces structures, choisie au hasard ou selon un critère bien défini (comme la jeunesse par exemple). Vous pouvez également choisir d'en afficher plusieurs ou tous. Si vous souhaitez en afficher plusieurs, il est généralement pratique de les regrouper dans une structure unique qui partagera ce qu'ils ont en commun. Cette économie d'espace et de temps de calcul, et la complexité peut être un vrai problème.

Lorsque vous choisissez de les sortir tous, vous n'avez pas d'autre choix que de les partager, car il peut y avoir un nombre infini d'analyses possibles. Et infiniment ne peut être représenté de manière finie qu'en ayant en quelque sorte un cycle dans un graphe. Vous devez donc produire une structure graphique en général. Mais les propriétés de cette structure graphique doivent être liées au type de syntaxe formelle que vous avez choisi.

A propos des arbres de syntaxe abstraite

Maintenant, la question portait également sur les arbres de syntaxe abstraite. J'ai sauté la partie "abstraite" car cela apporterait de la confusion, à mon humble avis. En effet, la question prête déjà à confusion dans ses différentes reformulations.

En ce qui concerne l'AST dans une perspective historique, ils proviennent du langage Lisp et des systèmes de manipulation de programmes dans les années 1960-1970. L'idée était de considérer les programmes comme de grandes expressions, comme des formules mathématiques, à la fois à des fins de manipulation et pour analyser les propriétés ou définir la sémantique de manière formelle, ce que les mathématiciens savent faire sur les formules. En tant que formules, elles étaient naturellement arborescentes, mais pouvaient être décorées de diverses informations qui transformaient ces arbres en graphiques. Cela était pratique à la fois formellement et pragmatiquement et a été utilisé par les compilateurs et les systèmes de programmation.

Donc, fondamentalement, un AST est un arbre, comme l'indique son nom, mais peut contenir des informations supplémentaires. Le reste est dans les choix du réalisateur et aux yeux du spectateur. Est-ce un graphique ou un arbre décoré? Cependant, l'arborescence AS de base est importante, car c'est l'échafaudage sur lequel vous construisez à la fois en théorie et en programmation.

Notez que l'AST était distinct de l'arbre d'analyse (la syntaxe était basée sur le contexte) tel que produit par l'algorithme d'analyse tel qu'il a été étudié dans la théorie du langage formel. La raison en était que la conception de la syntaxe était limitée par la technologie d'analyse de l'époque, elle-même contrainte par la faible puissance de calcul disponible. Le résultat était que les arbres de syntaxe n'étaient que des variantes torturées de ce que l'on considérerait naturellement comme la structure du programme, et un traitement ultérieur, ne faisant pas vraiment partie du processus d'analyse formelle de base, devait être effectué pour obtenir la version plus propre et plus simple appelée AST.

Cependant, la représentation des arbres sur l'ordinateur, qu'elle soit abstraite ou non, est quelque peu limitée lorsque vous souhaitez représenter toutes les structures d'une phrase ambiguë. En particulier, cela cache des problèmes de complexité. La préservation des ambiguïtés dans une structure graphique, lors de la conversion des arbres d'analyse en arbres AS peut également être un problème. Cependant, si cela vous intéresse, il est souvent possible de définir votre syntaxe concrète de telle manière que l'arbre d'analyse puisse servir d'AST. Cela est permis par les algorithmes très généraux qui gèrent l'ambiguïté et par la puissance des ordinateurs actuels.

Si vous analysez à l'aide de l'analyse GLR (LR généralisée) et si l'analyse de l'entrée est ambiguë (il existe plusieurs façons d'analyser l'entrée), le résultat de l'analyse peut être considéré comme un DAG d'analyse plutôt qu'un analyser l'arbre. Le parag DAG code de manière compacte de nombreuses analyses possibles: plusieurs arbres d'analyse possibles.

Cependant, la ligne de fond reste que si vous avez une grammaire sans contexte et si votre chaîne d'entrée est analysable sans ambiguïté (il n'y a qu'une seule dérivation dans la grammaire qui produit cette chaîne d'entrée), et si le travail d'analyse est de produire cette dérivation ... alors dans ces conditions, la sortie de l'analyse sera toujours nécessairement un arbre d'analyse, car toute production d'une grammaire sans contexte a intrinsèquement une structure arborescente.

Dans la PNL, les représentations syntaxiques abstraites sont des graphes acycliques dirigés (DAG). La situation où deux arêtes pointent vers le même nœud est appelée "partage de structure".

J'ai écrit une fois un interpréteur pour C dans lequel le "AST" pour l'opérateur + = (par exemple) n'était pas un arbre. Considérez a[i++] += doù a[i++]est intet dest double. Les opérations de conversion et d'extraction implicites étaient explicites dans l'arborescence, le problème est donc de savoir où placer l'extraction a[i++]et la conversion pour doubler. Notre solution a été d'abandonner les arbres. Le "ASG" résultant ressemblait à ceci

         +=
       / | \
      /  |  \
     /   |   \
    / convert \
    |     |    \
    |   fetch  fetch
    |   /       |
    index       d
    /  \
   a   postinc
       |
       i

J'ai été intrigué par cela moi-même, jusqu'à ce que je viens de réaliser que ce n'est pas l'arbre qui est abstrait, ni qu'il s'agit d'un "arbre de syntaxe" abstrait, mais la syntaxe est abstraite.

Donc, pour répondre à votre question, je conclus qu'un arbre de syntaxe abstrait, ainsi qu'un arbre de syntaxe concret ou un arbre de décision, ou tout autre arbre, devrait mieux être un arbre.

D'un autre côté, rien ne devrait empêcher quiconque d'utiliser un graphe de syntaxe abstraite, ou un diagramme de syntaxe abstraite, ou un cube de syntaxe abstraite, ou une spécification de syntaxe abstraite.

Je suppose qu'un arbre de syntaxe abstraite de "arbre de syntaxe abstrait" m'aurait aidé à éviter la confusion.