Erklärung zur EBNF < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | Gegeben ist die folgende, kontext-freie Grammatik in EBNF mit Startsymbol <E>
<E> ::= <T> ("+" <T>)*
<T> ::= <F> ("*" <F>)*
<F> ::= "(" <E> ")" | "x" | "y" | "z"
Geben Sie jeweils einen Ableitungsbaum für die folgenden Wörter:
a) "x + y * z"
b) "x * (y + z)" |
Hallo!
Hier ist eine Aufgabe aus einer Probeklausur:
Ich habe die Sache mit dem Ableitungsbaum glaube ich absolut nicht verstanden. Ich finde auch nirgends Beispiele oder Anleitungen.
Ich kenne nur diese Form für eine Ableitung:
Ich habe ein Bild gemalt und es auf www.imageshack.us hochgeladen. Klickt auf den Link um es zu sehen:
![[]](/images/popup.gif) hier klicken
So, dass ist natürlich nur eine ganz kleine Vereinfachung.
Ein Kommolitone meinte jetzt aber ein Ableitungsbaum sehe irgendwie so aus: <T> -> <F> usw. Wie es genau geht weiss er aber auch nicht.
Kann mir bitte jemand eine der beiden Teilaufgaben mit kleiner Erklärung lösen? Das wäre sehr nett.
Danke!
|
|
| |
|
Hallo nahpets87!
> Gegeben ist die folgende, kontext-freie Grammatik in EBNF
> mit Startsymbol <E>
>
> <E> ::= <T> ("+" <T>)*
> <T> ::= <F> ("*" <F>)*
> <F> ::= "(" <E> ")" | "x" | "y" | "z"
>
> Geben Sie jeweils einen Ableitungsbaum für die folgenden
> Wörter:
>
> a) "x + y * z"
> b) "x * (y + z)"
Das Prinzip dieser Aufgabe ist eigentlich ganz einfach. Du möchtest einfach herausfinden, wie diese Wörter durch diese Grammatik erzeugt werden können, also in welcher Reihenfolge welche Regeln angewendet werden. Ich hoffe, ich erinnere mich noch richtig an die EBNF - "*" bedeutet kein oder mehrmals? Und die Zeichen in Anführungsstrichen werden einfach ausgegeben - so wie Terminalsymbole?
Gucken wir uns also a) an. Als erstes wird "x" erzeugt. Nun können wir uns entweder überlegen, dass wir ja mit dem Startsymbol anfangen müssen, also mit <E>. Oder wir stellen fest, dass das "x" nur in der Formel <F> vorkommt, also müssen wir irgendwie dorthin gelangen.
Wenn wir also bei <E> starten, muss als erstes die Regel <T> angewendet werden. Diese wiederum sagt uns, dass als erstes die Regel <F> angewendet werden muss, und dort finden wir dann unser "x". Damit hätten wir das erste Zeichen "erzeugt". Nun brauchen wir ein "+" - haben aber auch unsere vorherigen Regeln noch nicht abgearbeitet. <F> haben wir komplett abgearbeitet - das ist ja nur eine Veroderung von mehreren Möglichkeiten, und wenn wir eine davon nehmen, können wir nicht mehr nehmen. Aber bei <T> hatten wir ja nur das <F> genommen, dahinter kann ja jetzt noch beliebig oft ("*"<F>) kommen. Wenn ich den Stern richtig deute, heißt das aber auch, dass es nicht kommen muss, und da wir ja ein "+" und kein "*" haben wollen, lassen wir es also weg. Nun also zurück zu <E> - da hatten wir nur das <T> genommen. Dahinter kann jetzt noch beliebig oft ("+"<T>) kommen - das ist toll, denn wir brauchen ja das "+". Also fügen wir das ein und weiter geht's mit dem folgenden <T>. Als nächstes Zeichen müssen wir dann ein y erzeugen - das können wir wieder mit <F> machen - dahin kommen wir von <T> aus wieder über <F> usw.
Das ist etwas anstrengend das aufzuschreiben - hast du das Prinzip verstanden? Ist die Frage überhaupt noch relevant - die Fälligkeit ist bereits abgelaufen...
Viele Grüße
Bastiane
![[cap]](/images/smileys/cap.gif "[cap]")
|
|
|
| |
|
Hi Bastiane, vielen Dank für deine Antwort!
Hmmm...also so ganz hab ich das glaub ich immernoch nicht vestanden.
Also: im Beispiel a)
Ich fange an bei <E> und gehe von dort nach <T>, also haben wir schonmal: <E> -> <T>. Bei T nehme ich F und von diesem F das "x".
Also <E> -> <T> -> <F> -> "x"
Jetzt müsste ich ja eigentlich wieder zurück zu <E>, dort dann wieder <T> nehmen und so weiter und so fort.
Schreib ich dann -> <E> -> "+" <T> -> "*" <F> -> <F> -> ???
Also irgendwie verstehe ich da noch nicht die Logik dahinter! Könntest du bitte die Aufgabe a mal hinschreiben, wie der Ableitungsbaum aussehen muss? Dann könnte ich schonmal versuchen das zu verstehen.
Vielen Dank!
|
|
|
| |
|
Hallo nahpets87!
> Hi Bastiane, vielen Dank für deine Antwort!
>
> Hmmm...also so ganz hab ich das glaub ich immernoch nicht
> vestanden.
>
> Also: im Beispiel a)
>
> Ich fange an bei <E> und gehe von dort nach <T>, also haben
> wir schonmal: <E> -> <T>. Bei T nehme ich F und von diesem
> F das "x".
> Also <E> -> <T> -> <F> -> "x"
> Jetzt müsste ich ja eigentlich wieder zurück zu <E>, dort
> dann wieder <T> nehmen und so weiter und so fort.
>
> Schreib ich dann -> <E> -> "+" <T> -> "*" <F> -> <F> ->
> ???
>
> Also irgendwie verstehe ich da noch nicht die Logik
> dahinter! Könntest du bitte die Aufgabe a mal hinschreiben,
> wie der Ableitungsbaum aussehen muss? Dann könnte ich
> schonmal versuchen das zu verstehen.
Leider hast du hier die Aufgabenstellung nicht mehr zitiert, so dass ich nicht direkt darauf zurückgreifen kann. Erstens weiß ich nicht genau, wie ihr einen Baum aufschreibt, ich würde da <E> als Wurzel hinschreiben und von dort dann zwei Kinder, <T> und +<T> und von dort aus wieder immer weiter Kinder - das lässt sich hier nur schlecht zeichnen.
Ich würde das Ganze so aufschreiben:
<E> -> <T>+<T>
Startsymbol ist E, von dort brauchst du einmal das <T> um das x zu erzeugen und einmal danach auch noch +<T> um das +< zu erzeugen. Das weißt du aber erst, wenn du die Aufgabe so mal durchgegangen bist - es könnte ja theoretisch auch sein, dass du alles nur aus einem T erzeugen kannst und das +<T> gar nicht brauchst. Aber, wie ich ja im vorigen Post schon erläutert hatte, brauchen wir es.
So, nun kannst du jedes <T> einzeln auflösen - wenn du aber eh weißt, welche Regeln du anwenden musst (weil du es ja vor dem Aufschreiben schon mal durchgegangen bist), kannst du jetzt auch beide gleichzeitig auflösen. Du weißt also, dass aus dem ersten T irgendwie das x entstehen muss und aus dem zweiten musst du noch y*z hervorzaubern. Also machen wir es so:
-> <F>+<F>*<F>
-> x+y*z
Ist klar, was ich hier gemacht habe? Eigentlich habe ich es gerade schon erläutert. 
Viele Grüße
Bastiane
|
|
|
|
![[]](http://img228.imageshack.us/img228/3537/unbenanntqa6.jpg){kind=small}
hier klicken
