Lab: A Sample Parser

Summary: You are currently working on predictive parsers for Pascal. In this laboratory, you will explore the design of a predictive parser for a simple language.

Contents:

• Preliminaries
• Background
• Exercises
  • Exercise 0: Preparation
  • Exercise 1: The Grammar
  • Exercise 2: Parsing Statements
  • Exercise 3: Adding Procedure Calls
  • Exercise 4: Parsing Terms
  • Exercise 5: Improving write

Preliminaries

Collaboration: Feel free to work on this lab in pairs or trios.

Turning It In: Don't worry about it.

Background

As you may recall from our discussion in class, the basic model of predictive parsing is that you do a top-down derivation of the input string by repeatedly expanding the next nonterminal to the appropriate right hand side, where the right-hand side is determined by the next input token.

In practice, there are two main ways to implement predictive parsers: You can automatically build tables related to the grammar or you can hand-code a parser based on the grammar. With a hand-coded parser, you write a parse function for each nonterminal, in which the function examines the next input symbol and then calls an appropriate sequence of procedures that correspond to the right-hand side.

Hand-coded parsers have many advantages. For example, you can return a different nonterminal than you match (useful when you've modified the grammar to elminate ambiguity but don't want the extra nodes such disambiguation creates). You can also use a number of special tricks, such as dealing with repetitions in the grammar, which Wirth represents with curly braces.

Exercises

Exercise 0: Preparation

a. Make a copy of the files for today's lab with

cvs -d  /home/rebelsky/Web/Courses/CS362/2004S/CVS checkout Lab06

b. Update your CLASSPATH to include /home/rebelsky/Web/Courses/CS362/2004S/Examples/. Here's one command that works (and that you might want to add to your .bashrc).

export CLASSPATH="$CLASSPATH:/home/rebelsky/Web/Courses/CS362/2004S/Examples/"

c. Compile StupidParser.java.

d. Ask StupidParser to parse expressions.stupid.

Exercise 1: The Grammar

Familiarize yourself with the STUPID grammar, which appears as a comment at the beginning of StupidParser.java.

a. Make a note of any aspects you find surprising.

b. Explain the difference between expressions, simple expressions, terms, and factors.

Exercise 2: Parsing Statements

Determine how parseStatement determines what right hand side to match.

a. What aspects of the code, if any, correspond to what you've learned about predictive parsers?

b. What aspects of the code, if any, fail to correspond?

c. Explain the following code, which appears in the middle of parseStatement.

    else if (tok == StupidTokens.TSEMI) {
      tokens.next();
      return null;
    }

Exercise 3: Adding Procedure Calls

Suppose we decide to permit procedure calls in STUPID (yes, we should also have procedure definitions, but we'll worry about those later). One way to define procedure calls is

procedure-call ::= EQUALS GREATERTHAN ID OPENPAREN expression CLOSEPAREN

Note that the call begins with an arrow (=>).

a. Write parseProcedureCall.

b. Update parseStatement to call parseProcedureCall when appropriate.

c. Why do you think I had procedure calls begin with an arrow rather than just with the procedure name (the ID)?

d. Try rewriting parseStatement so that it handles procedure calls without the arrow.

Exercise 4: Parsing Terms

The grammar we wrote for expressions had the following definition for terms had the following form:

term ::= term MULOP factor
term ::= factor

Unfortunately, that portion of the grammar is left recursive. As you may have noted from the grammar for STUPID, we use the following instead.

term ::= factor { MULOP factor }

a. Explain how parseTerm implements this rule.

b. Explain the programming strategy that permits parseTerm to treat multiplicative operations as left recursive.

Exercise 5: Improving write

Rewrite write and writeln so that they can take lists of expressions (separated by commas) as parameters, rather than single expressions. You will probably need to create a parseExpressionList procedure to help.