Software Construction
Gregor v. Bochmann

Assignment 3

A Simple Compiler in Java

Lab-8 : A Simple Compiler in Java (Originally prepared by  Abdelilah Maach and Alan Williams; revised 2009 by G.v.B. )

We saw the "Very Simple Programming Language" (VSPL) in Lab 7. During this lab, we learn how to write a compiler for this language in Java using the recursive descent methodology.

Preliminary Part: Study a given compiler for VSPL

The development of a compiler for VSPL in Java is explained here.

  1. Please study the explanations given and the Java code
    • for the lexical analyser
    • for the syntactic analyser and
    • for the evaluation (execution) of the expressions as performed by the code included in the syntax analyser.
  2. Execute the compiler with some example programs. Note: You can find some example here.
  3. When you understand the Java program, go to Part B.

Assignment 3 - 2016:

Given: March 14 - Due date: March 29 (NEW) - Please submit your report on paper into the drop box, and the Java files in a zip file sent by e-mail to the TA Rui Chen ‎[]‎ who will mark your report. -- Students may work individually or in groups of two

Modify the given compiler of VSPL in order to support the following:

(A) Your compiler should support the following language:

  1. The language VSPL should be supported, but excluding the minus operator.
  2. The following language extension should be supported:

(B) Your compiler should not only check the syntax of the language, but also do some sematic processing, similar to what the given VSPL compiler does. That is, you compiler should evaluate the expressions of assignment statements (like the VSPL compiler). But the expressions of assignment statements that should not be executed (because the assignment statement is in the body of an IF statement with a False expression) should not be evaluated. In addition, the compiler should print an error message if a variable is used in an expression before it was assigned a value (that is, if the identifier is not yet inserted into the symbol table). It is therefore suggested that you use the following semantic attributes:

The following semantic attributes should be used in the compiler program. An explanation of synthesized and inherited attributes for the example of expressions is discussed in the course notes unter the heading "Example: different grammars for expressions and static evaluation of the values of expressions" in the section on Semantic Attributes.


Your report should address (at least) the following steps of the development process. Note that most of the work for steps 1 and 2 were already done during Lab-7.

  1. Change your grammar to adjust to the new syntax defined above.
  2. Check that your proposed grammar is LL(1). If it is not LL(1), apply some transformation rules in order to obtain an equivalent LL(1) grammar. Repeat until you get an LL(1) grammar.
  3. Write down the recursive automata for the syntactic rules, in a manner similar to what is explained for VSPL.
  4. Write the recursive Java procedures for the non-terminals of the grammar.
  5. Revise the lexical analyser in order to include the new terminal tokens that are required for the extension.
  6. Integrate appropriate semantic evaluation rules for calculating the values of expressions during compilation time (similar to the ones included in the compiler for VSPL).
  7. Debug your extended compiler by executing it with some example programs. Here is an example program.