Грамматика
E→E+T
E→T
T→T*F
T→F
F→(E)
F→x
Шаг 1 Добавьте начальный символ
S=E
E→E+T
E→T
T→T*F
T→F
F→(E)
F→x
Шаг 2 Присвойте переменные терминалам
A→ +
B→ *
C→(
D→ )
F→x
Шаг 3 Удалите эпсилон, который в эта грамматика недоступна
Шаг 4 Удалить правило
S→E
E→E
T→T
So we have
T→F*F
E→T+T
S→E+T
Шаг 5 Удалить правило
E→T
T→F
So we have
T→F→(E)| x|F*F
E→T*F
Шаг 6
Преобразовать в форму A → B C и A → a До сих пор мы имели S = E + TT → (E) | x | F FE → T FF → (E) F → x A → + B → * C → (D →) F → x
Используя терминальные переменные, мы получаем
S=EAT
T→CED|F |FBF
E→TBF
F→CED
F→x
A→ +
B→ *
C→(
D→ )
F→x
Let
A_1=AT
B_1=BF
E_1=ED
Итак, окончательный CNF составляет
S=EA_1
T→CE_1 |x|FB_1
E→TB_1
F→CE_1 | x
A→ +
B→ *
C→(
D→ )
F→x
A_1=AT
B_1=BF
E_1=ED