Purpose

These computer based exercises should help you gain familiarity with context free grammars and a tool that, given a context free grammar, generates a program to recognize the sentences of the language.

Context Free Grammars
Where we use jacc to generate programs that recognize sentences or patterns.

1. Boolean Expressions.
   The file bexp.jacc is a source file for a tool called jacc that is already installed in your computer. As it is you can download it and do the following:

   jacc -pt bexp.jacc -r test1.be 
   

   (here is the file test1.be!)
   1. Look at the source file and, with help from the lecture and the manual, identify what things are specified where (for example, the directive %token TRUE states that one of the terminals of the language is the token TRUE). Look also at the command line and try to read about the options -pt and -r. Look at the test file!
   2. In the lecture we showed how to use directives for associativity and precedence in order to be able to use only one syntactic category and let jacc solve the ambiguity problems. Modify bexp.jacc so that there is only one syntactic category (bexp). Use the ambiguous grammar and the directives to deambiguate!
   3. In the examples above we did not generate a parser, we did not even need a lexer! The following two files contain sources for JFlex and jacc to generate compatible lexer and parser for boolean expressions
      • bexp.flex
      • bexpA.jacc
      The way to work with them is as follows:

      jacc bexpA.jacc
      jflex bexp.flex
      javac Scanner.java
      javac Evaluator.java
      java Evaluator some test file
      

      Where is it said that the scanner is in the class Scanner.java? What is Evaluator.java? Are there any other java files involved? What tool generated them? Why do we first run the parser generator? See to it that you understand the source files and that you see how they are related. Compare what you wrote in the .jacc file with the parser it generated!
   4. Use bexpA.jacc as guide and design a grammar for arithmetical expressions with numbers, plus, minus, times and division. See to it that you can calculate the value of an expression while parsing it! Try it on files containing correct and erroneous expressions.
2. anbn. Write a lexer and a parser to recognize sentences of the form a^n b^n (for example aaabbb). Let the parser compute the value of n for the sentence it parses (for example, for aaabbb it should calculate 3). Use the tools to generate the lexer and parser!
   Optional Recognize lists of such sentences and output a list of values!
3. Balanced parenthesis in a java file.
Write a program that inspects a java file and determines whether parentheses are balanced. We count (, ), {, }, [ and ] as parentehses!

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

1. Submit a zipped file with all the jflex and jacc sources and at least a test file of text for each exercise. Include also answers to the questions stated
2. Submit by sending an email to jerker.bengtsson|at|ide|dot|hh|dot|se with subject assignment 2. Attach only one file!
3. Deadline. Your mail should arrive before february 5th at 9.00 a.m.!