LR(1) grammar/parser and lookahead-restrictions

Michael Dyck jmdyck at
Tue Feb 7 14:39:15 UTC 2017

On 17-02-06 07:32 PM, Waldemar Horwat wrote:
> On 02/04/2017 07:20, Michael Dyck wrote:
>> On 17-02-03 05:32 PM, Waldemar Horwat wrote:
>>> On 02/03/2017 08:17, Michael Dyck wrote:
>>>> On 17-02-02 06:23 PM, Waldemar Horwat wrote:
>>>>> Lookahead restrictions fit very well into an LR(1) engine
>>>> Again: Great, but how? E.g., do you pre-process the grammar, modify the
>>>> construction of the automaton, and/or modify the operation of the parser?
>>> For each state × token combination, the automaton describes what happens
>>> when you're in state S and see a token T.  The lookahead restrictions remove
>>> possible transitions; without them there would be ambiguities where a given
>>> state × token combination would want to do two incompatible things.
>> Okay, so do you generate the automaton (ignoring lookahead restrictions)
>> and then remove transitions (using lookahead restrictions)? Or do you
>> integrate the lookahead-restrictions into the generation of the automaton?
> It's integrated.  You can't generate a valid automaton without the lookahead
> restrictions.

So, when you're making LR items for a production with a 
lookahead-restriction (l-r), do you:

-- treat the l-r as a (nullable) symbol, so that you get an item with the 
dot before the l-r, and one with the dot after, or

-- treat the l-r as occurring between two adjacent symbols, so that you get 
an item where the dot is "at" the l-r, or

-- something else?


More information about the es-discuss mailing list