Lookahead-Parser und Reduktionsregeln

[Desmulator]

Zitat von Namenloser:

Was für Grammatiken willst du denn überhaupt parsen? Kontextfreie? In dem Fall wäre es wohl vernünftig, die Definition erst mal in Chomsky-Normalform Greibach-Normalform zu bringen.

Wirklich viele Gedanken habe ich mir über die Grammatik nicht gemacht. Momentan gehe ich davon aus, dass ich in EBNF-kodierte Grammatik erhalte und anhand dieser will ich eine Eingabe bearbeiten. Also zum einen überprüfen ob die Eingabe eine gültige Syntax hat und auf der anderen, diese Eingabe eben als Baum darstellen.

Zitat von Namenloser:

Mir ist nicht klar, was du mit „keine Tabellen“ meinst.

Eine "Aktions- und Goto-Tabelle".

Habe mir heute nochmal Gedanken gemacht und bin dabei auf zwei "Lösungen" gekommen:
1. Die zuletzt benutze Regel wird vorranig vor allen anderen Regeln angewandt. Also in dem Fall würde ich, statt noch der ersten Reduktion von B zu A nicht versuchen direkt eine weitere Regel anzuwenden, sondern mit Lookahead versuchen die Reduktion von A erneut zu benutzen.
Das ganze scheint mir aber sehr unsauber und irgendwie eher eine Symptombekämpfung als eine richtige Lösung.

2. Ich ermittle vor der Reduktion alle möglichen Reduktionen und merke mir diese. Dann wende ich eine dieser an. Sollte als Folge dieser Reduktion irgendwann ein Fehler auftreten, so springe ich zurück und versuche die nächste Reduktion. Dies setzte ich dann jeweils rekursiv so fort.
Würde bestimmt funktionieren, aber hat einen ziemlich großen aufwand, wenn man davon aus geht, dass in den meisten Fällen die Regeln eben nicht eindeutig sind.

Zitat:

Was soll die Umwandlung in eine Normalform bringen? Die Grammatik (sofern das obige Beispiel nicht nur ein Ausschnitt ist) erzeugt die leere Sprache (es fehlt zumindest eine Regel wie B ← <Number>) und sie hat 2 Satzsymbole. Das müßte vor weiteren Diskussionen erst mal geregelt werden.

Zitat:

B ← "0"|...|"9"
A ← AB | B
C ← A + A | C + A

Die obigen Regeln waren nur als Beispiel gedacht um das Problem anschaulich zu beschreiben.