Recollecting Parsing

You must be aware of what precisely it means to 'parse' something. In technical terms, you are verifying the string's membership to a language. In other words, if w is the string you are parsing, you are trying to answer
"Does w belong to the language L?"
by checking the lexicon and the grammar rules of L.

For example, the language L you used for your C arithmetic parser is L = {e | e is a valid arithmetic expression}. The lexicon consisted of numbers, operators, parentheses, etc. The grammar rules consisted of specifications that looked like expr --> expr (+,-) term (disregarding the left recursion issue for now). With this language defined, if you parse the input (4 + 6) * 3,, you should succeed at the end of parsing because it is correct, whereas if you parse the input )4(8+ (wrong grammar) or (@ + ~) * Q (wrong words), you should fail.

In this exercise the language is a subset of grammatical English sentences. actual minimal grammar and lexicon for this assignment given below. The lexicon thus consists of words like boy, the, likes, and Rochester, with types like noun, determiner, verb, and proper_noun, respectively. The grammar rules dictates how a grammatical sentence is formed, as in sentence --> noun_phrase verb_phrase, noun_phrase --> determiner noun | proper_noun, and verb_phrase --> verb noun_phrase. Note that even with this simple lexicon and grammar, we can already parse the sentence "the boy likes Rochester":

			   sentence
			   /      |
                    noun_phrase   verb_phrase
                     /      |        /     |
                determiner noun   verb   noun_phrase
                    |        |      |          |
                   the      boy    likes    proper_noun
                                                 |
                                               Rochester
So this is a grammatical English sentence (according to the grammar and lexicon above). This parse tree is equivalent to the list form for a Prolog structure:
sentence(noun_phrase(determiner(the), noun(boy)),
         verb_phrase(verb(likes), noun_phrase(proper_noun(Rochester))).

In this project we use the parse tree in a nontrivial way -- we need to know more than "grammatical or not?". We generally build a parse tree when parsing. Strictly speaking, the parsing itself doens't have anything to do with tasks other than checking the membership of the given input to a language. But, not surprisingly, parsing a string reveals a lot about the syntactic structrue of the string with regards to the grammar used in parsing, and that structure is often helpful in further processing the string, such as trying to interpret its meaning (i.e., semantics). My analogy using a frog is that parsing is like dissecting the frog (to verify it really is a frog), building a parse tree is like recording the internal structure of the frog (to precisely know which is where), and doing something with a parse tree is like trying to use the information gained from the dissection for further research (perhaps to develop a frogman).