"Warmup" Programming Assignments

Choose one or more of the following and implement in a language of your choice.

1. Parse a simple language. Write a program to accept or reject strings in the language with the following production rules.
   • L -> (L)L
     L -> [L]L
     L -> lambda
     (lambda means the empty string)
   • Examples:
     • () accepts
     • ()) rejects
     • ([]) accepts
     • ([)] rejects
     • ([(([]))]) accepts
     • empty string accepts

2. Download these Prolog programs: permute.pl, maze.pl, maze2.pl, and parse.pl

3. Run each program and understand what each is doing, how it is working. This will be explained in class.
   Use "prolog" for Gnu-Prolog
   consult('file.pl'). This loads the file into Prolog.
   See sample Prolog queries listed below. Try each, and make up some of your own.

4. Implement permute, maze2.pl, and/or parse.pl in a language of your choice.

More detail:

| ?- consult(permute).   This loads the file permute.pl

| ?- permute([a,b,c], X).
X = [a,b,c] ? ;   The semicolon means "search for another solution"
X = [b,a,c] ? ;
X = [b,c,a] ? ;
X = [a,c,b] ? ;
X = [c,a,b] ? ;
X = [c,b,a] ? ;
(10 ms) no      The "no" means there are no more solutions
| ?- 

Here's a map of the maze:

   ---------------------------
   |          |              |
   |     d           c       | 
   |          |              |
   -----   ----------   -----
   |   |      |              |
   |   |      |              |
   |   |      |              |  
   | f     e          b            a
   |   |      |              |
   |   |      |              |
   -------   -----------------
   |          |
   |     g    |
   |          |
   |          |
   -----------

Room g currently has the phone.
Problem: How do you travel from room a to whichever room has the phone?

sentence --> noun_phrase, verb_phrase.
noun_phrase --> determiner, noun.
verb_phrase --> verb, noun_phrase.
verb_phrase --> verb.
determiner --> [the].
noun --> [apple].
noun --> [man].
verb --> [eats].
verb --> [sings].

Problem: Determine whether a given input stream is a valid sentence.
Ex. the man eats the apple YES
    the apple eats the man  YES
    man eats apple NO
    the man eats apple NO

1. Sample Prolog queries for maze.pl:
   • ?-go(a,X,[]), hasphone(X).
     Reports yes/no if you can travel from a to room X and X has a phone.
   • ?-go(a,X,[d,e]).
     Reports which rooms you can go to from a without going through d and e
   • ?-go(a,g,[d,e]).
     Reports yes/no if you can go from a to g without going through d and e
2. Sample Prolog queries for maze2.pl:
   • ?-go(a,X,Route), hasphone(X).
     Gives the Route (in reverse) from a to room X and X has a phone.
   • ?-go(a,g,Route).
     Reports the Route from a to g
3. Sample Prolog queries for parse.pl
   • ?-sentence([the,man,eats,the,apple],[]).
     Returns yes
   • ?-sentence([the,man,eats,the,apple],[]).
   • ?-sentence([the,apple,sings,the,man],[]).
     Returns yes
   • ?-sentence([man,eats,the,apple],[]).
     Returns no
   • ?-sentence([the,man,eats,apple],[]).
     Returns no