[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Pasrser and EOF

Archie Cobbs wrote:
> First of all, I'm a little ignorant of the precise meaning of the
> word "backtracking" and hence when it is required by the language.
> What I think you mean is shown by this example:
>   Start =
>     pair*;
>   pair =
>     foo bar;

OK. Let's not waiste too much time arguing about this.

Mainly, the problem is what is the following:

LR parse stack: pair
No Lookahead information
Parser doesn't know if it should:
(1) reduce: pair -> start
(2) shift the next token. (It could be a "foo").

Now, if it looks ahead, the parser might see a "foo" and decide to
continue parsing. But this means that the following three inputs will
have inconsistent results:

foo bar foo eof -> No AST. Error.
foo bar bar eof -> One AST (foo bar). 2 errors: (bar), (eof).
foo bar eof -> One AST. No error (?).

If you want a more consistent result like:

foo bar foo eof -> One AST (foo bar). 1 (or 2) error: (foo eof).
foo bar bar eof -> One AST (foo bar). 1 (or 2?) error: (bar eof).
foo bar eof -> One AST. No error (?).

then you need backtracking. i.e.: restore the parse stack to the state
it was before reducing the second foo, then resume parsing by doing a
reduce action instead of a shift.

Hendrick seemed to be aware of this problem, and he proposed a very
elegant solution. His solution has the advantage that the parser will
NEVER look ahead beyond the last token of a string of the recognized
language; which is exactly what we want.