Ist diese Grammatik LL(1)?

mrzb6
Mausschubser
Mausschubser
Beiträge: 54
Registriert: 4. Okt 2010 21:50
Wohnort: Darmstadt

Ist diese Grammatik LL(1)?

Beitrag von mrzb6 » 14. Feb 2014 17:03

Man stelle sich folgende Grammatik vor:

\(\begin{align*}S ::=& XY \\X ::=& \varepsilon |a \\Y ::=& a\end{align*}\)

Es ist weder eine Linksrekursion vorhanden, noch besteht eine Möglichkeit zum Linksausklammern. Die Zerlegungsregeln von Foliensatz 2, Folie 50 treffen auch nicht zu. Theoretisch wäre die Grammatik damit LL(1). Die zwei Herleitungsmöglichkeiten beim Einlesen von \(a\) sind aber trotzdem nicht mit einem Lookahead von 1 zu unterscheiden.

Ist die Grammatik nun LL(1) oder nicht? :|
Zuletzt geändert von mrzb6 am 14. Feb 2014 17:44, insgesamt 1-mal geändert.

Julian Oppermann
Mausschubser
Mausschubser
Beiträge: 88
Registriert: 3. Mai 2013 19:32

Re: Ist diese Grammatik LL(1)?

Beitrag von Julian Oppermann » 14. Feb 2014 17:12

Das ist eine schöne Übungsaufgabe für Ihre Kom­mi­li­to­nen... :)

simon.r
Mausschubser
Mausschubser
Beiträge: 59
Registriert: 4. Okt 2010 16:13

Re: Ist diese Grammatik LL(1)?

Beitrag von simon.r » 14. Feb 2014 19:07

Da die Grammatik nicht direkt gegen keine uns vorgestellte Regel verstößt, man aber bei der Implementierung der parseX Methode scheitern würde, habe ich nach weiteren Regeln für LL Parser/Grammatiken gesucht. Auf der englischen Wikipedia werden nur zwei entscheidende Grammatikkonflikte genannt. Letzterer scheint hier zu zutreffen und besagt, dass die starters und die follow Menge einer Regel disjunkt sein müssen. Für den konkreten Fall:

\(\begin{align*} \text{starters}[[\varepsilon|a]] \cap \text{follow}[[\varepsilon|a]] =& \{\varepsilon,a\} \cap \{a\} = \{a\} \ne \emptyset \end{align*}\)

Demnach wäre die Grammatik nicht in LL(1), was anhand der in den Folien direkt angegebenen Regeln nicht direkt ersichtlich ist, da Großbuchstaben wie X oder Y normalerweise für Nicht-Terminale reserviert sind...

mahi
Mausschubser
Mausschubser
Beiträge: 55
Registriert: 5. Aug 2012 14:06

Re: Ist diese Grammatik LL(1)?

Beitrag von mahi » 14. Feb 2014 19:42

die 2.Regel im Foliensatz 2 Folie 50 ist ja nicht erfüllt:

starters[X] = {a}

starters[Y] = {a}

follow[X|Y] = {a}

=> starters[X] und (starters[Y] oder follow[X|Y]) != leere Menge
=> nicht LL(1)

Julian Oppermann
Mausschubser
Mausschubser
Beiträge: 88
Registriert: 3. Mai 2013 19:32

Re: Ist diese Grammatik LL(1)?

Beitrag von Julian Oppermann » 15. Feb 2014 00:16

simon.r hat geschrieben: Demnach wäre die Grammatik nicht in LL(1), was anhand der in den Folien direkt angegebenen Regeln nicht direkt ersichtlich ist, da Großbuchstaben wie X oder Y normalerweise für Nicht-Terminale reserviert sind...
Ah ok, die Bezeichnungen auf der Folie sind etwas verwirrend. Dort meinen X und Y jeweils eine Alternative einer Produktion, und X|Y meint die gesamte rechte Seite der Produktion. Wir haben in der Musterlösung zu Aufgabe 1.5 versucht, die Prüfung auf die LL-Eigenschaft noch etwas genauer zu erklären. Schauen Sie doch bitte da mal hinein.

Bei der Grammatik von mrzb6 ist die LL(1)-Eigenschaft wie Sie richtig vermutet haben nicht erfüllt.

Die Produktion \(X ::= \varepsilon~|~a\) enthält eine Alternative und muss geprüft werden. Da aus Alternative 1 (das \(\varepsilon\)) eben dieses abgeleitet werden kann, trifft Regel 2 von den Folien zu.

Wir betrachten \((starters[[\varepsilon]] \cup follow[[\varepsilon~|~a]]) \cap starters[[a]] = \{a\} \neq \emptyset\) und sehen, dass die Regel verletzt ist, die Grammatik also nicht LL(1) ist. Hier ist \(follow[[\varepsilon~|~a]] = starters[[Y]] = \{a\}\)

mrzb6
Mausschubser
Mausschubser
Beiträge: 54
Registriert: 4. Okt 2010 21:50
Wohnort: Darmstadt

Re: Ist diese Grammatik LL(1)?

Beitrag von mrzb6 » 15. Feb 2014 15:11

Jetzt hat es sich ja geklärt. Vielen Dank für die Antworten.

Antworten

Zurück zu „Archiv“