Search code examples
grammarcontext-free-grammarbnf

BNF for a hexadecimal number

As a homework assignment I have to write a BNF definition for a hexadecimal number <hex>.

This is to be done using <digit> and <letter>, both of which are defined as follows:

<digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<letter> ::= A | B | C | D | E | F

The textbook answer is given as:

<hex> ::= <digit> | <letter> | <hex> <digit> | <hex> <letter>

I agree that this is a correct answer, but I would like to ask if it is also correct to give the answer as the following:

<hex> ::= <digit> | <letter> | <hex> <hex>
Solution

  • Nope, just look at the parse trees produced by textbook grammar vs. suggested grammar (code). Note: parse trees represent derivations.