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 ‎[rchen040@uottawa.ca]‎ 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:
• An additional statement: an IF statement without an ELSE part with the syntax of Java which contains within the curly brackets a <statement list> as defined for VSPL.
• A boolean expression which is used within the IF statement. It has the following syntax: an identifier followed by "=" or by "!=", followed by an identifier.

(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.

• An expression should have a synthesized attribute of integer type which represents the value of the expression (as used in the VSPL compiler).
• In order to know at each point of the program analysis whether the parsed statements should be executed or only parsed for checking the syntax, the statements should have an inherited attribute in the form of a parameter which is of boolean type and which indicates whether the analysed statement should also be executed. The value of this parameter of the syntax procedure must be defined when the syntax procedure is called, for instance during the analysis of the body of an IF statement, or when a statement is part of a <statement list> that is in the body of an IF statement.
• The checking for non-initialized variables should only be performed for statements that are also executed. Therefore it is suggested that the values of expressions would only be evaluated for expressions that are part of statements that will be executed. It is therefore suggested that the expressions also have an inherited boolean attribute that indicates whether the expression should be evaluated.

Report

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.