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

["Jonathan Hansford" <[e-mail]>]

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?

 

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