On the Wire
linguistics In the News
No current headlines.

Access Your PC from Anywhere
Outline
Parsing Strategies: Notes on Abney and Johnson
Table of Contents
1 Some Types of Parsing Strategies
2 Assumptions about the Parser
3 The Right-Hand Branching Grammar
4 Methodology: Memory Requirements
5 Methodology: Local Ambiguity
6 Related Pages

1 Some Types of Parsing Strategies

Note: The notes on this page are adopted from Abney and Johnson 1991.

Definition: A parsing strategy is a method of enumerating the arcs and nodes of parse trees.
Top-down: Each node is enumerated before any of its descendants.
Bottom-up: Each node is enumerated after all its descendants.
Left-corner: A node is built immediately after its first child and that child's descendants, but before the remaining children or any of their descendants.
Arc-eager: An arc is enumerated at the earliest point that the two nodes it connects have been enumerated.
Arc-standard: An arc is enumerated at the earliest point such that (i) both nodes it connects have been enumerated and (ii) either none or all of the subtree under the child node has been enumerated.

2 Assumptions about the Parser

An arc-eager strategy may require less but never more memory than a corresponding arc-standard strategy. It is thus assumed that the parser uses arc-eager enumeration, even though an arc-eager strategy may result in an increase in local ambiguity.
The parser produces only binary branching trees.
The parser has a one word look-ahead.
Each unit of memory is enough space for one node of a parse tree.

3 The Right-Hand Branching Grammar

Inspired by the German word-order in such sentences as die Frau kann das Buch lesen, which translates literally as the woman can the book read, the phrase-structure grammar is as follows:

S  > NP IP
NP > Det N
IP > I VP
VP > NP V
The final phrase-structure rule shows that, in contrast to typical declarative English sentences, a verb can be proceeded by its object.

4 Methodology: Memory Requirements

The memory usage of a parse tree is the maximum number of incomplete nodes at any point in the parse.
Recall the assumption that each unit of memory is enough space for one node of a parse tree. Thus, each incomplete node takes up one unit of memory.
A node is incomplete if it has been built but either its parent or one of its children has not been built.
Furthermore, any node is incomplete if its children or parent has been built but an arc connecting any one of them has not.

5 Methodology: Local Ambiguity

Local ambiguities arise when the input to the parser can result in more than one possible tree.
In particular, such ambiguities occur when the parser is unsure which set of arcs and nodes to build at a given point in the input string.
The parse increment: Local ambiguities can be determined by examining what is called the parse increments in the construction of a tree.
More specifically, the ith parse increment comprises those nodes and arcs enumerated between the terminal nodes for the first word that the parser sees and the next word of input.
Thus, local ambiguities can occur between those points in the input that have been read so far and the next word of look-ahead.
The first parse increment, for example, is the set of nodes and arcs enumerated before the first word (recall that the parser has a one-word look-ahead).
Google       

Criticism.com Web

cover artOld Testament Parsing Guide: Revised and Updated Edition
Broadman & Holman Publishers
New $26.39
cover artA Hebrew Reader for Ruth
Hendrickson Publishers
New $10.36
cover artA Parsing Guide to the Greek New Testament
Herald Pr
New
cover artPro Perl Parsing (Pro)
Apress
New $39.99
cover artPerl 6 and Parrot Essentials, Second Edition
O'Reilly Media, Inc.
New $29.95
cover artIntermediate Perl
O'Reilly Media, Inc.
New $23.09
cover artNew Developments in Parsing Technology
Springer
New $64.95
cover artData-Oriented Parsing (Center for the Study of Language and Information - Lecture Notes)
Center for the Study of Language and Inf
New $35.00
cover artConstraint-Based Grammar Formalisms: Parsing and Type Inference for Natural and Computer Languages
The MIT Press
New $45.00
cover artThe Theory of Parsing, Translation, and Compiling: Vol. 1 (Prentice-Hall Series in Automatic Computation)
Prentice Hall
New
(Prices May Change)
Privacy Information

cover artThe Theory and Practice of Discourse Parsing and Summarization (Bradford Books)
The MIT Press
New $38.98
cover artParsing through Customs: Essays by a Freudian Folklorist
University of Wisconsin Press
New $19.95
cover artGrammatical Competence and Parsing Performance
University Of Chicago Press
New $80.00
cover artGeneralized LR Parsing
Springer
New $166.00
cover artFoundations of Computational Linguistics : Human-Computer Communication in Natural Language
Springer
New $69.95
cover artParsing Techniques 2/e (Monographs in Computer Science)
Springer
New $75.00
cover artConstraint Grammar: A Language-Independent System for Parsing Unrestricted Text (Natural Language Processing, No 4)
Walter De Gruyter Inc
New $241.90
cover artEfficient Parsing for Natural Language : A Fast Algorithm for Practical Systems (The International Series in Engineering and Computer Science)
Springer
New $154.00
cover artThe Theory of Parsing, Translation, and Compiling: Vol. 2 (Prentice-Hall Series in Automatic Computation)
Prentice Hall
New
cover artOld Testament Parsing Guide: Genesis--Esther
Moody Pr
New
(Prices May Change)
Privacy Information