Was ist der Algorithmus zum Parsen von Ausdrücken in der Infix-Notation?

algorithm expression-trees language-agnostic parsing php

Frage

Ich möchte boolesche Ausdrücke in PHP analysieren. Wie in:

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

Die Begriffe können als einfache Identifikatoren betrachtet werden. Sie werden eine kleine Struktur haben, aber der Parser muss sich darüber keine Gedanken machen. Es sollte nur die Schlüsselwörter erkennen and or not ( ) . Alles andere ist ein Begriff.

Ich erinnere mich, dass wir in der Schule einfache Rechenexpressions-Evaluatoren geschrieben haben, aber ich erinnere mich nicht mehr daran, wie es gemacht wurde. Ich weiß auch nicht, nach welchen Keywords in Google / SO gesucht werden soll.

Eine fertige Bibliothek wäre schön, aber wie ich mich erinnere, war der Algorithmus ziemlich einfach, so dass es vielleicht lustig und lehrreich wäre, ihn selbst zu replizieren.

Beliebte Antwort

Rekursive Abstammung Parser sind lustig zu schreiben und leicht zu lesen . Der erste Schritt besteht darin, Ihre Grammatik zu schreiben.

Vielleicht ist das die Grammatik, die du willst.

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

Dies zu einem rekursiven Descent-Parser zu machen ist super einfach. Schreiben Sie einfach eine Funktion pro Nichtterminal.

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

Dies ist nicht vollständig. Sie müssen etwas mehr Code bereitstellen:

  • Eingabefunktionen consume , peek und is_term sind Funktionen , die Sie zur Verfügung stellen. Sie können einfach mit regulären Ausdrücken implementiert werden. consume(s) liest das nächste Token der Eingabe und gibt einen Fehler aus, wenn es nicht mit s übereinstimmt. peek() einfach einen Blick auf das nächste Token zurück, ohne es zu verbrauchen. is_term(s) gibt true zurück, wenn s ein Begriff ist.

  • Ausgabefunktionen OR , AND , NOT und TERM werden jedes Mal aufgerufen, wenn ein Teil des Ausdrucks erfolgreich analysiert wird. Sie können tun, was immer Sie wollen.

  • Wrapper-Funktion. Anstatt nur telefonieren expr direkt, sollten Sie eine wenig Wrapper - Funktion schreiben , die die Variablen durch verwendet initialisiert consume und peek , dann ruft expr , und schließlich überprüft , um sicherzustellen , gibt es kein Überbleibsel Eingang , die nicht verbraucht bekommt.

Trotz all dem ist es immer noch eine winzige Menge Code. In Python besteht das komplette Programm aus 84 Zeilen und das beinhaltet ein paar Tests.




Lizenziert unter: CC-BY-SA with attribution
Nicht verbunden mit Stack Overflow
Ist diese KB legal? Ja, lerne warum
Lizenziert unter: CC-BY-SA with attribution
Nicht verbunden mit Stack Overflow
Ist diese KB legal? Ja, lerne warum