[antlr-interest] Problem with EBNF

John B. Brodie jbb at acm.org
Sun Dec 5 15:17:28 PST 2010


Greetings!

On Sun, 2010-12-05 at 21:44 +0100, Morten Olav Hansen wrote:
> Hi, thanks for your reply.
> 
> Sorry if it wasn't clear, but the ordering does not matter.
> 
> The rule you proposed is basically what I had before, and as you say,
> it allows any number of ps* keywords.
> 
> What I meant by "rule combinations" (not sure what else to call them)
> is writing out all possible combinations.
> 
> (... psinitial=psinitialDecl ... finalstate=finalstateDecl? ...)
> (... finalstate=finalstateDecl ... psinitial=psinitialDecl? ...), etc.
> 
> But maybe theres no elegant way of doing this. Maybe adding some
> region scoped variables would be better, and setting hasInitial, etc,
> and doing the check in the grammar.

i think you should not try to do this in the parser, but rather keep
your checking in a separate semantic pass over the AST.

however what you want to do is possible ---- i think, haven't actually
tried it ---- by using Gated Semantic Predicates. not sure what sort of
error messages are produced when using them tho --- a reason to keep a
separate checking pass.

basically use a bunch of flags as you speculate.

something like this (untested):

rule_name_goes_here : 
@init{
    boolean initPresent = false;
    boolean finalPresent = false;
    boolean histPresent = false;
    boolean deepPresent = false;
  }
  'region' ID=identifier? '{' (
        ( { !initPresent }?=> i=psinitialDecl { initPresent=true; } )
      | ( { !finalPresent }?=> f=finalStateDecl { finalPresent=true; } )
      | ( { !histPresent }?=> h=pshistoryDecl { histPresent=true; } )
      | ( { !deepPresent )?=> d=dpsdeephistoryDecl {deepPresent=true;} )
      | s+=stateDecl
      | t+=transitionDecl
    )* '}' ';'?
  ;

notice that there are no ? nor * operators inside the outer ( )* loop. 

the ?'s are unnecessary because the Gated Predicates deal with the zero
or one semantics.

no *'s because a * loop inside another * loop introduces syntactic
ambiguity (e.g. (foo*)* is ambiguous).

hope this helps....
   -jbb


> On Sun, Dec 5, 2010 at 9:22 PM, Kevin J. Cummings
> <cummings at kjchome.homeip.net> wrote:
> > On 12/05/2010 12:09 PM, Morten Olav Hansen wrote:
> >> Hi!
> >>
> >> I have a problem with my EBNF I was hoping for a little help with. I
> >> have a block in my grammar that can contain certain keywords
> >> zero-or-one times, and other keywords zero-or-many times. My current
> >> solution is to enable every keyword to be zero-or-many, and then let
> >> my semantic checker deal with the problem. But I was hoping to solve
> >> it already on the grammar side, if possible.
> >>
> >> The basic block looks like this:
> >>
> >>       :       'region' ID=Identifier? '{'
> >>                       (
> >>                               psinitial=psinitialDecl?
> >>                               finalstate=finalstateDecl?
> >>                               pshistory=pshistoryDecl?
> >>                               psdeephistory=psdeephistoryDecl?
> >>                               states+=stateDecl*
> >>                               transitions+=transitionDecl*
> >>                       )
> >>               '}' ';'?
> >
> > Why doesn't this work for you?  There is an implied ordering here as in:
> > if finalstateDecl appears, it must be after the psinitialDecl, and
> > likewise for the rest.  All stateDecls must appear after any
> > psinitialDecl, finalstateDecl, pshistoryDecl, psdeephistoryDecl, and
> > before any transitionsDecls, and all transitionDecls mus appear at the
> > end after everything else.
> >
> > >From what I can see, the ()'s above are completely optional in your
> > grammar and only are provided for grouping, which in this case, to me,
> > seems unnecessary.  Did I miss something?
> >
> >> And the only solution I have come up with, is to generate every
> >> possible variant of this grammar, which is quite ugly.
> >>
> >> What would be nice, would be something like this:
> >>
> >>       :       'region' ID=Identifier? '{'
> >>                       (
> >>                               psinitial=psinitialDecl?
> >>                               finalstate=finalstateDecl?
> >>                               pshistory=pshistoryDecl?
> >>                               psdeephistory=psdeephistoryDecl?
> >>                               states+=stateDecl*
> >>                               transitions+=transitionDecl*
> >>                       )*
> >>               '}' ';'?
> >
> > How about this:
> >
> >        :       'region' ID=identifier? '{'
> >                        (
> >                                psinitial=psinitalDecl
> >                        |       finalstate=finalstateDecl
> >                        |       pshistory-pshistoryDecl
> >                        |       psdeephistory=psdeephistoryDecl
> >                        |       states+=stateDecl
> >                        |       transitions+=transitionDecl
> >                        )*
> >                '}' ';'?
> >
> > But this does not enforce the implied ordering of your first example,
> > and would allow any number of these to appear in any order.
> >
> > You would also have to keep track of (deal with) whether
> > psinitial/finalstate/pshistory/psdeephistory appear more than once, and
> > make sure that your states and transitions collect properly.
> >
> >> (with * at the end). And for every match to one of the zero-or-one
> >> rule, it would take it "away", so it can not be matched again. But
> >> this does not work.
> >
> > If you move your ? & * from inside the ()'s to outside, you will want to
> > remove them from the inside.  You could do this, but it will not enforce
> > the implied ordering that I see in the first example.
> >
> >> Any suggestions on how to solve this? If I have to end up with every
> >> possible rule combination, then I would probably be better of just
> >> doing it in the semantic checker as I was doing.
> >
> > I don't see any "rule combinations" since the original rule enforces and
> > ordering to the rules that you probably want to keep....
> >




More information about the antlr-interest mailing list