Question

construct a derivation tree for −109 using the grammar given in Example 15.

Short answer

The derivation tree of -1 0 9 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.

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

Using the symbol:: =

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

Using the grammar given in Example 15.

\(G{\bf{ }} = {\bf{ }}\left( {V,{\bf{ }}T,{\bf{ }}S,{\bf{ }}P} \right)\) is the phrase structure grammar described with

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

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

The initial symbol is a signed integer, and the outputs are

signed integeràsing integer,

sign \(\to\) +,

sign \(\to\) -,

integer \(\to\) digit,

integer \(\to\) digit integer,

digit \(\to\) 0,

digit \(\to\) 1,

…………

…………

digit \(\to\) 9.

Signed integer\(\to\)sign integer

\(\to\)sign (digit integer)

\(\to\)sign digit (digit integer)

\(\to\)sign digit digit digit

\(\to\)- digit digit digit

\(\to\)- 1 digit digit

\(\to\)- 1 0 digit

\(\to\)- 1 09

Let’s construct a derivation tree for −109.

Hence, the above derivation tree of -1 0 9.