Assignment 8 "Lite": Parsing and Prolog!
Due Monday, October 24 by 11:59 PM

Please remember to complete the on-line mid-semester course evaluation before you submit this assignment. Thank you!

This assignment has three parts. In the first part, you will implement a recursive descent parser for a small "language". In the second and third parts, you will have a chance to start playing with Prolog.

Part 1: Recursive Descent Parsing (35 Points)

S -> P + S | P
P -> E * P | E
E -> U ^ E | U
U -> ( S ) | - V | V
V -> '0' | ... | '9'

1. A parse tree, a tree of operations and variables that reflects the computational structure of the input expression as we demonstrated in class.
2. A residue list, a list of characters (tokens) that have not yet been parsed.

Note that the first element in each case will be a parse tree, and the second element will be the residue list. If the parsing was successful, the residue will be the empty list.

From our experience, a good way to approach this problem is to first build a parser for a simplified version of this grammar. For example, you might begin with the grammar:

S -> P + S | P
P -> E * P | E
E -> V
V -> '0' | ... | '9'

Note that in the full grammar, the rules for variable U are a little different from the other rules, in that they handle parentheses and negation. Think about these rules! While they seem a bit strange, they actually are "easier" for the parser than the other rules!

Here's an example of how your parse function will behave once you have implemented the full grammar. Notice that in the first two examples, the residue is empty because parsing was successful. The third example did not succeed in parsing because the input was malformed.

rex > parse("1+2^3");
[[+, 1, [^, 2, 3]], []]

rex > parse("(1+2)^3+-4");
[[+, [^, [+, 1, 2], 3], [-, 4]], []]

rex > parse("1+2*+3");
[[+, 1, [*, 2, Error]], [BADTOKEN, 3]]

Once you have successfully written your recursive descent parser, implement an Evaluate function and whatever other helper functions you need. Evaluate takes as input an arithmetic expression (with addition and multiplication and one digit numbers) and returns its arithmetic value. For example, here is how your Evaluate function should behave.

rex > Evaluate("1+2^4");
17

rex > Evaluate("1*2+3");
5

3 rex > Evaluate("1+");
Bad Input

rex > make_number('4');
4

rex > 1 + make_number('2');
3

Remember to place all of your code for this part of the assignment in a file called part1.rex.

For 5 extra credit points augment your grammar, parser and evaluator to permit the use of multi-digit numbers as input. For example, we could ask Evaluate("(60+42)+-1"). If you do this bonus, make sure to put a comment in the first line of your part1.rex file stating that "THIS SUBMISSION HANDLES THE BONUS PROBLEM".

Part 2: Playing with Prolog! (15 Points)

• grandparent(X, Y) is true if and only if X is a grandparent of Y.
  
  
• cousins(X, Y) is true if and only if X and Y are first cousins. Note that a person cannot be their own cousin. Also, do not consider brothers and sisters to be cousins for this problem.
  
  
• hasYS(X) is true if and only if X has a younger sister. (Consider "younger" to mean strictly younger in age.)
  
  

Part 3: Lists in Prolog (25 Points)

• reverse(X, Y) is true if and only if list Y is the reversal of list X. Notice that you can use this rule to now actually compute the reversal R of a list by typing, for example, reverse([1, 2, 3], R). Make sure this works.
  
  
• occurs(X, L, N) is true if and only if item X occurs in list L exactly N times. Here is an example:

        | ?- occurs(spam, [oh, spam, spam, we, love, spam], X).
  
        X = 3 ;
        no
      

  When writing this predicate, be careful that it "computes" exactly the correct number of occurences (an easy pitfall is to write a version of this function that returns all values of X less than or equal to the number of occurences). Also, your occurs predicate should be able to generate the terms that occur a particular number of times, e.g.,

        | ?- occurs(T, [oh, spam, spam, we, love, spam], 3).
  
        T = spam ;
        no
      




• One-dimensional pattern matching is an important task in many applications such as cryptography and DNA sequencing. We'll encode a pattern as a list of items and we'll search for a pattern in another list called the "target". The rule find(Pattern, Target, Index) takes two lists Pattern and Target and a non-negative integer Index as input. This rule is true if and only if Pattern occurs inside list Target beginning at position Index. For example, here is a Prolog query and response:

        | ?- find([1, 2], [1, 2, 1, 2, 1], 0).
        yes
      

  Notice that pattern [1, 2] occurs in target [1, 2, 1, 2, 1] beginning at position 0 of the target (that is, the very beginning of the target list).

      [1, 2, 1, 2, 1]
       ^
       |
       The pattern [1, 2] appears beginning right here at location 0.
       I'm looking for a 1 followed immediately by a 2 and I find it
       beginning here!
      

  It also occurs again at position 2 of the target.

      [1, 2, 1, 2, 1]
             ^
             |
             The pattern [1, 2] appears beginning right here at location
      2.
      

  Thus, here's another Prolog query and response:

        | ?- find([1, 2], [1, 2, 1, 2, 1], 2).        
        yes
      

  In fact, these are the only two occurences as indicated by the following Prolog query and response:

        | ?- find([1, 2], [1, 2, 1, 2, 1], X).   
  
        X = 0 ;
        X = 2 ;
        no
      

  find(P,T,I) should also work when both P and I are unbound variables. Write the rules for find. Submit your code in a file named part3.pl.