12.8.2 Treebanks for Spoken Language
Treebanks for spoken corpora like Switchboard use an augmented notation to deal with spoken language phenomena like disfluencies. Fig. 12.19 shows the parse tree for Switchboard sentence (12.18). This sentence shows how the Treebank marks disfluencies; square brackets are used to separate out the entire repair area, including the reparandum, editing phase, and the repair. The plus symbol marks the end of the reparandum.
(12.18) But I don't have [ any, + {F uh, } any ] real idea
12.9 GRAMMARS AND HUMAN PROCESSING
Do people use context-free grammars in their mental processing of language? It has proved very difficult to find clear-cut evidence that they do. For example, some early experiments asked subjects to judge which words in a sentence were more closely connected (Levelt, 1970), finding that their intuitive groupings corresponded to syntactic constituents. Other experimenters examined the role of constituents in auditory comprehension by having subjects listen to sentences while also listening to short “clicks” at different times. Fodor and Bever (1965) found that subjects often mis-heard the clicks as if they occurred at constituent boundaries. They argued that the constituent was thus a “perceptual unit” which resisted interruption. Unfortunately there were severe methodological problems with the click paradigm (see e.g., Clark and Clark (1977) for a discussion).
A broader problem with all these early studies is that they do not control for the fact that constituents are often semantic units as well as syntactic units. Thus, as will be discussed further in Ch. 18, a single odd block is a constituent (an NP) but also a semantic unit (an object of type BLOCK which has certain properties). Thus experiments which show that people notice the boundaries of constituents could simply be measuring a semantic rather than a syntactic fact.
Thus it is necessary to find evidence for a constituent which is not a semantic unit. Furthermore, since there are many non-constituent-based theories of grammar based on lexical dependencies, it is important to find evidence that cannot be interpreted as a lexical fact; that is, evidence for constituency that is not based on particular words.
One suggestive series of experiments arguing for constituency has come from Kathryn Bock and her colleagues. Bock and Loebell (1990), for example, avoided all these earlier pitfalls by studying whether a subject who uses a particular syntactic constituent (e.g., a verb-phrase of a particular type, like V NP PP), is more likely to use the constituent in the following sentences. In other words, they asked whether use of a constituent primes its use in subsequent sentences. As we saw in previous chapters, priming is a common way to test for the existence of a mental structure. Bock and Loebell relied on the English ditransitive alternation. A ditransitive verb is one like give which can take two arguments:
(12.19) The wealthy widow gave $ [NP\ the\ church] $ $ [NP\ her\ Mercedes] $.
The verb give allows another possible subcategorization frame, called a prepositional dative in which the indirect object is expressed as a prepositional phrase:
The wealthy widow gave $ [NP\ her\ Mercedes] $ [PP to the church].
As we discussed on page 18, many verbs other than give have such alternations (send, sell, etc.; see Levin (1993) for a summary of many different alternation patterns). Bock and Loebell relied on these alternations by giving subjects a picture, and asking them to describe it in one sentence. The picture was designed to elicit verbs like give or sell by showing an event such as a boy handing an apple to a teacher. Since these verbs alternate, subjects might, for example, say The boy gave the apple to the teacher or The boy gave the teacher an apple.
Before describing the picture, subjects were asked to read an unrelated “priming” sentence out loud; the priming sentences either had V NP NP or V NP PP structure. Crucially, while these priming sentences had the same constituent structure as the da-tive alternation sentences, they did not have the same semantics. For example, the priming sentences might be prepositional locatives, rather than datives:
(12.21) IBM moved $ [_{NP} a\text{ bigger computer}] $ $ [_{PP} \text{ to the Sears store}] $.
Bock and Loebell found that subjects who had just read a VNP PP sentence were more likely to use a VNP PP structure in describing the picture. This suggested that the use of a particular constituent primed the later use of that constituent, and hence that the constituent must be mentally represented in order to prime and be primed.
In more recent work, Bock and her colleagues have continued to find evidence for this kind of constituency structure.
12.10 SUMMARY
This chapter has introduced a number of fundamental concepts in syntax via the context-free grammar.
In many languages, groups of consecutive words act as a group or a constituent, which can be modeled by context-free grammars (also known as phrase-structure grammars).
- A context-free grammar consists of a set of rules or productions, expressed over a set of non-terminal symbols and a set of terminal symbols. Formally, a particular context-free language is the set of strings which can be derived from a particular context-free grammar.
- A generative grammar is a traditional name in linguistics for a formal language which is used to model the grammar of a natural language.
There are many sentence-level grammatical constructions in English; declarative, imperative, yes-no-question, and wh-question are four very common types, which can be modeled with context-free rules.
- An English noun phrase can have determiners, numbers, quantifiers, and adjective phrases preceding the head noun, which can be followed by a number of postmodifiers; gerundive VPs, infinitives VPs, and past participial VPs are common possibilities.
• Subjects in English agree with the main verb in person and number.
Verbs can be subcategorized by the types of complements they expect. Simple subcategories are transitive and intransitive; most grammars include many more categories than these.
- The correlate of sentences in spoken language are generally called utterances. Utterances may be disfluent, containing filled pauses like um and uh, restarts, and repairs.
- Treebanks of parsed sentences exist for many genres of English and for many languages. Treebanks can be searched using tree-search tools.
- Any context-free grammar can be converted to Chomsky normal form, in which the right-hand-side of each rule has either two non-terminals or a single terminal.
- Context-free grammars are more powerful than finite-state automata, but it is nonetheless possible to approximate a context-free grammar with a FSA.
There is some evidence that constituency plays a role in the human processing of language.
BIBLIOGRAPHICAL AND HISTORICAL NOTES
“den sprachlichen Ausdruck für die willkürliche Gliederung einer Gesammtvorstellung in ihre in logische Beziehung zueinander gesetzten Bestandteile”
“the linguistic expression for the arbitrary division of a total idea into its constituent parts placed in logical relations to one another”
Wundt's (1900:240) definition of the sentence; the origin of the idea of phrasal constituency, cited in Percival (1976).
According to Percival (1976), the idea of breaking up a sentence into a hierarchy of constituents appeared in the Völkerpsychologie of the groundbreaking psychologist Wilhelm Wundt (Wundt, 1900). Wundt's idea of constituency was taken up into linguistics by Leonard Bloomfield in his early book An Introduction to the Study of Language (Bloomfield, 1914). By the time of his later book Language (Bloomfield, 1933), what was then called "immediate-constituent analysis" was a well-established method of syntactic study in the United States. By contrast, traditional European grammar, dating from the Classical period, defined relations between words rather than constituents, and European syntacticians retained this emphasis on such dependency grammars.
American Structuralism saw a number of specific definitions of the immediate constituent, couched in terms of their search for a “discovery procedure”; a methodological algorithm for describing the syntax of a language. In general, these attempt to capture the intuition that “The primary criterion of the immediate constituent is the degree in which combinations behave as simple units” (Bazell, 1966, p. 284). The most well-known of the specific definitions is Harris’ idea of distributional similarity to individual units, with the substitutability test. Essentially, the method proceeded by breaking up a construction into constituents by attempting to substitute simple structures for possible constituents—if a substitution of a simple form, say man, was substitutable in a construction for a more complex set (like intense young man), then the form intense young man was probably a constituent. Harris’s test was the beginning of the intuition that a constituent is a kind of equivalence class.
The first formalization of this idea of hierarchical constituency was the phrase-structure grammar defined in Chomsky (1956), and further expanded upon (and argued against) in Chomsky (1957) and Chomsky (1975). From this time on, most generative linguistic theories were based at least in part on context-free grammars or generalizations of them (such as Head-Driven Phrase Structure Grammar (Pollard and Sag, 1994), Lexical-Functional Grammar (Bresnan, 1982), Government and Bind-
ing (Chomsky, 1981), and Construction Grammar (Kay and Fillmore, 1999), inter alia); many of these theories used schematic context-free templates known as X-bar schemata which also relied on the notion of syntactic head.
Shortly after Chomsky's initial work, the context-free grammar was rediscovered by Backus (1959) and independently by Naur et al. (1960) in their descriptions of the ALGOL programming language; Backus (1996) noted that he was influenced by the productions of Emil Post and that Naur's work was independent of his (Backus') own. (Recall the discussion on page ?? of multiple invention in science.) After this early work, a great number of computational models of natural language processing were based on context-free grammars because of the early development of efficient algorithms to parse these grammars (see Ch. 13).
As we have already noted, grammars based on context-free rules are not ubiquitous. Various classes of extensions to CFGs are designed specifically to handle long-distance dependencies. We noted earlier that some grammars treat long-distance-dependent items as being related semantically but not syntactically; the surface syntax does not represent the long-distance link (Kay and Fillmore, 1999; Culicover and Jackendoff, 2005). But there are alternatives. One extended formalism is Tree Adjoining Grammar (TAG) (Joshi, 1985). The primary data structure in Tree Adjoining Grammar is the tree, rather than the rule. Trees come in two kinds; initial trees and auxiliary trees. Initial trees might, for example, represent simple sentential structures, while auxiliary trees are used to add recursion into a tree. Trees are combined by two operations called substitution and adjunction. The adjunction operation is used to handle long-distance dependencies. See Joshi (1985) for more details. An extension of Tree Adjoining Grammar called Lexicalized Tree Adjoining Grammars will be discussed in Ch. 14. Tree Adjoining Grammar is a member of the family of mildly context-sensitive languages to be introduced in Ch. 15.
We mentioned on page 21 another way of handling long-distance dependencies, based on the use of empty categories and co-indexing. The Penn Treebank uses this model, which draws (in various Treebank corpora) from the Extended Standard Theory and Minimalism (Radford, 1997).
Representative examples of grammars that are based on word relations rather than constituency include the dependency grammar of Mel'čuk (1979), the Word Grammar of Hudson (1984), and the Constraint Grammar of Karlsson et al. (1995).
There are a variety of algorithms for building a regular grammar which approximates a CFG (Pereira and Wright, 1997; Johnson, 1998; Langendoen and Langsam, 1987; Nederhof, 2000; Mohri and Nederhof, 2001).
Readers interested in the grammar of English should get one of the three large reference grammars of English: Huddleston and Pullum (2002), Biber et al. (1999), and Quirk et al. (1985). Another useful reference is McCawley (1998).
There are many good introductory textbooks on syntax from different perspectives. Sag et al. (2003) is an introduction to syntax from a generative perspective, focusing on the use of phrase-structure, unification, and the type-hierarchy in Head-Driven Phrase Structure Grammar. Van Valin and La Polla (1997) is an introduction from a functional perspective, focusing on cross-linguistic data and on the functional motivation for syntactic structures.
See Bach (1988) for an introduction to basic categorial grammar. Various extensions to categorial grammars are presented in Lambek (1958), Dowty (1979), and Ades and Steedman (1982) inter alia; the other papers in Oehrle et al. (1988) give a survey of extensions. Combinatory categorial grammar is presented in Steedman (1989, 2000); see Steedman and Baldridge (2003) for a tutorial introduction. See Ch. 18 for a discussion of semantic composition.
EXERCISES
12.1 Draw tree structures for the following ATIS phrases:
a. Dallas
b. from Denver
c. after five p.m.
d. arriving in Washington
e. early flights
f. all redeye flights
g. on Thursday
h. a one-way fare
i. any delays in Denver
12.2 Draw tree structures for the following ATIS sentences:
a. Does American airlines have a flight between five a.m. and six a.m.
b. I would like to fly on American airlines.
c. Please repeat that.
d. Does American 487 have a first class section?
e. I need to fly between Philadelphia and Atlanta.
f. What is the fare from Atlanta to Denver?
g. Is there an American airlines flight from Philadelphia to Dallas?
12.3 Augment the grammar rules on page 16 to handle pronouns. Deal properly with person and case.
12.4 Modify the noun phrase grammar of Sections 12.3.3–12.3.4 to correctly model mass nouns and their agreement properties
12.5 How many types of NPs would the rule on page 12 expand to if we didn't allow parentheses in our grammar formalism?
12.6 Assume a grammar that has many VP rules for different subcategorizations, as expressed in Sec. 12.3.5, and differently subcategorized verb rules like Verb-with-NP-complement. How would the rule for post-nominal relative clauses (12.7) need to be
modified if we wanted to deal properly with examples like the earliest flight that you have? Recall that in such examples the pronoun that is the object of the verb get. Your rules should allow this noun phrase but should correctly rule out the ungrammatical S *I get.
12.7 Does your solution to the previous problem correctly model the NP the earliest flight that I can get? How about the earliest flight that I think my mother wants me to book for her? Hint: this phenomenon is called long-distance dependency.
12.8 Write rules expressing the verbal subcategory of English auxiliaries; for example you might have a rule verb-with-bare-stem-VP-complement $ \rightarrow $ can.
12.9 NPs like Fortune's office or my uncle's marks are called possessive or genitive noun phrases. A possessive noun phrase can be modeled by treating the sub-NP like Fortune's or my uncle's as a determiner of the following head noun. Write grammar rules for English possessives. You may treat 's as if it were a separate word (i.e., as if there were always a space before 's).
12.10 Page 9 discussed the need for a Wh-NP constituent. The simplest Wh-NP is one of the Wh-pronouns (who, whom, whose, which). The Wh-words what and which can be determiners: which four will you have?, what credit do you have with the Duke? Write rules for the different types of Wh-NPs.
12.11 Write an algorithm for converting an arbitrary context-free grammar into Chomsky normal form.
Ades, A. E. and Steedman, M. (1982). On the order of words. Linguistics and Philosophy, 4, 517–558.
Adjukiewicz, K. (1935). Die syntaktische Konnexität. Studia Philosophica, 1, 1–27. English translation "Syntactic Connexion" by H. Weber in McCall, S. (Ed.) Polish Logic, pp. 207–231, Oxford University Press, Oxford, 1967.
Bach, E. (1988). Categorial grammars as theories of language. In Oehrle, R. T., Bach, E., and Wheeler, D. (Eds.), Categorial Grammars and Natural Language Structures, pp. 17–34. D. Reidel, Dordrecht.
Backus, J. W. (1959). The syntax and semantics of the proposed international algebraic language of the Zurch ACM-GAMM Conference. In Information Processing: Proceedings of the International Conference on Information Processing, Paris, pp. 125–132. UNESCO.
Backus, J. W. (1996). Transcript of question and answer session. In Wexelblat, R. L. (Ed.), History of Programming Languages, p. 162. Academic Press.
Bar-Hillel, Y. (1953). A quasi-arithmetical notation for syntactic description. Language, 29, 47–58. Reprinted in Y. Bar-Hillel. (1964). Language and Information: Selected Essays on their Theory and Application, Addison-Wesley 1964, 61–74.
Bar-Hillel, Y., Perles, M., and Shamir, E. (1961). On formal properties of simple phrase structure grammars. Zeitschrift für Phonetik, Sprachwissenschaft und Kommunikationsforschung, 14, 143–172. Reprinted in Y. Bar-Hillel. (1964). Language and Information: Selected Essays on their Theory and Application, Addison-Wesley 1964, 116–150.
Bazell, C. E. (1952/1966). The correspondence fallacy in structural linguistics. In Hamp, E. P., Householder, F. W., and Austerlitz, R. (Eds.), Studies by Members of the English Department, Istanbul University (3), reprinted in Readings in Linguistics II (1966), pp. 271–298. University of Chicago Press, Chicago.
Biber, D., Johansson, S., Leech, G., Conrad, S., and Finegan, E. (1999). Longman Grammar of Spoken and Written English. Pearson ESL, Harlow.
Bies, A., Ferguson, M., Katz, K., and MacIntyre, R. (1995). Bracketing guidelines for Treebank II style Penn Treebank Project.
Bloomfield, L. (1914). An Introduction to the Study of Language. Henry Holt and Company, New York.
Bloomfield, L. (1933). Language. University of Chicago Press, Chicago.
Bock, K. and Loebell, H. (1990). Framing sentences. Cognition, 35, 1–39.
Bresnan, J. (Ed.). (1982). The Mental Representation of Grammatical Relations. MIT Press.
Charniak, E. (1997). Statistical parsing with a context-free grammar and word statistics. In AAAI-97, Menlo Park, pp. 598–603. AAAI Press.
Chomsky, N. (1956). Three models for the description of language. IRI Transactions on Information Theory, 2(3), 113–124.
Chomsky, N. (1956/1975). The Logical Structure of Linguistic Theory. Plenum.
Chomsky, N. (1957). Syntactic Structures. Mouton, The Hague.
Chomsky, N. (1959). On certain formal properties of grammars. Information and Control, 2, 137–167.
Chomsky, N. (1963). Formal properties of grammars. In Luce, R. D., Bush, R., and Galanter, E. (Eds.), Handbook of Mathematical Psychology, Vol. 2, pp. 323–418. Wiley.
Chomsky, N. (1981). Lectures on Government and Binding. Foris, Dordrecht.
Clark, H. H. and Clark, E. V. (1977). Psychology and Language. Harcourt Brace Jovanovich.
Collins, M. (1999). Head-driven Statistical Models for Natural Language Parsing. Ph.D. thesis, University of Pennsylvania, Philadelphia.
Collins, M., Hajič, J., Ramshaw, L. A., and Tillmann, C. (1999). A statistical parser for Czech. In ACL-99, College Park, MA, pp. 505–512. ACL.
Culicover, P. W. and Jackendoff, R. (2005). Simpler Syntax. Oxford University Press.
Dowty, D. R. (1979). Word Meaning and Montague Grammar. D. Reidel, Dordrecht.
Fodor, J. A. and Bever, T. G. (1965). The psychological reality of linguistic segments. Journal of Verbal Learning and Verbal Behavior, 4, 414–420.
Fox, B. and Jasperson, R. (1995). A syntactic exploration of repair in English conversation. In Davis, P. (Ed.), Descriptive and Theoretical Modes in the Alternative Linguistics, pp. 77–134. John Benjamins, Amsterdam. In press.
Gazdar, G., Klein, E., Pullum, G. K., and Sag, I. A. (1985). Generalized Phrase Structure Grammar. Basil Blackwell, Oxford.
Hajič, J. (1998). Building a Syntactically Annotated Corpus: The Prague Dependency Treebank, pp. 106–132. Karolinum, Prague/Praha.
Halliday, M. A. K. (1985). An Introduction to Functional Grammar. Edward Arnold, London.
Harris, Z. S. (1946). From morpheme to utterance. Language, 22(3), 161–183.
Hemphill, C. T., Godfrey, J., and Doddington, G. (1990). The ATIS spoken language systems pilot corpus. In Proceedings DARPA Speech and Natural Language Workshop, Hidden Valley, PA, pp. 96–101. Morgan Kaufmann.
Hindle, D. (1983). Deterministic parsing of syntactic nonfluencies. In ACL-83, pp. 123–128. ACL.
Hopcroft, J. E. and Ullman, J. D. (1979). Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading, MA.
Huddleston, R. and Pullum, G. K. (2002). The Cambridge grammar of the English language. Cambridge University Press.
Hudson, R. A. (1984). Word Grammar. Basil Blackwell, Oxford.
Järvinen, T. and Tapanainen, P. (1997). A dependency parser for English. Tech. rep. TR-1, Department of General Linguistics, University of Helsinki, Helsinki.
Johnson, M. (1998). Finite-state approximation of constraint-based grammars using left-corner grammar transforms. In COLING/ACL-98, Montreal, pp. 619–623.
Joshi, A. K. (1985). Tree adjoining grammars: how much context-sensitivity is required to provide reasonable structural descriptions?. In Dowty, D. R., Karttunen, L., and Zwicky, A. (Eds.), Natural Language Parsing, pp. 206–250. Cambridge University Press.
Karlsson, F., Voutilainen, A., Heikkilä, J., and Anttila, A. (Eds.). (1995). Constraint Grammar: A Language-Independent System for Parsing Unrestricted Text. Mouton de Gruyter, Berlin.
Kay, P. and Fillmore, C. J. (1999). Grammatical constructions and linguistic generalizations: The What's X Doing Y? construction. Language, 75(1), 1–33.
Lambek, J. (1958). The mathematics of sentence structure. American Mathematical Monthly, 65(3), 154–170.
Langendoen, D. T. and Langsam, Y. (1987). On the design of finite transducers for parsing phrase-structure languages. In Manaster-Ramer, A. (Ed.), Mathematics of Language, pp. 191–235. John Benjamins, Amsterdam.
Levelt, W. J. M. (1970). A scaling approach to the study of syntactic relations. In d'Arcais, G. B. F. and Levelt, W. J. M. (Eds.), Advances in psycholinguistics, pp. 109–121. North-Holland, Amsterdam.
Levelt, W. J. M. (1983). Monitoring and self-repair in speech. Cognition, 14, 41–104.
Levin, B. (1993). English Verb Classes And Alternations: A Preliminary Investigation. University of Chicago Press, Chicago.
Macleod, C., Grishman, R., and Meyers, A. (1998). COMLEX Syntax Reference Manual Version 3.0. Linguistic Data Consortium.
Magerman, D. M. (1995). Statistical decision-tree models for parsing. In ACL-95.
Marcus, M. P., Kim, G., Marcinkiewicz, M. A., MacIntyre, R., Bies, A., Ferguson, M., Katz, K., and Schasberger, B. (1994). The Penn Treebank: Annotating predicate argument structure. In ARPA Human Language Technology Workshop, Plainsboro, NJ, pp. 114–119. Morgan Kaufmann.
Marcus, M. P., Santorini, B., and Marcinkiewicz, M. A. (1993). Building a large annotated corpus of English: The Penn treebank. Computational Linguistics, 19(2), 313–330.
McCawley, J. D. (1998). The Syntactic Phenomena of English. University of Chicago Press, Chicago.
Mel'čuk, I. A. (1979). Studies in dependency syntax. Karoma Publishers, Ann Arbor.
Mohri, M. and Nederhof, M. J. (2001). Regular approximation of context-free grammars through transformation. In Junqua, J.-C. and van Noord, G. (Eds.), Robustness in Language and Speech Technology, pp. 153–163. Kluwer.
Naur, P., Backus, J. W., Bauer, F. L., Green, J., Katz, C., McCarthy, J., Perlis, A. J., Rutishauser, H., Samelson, K., Vauquois, B., Wegstein, J. H., van Wijnagaarden, A., and Woodger, M. (1960). Report on the algorithmic language ALGOL 60. Communications of the ACM, 3(5), 299–314. Revised in CACM 6:1, 1-17, 1963.
Nederhof, M.-J. (2000). Practical experiments with regular approximation of context-free languages. Computational Linguistics, 26(1), 17–44.
Oehrle, R. T., Bach, E., and Wheeler, D. (Eds.). (1988). Categorial Grammars and Natural Language Structures. D. Reidel, Dordrecht.
Percival, W. K. (1976). On the historical source of immediate constituent analysis. In McCawley, J. D. (Ed.), Syntax and Semantics Volume 7, Notes from the Linguistic Underground, pp. 229–242. Academic Press.
Pereira, F. C. N. and Wright, R. N. (1997). Finite-state approximation of phrase-structure grammars. In Roche, E. and Schabes, Y. (Eds.), Finite-State Language Processing, pp. 149–174. MIT Press.
Pito, R. (1993). Tgrepdoc man page..
Pollard, C. and Sag, I. A. (1994). Head-Driven Phrase Structure Grammar. University of Chicago Press, Chicago.
Pullum, G. K. (1991). The Great Eskimo Vocabulary Hoax. University of Chicago, Chicago, IL.
Quirk, R., Greenbaum, S., Leech, G., and Svartvik, J. (1985). A Comprehensive Grammar of the English Language. Longman, London.
Radford, A. (1988). Transformational Grammar: A First Course. Cambridge University Press.
Radford, A. (1997). Syntactic Theory and the Structure of English: A Minimalist Approach. Cambridge University Press.
Rohde, D. L. T. (2005). Tgrep2 user manual..
Sag, I. A., Wasow, T., and Bender, E. M. (Eds.). (2003). Syntactic Theory: A Formal Introduction. CSLI Publications, Stanford, CA.
Sanfilippo, A. (1993). LKB encoding of lexical knowledge. In Briscoe, T., de Paiva, V., and Copestake, A. (Eds.), Inheritance, Defaults, and the Lexicon, pp. 190–222. Cambridge University Press.
Shriberg, E. (1994). Preliminaries to a Theory of Speech Disfluencies. Ph.D. thesis, University of California, Berkeley, CA. (unpublished).
Sleator, D. and Temperley, D. (1993). Parsing English with a link grammar. In Proceedings, Third International Workshop on Parsing Technologies, Tilburg, The Netherlands/Durbuy, Belgium.
Steedman, M. (1989). Constituency and coordination in a combinatory grammar. In Baltin, M. R. and Kroch, A. S. (Eds.), Alternative Conceptions of Phrase Structure, pp. 201–231. University of Chicago, Chicago.
Steedman, M. (2000). The Syntactic Process. The MIT Press.
Steedman, M. and Baldridge, J. (2003). Combinatory categorical grammar. Unpublished tutorial paper.
Tesnière, L. (1959). Éléments de Syntaxe Structurale. Librairie C. Klincksieck, Paris.
Van Valin, Jr., R. D. and La Polla, R. (1997). Syntax: Structure, meaning, and function..
Wundt, W. (1900). Völkerpsychologie: eine Untersuchung der Entwicklungsgesetze von Sprache, Mythus, und Sitte. W. Engelmann, Leipzig: Band II: Die Sprache, Zweiter Teil.
Xia, F. and Palmer, M. (2001). Converting dependency structures to phrase structures. In HLT-01, San Diego, pp. 1–5.
13
PARSING WITH CONTEXT-FREE GRAMMARS
There are and can exist but two ways of investigating and discovering truth. The one hurries on rapidly from the senses and particulars to the most general axioms, and from them...derives and discovers the intermediate axioms. The other constructs its axioms from the senses and particulars, by ascending continually and gradually, till it finally arrives at the most general axioms.
Francis Bacon, Novum Organum Book I.19 (1620)
We defined parsing in Ch. 3 as a combination of recognizing an input string and assigning a structure to it. Syntactic parsing, then, is the task of recognizing a sentence and assigning a syntactic structure to it. This chapter focuses on the kind of structures assigned by context-free grammars of the kind described in Ch. 12. However, since they are a purely declarative formalism, context-free grammars don't specify how the parse tree for a given sentence should be computed, therefore we'll need to specify algorithms that employ these grammars to produce trees. This chapter presents three of the most widely used parsing algorithms for automatically assigning a complete context-free (phrase structure) tree to an input sentence.
These kinds of parse trees are directly useful in applications such as grammar checking in word-processing systems; a sentence which cannot be parsed may have grammatical errors (or at least be hard to read). More typically, however, parse trees serve as an important intermediate stage of representation for semantic analysis (as we will see in Ch. 18), and thus plays an important role in applications like question answering and information extraction. For example, to answer the question
What books were written by British women authors before 1800?
we'll need to know that the subject of the sentence was what books and that the by-adjunct was British women authors to help us figure out that the user wants a list of books (and not a list of authors).
Before presenting any parsing algorithms, we begin by describing some of the factors that motivate the standard algorithms. First, we revisit the search metaphor for parsing and recognition, which we introduced for finite-state automata in Ch. 2, and talk about the top-down and bottom-up search strategies. We then discuss how the
| S \rightarrow NP VP | Det \rightarrow that | this | a |
| --- | --- |
| S \rightarrow Aux NP VP | Noun \rightarrow book | flight | meal | money |
| S \rightarrow VP | Verb \rightarrow book | include | prefer |
| NP \rightarrow Pronoun | Pronoun \rightarrow I | she | me |
| NP \rightarrow Proper-Noun | Proper-Noun \rightarrow Houston | TWA |
| NP \rightarrow Det Nominal | Aux \rightarrow does |
| Nominal \rightarrow Noun | Preposition \rightarrow from | to | on | near | through |
| Nominal \rightarrow Nominal Noun | |
| Nominal \rightarrow Nominal PP | |
| VP \rightarrow Verb | |
| VP \rightarrow Verb NP | |
| VP \rightarrow Verb NP PP | |
| VP \rightarrow Verb PP | |
| VP \rightarrow VP PP | |
| PP \rightarrow Preposition NP | |
ambiguity problem rears its head again in syntactic processing, and how it ultimately makes simplistic approaches based on backtracking infeasible.
The sections that follow then present the Cocke-Kasami-Younger (CKY) algorithm (Kasami, 1965; Younger, 1967), the Earley algorithm (Earley, 1970), and the Chart Parsing approach (Kay, 1986; Kaplan, 1973). These approaches all combine insights from bottom-up and top-down parsing with dynamic programming to efficiently handle complex inputs. Recall that we've already seen several applications of dynamic programming algorithms in earlier chapters — Minimum-Edit-Distance, Viterbi, Forward. Finally, we discuss partial parsing methods, for use in situations where a superficial syntactic analysis of an input may be sufficient.
13.1 PARSING AS SEARCH
Chs. 2 and 3 showed that finding the right path through a finite-state automaton, or finding the right transduction for an input, can be viewed as a search problem. For finite-state automata, the search is through the space of all possible paths through a machine. In syntactic parsing, the parser can be viewed as searching through the space of possible parse trees to find the correct parse tree for a given sentence. Just as the search space of possible paths was defined by the structure of an automata, so the search space of possible parse trees is defined by a grammar. Consider the following ATIS sentence:
(13.1) Book that flight.
Fig. 13.1 introduces the $ \mathcal{L}_{1} $ grammar, which consists of the $ \mathcal{L}_{0} $ grammar from the last chapter with a few additional rules. Given this grammar, the correct parse tree for this example would be the one shown in Fig. 13.2.
How can we use $ \mathcal{L}_1 $ to assign the parse tree in Fig. 13.2 to this example? The goal of a parsing search is to find all the trees whose root is the start symbol S and which cover exactly the words in the input. Regardless of the search algorithm we choose, there are two kinds of constraints that should help guide the search. One set of constraints comes from the data, that is, the input sentence itself. Whatever else is true of the final parse tree, we know that there must be three leaves, and they must be the words book, that, and flight. The second kind of constraint comes from the grammar. We know that whatever else is true of the final parse tree, it must have one root, which must be the start symbol S.
These two constraints, invoked by Bacon at the start of this chapter, give rise to the two search strategies underlying most parsers: top-down or goal-directed search, and bottom-up or data-directed search. These constraints are more than just search strategies. They reflect two important insights in the western philosophical tradition: the rationalist tradition, which emphasizes the use of prior knowledge, and the empiricist tradition tradition, which emphasizes the data in front of us.