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

Abstract
Earley's Efficient Context-Free Parsing Algorithm
By Steve Hoenisch
Last updated on Oct. 31, 2012
Copyright 1996-2006 www.Criticism.Com
Table of Contents
1 Citation
2 Top-Down and Bottom-Up Algorithms
3 Related

1 Citation

From: Earley, Jay. 1970. An Efficient Context-Free Parsing Algorithm. Reprinted in Readings in Naturual Language Processing, Grosz, Jones and Webber, eds. 1986. Los Altos, Calif.: Morgan Kaufmann.

Top

2 Top-Down and Bottom-Up Algorithms

Earley aims to describe what he argues to be the most efficient possible context-free parsing algorithm and to provide empirical evidence for his argument by comparing his top-down algorithm to other familiar parsing algorithms, including those of both the top-down and bottom-up variety. Constructed as a recognizer -- that is, as an algorithm that scans input in the form of a string and either allows or rejects it based on whether the string is a sentence of the grammar -- his algorithm scans a string of input from left to right while looking ahead a fixed number of symbols. At each symbol, the recognizer constructs a set of states that characterize the condition of the recognition process at that point in the scan. The look-ahead feature of Earley's algorithm is argued to be especially useful in the parsing of bounded-state LR(k) grammars.
Earley maintains that his algorithm has several strengths over its competitors and demonstrates those strengths by comparing his alorithm to others. The strengths of his algorithm, which uses, a random access model, include an upper bound on time proportional to n3, with n standing for the length of string being parsed. Earley shows that his algorithm can parse at n2 given unambiguous input. As an example, Earley briefly compares the efficiency of his algorithm to the results that Younger obtained using Cocke's algorithm. Earley maintains his is better for two reasons: First, it does not require a special form for the grammar, whereas Cocke's required normal form; second, Earley shows his algorithm often performs better than n2, whereas Cocke's requires n2.
Earley also compares his algorithm with the backtracking-dependent bottom-up and top-down context-free parsers that have been examined by Griffiths and Petrick, arguing that his is superior because theirs have expediential upper bounds for time. Earley compares the algorithms on seven different grammars and demonstrates that while his algorithm performs similar to the others on simple grammars, it is substantially faster, and thus superior, on very ambiguous grammars.
Although much of Earley's discussion addresses the technicalities of his recognizer and how it compares with other algorithms, he also discusses the pratical applications of his algorithm after it is made into a parser.
Part of Earley's discussion assumes a knowledge of basic list processing techniques, making some aspects of his presentation difficult to access for a linguist without a computer science background.
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