Purpose

These computer based exercises should help you understand when shift-reduce conflicts can arise and how to solve some of them. You should also be able to use jacc to better understand the consequences of a conflict. You will also learn how to implement abstract syntax trees and you will use jacc to generate abstract syntax. You will see a simple example of the visitor pattern.

Conflicts
Where we use jacc to describe grammars, generate the push-down automata and follow the workings of the parser.

1. If statements.
   The file if.jacc contains a jacc version of the grammar we discussed in the lecture. The first rule for stm is a prefix of the second rule for the same nonterminal and this leads to a shift/reduce conflict. Download it and compile:

   jacc -pt if.jacc -r a test file 
   

   See to it that the test file (in the right format, with tokens!) contains the example we discussed in the lecture, where the conflict is apparent.
   1. In spite of the conflict, jacc accepts the sentence. What action did it take when the conflict occurred? Can you see it in the output? (jacc uses _ for the bullet!). Explain!
   2. In order to see that another parsing of the sentence is possible you can use jacc with the option -h. It will generate an html version of the push down automaton. If you open the file with a web browser you can use the links to follow the workings of the parser. When you want to do a reduce you have to use the back-button! (see the manual!). Do it for the sentence in question!
   3. Implement in jacc the grammar that solves the conflict in favour of shift. Generate the html version of the automaton and use it with the same sentence as before.
2. Method body.
   In the declaration of a method we want to allow for a sequence of variable declarations (possibly empty) followed by a sequence of statements (possibly empty). A variable declaration consists of an identifier (for the type) followed by an identifier (for the variable) followed by a semicolon. A statement is an assignment of the form identifier, equals sign, expression followed by semicolon. Here is an example:

   A x;
   B myB;
   x = exp;
   myB = exp;
   y = exp;
   

   The jacc specification methodDec.jacc is an implementation of the grammar for this kind of body in a method declaration.
   1. What happens when you run

      jacc -pt methodDec.jacc
      

   2. Try

      jacc -pt methodDec.jacc -r test.md
      

      with test.md. What happens? Explain! You might want to use the generated machine to see if you can get the example accepted by making other choices than the parser does. To generate the machine you have to do

      jacc -h methodDec.jacc
      

   3. Fix the grammar so that there are no conflicts and try the example again. Try other examples, with empty list of variable declarations or empty list of statements.

Abstract Syntax
Where we use jacc to generate abstract syntax and we define a little visitor for calculating values boolean expressions.

1. Abstract syntax
   You are provided with the JFlex and the jacc specifications for the syntax of boolean expressions (including very simple identifiers!). By now you should know how to use the tools to generate a parser. You are also provided with files with boolean expressions that should be accepted by your parser.
   • bexp.flex
   • bexp.jacc
   • test2.be, test2.be, test3.be
   1. Try the parser on these sources so that you understand how the actions specified for each rule are used!
   2. Define java classes that implement the syntactic category of boolean expressions using the principles we defined in the lecture. Change the jacc specification so that the abstract syntax of a boolean expression is built while parsing. Organize the programs as follows:
      • Place the classes for the abstract syntax in a directory syntaxtree
      • Declare the classes as belonging to the package syntaxtree
      • Add the directive

        %{
        import syntaxtree.*;
        %}
        

        at the beggining of your jacc specification.
      See to it that you can test that your parser generates the right abstract syntax tree (You could add a method String toString() to each class in the abstract syntax ...)
2. Visitors
   Because we will want to do other things with the classes of the abstract syntax other than printing them, we will use a design pattern that allows us to define new operations on the classes without having to modify them. The pattern is called the visitor pattern and it looks a little bit complicated due to some semantic issues from Java that we will discuss later. In this exercise you will implement the visitor pattern for boolean expressions and you will use it to implement an evaluator.
   1. Define a generic interface

      package visitor;
      import syntaxtree.*;
      public interface Visitor < A, Env >{
          A visit(BooleanLiteral x, Env e);
          A visit(Id x, Env e);
          A visit(And x, Env e);
          A visit(Or x, Env e);
          A visit(Not x, Env e);
      }
      

      (Notice: see to it that you use the names of YOUR abstract syntax classes in the arguments to the methods visit!)

      The idea is that different operations on boolean expressions will be implemented by redefining these visit methods in new classes.

   2. In each of your abstract syntax classes you will have to include a method

          public < A, B > A accept(Visitor < A, B > v, B b){return v.visit(this,b);}
      

      and you will have to define an abstract variant of the method in your abstract class for the category of boolean expressions.
   3. Now you can define a class Evaluator: a visitor where we use environments to assign boolean values to variables and calculates the value of a boolean expression in this environment. For my abstract syntax classes it looks like this:

      package visitor;
      import syntaxtree.*;
      
      public class Evaluator implements Visitor < Boolean,java.util.HashMap < String, Boolean > >{
      
          public Boolean visit(BExp x, java.util.HashMap < String, Boolean > e){
      	return x.accept(this,e);
          }
          
      
          public Boolean visit(BooleanLiteral x, java.util.HashMap < String,Boolean > e){
      	return x.v;
          }
      
          public Boolean visit(Id x, java.util.HashMap < String,Boolean > e){
      	return e.get(x.id);
          }
          
          public Boolean visit(And x, java.util.HashMap < String,Boolean > e){
      	return x.left.accept(this,e) && x.right.accept(this,e);
          }
          
          public Boolean visit(Or x, java.util.HashMap < String,Boolean > e){
      	return x.left.accept(this,e) || x.right.accept(this,e);
          }
          
          public Boolean visit(Not x, java.util.HashMap < String,Boolean > e){
      	return !(x.bexp.accept(this,e));
          }
      }
      

      Do you understand why we need the method accept defined the same way in all abstract syntax classes? Try instead to do the recursive calls using visit directly. What happens? Why?
   4. Now you need an abstract syntax tree to visit! You can obtain it by means of the variable Object yyrv from the parser after you have parsed! Write a program that evaluates a boolean expression. Remember to provide an environment for the values of the variables

Submission
Who should submit? What should be submitted? How to submit? When?

1. Submit a zipped file with all the sources for the last two exercises.
2. Submit by sending an email to jerker.bengtsson|at|ide|dot|hh|dot|se with subject assignment 3. Attach only one file!
3. Deadline. Your mail should arrive on thursday february 11 at 9.00 a.m. at the latest!