Re: Forcing multiple parse stacks to 'reduce'

[Hans Aberg]

At 19:24 +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?)
>
>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).

You are clearly not parsing the full C language then, but some subsets. It
is hard to for me to judge, as I do not know what you are doing.

>My aim is to parse the visible source (i.e., preprocessing
>directives are ignored).  Error recovery is better if
>statements/declarations are parsed individually.

LALR(1) usually provides very basic error recovery, as the states LR(1) are
merged together in a way that when an error token is detected, reductions
may become performed before the error is reported. So LR(1) might be better,
but Bison does not support that yet.

>'Errors'
>might be caused by conditional preprocessor directives
>that select how a statement, for instance, should be processed.

C in reality has two languages, a preprocessor language, that produces a
single stream as output. Then that stream is parsed by the actual C
compiler. If you want to get inputs on how to sync that for error reoprting,
you check out te GNU GCC compiler.

>Single statement/declaration at a time localises syntax errors.

But if that is your only motivation, it does not seem mecessary to actually
abort the compilation process, to read one statement at a time.

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

See my other reply. I have a vague memory that people have better ways to
use a LALR(1) grammar with C. Check the newsgroup comp.copmilers and its
FAQ, published there monthly. The original grammar fomr the standrad is
probaly unsuitable for direct LALR(1) implementation.

>I am guessing that some form of lazy evaluation is being used
>internally by Bison.

No.

>After all, in most cases an end-of-file
>indicator is used to force reductions.

This is just a consequence of how the LALR(1) algorithm works. See for
example the AHO et all "Compilers...) ("Dragon") book. For a given input
grammar, one creates an new "augmented" grammar with an endmarker. Provides
push-down automaton is created from that. One is thus parsing a sentence
with a given endmarker, which must be provided by the lexer.

  Hans Aberg