Re: a yacc grammar for palindromes?

" Parag V. Tijare" <caibmnfx@ibmmail.com>
Wed, 12 Apr 1995 18:06:16 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: " Parag V. Tijare" <caibmnfx@ibmmail.com>
Keywords: yacc, theory
Organization: Compilers Central
References: 95-04-062
Date: Wed, 12 Apr 1995 18:06:16 GMT

Stefen Griesser 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 :-(


The algorithm is called CYK (Coke, Younger and Kasami) algorithm described
in most of the standard texts on automata theory.
It is described in "Introduction to automata theory, languages and computation"
by Aho, Hopcroft and Ullman.


Parag e-mail : caibmnfx@ibmmail.com
IBM Toronto Labs or parag@genius.tisl.soft.net
1150 Eglinton Avenue (E) voice-mail:(001)(416)448-4126
North York, ON. M3C 1H7 Tie Line: 778-4126
--

Post a followup to this message

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