Mon, 10 Apr 1995 10:00:25 GMT

Related articles |
---|

a yacc grammar for palindromes? ted@mayfield.hp.com (1995-03-31) |

Re: a yacc grammar for palindromes? oracle@mch.sni.de (1995-04-04) |

Re: a yacc grammar for palindromes? dodd@csl.sri.com (1995-04-14) |

Re: a yacc grammar for palindromes? torbenm@diku.dk (1995-04-10) |

Re: a yacc grammar for palindromes? caibmnfx@ibmmail.com (Parag V. Tijare) (1995-04-12) |

Re: a yacc grammar for palindromes? hbaker@netcom.com (1995-04-12) |

Re: a yacc grammar for palindromes? will@ccs.neu.edu (1995-04-19) |

Newsgroups: | comp.compilers |

From: | torbenm@diku.dk (Torben AEgidius Mogensen) |

Keywords: | yacc |

Organization: | Department of Computer Science, U of Copenhagen |

References: | 95-04-031 |

Date: | Mon, 10 Apr 1995 10:00:25 GMT |

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)

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.