Format standard pour arbres syntaxiques concrets et abstraits

Question

J'ai une idée pour un projet de passe-temps qui effectue une analyse et une manipulation de code. Ce projet nécessitera à la fois les arbres de syntaxe concrète et abstraite d'un fichier source donné. De plus, des références bidirectionnelles entre les deux arbres seraient utiles. Je voudrais éviter le travail de transcription d'une grammaire pour construire mon propre lexer et analyseur.

Existe-t-il un format standard pour décrire les arbres de syntaxe concrets ou abstraits? Est-ce que les chaînes d'outils largement utilisées prennent en charge la sortie de ces formats?

Je n'ai pas de langage de programmation cible en tête. Tout ce qui est populaire va faire pour un prototype, mais je préférerais celui que je connais bien: Python, C#, Javascript, ou C/C++. J'aimerais pouvoir exécuter un fichier source à l'aide d'un outil ou d'une bibliothèque et récupérer les deux arborescences. Dans un monde idéal, il serait pratique d'exécuter cet outil sur du code car il est édité par un utilisateur et tolère les erreurs. Encore une fois, j'essaie simplement de développer un prototype, donc ces exigences sont assez laxistes.

Merci!

Answer 1

En our project nous avons défini le métamodèle AST dans UML et utilisons ANTLR (Java) pour peupler le modèle. Nous conservons également les informations de jeton d'ANTLR après l'analyse, mais nous n'avons pas encore essayé de mettre à jour le fichier texte sous-jacent avec les modifications apportées au modèle. Cela a des frais généraux hideux (dans l'infrastructure, comme Eclipse UML2/EMF), mais notre objectif est de toute façon d'utiliser des outils de haut niveau pour le développement basé sur un modèle (MDD, MDA), nous avons donc décidé d'utiliser à chaque niveau.

Je pense que l'un de nos étudiants a déjà joué avec OpenArchitectureWare et a réussi à récupérer automatiquement les modifications de l'éditeur généré Eclipse dans l'arbre de syntaxe (sans rapport avec le modèle UML ci-dessus), mais je ne connais pas détails à ce sujet.

Vous pouvez également regarder ANTLR's grammaires d'arbres.

Answer 2

La communauté de recherche a décidé que l'échange de graphiques était la bonne chose à faire lors du transfert d'information d'un outil d'analyse de programme à un autre. Voir http://www.gupro.de/GXL

Plus récemment, l'OMG a défini une norme pour l'échange d'arbres syntaxiques abstraits. Voir http://www.omg.org/spec/ASTM/1.0/Beta1/

Ce problème semble être résolu à maintes reprises. Il ya une demi-douzaine de propositions de «bus d'outils» faites au cours des années qui ont toutes résolu le problème, sans que personne ne dépasse jamais l'industrie. Le problème est que a) il est facile de représenter les ASTs en utilisant toute sorte de notation imbriquée [parenthèses comme LISP, comme XML, ...] afin que les gens roulent facilement leur propre solution, et b) pour un outil d'échange un AST avec un autre, ils tous les deux doivent être d'accord essentiellement sur ce que les nœuds AST signifient; mais la plupart des ASTs sont plutôt dérivés accidentellement de la grammaire/syntaxe particulière utilisée par chaque outil, et il ya désaccord presque toujours à ce sujet entre les outils. Ainsi, j'ai vu très peu d'outils qui échangent des AST significativement.

Si vous faites une chose passe-temps, je bâton avec un Lisp comme l'encodage des arbres, où chaque noeud a le format suivant: (...) Il est facile à produire, et facile à lis. Je travaille sur un professional tool to manipulate programs. Si nous avons imprimer l'AST, nous faisons ce qui précède. La plupart des individus sont beaucoup trop compliqués à regarder dans la pratique, donc nous n'imprimons presque jamais l'ensemble de l'AST, au mieux seulement un nœud et quelques enfants de profondeur. Notre outil n'échange pas ASTs avec n'importe qui (voir ci-dessus raisons :) mais fait juste le construisant bien dans la mémoire, faisant des choses whizzy avec lui pour des raisons d'analyse ou des raisons de transformation, et puis le supprimant juste (pas besoin de envoyez-le n'importe où) ou en régénérant le texte de la langue originale à partir de l'arbre. [Ce dernier signifie que vous avez besoin d'anti-parser, ou « prettyPrinting » la technologie ]

Answer 3

normes spécifiques sont une attente, alors que les normes d'usage plus général peuvent également convenir. Ira Baxter a déjà mentionné GXL, et RDF peut aussi être ajouté, juste qu'il aurait besoin d'une ontologie appropriée et serait plus orienté vers la sémantique que la syntaxe. Encore peut-être une option à étudier.

Pour des normes spécifiques, Ira Baxter a déjà été mentionné ASTM, un autre, même si elle vise plutôt un type spécifique de langage de programmation (langages logiques), est a standard for semantic/conceptual graph, connu sous le nom ISO‑IEC 24707 2007.

Pas une norme en soi, mais un papier à ce sujet: Towards Portable Source Code Representations Using XML .

Je ne connais pas de norme effectivement utilisée (dans ce domaine, c'est toujours la cuisine faite maison partout), je m'intéresse aussi à ce sujet.