Re: Error reporting, was Infinite look ahead required by C++?

Stephen Horne wrote:
>> Those use LALR(1), though LR(1) support may be in the works for Bison,
>
> Just making sure I haven't misunderstood...
>
> LALR(1) is basically a minor variation of LR(1). The derivation of the
> state model is a little different, but each state still has a set of
> valid next tokens, used to choose between shifting and reducing.


Whether minor or radical variation probably depends on your taste.


LALR(1) can be computed in linear time I think. LR(1) can blow up
exponentially, just as common NFA to DFA conversions.


Therefore, one commonly do not implement pure LR(!), but one that
compacts the states. In the past, this must have been very important, in
view of the limited capacity of past computers.


>> which compacts the states in such a way that when an error token
>> appears, some extra reductions may take place before issuing the error.
>
> This sounds like table compression modified by some form of
> preprocessing of the state model, but it doesn't sound like an
> inherent part of LALR, but rather an optimisation specific to Bison?


Bison just implements straight off some common LALR(1) algorithm, I do
not recall exactly what.


When an error token appears in the input, it may not, due to the
compaction technique be in the present state, but only in one appearing
after some reductions. NO extra error token will be read, though.


The same thing may though happen in what is labeled as LR(!), as what is
actually implemented may use a similar state compaction technique.


      Hans

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