LL(0)-Grammatik

Talaron
Mausschubser
Mausschubser
Beiträge: 85
Registriert: 26. Apr 2012 11:34

LL(0)-Grammatik

Beitrag von Talaron » 20. Feb 2014 16:25

Hallo,

da bei uns nach der entsprechenden Klausuraufgabe doch eine kleine Diskussion aufgekommen ist: Welche Antwort war denn auf die Frage nach der Anzahl der Worte der LL(0)-Grammatik beabsichtigt? Im Internet findet man relativ logisch klingende Erklärungen, die auf null, eines oder unendlich verschiedene viele Worte passen würden...

Danke schonmal!

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

Re: LL(0)-Grammatik

Beitrag von Julian Oppermann » 20. Feb 2014 16:32

Ein Wort, weil die Grammatik keine Alternativen enthalten kann (diese müsste man mit 0 Zeichen Lookahead unterscheiden können).

LukasBanana
Erstie
Erstie
Beiträge: 19
Registriert: 25. Okt 2010 11:04

Re: LL(0)-Grammatik

Beitrag von LukasBanana » 21. Feb 2014 11:34

Ich hatte da einen Parser im Kopf, der Tokens nur akzeptieren kann (oder nicht -> dann gibt's einen Fehler)
und keine Unterscheidung machen kann (weil Lookahead von 0):

Code: Alles auswählen

// LL(1):
void parseS() {
    if (currentToken == X)
        parseX();
    else if (currentToken == Y)
        parseY();
    else
        error();
}

// LL(0):
void parseS() {
    parseX();
    parseY();
}
EDIT:
Als ich gerade über die Sinnhaftigkeit einer LL(0) Grammatik nachdachte, ist mir noch eine Frage dazu eingefallen:
bezieht sich das LL(k) nur auf die Grammatik des Parsers oder bezieht es die Grammatik des Scanners mit ein?
Bei einem "Lookahead" von 1 ( also LL(1) ) denke ich nämlich erst mal nur an "currentToken", also nur den Lookahead des Parsers, aber nicht des Scanners (currentChar).

Benutzeravatar
Cpro
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 109
Registriert: 16. Okt 2010 22:13
Wohnort: Darmstadt

Re: LL(0)-Grammatik

Beitrag von Cpro » 21. Feb 2014 13:37

Ich glaube die Fragestellung war sehr allgemein gehalten: "Wie viele Wörter kann eine LL(0)-Grammatik enthalten" (kein Zitat!).

Du kennst die Grammatik, du kannst errechnen, wie viele k Schritte du benötigst, um ein beliebiges Wort - welches von dieser gebildet wird - vorhersagen zu können.
Sei es nun die Grammatik (S, a) mit S -> a, so kannst du ohne den Zeichenstrom zu kennen direkt vorhersagen, dass ein Wort der Grammatik immer "a" ist.
Gleiches gilt auch beim leeren Wort: S -> epsilon - das leere Wort ist auch ein Wort. Eine Grammatik, die keine Terminalsymbole enthält, ist keine Grammatik, weil S -> {} nie irgendwo definiert wurde (tauchte auch in der Tat in noch keinem Fach auf bisher).

Antworten

Zurück zu „Archiv“