Seite 1 von 1

auf LL(1) prüfen

Verfasst: 20. Feb 2013 11:54
von jonas
Hi,

wie ist das konkrete "formale" Vorgehen um eine Grammatik auf LL(1) zu prüfen?

Grundsätzlich wollen wir die Grammatik gemäß der Regeln vom lexparse-Foliensaz, Folie 50 prüfen.
Diese Regeln dürfen wir jedoch nur auf "standardisierte" Grammatiken anwenden.(???? stimmt das?)

"Standardisieren" der Grammatik:
  • zusammenfassen gleicher linker Seiten ( A => B und A => C wird zu A => B | C )
  • zusammenfassen gleicher Anfänge ( A => xB | xC wird zu A => x(B|C) )
  • beseitigen von Linksrekursion. (A => BA wird zu A => B+ )

Somit wäre das "formale Vorgehen:
1) Grammtik standardisieren bzw. überprüfen ob sie es bereits ist
2) Regeln von Folie 50 lexparse prüfen



Meine Frage kommt daher, dass ich mir dazu nochmal Aufgabenblatt 1, Aufgabe 1.3 angesehen habe.
In der Musterlösung steht bei Teilaufgabe a) lediglich "ist durch einen LL(1) Parser verarbeitbar".
Hierzu fragte ich mich, wie man die Linksrekursion los wird - ohne das Einführen von einem neuen Nicht-Terminal-Symbol ist das nicht möglich, oder?

Also dann:
A => if (B) E T | D
E => A
B,C,D unverändert

( "| D" muss in A stehen, da A Startsymbol ist und auch direkt D herleitbar sein soll)
Damit hat man dann für E nur eine einzige Produktion, die man direkt ersetzten könnte - dies ist ja aber keine Pflicht (siehe obige Liste) um auf LL(1) zu prüfen.

Intuitiv verstehe ich/sehe ich, dass die Grammatik LL(1) ist - jedoch versuchte ich es mal über den "formalen" Weg um diesen zu üben und finde meine Lösung eher verwirrend.... ist da irgendwo ein (Denk-)Fehler drin?


Grüße,
Jonas

Re: auf LL(1) prüfen

Verfasst: 20. Feb 2013 12:12
von mf1008
Du musst die Grammatik vorher nicht standardisieren.
Wenn du es nicht tust, werden die Zerlegungsregeln aber ein negatives Ergebnis liefern.
In dem Fall kannst du die Regeln anwenden und bekommst ein positives Ergebnis,
da die Grammatik nicht linksrekursiv ist.
Eine Grammatik G ist linksrekursiv,
wenn es eine Folge von Nichtterminalen A1,...,An gibt und eine Folge von Regeln der Grammatik
der Form A1 ::= A2w1,A2 ::= A3w2,...,An ::= A1wn.
Trivialfall: A1 := A1w1

Re: auf LL(1) prüfen

Verfasst: 20. Feb 2013 12:39
von jonas
Ha! Wusste ich doch, dass da ein kolossaler Denkfehler drin war - Danke!

Re: auf LL(1) prüfen

Verfasst: 20. Feb 2013 15:54
von Martek
Noch eine Frage zur Notation:

S ::= (Y (0 | 1) | 2) +
vs
S ::= (Y (0 | 1) | 2) *


Stimmt es dass es beide Varianten gibt, also einmal mit + und einmal mit *, wobei das + mindestens 1 mal, aber beliebig oft und das * einfach nur beliebig oft (auch 0 mal) bedeutet?

Re: auf LL(1) prüfen

Verfasst: 20. Feb 2013 16:03
von mmi1991
@Martek:
AFAIK ja.
Somit ist
S ::= (Y (0 | 1) | 2) +
äquivalent zu
S ::= (Y (0 | 1) | 2) (Y (0 | 1) | 2) *