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

Übung Compilerbau

Dozent:Vesal Vojdani
Ort/Zeit:MI 02.07.034 Mi 12:15 und 16:00
Beschreibung:    Hier werden wir einen kleinen Compiler für C bauen, und Euch ein bisschen theoretischer fordern/foltern.

Syllabus & Supplementary Material

  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.
  2. Regexp to DFA conversion.
    • Computing the empty, first, next and last sets to get (implicitly) an NFA.
    • Translating to DFA using the subset construction (lectures) & the slightly more direct method (dragon book).
    • Play around with the Java implementation: bs.zip. (BS as in Berry-Sethi.)  There is a README file; read it!
    • The solution is here: RegexpVisitorSol.java
  3. Practical Stuff: Using Lexer Generators.
    • Please install jflex on your machine. For debian-based distributions, simply sudo apt-get install jflex.
    • We will follow the Victor Eijkhout's Lex tutorial. The syntax of JFlex is slightly different, so you may need to consult the JFlex manual if you do this at home.
    • The exercise material is available here: jflex.zip.
  4. Intro to parsing theory & LL(1) parsing.
    • We will first look at pushdown automata using the JFLAP tool.
    • The sample grammars are available in this archive: grammars.zip.
    • Take the simple.jff grammar and "convert CFG to PDA (LR)". The rules for shift reduce parsers are not yet explained, so focus more on how the automaton applies these rules.
    • Convert the same grammar to PDA (LL). Here, pay attention to how these rules correspond what was presented in the lecture. The tool does not use items but pushes non-terminal symbols immediately on the stack. (Think of this as inlining function calls!)
    • Now, build the LL(1) parse table! For this we need to compute first and follow sets. We will do this for the slightly more complicated leftfac.jff grammar as well.
  5. Practical Stuff: Hand-written & Generated LL parsers.
    • We begin with hand-written recursive descent parsers based on LL(1) grammars. Then, we look at how such code can be automatically generated.
    • The exercise material is here: parsers.zip. See the readme file.
    • Play around with the ANTLRWorks. Then, have a look at the example project, antlr.zip, to see how to integerate our own syntax tree classes. For this, you should download the complete jar and put it in the same directory as the source files; now if you do "make run", it produce our familiar dot-files.
  6. Deterministic bottom-up parsing.
    • The theoretical exercsises with solutions: theory.pdf.
    • Try each of these grammars with JFLAP. Since it only supports SLR parsing, it cannot deal with the last one, but you can obviously do the LALR(1) by filling in the table yourself.
  7. Focus on practical Frontend-Engineering: Inside Javac and CUP2.
    • Download the Javac-Sources from Openjdk
      and implement C-style instant object declaration :-)
    • Download the CUP2 Task and
      • Load the CUP2-Project into Netbeans
      • Explore the docs/MiniJavaSample Example
      • fix test/edu/tum/cup2/generator/LR0GeneratorTest.java and subsequent problems :-)
  8. Parsing MiniC.
    • We focus on parsing the type declarations for pointers and functions. You may find this tutorial (in German) helpful about C pointers.
    • We start from the following stubs: minic.zip. You may develop it in 3 steps; the output folder shows what the expected output should be. The only files that need to be changed are Parser.cup, Declaration.java, Type.java, TPtr.java, TPrim.java, and TFun.java.
    • The solutions are here: minic-sol.zip. This also includes a file Parser.cup.prec which uses precedence to disambiguate the shift/reduce conflict.
  9. Symbol table & type checking.
    • We continue with minic, starting from the following package: typecheck.zip.
    • First, we want to use a symbol table to distinguish different uses of the same symbol. This only requires modifications in the Parser.cup files.
    • Second, we implement the computeType() function in the ast classes which extend the Expression class.
  10. Exam Discussions 1: Type Environments.
  11. Exam Discussions 2: Code Generation.
  12. Exam Discussions 3: Everything Else.

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