Class 19: A Sample Parser

Back to Predictive Parsing (4). On to Shift-Reduce Parsing (1).

Held: Wednesday, 3 March 2004

Summary: Today we look at some details in going from grammar to parser.

Related Pages:

Notes:

• Don't forget about the Math/CS journal club today at 4:30.
• Tomorrow's convo looks to be quite interesting.

Overview:

• Building the parse functions.
• An example.
• Explaining expressions.

• For each nonterminal, n, write `parse_n`.
• The standard structure:
```Node parse_n(TokenStream ts)
throws ParseException
{
Token tok = ts.peek();
Vector children = new Vector();
Code for rules
return new Node(Nonterminals.n,children);
} // parse_n(TokenStream)
```
• For each rule n ::= rhs
• Identify the symbols in first(rhs). Assume s0 ... sk.
```   if ((tok == s0) || (tok == s1) || ... || (tok == sk)) {
translation of rhs
}
```
• If rhs is nullable, identify the symbols in Follow[n]. Assume t0 ... tl.
```  if ((tok == t0) || (tok == t1) || ... || (tok == tl)) {
translation of rhs
}
```
• Note that you can probably combine the two.
• To translate a rhs,
• Translate each token, T, into `consume(T,ts)`
• Translate each nonterminal, m, into `parse_m(ts)`
• Sequence them
• Combine the parsed parts of the rhs appropriately into a vector.
• Return a new node.
• Observation: repetition is slightly harder, but not much.
• Expect to add an extra X-list node.
• This technique is fairly general. You may find that you want to clean up the code somewhat.

Some Examples

• To be determined in class.

A Note on Expressions

• Some of you may have noted that I do some 'creative' stuff with expressions.
• We'll go over that stuff.

Back to Predictive Parsing (4). On to Shift-Reduce Parsing (1).

Disclaimer: I usually create these pages on the fly, which means that I rarely proofread them and they may contain bad grammar and incorrect details. It also means that I tend to update them regularly (see the history for more details). Feel free to contact me with any suggestions for changes.

This document was generated by Siteweaver on Wed May 5 11:47:05 2004.
The source to the document was last modified on Tue Jan 20 23:06:45 2004.
This document may be found at `http://www.cs.grinnell.edu/~rebelsky/Courses/CS362/2004S/Outlines/outline.19.html`.

You may wish to validate this document's HTML ; ; Check with Bobby

Samuel A. Rebelsky, rebelsky@grinnell.edu