1 Nov 2006 00:55:35 -0500

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: | Leonardo Teixeira Passos <leonardo@dcc.ufmg.br> |

Newsgroups: | comp.compilers |

Date: | 1 Nov 2006 00:55:35 -0500 |

Organization: | POP-MG/RNP |

References: | 06-10-101 06-10-117 |

Keywords: | parse, LR(1) |

Posted-Date: | 01 Nov 2006 00:55:35 EST |

On Thu, 26 Oct 2006, Chris F Clark wrote:

*> 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;*

*>*

I've tried your grammar, but it happens that it is a genuine LALR(1)

grammar, and thus LR(1).

This can be seen when the closure operation is executed in the

generation of the 1st LR(0) state:

goal ::= (*)nt1

goal ::= (*)nt2

nt1 ::= (*) cfl1 "b"

nt2 ::= (*) cfl2 "c"

cfl1 ::= (*) "a"

cfl1 ::= (*) cfl1 "a"

cfl2 ::= (*) "a"

cfl2 ::= (*) cfl2 "a"

As can be infered from that, in the LALR(1) machine cfl1 and cfl2 will be

reduced in the presence of "b" and "c" respectively, causing no conflicts.

However, based on your example, I've wrote a non LALR(k) grammar that

meets conditions (i) and (ii):

s ::= a | b ;

a ::= b1 A ;

b ::= b2 B ;

b1 ::= B b1 | B ;

b2 ::= B b2 | B ;

That suits my needs, although I haven't checked if it is a non LR(k)

grammar - a non LALR(k) was ok for me :)

Thanks for your help and patience.

*> 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.*

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.