Re: Forcing multiple parse stacks to 'reduce'

[Hans Aberg]

At 17:03 +0000 2005/02/28, Derek M Jones wrote:
>I have written a parser for C that processes
>a single statement or declaration at a time.
>So after each statement/declaration yyparse
>returns.

Bison is clearly not built to handle such applications. The normal thing is
to handle the whole language in one go. (How do you handle environments,
like "{...}" statement-by-statement?)

>Originally I used various ad-hoc rules in yylex
>to figure out which was the last token of a
>statement/declaration and then returned a zero
>value as the subsequent token.
>
>These ad-hoc rules are complicated (for instance,
>a ; can occur in a for loop header and a { can
>occur in a cast) and I had the 'great' idea of allowing
>the token following the last token of a statement/declaration
>to 'naturally' cause yyparse to generate the outstanding
>reductions.  So in:
>
>w=3;
>y=5;
>
>when yylex returns id (because it has encountered y)
>the sequence w=3; reduces to statement and yyparse
>returns (yes, I need to hang onto y in order to correctly
>parse the next statement).
>
>In some cases multiple parse stacks are outstanding,
>and in most cases the following token causes the expected
>return to deterministic parsing and subsequent reduction to
>the accept state.  But in some cases it does not.  For instance,
>in
>
>typedef x y;
>
>by the time the ; is encountered there are three parse stacks.
>Depending on the token that follows the ; these three parse stacks
>may or may not be reduced to a single stack (which then reduces
>to a declaration).
>
>In the case:
>
>typedef x, y;
>typedef i, j;
>
>the second typedef token is shifted onto all three stacks and
>subsequent tokens are processed like a declaration (which they
>do form part of)!  So I don't get a parse of a single declaration
>(in fact yyparse eventually reports an ambiguity).
>
>I know that for some grammars the optimizations performed by
>Bison result in ambiguities being reported (i.e., the BOGUS
>example in 5.7 of bison.info).
>
>In my case no ambiguity is being reported (I am in glr mode
>after all ;-).  But the parse stacks are not being reduced as
>expected (all three are in the state I would expect them to be
>in when the second typedef token is encountered).
>
>Does anybody have any ideas on how I can force yyparse
>to consider reductions in the number of parse stacks and
>thence reductions to the accept state?

In general, there is none, it seems. The idea of the GLR is that
reduce/reduce conflicts may split the deterministic parser, until the
ambiguity is resolved later in the parsing. The manual mentions the use of
%dprec to choose between different actions, but that seems to be it. (I am
not using %glr myself, so I am guessing here.)

You might try to rewrite your input grammar so that when the ";" of a
typedef is encountered, it reduces.

Alternatively, you might try an entirely new approach to your whole program
setup. You have not told us why you need this feature, to halt after each
statement. Is it imperative that the parser halts right after the statement
is finished? If not, assuming that the you have written a correct parser,
you might attempt to halt it in the actions. The feature is similar to that
of so called coroutines (part of Simula, for example). Coroutines can be
implemented using threads. So you might use threads to achieve the same
effect: Put the parser in a thread. Activate it. When an action where you
want the parser to halt is executed, as a part of the action, halt the
parser thread. Then do the other stuff you want to do. When parsing needs to
be resumed, reactivate the parser thread.

  Hans Aberg