Re: Lookahead vs. Scanner Feedback

Jan.Rekers@cwi.nl (Jan Rekers) writes:


>We use a different approach:
>As we use the GLR parsing technique, which is an LR parser which is
>able to split up in several LR parsers on a conflict, we are able to
>solve this problem in a very general way. The scanner just returns
>all possible interpretations of a token, the parser splits up to
>pursuit the different possibilities; some of these will die in the
>sequel and the correct choice survives. This leaves all information
>about the grammar out of the lexical scanner and is guaranteed to
>work for any case without any inspection of the grammar by a programmer.


I hate to disagree with my friend Jan, but this idea of splitting
off alternative parses introduces other nasty problems and it is
not clear that you would be any better off. Consider the
following C expression:
(foo)-3
This has two different parses depending on whether foo is declared
as a variable or as a typedef name. I.e., if foo is an int variable
then the expression is equivalent to foo-3; but if foo is a typedef
name, then the expression is equivalent to (foo)(-3) where a type
cast is being applied.


If we feed a program containing the k consecutive statements
v1 = (foo)-1;
v2 = (foo)-2;
v3 = (foo)-3;
.
.
vk = (foo)-k;
into Rekers' parser, we should get back at least 2**k different
parses.


The only way to prevent this combinatorial explosion of
possibilities is to kill off the alternative parse possibilities
as they are created. For example, the C grammar rule
<Expression> ::= ( <type-name> ) <Expression>
would need to have an associated semantic test to check whether
the type-name has actually been declared as a type name and, if
not, suppress this particular parsing possibility.


Thus there has to be feedback from semantic analysis into the
parser. I don't believe this is any great improvement over the
conventional approach of having feedback from semantic analysis to
the lexer so that typedef names can be returned as a different kind
of token.


Nigel Horspool
University of Victoria
--

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