Compilerbau Übungen

Aufgabe 1

Gegeben sei die durch die Produktionen P={ S::=AS|b, A::=SA|a } festgelegte Grammatik. Konstruieren Sie die Parse-Tabellen nach dem Algorithmus von Cocke-Kasami-Younger zu folgenden Wörtern:

bbaab
ababab
aabba

Ggf. programmieren Sie den Algorithmus dazu.

Lösung:

  Wort bbaab ist in L(G)
  Matrix:
  (0,1)=S (0,2)=  (0,3)=A (0,4)=  (0,5)=S 
          (1,2)=S (1,3)=A (1,4)=  (1,5)=S 
                  (2,3)=A (2,4)=  (2,5)=S 
                          (3,4)=A (3,5)=S 
                                  (4,5)=S

   
   Wort ababab ist in L(G)
   Matrix:
   (0,1)=A (0,2)=S (0,3)=A (0,4)=S (0,5)=A (0,6)=S 
           (1,2)=S (1,3)=A (1,4)=S (1,5)=A (1,6)=S 
                   (2,3)=A (2,4)=S (2,5)=A (2,6)=S 
                           (3,4)=S (3,5)=A (3,6)=S 
                                   (4,5)=A (4,6)=S 
                                           (5,6)=S

 
   Wort aabba ist nicht in L(G)
   Matrix:
   (0,1)=A (0,2)=  (0,3)=S (0,4)=  (0,5)=A 
           (1,2)=A (1,3)=S (1,4)=  (1,5)=A 
                   (2,3)=S (2,4)=  (2,5)=A 
                           (3,4)=S (3,5)=A 
                                   (4,5)=A

Leider tritt bei den Beispielen nicht der Fall auf, das mehr als ein Nichtterminal in einer Zelle steht, das kann aber durchaus vorkommen!

Aufgabe 2

Die Schlüsselwörter der Sprache MMS (lt. Anhang Script CB-I) sind program, real, proc, od, begin, boolean, goto, if, end, array, while, else, integer, of, do und fi.
Boolsche Operatoren sind not, or und not und auch true und false sind (0-stellige) boolesche Operatoren.

Suchen Sie sich aus den Schlüsselwörtern 4 heraus, geben Sie für diese 4 einen gemeinsamen regulären Ausdruck an, und einen Automaten, der genau diese vier Wörter erkennt.
Geben Sie die vier Schlüsselwörter und die boolschen Operatoren dann in flex ein, und lassen Sie von flex einen erkennenden Automaten als Programm generieren, der entsprechend KEYWORD, LOG_OP_NULL, LOG_OP_UNARY und LOG_OP_BIANRY erkennt, und beurteilen Sie den Automaten.

Hinweis: man flex, Option -T

Lösung

Wir wählen if, fi, do und od. Ein einfacher regulärer Ausdruck der alle erkennt wäre ((((if)+(fi))+(do))+(od)). Ein entsprechender Automat mit Startzustand q0, endzustand q5, in Tabellenform angegeben:

Zus/Inp	i	f	o	d
q0	q1	q2	q3	q4
q1	-	q5	-	-
q2	q5	-	-	-
q3	-	-	-	q5
q4	-	-	q5	-
q5	-	-	-	-

flex-Eingabe:
```
	  
%%
if|fi|od|do	printf("KEYWORD");
true|false	printf("LOG_OP_NULL");
not		printf("LOG_OP_UNARY");
and|or		printf("LOG_OP_BINARY");
	  
```
Die flex-Ausgabe, selbst wenn man sich auf die erste Zeile als Eingabe beschränkt, ist etwas länglich und wird hier nicht zitiert. Die Angabe der Endzustände dort ist mir unklar, und es wird ein weiterer Zustand eingeführt, der offenbar unnötig ist. Allerdings ist der generierte Automat vollständig.

CB-I im WS99/00

Blatt 5

Aufgabe 1

Lösung:

Aufgabe 2

Lösung