Consider the grammar given by the production rules below whe

Consider the grammar given by the production rules below, where S is the start; if, then, else, :, =, <, x, y, z are terminal symbols; and epsilon is the empty string.

S -> if C then S | if C then S else S | I := I

C -> I = I | I < I

I -> x | y | z

Write a leftmost derivation of the sentence: if x < y then if y < z then x := z else x := y. Keep in mind that in a derivation only one variable at a time gets rewritten, and that applying a production rule of the form N -> epsilon to an occurance of the variable N amounts to removing that occurance.

Solution

Leftmost derivation
....................
A derivation S * y is called a leftmost derivation
and write
...>S *y

if y is obtained from S by a sequence of steps
at each of which apply a rule to the leftmost
nonterminal symbol.
S ....> SbS ....> abS ....> abScS ...> abacS ...> abaca