Тестирование софта - статьи


Предварительные сведения - часть 2


>

Активным префиксом правосентенциальной формы называется префикс, не выходящий за границы самой правой основы этой формы.

Пунктом грамматики G называется правило вывода с точкой в некоторой позиции правой части. Множество всех пунктов грамматики G будем обозначать через

.

Пример. Правило вывода A > XYZ дает 4 пункта: A > •XYZ, A > X•YZ, A > XY•Z и A > XYZ•. >

Базисным называется пункт с точкой не у левого края правой части правила, а также пункт S' > •S в расширенной грамматике.

Замыканием множества пунктов I (обозначается closure(I)) называется наименьшее множество пунктов, содержащее I в качестве подмножества такое, что для всякого пункта A > ?•B?? I и любого правила B > ? пункт B > •? лежит в closure(I).

Для пары (I,X), где I некоторое множество пунктов грамматики G, а X – символ грамматики (терминал или нетерминал), определим функцию goto(I,X) – замыкание множества всех пунктов A > ?X•? таких, что A > ?•X? ? I.

Рассмотрим расширенную грамматику G' = (T,N',P',S'), где N' = N?{S'}, P = P?{S' > S}. Пусть I0 = closure({S' > •S}). Начиная с I0, строится система множеств пунктов I0,...,IN так, что для всякой пары (Ik,X), где k = 0,...,N и X – символ грамматики, существует индекс j = 0,...,N такой, что goto(Ik,X) = Ij. Эта система пунктов называется канонической системой множеств пунктов. Используя каноническую систему I0,...,IN, можно построить конечный автомат V, распознающий активные префиксы, если в качестве состояний sj взять канонические множества Ij, а переходы задать с помощью функции goto.

Широко известны два класса алгоритмов синтаксического анализа: LL-анализ и LR-анализ (см. [5]). LL-анализатор с помощью диаграммы переходов или таблицы разбора строит левый вывод предложения целевого языка. Нерекурсивная реализация LL-анализатора использует стек и таблицу разбора. Изначально в стеке находится символ конца строки $ и стартовый символ грамматики.


Начало  Назад  Вперед