Question

Let $\mathit{G}\mathbf{=}\mathbf{(}\mathit{V}\mathbf{,}\mathit{\Sigma }\mathbf{,}\mathit{R}\mathbf{,}\mathbf{⟨}\mathbf{S}\mathbf{T}\mathbf{M}\mathbf{T}\mathbf{⟩}\mathbf{)}$be the following grammar.

$\begin{array}{c}\mathbf{⟨}\mathbf{S}\mathbf{T}\mathbf{M}\mathbf{T}\mathbf{⟩}\mathbf{\to }\mathbf{⟨}\mathbf{A}\mathbf{S}\mathbf{S}\mathbf{I}\mathbf{G}\mathbf{N}\mathbf{⟩}\mathbf{\left|}\mathbf{⟨}\mathbf{I}\mathbf{F}\mathbf{-}\mathbf{T}\mathbf{H}\mathbf{E}\mathbf{N}\mathbf{⟩}\mathbf{\right|}\mathbf{⟨}\mathbf{I}\mathbf{F}\mathbf{-}\mathbf{T}\mathbf{H}\mathbf{E}\mathbf{N}\mathbf{-}\mathbf{E}\mathbf{L}\mathbf{S}\mathbf{E}\mathbf{⟩}\\ \mathbf{⟨}\mathbf{I}\mathbf{F}\mathbf{-}\mathbf{T}\mathbf{H}\mathbf{E}\mathbf{N}\mathbf{⟩}\mathbf{\to }\mathbf{i}\mathbf{f}\mathbf{c}\mathbf{o}\mathbf{n}\mathbf{d}\mathbf{i}\mathbf{t}\mathbf{i}\mathbf{o}\mathbf{n}\mathbf{t}\mathbf{h}\mathbf{e}\mathbf{n}\mathbf{⟨}\mathbf{S}\mathbf{T}\mathbf{M}\mathbf{T}\mathbf{⟩}\\ \mathbf{⟨}\mathbf{I}\mathbf{F}\mathbf{-}\mathbf{T}\mathbf{H}\mathbf{E}\mathbf{N}\mathbf{-}\mathbf{E}\mathbf{L}\mathbf{S}\mathbf{E}\mathbf{⟩}\mathbf{\to }\mathbf{i}\mathbf{f}\mathbf{c}\mathbf{o}\mathbf{n}\mathbf{d}\mathbf{i}\mathbf{t}\mathbf{i}\mathbf{o}\mathbf{n}\mathbf{t}\mathbf{h}\mathbf{e}\mathbf{n}\mathbf{⟨}\mathbf{S}\mathbf{T}\mathbf{M}\mathbf{T}\mathbf{⟩}\mathbf{e}\mathbf{l}\mathbf{s}\mathbf{e}\mathbf{⟨}\mathbf{S}\mathbf{T}\mathbf{M}\mathbf{T}\mathbf{⟩}\\ \mathbf{⟨}\mathbf{A}\mathbf{S}\mathbf{S}\mathbf{I}\mathbf{G}\mathbf{N}\mathbf{⟩}\mathbf{\to }\mathbf{a}\mathbf{:}\mathbf{=}\mathbf{1}\end{array}$

$\begin{array}{c}\mathbf{\Sigma }\mathbf{=}\mathbf{\{}\mathbf{i}\mathbf{f}\mathbf{,}\mathbf{c}\mathbf{o}\mathbf{n}\mathbf{d}\mathbf{i}\mathbf{t}\mathbf{i}\mathbf{o}\mathbf{n}\mathbf{,}\mathbf{t}\mathbf{h}\mathbf{e}\mathbf{n}\mathbf{,}\mathbf{e}\mathbf{l}\mathbf{s}\mathbf{e}\mathbf{,}\mathbf{a}\mathbf{:}\mathbf{=}\mathbf{1}\mathbf{\}}\\ \mathbf{V}\mathbf{=}\mathbf{\{}\mathbf{⟨}\mathbf{S}\mathbf{T}\mathbf{M}\mathbf{T}\mathbf{⟩}\mathbf{,}\mathbf{⟨}\mathbf{I}\mathbf{F}\mathbf{-}\mathbf{T}\mathbf{H}\mathbf{E}\mathbf{N}\mathbf{⟩}\mathbf{,}\mathbf{⟨}\mathbf{I}\mathbf{F}\mathbf{-}\mathbf{T}\mathbf{H}\mathbf{E}\mathbf{N}\mathbf{-}\mathbf{E}\mathbf{L}\mathbf{S}\mathbf{E}\mathbf{⟩}\mathbf{,}\mathbf{⟨}\mathbf{A}\mathbf{S}\mathbf{S}\mathbf{I}\mathbf{G}\mathbf{N}\mathbf{⟩}\mathbf{\}}\end{array}$

G is a natural-looking grammar for a fragment of a programming language, but G is ambiguous.

a. Show that G is ambiguous.

b. Give a new unambiguous grammar for the same language

Short answer

a) The grammar is ambiguous.

b) A new unambiguous grammar for the same language is given below.

Step-by-step solution

Define ambiguous and unambiguous languages

The unambiguous CFGs context free grammar is a context free grammar by which only one parse tree or only one derivation tree is possible.

It means that for all string of a language there exist more than one left most derivation or more than one right most derivation or more than one parse tree is called ambiguous grammar.

Show that G is ambiguous

For all string of a language there exist more than one left most derivation or more than one right most derivation or more than one parse tree is called ambiguous grammar.

Here the proof by driving the sentence: if condition then if condition then

$a:=1elsea:=1$

Using two different leftmost derivation, as in the following:

First One: STMT => IF-THEN-ELSE =>

if condition then STMT else STMT => if condition then IF-THEN else STMT => if condition then if condition then STMT else STMT => if condition then if condition then ASSIGN else STMT => if condition then if condition then else STMT => if condition then if condition then else ASSIGN => if condition then if condition then .

Second One: STMT => IF-THEN =>

if condition then STMT => if condition then IF-THEN-ELSE => if condition then if condition then STMT else STMT => if condition then if condition then ASSIGN else STMT => if condition then if condition then else STMT => if condition then if condition then

else ASSIGN => if condition then if condition then $a:=1$else$a:=1$

A new unambiguous grammar.

(b)

The new unambiguous grammar is given below:

$\begin{array}{l}⟨STMT⟩\to ⟨ASSIGN⟩|⟨IF-THEN-ELSE⟩\\ ⟨IF-THEN-ELSE⟩\to ifconditionthenT⟨elsenSTMT⟩|T\\ T\to ⟨IF-THEN⟩⟨IF-THEN⟩\to ifconditionthen⟨STMT⟩\\ ⟨ASSIGN⟩\to a:=1\end{array}$