[CB-Logo]
Compilerbau I WS97/98
Übungen

Blatt 5

Abgabe: Montag, 24.11.1997

(ggf. Lösungen)

[Compilerbau-Homepage]

Aufgabe 1 (20 Pkt)

Programmieren Sie eine nichtdeterministische Analysemethode (bottom-up oder top-down), so daß Sie Programm folgender Funktionalität erhalten:
Eingabe:
Ausgabe:
"akzeptiert mit" und der Parse (die Folge der anzuwendenden Regelnummern), falls das Wort w in G enthalten ist, und "nicht akzeptiert" sonst.
Sie dürfen dabei vereinfachend annnehmen, daß die Nichtterminale der Grammatik Großbuchstaben sind, und die Terminalsymbole durch Kleinbuchstaben, Ziffern und übliche Zeichen (*,/,;, ...) dargestellt werden.
  1. (5P) Geben Sie eine sinnvolle Datenstruktur zur Repräsentation der Produktionen an.
  2. (11P) Implementieren Sie entweder die top-down oder die bottom-up-Analyse mit der oben beschriebenen Ein-/Ausgabe in eine Sprache ihrer Wahl.
    Hinweis: Backtracking läßt sich am einfachsten durch Rekursion realisieren.

  3. (4P) Testen Sie Ihr Programm mit folgenden Eingaben:
    1. G = ({S,A,B,W,R,K}, {a,e,l,k,m,r,t,p,s,u,w,z}, P, S)
      mit P = { S::=ApeK|BR , A::=epsilon|As , B::=tWl , W::=atze|aWe|epsilon , R::=wurm|ApeK , K::=epsilon|Kk }
      und w = tatzelspekk
    2. G = ( {E,D,F}, {a,+,*}, P, E )
      mit P = { E::=E+D|D , D::=D*F|F , F::=(E)|a }
      und w = a+a*a
    Es ist vermutlich einfacher, wenn Sie die EBNF zunächst in BNF-Regeln übersetzen.

Die Abgabe zumindest von Teil (2) und (3) sollte diesmal per Email an lammers bzw. ausendo erfolgen, und zwar als ausführlich kommentierter Sourcecode, der sich am FB15 übersetzen (bzw. bei Interpretersprachen ausführen) läßt.
[Compilerbau-Homepage]
IfI Mathe WWU
Dietmar Lammers
Last modified: Mon Nov 17 13:04:38 MET 1997