[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.
Etienne