Системное программное обеспечение. Лабораторный практикум

(начало и конец цепочки). Для них определены следующие отношения предшествования:

Имея построенные множества L_t(U) и R_t(U), заполнение матрицы операторного предшествования для КС-грамматики G(VT,VN,P,S) можно выполнить по следующему алгоритму:

1. Берем первый символ из множества терминальных символов грамматики VT:

Будем считать этот символ текущим терминальным символом.

2. Во всем множестве правил Р ищем правила вида C → xa_iby или C → xa_iUb_jy, где а_i – текущий терминальный символ, Ь_j – произвольный терминальный символ

U и С – произвольные нетерминальные символы

а х и у – произвольные цепочки символов, возможно пустые

Фактически производится поиск таких правил, в которых в правой части символы а_i и Ъ_j стоят рядом или же между ними есть не более одного нетерминального символа (причем символ а_i обязательно стоит слева от Ь_j).

3. Для всех символов Ь_j, найденных на шаге 2, выполняем следующее: ставим знак «=.» («составляет основу») в клетки матрицы операторного предшествования на пересечении строки, помеченной символом а_i, и столбца, помеченного символом b_j.

4. Во всем множестве правил Р ищем правила вида С → xa_iU_jy, где а_i – текущий терминальный символ, U_j и С– произвольные нетерминальные символы (U_j,

а х и у – произвольные цепочки символов, возможно пустые

Фактически ищем правила, в которых в правой части символ а_i стоит слева от нетерминального символа U_j.

5. Для всех символов U_j, найденных на шаге 4, берем множество символов L_t(U_j). Для всех терминальных символов c_k, входящих в это множество, выполняем следующее: ставим знак «<.» («предшествует») в клетки матрицы операторного предшествования на пересечении строки, помеченной символом a_i, и столбца, помеченного символом с_k.

6. Во всем множестве правил Р ищем правила вида С → xU_ja_iy, где a_i – текущий терминальный символ, U_j и С – произвольные нетерминальные символы

а x и y – произвольные цепочки символов, возможно пустые

Фактически ищем правила, в которых в правой части символ а стоит справа от нетерминального символа U_j.

7. Для всех символов U_j, найденных на шаге 6, берем множество символов R_t(U_j). Для всех терминальных символов c_k, входящих в это множество, выполняем следующее: ставим знак «.>» («следует») в клетки матрицы операторного предшествования на пересечении строки, помеченной символом с_k, и столбца, помеченного символом а_i.

8. Если рассмотрены все терминальные символы из множества VT, то переходим к шагу 9, иначе – берем очередной символ

из множества VT, i:= i + 1, делаем его текущим терминальным символом и возвращаемся к шагу 2.

9. Берем множество L_t(S) для целевого символа грамматики S. Для всех терминальных символов c_k, входящих в это множество, выполняем следующее: ставим знак «<.» («предшествует») в клетки матрицы операторного предшествования на пересечении строки, помеченной символом

(«начало строки»), и столбца, помеченного символом c_k.

10. Берем множество R_t(S) для целевого символа грамматики S. Для всех терминальных символов c_k, входящих в это множество, выполняем следующее: ставим знак «.>» («следует») в клетки матрицы операторного предшествования на пересечении строки, помеченной символом c_k, и столбца, помеченного символом

(«конец строки»). Построение матрицы закончено.

Если на всех шагах алгоритма построения матрицы операторного предшествования не возникло противоречий, когда в одну и ту же клетку матрицы надо записать два или три различных символа предшествования, то матрица построена правильно (в каждой клетке такой матрицы присутствует один из символов предшествования – «=.», «<.» или «.>» – или же клетка пуста). Если на каком-то шаге возникло противоречие, значит, исходная КС-грамматика G(VT,VN,P,S) не является грамматикой операторного предшествования. В этом случае можно попробовать преобразовать грамматику так, что она станет удовлетворять требованиям операторного предшествования (что не всегда возможно), либо необходимо использовать другой тип распознавателя.

Более подробно работа с грамматиками предшествования и другими типами распознавателей описана в [1–4, 7].

Алгоритм «сдвиг-свертка» для грамматик операторного предшествования

Алгоритм «сдвиг-свертка» для грамматики операторного предшествования выполняется МП-автоматом с одним состоянием. Для моделирования его работы необходима входная цепочка символов и стек символов, в котором автомат может обращаться не только к самому верхнему символу, но и к некоторой цепочке символов на вершине стека.

Этот алгоритм для заданной КС-грамматики G(VT,VN,P,S) при наличии построенной матрицы предшествования можно описать следующим образом:

1. Поместить в верхушку стека символ «начало строки», считывающую головку МП-автомата поместить в начало входной цепочки (текущим входным символом становится первый символ входной цепочки). В конец входной цепочки надо дописать символ «конец строки».