Re: LR(0) and Lookaheads

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

Return to the comp.compilers page.
Search the comp.compilers archives again.