1 Dec 2004 23:14:57 -0500

Related articles |
---|

How to check if grammar is LR(k) hhsaffar@gmail.com (2004-11-28) |

Re: How to check if grammar is LR(k) cfc@shell01.TheWorld.com (Chris F Clark) (2004-12-01) |

Re: How to check if grammar is LR(k) schmitz@i3s.unice.fr (Sylvain Schmitz) (2004-12-05) |

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

Newsgroups: | comp.compilers |

Date: | 1 Dec 2004 23:14:57 -0500 |

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

References: | 04-11-113 |

Keywords: | parse, LR(1) |

Posted-Date: | 01 Dec 2004 23:14:57 EST |

Hossein Saffar asked:

*> Is it possible to find out if a grammar is LR(k) or not without making*

*> the parsing table?*

1) There are some sets of grammars which are known to be LR(k). For

example, if all the recursion in the grammar is either left or

right (but not a mixture of some left and some right)--the grammar

is linear and all linear grammars are LR(k). Similarly, if the

grammar is known to be LL(k), the grammar is known to be LR(k), but

not necessarily SLR(k) or LALR(k).

2) Likewise, there are some things know to make a grammar inherently

not LR(k), ambiguity is one of them. Thus, the inclusion of a rule

like "A: A A ; /* A being a non-terminal */" is ambiguous and means

any grammar with the rule used in it is not LR(k).

3) There is an algebra promoted by Mark William Hopkins (sp?) that

purports to solve the LR problem, but produces results that have

always struck me as supiciously contradictory of other facts I know

of grammar theory. However, perhaps I just don't understand.

4) Making a parser table is easy (well, perhaps not by hand for a

non-trivial grammar, but quite easy once mechanized).

Why do you ask?

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