Programmiersprachen und Übersetzer (LL(1)-Grammatik) Übung 4

Noryne

Trainee

Posts: 36

Date of registration: Oct 8th 2007

Location: Wunstorf

1

Monday, May 11th 2009, 8:12am

Hallo alle zusammen!

Hätte da ne kleine Frage zum 4. Übungsblatt Aufgabe 2a).

Soweit ich das verstanden habe kann eine Grammatik mit Produktionen, welche den gleichen Präfix enthalten keine Grammatik vom Typ LL(1) sein. Deshalb muss man sie ja auch zuerst umformen.
Wenn ich sie aber erst umgeformt habe, dann hat sie ja keine Produktionen mehr mit gleichem Präfix.

Wie soll ich also dann die Aufgabe verstehen? Gibt es da einen Sonderfall der mir einfach nicht auffallen will? Ist die Frage unglücklich gestellt und wir sollen einfach nur eine Grammatik angeben und dann umformen?

Habe bisher in alle meinen Quellen noch nie irgendeine Sonderfall-Grammatik gesehen welche die LL(1)-Bedingung trotzdem erfüllt. Vielleicht übersehe ich grad aber auch etwas ziemlich Simples, da die Aufgabe ja nur einen Punkt zu geben scheint und von daher ja nicht sehr schwer sein dürfte...

mfg
Noryne

Go to the top of the page

SunshineSunny

Sonnenscheinchen auf'm Campus

Posts: 1,071

2

Monday, May 11th 2009, 8:34am

Präfix heißt ja das Ende der Produktionen ist gleich. Nicht aber das erste Zeichen!

Du sollst nur die Grammatik angeben und dabei nichts verändern.
Wichtig ist nur das keine Linksrekursiven Produktionen enthalten sind.

Manche Männer bemühen sich lebenslang, das Wesen einer Frau zu verstehen.
Andere befassen sich mit weniger schwierigen Dingen z.B. der Relativitätstheorie.

Go to the top of the page

Helicase

Trainee

Posts: 85

Date of registration: Oct 3rd 2006

3

Monday, May 11th 2009, 9:11am

Ich glaub Sandra du hast das einfach verdreht..

Gemeinsames Präfix heißt ja ganz einfach, sie fangen mit dem gleichen an

A -> ab
B -> ac

Hier ist LL1 nicht erfüllt, weil man nach lesen des ersten Zeichens nicht weiß ob man A oder B nehmen soll (man bräucht das 2. Zeichen zum entscheiden). Es gibt aber eine mögliche Grammatik, bei der du es trotzdem hinkriegst, dass die beiden Produktionen mit dem selben anfangen und trotzdem LL1 sind. Ich saß damals auch lange dran und wie immer ist die Antwort dann natürlich total einfach

.
Ich hatte damals die Grammatik und First von meinen Produktionen angegeben das "reichte" für die Korrekte bearbeitung. Umformen musste man nichts.

Go to the top of the page

SunshineSunny

Sonnenscheinchen auf'm Campus

Posts: 1,071

4

Monday, May 11th 2009, 9:18am

ja ja präfix und Suffix... wie rechts und links

Manche Männer bemühen sich lebenslang, das Wesen einer Frau zu verstehen.
Andere befassen sich mit weniger schwierigen Dingen z.B. der Relativitätstheorie.

Go to the top of the page

Noryne

Trainee

Posts: 36

Date of registration: Oct 8th 2007

Location: Wunstorf

5

Monday, May 11th 2009, 9:24am

hatte mich schon gewundert im ersten moment @ Sunny

hm ja denke ich habe die Lösung jetzt, wenn man nen bisschen nachdenkt ist sie wirklich sehr simpel :thumbup:

mfg
Noryne

Go to the top of the page

0x17

Junior Schreiberling

Posts: 215

6

Monday, May 11th 2009, 5:45pm

Quoted from "Helicase"

Gemeinsames Präfix heißt ja ganz einfach, sie fangen mit dem gleichen an

A -> ab
B -> ac

Hier ist LL1 nicht erfüllt, weil man nach lesen des ersten Zeichens nicht weiß ob man A oder B nehmen soll (man bräucht das 2. Zeichen zum entscheiden).

Vorsicht: Laut Skript liegt ein gemeinsames Präfix nur vor, wenn es verschiedene Produktionen mit gleicher linken Seite gibt, deren rechte Seite gleiches Anfangsstück besitzen!

In deinem Beispiel wäre LL1 also sehr wohl erfüllt. Wäre andernfalls auch arg verwunderlich, da es jeweils nur eine rechte Seite gibt und daher alle Bedingungen für LL1 automatisch erfüllt sind.

Go to the top of the page

Soul

Trainee

Posts: 79

Date of registration: Oct 4th 2007

7

Monday, May 11th 2009, 6:31pm

Mal was anderes zu dieser Übung.
Bei 1. b) wird von einer G2 Grammatik gesprochen, welche ist damit gemeint?
Ich seh nur die G1 Grammatik

Go to the top of the page

0x17

Junior Schreiberling

Posts: 215

8

Monday, May 11th 2009, 6:41pm

Quoted from "Soul"

Mal was anderes zu dieser Übung.
Bei 1. b) wird von einer G2 Grammatik gesprochen, welche ist damit gemeint?
Ich seh nur die G1 Grammatik

Ja der Übungszettel wurde kurz nach der Veröffentlichung mehrfach revidiert. Lad dir doch hier die aktuelle Version runter.