String auf bestimmte Syntax testen

Ein simples Beispiel für die Anwendung des Compilerbaus.

Üblicherweise geht man mehrstufig vor:
- Ein Tokenizer zerlegt den String in Tokens, also Zahlen, Operatoren, Klammern.
- Ein Parser überprüft, ob die Syntax in Ordnung ist und kann auch gleich einen Baum erstellen. Bei so einfachen Parsern verwendet man üblicherweise rekursiven Abstieg (LL(n)), bei komplexeren Dingen eher etwas wie LR(n).
- Diesen Baum wertest du dann aus (z.b. mit einem Visitor oder einer calc()-Methode in jedem Objekt des Baums).

Für Tokenizer und Parser kannst du auch Tools verwenden, die dir die meiste Arbeit abnehmen: lex und yacc.

Im Übrigen ist das ein Standardbeispiel - es sollte genug Literatur dazu im Google geben, wie man so was baut.

EDIT: Wenn es dir aber nur um die Überprüfung und nicht so sehr um die Auswertung des Strings geht, dann reicht auch eine Regular Expression Library aus.

Wurde eh schon fast alles gesagt was wichtig ist, aber hier noch 2 Anmerkungen:

• Auf jeden Fall http://www.antlr.org/ evaluieren, bevor Du dich auf lex/yacc stuerzt.
  
• Was in deinem Fall vielleicht Sinn machen koennte: Anstatt einen neuen Interpreter fuer eine neue Sprache zu schreiben, kannst Du natuerlich auch einen bestehende Interpreter von einer anderen Sprache verwenden. Mathematische Ausdruecke auswerten koennen ja sehr viele Sprachen. Du koenntest z.b. den Ausdruck von bc oder python oder Rhino oder SQLite auswerten lassen. In diesem Fall wuerde ich aber den Ausdruck zumindest vorher mit einer Regular Expression pruefen, vor allem, wenn die Ausdruecke von einem Benutzer eingegeben werden koennen.

Antlr evaluieren - auf jeden Fall.

Aber mir ist er nicht sehr sympathisch. Da mag ich flex/bison schon viel lieber. Mir geht auf die Nerven, dass der von ANTLR erzeugte Parser bei der Auswertung ständig Exceptions wirft - sehr unpraktisch, wenn man im Debugger einen Breakpoint auf Exception throw gesetzt hat.
Und die Diagnostics versteh ich auch nicht wirklich. Die vom bison sind da schon eher verständlich, wenn man eine Ahnung vom shift/reduce-Mechanismus hat.

Zitat von sauzachn

EDIT: Wenn es dir aber nur um die Überprüfung und nicht so sehr um die Auswertung des Strings geht, dann reicht auch eine Regular Expression Library aus.

Nicht wirklich, wenn du auch die Klammerebenen kontrollieren willst. Das ist nämlich nicht regulär, dazu brauchst du schon einen Kellerautomaten.

kannst dich noch an eProg erinnern ....

verwende so einen Operationsbaum:

3+5*7 =>
+
/ \
3 *
/ \
5 7

und so weiter das ist das einfachste und wenn mal wo ein blatt felt -> fehler
oder nach jeden operator keine zahl kommt ....

Naja, das geht zB mit boost::spirit. Aber das könnte evtl etwas über die OOP-LVA hinaus gehen.

Zitat von Thorgos

Ich möchte am liebsten das alles in EBNF Notation schreiben und dann den string anhand dieser EBNF Notation kontrollieren.

Du kannst deine EBNF-Grammatik praktisch 1:1 in einen rekursiven Abstieg ("recursive descent") abbilden.

Kurz gesagt machst du für jedes Nichtterminal eine Methode dieses Namens in deiner Parser-Klasse, die das überprüft, was bei dem Nichtterminal nach ::= steht.

Der Body sieht immer recht ähnlich aus. Du schaust dir das nächste Token an und wenn es der Erwartung entspricht, baust du deinen Syntaxbaum (auch AST genannt) weiter auf. Ansonsten gibst du einen Fehler aus o.ä.

Probleme (im Sinne von Komplexität) gibts beim rekursiven Abstieg immer erst dann, wenn du mehr als ein Zeichen Lookahead brauchst (LL(n) für n >= 2) oder wenn du sehr umfangreiche Grammatiken hast, die man besser mit (automatisch erzeugten, da händisch sehr umständlich zu erstellende FIRST- und FOLLOW-Mengen anstehen) LR(1) erschlägt. In deinem Fall seh ich das Problem aber nicht, da du mit einem Token Lookhead auskommen solltest.