Re: a yacc grammar for palindromes?

hbaker@netcom.com (Henry Baker) writes:
>Vaughan Pratt's 'Lingol' parsing system (quite different from his parser
>which was used in Macsyma) is an O(n^3) algorithm.


In 1970, Earley's algorithm proved that all context-free languages
could be parsed in O(n^3) time:


        Earley, J. An efficient context-free parsing algorithm.
        CACM 13(2), 1970, pages 94--102.


I think Earley's algorithm runs in O(n^2) for unambiguous grammars,
and runs in O(n) time for LR(0) grammars. The palindrome grammar is
unambiguous, so palindromes are recognizable in quadratic time using
Earley's algorithm (if I recall correctly).


For general context-free grammars, the fastest known parsing
algorithm seems to run in O(n^a) time, where a = log_2(7) is
approximately 2.807354922057604:


        Valiant, L. General context-free recognition in less than
        cubic time. Journal of Computer and System Sciences 10(2),
        1975, pages 308--315.


William Clinger
--

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