Language Processors, Spezialvorlesung, WS2001/2002

General Information

Lectures

(handouts, source code, etc.)

• First introductory lecture : 16 October 2001
• Actual start of course: 11 December 2001
• Final test (oral): to be announced individually
• Source code:
  • lex.ml, lex.mli, lexspec.ml, lexstate.ml, lexstate.mli, regexp-match.ml, regexp.ml, regexp.mli
  • camllex.ml
  • complete-grammar.ml, complete-grammar.mli
  • lambda.ml, ident.ml, listplus.ml
  • lambda-int1.ml, lambda-int-cps.ml, lambda-int-cps-exc.ml
  • lambda-int-cps-closure1.ml, lambda-int-cps-closure2.ml, lambda-int-cps-closure3.ml
  • cps.ml, cps_int.ml
• Script:
  • part1

Exercises

• One exercise sheet every week
• First sheet : 11th of December 2001
• First exercise session : 13th of December 2001
• Material for the exercises:
  • The following is a sample xml file : album.xml
  • Grammar auxiliaries: grammar.ml and grammar.mli
• first sheet, (pdf) at 11.12.01, Return 18.12.01, model solution, (pdf)
• second sheet, (pdf) at 18.12.01, Return 8.1.02, model solution, (pdf)
• third sheet, (pdf) at 8.1.02, Return 15.1.02, model solution, (pdf)
• fourth sheet, (pdf) at 15.1.02, Return 22.1.02, model solution, (pdf)
• fifth sheet, (pdf) at 25.1.02, Return 29.1.02, model solution, (pdf)
• sixth sheet, (pdf) at 30.1.02, Return 5.2.02, model solution, (pdf)
• seventh sheet, (pdf) at 5.2.02, Return 12.2.02, model solution, (pdf)
• eigth sheet, (pdf) at 12.2.02, Return 19.2.02, model solution, (pdf)

Contents

The course Language Processors deals with the recognition, the translation, and the execution of formal languages. It is closely related to compiler construction. It covers the following subjects

• lexical analysis, for decomposing a character stream into lexical units (the lexemes), ocaml-lex;
• syntax analysis, for recovering context-free structure from an input stream, error correction, ocaml-yacc;
• semantic analysis, for enforcing non-context-free requirements, attribute grammars;
• semantic definition, for describing the meaning of a phrase (we rely on interpretive definitions);
• implementation of programming concepts, control structures;
• data representation, implementation of data structurs;
• partial evaluation, for removing interpretation overhead;
• code generation: instruction selection, register allocation;
• further semantic analysis: document validation, type checking.

OCaml

Concrete code in the lecture and the programming exercises will be written in the programming language Objective Caml. It is an object-oriented extension of the ML language dialects and is reminiscent of Haskell, but with imperative features and a call-by-value parameter passing mechanism. It features a.o. polymorphic types, pattern matching, and first-class functions. OCaml is particularly well suited for writing translators and compilers. We will not use the object-oriented extensions.

• The language OCaml This is the main source for information on the language and its tools.
• Solutions and exercises are to be written in Ocaml 3.02, which can be downloaded here. The distribution includes source code for Unix, Win32 and MacOS. Binaries are available for Intel-Linux, MS Windows and MacOS X.
• The OCaml reference manual (online, postscript)
• The OCaml FAQ
• There is an English book on functional programming in OCaml [4] and also German one [8]. However, they are both based on older versions of the language, so not all constructs and features may be valid anymore.
• There is an Introduction into programming with OCaml by John Harrison.
• There is an impressive list of OCaml tools and libraries in the OCaml Hump.

References

 [1]

Alfred V. Aho, Ravi Sethi, and Jeffrey D. Ullman. Compilers Principles, Techniques, and Tools. Addison-Wesley, 1986.

 [2]

Andrew W. Appel. Compiling with Continuations. Cambridge University Press, 1992.

 [3]

Andrew W. Appel. Modern Compiler Implementation in ML. Cambridge University Press, 1998.

 [4]

Guy Cousineau and Michel Mauny. The Functional Approach to Programming. Cambridge University Press, 1998.

 [5]

Christopher W. Fraser and David R. Hanson. A Retargetable C Compiler: Design and Implementation. Benjamin/Cummings, 1995.

 [6]

Rene Leermakers. The Functional Treatment of Parsing. Kluwer Academic Publishers, Boston, 1993.

 [7]

Xavier Leroy. The Objective Caml system release 3.02, Documentation and user's manual. INRIA, France, July 2001. From http://pauillac.inria.fr/caml.

 [8]

Jürgen Wolff von Gudenberg. Algorithmen - Datenstrukturen - Funktionale Programmierung - Eine praktische Einführung mit Caml-Light. Addison-Wesley, 1996.

 [9]

Reinhard Wilhelm and Dieter Maurer. Übersetzerbau -- Theorie, Konstruktion, Generierung -- 2 Auflage. Lehrbuch. Springer-Verlag, Berlin, Heidelberg, 1996.