Re: a yacc grammar for palindromes?

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

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