Lab 4: Parse Lab I

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 pat. The lab is due at the beginning of your next lab period. You should submit a folder called lab04 containing all of the following files:

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 individually.

A different kind of language

The pat language is a simple language for defining sequences. Here are some examples:

> ./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 followed by : 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 operator * 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 pat language:

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 pat program, which is just a sequence of ;-terminated pat expressions:

Sseq STOP S | ε
seqseq FOLD catseq | catseq
catseqcatseq opseq | opseq
opseqopseq COLON NAME | opseq REV | atom
atomSYM | NAME | LB seq RB

A recursive descent parser for pat: Part I

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!):

Sseq STOP S | ε
seqcatseq seqtail
seqtailFOLD catseq seqtail | ε
catseqopseq cattail
cattailopseq cattail | ε
opseqatom optail
optailCOLON NAME optail | REV optail | ε
atomSYM | 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.


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!

Stop, copy, and roll

When you finish Part I, copy your do-nothing recursive-descent parser into the pat2.cpp file. And if you get here during the lab time, flag down the instructor and show off your Part I!

A recursive descent paser for pat: Part II

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, calc.lpp, rdcalc2.cpp) and make sure you understand how it works. See how semantic values (the union type 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 non-terminals have vector<string> objects 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 union types. 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 pat2.cpp.


Enrichment: Efficiency

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 vector<string>'s 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. gcc 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 -O2. 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!)