Re: a yacc grammar for palindromes?

will@ccs.neu.edu (William D Clinger)
Wed, 19 Apr 1995 15:14:41 GMT

          From comp.compilers

Related articles
a yacc grammar for palindromes? ted@mayfield.hp.com (1995-03-31)
Re: a yacc grammar for palindromes? oracle@mch.sni.de (1995-04-04)
Re: a yacc grammar for palindromes? dodd@csl.sri.com (1995-04-14)
Re: a yacc grammar for palindromes? torbenm@diku.dk (1995-04-10)
Re: a yacc grammar for palindromes? caibmnfx@ibmmail.com (Parag V. Tijare) (1995-04-12)
Re: a yacc grammar for palindromes? hbaker@netcom.com (1995-04-12)
Re: a yacc grammar for palindromes? will@ccs.neu.edu (1995-04-19)
| List of all articles for this month |

Newsgroups: comp.compilers
From: will@ccs.neu.edu (William D Clinger)
Keywords: yacc, parse
Organization: College of CS, Northeastern University
References: 95-04-031 95-04-113
Date: Wed, 19 Apr 1995 15:14:41 GMT

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
--


Post a followup to this message

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