Thumbnail
Access Restriction
Subscribed

Author Earley, Jay
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Language English
Subject Keyword Parsing ♦ Context-free grammar ♦ Computational complexity ♦ Compilers ♦ Syntax analysis
Abstract A parsing algorithm which seems to be the most efficient general context-free algorithm known is described. It is similar to both Knuth's LR(k) algorithm and the familiar top-down algorithm. It has a time bound proportional to n3 (where n is the length of the string being parsed) in general; it has an n2 bound for unambiguous grammars; and it runs in linear time on a large class of grammars, which seems to include most practical context-free programming language grammars. In an empirical comparison it appears to be superior to the top-down and bottom-up algorithms studied by Griffiths and Petrick.
Description Affiliation: Univ. of California, Berkeley (Earley, Jay)
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2005-08-01
Publisher Place New York
Journal Communications of the ACM (CACM)
Volume Number 13
Issue Number 2
Page Count 9
Starting Page 94
Ending Page 102


Open content in new tab

   Open content in new tab
Source: ACM Digital Library