Question about Backus-NaurForm (BNF)

To write the grammar for Whole Numbers (0,1,2...) in BNF, we may write:

``````Number ::⇒ Digit MoreDigits
MoreDigits ::⇒
MoreDigits ::⇒ Number
Digit ::⇒ 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
``````

For a number like 37, the parse tree would be:

Now here is the part that confuses me. If we replaced the first rule `Number ::⇒ Digit MoreDigits` in the whole numbers grammar with: `Number ::⇒ MoreDigits Digit`, I would think that this would lead to a Circular definition. Instead it is said to lead to:

Why does the root `Number` have a combination order of `MoreDigits Digit`, while and the second `Number` have a combination order of `Digit MoreDigits`.

• What is this example from? – user214290 May 13 '19 at 11:20
• It's from 'Introduction to computing by David Evans' (computingbook.org), the specific exercise is at computingbook.org/exercises/chapter2.pdf Exercise 2.11 – Promise Tochi May 13 '19 at 11:28
• My amateur reading is that this is just a typo. If you assume the author meant to swap the children of the last `Number` node, does everything make sense? – user214290 May 13 '19 at 11:40
• I guess it does make sense now, if it's swapped. My initial thought is that it would lead to a circular definition that goes on and on even when it's swapped to the correct order, but that won't be the case. – Promise Tochi May 13 '19 at 12:08
• It would be worth looking for an errata online, as in the last 2 lines it should be MoreDigits Digits. Recursion termination is another matter, concerning successors and such. – Joop Eggen May 13 '19 at 13:03

If we replaced the first rule `Number ::⇒ Digit MoreDigits` in the whole numbers grammar with: `Number ::⇒ MoreDigits Digit`, I would think that this would lead to a Circular definition.

A grammar describing something that can repeat an indefinite number of times has to be circular. Circularity isn't bad in this context because the grammar isn't a program where something follows the path through it as if each reference to a nonterminal is a function call. Rather, the grammar is driven by the tokens in the input stream, which means the state machine that runs it is only going to traverse the path dictated by the tokens. Of course, if the input is an infinite stream of valid tokens, the parser will run forever and the effect is the same, but that really wasn't the intended use.

While repetitive, grammars are often easier to understand when repeating terms refer to themselves rather than to the terms that refer to them (not to mention that a non-forward-referencing grammar can be analyzed in a single pass):

``````MoreDigits ::= NOTHING | Digit MoreDigits
Number ::= Digit MoreDigits
``````

Changing the order of the terms as shown in the example has no effect on the language but, as you noticed, does change the parsed representation. In less-theoretical terms, this is important because the path to producing the `MoreDigits Digit` parse tree requires lookahead down the entire `Number` term where the opposite can happily consume it a token at a time.

Why does the root Number have a combination order of `MoreDigits Digit`, while and the second Number have a combination order of `Digit MoreDigits`.

As pointed out in the comments, it's a mistake in the diagram. There are no terms in that version of the grammar that would make that ordering possible.