|a yacc grammar for palindromes? email@example.com (1995-03-31)|
|Re: a yacc grammar for palindromes? firstname.lastname@example.org (1995-04-04)|
|Re: a yacc grammar for palindromes? email@example.com (1995-04-14)|
|Re: a yacc grammar for palindromes? firstname.lastname@example.org (1995-04-10)|
|Re: a yacc grammar for palindromes? email@example.com (Parag V. Tijare) (1995-04-12)|
|Re: a yacc grammar for palindromes? firstname.lastname@example.org (1995-04-12)|
|Re: a yacc grammar for palindromes? email@example.com (1995-04-19)|
|From:||firstname.lastname@example.org (Chris Dodd)|
|Organization:||Computer Science Lab, SRI International|
|Date:||Fri, 14 Apr 1995 05:36:10 GMT|
email@example.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
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
% 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>
Return to the
Search the comp.compilers archives again.