49
правок
Изменения
→Алгоритм Кока-Янгера-Касами
:: <tex>\forall</tex>i <tex>t_{i1}</tex> = { A | A → <tex>a_i</tex>};
:: <tex>\forall</tex>i < j <tex>t_{ij}</tex> = {A | A→BC и <tex>1 \leqslant k < j : B \in t_{ik}, C \in t_{i+k, j-k}</tex>}.
Действительно, в каждый элемент <tex>t_{i1}</tex> (в данном случае удобнее рассматривать первой нижнюю строку) помещаются все нетерминалы, для которых существует правило A → <tex>a_i</tex>. Пусть теперь заполнены все строки до j-1-й включительно.
Рассмотрим элемент <tex>t_{ij}</tex>, соответствующий фрагменту <<tex>a_1,\ldots, a_j </tex>> входной строки. Разобьём его всеми способами на пары соседних строк <<tex>a_i</tex>> и <<tex>a_{i+1}...a_j</tex>>; <<tex>a_ia_{i+1}</tex>> и <<tex>a_{i+2} ...a_j</tex>>, и т.д. Каждому варианту разбиения соответствует пара элементов матрицы, в которых стоят нетерминалы, из которых могут быть выведены соответствующие строки. Пусть эта пара элементов – (t',t"). В рассматриваемый элемент <tex>t_{ij}</tex> помещаем нетерминал А, если среди правил грамматики есть правило А→ВС, и нетерминал В входит в элемент t', а С – входит в элемент t".
