8 Feb 2004 22:09:33 -0500

Related articles |
---|

Quick way to recognize grammar type srivatsar@yahoo.com (2004-02-01) |

Re: Quick way to recognize grammar type haberg@matematik.su.se (2004-02-04) |

Re: Quick way to recognize grammar type joachim.durchholz@web.de (Joachim Durchholz) (2004-02-04) |

Re: Quick way to recognize grammar type cfc@shell01.TheWorld.com (Chris F Clark) (2004-02-04) |

Re: Quick way to recognize grammar type scavadini@ucse.edu.ar (2004-02-08) |

Re: Quick way to recognize grammar type tbauer@cadrc.calpoly.edu (Tim Bauer) (2004-02-08) |

From: | scavadini@ucse.edu.ar |

Newsgroups: | comp.compilers |

Date: | 8 Feb 2004 22:09:33 -0500 |

Organization: | Compilers Central |

References: | 04-02-014 04-02-048 |

Keywords: | parse |

Posted-Date: | 08 Feb 2004 22:09:33 EST |

*>Is there any way of determining quickly if a given grammar is one of*

*>LL(0)/LR(0)/LALR/LR(1). I know that we can construct the set of items*

*>and hence the parsing table. But I am looking for some tricks/tips by*

*>which we can quickly determine if the grammar is one of the above four*

*>types.*

Some definitions first:

"null" no-terminal symbol: a no-terminal tha ONLY derives or produces the

null string (lambda)

"p-reduced" no-terminal symbol: a no-terminal symbol tha is not "null"

"p-reduced" grammar: a reduced grammar with all it's no-terminal symbols

"p-reduced"

You can compute First(1) sets to know if the no-terminals are "null" or

"p-reduced":

if First(A) == {lambda} then A is NULL

if First(A) != {lambda} then A is P-REDUCED

Then check if the grammar is LL(1).

We know that when a CFG is LL(1) then it's LR(1). The problem is that this

is not true for other members of the LR family: LR(0), SLR(1) and LALR(1).

But there are two sufficient conditions that can help us:

if a CFG is LL(1) AND

a) do not have lambda-rules, then the CFG is LR(0)

b) is "p-reduced", then is LALR(1)

If you know that the CFG G is reduced and LL(1) then:

if G don't have lambda-rules then

G is LR(0)

else

if G is "p-reduced" then

G is LALR(1)

else (there are lambda-rules and null terminals in G)

You must try to construct the LALR automaton and check for conflicts...

endif

endif

These are ideas from

On the relationship Betwen the LL(1) and LR(1) Grammars.

John C. Beatty

JACM Vol. 29, Nš 4, 1982.

Hope this help

Salvador Cavadini

http://www.ucse.edu.ar/fma/staff/svcavadini

Software for Teach Parsing Techniques: www.ucse.edu.ar/fma/sepa

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.