Re: a yacc grammar for palindromes?

ted@mayfield.hp.com (Ted Johnson) writes:


>SHORT VERSION:


> Q: is it possible to write a yacc grammar to recognize palindromes?


        A: No.


>LONG VERSION:


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


True. An NPDA can handle any context-free language.


>But a D-PDA can *simulate* a ND-PDA by basically trying all the possible
>combinations. This would take exponential time (i.e., each time we added
>one token to the input, it would double the time it takes to parse the
>input).


"Trying all possible combinations" is basically the difference between
DPDAs and NPDAs. What you're saying is really "A DPDA can simulate an
NDPA by nondeterministically trying all possible shif/reduce
combinations".


>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


>but it wasn't a fatal error. However, it refused to recognize any
>palindromes:


Yacc doesn't do backtracking, so it tries to resolve the ambiguity by
choosing shift every time (this can be modified by adding precedence
rules). But no static ambiguity resolution will allow recognition of
palindromes.


>Q: is it impossible for a D-PDA to recognize palindromes, or did I
> just screw up my yacc grammar?


It is impossible for a DPDA with finite look-ahead to recognize
palindromes. Any PDA that recignizes palindromes must store the first
half of the string on the stack, to compare it against the second
half, at which point it pops the symbols off the stack. However, no
finite look-ahead will tell you when you have read the first half of
the string.


It is fairly simple to add backtracking to LR parsers, so they on
conflicts try all possibilities in some order (my parser generator for
Gofer & Haskell, Ratatosk does this). Such a parser will recognize
palindromes, but in quadratic time. A two-way deterministic PDA
(2DPDA) can recognize palindromes in linear time, but I know of no
parser generator that generates 2DPDAs.


Torben Mogensen (torbenm@diku.dk)
--

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