URL:
/axel/informatik3_ws0203_blatt5.html
Dieses Übungsblatt ist in Zweiergruppen
zu bearbeiten.
Aufgabe 13 (10 + 3 Programmier Punkte)
Nun soll unser Taschenrechner mittels lex/yacc implementiert
werden. Dazu gebe man per email den yacc source, den lex source (10 Punkte) und
die Dokumentation (3 Punkte) ab. Beim Programm soll z.B. folgendes
funktionieren:
<eingabe> 5.3;
<ausgabe> 5.3
<eingabe> 3+4.0*2^2*7;
<ausgabe> 115.0
<eingabe> (3+4*2)^2*7;
<ausgabe> 847
wer einen Eindruck von der
Funktionsweise gewinnen will, kann das linux Programm bc studieren.
Aufgabe 14 (6 Punkte)
Man konstruiere zu folgendem Automaten A eine Grammatik G mit
L(A) = L(G). A habe das Eingabealphabet
{a,b,c,d,e,f} und die Zustandmenge {1,2,3,4,5}, Startzustand
sei 1 und die Finalmenge sei {4}, die Übergangsfunktion sei gegeben durch
| a | b | c | d | e | f | |
| 1 | 5 | 5 | 5 | 2 | 5 | 5 |
| 2 | 2 | 5 | 4 | 5 | 3 | 5 |
| 3 | 5 | 4 | 5 | 5 | 5 | 1 |
| 4 | 5 | 5 | 4 | 5 | 5 | 5 |
| 5 | 5 | 5 | 5 | 5 | 5 | 5 |
Aufgabe 15 (5+3 Punkte)
a) Sei
G=({X} , {[,],x,#,^}, R, X)
mit
R={ X --> [X#X], X --> [X^X], X-->[X]
, X --> x}
eine Grammatik. Wieviel Ableitungen gibt es für
[[[ x^x ]] # [x#x]]?
Begründung.
b) Wir erweitern die Regelmenge R aus Teil a um die
beiden Regeln:
X] --> [X und [X --> X]
Wieviel Ableitungen gibt es jetzt für das obige Wort? Begründung.
Ergänzung: Eine Ableitung ist ein Weg vom Startsymbol zum Wort, wobei bei
jedem Schritt genau eine Regel der Grammatik angewendet wird. So hat das Wort
aa in der Grammatik S->AA; A->a genau zwei Ableitungen.