Frage zu LL(1) Parser

AlexanderF
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 140
Registriert: 2. Mai 2010 17:55

Frage zu LL(1) Parser

Beitrag von AlexanderF »

Hallo,

oh, bisher ist ja überhaupt nichts geschrieben worden in dem Forum zu dieser Veranstaltung,


also, ich habe zwei Verständnisfrage zu LL(1) Parsern,
zum einen, sehe ich es richtig, dass, wenn ich die Beispielgrammatik(Micro-English) von Folie 31 des 2. Foliensatz nehme, und Subject um eine weitere Produktion erweitere, so dass ich folgende Grammatik habe:

Sentence ::= Subject Verb Object.
Subject ::= I | a Noun | the Noun | the Noun Verb
Object ::= me | a Noun | the Noun
Noun ::= cat | mat | rat
Verb ::= like | is | see | sees

diese Grammatik nicht mehr durch einen LL(1) Parser erkannt werden kann?
Ich kann jetzt zwar linksausklammern, und bekomme dann:

Sentence ::= Subject Verb Object.
Subject ::= I | a Noun | the Noun (epsilon | Verb)
Object ::= me | a Noun | the Noun
Noun ::= cat | mat | rat
Verb ::= like | is | see (epsilon | s)

Aber dennoch kann hier, denke ich,
wenn z.B. die Zeichenfolge „the cat sees ths rat“ eingelesen warden soll,
parseSubject nicht mit einem Lookahead von 1 entscheiden,
ob jetzt ein Verb eingelesen werden soll, oder erstmal nichts(epsilon),
denn hier wären ja „the cat sees ths rat“, sowie auch „the cat sees sees ths rat“,
ableitbare Sätze, und um zu entscheiden, ob jetzt schon ein Verb eingelesen werden sollte, oder erst später, müsste man ja erst zum Ende des Wortes gehen und schauen ob nach dem Verb noch ein zweites Verb in der Zeichenkette vorkommt(also bei sees ein lookahead von 4 bzw 5)

ich finde auch keine Umformung der Grammatik,
so dass, der Parser Generator, den ich mir zum Testen mal runtergeladen habe, mir nicht mehr sagt, dass Konflikte auftreten.


Und ich hab auch noch eine zweite Frage,
und zwar zum Beseitigen von Linksrekursion (2. Foliensatz, Seite 25)
Dort wird ja im Beispiel, die Grammatik
N ::= X | N Y
in
N ::= X(Y)*
Überführt.

Was genau soll hier "Links-" Rekursion bedeuten,
dass man immer die Rekursion ersetzt, wenn das Nichtterminalsymbol auf der linken Seite der Produktion auf der rechten Seite als erstes Zeichen (also links) also wie bei N ::= NY,

nun bei N ::= yN|epsilon tritt offenbar kein Konflikt auf,

aber bei N ::= yNy|epsilon (L(N) = {yy, yyyy, …}) tritt ein Konflikt auf,
und ich muss umformen zu N ::= yyN|epsilon, obwohl das N nicht der erste Zeichen auf der rechten Seite ist.

Bei N ::= yNxy|epsilon (L(N) = {yxy, yyxyxy, …}) tritt wiederum kein Konflikt auf.

Also wie genau ist nun das Vorgehen beim Ersetzten von „Linksrekursionen“?

Mit freundlichen Grüßen,
Alexander

Bill
Neuling
Neuling
Beiträge: 6
Registriert: 19. Mär 2009 16:57

Re: Frage zu LL(1) Parser

Beitrag von Bill »

Hallo,

zu Ihrer ersten Frage zunächst einige Anmerkungen:

1. Für das Nicht-Terminal "Verb" haben Sie eine Ausklammerung der Terminale "see" und "sees" vorgenommen. Bitte beachten Sie hier, dass Ausklammerungen nur für Nicht-Terminalsymbole zulässig sind.
2. Die Verwendung von epsilon-Symbolen ist auf theoretischer Ebene durchaus möglich, jedoch wird in den seltensten Fällen praktisch darauf zurückgegriffen. Sie sollten Ihre Grammatik stets derart ausformen, dass epsilon-Transitionen vermieden werden.

Nun zum Kern der Frage: Die von Ihnen genannte Grammatik ist tatsächlich nicht LL(1). Der Grund hierfür ist, dass nach "Subject" sowohl im Nicht-Terminal "Sentence" nach "Verb" übergegangen werden kann, als auch in "Subject". Daher sind mehr Folge-Token notwendig, um die passende Transitionen auswählen zu können.

Tipp: Greifen Sie auf die Regeln von Folie 51 im 2. Block zurück, um zu bewerten, ob eine LL(1)-Grammatik vorliegt.

Zur nächsten Frage: "Was ist Linksrekursion?"

Ihr Beispiel: N ::= X | N Y

Stellen Sie sich die Frage, wie Sie mit dieser Grammatik die Folge "XYY" erkennen würden. Hierbei stellen Sie fest, dass das Nicht-Terminal "N" derart erweitert werden muss, dass es wiederum auf der linken Seite der gewählten Produktion steht (hier: "N Y"). Dies stellt eine linksrekursive Expansion dar.

Die Beseitigung von Linksrekursion verfolgt das Ziel, eine eindeutig interpretierbare Grammatik zu schaffen (Vgl. 62-63, 2. Block). Hierzu ist die Betrachtung der starters-Mengen der einzelnen Nicht-Terminale entscheidend. Führen Sie dies für Ihre Grammatiken durch, stellen Sie fest, dass unter diesem Gesichtspunkt kein Problem vorliegt.

Tipp: Vermeiden Sie auch hier unbedingt epsilon-Symbole.

Antworten

Zurück zu „Archiv“