Quel est l'algorithme d'analyse des expressions en notation infixe?

algorithm expression-trees language-agnostic parsing php

Question

Je voudrais analyser les expressions booléennes en PHP. Un péché:

A and B or C and (D or F or not G)

Les termes peuvent être considérés comme des identificateurs simples. Ils auront un peu de structure, mais l'analyseur n'a pas besoin de s'inquiéter de cela. Il faut juste reconnaître les mots-clés and or not ( ) . Tout le reste est un terme.

Je me souviens que nous avions écrit à l'école des évaluateurs d'expression arithmétique simples, mais je ne me souviens plus comment cela s'est passé. Je ne sais pas non plus quels mots clés rechercher dans Google / SO.

Une bibliothèque prête à l'emploi serait bien, mais si je me souviens bien, l'algorithme était assez simple, il serait donc amusant et éducatif de le ré-implémenter moi-même.

Réponse populaire

Les analyseurs récursifs de descente sont amusants à écrire et faciles à lire . La première étape consiste à écrire votre grammaire.

Peut-être que c'est la grammaire que vous voulez.

expr        = and_expr ('or' and_expr)*
and_expr    = not_expr ('and' not_expr)*
not_expr    = simple_expr | 'not' not_expr
simple_expr = term | '(' expr ')'

Il est très facile de transformer cela en analyseur de descente récursif. Il suffit d'écrire une fonction par terminal.

expr        = and_expr ('or' and_expr)*
and_expr    = not_expr ('and' not_expr)*
not_expr    = simple_expr | 'not' not_expr
simple_expr = term | '(' expr ')'

Ce n'est pas complet. Vous devez fournir un peu plus de code:

  • Fonctions d'entrée. consume , peek d' is_term peek , et is_term sont des fonctions que vous fournissez. Ils seront faciles à implémenter en utilisant des expressions régulières. consume(s) lit le prochain jeton d’entrée et renvoie une erreur s’il ne correspond pas à s . peek() renvoie simplement un jeton au prochain jeton sans le consommer. is_term(s) renvoie true si s est un terme.

  • Fonctions de sortie. OR , AND , NOT et TERM sont appelés à chaque fois qu'une partie de l'expression est analysée avec succès. Ils peuvent faire ce que tu veux.

  • Fonction d'emballage. Au lieu d'appeler directement directement expr , vous aurez envie d'écrire une petite fonction wrapper qui initialise les variables utilisées par consume et peek , puis d'appeler expr et enfin de vérifier que rien ne reste non plus consommé.

Même avec tout cela, cela reste une petite quantité de code. En Python, le programme complet compte 84 lignes et comprend quelques tests.




Sous licence: CC-BY-SA with attribution
Non affilié à Stack Overflow
Est-ce KB légal? Oui, apprenez pourquoi
Sous licence: CC-BY-SA with attribution
Non affilié à Stack Overflow
Est-ce KB légal? Oui, apprenez pourquoi