Class 9: Recursive descent and table-driven top-down parsing


Display version (pdf).




PLP, Section 2.3.2 "Table-Driven Top-Down Parsing". (You can gloss over the details in the subsection on "Predict Sets".)


Suppose you wanted to add a feature to the calculator for computing max, so you could enter:

max{3, (2+1)*7/4, 68 - 3*4*5 - 9/2};
... and get the answer 5.

Your task is to determine how to modify the simple calculator syntax (as specified on slides 7 and 8) to accommodate this new syntactical structure. This will require changing both the scanner specification (regular expressions and token names) and parser specification (CFG).

Specifically, submit the following:

  1. Any new tokens that must be added (names and regular expressions).
  2. Any grammar rules that must be changed, or new grammar production rules that must be added.
  3. A parse tree using your augmented grammar on the string 1 + max{3,7,-2};.

It would be great if you also modified the recursive-descent parser above to include your new tokens and rules, but this is not required to be turned in.