19 Aug 1998 21:28:40 -0400

Related articles |
---|

Types of grammars. Luke@comodo.techi.com.force9.net (Luke) (1998-08-19) |

Re: Types of grammars. cfc@world.std.com (Chris F Clark) (1998-08-19) |

Re: Types of grammars. cfc@world.std.com (Chris F Clark) (1998-08-20) |

Re: Types of grammars. adrian@dcs.rhbnc.ac.uk (1998-08-24) |

Re: Types of grammars. sergenth@tin.it (1999-05-20) |

Re: Types of grammars. hunk@alpha1.csd.uwm.edu (1999-06-02) |

From: | Chris F Clark <cfc@world.std.com> |

Newsgroups: | comp.compilers |

Date: | 19 Aug 1998 21:28:40 -0400 |

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

References: | 98-08-134 |

Keywords: | parse |

"Luke" <Luke@comodo.techi.com.force9.net> asked:

*> Could somebody please tell me how all the grammars fit together? i.e. Is an*

*> LL(k) grammar a subset of LR(k)?*

1) All LL(k) grammars are LL(k+1) grammars.

2) All LR(k) grammars are LR(k+1) grammars.

3) All LALR(k) grammars are LALR(k+1) grammars.

4) All LALR(k) grammars are LR(k) grammars.

5) All LL(k, for any k) grammars are LR(1) grammars.

6) All LR(0) grammars are LALR(1) grammars.

But

7) There are LL(k) grammars which are not LALR(1) grammars,

nor LR(0) grammars. (The LR(0) method throws away left context the

LL(k) grammars preserve, and the LALR method does not restore all

of it, but the LR(1) method does.)

*> Also, when building LR state diagrams, are the epsilon productions also*

*> included?*

*>*

*> i.e.*

*> stmt -> .expr '+' expr*

*> stmt -> .E*

*> Where E == epsilon.*

Yes, but you should think of the dot as being pushed through the

epsilon and ending up at the end of the rule, which means there will

be some reduce actions (or conflicts) in that state. Does that make

any more sense?

Epsilon is an important concept, but in this case it is confusing,

which is why I prefer a more yacc-like notation without any epsilons,

but with terminating semi-colons and with empty rules allowed.

Thus, your example would be written:

stmt : .expr '+' expr ;

stmt : .;

In this notation, when you get the dot to the semi-colon, it means

there are reduce transitions.

Hope this helps,

-Chris

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

Chris Clark Internet : compres@world.std.com

Compiler Resources, Inc. CompuServe : 74252,1375

3 Proctor Street voice : (508) 435-5016

Hopkinton, MA 01748 USA fax : (508) 435-4847 (24 hours)

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

Web Site in Progress: Web Site : http://world.std.com/~compres

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.