Chapter 4: Grammars and Parsing

Getting Started (5 minutes)

• Review the Studio Guidelines if necessary.
• Locate and install the studio4 project into your eclipse workspace as directed by your instructor, following the usual instructions.
• Open report.txt in eclipse, fill in your team members' names, and keep the file open so that you can record your findings.
• Browse this studio document to get an idea of the work you will do in this session.

In this studio you develop the analysis necessary to create recursive-descent parsers in the Chapter 5 studio.

Setup (15 minutes)

1. Fill in the group's members' names in the Main.java file.
2. Although eclipse will show many errors, do not worry about them. You won't be running or compiling any programs in this studio. The file you complete will be copied into Studio 5.
3. Open your book open to Chapter 4, pages 130–137, to have handy the algorithms for computing First and Follow sets.
4. Discuss the First and Follow algorithms in your group as you try them on grammars provided by your instructor.

Main Problems

A series of grammars is presented in Main.java, found in the studio4 package. For each grammar, you will compute the First and Follow sets for each of the grammar's nonterminal symbols.

All of your work is given and can be done in the Main.java file. The information here is supplemental.

Type in your First and Follow set solutions as indicated in the Main.java file.

Part 1 (10 minutes)

Compute First and Follow sets for the nonterminals in each of the following grammars:
1. MatchingParens
2. Problem1a (from page 173 of the text, but the grammar is included in Main.java)
3. Problem1d (from page 173 of the text, but the grammar is included in Main.java)

Part 2 (10 minutes)

Compute First and Follow sets for the nonterminals in each of the following grammars:
1. Declarations
2. IfThenElseFi

Part 3 (10 minutes)

Compute First and Follow sets for the nonterminals in the following grammar:
• Expressions

Part 4 (time permitting)

Compute First and Follow sets for the nonterminals in the following grammar:
• IfThenElse Do not implement a parser for this grammar, just try to make the grammar suitable for top-down parsing.