Re: a yacc grammar for palindromes

" Parag V. Tijare" <>
Tue, 18 Apr 1995 16:42:52 GMT

          From comp.compilers

Related articles
a yacc grammar for palindromes? (1995-03-31)
Re: a yacc grammar for palindromes (Parag V. Tijare) (1995-04-18)
| List of all articles for this month |

Newsgroups: comp.compilers
From: " Parag V. Tijare" <>
Keywords: yacc
Organization: Compilers Central
References: 95-04-031
Date: Tue, 18 Apr 1995 16:42:52 GMT

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


>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

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?
{reduce by start -> ONE}
Now you get the error since the automaton cannot proceed further
(since it cannot recognize any "handle").

Parag e-mail :
IBM Toronto Labs or
1150 Eglinton Avenue (E) voice-mail: (001)(416)448-4126
North York, ON. M3C 1H7 Tie Line: 778-4126

Post a followup to this message

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