Lehrstuhl Informatik II   
Sprachen und Beschreibungsstrukturen      
   Home Lehre Sommersemester 12 Vorlesungen Compilerbau I Übung login


Dozent:Alexander Herz
Ort/Zeit:Mittwoch 02.07.014 10:15-11:45 und 16:00-17:30
Beschreibung:    Übung zum Compilerbau

  1. Generating automata from regular expressions

    • Use JFLAP to generate NFA from regexp, make it deterministic, and then minimize it.
    • Consider the inductive Glushkov construction from (page 7) of this paper
    • HA: Generate NFA and DFA for a regexp using Thomson und Glushkov.

  2. Build a little compiler that generates a DFA from a given regexp using berri-sethi

    Please install the following software for the second lab:

    • graphviz: http://www.graphviz.org/
    • a recent JDK (e.g. oracle-6 or openjdk-6)
    • template java source files

    mini-java grammar

    mini-java program +  AST

  3. Build a recursive descent parser and an interpreter for the given calculator grammar

  4. Formally construct LL(1) PDA and look ahead table

    • for (S->eps|aSb) like in the lecture
    • NOTE for 10:15 group: The correct defintion for L1 * L2 = L1 if epsilon not in L1, L1\{epsilon} U L2 otherwise (as given in the lecture, I was missing the "\{epsilon}" part)
    • Homework: Do construction (Item-Keller-Automat, First1 and Follow1 sets and LA-table) for this grammar (can be opened with jflap)
    • Homework: Try to apply the strongly connected components algorithm to solve the constraint system

  5. Construct LR(0)-Automaton, LR(0) and SLR parsers

  6. Construct LR(1)-Automaton & Parse Table, Start construction of mini-c parser using ANTLR

    • PLEASE INSTALL THIS ON YOUR SYSTEM (antlr3.1.1 and antlrworks1.4+Main.java)
    • expr.g
    • Homework:

  7. MINI-TEST1 (06.06.12)

    • You have to be present at this lab unit to participate at the test (and possibly earn the bonus).
  8. Discussion of the Mini-Test and implementation of scope analysis (as defined in the lecture using a visitor)

    • Homework: write pass (visitor impl) that dumps the parser generated AST as a .dot file (graph)

  9. Type Checking (implemented as seperate vistor bu reusing the ScopedCommonTrree class)

    • Homework: finish type analysis, add type 'bool' to grammar and type analysis (so that vars of type bool can be declared) and fix the interpreter to respect scoping
  10. rcma assembly hacking

    • install the rcma assembler + VM (requires java)
    • download the rcma instruction set
    • Homwork:
      • write visitor that calculates mapping from global var decls to registers
      • write visitor to emit rcma assembly
      • test your emitter with a small program that calcs the nth fib(n read from user) and run it using the rcma vm
      • (fully fledged compiler that creates executable rcma assmbler and interprets the program as well - includes some refactoring of the visitors etc)
  11. Procedures (add to grammar, type check, register alloc and code emit)

    • bugfixed RCMA
    • template for procedures
    • note: the solution does not adhere 100% to the rcma codegen (it utilizes R0 for calculations and emits an enter 100 instead of the exactly required stack space)

  12. LAST LAB

TUM - Lehrstuhl Informatik II (Sprachen und Beschreibungsstrukturen) Thanks: Tango and TinyMCE     Generationszeit: 10 ms