auf LL(1) prüfen

jonas
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 177
Registriert: 5. Okt 2008 21:35
Wohnort: DA

auf LL(1) prüfen

Beitrag von jonas » 20. Feb 2013 11:54

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

mf1008
Erstie
Erstie
Beiträge: 15
Registriert: 19. Okt 2008 18:05

Re: auf LL(1) prüfen

Beitrag von mf1008 » 20. Feb 2013 12:12

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

jonas
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 177
Registriert: 5. Okt 2008 21:35
Wohnort: DA

Re: auf LL(1) prüfen

Beitrag von jonas » 20. Feb 2013 12:39

Ha! Wusste ich doch, dass da ein kolossaler Denkfehler drin war - Danke!

Martek
Windoof-User
Windoof-User
Beiträge: 35
Registriert: 28. Sep 2009 15:48
Wohnort: Darmstadt
Kontaktdaten:

Re: auf LL(1) prüfen

Beitrag von Martek » 20. Feb 2013 15:54

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?
Wer aufgehört hat besser zu werden, der hat aufgehört gut zu sein!

Benutzeravatar
mmi1991
Computerversteher
Computerversteher
Beiträge: 349
Registriert: 20. Okt 2011 18:46
Wohnort: Hattersheim

Re: auf LL(1) prüfen

Beitrag von mmi1991 » 20. Feb 2013 16:03

@Martek:
AFAIK ja.
Somit ist
S ::= (Y (0 | 1) | 2) +
äquivalent zu
S ::= (Y (0 | 1) | 2) (Y (0 | 1) | 2) *
Ophasentutor SoSe 2014, WiSe 2015/16
Alle Angaben wie immer ohne Gewähr

Antworten

Zurück zu „Archiv“