Question

Give production rules in extended Backus–Naur form that generate all decimal numerals consisting of an optional sign, a nonnegative integer, and a decimal fraction that is either the empty string or a decimal point followed by an optional positive integer optionally preceded by some number of zeros.

Short answer

The production rules in extended Backus–Naur form is,

\(\begin{array}{c}{\bf{numeral :: = sign? nonzerodigit digit*decimal? I sign? 0 decimal?}}\\{\bf{sign :: = + I - }}\\{\bf{nonzerodigit :: = 1 |2 | }}...{\bf{|9}}\\{\bf{digit :: = 0| nonzerodigit}}\\{\bf{decimal :: = digit*}}\end{array}\)

Step-by-step solution

About Backus-Nour form

The Backus-Naur form is a notation for specifying a type 2 grammar.

Productions in a type 2 grammar have a single non-terminal symbol on the left.

Rather of listing all the productions individually, we can merge all those with the same non terminal symbol on the left-hand side into one statement rather of using the symbolàin a production,

The symbol:: =

All non-terminal symbols are enclosed in brackets (>), and all productions' right-hand sides are listed in the same statement, separated by bars.

The Backus-Naur form's additions include the following:

a) "+": denotes that the symbol to the left of it may appear once or more.

b) A symbol or set of symbols denoted by the question mark ("?) to the left of it may appear 0 or 1 times.

c) "*": denotes that the sign to the left of it may appear once or more.

Assume that leading 0's are not allowed in the whole number part

Because the problem explicitly mentioned them only for the decimal part. Our rules should allow the optional sign using the question mark character, the integer part consisting of one or more digits, which does not start with a 0 unless 0 is the integer part of the integer, so the decimal part or not.

Note that the decimal part has a decimal point followed by 0 or more digits.

\(\begin{array}{c}{\bf{numeral :: = sign? nonzerodigit digit*decimal? I sign? 0 decimal?}}\\{\bf{sign :: = + I - }}\\{\bf{nonzerodigit :: = 1 |2 | }}...{\bf{|9}}\\{\bf{digit :: = 0| nonzerodigit}}\\{\bf{decimal :: = digit*}}\end{array}\)

Hence, the above production rules in extended Backus–Naur form.