CS 415 Project 1
You may use any programming language that runs on the ilab machines for
these problems.
1. Use a recursive descent parser to implement an interpreter for this (LL(1))
arithmetic grammar:
hProgrami ::= hStmtListi .
hStmtListi ::= hStmti hNextStmti
hNextStmti ::= ; hStmtListi | ?
hStmti ::= hAssigni | hPrinti
hAssigni ::= hIdi = hExpr i
hPrinti ::= ! hIdi
hExpr i ::= + hExpr i hExpr i
| - hExpr i hExpr i
| * hExpr i hExpr i
| / hExpr i hExpr i
| hIdi
| hConsti
hIdi ::= a | b | c
hConsti ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
The arithmetic operators indicate addition, subtraction, multiplication,
and (integer) division, respectively.
For example, on the input
a=3;b=2;c=+ab;!c.
Your program should print 5.
For invalid inputs, such as
a=+12;!a.b
you should print “syntax error”.
For runtime errors, print “exception”.
Please treat referencing a variable before it’s assigned a value as an error.
Note that all tokens are single characters, and you can assume we will not
include any whitespace, which should help simplify the scanner implementation.
2. Consider this grammar of boolean expressions:
hProgrami ::= hExpr i .
hExpr i ::= hExpr i && hExpr i
| hExpr i || hExpr i
| hExpr i ˆ hExpr i
| ∼ hExpr i
| hConsti
| ( hExpr i )
hConsti ::= F | T
where the expression operators denote AND, OR, XOR, and NOT, respectively.
• What happens if you try to use this grammar in flex/bison?
• Modify the grammar to make flex/bison happy, without changing
the language itself. Binary operators should have the precendence
&&, ^, || (highest to lowest) and be left associative.
• Use your modified grammar and flex/bison to implement an interpreter for the language. For invalid inputs, you should print “syntax
error”. For example, on input F || T., you should print T. (just T,
not the period)
2
