Analyser des expressions avec un nombre non défini d'arguments

Question

J'essaie d'analyser une chaîne dans un langage qu'il a créé lui-même en une sorte d'arborescence, par exemple:

# a * b1 b2 -> c * d1 d2 -> e # f1 f2 * g

devrait avoir pour résultat:

# a
  * b1 b2
    -> c
  * d1 d2
    -> e
# f1 f2
  * g

#, * et - > sont des symboles. a, b1, etc. sont des textes.

Depuis que je ne connais que la méthode rpn pour évaluer les expressions, ma solution actuelle est la suivante. Si je n'autorise qu'un seul jeton de texte après chaque symbole, je peux facilement convertir d'abord l'expression en notation RPN (b = b1 b2; d = d1 d2; f = f1 f2) et l'analyse à partir d'ici:

a b c - > * d e - > * # f g * #

Cependant, la fusion de jetons de texte et de tout ce qui vient semble poser problème. Mon idée était de créer des jetons de marqueur (M), ainsi RPN ressemble à:

a M b2 b1 M c - > * M d2 d1 M e - > * # f2 f1 M g * #

qui est également analysable et semble résoudre le problème.

Cela dit:

1. Quelqu'un at-il de l'expérience dans ce domaine et peut-il affirmer que ce n'est pas une solution viable pour l'avenir?
2. Existe-t-il de meilleures méthodes pour analyser les expressions à arité non définie d'opérateurs?
3. Pouvez-vous m'indiquer de bonnes ressources?

Remarque. Oui, je sais que cet exemple ressemble beaucoup à la notation de préfixe Lisp et que la meilleure solution serait peut-être d'ajouter des crochets, mais je n'ai aucune expérience ici. Cependant, le texte source ne doit pas contenir de crochets artificiels et je ne sais pas trop quoi faire à propos des mixins potentiels d'infix, comme # a * b - > [si valeur1 = valeur2] c - > d.

Merci pour toute aide.

EDIT: Il semble que ce que je cherche, ce soient des sources en notation postfixe avec un nombre variable d’arguments.

Answer 1

Je ne comprenais pas tout à fait votre question, mais il semble que vous souhaitiez une définition de la grammaire et un générateur d’analyseur. Je vous suggère de consulter ANTLR . Il devrait être assez simple de définir une grammaire pour votre la syntaxe originale ou le RPN.

Modifier: (Après avoir exercé son autocritique et fait un effort pour comprendre les détails de la question.) En fait, la grammaire linguistique n'est pas claire à partir de votre exemple. Cependant, il me semble que les avantages des notations prefix / postfix (c’est-à-dire que vous n’avez besoin ni de parenthèses ni d’un analyseur syntaxique tenant compte de la préséance) proviennent du fait que vous connaissez le nombre d’arguments à chaque fois. vous rencontrez un opérateur, vous savez donc exactement combien d'éléments à lire (pour la notation avec préfixe) ou à sortir de la pile (pour la notation avec postfix). OTOH, je crois que le fait d’avoir des opérateurs pouvant avoir un nombre variable d’arguments rend les notations préfixes / postfixes non seulement difficiles à analyser, mais carrément ambiguë. Prenons par exemple l'expression suivante:

# a * b c d

Lequel des trois suivants est la forme canonique?

1. (a, * (b, c, d))

2. (a, * (b, c), d)

3. (a, * (b), c, d)

Sans en savoir plus sur les opérateurs, il est impossible de le savoir. Vous pouvez bien sûr définir une sorte de cupidité des opérateurs, par exemple. * est plus gourmand que #, donc il engloutit tous les arguments. Mais cela irait à l'encontre de la notation par préfixe, car vous ne pourriez tout simplement pas écrire la deuxième variante parmi les trois précédentes; non sans éléments syntaxiques supplémentaires.

Maintenant que j'y pense, ce n'est probablement pas par hasard qu'aucun des langages de programmation que je connais ne prend en charge les opérateurs avec un nombre variable d'arguments, uniquement les fonctions / procédures .