KOI: Lab Exercise 2

Don't worry if this assignment takes longer to complete than the others. It could have been split into two or more assignments, but since it covers a single subject (parsing using a hand-coded predictive recursive-descent parser) it has been kept as one assignment.

The grammar

start -> list eof
list -> expr ; list
       | empty
expr -> expr + term { print('+') }
       | expr - term { print('-') }
       | term
term -> term * factor { print('*') }
       | term / factor { print('/') }
       | term div factor { print('DIV') }
       | term mod factor { print('MOD') }
       | factor
factor -> ( expr )
       | id { print(id.lexeme) }
       | num { print(num.value) }

The grammar is left-recursive. We use the standard method (see the lecture notes from lecture 3) to eliminate left-recursion. We get this syntax-directed translation scheme (ASU-86 Fig 2.38):

start -> list eof
list -> expr ; list
       | empty
expr -> term moreterms
moreterms -> + term { print('+') } moreterms
       | - term { print('-') } moreterms
       | empty
term -> factor morefactors
morefactors -> * factor { print('*') } morefactors
       | / factor { print('/') } morefactors
       | div factor { print('DIV') } morefactors
       | mod factor { print('MOD') } morefactors
       | empty
factor -> ( expr )
       | id { print(id.lexeme) }
       | num { print(num.value) }

In the program in section 2.9 of the course book (ASU-86), the parser in parser.c has been hand-optimized to eliminate tail recursion, using the methods described on page 52-53 in ASU-86. For example, the non-terminals term and morefactors are handled by the function term, which contains a while loop. Modern C compilers will perform these optimizations automatically. Since they are unnecessary and make the program harder to understand, they have been removed in the version of the program available on these web pages.

Part A: Modifying the grammar

The postfix representation of an assignment variable = value is variable value =. For example, the postfix representation of x = 17 is x 17 =, and the postfix representation of fum = 10 * 3 + foo is fum 10 3 * foo + =.

To change the grammar from above to one that understands assignments, we first add a production for a new non-terminal called assignment. We also change the definition of list from a list of expressions to a list of assignments. The grammar now starts like this:

start -> list eof
list -> assignment ; list
       | empty
assignment -> id = expr
expr -> term moreterms
...

Assume that we want to handle both assignments and expressions. Write a grammar for that.

Would it be possible to write a predictive recursive-descent parser for your grammar? (Hints: Is it ambiguous? Is it left-recursive? Are FIRST sets disjoint?)

Part B: Change the program

Part C: Calculate the values

Also print the assigned value after each assignment.

Just use integer operations in your calculations. The result of 10 / 3 should be 3, and the result of 1 / 3 should be 0.

Another hint: The infix expression x = x + 1 has the postfix representation x x 1 + =, but those two xes are different! The second x refers to the value of the variable, as usual in an expression, but the first x refers to the variable itself. So what should be pushed onto the stack for those xes?

Part D: The exponential function

Examples of input and output:

For the report, include and explain any changes you made to the grammar and to the program.

Report

Even if you don't send a report by e-mail, we advise that you write down your answers, to facilitate communication and for your own later use.