Hi There!

I'm Dan Schlegel, an Associate Professor in the Computer Science Department at SUNY Oswego

Assignment 3

Microproject

Begin with the code from the class example on recursive descent parsers in Scala. That program implements a parser for the following grammar:

It also implements evaluation for parse trees in that grammar. Modify the program to implement the following, modified grammar:

Be sure the parser works as well as the evaluation component. You will need to modify the case classes, the parser, and the evaluation.

Main Project

Write a Scala program that performs pattern matching on strings, where patterns are expressed using only the concatenation, alternation (“|”), and optional (“?”) operators of regular expressions (no loops/”*”, no escape characters), and the tokens are letters and digits, plus period (“.”) to mean any letter. Each run of the program should accept a pattern, and then any number of strings, reporting only whether they match. Your program should represent expressions as trees (use case classes) and evaluate on the inputs, without using any regular expressions or Scala’s regular expression library except for matching the individual alphanumeric characters, if you’d like. For example:

Bootstrap

An ambiguous grammar for patterns is:

To reflect that option(‘?’) has highest precedence, then concatenation, then alternation(‘|’), the following unambiguous grammar can be created:

For the purposes of writing a recursive descent parser, this can be transformed into an ugly but simpler-to-use form:

where ‘$’ is eof/end-of-string, and NIL means empty (which in these productions means take the rhs only if others do not apply).

Use the following case classes to get you started. You will need several more, but you should be able to deduce the general pattern from these:

You must implement a recursive descent parser yourself to build a tree of case classes from the input string. Remember not to use any regular expression processing other than for the individual characters (either built in or in external libraries)!

Some Helpful Resources

Scala Pattern Matching Documentation

Suggested Development Environment

IntelliJ + Scala Plugin