Lookahead-Parser und Reduktionsregeln

[Desmulator]

Guten Morgen,

Es geht um Parser und zwar möchte ich gerne einen Bottom-Up-Parser implementieren, der zuvor aus EBNF erzeugte Regel an einer Eingabe auswertet und entsprechend die Eingabe reduziert. Dazu kommt, dass ich keine Tabellen verwenden möchte. Also liegt ja ein Shift-reduce-parser nahe, aber da habe ich folgendes Problem:

Zitat:

A ← AB | B
C ← A + A

Das sind die Regeln und nun folgender Code:

Zitat:

BB+BBB
AB+BBB
A+BBB
A+ABB
CB

würde mir also jetzt einen Fehler ausgeben, obwohl sich die Eingabe vollkommen zu C reduzieren müsste. Was kann man da tun? O_o

[Dejan Vu]

Die Grammatik ist wohl nicht eindeutig.
AB+AB => A+A => C
AB+AB => AA+AA => ACA

Soweit ich mich erinnere, musst Du den SR-Konflikt auflösen, durch zusätzliche Regeln.

[Sailor]

Jein, aus dem Fragment läßt sich das nicht erschließen. Es kommt darauf an, wie C eingebunden ist:

X ← A | C
A ← AB | B
C ← A + A

ist eindeutig, läßt aber nur eine Addition zu.

X ← A
A ← AB | B | C
C ← A + A

läßt mehrmalige Additionen zu, ist aber mehrdeutig.

X ← A | C
A ← AB | B
C ← A + A | C + A

ist eindeutig und läßt mehrmalige Additionen zu.

[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.

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

[Sailor]

Zitat:

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.

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

Keine Tabellen: Er will sowas wie yacc nicht benutzen.
Vielleicht will er einen Early-Parser bauen.

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.

[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.