Question

a) Construct a phrase-structure grammar for the set of all fractions of the form a/b, where a is a signed integer in decimal notation and b is a positive integer.

b) What is the Backus–Naur form for this grammar?

c) Construct a derivation tree for +311/17 in this grammar.

Short answer

a) The productions are, in addition to the productions given above for a signed integer and a positive integer:

Sà< signed integer >< slash >< positive integer > < slash >à/.

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

\(\begin{array}{l}S{\bf{ }}:: = < {\rm{ signed integer}}{\bf{ }} > < {\bf{ }}{\rm{slash}}{\bf{ }} > < {\rm{ positive integer}}{\bf{ }} > {\bf{ }}\\ < {\bf{ }}{\rm{slash}}{\bf{ }} > :: = {\bf{ }}/{\bf{ }}\\ < {\bf{ }}{\rm{positive integer}}{\bf{ }} > :: = < {\bf{ }}{\rm{positive digit}}{\bf{ }} > < {\rm{ other digits}} > {\bf{ }}\\ < {\rm{other digits}}{\bf{ }} > :{\bf{ }} = < {\bf{ }}{\rm{integer}}{\bf{ }} > |\lambda {\bf{ }}\\ < {\rm{signed integer}}{\bf{ }} > :: = < {\bf{ }}{\rm{sign}}{\bf{ }} > < {\bf{ }}{\rm{integer}}{\bf{ }} > {\bf{ }}\\ < {\rm{ sign}}{\bf{ }} > :: = - I + {\bf{ }}\\ < {\bf{ }}{\rm{int eger}}{\bf{ }} > :: = < {\bf{ }}{\rm{integer}}{\bf{ }} > < {\bf{ }}{\rm{digit}}{\bf{ }} > l < {\bf{ }}{\rm{digit}}{\bf{ }} > {\bf{ }}\\ < {\rm{digit}}{\bf{ }} > :: = < {\bf{ }}{\rm{positive digit}}{\bf{ }} > |0{\bf{ }}\\ < {\bf{ }}{\rm{positive digit}}{\bf{ }} > :: = 0|1|2|3|4|5|6|7|8|9{\rm{ }}\end{array}\)

c) The derivation tree for +311/17 is,

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's production is one non-terminal symbol.

It 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,

It use the symbol:: =

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

The phrase structure grammar expresses fractions of the form a/b, where a is a signed decimal integer and a positive decimal integer.

(a)Start by defining the grammar for a signed integer and a positive integer.

A positive digit is defined as:

\(\begin{array}{c} < {\rm{positive digit}} > \, \to 1\\ < {\rm{positive digit}} > \, \to 2\\ < {\rm{positive digit}} > \, \to 3\\ < {\rm{positive digit}} > \, \to 4\\ < {\rm{positive digit}} > \, \to 5\\ < {\rm{positive digit}} > \, \to 6\\ < {\rm{positive digit}} > \, \to 7\\ < {\rm{positive digit}} > \, \to 8\\ < {\rm{positive digit}} > \, \to 9\end{array}\)

Adding a production for the digit 0 will give the productions for a digit:

<digit > \(\to\) < positive digit >

<digit > \(\to\) 0

An integer is a sequence of digits, so the productions for an integer will be:

< integer > \(\to\) < integer >< digit >

< integer > \(\to\) < digit >

A signed integer can be produced from an integer with the following productions:

<signed integer> \(\to\) <sign><integer>

<sign> \(\to\) -

<sign> \(\to\) +

While for a positive integer, the productions just require adding a few productions to the productions for an integer, that is:

<positive integer> \(\to\) < positive digit >< other digits >

<other digits> \(\to\) < integer >

<other digits > \(\to\) \(\lambda \)

Using the productions for an integer and a positive integer, the phrase structure grammar \(G{\bf{ }} = {\bf{ }}\left( {V,{\bf{ }}T,{\bf{ }}S,{\bf{ }}P} \right)\) for a / b will be:

\(V{\bf{ }} = {\bf{ }}\left\{ {0,1,2,3,4,5,6,7,8,9,{\bf{ }} + ,{\bf{ }} - ,{\bf{ }}/,{\bf{ }}{\rm{sign, digit, positive digit, integer, signed integer, positive integer, slash}},{\bf{ }}S} \right\}\)

\(T = {\bf{ }}\left\{ {0,1,2,3,4,5,6,7,8,9,{\bf{ }} + ,{\bf{ }} - } \right\}\)

Hence, the productions are, in addition to the productions given above for a signed integer and a positive integer:

S \(\to\) < signed integer >< slash >< positive integer > < slash > \(\to\) /.

Backus-Naur form of productions of the above grammar.

(b)The productions for the grammar created for part (a), all have a single non-terminal on the left-hand side.

Thus, this grammar is type 2 grammar.

The grammar is converted to the Backus-Naur form by combining the productions which have the same non-terminal on the left-hand side into a single product; and by replacing " with:: =”

This gives the following productions.

