Project 1

Jump to: test cases , turnin info

Extending a grammar and using ANTLR to build an abstract syntax tree

Due Tuesday, October 5 at 11:59pm, via turnin.

For part 1 of your project, you are to take a grammar for a small language called Simple (see the Examples section) and extend it to parse and build an AST for the features described in what follows.

The grammar for Simple describes a very limited programming language made of a single block of statements enclosed within a begin..end pair. The only statements available are

assignment, as in:

a := 3;

a := b;

a limited form of conditional statement:

read and write statements that take lists of variables and expressions, respectively

Expressions involving integer constants and variables with 1 character names, plus the a list of built-in operators.

Your assignment is to augment this grammar to recognize the following language:

The explcit required additions are:

Declarations of the form:

<id1>, <id2>, ... <idn> : <type> ;

An augmented if statement with an optional else part so that:

A while statement of the following form

The following operators:

=, <, >, <>, <=, >= (relational operators)
and, or, not (boolean operators)
. (concatenation operator for strings)

Identifiers which can be any length and can contain any combination of uppercase letters, lowercase letters, and underscores.

Comments that begin with "--" and continue to the end of a line, as in

In designing your abstract syntax tree nodes, keep in mind the information that will be necessary in order to interpret or translate any node. You many use any combination of built-in and customized tree construction that you choose. Do make sure that you can tell what kind of node is constructed by any of your syntax rules.

Note the following operator precedence holds:

   HIGHEST
      not, unary-minus, parentheses
      * /
      + - .
      = <> < > <= >=
      and
      or
   LOWEST

For now, assume all binary operators associate left-to-right.

Test cases

Here are a few test files, with some sample output. Your output needn't match mine exactly (though it would be convenient for this project if it did); all that matters is that your parse tree unambigously communicates the information in the original source files.

Turnin information

To turn in the project, make sure you have set up workon, and then do

   workon  cs4240
   turnin  prj1  simple.g  Main.java