Re: [xdi] ABNF pattern question - maybe for Joseph?

[Markus Sabadello <markus.sabadello@xdi.org>]

I would be curious about that as well, myself I don't know the answer.

It might just not be possible with certain parser implementations such as this left-recursive one.

One thing I might point out is that the online interactive version of APG is version 6.1, whereas the downloadable version is 6.3.

One case where this manifests is when you parse our XDI grammer, the interactive version of APG will say that some of the rules are "infinite", which is a bad thing.

Self-Recursive Attributes

RULE NAME	LEFT	NESTED	RIGHT	EMPTY	INFINITE	CYCLIC
attr-member-context	x	√	x	x	√	x
collection-context	x	√	x	x	√	x
collection-inverse	x	√	x	x	√	x
collection-rooted	x	√	x	x	√	x
local-inverse	x	√	x	x	√	x

However, when I process the same ABNF with the downloadable 6.3 APG as opposed to the online interactive 6.1 one, it does NOT identify any "infinite" rules, and everything is fine.

So my point is, the online APG seems to be a bit buggy, but I don't think this changes anything about the effects we have observed.

Markus

On Mon, Mar 4, 2013 at 8:32 AM, Drummond Reed <drummond.reed@xdi.org> wrote:

I'm posing this question of everyone on the TC but hoping Joseph might have some time to dig into it. 

When I completed my action item from last Fridays's telecon to shorten the Ful Graph ABNF by condensing some of the rules (see the 2013-03-02 post to https://wiki.oasis-open.org/xdi/XdiAbnf/Discussion), I also update it with Markus' simpler version of the collection-context and literal-context rules. See the bolded lines below (these most likely wrap in this email).

literal                 = literal-value / literal-ref
literal-value           = literal-context "/!/" data-xref
literal-ref             = literal-context "/!/()"                                                              <== NEW

context                 = peer / peer-relative-context / relative-context
peer                    = 1*xref
peer-relative-context   = peer relative-context
relative-context        = 1*( singleton / ( collection [ member ] ) )

collection-context      = [ peer ] *( singleton / ( collection [ member ] ) ) collection

member-context          = member [ relative-context ]

literal-context         = [ peer ] *( singleton / ( collection [ member ] ) ) ( attribute-singleton / collection attribute-member )   

The problem is that, as Markus noted, these don't actually work with the Interactive APG parser. I did a little testing this weekend and found it's because the "tail matching" pattern itself doesn't work. For example, I created this very simple test of an ABNF _expression_ that would match a string containing any combination of letters and digits as long as it ended it a digit:

ID        =  *( DIGIT / ALPHA ) DIGIT

ALPHA     =  %x41-5A / %x61-7A   ; A-Z / a-z

DIGIT     =  %x30-39     ; 0-9

As I suspected, it doesn't work. As Markus detected last week, the greedy algorithm "sucks up" all the letters and digits in the *( DIGIT / ALPHA )rule and doesn't leave any to match the final DIGIT rule. 

So, here's my question to Joseph (or anyone else who's deep enough into ABNF to answer it): is there an ABNF pattern I'm missing that's able to match the tail token in a sequence of tokens?

That's what we need for the collection-context and literal-context rules in the Full Graph ABNF.

Thanks,

=Drummond