\(\begin{array}{l}S{\bf{ }}:: = < {\bf{ }}{\rm{signed integer}}{\bf{ }} > < {\bf{ }}{\rm{slash}}{\bf{ }} > < {\bf{ }}{\rm{positive integer}}{\bf{ }} > {\bf{ }}\\ < {\bf{ }}{\rm{slash}}{\bf{ }} > :: = {\bf{ }}/{\bf{ }}\\ < {\bf{ }}{\rm{positive integer}}{\bf{ }} > :: = < {\bf{ }}{\rm{positive digit}}{\bf{ }} > < {\bf{ }}{\rm{other digits}} > {\bf{ }}\\ < {\rm{other digits}}{\bf{ }} > :{\bf{ }} = < {\bf{ }}{\rm{integer}}{\bf{ }} > |\lambda {\bf{ }}\\ < {\rm{signed integer}}{\bf{ }} > :: = < {\bf{ }}{\rm{sign}}{\bf{ }} > < {\rm{ integer}}{\bf{ }} > {\bf{ }}\\ < {\bf{ }}{\rm{sign}}{\bf{ }} > :: = - I + {\bf{ }}\\ < {\bf{ }}{\rm{int eger}}{\bf{ }} > :: = < {\bf{ }}{\rm{integer}}{\bf{ }} > < {\bf{ }}{\rm{digit}}{\bf{ }} > l < {\bf{ }}{\rm{digit}}{\bf{ }} > {\bf{ }}\\ < {\rm{digit}}{\bf{ }} > :: = < {\bf{ }}{\rm{positive digit}}{\bf{ }} > |0{\bf{ }}\\ < {\rm{ positive digit}}{\bf{ }} > :: = 0|1|2|3|4|5|6|7|8|9{\rm{ }}\end{array}\)

Hence, the above productions is The Backus–Naur of productions form of the grammar G.

To get the derivation tree for +311/7 first we do a top-down derivation for it, which is:

(c)Now, the deviation is

\(\begin{array}{c}S{\bf{ }} = > < {\bf{ }}{\rm{signed integer}}{\bf{ }} > < {\bf{ }}{\rm{slash}}{\bf{ }} > < {\bf{ }}{\rm{positive integer}}{\bf{ }} > {\bf{ }}\\ = > < {\bf{ }}{\rm{sign}}{\bf{ }} > < {\bf{ }}{\rm{integer}}{\bf{ }} > < {\bf{ }}{\rm{slash}}{\bf{ }} > < {\bf{ }}{\rm{positive integer}}{\bf{ }} > {\bf{ }}\\ = > {\bf{ }} + {\bf{ }} < {\rm{integer}}{\bf{ }} > < {\bf{ }}{\rm{slash}}{\bf{ }} > < {\bf{ }}{\rm{positive}}\,\,{\rm{integer}} > {\bf{ }}\\ = > {\bf{ }} + {\bf{ }} < {\bf{ }}{\rm{integer}}{\bf{ }} > < {\bf{ }}{\rm{digit}}{\bf{ }} > < {\bf{ }}{\rm{slash}}{\bf{ }} > < {\bf{ }}{\rm{positive integer}}{\bf{ }} > \\ = > {\bf{ }} + {\bf{ }} < {\rm{integer}}{\bf{ }} > {\bf{ }}|{\bf{ }} < {\bf{ }}{\rm{slash}}{\bf{ }} > < {\bf{ }}{\rm{positiveinteger}} > {\bf{ }}\\ = > {\bf{ }} + {\bf{ }} < {\bf{ }}{\rm{integer}}{\bf{ }} > < {\bf{ }}{\rm{digit}}{\bf{ }} > {\bf{ }}||{\bf{ }} < {\bf{ }}{\rm{slash}}{\bf{ }} > < {\bf{ }}{\rm{positive integer}}{\bf{ }} > {\bf{ }}\\ = > {\bf{ }} + {\bf{ }} < {\bf{ }}{\rm{integer}}{\bf{ }} > {\bf{ }}||{\bf{ }} < {\bf{ }}{\rm{slash}}{\bf{ }} > < {\bf{ }}{\rm{positive}}\,\,{\rm{integer}} > {\bf{ }}\\ = > {\bf{ }} + {\bf{ }} < {\bf{ }}{\rm{digit}}{\bf{ }} > {\bf{ }}||{\bf{ }} < {\bf{ }}{\rm{slash}}{\bf{ }} > < {\bf{ }}{\rm{positive}}\,\,{\rm{integer}}{\bf{ }} > \\ = > {\bf{ }} + 311{\bf{ }} < {\bf{ }}{\rm{slash}}{\bf{ }} > < {\bf{ }}{\rm{positive integer}}{\bf{ }} > {\bf{ }}\\ = > {\bf{ }} + 311/{\bf{ }} < {\bf{ }}{\rm{positive}}\,\,{\rm{integer}} > {\bf{ }}\\ = > {\bf{ }} + 311/{\bf{ }} < {\bf{ }}{\rm{positive digit}}{\bf{ }} > < {\bf{ }}{\rm{other digits}}{\bf{ }} > {\bf{ }}\\ = > {\bf{ }} + 311/{\bf{ }}7{\bf{ }} < {\bf{ }}{\rm{other digits}}{\bf{ }} > \\ = > {\bf{ }} + 311/{\bf{ }}7\lambda {\bf{ }}\\ = > + 311/7{\bf{ }}\end{array}\)

Let’s construct a derivation tree for +311/17 in the above grammar is.

Hence, the above derivation tree for +311/17.