|a yacc grammar for palindromes? firstname.lastname@example.org (1995-03-31)|
|Re: a yacc grammar for palindromes? email@example.com (1995-04-04)|
|Re: a yacc grammar for palindromes? firstname.lastname@example.org (1995-04-14)|
|Re: a yacc grammar for palindromes? email@example.com (1995-04-10)|
|Re: a yacc grammar for palindromes? firstname.lastname@example.org (Parag V. Tijare) (1995-04-12)|
|Re: a yacc grammar for palindromes? email@example.com (1995-04-12)|
|Re: a yacc grammar for palindromes? firstname.lastname@example.org (1995-04-19)|
|From:||email@example.com (William D Clinger)|
|Organization:||College of CS, Northeastern University|
|Date:||Wed, 19 Apr 1995 15:14:41 GMT|
firstname.lastname@example.org (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
Valiant, L. General context-free recognition in less than
cubic time. Journal of Computer and System Sciences 10(2),
1975, pages 308--315.
Return to the
Search the comp.compilers archives again.