The various parsers in this chapter are all deterministic simulations of a particular kind of non-deterministic pushdown automaton associated with context-free grammars. There are three well-known types of non-deterministic pushdown automata for CFGs that are used as bases of parsing: top-down, bottom-up, and left-corner (see here for more information). The one that's used here is the top-down variety, and the corresponding parsing method is also called "recursive descent". It is particularly natural in the context of functional programming. (Note that the term "stack-based" is often used to describe parsing based on NPDA.)
Well-known disadvantages of recursive descent parsing are its exponential time complexity and non-termination in the face of left recursion. Johnson (1995) addresses both issues in relation to implementations using functional programming.
The implementation of the recursive-descent parser for sequentially indexed grammars given in the text is incorrect. The list of expected empty categories gets passed (i) top-down from a node to its first child; (ii) left-to-right from a node to its immediate right sibling; and (iii) bottom-up from a node with no right sibling to its parent. This allows binding of an empty category (trace) by a relative pronoun anywhere to its left, whether or not the relative pronoun "c-commands" the empty category.
*P> parses "the boy that Alice smiled helped" [[.S[Masc,Sg,Thrd] [[.NP[Masc,Sg,Thrd,Nom] [the DET,[.CN[Sg,Masc,Thrd] [boy CN[Sg,Masc,Thrd],[.COMP [that REL,[.S[Thrd,Fem,Sg] [alice NP[Fem,Sg,Thrd,Nom],[.VP[Tense] [smiled VP[Tense]]]]]]]]]]],[.VP[Tense] [helped VP[Tense],# NP]]]]]This implementation would actually be adequate for an unrestricted version of global index grammar (Castaño 2004).
splitN, but there is a dual solution that passes the list of "discovered" empty categories bottom-up. Discuss how one method may be more efficient than the other. Note that in both approaches, you have to change the type of the stack parser.)
*P> parses "the boy that if smiled, then Alice smiled smiled" [[.S[Masc,Sg,Thrd] [[.NP[Masc,Sg,Thrd,Nom] [the DET,[.CN[Sg,Masc,Thrd] [boy CN[Sg,Masc,Thrd],[.COMP [that REL,[.S [if COND,[.S [# NP[Nom],[.VP[Tense] [smiled VP[Tense]]]]],[.S[Thrd,Fem,Sg] [alice NP[Fem,Sg,Thrd,Nom],[.VP[Tense] [smiled VP[Tense]]]]]]]]]]]]],[.VP[Tense] [smiled VP[Tense]]]]]]
*P> parses "if the boy helped Alice and Alice smiled, then the boy admired Alice" 
"the boy that helped Alice and Alice smiled admired Alice". Implement the Coordinate Structure Island Constraint, by which such sentences are ruled out.
"the boy that helped Alice and admired Dorothy smiled"get parsed. This is known as Across-the-Board extraction.
Back to the seminar main pageMakoto Kanazawa
Last modified: 2017-04-06 19:08:12 JST