Assignment 3 Solution

Microproject
Begin with the code from the page on recursive descent vs. parser combinators. Make a selection of using either recursive descent or parser combinators (or, try both and see which you prefer).  That program implements parsers for the following grammar:
1
2
  E -: T + E | T
  T -: Const | Var

It also implements an evaluation function for parse trees in that grammar. Modify the program to implement the following, modified grammar:
1
2
3
  E -: T + E | T
  T -: F * T | F
  F -: Const | Var

Be sure the parser works as well as the evaluation component. You will need to modify the case classes, the parser, and the evaluation function.
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 except for matching the individual alphanumeric characters, if you’d like. For example:
1
2
3
4
5
6
7
8
9
10
11
12
13
pattern? ((h|j)ell. worl?d)|(42)
string? hello world
match
string? jello word
match
string? jelly word
match
string? 42
match
string? 24
no match
string? hello world42
no match

Bootstrap
An ambiguous grammar for patterns is:
1
2
  E -: C | EE | E'|'E | E'?' | '(' E ')'
  C -: '0' | '1' | ... | '9'| 'a' | 'b' | ... | 'z' | '.'

To reflect that option(‘?’) has highest precedence, then concatenation, then alternation(‘|’), the following grammar may be used:
1
2
3
4
5
S  -: E$
E  -: T '|' E | T
T  -: F T | F
F  -: A '?' | A
A  -: C | '(' E ')'

For the purposes of writing a recursive descent parser specifically, this can be transformed into an ugly but simpler-to-use form:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
  S  -: E$
  E  -: T E2
  E2 -: '|' E3
  E2 -: NIL
  E3 -: T E2
  T  -: F T2
  T2 -: F T2
  T2 -: NIL
  F  -: A F2
  F2 -: '?' F2
  F2 -: NIL
  A  -: C
  A  -: '(' A2
  A2 -: E ')'

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 of case classes from the input string, or use Scala’s parser combinators to do the same. Remember not to use any regular expression processing other than for the individual characters (either built in or in external libraries)! You may alter the grammar if it makes the program easier to implement, but you must maintain all functionality and precedence levels.
Note: As of Scala 2.11 parser combinators are in an external library, so you may need the jar file for Scala 2.12.
Some Helpful Resources
Scala Recursive Descent vs. Parser Combinators
Approaches to Designing Case Classes for a Grammar
Scala Parser Combinators: Getting Started
A More Complex Parser Combinators Example
Scala Pattern Matching Documentation