Aufgabe 1

Gibt es einen deterministischen 1-Weg Kellerautomaten, der genau die Menge aller Palindrome (über einem Alphabet mit mind. 2 Buchstaben) akzeptiert? Begründung!

Lösung

Nein. Gegenbeispiel: Bei der Analyse des Wörtes abba muß nach Bearbeitung von ab eindeutig festliegen, welcher Analysezustand vorliegt - also was noch akzeptiert wird. Dann kann z.Bsp. nicht mehr abbaabba erkannt werden.

Bemerkung:

Ist die Wortmitte durch ein Sonderzeichen eindeutig markiert, geht das natürlich: Der Automat kellert solange die Eingabe, bis das Sonderzeichen auftritt, dann entfernt er jeweils den stacktop und das identische Eingabezeichen.
Auch der nichtdeterminstische Automat ist ganz einfach, er braucht nur 2 Zustände, die Eingabe auf den Stack bzw. Eingabe und identischen Stacktop löschen realisieren, wobei ersterer immer beide Folgezustände zulässt.

Aufgabe 2

Sei G=({S,A,B},{0,1},P,S) mit P={ S::=ABA|BA, A::=0, B::=B01|eps} gegeben. Berechnen Sie die kanonische Kollektion J2 zu G. Ist J2 konsistent?

Lösung

Benötigt werden die Anfangsmengen Lk(BA)={0, 01}, Lk(A)={0}, Lk(010)={01} und Lk(0101)={01}. Damit ergeben sich

z0= Ik(epsilon)= { [S-> . ABA, ], [S-> . BA, ], [A-> . 0, 0], 
                   [A-> . 0, 01], [B-> . B01, 0], [B-> . , 0], 
                   [B-> . B01, 01], [B-> . , 01] } 
z1 = Ik(A)= { [S->A . BA, ], [B-> . B01, 0], [B-> . , 0], 
              [B-> . B01, 01], [B-> . , 01] }
z2 = Ik(B)= { [S->B . A, ], [B->B . 01, 0], [B->B . 01, 01], 
              [A-> . 0, ]}
z3 = Ik(0)= { [A->0 . , 0], [A->0 . , 01] } 
z4 = Ik(AB)= { [S->AB . A, ], [B->B . 01, 0], [B->B . 01, 01], 
               [A-> . 0, ] } 
z5 = Ik(BA)= { [S->BA . , ] }
z6 = Ik(B0)= { [B->B0 . 1, 0], [B->B0 . 1, 01], [A->0 . , ] }
z7 = Ik(ABA)= { [S->ABA . , ] }
z8 = Ik(AB0)= { [B->B0 . 1, 0], [B->B0 . 1, 01], [A->0 . , ] }
z9 = Ik(B01)= { [B->B01 . , 0], [B->B01 . , 01] } 
z10 = Ik(AB01)= { [B->B01 . , 0], [B->B01 . , 01] } 
     

Jk scheint mir konsistent - das will ich hier nicht einzeln prüfen. Als Beispiel die Ableitung für w=0:

K= z0
look = 0
	Reduktion [B-> . , 0]
	([A-> . 0, 0] nicht anzuwenden, da 0 nicht aus Lk(00)={00} ist.)
K= z0 B
	goto liefert Ik(B)
K = z0 B z2
look = 0
	shifte wegen [B->B . 01, 0]
K = z0 B z2 0
look = epsilon
	goto liefert Ik(B0)
K = z0 B z2 0 z6
	reduziere mit [A->0 . , ]
K = z0 B z2 A
	goto liefert Ik(BA)
K = z0 B z2 A z5
	reduziere mit [S->BA . , ]
K = z0 S

fertig.

Aufgabe 3

Setzen Sie die Grammatik G = ( {E,D,F}, {a,+,*}, P, E )
mit P = { E::=E+D|D , D::=D*F|F , F::=(E)|a } als Eingabe für bison um, und beschreiben (ggf. zeichnen) Sie den erzeugten Analysator.

Hinweis: Option -v erzeugt eine beschreibende Ausgabe

Lösung:

/*
 */

%%

E:    E '+' D
   |  D
;

D:    D '*' F
   |  F
;

F:    '(' E ')'
   | 'a'
;

%%
      

Die Ausgabe ist recht umfangreich und wird hier nicht angegeben. Sie lässt sich entweder in eine Wertetabelle für die Analyseaktionsfunktion umsetzen, oder direkt für die Analyse einsetzen.

Aufgabe 4

Setzen Sie den Teil <Ausdruck>der MML-Grammatik in bison-Eingabe um, und lassen Sie bison eine parser dafür erzeugen. Welche Probleme gibt es? Können Sie sie lösen?

Lösung:

Eine mögliche Eingabe ist

/*
 Bison-Eingabe für den MMS-Grammatikteil <ausdruck>
 */

%%


Ausdruck: logAusdruck | arithAusdruck ;

logAusdruck: 't''r''u''e' | 'f''a''l''s''e' 
   | Variable
   | '(' unaryLogOp logAusdruck ')'
   | '(' logAusdruck binaryLogOp logAusdruck ')'
   | '('arithAusdruck Vergleichsop arithAusdruck ')'
;

arithAusdruck: realZahl | intZahl | Variable
   | '(' arithAusdruck ')'
   | '(' unaryArithOp arithAusdruck ')'
   | '(' arithAusdruck binaryArithOp arithAusdruck ')'
;

Variable: VariablenID
   | VariablenID '[' Indizes ']'
;

Indizes: arithAusdruck
   | arithAusdruck ',' Indizes
;

VariablenID: Identifikator
;

Identifikator: Buchstabe 
   | Buchstabe IdEnde
;

IdEnde: BoZ | BoZ IdEnde | '_' BoZ | BoZ IdEnde
;

Buchstabe: 
     'A' | 'B' | 'C' | 'D' | 'E' | 'F' | 'G' 
   | 'H' | 'I' | 'J' | 'K' | 'L' | 'M'
   | 'N' | 'O' | 'P' | 'Q' | 'R' | 'S' | 'T'
   | 'U' | 'V' | 'W' | 'X' | 'Y' | 'Z'
   | 'a' | 'b' | 'c' | 'd' | 'e' | 'f' | 'g' 
   | 'h' | 'i' | 'j' | 'k' | 'l' | 'm'
   | 'n' | 'o' | 'p' | 'q' | 'r' | 's' | 't'
   | 'u' | 'v' | 'w' | 'x' | 'y' | 'z'

Ziffer: '0' | '1' | '2' | '3' | '4' | '5' 
   | '6' | '7' | '8' | '9' 
;

BoZ: Buchstabe | Ziffer
;

unaryLogOp: 'n''o''t'
;

binaryLogOp: 'a''n''d' | 'o''r'
;

Vergleichsop: '>' | '<' | '<''=' | '=''>' | '=' | '<''>'
;

unaryArithOp: '+' | '-'
;

binaryArithOp: '+' | '-' | '*' | '/'
;

intZahl: Ziffer | Ziffer intZahl
;

realZahl: intZahl '.' intZahl 
   | '.' intZahl | intZahl '.'
;

%%      

Die mit bison -v erzeugte Ausgabe liefert u.a.:

State 1 contains 1 shift/reduce conflict.
State 5 contains 1 shift/reduce conflict.
State 67 contains 1 reduce/reduce conflict.
State 70 contains 2 shift/reduce conflicts.
State 76 contains 1 shift/reduce conflict.
State 91 contains 2 shift/reduce conflicts.
State 119 contains 14 reduce/reduce conflicts.
      

Diese sind auf unterschiedliche Weise zu lösen.