UP PREVIOUS NEXT

CS5031 Practical 3: Syntax-directed Translation

PURPOSE

This practical is designed to introduce you to syntax-directed translation - that is, translation from one notation (infix) to another (postfix) organised around the parsing process (e.g. in the actions in yacc).

OBJECTIVES

To create an infix-to-postfix filter using flex and byacc.

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 "$CS5031/p*/ex3". 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 ';')+
Note that you can't directly write something like this in yacc. Instead, you have to use recursion to read several expressions, just like in the previous lab. (hints from the previous lab)

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

If you have time to spare, you could implement more of the facilities of the real dc and bc programs, such as floating point, functions or variables.
Alternatively, you could try adapting the code from the previous lab exercise to generate postfix output from the parse-trees, rather than (as in this lab exercise) directly in the actions in flex and byacc. You need to modify the c code so that "evaluate" outputs postfix for dc rather than calculating the answer directly.


UP PREVIOUS NEXT