Re: LALR parser question

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

Stephen Leake <stephen_leake@stephe-leake.org> writes:

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

I misread Randy's grammar the first time; it is actally a fourth choice.
In my terms, it is:

package_body
 : IS declarative_part BEGIN SEMICOLON
 ;

declarative_part
 : ;; empty
 | declaration_list
 ;

declaration_list
 : declaration
 | declaration_list declaration
 ;

OpenToken definitely has a bug in processing this grammar; the empty
production is simply not considered. That leads to incorrect errors at
parse time.

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

My choice 2 is in fact ambiguous, and does have a shift/reduce conflict.
Consider these statements:

1) is <null declaration> begin ;
2) is is <null declaration> begin ; begin ;
3) is <null declaration> is <null declaration> begin ; begin ;

In parsing 3), the second 'is' causes a shift/reduce conflict;
shift to start the nested declaration (as in 2), reduce to the null
declaration. Both are correct according to the grammar.

OpenToken has the same bug in handling this empty production, but it
shows up sooner, because it interferes with the conflict reporting code.

-- 
-- Stephe