8 Nov 2001 01:11:01 -0500

Related articles |
---|

LR(0) and Lookaheads willverine@hotpop.com (Will) (2001-11-04) |

Re: LR(0) and Lookaheads thant@acm.org (Thant Tessman) (2001-11-08) |

Re: LR(0) and Lookaheads jjan@cs.rug.nl (J.H.Jongejan) (2001-11-08) |

From: | "J.H.Jongejan" <jjan@cs.rug.nl> |

Newsgroups: | comp.compilers |

Date: | 8 Nov 2001 01:11:01 -0500 |

Organization: | Groningen University (NL) |

References: | 01-11-007 |

Keywords: | parse, LR(1) |

Posted-Date: | 08 Nov 2001 01:11:01 EST |

Will wrote:

*>*

*> The new dragon book gives an algorithm for constructing parsing tables*

*> for LR(1) grammars. The '1' is suppose to be 1 lookahead. If you can*

*> construct such an LR(1) parsing table without conflicts for a given*

*> grammar, then the grammar is LR(1) grammar.*

*>*

*> Is lookahead and the current input symbol the same thing?*

It is.

*>*

*> I had thought that LR(0) was just another way of saying SLR(1) because*

*> in constructing SLR(1) grammars, LR(0) items are used. However I am*

*> wrong. As a matter of fact, LR(0) grammars are "smaller" than SLR(1)*

*> grammars. So how do I test a grammar to see if it is LR(0) grammar*

*> (i.e. where in the new dragon is this explained ... how do you*

*> construct a LR(0) parsing table)? Also the '0' in LR(0) grammars means*

*> 0 lookahead? That does not make sense, unless I am not understanding*

*> what lookahead means. If you don't look at any input symbols, how are*

*> you suppose to parse the input string?*

LR(0) means that, after calculating the sets of items (states), you

can decide between accept,error,shift,reduce without inspecting the

next input symbol. After you decide e.g. to shift you inspect what

token you have read and determine the next state number.

In SLR(1) a state can contain shift and/or reduce items at the same

time; now you will have to inspect the next input symbol to make a

decision between the shifts and/or reduce actions.

LR(0) and SLR(1) use the same states, so "smaller" is not applicable

in this situation.

--

My $0.02

Jan Jongejan

Dept. Comp.Sci.,

Univ. of Groningen,

Netherlands.

email: jjan@cs.rug.nl

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.