Building a compiler for VSPL

Recall the Syntax of SVPL:

  1. <program> --> begin <statement list> end
  2. <statement list> --> <statement> ; <statement list>
  3. <statement list> --> <statement>
  4. <statement> --> <id> := <expression>
  5. <expression> --> <id> + <id>
  6. <expression> --> <id> - <id>
  7. <expression> --> <id>

Requirements for the Java program:

The Java program should read (on the standard system input file) a program written in the Very-Simple-Programming-Language and produce as output (on the standard system output file) either an appropriate error message (if the program contains a syntax or semantic error), or a list of integer values equal to the values of the expressions contained in the assignment statements of the program (and in the order in which they are contained in the program).


Please read again the following sections in the course notes: "Syntax Diagrams" and "Example: different grammars for expressions and static evaluation of the values of expressions" in the section on "Semantic Attributes".

We use recursive descent syntax analysis. This means that the compiler will contain a recursive procedure for each non-terminal of the grammar: <program>, <statement list>, <statement> and <expression>. However, <statement list> can be eliminated by noting that the rules (2) and (3) may be replaced by the rule (extended BNF, including the Kleene star): <statement list> --> ( <statement> ; )* <statement> and then substituting the regular expression on the right side into rule (1), resulting in the following: <program> --> begin ( <statement> ; )* <statement> end .

Then we can write down (recursive) automata, one for each non-terminal, as follows (we have seen an example of such a recursive automaton in the discussion of the grammar of regular expressions at the beginning of the chapter on syntax analysis):

programstatement expression

This can also be written in the form of a so-called syntax graph . These recursive automata (or the corresponding syntax graphs) can be easily translated into Java code, as shown in the Syner class in the Java program called SimpleCompiler. Similarly, one can write down a syntax graph for the lexical analysis and construct a corresponding Java program which is given in the form of the Lexer class of the SimpleCompiler. Here is an example program that has been analyzed by the SimpleCompiler and has produced the following output.

Notes on the SimpleCompiler program: