Question

Give production rule in Backus-Naur form for an identifier if it can consist of

a. One or more lower case letters.

b. At least three but no more than six lowercase letter

c. One to six uppercase or lowercase letters beginning with an uppercase letter.

d. A lowercase letter, followed by a digit or an underscore, followed by three or four alphanumeric characters (lower or uppercase letters and digits.)

Short answer

a) \(\begin{array}{l}\left\langle {identifier} \right\rangle :: = = \left\langle {identifier} \right\rangle \left\langle {letter} \right\rangle \left\langle {letter} \right\rangle \\\left\langle {letter} \right\rangle :: = = a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z\end{array}\)

b) \(\begin{array}{l}\left\langle {identifier} \right\rangle :: = = \left\langle {letter} \right\rangle \left\langle {letter} \right\rangle \left\langle {letter} \right\rangle |\left\langle {letter} \right\rangle \left\langle {letter} \right\rangle \left\langle {letter} \right\rangle \left\langle {letter} \right\rangle \\\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,|\left\langle {letter} \right\rangle \left\langle {letter} \right\rangle \left\langle {letter} \right\rangle \left\langle {letter} \right\rangle \left\langle {letter} \right\rangle \\\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,|\left\langle {letter} \right\rangle \left\langle {letter} \right\rangle \left\langle {letter} \right\rangle \left\langle {letter} \right\rangle \left\langle {letter} \right\rangle \left\langle {letter} \right\rangle \\\left\langle {letter} \right\rangle :: = = a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z\end{array}\)

c) \(\begin{array}{l}\left\langle {identifier} \right\rangle :: = = \left\langle {ucletter} \right\rangle |\left\langle {ucletter} \right\rangle \left\langle {lcletter} \right\rangle |\left\langle {ucletter} \right\rangle \left\langle {lcletter} \right\rangle \left\langle {lcletter} \right\rangle \\\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,|\left\langle {ucletter} \right\rangle \left\langle {lcletter} \right\rangle \left\langle {lcletter} \right\rangle \left\langle {lcletter} \right\rangle \\\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,|\left\langle {ucletter} \right\rangle \left\langle {lcletter} \right\rangle \left\langle {lcletter} \right\rangle \left\langle {lcletter} \right\rangle \left\langle {lcletter} \right\rangle \\\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,|\left\langle {ucletter} \right\rangle \left\langle {lcletter} \right\rangle \left\langle {lcletter} \right\rangle \left\langle {lcletter} \right\rangle \left\langle {lcletter} \right\rangle \left\langle {lcletter} \right\rangle \\\left\langle {letter} \right\rangle :: = = \left\langle {lcletter} \right\rangle |\left\langle {ucletter} \right\rangle \\\left\langle {lcletter} \right\rangle :: = = a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z\\\left\langle {ucletter} \right\rangle :: = = A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|\\\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,W|X|Y|Z\end{array}\)

d) \(\begin{array}{l}\left\langle {identifier} \right\rangle :: = = \left\langle {lcletter} \right\rangle \left\langle {digitorus} \right\rangle \left\langle {alphanumeric} \right\rangle \left\langle {alphanumeric} \right\rangle \left\langle {alphanumeric} \right\rangle |\\\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,|\left\langle {lcletter} \right\rangle \left\langle {digitorus} \right\rangle \left\langle {alphanumeric} \right\rangle \left\langle {alphanumeric} \right\rangle \left\langle {alphanumeric} \right\rangle \\\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\left\langle {alphanumeric} \right\rangle \\\left\langle {digitorus} \right\rangle :: = = \left\langle {digit} \right\rangle |\_\\\left\langle {alphanumeric} \right\rangle :: = = \left\langle {digit} \right\rangle |\left\langle {lcletter} \right\rangle |\left\langle {ucletter} \right\rangle \\\left\langle {digit} \right\rangle :: = = 0|1|2|3|4|5|6|7|8|9\\\left\langle {lcletter} \right\rangle :: = = a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z\\\left\langle {ucletter} \right\rangle :: = = A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|\\\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,W|X|Y|Z\end{array}\)

