CIS-4050 Homework #3 (Recursive Descent)

Due: Friday, March 22, 2019

Review Chapter 3 in the text.

In this assignment you will be asked to implement a parser for part of the Phoebe pseudo-code interpreter. You first need to obtain the Phoebe source code using Git. The clone URL is: You will find an IntelliJ project already defined (you can probably also clone the Phoebe code base from inside IntelliJ).

The ultimate goal of this assignment is create a recursive descent parser for a subset of the pseudo-code grammar defined in pcode-grammar.txt in the Phoebe repository. The grammar of interest starts at program and consists of a function_list made up of only a statement_list. You can ignore the declare_block and function grammar. For statements you should support EP statements, RETURN statements, if statements, while statements, and repeat statements. You should also fully support the grammar of conditional_expr. This is sufficient to parse the bubble.pcd example given in the examples folder.

Roughly the assignment entails completing the method parse in the main file so that it returns an appropriate parse tree. The main method then prints that parse tree for inspection. It will likely also be necessary to make some transformations to the grammar to remove left recursion, etc. This will entail making corresponding changes to TreeNode.scala.

You'll need to add a method to output error messages. If you want to write a more purely functional style, this would be handled by having the various parsing methods return a list of error messages as part of the information they send back to their callers. This list would also have to be handed into each method as a parameter. Thus the list of error messages would grow as the parsing continues. The final parse tree would be a "best guess" based on error recovery actions in the methods. You don't need to get this fancy for this assignment, but I invite you to try it if yo are feeling adventurous.

Submit your modified files in a zip archive to Moodle.

Last Revised: 2019-03-03
© Copyright 2019 by Peter C. Chapin <>