Shift-Reduce Grammar Rules

Paraphrased Production Rules for Shift-Reduce Parser

This file contains English paraphrases of the production rules you should use to create a shift-reduce parser for Part A of Assignment 2. The rules are grouped into four broad categories to help in coding and debugging.

You will need to make your own decisions about how to represent elements in working memory and the rules that match against them. We have written the paraphrases to suggest list structures you may want to utilize, but do not feel limited by them. You may use whatever knowledge structures you like, providing you organize them into the rules given and providing they produce the correct parse tree for each test sentence. However, it seems likely that you will need one element in working memory for the stack and one for the buffer. The rules should include conditions that match against these elements and that replace them with updated versions upon firing.

When reading the paraphrased rules, it should be clear from context that some terms correspond to pattern-match variables. For example, the string "word" in the third rule, create-VP-in-S-for-V, refers to such a variable. The use of lower case here contrasts with Prolog's convention of denoting variables in capital letters, so be careful to keep the two notations distinct. Also note that many rules refer to variables which match against either the first element or the tails of lists.

Although most of these rules have mutually exclusive conditions, one of them (the "fail" rule in the final group) has very general conditions that will match on every cycle. Since this is a default rule that should fire only if no others match, it is important that you add it to production memory last; this will cause the interpreter to prefer other rules when their conditions are satisfied.

Rules for parsing verb phrases

create-VP-in-S-for-V
If the first element of the stack is a list that starts with S,
   and the first element of the buffer is word,
   and word is a VERB,
   and the first element of the stack contains the symbol NP, 
then insert a list containing the symbol VP at the start of the stack. 

create-VP-in-S-for-AUX
If the first element of the stack is a list that starts with S,
   and the first element of the buffer is word,
   and word is an AUXILIARY word,
   and the first element of the stack contains the symbol NP, 
then insert a list containing the symbol VP at the start of the stack. 

attach-AUX-and-V-to-VP
If the first element of the stack is a list that starts with VP,
   and the first element of the buffer is word1 and the second element is word2,
   and word1 is an AUXILIARY word,
   and word2 is a VERB,
then add a list with the symbol AUX followed by word1, followed by a list with the 
         symbol VERB followed by word2, at the end of the stack's first element,
   and remove the first and second element from the buffer.

attach-V-to-VP
If the first element of the stack is a list that starts with VP,
   and the first element of the buffer is word,
   and word is a VERB,
then add a list with the symbol VERB followed by word to the end of the stack's 
         first element,
   and remove the first element from the buffer.

attach-NP-to-VP
If the first element of the stack is a list that starts with VP,
   and the first element of the buffer is a list that starts with NP,
then add the first element of the buffer to the end of the first element of the stack,
   and remove the first element from the buffer.

create-NP-in-VP-for-D
If the first element of the stack is a list that starts with VP,
   and the first element of the buffer is word,
   and word is a DETERMINER,
then insert a list containing the symbol NP at the start of the stack.

create-NP-in-VP-for-N
If the first element of the stack is a list that starts with VP,
   and the first element of the buffer is word,
   and word is a NOUN,
then insert a list containing the symbol NP at the start of the stack.

create-NP-in-VP-for-ADJ
If the first element of the stack is a list that starts with VP,
   and the first element of the buffer is word,
   and word is an ADJECTIVE,
then insert a list containing the symbol NP at the start of the stack.

attach-VP-to-S
If the first element of the stack is a list that starts with S,
   and the first element of the buffer is a list that starts with VP, 
then add the buffer's first element to the end of the stack's first element,
   and remove the first element from the buffer.

Rules for parsing noun phrases

create-NP-in-S-for-N
If the first element of the stack is a list that starts with S,
   and the first element of the buffer is word,
   and word is a NOUN, 
then insert a list containing the symbol NP at the start of the stack.

create-NP-in-S-for-D
If the first element of the stack is a list that starts with S,
   and the first element of the buffer is word,
   and word is a DETERMINER, 
then insert a list containing the symbol NP at the start of the stack.

attach-NP-to-S-for-V
If the first element of the stack is a list that starts with S,
   and the first element of the buffer is a list that starts with NP, 
   and the second element of the buffer is word, 
   and word is a VERB,    
