Re: Forcing multiple parse stacks to 'reduce'

[Derek M Jones]

Hans,

>>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?)

I don't see why not.  Bison is built to handle grammars.
My grammar does not support sequences of  statements
or declarations.  The whole language, in my case, consists of
one statement or one declaration (which includes the
header of a function definition).  Characters such as { }
are not part of the grammar (they are handled by a higher
level routine).

My aim is to parse the visible source (i.e., preprocessing
directives are ignored).  Error recovery is better if
statements/declarations are parsed individually.  'Errors'
might be caused by conditional preprocessor directives
that select how a statement, for instance, should be processed.
Single statement/declaration at a time localises syntax errors.

>>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.)

%dprec is designed to resolve ambiguities between multiple parse
stacks.  My multiple parse stacks are in agreement with each other.  

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

My question is how do I do that?  My grammar is copied
straight from annex A of the C Standard (plus six or so %dprecs
and two changes from right recursion to left recursion).

I am guessing that some form of lazy evaluation is being used
internally by Bison.  After all, in most cases an end-of-file
indicator is used to force reductions.

>Alternatively, you might try an entirely new approach to your whole program
>setup. You have not told us why you need this feature,

See above.


derek

--
Derek M Jones                                           tel: +44 (0) 1252 520 
667
Knowledge Software Ltd                            mailto:address@hidden
Applications Standards Conformance Testing   http://www.knosof.co.uk