Laboratory 3, Components I and II:Context-free parsing, Spring Pitching Warmup1. Introduction: Goals of the Laboratory & Background Reading1.1 Why parsing?You should refer to the online notes and lectures for much more detailed background on the following material. In the following three subsections (2.1, 2.2, 2.3, and 2.4) we shall take a look at four distinct parsing methods: recursive-descent parsing; shift-reduce parsing; chart parsing; and Earley parsing. Questions will pertain only to the last three.2.1. Recursive Descent Parsing: Top-down, depth-first search2.2. Shift-Reduce Parsing: Bottom-up search2.3.1 Charts2.3.2 Chart RulesBottom Up RuleTop Down InitializationTop Down RuleFundamental Rule2.3.4 Chart Parser Strategies2.4. Chart ParsersThis concludes Laboratory 3, Components I and IIMassachusetts Institute of TechnologyDepartment of Electrical Engineering and Computer Science6.863J/9.611J Natural Language Processing, Spring, 2004Laboratory 3, Components I and II: Context-free parsing, Spring Pitching WarmupHanded Out: March 08 Due: March 171. Introduction: Goals of the Laboratory & Background ReadingThe main aim of this laboratory is to give you a brief exposure to building “real” grammars, along with an understanding of how syntactic phenomena interact with context-free parsing algorithms. The laboratory is designed so that you will become familiar with chart context-free parsing and the Earley parser we have described and implemented, and the ways in which they achieve their efficiency, including the important issue of how they deal with ambiguity. You will also examine indetail one other parsing method, shift-reduce (bottom-up) parsing, as a way in which to think abouthuman parsing strategies. We shall use this laboratory as a way of introducing you to the terminology of linguistics and the way that we will describe more sophisticated grammars that can handle cases of apparent ‘long distance’ dependencies, such as the connection between ‘what’ and the object of the verb ‘eat’ in a sentence such as ‘What did John eat?’ Finally, you will learn how to use features-for example, those returned by the Kimmo or part of speech taggers of Lab 2 – to simplify grammar construction, and illustrate the important principle of modularity in NLP design-in this case, the separation of lexical information from hierarchical, syntactic information. The organization of this laboratory is much like that of Lab 1. Specifically, in the first part of the laboratory, Component II, we will introduce you to the subject and give you some ‘warmup’ questions to think about parsing, as well as introduce you to running the shift-reduce, chart, and Earley parsers. A few of the questions may require more than casual thinking. In the second part of the lab handed out next time, Component III, you will have the job of implementing a larger grammar to capture certain syntactic phenomena in English. General Background reading for this Laboratory You should prepare for this laboratory by reading the following: First, the third and fourth installments of course notes on the website here and here provide an overview of syntactic structure and parsing, including much more detail on Earley parsing than we can provide in this document. Second, we include below concise descriptions of general context-free parsing, shift-reduce parsing, and chart parsing. Finally, your textbook’s chapters on context-free parsing offer additional discussion of chart parsing and the general topic of context-free parsing.Running the parsersThe material in the subsequent sections describes in detail how to use and run the parsers for the laboratory. A concise reference summary of the operation of the first two can be obtained by selecting the “Help” button in each. (Note: much of the following material is taken, slightly modified, from Edward Loper and Steven Bird’s introduction to these parsers)1.1 Why parsing?Native speakers of any language have strong intuitions about the well-formedness of sentences in that language. These intuitions are surprisingly detailed. For example, consider the following six sentences involving three synonymous verbs loaded, dumped, and filled. (We shall return to this question later in the course, under the heading of lexical semantics.)a. The farmer loaded sand into the cart b. The farmer loaded the cart with sand c. The farmer dumped sand into the cart d. *The farmer dumped the cart with sand e. *The farmer filled sand into the cart f. The farmer filled the cart with sandg. I wonder who likes ice-creamh. *What do you wonder who likesThree of the sentences (starred) are ill-formed. As we shall see, many patterns of well-formedness and ill-formedness in a sequence of words can be understood with respect to the internal phrase structure of the sentences. We can develop formal models of these structures using grammars and parsers. In particular, as we have discussed, we can use context-free grammars to describe the phrase structure – at least for part of natural languages.In the context of computational modeling, a language is often viewed as a set of well-formed sentences. Sequences of words that are not grammatical are excluded from this set. We remind you again that this notion of ‘grammatical’ is one that may have little in common with prescriptive grammar that you might have been taught in elementary school. Now, since there is no upper-bound on the length of a sentence, the number of possible sentences is unbounded. For example, itis possible to add an unlimited amount of material to a sentence by using and or by chaining relative clauses, as illustrated in the following example from a children's story: You can imagine Piglet's joy when at last the ship came in sight of him. In after-years he liked to think that he had been in Very Great Danger during the Terrible Flood, but the only danger he had really been in was the last half-hour of his imprisonment, when Owl, who had just flown up, sat on a branch of his tree to comfort him, and told him a very long story about an aunt who had once laid a seagull's egg by mistake, and the story went on and on, rather like this sentence, until Piglet who was listening out of his window without much hope, went to sleep quietly and naturally, slipping slowly out of the window towards the water until he was only hanging on by his toes, at which
View Full Document
Unlocking...