Set QG for Grammar G 1/2
24/42
Definition:
Let G = (N, T, P, S) be CFG.
QG = {<y>: A
® y·z is
an item in G}
Example:
Gist: QG is the set of all prefixes of the right-hand sides of rules from G.
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 }
Task: QG’expr1
1) Members
of QG’expr1
of length 0: <e> Î QG’expr1
2) Members
of QG’expr1
of length 1:
E’ ® E,
E ® E+T, E ® T, T ® T*F, T
® F, F ® (E), F
® i
<E> Î QG’expr1
<T> Î QG’expr1
<F>, <(>, <i> Î QG’expr1