7. Übungsaufgabe (40/40/40) Punkte)

Abgabetermine:
Auf Grund der grössen Nachfrage verzichte ich auf ein großes Programmierprojekt noch in Compilerbau. Aber ein bißchen müssen wir noch tun. Ich stelle hier alle Aufgaben bis zum Ende des Semesters auf, die Abgabe-Termine entnehmen Sie die Aufstellung. Frühzeitiger Abgabe ist natürlich jederzeit möglich!

• Aufgabe 7.1 : 29.6. bzw. 2.7.
• Aufgaben 7.2 - 7.5: 6.7. bzw. 9.7.
• Aufgaben 7.6 - 7.8 + Zusatzaufgabe: 13.7. bzw. 16.7.

Lernziele:
Recursive-Descent Parser verstehen; Linksrekursion eliminieren üben; Befestigung der Begriffe Syntaxbaum, Rechts- bzw. Linksableitung, Grammatik, FIRST- und FOLLOW-Mengen, Parse

1. (40 Punkte) Implementieren Sie ein Rekursiven-Descent-Parser für die Grammatik! G_expr =
   

   E -> E + T | E - T | T
   T -> T * F | T / F | F
   F -> i | (E)

   Dazu muß natürlich erst mal die Linksrekursion eliminiert werden. Entwickeln Sie geeigneten Testfälle, um Ihr Parser zu testen, und geben Sie einen Testbericht mit ab. Mein Beispiel Parser recdesc.ada können Sie als Grundlage verwenden.

2. (5 Punkte) Entferne die Linksrekursion aus
   

          A -> Ab | cA | Bd | e
          B -> Ba | \epsilon      

3. (15 Punkte) Gegeben sei die Grammatik
   

   	 G =
   	 A -> Ba | bC
   	 B -> d  | eBf
   	 C -> gC | g       

   Welche Zeichenreihen sind in L(G)? Geben Sie Syntaxbäume und Ableitungen für diejenigen an, die dazugehören!

   bg  bffd  bggg  edfa  eedffa  faae  defa

4. (5 Punkte) Bestimmen Sie ein Syntaxbaum für folgende Ableitung:
   

   	 S => AB => BeB => deB => deaBc => deadc       

5. (15 Punkte) Gegeben sie folgender Syntaxbaum: Bestimmen Sie die Rechtsableitung, die Linksableitung und so wie so viel der Grammatik, wie möglich!

                    S
                  / | \
                 /  |  \
                /   |   \
               /    |    \
              A     B     C
             / \   / \   /|\
            B  d  e   f g C g
           / \           / \  
          e   f         A   d  
                        |
                        h
   

6. (10 Punkte) Gegeben sei der Grammatik
   

          S -> aS | SB | d
          B -> Bb | c       

   Zeigen Sie, daß die Grammatik mehrdeutig ist, in den Sie mehrere Syntaxbäume für aadccb angeben!

7. (10 Punkte) Berechnen Sie die FIRST- und FOLLOW-Mengen für
   

          S -> ABC
          A -> a | Cb | \epsilon
          B -> C | dA | \epsilon
          C -> e | f       

8. (20 Punkte) Die Grammatik aus der Vorlesung
   

          S -> if E then S | if E then S else S | a | b
          E -> x | y       

   ist mehrdeutig. Nach Linksfaktorisierung bekommen wir

          S -> if E then SQ | a | b
          E -> x | y
          Q -> else S | \epsilon
   
          FIRST(Q) = {else \epsilon}
          FOLLOW(S) = {$, else}
          FOLLOW(Q) = {$, else}       

   die natülich immer noch mehrdeutig ist, weil FOLLOW(S) und FOLLOW(Q) nicht disjunkt sind. Damit sieht die Tabelle wie folgt aus:

   	if	x	y	then	a	b	else	$
   S	if E then SQ				a	b
   E		x	y
   Q							else S \epsilon	\epsilon

   Wenn wir für [Q, else] else S wählen, behaupte ich, daß der Parser nun korrekt arbeitet, d.h. ein else paßt immer zum nächsten if. Zeigen Sie dies durch Angabe eines Parses und der Syntaxbaum für

   1. if x then if y then a else b
   2. if x then a else if y then b

Ist dies eine gute Idee? Belegen Sie Ihre Begründung mit guten Beispielen!