Question 14.4.1: Write a grammar whose nonterminals generate the sets Left(K,......
Write a grammar whose nonterminals generate the sets Left(K, t) for all nonterminals K of the given grammar.
Nonterminals are symbols (LeftK t) for any nonterminal K and any terminal t (and also for t = EOI). Its production rules are as follows: Let P be the initial nonterminal (the axiom) of the given grammar. Then our new grammar has the rule
〈LeftP EOI〉 → (the right-hand side is the empty string).
Each rule of the given grammar produces several rules of the new one. For example, if the given grammar has a rule
K → L u M N
(L, M, N are nonterminals, u is a terminal), then the new grammar has rules
\langle{{\mathrm{Left \ Lu}}}\to\langle{\mathrm{LeftK}}\,x\rangle
for all terminals x;
〈LeftM s〉 → (LeftK y〉 L u
for any s that may appear as a first character in a string derivable from N, and for any y, as well as for all pairs s = y, if the empty string is derivable from N); and
〈LeftN s〉 → 〈LeftK s〉 LuM
for any terminal s.