UP PREVIOUS NEXT

CS5031 Practical 2: Introduction to Yacc & Parse Trees

PURPOSE

This practical is designed to familiarise you with the use of byacc (manual available via the web pages) and with parse trees.

OBJECTIVES

The starting point is the calculator given in the lectures but modified to build a parse tree for each expression, print it out, and then traverse it to calculate the value of the expression. Using byacc and flex, create several versions of this program to investigate grammars, precedence, associativity, and parse trees.

(a) Check your answers for the exercise sheet by modifying the existing calculator program to use different grammars.

(b) Use "%left" and "%right" to give the correct precedence and associativity to the operators (notes and examples available via the web pages).

If you have time:

(c) Change the order of evaluation of the left- and right-hand-side of the operator nodes to check that this doesn't change the values of any expressions.

(d) Add extra operators, including lazy operators (such as "&&" and "||"), being careful not to evaluate more of the parse tree than you need to.

(e) Create and include calls to another tree-walking function that "free"s the previously "malloc"ed data structures, once each parse tree is finished with.

The important sections for (a) are questions 2, 3, and 5 and then questions 6 and 7. Once you understand these, you can try modifying the program to input multiple expressions, but don't worry if you can't see how to do this - just move on to the next part (this comes up again in the 3rd lab exercise, so sort it out then). Question 1 is not important for an understanding of lex and yacc, and question 4 is very complicated, so don't worry about them.

Please try part (b), at least to change the existing grammar to use %left. Once you have done that, it is simple to swap the order of the %left lines, or change %left to %right, and see how the parse trees change.

DESCRIPTION

Copy the starting files from "$CS5031/p*/ex2/*". The files include a makefile, some test data, byacc, flex and c code and an include file.
The makefile relies on make's built-in knowledge of how to compile certain kinds of program. You can type "make twopass" and it will compile your "twopass_y.y", "twopass_l.l", "twopass.c" and "twopass.h" files using byacc, flex and gcc. You can then run it by typing "twopass", or run it on the given "data" file by typing "twopass <data". However, until you have done the first step in part (a) below it will only recognise the first expression and then halt with an error message.

When you modify "twopass_y.y", you should not have any shift-reduce or reduce-reduce conflicts reported by byacc. If you do have conflicts, you must get rid of them before going any further. Ask for help if you can't see how to do so.

Each time you complete a part, keep a working copy of that version of your program.

(a)
* To make your life a little easier, modify the byacc grammar rule for "input" to recognise none, one or more pairs of expressions and semicolons. Check that you have done this correctly by running your program on the given test data.
* For question 1, you should simply create a simple C program, use gcc to compile it, and run it. To understand why gcc behaves as it does for "+++" and "+++++", consider what would happen if you modified the lex file to recognise "++" as well as "+". If you still don't understand, maybe you should try it!
* For questions 2, 3, and 5, run the different expressions through the given calculator program to see what parse trees and values it generates.
* For question 4, you will need to modify the given grammar to recognise "^" and evaluate it in the corresponding action using "pow" and "nint". You can simply add the grammar rule for "^" to "exp", although this will give it the wrong precedence in a more compicated expression.
* For questions 6 and 7, modify the grammar rules in the ways suggested. You can comment out unwanted grammar rules using "/*" and "*/" as in C. If a grammar gives shift-reduce or reduce-reduce conflicts then don't bother to run the resulting calculator - the grammar is unusable.

(b)
Modify the previous version of your program by combining your byacc rules for "exp", "term" and "factor" into a single rule for "exp", and instead using "%left", "%right" or "%nonassoc" to give the correct precedence and associativity to the operators. Remember to modify your %type declarations.

(c), (d) & (e)
It is important that you do parts (a) and (b), but you should only attempt the later parts if you have spare time, or you are interested to see what will happen.


UP PREVIOUS NEXT