Step-by-step solution

Backus-Naur form

Many programming languages, including Java, define their grammatical rules using the Backus-Naur form. A type 2 grammar has a single nonterminal symbol on the left side of each production. it can group all the productions that share the same nonterminal symbol on the left side into a single statement rather than listing each one separately.

Giving Production rule in Backus-Naur form for an identifier if it can consist of one or more lower case letters.

(a) The identifier must consist of at least one letter, therefore it can either be a single letter or an identifier that is followed by a single letter.

Now, the lowercase letters are

\(a,\,b,\,c,\,d,\,e,\,f,\,g,\,h,\,i,\,j,\,k,\,l,\,m,\,n,\,o,\,p,\,q,\,r,\,s,\,t,\,u,\,v,\,w,\,x,\,y,\,z\).

Now, \(|\) will be used to represent “or”.

Now, the Backus-Nour form is given by,

\(\begin{array}{l}\left\langle {identifier} \right\rangle :: = = \left\langle {identifier} \right\rangle \left\langle {letter} \right\rangle \left\langle {letter} \right\rangle \\\left\langle {letter} \right\rangle :: = = a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z\end{array}\)

Giving Production rule in Backus-Naur form for an identifier if it can consist of at least three but no more than six lowercase letters

(b) It is given that it can consists of at least three but no more than six lowercase letters.

So, the identifier can only contain three, four, five or six lowercase letters.

Now, the lowercase letters are

\(a,\,b,\,c,\,d,\,e,\,f,\,g,\,h,\,i,\,j,\,k,\,l,\,m,\,n,\,o,\,p,\,q,\,r,\,s,\,t,\,u,\,v,\,w,\,x,\,y,\,z\).

Now, \(|\) will be used to represent “or”.

Now, the Backus-Nour form is given by,

\(\begin{array}{l}\left\langle {identifier} \right\rangle :: = = \left\langle {letter} \right\rangle \left\langle {letter} \right\rangle \left\langle {letter} \right\rangle |\left\langle {letter} \right\rangle \left\langle {letter} \right\rangle \left\langle {letter} \right\rangle \left\langle {letter} \right\rangle \\\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,|\left\langle {letter} \right\rangle \left\langle {letter} \right\rangle \left\langle {letter} \right\rangle \left\langle {letter} \right\rangle \left\langle {letter} \right\rangle \\\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,|\left\langle {letter} \right\rangle \left\langle {letter} \right\rangle \left\langle {letter} \right\rangle \left\langle {letter} \right\rangle \left\langle {letter} \right\rangle \left\langle {letter} \right\rangle \\\left\langle {letter} \right\rangle :: = = a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z\end{array}\)

Giving Production rule in Backus-Naur form for an identifier if it can consist of one to six uppercase or lowercase letters beginning with an uppercase letter.

(c) It is given that it can consists of one to six uppercase or lowercase letters beginning with an uppercase letter.

So, the identifier can only contain one, two, three, four, five or six letters.

The first letter has to be uppercase, while other letter can be lowercase or uppercase letter.

Now, the lowercase letters are

\(a,\,b,\,c,\,d,\,e,\,f,\,g,\,h,\,i,\,j,\,k,\,l,\,m,\,n,\,o,\,p,\,q,\,r,\,s,\,t,\,u,\,v,\,w,\,x,\,y,\,z\).

The uppercase letters are

\(A,\,B,\,C,\,D,\,E,\,F,\,G,\,H,\,I\,,J,\,K,\,L,\,M,\,N,\,O,\,P,\,Q,\,R,\,S,\,T,\,U,\,V,\,W,\,X,\,Y,\,Z\)

Now, \(|\) will be used to represent “or”. \(\left\langle {ucletter} \right\rangle \) will be used to represent Uppercase letter. \(\left\langle {lcletter} \right\rangle \) will be used to represent Uppercase letter.

Now, the Backus-Nour form is given by,

