Prof. Dr. R. Laue
Dr. A. Kohnert                                                                                                                                             SS 2005
Compilerbau und formale Sprachen
                                Übungsblatt 7
                              

URL:         /axel/compiler_ss05_blatt7.html

 Dieses Blatt wird am 1.6.2005 besprochen.



Aufgabe 17 epsilon - freie Grammatik
Eine Grammatik heisst epsilon -frei, falls sie keine Regel der Form A->epsilon enthält. Schreiben Sie einen Algorithmus, der eine Grammatik in eine äquivalente epsilon -freie überführt. Äquivalent bedeutet: beide Grammatiken haben die gleiche Sprache. Geben Sie ein instruktives Beispiel zur Wirkungsweise Ihres Algorithmus.


Aufgabe 18
Erweitern Sie das lex Programm und yacc Programm (abgabe von a18.l und a18.y per email bis 31.5.05. 24.00 Uhr an a18ss05 at btm2x3.mat.uni-bayreuth.de)
um Dezimalzahlen. Folgende Beispielsitzung sollte funktionieren:

<eingabe>      -53.0+7%2;
<ausgabe>     -52.0
<eingabe>   7-4-3;
<ausgabe>  0
<eingabe>   7-(4-3.0);
<ausgabe>  6.0

<eingabe>       3+4*2^2*7;
<ausgabe>      115
<eingabe>  
(3+4*2)^2*7;
<ausgabe>   847
<eingabe>   4^0.5;
<ausgabe>  2.0


Aufgabe 19 zykelfreie Grammatik
Eine Grammatik heisst zykelfrei, falls sie keine Ableitung der Form A==>A gibt (A ist irgendein Nichtterminalsymbol). Schreiben Sie einen Algorithmus, der eine Grammatik in eine äquivalente zykelfreie überführt. Testen Sie den Algorithmus an der  Grammatik  mit der einzigen Regel  S-->SS|(S)|epsilon