You may work in pairs for this lab. If you choose to do so, only have one partner submit the required files electronically. Be sure to include both partners' names at the top of every submitted file.
In this lab you will implement a recursive descent parser and
interpreter for a special language called
The lab is due at the beginning of your next lab period.
You should submit a folder called lab04
containing all of the
pat2programs. The rules in the included Makefile will probably suffice.
Starter code for all these files has been generously provided for you:
download and extract lab04.tar.gz.
(On any unix/linux machine, type
tar xzvf lab04.tar.gz to
create a subdirectory
lab04 and extract the files into it.)
You can also click on the links in the list above to get the files
pat language is a
simple language for defining sequences. Here are some
> ./pat2 a b c; a b c [a b c]_r; c b a [a b b d]:X; a b b d X X_r; a b b d d b b a [a b c [d e]:X f g h] X_r; a b c d e f g h e d
"Symbols" are alpha-numeric
strings beginning with lower-case letters (such as 'a', 'b', or 'cat').
Pattern variables are alpha-numeric strings beginning with upper-case
letters. Square brackets are used for grouping. A sequence
: NAME is assigned to a variable
as a side effect. That variable is in scope from that moment
on until the interpreter is exited (with ctrl-d). The
_r operator reverses a sequence. Its precedence
(and variable assignment) are higher than concatenation, so
a b [c d]_r gives a b d c, not d c b a. Finally, there's an
* that interleaves two sequences, like
[a b c] * [x y z]; a x b y c z [a b c d e] * [x y]; a x b y c d e
This operator has lowest precedence, so the [ ]'s above are unnecessary. If the interleaved sequences have different lengths, the unmatched extra characters in the longer one are just written out sequentially at the end.
Here are the tokens for the
SYM: [a-z][a-zA-Z0-9]* FOLD: "*" STOP: ";" COLON: ":" NAME: [A-Z][a-zA-Z0-9]* REV: "_r" LB: "[" RB: "]"
And here is the grammar for a
which is just a sequence of ;-terminated
S → seq STOP S | ε
seq → seq FOLD catseq | catseq
catseq → catseq opseq | opseq
opseq → opseq COLON NAME | opseq REV | atom
atom → SYM | NAME | LB seq RB
In this part of the lab, I provide a flex scanner file and an abstract grammar for the language, and you create the recursive descent parser. For the moment, your parser should simply accept valid program strings and print out an error message and exit in the presence of a syntax error. This will be similar to the basic recursive-descent parser from Class 9: Look at the file rdcalc.cpp and make sure you understand how it works.
The grammar above is probably the natural grammar for this language, at least if you want to specify the associativities and precedences of the language's operators. However, it is not appropriate for LL (top-down) parsing. Please stop for a moment, look at the grammar and make sure you understand why. Which rules are troublesome?
For purposes of this lab, I'm going to give you a rewriting of the grammar in a form that is amenable to top-down parsing (though I'd like you to be able to do it yourselves!):
S → seq STOP S | ε
seq → catseq seqtail
seqtail → FOLD catseq seqtail | ε
catseq → opseq cattail
cattail → opseq cattail | ε
opseq → atom optail
optail → COLON NAME optail | REV optail | ε
atom → SYM | NAME | LB seq RB
Now you are write a recursive descent top-down parser for this grammar. You should refer to Class 9 to see how this works. The provided files pat.h, pat.lpp, pat.cpp, and Makefile should help get you started.
pat.cppfile to get this part working. That is, the scanner should work as-is.
pat.hdefines constant integer values for the token types, counting up from 1. On end-of-file, the scanner returns 0 instead of a valid token type.
mainfunction will be a little simpler than in the calculator parser, but the function for the start symbol will be a little more complicated.
When your recursive descent parser works, you should be able to enter statement after statement with no feedback, until a syntax error cases a message and aborts the program. For example:
> ./pat a b c; [a b c]:X X_r; [ a b : c d ]; Parse error!
When you finish Part I, copy your do-nothing recursive-descent parser
pat2.cpp file. And if you get here during the lab
time, flag down the instructor and show off your Part I!
Now it's time to build a functioning interpreter for the
pat mini-language. I suggest you look at
the recursive-descent parser and interpreter for the calculator
language from Class 9 (calc.h,
and make sure you understand how it works.
See how semantic values (the
TokenSemantic for the calculator) are handled?
See how we evaluate across
those akward "tail" productions?
Now, for your interpreter I suggest that the tokens have C++
string objects as semantic values, and that
for semantic values, i.e. that's what the grammar rule
functions return. Since every token will have the same type,
you don't need to bother with any
And because I like you, I've implemented a
few helful helper functions, to perform the fold
(*) operation, concatenation and the reverse (_r) operations.
These are already included in the starter file for this part
pat.lpp. However, your modifications should not affect the original
patprogram from Part I. (The basic parser will just ignore these return types.)
vector<string>'s for the cases you want to ignore. Get that working then add the non-ε
cattailrule. Get that working then add the rest. Leave variables for last.
pat-language variables. Once again we'll use maps, but this time we're mapping strings to vectors of strings, i.e.:
map<string, vector<string> > symTable;Make sure you use the spaces in between > and >. Why? Becauase C++'s scanner treats >> as a single token, not as two >'s.
A hallmark feature of any good compiler or interpreter is how
fast programs will run. The interpreter you created in Part II
is probably quite inefficient in the way it handles memory.
In particular, passing around
by value and returning them from functions involves a lot
of memory copying. Much of this is unnecessary.
Re-write your interpreter from Part II to use memory more efficiently.
In particular, your recursive descent functions should all return
void, and they should store their results in
the first argument, which should be non-const and passed by reference.
For instance, the signature for
cattail might be:
void cattail(vector<string>& vec);
With this, you should be able to make your recursive descent
functions tail recursive.
will actually optimize for tail
recursion in your programs (just like DrScheme would), but only if
you tell it to with an optimization flag like
You can insert this into the Makefile.
(Nothing to submit for this part. You can feel free to include your amped-up interpreter in what you submit for Part II, but make sure it doesn't break what you already had working!)