Extended Grammar with a “Dummy Rule”
19/42
Gexpr1 = (N, T, P, E), where N = {E, F, T}, T = {i, +, *, (, )},
P = { 1: E ® E+T, 2: E ® T, 3: T ® T*F,
4: T ® F, 5: F ® (E),    6: F ® i        }
Definition: Let G = (N, T, P, S) be a CFG, S’ Ï N. Extended grammar for G is grammar
G’ = (N È {S’}, T, P È {S’ ® S}, S’).
Gist: Grammar with special “starting rule”
Example:
Why a dummy rule? When S’ ® S is used and the input token is endmarker, then syntax analysis is successfully completed.
Extended grammar for Gexpr1:
G’expr1 = (N, T, P, E’), where N = {E’, E, F, T}, T = {i, +, *, (, )},
P = {   0: E’ ® E, 1: E ® E+T, 2: E ® T,    3: T ® T*F,
  4: T ® F, 5: F ® (E), 6: F ® i        }