Курсовая работа: Построение распознавателя для заданной грамматики и реализация его в виде программы которая проверяет

Пример проверки нетерминалов грамматики:

G [S]: VN = {S, A, B, C, D}; VT = {a, b, c, d}; P = {S - aS (1), S - aA (2), A - bB (3),

A - bC (4), B - d (5) D - c (6) }.

1. Проверка нетерминалов на продуктивность.

В правых частях правил (5) и (6) только терминалы. Внесем в создаваемый список продуктивных нетерминалы B и, D. Затем в соответствии с правилом (3) - A (в правой части терминал и продуктивный нетерминал); в соответствии с правилом (2) - S; анализ других правил список не пополняет. Получен исчерпывающий список продуктивных нетерминалов - { B, D, A, S}. В списке отсутствует нетерминал С (непродуктивный, правило (4) для минимизации исходной грамматики исключим из множества P).

2. Проверка нетерминалов на достижимость.

Внесем на первом шаге в создаваемый список достижимых нетерминалов начальный символ грамматики S, затем на основании правила (2) дополним список нетерминалом A; правило (3) дает основания внести в список нетерминал В. Дальнейший анализ правил в соответствии с алгоритмом поиска достижимых нетерминалов список не пополняет. Получен исчерпывающий список продуктивных нетерминалов - {S,A,B}. В списке отсутствует нетерминал D (недостижимый, правило (6) для минимизации исходной грамматики исключим из множества P).

В результате этих преобразований получим минимальную грамматику G1 [S], эквивалентную исходной.

G1 [S]: VN = {S, A, B}; VT = {a, b, d}; начальный символ S;

P = { S - aS (1), S - aA (2), A - bB (3), B - d (4) }.

2. Разработка программного продукта

2.1 Построение распознавателя для грамматики

Для заданной в варианте грамматики построить распознаватель.

Вариант 10:

G [Q] = (VT = { a, b, h }; VN = { Q, A, B, H }; P = { Q -a Q H (1);

Q - b a h A (2); A - a b B h (3); H - b B (4); B - a b b H h (5); H -e (6) })

Решение:

1 Проверка нетерминальные символов исходной грамматики на достижимость (все правила, в которые входят недостижимые нетерминалы, не нарушая эквивалентности, можно исключить).

(2) (3) (5) - (номера правил)

{ Q} -{ Q, A } - { Q, A, B } - { Q, A, B, H }

(недостижимых нетерминалов нет)

2 Проверка нетерминальных символов полученной после выполнения п.1 грамматики на продуктивность (все правила, в которые входят непродуктивные нетерминальные символы, не нарушая эквивалентности, можно исключить).

(6) (5) (3) (2) - (номера правил)

-{ Н } -{ Н, B } -{Н, B, A }-{Н, B, A, Q }

(непродуктивных нетерминалов нет).

3. Определение типа полученной после выполнения предыдущих пунктов грамматики.

После эквивалентных преобразований новая грамматика не изменилась:

G [Q] = (VT = { a, b, h }; VN = { Q, A, B, H };

P = { Q-aQ H (1);

Q - b a h A (2);

A - a b B h (3);