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: 103376,4fd338e56f592cfb X-Google-NewGroupId: yes X-Google-Attributes: gida07f3367d7,domainid0,public,usenet X-Google-Language: ENGLISH,ASCII-7-bit X-Received: by 10.66.146.168 with SMTP id td8mr7616546pab.17.1367833556508; Mon, 06 May 2013 02:45:56 -0700 (PDT) Path: ln4ni1451pbb.0!nntp.google.com!npeer02.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 Newsgroups: comp.lang.ada Subject: Re: LALR parser question References: <85sj2aydwi.fsf@stephe-leake.org> <85zjwc8khm.fsf@stephe-leake.org> Date: Mon, 06 May 2013 04:45:54 -0500 Message-ID: <85li7s786l.fsf@stephe-leake.org> User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.3 (windows-nt) Cancel-Lock: sha1:hmmCqRFnprhPi/Jja4rr3H2dkg0= MIME-Version: 1.0 X-Complaints-To: abuse@flashnewsgroups.com Organization: FlashNewsgroups.com X-Trace: 4f40651877bd4c7c1c72711917 X-Received-Bytes: 3928 Content-Type: text/plain Date: 2013-05-06T04:45:54-05:00 List-Id: Stephen Leake writes: > "Randy Brukardt" writes: > >> "Stephen Leake" 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 begin ; 2) is is begin ; begin ; 3) is is 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