Exercise 2

Write a bottom up parser, in a language of your choice, for the language described by the grammar below. You will be expected to produce a running parser on the CS Suns. This should generate output which demonstrates the successful parsing of strings matching the grammar. You should hand in

• a listing of your program or programs;

• output from a set of sample runs, demonstrating the functionality of your parser;

• matching input files;

• a brief description of your code, which should also be well commented;

• instructions on how your tutor can run the parser;

The grammar:

Exp → Exp Arithop Exp | ( Exp ) | Id
Arithop → + | − | ∗ | / | ↑
Id → a | b | c | d

C rules of associativity and precedence apply, except for the exponentiation operator, ↑, which uses Pascal’s rules..

Some sample input:

a+b
a+b*c
(a+b)*c

For a reasonable mark, you should recognise, but not necessarily recover from, errors in the input. For full marks, you should report errors clearly and recover to continue recognising subsequent input if possible.

Use of compiler generator tools, such as LEX and YACC, is not allowed. The work should be completed and handed in by the end of week 9. It is

more sensible to hand in a well described, but incomplete, exercise than to spend too long on this work. All necessary material will have been covered by lecture 8. Work handed in late will be penalised.