Re: a yacc grammar for palindromes

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


No. It cannot be done using purely yacc. The automaton built by yacc
is not even as powerful as a DPDA. ( LALR(1) is a subset of Deterministic
CFG).




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


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


It is not possible for a DPDA to simulate NDPDA. There is no way to keep
track of multiple stacks required for the simulation in a single DPDA.
So a even a DPDA *cannot* recognize palindromes.


>I tried this with yacc, with a simple grammar for palindromes for the


> conflicts: 6 shift/reduce
> .....
> 10101
> hprcl171(ted) 668>p < test1
> S -> ONE
> syntax error
> hprcl171(ted) 669>




When you ignore the shift-reduce conflicts, the default action taken by yacc
is SHIFT. So with your grammar, the yacc automaton will keep on shifting
until and including the last '1' onto its stack. On encountering end of input,
it will start reducing. That's how you got the "S -> ONE" in the output.
The stack at different stages will look as follows.
YTop of the stack is to the right side?
10101
{reduce by start -> ONE}
1010start
Now you get the error since the automaton cannot proceed further
(since it cannot recognize any "handle").


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

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