[antlr-interest] Problem with EBNF

[Kevin J. Cummings]

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

> Regards,
> Morten

-- 
Kevin J. Cummings
kjchome at rcn.com
cummings at kjchome.homeip.net
cummings at kjc386.framingham.ma.us
Registered Linux User #1232 (http://counter.li.org)