Question

Give production rules in extended Backus–Naur form for identifiers in the C programming language (see Exercise 33).

Short answer

The production rules in extended Backus–Naur form is,

\(\begin{array}{c}\left\langle {{\rm{Identifiers}}} \right\rangle {\rm{:: = }}\left\langle {{\rm{Start}}} \right\rangle \left\langle {{\rm{Lowercase letters}}} \right\rangle {\rm{ + }}\left\langle {{\rm{Uppercase letters}}} \right\rangle \\{\rm{ + }}\left\langle {{\rm{Underscore}}} \right\rangle {\rm{ + }}\left\langle {{\rm{Digits}}} \right\rangle {\rm{ + }}\\\left\langle {{\rm{Start}}} \right\rangle {\rm{:: = }}\left\langle {{\rm{Letter}}} \right\rangle {\rm{|\_ }}\\\left\langle {{\rm{Letter}}} \right\rangle {\rm{:: = }}\left\langle {{\rm{Uppercase letters}}} \right\rangle {\rm{|}}\left\langle {{\rm{Lowercase letters}}} \right\rangle \\\left\langle {{\rm{Underscore}}} \right\rangle {\rm{:: = \_}}\\\left\langle {{\rm{Digits}}} \right\rangle {\rm{:: = 0|1|2|}}...{\rm{|9 }}\\\left\langle {{\rm{Lowercase letters}}} \right\rangle {\rm{:: = a|b|c|}}...{\rm{|z }}\\\left\langle {{\rm{Uppercase letters}}} \right\rangle {\rm{:: = A|B|C|}}...{\rm{|Z}}\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 separately, we can merge all those with the same non terminal symbol on the left-hand side into one statement instead 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 now includes the following extensions:

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

The symbol or group of symbols enclosed in parenthesis to the left of the sign "?" may appear zero or once.

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

Step 3: The production rules in extended Backus-Naur form for identifiers in the C programming language can be given as:

\(\begin{array}{c}\left\langle {{\rm{Identifiers}}} \right\rangle {\rm{:: = }}\left\langle {{\rm{Start}}} \right\rangle \left\langle {{\rm{Lowercase letters}}} \right\rangle {\rm{ + }}\left\langle {{\rm{Uppercase letters}}} \right\rangle \\{\rm{ + }}\left\langle {{\rm{Underscore}}} \right\rangle {\rm{ + }}\left\langle {{\rm{Digits}}} \right\rangle {\rm{ + }}\\\left\langle {{\rm{Start}}} \right\rangle {\rm{:: = }}\left\langle {{\rm{Letter}}} \right\rangle {\rm{|\_ }}\\\left\langle {{\rm{Letter}}} \right\rangle {\rm{:: = }}\left\langle {{\rm{Uppercase letters}}} \right\rangle {\rm{|}}\left\langle {{\rm{Lowercase letters}}} \right\rangle \\\left\langle {{\rm{Underscore}}} \right\rangle {\rm{:: = \_}}\\\left\langle {{\rm{Digits}}} \right\rangle {\rm{:: = 0|1|2|}}...{\rm{|9 }}\\\left\langle {{\rm{Lowercase letters}}} \right\rangle {\rm{:: = a|b|c|}}...{\rm{|z }}\\\left\langle {{\rm{Uppercase letters}}} \right\rangle {\rm{:: = A|B|C|}}...{\rm{|Z}}\end{array}\)

First production shows that the Identifiers starts with the symbol Start and it is followed by one or more Lowercase letters, Uppercase letters, Underscores and Digits.

Second production defines symbol Start.

Third, fourth, fifth, sixth and seventh productions define Letter, Underscore, Digits, Lowercase letters and Upper-case letters respectively.

For example, identifier c_highest can be generated using production rules:

\(\begin{array}{c}\left\langle {{\rm{Identifiers}}} \right\rangle {\rm{:: = }}\left\langle {{\rm{Start}}} \right\rangle \left\langle {{\rm{Lowercase letters}}} \right\rangle {\rm{ + }}\left\langle {{\rm{Uppercase letters}}} \right\rangle \\{\rm{ + }}\left\langle {{\rm{Underscore}}} \right\rangle {\rm{ + }}\left\langle {{\rm{Digits}}} \right\rangle {\rm{ + }}\\\left\langle {{\rm{Start}}} \right\rangle {\rm{:: = }}\left\langle {{\rm{Letter}}} \right\rangle {\rm{|\_ }}\end{array}\)

This production rule gives

\({\rm{c\_}}\left\langle {{\rm{Lowercase letters}}} \right\rangle {\rm{ + }}\left\langle {{\rm{Uppercase letters}}} \right\rangle {\rm{ + }}\left\langle {{\rm{Underscore}}} \right\rangle {\rm{ + }}\left\langle {{\rm{Digits}}} \right\rangle \)

Using production rules

\(\left\langle {{\rm{Lowercase letters}}} \right\rangle {\rm{:: = a|b|c|}}...{\rm{|z}}\)

c_highest

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