Re: Parsing with infinite lookahead

Terence parr writes:
!I think the Early Algorithm (in O(n^3) time?) parses any unambiguous
!context-free language. However, most parser-generators are restricted to
!the LALR(1), LR(1), or LL(1) grammars and, hence, cannot handle all
!context-free languages.


Earley's Algorithm parses any grammar (ambiguous or unambiguous) in O(n^2)
space and O(n^2) or O(n^3) time, depending upon whether the grammar is
unambiguous or ambiguous, respectively. The best part about the algorithm
is that no tables are constructed before hand (unlike any other parser)
but instead, built on the fly, for a given string to be parsed. It is
undecidable whether a CFG is ambiguous, as was pointed out earlier, but
for a given string to be parsed, Earley's algorithm will tell you whether
more than one derivation exists or not. For Further information, refer AHO
and ULLMAN, "The Theory of Parsing, Translation and Compiling", Volume 1,
Prentice Hall.


As an aside, does anybody know where Dr. Earley is and if he is still
working on parsers or not?
--
Nandakumar Sankaran (nandu@cs.clemson.edu) (nsankar@hubcap.clemson.edu)
311-8 Old Greenville Hwy. Clemson SC 29631-1651 (803)653-7749
G34 Jordan Hall Comp. Sci. Dept. Clemson Univ. SC 29634 (803)656-6979
--

Return to the comp.compilers page.
Search the comp.compilers archives again.