Re: [abnf-discuss] Mail regarding draft-seantek-constrained-abnf

[Paul Kyzivat <[e-mail]>]

On 7/8/16 5:08 PM, Jonathan Hansford wrote:
> Paul and Sean,
>
>
>
> Thanks for the replies. Life is too hectic at the moment, but I’m hoping
> I will find some time to properly read the I-D and your replies and see
> how it would all work for me. Is there a parser for constrained ABNF at
> the moment?

AFAIK there is not. As I said, the draft is a trial balloon. I think it 
still needs a lot of work, not on the general concept, but on how you 
link grammars together. (The use case that drives my interest is 
defining extensibility hooks in a grammar when defining a standard, and 
then writing another draft that adds syntactical extensions from such a 
hook.)

I'm not aware of a generally available parser for case-sensitive ABNF 
either. I developed extensions to Bap to do it, and made them available 
to the author on github, but he never took them. I saw somebody else 
with another (worse) implementation, but AFAIK it also at least hasn't 
made it into the web-based Bap linked to the ietf tools page.

	Thanks,
	Paul

> Jonathan
>
>
>
> =O)
>
>
>
> *From:*Sean Leonard [mailto:[e-mail]]
> *Sent:* 08 July 2016 17:23
> *To:* Paul Kyzivat <[e-mail]>; Jonathan Hansford
> <[e-mail]>; [e-mail]
> *Cc:* [e-mail]
> *Subject:* Re: Mail regarding draft-seantek-constrained-abnf
>
>
>
> +abnf-discuss@
>
> On 7/8/2016 8:06 AM, Paul Kyzivat wrote:
>
>     On 7/8/16 8:11 AM, Jonathan Hansford wrote:
>
>         Hi,
>
>
>
>         I’ve just discovered draft-seantek-constrained-abnf-00 and have
>         a couple
>         of questions:
>
>
>     Note that while Sean and I have been bouncing ideas around about
>     this for some time, the draft is a trial balloon and the specific
>     text is all Sean's. I'm not yet wild about some of the syntax, but
>     it is good to have something tangible written down to talk about.
>
>     So far it seems that only Sean and I are interested. If you are,
>     then that would make three.
>
>
> Yay for three!
>
>
>
>
>         1)      Does Constrained ABNF work with RFC 7405 “Case-Sensitive
>         String
>         Support in ABNF”? Either way, it might be worth mentioning that
>         RFC in
>         your I-D.
>
>
>     Certainly it does. The functionality is entirely orthogonal.
>
>
> Yes, what Paul said.
>
>
>
>
>         2)      Has there been any call to further constrain ABNF such that
>         rules can have length constraints applied to them? I’m not sure
>         how much
>         benefit there would be for RFCs (though I can think of examples
>         where
>         identifying such a constraint within the ABNF rather than just
>         within
>         the accompanying text would be beneficial), but a Constrained ABNF
>         compliant parser that included length constraints would be good.
>
>
>     I'm not aware of any such thing. Of course it already has repetition
>     constraints, but I guess that is not what you are looking for.
>
>     I have difficulty imagining how you would fit such constraints into
>     the syntax. The syntax of ABNF is pretty nice for what it does, but
>     it doesn't leave much room for extension because we are running out
>     of special characters. (Perhaps the possibilities could be expanded
>     by using unicode characters. Imagine what could be done with emojis
>     as operator characters.)
>
>
> Length constraints are expressible with current ABNF. Generically,
> suppose you have an identifier comprised of ALPHAs and DIGITs:
>
> identifier = 1*(ALPHA / DIGIT)
>
> Well, if you want to limit identifier to 20 chars, then you can say max
> twenty:
>
> identifier = 1*20(ALPHA / DIGIT)
>
> As Paul says, this is a repetition constraints, and is easy to analyze
> with the repeated symbols are fixed-width. But what about variable width?
>
> Well, suppose you have Domain from RFC 5321:
>
>
>
>    Domain         = sub-domain *("." sub-domain)
>
>    sub-domain     = Let-dig [Ldh-str]
>
>    Let-dig        = ALPHA / DIGIT
>
>    Ldh-str        = *( ALPHA / DIGIT / "-" ) Let-dig
>
>
>
> Now suppose you want to constrain Domain to be 255 chars. Such a
> constrained domain might be called DNSDomain. Then you can say:
>
>
>    DNSDomain ^ Domain = 1*255ASCII
>
>
> ...and that's it! Basically you have to compose a production that
> evaluates to a single symbol (character/integer), where the domain of
> the symbol is any possible character that can appear in the production.
> The minimum conforming production would be:
>
>
>    DNSDomain ^ Domain = 1*255(ALPHA / DIGIT / "-" / ".")
>
>
> The maximum conforming production would be:
>
>
>    DNSDomain ^ Domain = 1*255(%x00-FFFFFFFFFFFFFFFFFFFFFFFFF...(infinity))
>
>
> Reducing the production from a non-maximum to the minimum form, can be
> evaluated programmatically. A parser would need to evaluate the
> constrained production for all "reachable" single terminal symbols
> (characters/integers that may appear at least once), which can be done
> more-or-less in O(n) time. It adds all such integers to a set, and then
> expresses the set.
>
> It can also be shown that you can also integrate the constraint into the
> base production, at least for all non-recursive productions. In this
> case, you would have to break down Domain into a very, very long string
> of terminal symbol possibilities (essentially, expressing it as a huge
> finite state machine). Once you get all the possible states, you can
> limit each symbol combination so that the total combinations do not
> exceed 255. This can probably be done computationally, but the proof
> would require a lot of math that I do not care to figure out right now.
> :) And it's unclear how computationally difficult it would be to do it
> in the general case.
>
> Actually now that I think about it, if your constraint is to limit the
> total number of symbols, you can probably prove that any recursive
> expression can be expressed as a finite state machine. Therefore,
> integrating length constraints would actually be computable. It would
> also be super-ugly, but you get the point.
>
> ***
>
> Regarding Paul's Unicode point: it would be nice for ABNF to have an
> extension that defines the domain of the input symbols, with specific
> options for: ASCII-only, octets, fixed-bit-width units, UTF-8,
> UTF-16LE/BE, and Unicode scalar values (0-0xD7FF, 0xE000-0x10FFFF), and
> Unicode characters (non-characters such as 0xFFFF are excluded). The
> most important of these are ASCII-only, octets, and Unicode scalar values.
>
> I thought about writing such an I-D, but, it would take more work than I
> have time for right now, and one would have to address a few of issues.
>
> Currently the domain of ABNF is any unsigned integer, which is an
> infinite set. This is good in that you can express anything positive,
> and bad in that you can't express negative symbol productions (e.g., all
> symbols EXCEPT "Q"). Once you constrain the set to finite, you can
> express things like the regex [^Q]. This makes ABNF compilers more
> complex. If you really want to express exclusionary productions, maybe
> BNF languages aren't the right tool for the job?
>
> A compatibility problem arises when you want to reference productions
> from other specs, that have different domains. Suppose that one spec is
> authored in the UTF-8 domain (see LDAP specs e.g., RFC 4512), and other
> spec is authored in the Unicode scalar value domain. This is a real
> issue that I am encountering in draft-seantek-certspec, which I
> encourage you to read...I wanted to import (reference) distinguishedName
> from LDAP / RFC 4514, but distinguishedName includes UTF-8 multibyte
> productions, and draft-seantek-certspec is authored to be at least
> potentially character set neutral. It would be okay (in
> draft-seantek-certspec) to write the string in ISO-2022-JP and then
> convert it to something else.
>
> Converting between domains is computable (e.g., the Unicode scalar value
> expressed as %x1F60A 😊 can be broken down into %xD83D.DE0A or
> %xF0.9F.98.8A), but symbology for doing it would be arcane. We want to
> keep ABNF as simple as possible, and that stuff strikes me as calling
> for a complex syntax.
>
> Any proposal that involves Unicode is going to have to at least think
> about character properties and classes. See UTS #18.
>
> Both the Unicode Consortium and W3C use BNF flavors to describe Unicode
> things. As ABNF uses the same mathematical theories and their BNF
> flavors, it would be good to replicate syntax where possible.
>
> Regards,
>
> Sean
>
>
>
>         Thanks,
>         Paul
>
>
>
>
>
> _______________________________________________
> abnf-discuss mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/abnf-discuss
>