26 Oct 2006 00:31:56 -0400

Related articles |
---|

Grammar needed leonardo@dcc.ufmg.br (Leonardo Teixeira Passos) (2006-10-24) |

Re: Grammar needed schmitz@i3s.unice.fr (Sylvain Schmitz) (2006-10-26) |

Re: Grammar needed 148f3wg02@sneakemail.com (Karsten Nyblad) (2006-10-26) |

Re: Grammar needed pjj@cs.man.ac.uk (Pete Jinks) (2006-10-26) |

Re: Grammar needed cfc@shell01.TheWorld.com (Chris F Clark) (2006-10-26) |

Re: Grammar needed leonardo@dcc.ufmg.br (Leonardo Teixeira Passos) (2006-11-01) |

From: | Chris F Clark <cfc@shell01.TheWorld.com> |

Newsgroups: | comp.compilers |

Date: | 26 Oct 2006 00:31:56 -0400 |

Organization: | The World Public Access UNIX, Brookline, MA |

References: | 06-10-101 |

Keywords: | parse, theory |

Leonardo Teixeira Passos <leonardo@dcc.ufmg.br> writes:

*> Hi there.*

*>*

*> I've been trying to obtain a grammar that meets two properties:*

*>*

*> (i) It represents an LR(k) language*

*> (ii) The grammar it self isn't LR(k) for any k, for there is at least*

*> one conflict. One or more of these conflicts does not indicate*

*> ambiguity in the grammar, but can't be solved with any k.*

*>*

*> Condition (i) is relatively easy to achieve. However, I can't put (ii) to*

*> work with (i).*

*>*

*> Any suggestions?*

Does this grammar meet your needs?

goal : nt1 | nt2;

nt1: cfl1 "b";

nt2: cfl2 "c";

cfl1 : "a" | "a" cfl1;

cfl2 : "a" | "a" cfl2;

It describes the language a+b | a+c which is LR(1), and is not

ambiguous--each string has one unique parse. However, you cannot

distinguish wether to reduce the a+ sequence as non-terminal cfl1 or

cfl2 until seeing the final b or c terminal, which can be arbitrarily

far away--thus the grammar is not LR(k) for any k.

We used grammars like this to test Yacc++'s advanced lookahead modes

when we were first trying to make it LR(infinity), back in 1989 or so.

It's easy to construct an algorithm that handles cases like this.

Think of taking a limit (or closure). However, one eventually runs

into the wall that proving a context free grammar is unambiguous is

equivalent to solving the halting problem. Thus, when you have a

closure computing parser generator, there must be some context free

grammars it doesn't resolve, or some grammars it loops on. My

suspicion is that the algorithm we use will loop, but I could never

find a small test case that was comprehensible and also showed the

algorithm looping.

Hope this helps,

-Chris

*****************************************************************************

Chris Clark Internet : compres@world.std.com

Compiler Resources, Inc. Web Site : http://world.std.com/~compres

23 Bailey Rd voice : (508) 435-5016

Berlin, MA 01503 USA fax : (978) 838-0263 (24 hours)

------------------------------------------------------------------------------

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.