11. Transformations of CFG

Expression is open or closed

$S \to S_0 | S_C$ $S _0 \to if (E)S | if (E) S_c else S_0$ $S_c\to S_s | if(E)S_c else S_c$

Transformation of CFG

$L(G_n) = L(G_2)$ Removal of useless pro...

$S\to aAB | b$ $A\to aA | a$ $B\to Bb$

$X:N$ .....

$B$ is non-productive $A$ is unreachable

Substitution

$A \to XBY$ $B \to C|D|\epsilon$

$A\to XCY | XDY | XY$

Eliminating left recursion

$A \to Aa|b$ $X$ is left-recursive, if $X =>* Xx$ $A\to bA'$ $A' -> aA'\epsilon$

$S\to A | B$ $A \to ABc | AAd | a | aa$

$B\to Bcc | b$

$A\to aA' | aaA'$ $A' \to BcA' | AdA' | \epsilon$ $B\to bB'$ $B' \to cc B' | \epsilon$

??

$A\to BaB$ $B\to Abb|Acb|\epsilon$ $A=> BaB => AbbaB$