UP PREVIOUS NEXT

Ex. 2111.4 : INTRODUCTION TO LEX + YACC

DURATION 1 lab session

PURPOSE

This exercise is designed to familiarise you with the use of flex and byacc together so that, when you come to use them later, you can concentrate on the important aspects of the problem.

OBJECTIVES

To create an infix-to-postfix filter using flex and byacc, which turns out to be a simple example of code generation.

DESCRIPTION

dc is a calculator program available as part of the unix utilities. Unfortunately, it uses reverse-polish notation (postfix). bc is a front-end for dc that reads infix expressions from the user, translates them into postfix, and hands them on to dc, which performs the arithmetic. You should read the man information for bc and dc and try running them both. In particular, try "bc -c" to see the output it generates. You are going to create a simple version of bc, using flex and byacc.

Copy the starting files from "$CS2111/p*/ex4". The files include byacc and flex programs, a makefile and some (trivial) test data. This is the flex and byacc calculator used in the lectures, slightly changed to be usable in a pipeline. You can compile and run it against the test data by: 

	make test
but you will only see: 
	result is 7
	syntax error
until you have modified the grammar descriptions and actions in the byacc file as outlined below.

If you are not using Linux, you may get an error message about "setlinebuf". On SunOS/Solaris, you may need to remove the comment around the "extern" for it in bcy.y. On other operating systems, you may also have to edit the "extern" line.

You should modify the grammar rules to allow more than one calculation i.e. change "input" to be the equivalent of: 

        input  =  (expression ';')+
As you don't calculate directly in your bc but output to dc instead, you should get rid of the %type declaration and replace all the existing actions in the byacc file. To convert infix to postfix, your new actions must:
* output each number as it is recognised by byacc (i.e in the rule for a factor).
* output each operator after the pair of numbers (or terms or factors or whatever) that it operates on i.e. by the byacc rules for expression and term.
* output "p\n" (to print the answer) after recognising each ";" i.e. by the byacc rule for input.
* output "q\n" (to exit dc) at the end of input. To do this, you need an extra rule that matches all the input and then outputs "q\n" as its action. Set the "%start" rule to be this new rule.

For example, (infix) input of: 

        1 * 2 + 3 / 4 ;
        1 * ( 2 + 3 ) / 4 ;
should generate (postfix) output of: 
        1 2 * 3 4 / + p
        1 2 3 + * 4 / p
        q

You can run your version of bc by itself initially, but you should be able to use it as a calculator by typing: bc | dc

Bonus: Implement more of the facilities of the real dc and bc programs, such as floating point, functions or variables. (This is probably worth 1 or 2 marks.)

DELIVERABLES

Demonstrate your working program to a demonstrator or lab supervisor. You must "labmail" the final version of your byacc code i.e. "bcy.y".

UP PREVIOUS NEXT