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

[Sean Leonard <[e-mail]>]

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