Seite 1 von 1

Ist diese Grammatik LL(1)?

Verfasst: 14. Feb 2014 17:03
von mrzb6
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? :|

Re: Ist diese Grammatik LL(1)?

Verfasst: 14. Feb 2014 17:12
von Julian Oppermann
Das ist eine schöne Übungsaufgabe für Ihre Kom­mi­li­to­nen... :)

Re: Ist diese Grammatik LL(1)?

Verfasst: 14. Feb 2014 19:07
von simon.r
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...

Re: Ist diese Grammatik LL(1)?

Verfasst: 14. Feb 2014 19:42
von mahi
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)

Re: Ist diese Grammatik LL(1)?

Verfasst: 15. Feb 2014 00:16
von Julian Oppermann
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\}\)

Re: Ist diese Grammatik LL(1)?

Verfasst: 15. Feb 2014 15:11
von mrzb6
Jetzt hat es sich ja geklärt. Vielen Dank für die Antworten.