This lab contains both written and electronic parts, to be submitted separately. Each exercise is marked according to whether it should be part of the electronic or written submission. Both parts are due at the beginning of your lab period next week, as usual. And as always, you are advised to type up your written parts whenever possible so that they are legible.
You can (and should) work with a parter for this lab, and if so, only one of you should submit each part. And of course include both your names on everything you submit, electronically or on paper.
Your electronic submission should come from a folder called
lab05 and include the following files. You
can download all the starter code at once with the file
We're going to consider a grammar for the language we use to define ... grammars. We have rules with symbols and arrows and bars for "or". These descriptions must themselves obey a grammar:
S → S rule | rule
rule → SYM ARROW rlist
rlist → rlist OR rhs | rhs
rhs → rhs SYM | SYM
These rules are coded in a way Bison can understand in the file
ex1.ypp. Take a look at this file, download
it, and run
bison on it.
Bison will produce an error message. The exercises below are about this error and what you can do to fix it. To help see the error, I recommend you consider the following valid input:
X -> a b Y -> c dwhere X,Y,a,b,c,d are all SYM tokens and -> is an ARROW token. Trace through the parse modelling the stack (which remember contains states as well as grammar symbols) at each step. Determine where you first run into a conflict, and try to figure out why it really happens.
bison -v ex1.ypp, which will produce the file
ex1.output. This file lists the states of the parser's CFSM along with the actions for each state, depending on the lookahead token.
ex1.yppfiles to account for your change. Add an entry to
features.txtfor this exercise, including a short (plain language) description of how the language has been modified.
3*12 > 15+3 > 10;. The new token COMP is a comparison operator like > or <.
run → res STOP run | res STOP
res → exp | res COMP res
exp → exp OPA term | term
term → term OPM factor | factor
factor → NUM | LP exp RP
This grammar is written for
bison -v ex2.ypp and you should see another error...
ex2.yppto incorporate your fix, and compile it to verify that
bisonno longer gives an error. Add an entry to
features.txtindicating that you did this exercise. You shouldn't have to add any description there, since you didn't change the language!