Re: a yacc grammar for palindromes?

hbaker@netcom.com (Henry Baker)
Wed, 12 Apr 1995 23:58:07 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: hbaker@netcom.com (Henry Baker)
Keywords: yacc
Organization: nil
References: 95-04-031 95-04-062
Date: Wed, 12 Apr 1995 23:58:07 GMT

ted@mayfield.hp.com wrote:
> Q: is it possible to write a yacc grammar to recognize palindromes?


<oracle@mch.sni.de> wrote:
> To recognize the palindrome-language you have to switch to more generic
> parsing methods. For example there exists one parsing algorithm that
> recognizes any CFL in O(n^3) (n being the length of the input stream).
> Unfortunately I don't remember its name :-(


Vaughan Pratt's 'Lingol' parsing system (quite different from his parser
which was used in Macsyma) is an O(n^3) algorithm.


The algorithm is described in two papers available on the 'web if you
follow the links from:


ftp://ftp.netcom.com/pub/hb/hbaker/lingol/NLingol.html


--
www/ftp directory:
ftp://ftp.netcom.com/pub/hb/hbaker/home.html
--

Post a followup to this message

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