|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)|
|Date:||Tue, 4 Apr 1995 13:24:13 GMT|
> 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
> 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
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 :-(
currently at: permanent address:
SNI BS2000 TP 133 FMI, Universit"at Passau
Return to the
Search the comp.compilers archives again.