Question

a) Construct a phrase-structure grammar that generates all signed decimal numbers, consisting of a sign, either + or −; a nonnegative integer; and a decimal fraction that is either the empty string or a decimal point followed by a positive integer, where initial zeros in an integer are allowed.

b) Give the Backus–Naur form of this grammar.

c) Construct a derivation tree for −31.4 in this grammar.

Short answer

a) A phrase-structure grammar that generates all signed.

\(\begin{array}{c}V = \left\{ {0,1,...,9, + , - ,...,sign,{\bf{ }}{\mathop{\rm int}} eger,{\bf{ }}positive{\bf{ }}{\mathop{\rm int}} eger,digit{\bf{ }},{\bf{ }}nonzero{\bf{ }}digit,{\bf{ }}S} \right\}\\T = \left\{ { + , - ,...,0,1,...,9} \right\}\\S{\bf{ }} = {\bf{ }}{\rm{starting symbol or production symbol}}{\bf{ }}\\S \to {\rm{sign integer}},{\bf{ }}\\{\rm{Sign}}{\bf{ }} \to + ,{\bf{ }}{\rm{sign}}{\bf{ }} \to - \\{\rm{integer}} \to {\bf{ }}{\rm{digit, integer}}{\bf{ }} \to {\bf{ }}{\rm{integer digit}}{\bf{ }}\\{\rm{digit}}{\bf{ }} \to i,i = {\bf{ }}0,1,2,\;...,9{\bf{ }}\\{\rm{positive integer}}{\bf{ }} \to {\bf{ }}{\rm{integer non zero digit}}{\bf{ }}\\{\rm{positive integer}}{\bf{ }} \to {\bf{ }}{\rm{non zero digit integer}}{\bf{ }}\\{\rm{positive integer}}{\bf{ }} \to {\bf{ }}{\rm{integer non zero digit integer}}{\bf{ }}\\{\rm{positive integer}}{\bf{ }} \to {\bf{ }}{\rm{non zero digit}}\\{\rm{non zero digit}}{\bf{ }}i,i{\bf{ }} = {\bf{ }}1,2,...,9\end{array}\)

b) The Backus–Naur form of the grammar G.

\(\begin{array}{c} < S > :: = < sign > < {\rm{integer}} > | < {\rm{sign}} > < {\rm{integer}} > < {\rm{positive integer}} > {\bf{ }}\\ < {\rm{sign}}{\bf{ }} > :: = + | - \\ < {\rm{integer}} > :: = < {\rm{digit}} > | < {\rm{integer}} > < {\rm{digit}} > {\bf{ }}\\ < {\rm{digit}} > :: = 0|1|2|3|4|5|6|7|8|9{\bf{ }}\\ < {\rm{positive integer}} > :: = < {\rm{integer}} > < {\rm{non zero digit}} > |\\ < {\rm{nonzero}}\,{\rm{digit}} > < {\rm{integer}} > |\\ < {\rm{integer}} > < {\rm{nonzero digit}} > < {\rm{integer}} > |\\ < {\rm{nonzero digit}} > {\bf{ }}\\ < nonzerodigit > :: = 0|1|2|3|4|5|6|7|8|9{\rm{ }}\end{array}\)

c) The derivation tree for -31.4.

Step-by-step solution

About Backus-Nour form.

A type-2 grammar is designated by the notation known as Backus-Naur form.

The left side of a type 2 grammar production is one non-terminal symbol.

I can merge all of the productions into a single statement using the same left non-terminal symbolàrather than listing each one separately in production,

Use the symbol:: =

Enclose all non-terminal symbols in brackets <>, and i list all right-hand sides of productions in the same statement, separating them by bars.

Let’s construct a phrase-structure grammar:

(a)The phrase structure grammar, \(G{\bf{ }} = {\bf{ }}\left( {V,{\bf{ }}T,{\bf{ }}S,{\bf{ }}P} \right)\), generates all signed decimal numbers, consisting of a sign, either + or -, a non-negative integer, and a decimal fraction, which is either the empty string or a decimal point followed by a positive integer, where the initial zeros in an integer are allowed, with initial zeros in the following format:

\(\begin{array}{c}V = \left\{ {0,1,...,9, + , - ,...,{\rm{sign, integer, positive integer,digit , nonzero digit}},{\bf{ }}S{\bf{ }}} \right\}\\T = \left\{ { + , - ,...,0,1,...,9} \right\}\\S{\bf{ }} = {\bf{ }}{\rm{starting symbol or production symbol}}{\bf{ }}\\S \to {\rm{sign integer}},\\{\rm{Sign}}{\bf{ }} \to + ,{\bf{ }}{\rm{sign}}{\bf{ }} \to - \\{\rm{integer}} \to {\bf{ }}{\rm{digit, integer}}{\bf{ }} \to {\bf{ }}{\rm{integer digit}}\\{\rm{digit}}{\bf{ }} \to i,i = {\bf{ }}0,1,2,\;...,9{\bf{ }}\\{\rm{positive integer}}{\bf{ }} \to {\bf{ }}{\rm{integer non zero digit}}\\{\rm{positive integer}}{\bf{ }} \to {\bf{ }}{\rm{non zero digit integer}}\\{\rm{positive integer}}{\bf{ }} \to {\bf{ }}{\rm{integer non zero digit integer}}\\{\rm{positive integer}}{\bf{ }} \to {\bf{ }}{\rm{non zero digit}}\\{\rm{non zero digit}}{\bf{ }}i,i{\bf{ }} = {\bf{ }}1,2,...,9\end{array}\)

Hence, A phrase-structure grammar that generates all signed.

Backus-Naur form of productions of the above grammar.

(b)Now, the Backus–Naur form of the grammar G is

\(\begin{array}{c} < S > :: = < {\rm{sign}} > < {\rm{integer}} > | < {\rm{sign}} > < {\rm{integer}} > < {\rm{positive integer}} > {\bf{ }}\\ < {\rm{sign}}{\bf{ }} > :: = + | - \\ < {\rm{integer}} > :: = < {\rm{digit}} > | < {\rm{integer}} > < {\rm{digit}} > {\bf{ }}\\ < {\rm{digit}} > :: = 0|1|2|3|4|5|6|7|8|9{\bf{ }}\\ < {\rm{positive integer}} > :: = < {\rm{integer}} > < {\rm{non zero digit}} > |{\bf{ }}\\ < {\rm{nonzero}}\,\,{\rm{digit}} > < {\rm{integer}} > |{\bf{ }}\\ < {\rm{integer}} > < {\rm{nonzero digit}} > < {\rm{integer}} > |{\bf{ }}\\ < {\rm{nonzero digit}} > {\bf{ }}\\ < {\rm{nonzero digit}} > :: = 0|1|2|3|4|5|6|7|8|9{\rm{ }}\end{array}\)

Hence, the Backus–Naur form of the grammar G.

Let’s construct a derivation tree for -31.4 in the above grammar

(c)

Hence, the above derivation tree for -31.4.