Class 19: A Sample Parser

Held: Wednesday, 3 March 2004

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

Related Pages:

• EBoard.
• Code related to the STUPID parser.

Notes:

• Don't forget about the Math/CS journal club today at 4:30.
• Tomorrow's convo looks to be quite interesting.
• The focus of today is answering questions about your parsers.

Overview:

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

Building Your Parser

• Create your tables.
• 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.
• Add

     if ((tok == s0) || (tok == s1) || ... || (tok == sk)) {
       translation of rhs
     }
  

• If rhs is nullable, identify the symbols in Follow[n]. Assume t0 ... tl.
• Add

    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.