On the Wire
Linguistics In the News
No current headlines.
On the Wire
Science In the News

Abstract
Memory Requirements and Lexical Ambiguities of Parsing Strategies
By Steve Hoenisch
Last updated on Oct. 31, 2012
Copyright 1996-2006 www.Criticism.Com
Table of Contents
1 Citation
2 Optimal Parsing Strategies
3 Related

1 Citation

From: Abney, S. and Johnson, M. 1991. Memory Requirements and Lexical Ambiguities of Parsing Strategies, Journal of Psycholinguistics Research 20:233-250.

Top

2 Optimal Parsing Strategies

Abney and Johnson, maintaining that two properties of parsing strategies -- space requirements and local ambiguities -- have been subject to imprecise examination and unrealistic assumptions, investigate the range of possible parsers, their memory requirements, and the number of local ambiguities they face. Abney and Johnson lay the foundation for determining and executing the parsing strategy that, given a grammar, optimizes the combination of memory requirements and local ambiguities. In doing so, they provide a method for measuring the local ambiguities and space requirements of a selected parsing strategy for a particular grammar. (For Abney and Johnson, a parsing strategy "is a way of enumerating the nodes and arcs of parse trees" (236).)
Because of the controversy over center-embedded constructions, Abney and Johnson's method for measuring space requirements is of particular importance. The method rests on assigning one unit to each node to which the parser may need to refer, including nodes left incomplete because their parent or child has yet to be constructed. Given a grammar, a parsing strategy's required space is the maximum necessitated by an enumeration that the strategy designates for a parse tree of the grammar. The measurement's application shows that in languages like English which branch heavily to the right, a top-down strategy makes more efficient use of memory than a bottom-up strategy -- because a top-down strategy keeps the number of incomplete nodes lower. Conversely, in left-branching structures, a bottom-up parser more efficiently utilizes space. Meantime, the parsing strategy for center embedding should require maximal memory requirements if the inability to parse center-embedded constructions is to be attributed to memory limitations. However, Abney and Johnson show, neither top-down nor bottom-up strategies reach their maximum space requirements when applied to center-embedded structures, a finding that Abney and Johnson make convincing by providing and comparing clear, concrete enumerations of the memory requirements for left-branching, right-branching, and center-embedded structures.
Regarding local ambiguities, Abney and Johnson use calculations to show that a "less eager" strategy -- that is, one that constructs nonterminal nodes earlier in the input string -- may reduce the local ambiguities encountered by the parser. Bottom-up strategies are less eager than top-down strategies, revealing an efficiency trade off for right-branching languages like English between reducing local ambiguities and minimizing memory requirements. Accordingly, Abney and Johnson maintain that the optimal parsing strategy for English is probably neither top-down nor bottom-up.
Considered a classic essay in the computational linguistic literature as well as an important psycholinguistic contribution, the essay is well organized and highly readable, making it accessible to readers not initiated into the technical background of computational linguistics. Abney and Johnson take particular care to define their terms and provide concrete examples backing up their major points.
Top
Google       

Criticism.com Web

cover artFoundations of Statistical Natural Language Processing
The MIT Press
New $60.83
cover artFoundations of Language : Brain, Meaning, Grammar, Evolution
Oxford University Press
New $19.95
cover artSpeech and Language Processing: An Introduction to Natural Language Processing, Computational Linguistics and Speech Recognition
Prentice Hall
New $83.28
cover artThe Oxford Handbook of Computational Linguistics (Oxford Handbooks)
Oxford University Press, USA
New $45.00
cover artConstructions at Work : The Nature of Generalization in Language
Oxford University Press, USA
New $29.95
cover artComputational Linguistics and Formal Semantics (Studies in Natural Language Processing)
Cambridge University Press
New $39.16
cover artRepresentation and Inference for Natural Language : A First Course in Computational Semantics (Center for the Study of Language and Information - Lecture Notes)
Center for the Study of Language and Inf
New $30.00
cover artComputational Linguistics (Studies in Natural Language Processing)
Cambridge University Press
New $26.99
cover artFinite State Morphology
Center for the Study of Language and Inf
New $34.76
cover artBeyond Communities of Practice : Language Power and Social Context (Learning in Doing: Social, Cognitive & Computational Perspectives)
Cambridge University Press
New $24.99
(Prices May Change)
Privacy Information

cover artNatural Language Information Retrieval (Text, Speech and Language Technology)
Springer
New $151.00
cover artLanguage As a Cognitive Process: Syntax
Addison-Wesley
New
cover artCorpus Linguistics : Investigating Language Structure and Use (Cambridge Approaches to Linguistics)
Cambridge University Press
New $31.99
cover artMathematical Models of Spoken Language
John Wiley & Sons
New $120.00
cover artModels of Language Acquisition : Inductive and Deductive Approaches (Oxford Linguistics)
Oxford University Press, USA
New $33.35
cover artMemory-Based Language Processing (Studies in Natural Language Processing)
Cambridge University Press
New $75.00
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 artComputer-Assisted Language Learning : Context and Conceptualization
Oxford University Press, USA
New $45.00
cover artConstraint-Based Grammar Formalisms: Parsing and Type Inference for Natural and Computer Languages
The MIT Press
New $45.00
cover artWordNet: An Electronic Lexical Database (Language, Speech, and Communication)
The MIT Press
New $58.19
(Prices May Change)
Privacy Information