Hi There!

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

CSC344 – Assignment 3

Microproject

Write a Scala program which reads a string from the user, and uses either a recursive descent parser or parser combinators to determine if the input string matches the below grammar (i.e., is made up of a’s and b’s), building a parse tree along the way. Output the generated tree if the match is successful.

Read the below project description for assistance.

Main Project

Write a Scala program that performs pattern matching on strings, where patterns are expressed using only the concatenation, alternation (“|”) 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. For example:

Bootstrap

An ambiguous grammar for patterns is:

To reflect that option(‘?’) has highest precedence, then concatentation, then alternation(‘|’), 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).

You may decide to implement a recursive descent parser yourself to build a tree from the input string, or use Scala’s parser combinators to do the same (see Blackboard for a chapter on this topic). Remember not to use any regular expression processing (either built in or in external libraries)!

Note: As of Scala 2.11 parser combinators are in an external library, so you may need the jar file.

Suggested Development Environment

Eclipse + Scala IDE