Re: a yacc grammar for palindromes?

dodd@csl.sri.com (Chris Dodd)
Fri, 14 Apr 1995 05:36:10 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: dodd@csl.sri.com (Chris Dodd)
Keywords: yacc
Organization: Computer Science Lab, SRI International
References: 95-04-031
Date: Fri, 14 Apr 1995 05:36:10 GMT

ted@mayfield.hp.com (Ted Johnson) writes:
> Q: is it possible to write a yacc grammar to recognize palindromes?
>
>If I recall language theory class correctly, a ND-PDA (non-deterministic
>pushdown automata) is more powerful than a D-PDA (a deterministic PDA).
>In particular, a ND-PDA can handle the language of palindromes, whereas
>a D-PDA can't.
>
>But a D-PDA can *simulate* a ND-PDA by basically trying all the possible
>combinations.


Actually, a D-PDA can't do this. A computer (which is a deterministic
automata of a class both more and less powerful than D-PDAs) can, until
it runs out of memeory.


>I tried this with yacc, with a simple grammar for palindromes for the
>input characters 0 and 1. yacc reported the warning:
> conflicts: 6 shift/reduce


Yacc reporting conflicts means that the PDA it constructed from the
grammar was not deterministic. Yacc deals with this by making a fixed
choice at each point non-determinism creeps in, resulting in a D-PDA
that accepts some subset of the input grammar. This doesn't necessarily
mean that you CAN'T construct a D-PDA recognizing the grammar, only that
the particular construction method used by yacc failed to.


My btyacc parser generator deals with this problem by leaving the
non-determinism in the PDA and trying all combinations at runtime.
If you compile your example with btyacc, it works just as you
expect.


        % echo 10101 | ./p
        S -> ONE
        S -> ZERO S ZERO
        S -> ONE S ONE


You can get btyacc from <ftp://ftp.csl.sri.com/pub/dodd/btyacc.tar.gz>


Chris Dodd
dodd@csl.sri.com
--


Post a followup to this message

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