1

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:

parse tree for 37

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:

enter image description here

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? – JETM May 13 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 at 11:28
  • 3
    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? – JETM May 13 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 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 at 13:03
2

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.