\(\begin{array}{l}\left\langle {identifier} \right\rangle :: = = \left\langle {ucletter} \right\rangle |\left\langle {ucletter} \right\rangle \left\langle {lcletter} \right\rangle |\left\langle {ucletter} \right\rangle \left\langle {lcletter} \right\rangle \left\langle {lcletter} \right\rangle \\\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,|\left\langle {ucletter} \right\rangle \left\langle {lcletter} \right\rangle \left\langle {lcletter} \right\rangle \left\langle {lcletter} \right\rangle \\\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,|\left\langle {ucletter} \right\rangle \left\langle {lcletter} \right\rangle \left\langle {lcletter} \right\rangle \left\langle {lcletter} \right\rangle \left\langle {lcletter} \right\rangle \\\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,|\left\langle {ucletter} \right\rangle \left\langle {lcletter} \right\rangle \left\langle {lcletter} \right\rangle \left\langle {lcletter} \right\rangle \left\langle {lcletter} \right\rangle \left\langle {lcletter} \right\rangle \\\left\langle {letter} \right\rangle :: = = \left\langle {lcletter} \right\rangle |\left\langle {ucletter} \right\rangle \\\left\langle {lcletter} \right\rangle :: = = a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z\\\left\langle {ucletter} \right\rangle :: = = A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|\\\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,W|X|Y|Z\end{array}\)

Giving Production rule in Backus-Naur form for an identifier if it can consist of a lowercase letter, followed by a digit or an underscore, followed by three or four alphanumeric characters (lower or uppercase letters and digits.)

(d) It is given that it can consists of a lowercase letter, followed by a digit or an underscore, followed by three or four alphanumeric characters.

The identifier contains a lowercase letter, then a digitorus, then three or four alphanumeric characters.

A digitorus is a digit or underscore _.

A digit, lowercase letter, or capital letter are examples of alphanumeric characters.

Now, the lowercase letters are

\(a,\,b,\,c,\,d,\,e,\,f,\,g,\,h,\,i,\,j,\,k,\,l,\,m,\,n,\,o,\,p,\,q,\,r,\,s,\,t,\,u,\,v,\,w,\,x,\,y,\,z\).

The digits are \(0,\,1,\,2,\,3,\,4,\,5,\,6,\,7,\,8,\,9\).

The uppercase letters are

\(A,\,B,\,C,\,D,\,E,\,F,\,G,\,H,\,I\,,J,\,K,\,L,\,M,\,N,\,O,\,P,\,Q,\,R,\,S,\,T,\,U,\,V,\,W,\,X,\,Y,\,Z\).

Now, \(|\) will be used to represent “or”. \(\left\langle {ucletter} \right\rangle \) will be used to represent Uppercase letter. \(\left\langle {lcletter} \right\rangle \) will be used to represent Uppercase letter.

Now, the Backus-Nour form is given by,

\(\begin{array}{l}\left\langle {identifier} \right\rangle :: = = \left\langle {lcletter} \right\rangle \left\langle {digitorus} \right\rangle \left\langle {alphanumeric} \right\rangle \left\langle {alphanumeric} \right\rangle \left\langle {alphanumeric} \right\rangle |\\\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,|\left\langle {lcletter} \right\rangle \left\langle {digitorus} \right\rangle \left\langle {alphanumeric} \right\rangle \left\langle {alphanumeric} \right\rangle \left\langle {alphanumeric} \right\rangle \\\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\left\langle {alphanumeric} \right\rangle \\\left\langle {digitorus} \right\rangle :: = = \left\langle {digit} \right\rangle |\_\\\left\langle {alphanumeric} \right\rangle :: = = \left\langle {digit} \right\rangle |\left\langle {lcletter} \right\rangle |\left\langle {ucletter} \right\rangle \\\left\langle {digit} \right\rangle :: = = 0|1|2|3|4|5|6|7|8|9\\\left\langle {lcletter} \right\rangle :: = = a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z\\\left\langle {ucletter} \right\rangle :: = = A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|\\\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,W|X|Y|Z\end{array}\)