Re: LALR parser question

[Stephen Leake <stephen_leake@stephe-leake.org>]

"Randy Brukardt" <randy@rrsoftware.com> writes:

> "Stephen Leake" <stephen_leake@stephe-leake.org> wrote in message 
> news:85sj2aydwi.fsf@stephe-leake.org...
>> As part of Emacs Ada mode 5.0, I'm building a generalized LALR grammar
>> for Ada (see
>> http://stephe-leake.org/emacs/ada-mode/emacs-ada-mode.html#ada-mode-5.0 )
>>
>> I'm having trouble with empty declarations. For example (using Bison
>> syntax for the grammar), a simplified subset of the Ada package_body sytax 
>> is:
>>
>> package_body
>>  : IS declaration_list BEGIN SEMICOLON
>>  ;
>>
>> declaration_list
>>  : declaration
>>  | declaration_list declaration
>>  ;
>>
>> declaration
>>  : object_declaration
>>  | subprogram_declaration
>>  ;; ...
>>  ;
>>
>> 1) Add an empty declaration choice to declaration_list:
>>
>> declaration_list
>>  : ;; empty list
>>  | declaration_list declaration
>>  ;
>>
> > 2) Add an empty declaration choice to declaration:
> >
> > declaration
> >   : ;; empty declaration
> >   | object_declaration
> >   | subprogram_declaration
> >   ;; ...
> >   ;


> Choice 1 here is the best way to do this for an LALR(1) grammar. The 
> equivalent part of the Janus/Ada grammer reads:
>
> package_body ::= package_head declarative_part block_option ## 8
>
> declarative_part ::= dec_option ## 0
> dec_option ::= pragma_option
>     | dec_option declaration pragma_option
>     | dec_option body_dec pragma_option ## 0
>
> pragma_option ::= pragma_option pragma_stmt
>     | ## 0                                             -- Empty production
>
> "declaration" and "body_dec" include the usual suspects, and no empty
> parts.

This actually the same as my choice 2; the empty production is not in
the list rule (dec_option), it's in one of the options of that rule
(pragma_option).
 
> This generates a grammar with no conflicts.

I get a conflict with choice 2, but I now believe that's a bug; I think
there's something wrong with the lookahead propagation step.

>> Any other ways to handle this problem?
>
> Get a better parser generator?? 

I'm fixing OpenToken; I'm asking if the OpenToken behavior for choice 1
is a bug. You have not directly addressed that, but thanks for letting
me know someone is using LALR in a commercial product!

-- 
-- Stephe