Chomsky Normalform < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 17:27 Do 20.05.2010 | | Autor: | angelnc |
| Aufgabe | Der Parser eines Compilers arbeitet üblicherweise in zwei Schritten. Zunächst wird als Vorverarbeitung die Eingabe in eine Folge sogenannter > Tokens < zerlegt. Die eigentliche Syntaxanalyse arbeitet dann mit Wörtern über dem Alphabet, welches aus diesen Tokens besteht.
Beispielsweise könnte die Eingabe
fac n := if n = 0 then 1 else n * fac (n-1);
in die Token-Folge
id id := if id op num then num else id op id ( id op id ) ;
konvertiert werden. Wir betrachten das Tokenalphabet
Σ := { id, op, num, if , then, else, :=, (, ), ; }
und die Grammatik G = (Σ, V, P, S) mit Produktionen
S → D | D S
D → id A := E ;
A → ε | id A
E → id | num | ( E ) | E op E | id P | if E then E else E
P → E | E P
(a) Transformieren Sie G in Chomsky-Normalform und bestimmen Sie mit Hilfe des CYK-Algorithmus, ob das Wort
id id := id ( id op id op num ) ;
zu L(G) gehört.
(b) Konstruieren Sie einen Kellerautomaten, welcher L(G) erkennt. |
Hallo,
ich habe versucht die Aufgabe zu lösen und auch eine Grammatik in Chomsky-Normalform gefunden.
Ich bin mir aber nicht sicher, ob ich das richtig gemacht habe.
Meine Chomsky-Normalform:
S → DS
D → DD | id | := | DE | ε
E → DD | num | EG | GE
G → GE | ( | ) | op | if | then | else
Ich habe das Gefühl, dass man mit der Chomsky-Normalform, die ich gemacht habe, mehr Wörter produzieren kann, als mit G, deshalb hätte ich gerne eine Rückmeldung.
Ich denke, wenn ich die Chomsky-Normalform habe, schaffe ich den Rest der Aufgabe alleine.
Vielen Dank schon mal.
Gruß
angelnc
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
edit:
Ich habe jetzt einen neuen Lösungsversuch.
Um nicht alles abtippen zu müssen, hänge ich ihn als Dateianhang an.
Dateianhänge:
Anhang Nr. 1 (Typ: jpg) [nicht öffentlich]
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:20 Mo 24.05.2010 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
