University of Texas at El Paso
Compuer Science
Assignment 3 Minimize    

Compilers and Interpreters: Assignment 3

October 19, 2010

Make an ANTLR grammar for Mini-Triangle, as described in pages 8-9
of our textbook. As opposed to Assignment 2, you need to build an AST tree
similar to the AST built in the Triangle parser (pages 109-110 of our
textbook). This is done by building two grammars, one that parses the input
and creates an AST tree. The other parses the AST tree and performs the
necessary actions. For this assignments, the necessary actions are to
output the level where a variable was declared each time a variable is
used in an expression. The levels are defined as in figure 5.3, page 145
of our textbook. I myself implemented this with a fixed size array of hashmaps.
This means that there is a limit on levels of nesting. You're welcome to
do the same, or use another method if you prefer.

On the web site, I have included an example (mostly taken from the ANTLR book) of an
Expr grammar that outputs an AST for expressions, and an Eval grammar that evaluates the
expressions in the AST. To run this example:

java org.antlr.Tool Expr.g

java org.antlr.Tool Eval.g

javac *.java

java Testg

I have also included a bare grammar for Mini-Triangle.

Due Wednesday, November 2, before the start of class, or before 11pm if sent by e-mail.
Include "CS4352, assignment 3" on the subject line.
E-mail to the instructor (

  1. the grammars.
  2. a sample Mini-Triangle program (perhaps the same as in the previous assignment)
    that causes the parser to execute all rules of the grammars.
  3. the output AST, as printed as printed by the "toStringTree" method
  4. the level of each variable as encountered in expressions.

Documents Minimize    

 TitleOwnerCategoryModified DateSize (Kb) 
Supporting filesLuc Longpre 10/19/20103.43Download