From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me
X-Spam-Level: 
X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00 autolearn=ham
	autolearn_force=no version=3.4.4
X-Google-Thread: a07f3367d7,4fd338e56f592cfb,start
X-Google-Attributes: gida07f3367d7,public,usenet
X-Google-NewGroupId: yes
X-Google-Language: ENGLISH,ASCII-7-bit
X-Received: by 10.180.10.196 with SMTP id k4mr2882867wib.6.1367665374530;
        Sat, 04 May 2013 04:02:54 -0700 (PDT)
Path: 
 hg5ni66809wib.1!nntp.google.com!feeder1.cambriumusenet.nl!feed.tweaknews.nl!194.109.133.83.MISMATCH!newsfeed.xs4all.nl!newsfeed4.news.xs4all.nl!xs4all!border4.nntp.ams.giganews.com!border2.nntp.ams.giganews.com!border2.nntp.dca.giganews.com!nntp.giganews.com!newsfeed.news.ucla.edu!nrc-news.nrc.ca!News.Dal.Ca!news.litech.org!news.etla.org!usenet.blueworldhosting.com!npeer01.iad.highwinds-media.com!news.highwinds-media.com!feed-me.highwinds-media.com!post02.iad.highwinds-media.com!news.flashnewsgroups.com-b7.4zTQh5tI3A!not-for-mail
From: Stephen Leake <stephen_leake@stephe-leake.org>
Newsgroups: comp.lang.ada
Subject: LALR parser question
Date: Sun, 28 Apr 2013 08:37:33 -0500
Message-ID: <85sj2aydwi.fsf@stephe-leake.org>
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.3 (windows-nt)
Cancel-Lock: sha1:WMBP1OaQOhCPvg7Uw/QC67KT8Bs=
MIME-Version: 1.0
X-Complaints-To: abuse@flashnewsgroups.com
Organization: FlashNewsgroups.com
X-Trace: ce0e1517d261dc7c1c72715631
X-Received-Bytes: 2967
Content-Type: text/plain
Date: 2013-04-28T08:37:33-05:00
List-Id: <comp.lang.ada>

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

This does not allow an empty declaration_list. But Ada does, so the
question is how can we add that to the grammar.

There are three choices:

1) Add an empty declaration choice to declaration_list:

declaration_list
  : ;; empty list
  | declaration
  | declaration_list declaration
  ;

This is now redundant; since declaration_list can be empty, the second
choice is not needed:

declaration_list
  : ;; empty list
  | declaration_list declaration
  ;

2) Add an empty declaration choice to declaration:

declaration
  : ;; empty declaration
  | object_declaration
  | subprogram_declaration
  ;; ...
  ;

3) Add another choice in package_body that leaves out declaration_list:

package_body
  : PACKAGE name IS declaration_list BEGIN statement_list END SEMICOLON
  | PACKAGE name IS BEGIN statement_list END SEMICOLON
  ;

OpenToken cannot handle choice 1; every occurance of declaration_list
appears to be empty, giving parse errors at parse time. For example, on
this input:

is begin;

gives a syntax error:
shift_conflict_bug.input:2:4: Syntax error; expecting 'EOF_ID' or
'IS_ID'; found BEGIN_ID 'begin'

I'm not clear if this is expected because of the way LALR works, or if
this is a bug somewhere in OpenToken (either the grammar generator or
the parser); any clues?

Choice 2 leads to a shift/reduce conflict in the production for
package_body; I believe extending the OpenToken parser to a generalized
parser would allow it to handle this option. However, the OpenToken
grammar generator currently reports a bug, instead of reporting the
conflict.

Choice 3 works with the current OpenToken, but of course it is very
tedious; every occurance of declaration_list must be handled in the
same way.

Any other ways to handle this problem?

-- 
-- Stephe