Re: a yacc grammar for palindromes?

ted@mayfield.hp.com wrote:


> Q: is it possible to write a yacc grammar to recognize palindromes?
[...]
> 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).


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


That is because of the conflicts. yacc resolves shift/reduce conflicts with
shift by default, so your parser shifts on every input token and reduces only
when it reaches the end of the token-stream. Then it can reduce only once,
before it runs into an error state. Thus your sample parser behaves
in a "correct" manner.




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


yacc parses LALR(1) languages, a subclass of CFL designed to be parsed in
linear time. Thus yacc-parsers are *always* linear in time. Hence there is
no yacc-grammar that implements the D-PDA you are trying to implement.


To parse a palindrome the parser must be able to decide when it has
reached the "middle" of the palindrome. With a lookadead of just 1
(or any other constant) this is obviously not possible.


BTW IMHO a D-PDA *cannot* simulate a ND-PDA as sketched above, because to do
so the automaton would have to back up on the input stream, sth. it can't do.


To recognize the palindrome-language you have to switch to more generic
parsing methods. For example there exists one parsing algorithm that
recognizes any CFL in O(n^3) (n being the length of the input stream).
Unfortunately I don't remember its name :-(


Stefan
--
--------------------------------------------------------------------------
      Stefan Griesser


      currently at: permanent address:


      SNI BS2000 TP 133 FMI, Universit"at Passau
      oracle@mch.sni.de griesser@fmi.uni-passau.de
--

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