then add the buffer's first element to the end of the stack's first element,
   and remove the first element from the buffer. 

attach-NP-to-S-for-AUX
If the first element of the stack is a list that starts with S,
   and the first element of the buffer is a list that starts with NP, 
   and the second element of the buffer is word, 
   and word is an AUX,    
then add the buffer's first element to the end of the stack's first element,
   and remove the first element from the buffer. 
       
attach-N-to-NP
If the first element of the stack is a list that starts with NP,
   and the first element of the buffer is word,
   and word is a NOUN,
then add a list with the symbol NOUN followed by word to the end of the 
         stack's first element,
   and remove the first element from the buffer.

attach-D-to-NP
If the first element of the stack is a list that contains only the symbol NP,
   and the first element of the buffer is word,
   and word is a DETERMINER,
then add a list consisting of the symbol DETERMINER followed by word to the 
         end of the stack's first element,
   and remove the first element from the buffer.

drop-NP-for-V
If the first element of the stack is a list that starts with NP,
   and the first element of the buffer is word,
   and word is a VERB,
   and the first element of the stack contains the symbol NOUN,
then insert the first element of the stack at the start of the buffer,
   and remove the first element from the stack.

drop-NP-for-AUX
If the first element of the stack is a list that starts with NP,
   and the first element of the buffer is word,
   and word is an AUXILIARY word,
   and the first element of the stack contains the symbol NOUN,
then insert the first element of the stack at the start of the buffer,
   and remove the first element from the stack.

drop-NP-for-D
If the first element of the stack is a list that starts with NP,
   and the first element of the buffer is word,
   and word is a DETERMINER,
   and the first element of the stack contains the symbol NOUN,
then insert the first element of the stack at the start of the buffer,
   and remove the first element from the stack.

Rules for parsing adjective phrases

create-NP-in-S-for-ADJ
If the first element of the stack is a list that starts with S,
   and the first element of the buffer is word, 
   and word is an ADJECTIVE,
then insert a list containing the symbol NP at the start of the stack.

create-AP-in-NP-for-ADJ
If the first element of the stack is a list that starts with NP,
   and NOUN is not contained in the first element of the stack, 
   and the first element of the buffer is word, 
   and word is an ADJECTIVE,
then insert a list containing the symbol AP at the start of the stack.

attach-ADJ-to-AP
If the first element of the stack is a list that starts with AP,
   and the first element of the buffer is word, 
   and word is an ADJECTIVE,
then add a list with the symbol ADJ followed by word to the end 
         of the stack's first element,
   and remove the first element from the buffer.

drop-AP-for-N
If the first element of the stack is a list that starts with AP,
   and the first element of the buffer is word,
   and word is a NOUN,
   and the first element of the stack contains the symbol ADJ,
then insert the first element of the stack at the start of the buffer,
   and remove the first element from the stack.

attach-AP-to-NP
If the first element of the stack is a list that starts with NP,
   and NOUN is not in the first element of the stack, 
   and the first element of the buffer is a list that starts with AP,
then add the first element of the buffer to the end of the first element of the stack,
   and remove the first element from the buffer.

create-NP-in-PP-for-A
If the first element of the stack is a list that starts with PP,
   and the first element of the buffer is word, 
   and word is an ADJECTIVE,
then insert a list containing the symbol NP at the start of the stack.

Miscellaneous rules

drop-node-into-empty-buffer
If the first element of the stack is a list that does not contain S,
   and the buffer is empty,
then insert the first element of the stack at the start of the buffer.
   and remove the first element of the stack,

successful-parse
If the only element of the stack is a list that starts with S,
   and the buffer is empty,
then print the parse tree as output, 
   and remove the element from the stack
   and end the run and reset the system. 

ask-for-input
If the stack is empty,
   and the buffer is empty
then ask the user for a new sentence, 
   and obtain a sentence from the user, 
   and add the list containing S to the stack,
   and add the input from the user to the buffer.

failed-parse
If the stack contains anything,
then write-out as output a message that the parse failed,
   and remove what is left in the stack,
   and reinitialize the buffer, 
   and end the run and reset the system.