M. Sperber, H. Klaeren Wintersemester 1997/98

Compilerbau I

Blatt 5

Abgabe: 27.11.1997

1. [5 Punkte] Die in der Vorlesung angegebene Grammatik für Mini-Caml ist mehrdeutig -- es gibt z.B. mehrere Syntaxbäume für den Ausdruck 1 + 1 + 1. Geben Sie -- gemäß der Angaben über Präzedenz und Assoziativität im Caml-Handbuch -- eine äquivalente eindeutige Grammatik an.
2. [10 Punkte] Implementieren Sie einen Parser für Mini-Caml, der abstrakte Syntax wie in der Vorlesung beschrieben erzeugt. Benutzen Sie (vorzugsweise) Ihren eigenen Scanner und Parser oder den Scanner in der Struktur Camllex und den Parser aus der Struktur Lr.
3. [10 Punkte] Die Grammatik von Mini-Caml erfaßt nicht alle Korrektheitseigenschaften eines Programms, die für eine weitere Übersetzung notwendig sind. Insbesondere wird nicht überprüft, ob alle verwendeten Bezeichner auch tatsächlich gebunden sind. Implementieren Sie eine entsprechende Analyse mit folgender Signatur:

   val analyze_bound :
         'ident Camlsyn.program
            -> 'ident list
              -> ('ident Camlsyn.program * 'ident list)

   Für analyze_bound e l ist e ein Mini-Caml-Programm und l eine Liste eingebauter Bezeichner. Der Rückgabewert ist ein Tupel aus einem Mini-Caml-Programm, in dem Referenzen Ident i auf eingebaute Bezeichner durch Builtin i ersetzt worden sind, und einer Liste im Programm verwendeter aber nicht gebundener Bezeichner.
4. [5 Punkte] Geben Sie einen ``Un-Parser'' für Mini-Caml an, der aus der abstrakten Syntax wieder ein konkretes Programm produziert. Testen Sie den Un-Parser an einigen repräsentativen Beispielen.

\: \| `=13

 ¯   ¯  exp   \:   literal  
		 \|   ident  
		 \| (   operator-name   )
		 \| (   exp   )
		 \|   exp     exp  
		 \|   prefix-symbol     exp  
		 \|   exp     infix-symbol     exp   
		 \| if   exp   then   exp   else   exp  
		 \|   exp   or   exp  
		 \|   exp   &   exp  
		 \|   exp   ;   exp  
		 \| function   ident   ->   exp  
		 \| raise   exp  
		 \| try   exp   with   ident   ->   exp  
		 \| let rec     let-binding     more-bindings   in   exp  
		 \| [   sequence   ]
  literal   \: ( ) \|   integer-literal   \|   character-literal   \|   string-literal  
  operator-name   \:   infix-symbol   \|   prefix-symbol  
  sequence   \:   empty   \|   exp     sequence-rest  
  sequence-rest   \: ;   exp  
  let-binding   \:   ident     =   exp  
  more-bindings   \: and   let-binding  
  definition   \: let rec     let-binding     more-bindings  
  program   \:   definition  

• Über dieses Dokument ...