Aufgabe 1

Berechen Sie für die Grammatiken aus Blatt 6, Aufgabe 2 die Goto- und die Analyseaktionstabelle. Analysieren Sie damit die Wörter

1. 010
2. 0101010

Lösung:

Nr.	Gamma	goto					f
		0	1	S	A	B	eps	0	1	00	01	10	11
0	eps	3			1	2		B->eps		S	B->eps
1	A					4		b->eps			B->eps
2	B	6			5			S			S
3	0							A->0			A->0
4	AB	8			7			S			S
5	BA						S->BA
6	B0		9				A->0					S
7	ABA						S->ABA
8	AB0		9				A->0					S
9	B01							B->B01			B->B01

Nun die Ableitung, wir beschränken uns hier auf 010:

1. K=Z0, L=01 f=>(B->eps)
2. K=Z0 B, L=01, g=>
3. K=Z0 B Z2, L=01, f=>
4. K=Z0 B Z2 0, L=10, g=>
5. K=Z0 B Z2 0 Z6, L=10, f=>
6. K=Z0 B Z2 0 Z6 1, L=0, g=>
7. K=Z0 B Z2 0 Z6 1 Z9, L=0, f=>(B->B01)
8. K=Z0 B, L=0, g=>
9. K=Z0 B Z2, L=0, f=>
10. K=Z0 B Z2 0, L=eps, g=>
11. K=Z0 B Z2 0 Z6, L=eps, f=>(A->0)
12. K=Z0 B Z2 A, L=eps, g=>
13. K=Z0 B Z2 A Z5, L=eps, f=>(S->BA)
14. K=Z0 S, L=eps
15. fertig, 010 wird akzeptiert.

Aufgabe 2

Gegeben seien die kontextfreie Grammatik G = ({s,x,e,a,p},{REAL,INT,VAR,+,-,*,/,(,),=},P,s) mit P = { s::=x, x::= x=e|e, e::= e+p|e-p|p, p::= p*a|p/p|a, a::= REAL|INT|VAR|(e) } und die folgenden Ausdrücke:

1. ( rx - rm ) / rs * 2.0 * rpi
2. 1.14 - rs / (ra * rb ) + (1.0 - rs ) / 2
3. ( ia + ib ) * ( ia + ib ) = 2

1. Normalisieren Sie die Ausdrücke
2. Führen Sie eine Typbestimmung der Teilausdrücke anhand der Kellermethode durch
3. Erzeugen Sie eine Folge von Einadreß-Befehlen des vonNeumann-Simulators zur Berechung der drei Terme

   Dokumentation des Simulators

   
   

Lösung:

1. 1. (((( rx - rm ) / rs) * 2.0) * rpi)
   2. ((1.14 - (rs / (ra * rb ))) + ((1.0 - rs ) / 2))
   3. ((( ia + ib ) * ( ia + ib )) = 2)
2. Das Verfahren ist im Script erklärt, jedoch muß der Eintrag an der Stelle (real+-*/ , real) statt E(real lauten Ereal. Wir erhalten:
   1. real
   2. real
   3. boolean
3. (Wir machen das nur beispielhaft am ersten Term)

   verb. Ausdruck	Hilfsausdruck	freie Hilfsvariablen
   ((((rx-rm)/rs)*2.0)*rpi)		F={h1,h2,...}
   (((h1/rs)*2.0)*rpi)	h1:=(rx-rm)	F={h2,h3,...}
   ((h2*2.0)*rpi)	h2:=(h1/rs)	F={h1,h3,h4,...}
   (h1*rpi)	h1:=(h2*2.0)	F={h2,h3,...}
   h2	h2:=(h1*rpi)	F={h1,h3,h4...}

   Nun können wir den Code erzeugen. Wir gehen mal davon aus, das der Code im Hauptprogramm steht, also das statische Niveau der Hilfsvariablen 0 ist, und der Platz für Hilfsvariablen im FSB des Hauptprogramms an der Relativadresse 11 beginnt, die Variblen und die Konstante 2.0 ab Relativadresse 6 stehen (also rx->6, rm->7, rs->8, 2.0->9, rpi->10). Dann ergibt sich folgende Code:

   Code	Kommentar
   LDA 6,0	rx in den Akkumulator
   FSB 7,0	rm abziehen
   STA 11,0	in h1 speichern
   LDA 11,0	h1 laden (eingentl. überflüssig)
   FDV 8,0	durch rs teilen
   STA 12,0	in h2 speichern
   LDA 12,0	h2 laden
   FMU 9,0	2.0 multipliziern. (Wäre das nicht im Konstantenspeicher abgelegt, hätten wir hier erst FNA 2.0 verwenden müssen)
   STA 11,0	Speichern in h1
   LDA 11,0	h1 laden
   FMU 10,0	mal rpi
   STA 12,0	in h2 speichern. Fertig.