Programmmieren eines Mathe-Parsers

[FAlter]

Hi,

die Behauptung stammt von einem Info-Lehrer und als Beispiel hatten wir einen Kellerautomat (der mit einem Stack arbeitet), meist reicht es stattdessen schon, einen Automat mit einem zusätzlichen Zähler anstelle des Stacks zu verwenden, da nur gleichartige Informationen auf dem Stack abgelegt werden und es lediglich nötig ist, zu unterscheiden, ist was drauf oder nicht. Und doch, in gewissen Grenzen bereiten Syntaxchecks mit einem Automaten kein Problem, es muss nicht einmal ein Kellerautomat sein, wenn du z. B. nur prüfen willst, ob die Eingabe eine natürliche Zahl ist. Es kommt auf den Sprachaufbau an, aber etwas in der Form (1+2)*(3^4) zu überprüfen ist möglich. (Der Stack wird dann höchstens für die Klammern benötigt, alles andere schafft man auch ohne).

Tatsächlich sind komplexere Syntaxchecks bisher das einzige, wozu ich bisher einen Automaten vorgezogen habe, da ich sonst keine Idee hatte. In anderen Anwendungsfällen kann man auf die Automatentheorie meist verzichten, jedenfalls den blöden Schulbeispielen nach.

Wikipedia gibt mir auch recht:

Zitat:

Der eigentliche Parser als Implementierung eines abstrakten Automaten (meist realisiert als Kellerautomat) kümmert sich dagegen um die Grammatik der Eingabe, führt eine syntaktische Überprüfung der Eingangsdaten durch und erstellt in der Regel aus den Daten einen Ableitungsbaum (in Anlehnung an das Englische gelegentlich auch als Parse-Baum bezeichnet). Dieser wird danach zur Weiterverarbeitung der Daten verwendet; typische Anwendungen sind die semantische Analyse, Codegenerierung in einem Compiler oder Ausführung durch einen Interpreter.

Absatz 2 unter Funktionsweise
http://de.wikipedia.org/wiki/Parser#Funktionsweise

Mfg
FAlter

[Macci]

Hallo,

klar funktioniert es mit einem Kellerautomaten. Ich dachte jetzt eher du meinst einen DFA, weil ein Computer ist nichts anderes als ein solcher, und Sebastian92 will das ganze ja auf Delphi programmieren, also kommt nur ein DFA in Frage.

Ein Kellerautomat kann mehr als reguläre Sprachen erkennen (nämlich genau kontextfreie), und das reicht für solche Ausdrücke aus. Ein DFA wird aber im Allgemeinen NICHT ausreichen. (Beispielweise für Additionen im R^n oder auch N^n, wenn du - wie du vorgeschlagen hast - nur natürliche Zahlen verwenden willst, funktioniert es nicht.)

[Medium]

Ja nun werft dem armen doch nicht gleich die gesamte Automatentheorie vor die Füße :). Wobei ich zugeben muss, dass ich erst so wirklich verstanden habe was ein Parser genau tut, nachdem ich mir die theoretische Informatik Vorlesung reingeschlabbert hab.
Wenn du (TE) noch ziemlicher Neuling beim Programmieren bist, und mit Begriffen wie Compilerbau, Tokenizer oder Automaten so überhaupt nichts verbindest, wäre es in der Tat erstmal ratsam, wenn du dir einen existierenden Parser schnappst und ihn nutzt. Um einen eigenen so gut zu bekommen wie manchen bestehenden (HAM z.B. ;)) wird, so meine Vermutung stimmt, dass du Neuling bist, eine ganz schön beachtliche Menge Theorie zwischen dir und einem eigenen brauchbaren Parser stehen.