RFC Errata


Errata Search

 
Source of RFC  
Summary Table Full Records

RFC 5234, "Augmented BNF for Syntax Specifications: ABNF", January 2008

Source of RFC: IETF - NON WORKING GROUP
Area Assignment: app

Errata ID: 1423
Status: Rejected
Type: Technical
Publication Format(s) : TEXT

Reported By: David J. Rutkin
Date Reported: 2008-05-13
Rejected by: Alexey Melnikov
Date Rejected: 2010-09-03

Section 4. says:

repeat         =  1*DIGIT / (*DIGIT "*" *DIGIT)

It should say:

repeat         =  *DIGIT ["*" *DIGIT]

Notes:

In section 4. ABNF Definition of ABNF, on Page 10, the definition of <repeat> appears to be ambiguous.

After many weeks of study of RFC 5234 I am unable to discern which alternation to choose for <repeat> for the following string.

21*ARULENAME

Both alternatives are a valid solution but I was not able to determine from the RFC which one should be chosen. By my way of thinking, the first one encountered should be chosen but when done, the "*" is left and will cause a parsing error. Conversely I could have performed a look ahead check in my parsor, but that would produce a less efficient parser, forcing all alternatives to always be processed. In either case, the rule is ambiguous and, in my opinion, requires further definition.

My recommendation would be to change it to

repeat = *DIGIT ["*" *DIGIT]

This solution does not introduce any ambiguity and does not break any components of the definition of ABNF.

I realize that the forced presence of a digit on the <repeat> without the * is no longer present, but it was not necessary since the only use of <repeat> is by <repetition> and its presence is optional.

--VERIFIER NOTES--

The following is the text of an analysis of Erratum entry <http://www.rfc-editor.org/errata_search.php?rfc=5234&eid=1423>, made by Paul Overell:


> Section: 4.
>
> Original Text
> -------------
> repeat = 1*DIGIT / (*DIGIT "*" *DIGIT)
>

I can see nothing wrong with this, there is no ambiguity. To be ambiguous it would have to be able to generate a particular string in more than one way.

A <repeat> without a "*" can only be generated by the first alterative. A <repeat> with a "*" can only be generated by the second alternative.


> Corrected Text
> --------------
> repeat = *DIGIT ["*" *DIGIT]

This changes the syntax of <repeat> as it allow the empty string.


> Notes
> -----
> In section 4. ABNF Definition of ABNF, on Page 10, the definition of <repeat> appears to be ambiguous.
>
> After many weeks of study of RFC 5234 I am unable to discern which alternation to choose for <repeat> for the following string.
>
> 21*ARULENAME

This clearly matches the second alternative (*DIGIT "*" *DIGIT) and therefor is an instance of a <repeat>. This string can only be generated using the second alternative.


> Both alternatives are a valid solution but I was not able to determine from the RFC which one should be chosen. By my way of thinking, the first one encountered should be chosen but when done, the "*" is left and will cause a parsing error.

The first cannot be chosen precisely because the "*" is left and causes a parsing error.

> Conversely I could have performed a look ahead check in my parsor, but that would produce a less efficient parser, forcing all alternatives to always be processed.

The grammar given for ABNF is not, and does not claim to be, LL(0). I expect the ABNF grammar could be recast as LL(0) but there is no need, it was written for clarity.

I can't see the relevance of parser efficiency here.

> In either case, the rule is ambiguous and, in my opinion, requires further definition.

As discussed above, there is no ambiguity.


> My recommendation would be to change it to

> repeat = *DIGIT ["*" *DIGIT]
>
> This solution does not introduce any ambiguity and does not break any components of the definition of ABNF.

It is not equivalent to the original in that it allows the empty string.


> I realize that the forced presence of a digit on the <repeat> without the * is no longer present, but it was not necessary since the only use of <repeat> is by <repetition> and its presence is optional.

The proposed change to <repeat> breaks the definition of <repetition> as it then becomes ambiguous.

Consider the string "foo". With the proposed change to <repeat> it can be parsed as a <repetition> in two ways: <repeat> <element> or as <element>, the first with the option taken, the second with the option not taken. Two parse trees for the same string. To fix this ambiguity the definition of <repetition> would have to be changed to

repetition = repeat element


I recommend that this errata is rejected.

There is no ambiguity to fix, the proposed change is unnecessary, and would require an additional change to the definition of <repetition>.

Report New Errata