Re: [abnf-discuss] ABNF colloquialism for end-of-line

[Sean Leonard <[e-mail]>]

> On Nov 16, 2017, at 11:31 PM, Dave Crocker <[e-mail]> wrote:
> 
> Carsten,
> 
> On 11/15/2017 6:35 PM, Carsten Bormann wrote:
>> Hi Dave,
>> On Nov 15, 2017, at 23:37, Dave Crocker <[e-mail]> wrote:
>>> 
>>> [...]
> 
>> PS.: If ABNF had cuts, I’d write
>>    EOL = [CR ^] LF
>> to get better errors on stray CRs.  Maybe not so important these days.
> 
> Sorry.  Not sure what you mean.  "cuts"? "^”?

To add some color to this point, “cuts” was discussed in the CBOR WG in the context of CDDL. It is a technique from Parsing Expression Grammars. Here is overview:

http://www.romanredz.se/papers/CSP2014.pdf

https://en.wikipedia.org/wiki/Parsing_expression_grammar
(see soft cut)

Basically it commits the parser at a particular point, so that it does not backtrack.

However, PEGs are ordered; ABNF is unordered. With ABNF (as presently constituted), all alternatives in a choice are considered simultaneously (order is not relevant). Even if you match one alternative, you’re supposed to try all other alternatives.

EOL = [CR ~CUT~] LF
EOL = CR ~CUT~ LF / LF

are equivalent: the point being that once a CR is encountered, LF is supposed to follow...and if LF does not follow, then the parser fails but throws an error that EOL did not match because there was no LF after the CR (because it’s more specific). However, cuts also takes the initial production CR out of the equation, so if you have:

EOL = CR ~CUT~ LF / LF / CR "foo"

the last alternative will never be reached, because it’s order-sensitive: the ~CUT~ will consume the first CR, so CR "foo" can never be matched. The equivalent technology in regular expressions is “atomic grouping”.

With a context-free grammar, it is better to think about all alternatives simultaneously.

Sean