Постановка задачи к лабораторной работе № 4

Разработать программное средство, автоматизирующее процесс эквивалентного преобразования КС-грамматик. Программное средство должно выполнять следующие функции:

1) организация ввода грамматики и проверка ее на принадлежность к классу КС-грамматик;

2) проверка существования языка КС-грамматики;

3) реализация эквивалентных преобразований грамматики, направленных на удаление:

а) бесполезных символов;

б) недостижимых символов;

в) e-правил;

г) цепных правил;

д) левой факторизации правил;

е) прямой левой рекурсии.

Варианты индивидуальных заданий представлены в таблице 4.1.

 

Таблица 4.1 – Варианты индивидуальных заданий к лабораторной работе № 4 и 5

 

Вариант	Контекстно-свободная грамматика
	G =({ S, A, B, D, E },{ a, b, c, e }, P, S),где P: 1) S ® AB | e;2) A ® Aa | S | a;3) B ® bD | bS | b;4) D ® ccD;5) E ® eE |e.
	G =({ E, T, F, G, H }, {+, -, *, /, n, m, h }, P, E), где P: 1) E ® T | E + T | E - T | e; 2) T ® F | F * T | F / T | e; 3) F ® G | Fn | n; 4) G ® Gm; 5) H ® Hh | h.
	G =({ S, R, T, X, Y }, { a, b, p, g, y }, P, S), где P:
	G =({ Q, A, B, C, D }, { a, b, c, d }, P, Q), где P:
	G =({ R, T, F, G, K }, { m, i, j, k, ^, ~, ^}, P, R), где P: 1) R ® R ~ T ^ | R ^ T ^ | e; 2) T ® F | Fi | Fj | Gk | e;3) G ® GkG; 4) K ® Ki | Km | m.
	G =({ S, X, Y, Z, K }, { x, y, z, k, #, $}, P, S), где P: 1) S ® X | Y | Z; 2) X ® x#X | x#Y | e;3) Y ® Yy $ |Yz $ | $ | e;4) Z ® Zz $;5) K ® Kk $ | k $.
	G =({ S, L, M, P, N }, { n, m, l, p, @, ^}, V, S), где V: 1) S ®@ nL | @ mM | P;2) L ® M | Ll ^ | Lm ^ | e;3) M ® L | Mm | mm; 4) N ® pN @ | @;5) P ® nmP.
	G =({ X, Y, Z, K, L }, { a, b, l, =, <, >, Ù, Ú, Ø}, V, X), где V: 1) X ® Y | Y = Y | Y < Y | Y > Y | K;2) Y ® Y Ù Z | Y Ú Z | e; 3) Z ® Ø a | Ø b| e;4) K ® Ø K;5) L ® l | a | b.
	G =({ Q, A, B, C, D }, {0, 1, -}, P, Q), где P: 1) Q ®01 A | 01 B | A; 2) A ® 0 B 1 | B | 1 | e; 3) B ® BA 0 | B 1 | C | e; 4) C ®0 C 11; 5) D ® - D 1 | -0 | -1.
	G =({ R, T, U, W, V }, {0, 1, +, -, *, /}, P, R), где P: 1) R ® T 1 T | T 1 U | W | e;2) T ® U | T 01 | T 10 | e;3) U ®+ U | + 0 | +1 4) W ® W - W | W + W;5) V ®*0 | /1.

Продолжение таблицы 4.1 – Варианты индивидуальных заданий к лабораторной работе № 4 и 5

 

Вариант	Контекстно-свободная грамматика
	G =({ S, R, T, F, E }, { a, b, k, {, [, }, ], ^}, P, S), где P: 1) S® { R | [ R;2) R ® Ra } | Ra ] | a | T | F | e;3) F ®{ F } | bb; 4) T ®[ T ];5) E ® k ^.
	G =({ Y, K, M, L, S }, { a, b, *, /, ^}, P, Y), где P: 1) Y ® KS | KM;2) K ® K * | K / | S;3) S ® Sa / | Sb / | e;4) M ®* M *; 5) L ® L^ | ^a.

 

5 Лабораторная работа № 5. Построение автомата с магазинной памятью по контекстно-свободной грамматике

 

Цель: - закрепить понятия «автомат с магазинной памятью (МП-автомат)», «расширенный МП-автомат», «конфигурация МП-автомата»; «строка и язык, допускаемые МП-автоматом»;

- сформировать умения и навыки построения МП-автомата и расширенного МП-автомата по КС-грамматике, разбора входной строки с помощью МП-автомата.

 

Основы теории

 

КС-языки можно распознавать с помощью автомата с магазинной памятью (МП-автомата).

Определение 5.1. МП-автомат можно представить в виде семерки:

 

, (5.1)

 

где Q – конечное множество состояний автомата;

T – конечный входной алфавит;

N – конечный магазинный алфавит;

F – магазинная функция, отображающая множество

во множество всех подмножеств множества , т.е.

® ;

q ₀ – начальное состояние автомата, q ₀ Î Q;

N ₀– начальный символ магазина, N ₀ Î N;

Z – множество заключительных состояний автомата, Z Í Q.

 

Определение 5.2. Конфигурацией МП-автомата называется тройка вида:

 

, (5.2)

где q - текущее состояние автомата, q Î Q;

w - часть входной строки, первый символ которой находится под входной головкой,

- содержимое магазина,

Общая схема МП-автомата представлена на рисунке 5.1.

 

 

 

Рисунок 5.1 – Схема МП-автомата

 

Алгоритм 5.1. Функционирование МП-автомата

 

Начальной конфигурацией МП-автомата является конфигурация (q ₀, , N ₀).

Шаг работы МП-автомата будем представлять в виде отношения непосредственного следования конфигураций (обозначается «|=») и отношения достижимости конфигураций (обозначается «|=*»). Если одним из значений магазинной функции является , то записывается . При этом возможны следующие варианты.

1) Случай t Î T. Автомат находится в текущем состоянии q, читает входной символ t, имеет в вершине стека символ S. Он переходит в очередное состояние , сдвигает входную головку на ячейку вправо и заменяет верхний символ S строкой магазинных символов. Вариант означает, что S удаляется из стека.

2) Случай . Отличается от первого случая тем, что входной символ t просто не принимается во внимание, и входная головка не сдвигается. Такой шаг работы МП-автомата называется -шагом, который может выполняться даже после завершения чтения входной строки.

Заключительной конфигурацией МП-автомата является конфигурация (q, , ), где q Î Z.

Определение 5.3. МП-автомат допускает входную стоку , если существует путь по конфигурациям для некоторых q Î Z и .

Определение 5.4. Язык L, распознаваемый (принимаемый) МП-автоматом М определяется как множество вида:

 

и для некоторых q Î Z и }.

 

Определение 5.5. МП-автомат с магазинной функцией называется расширенным МП-автоматом, т.е. автоматом, который может заменять цепочку символов конечной длины в верхушке стека на другую цепочку символов конечной длины.

 

Существуют КС-языки, МП-автоматы и расширенные МП-автоматы, определяющие один и тот же язык.

 

Алгоритм 5.2. Построение МП-автомата по КС-грамматике

 

Построим МП-автомат, выполняющий левосторонний разбор. Данный автомат обладает только одним состоянием и принимает входную строку опустошением магазина. Стек используется для размещения текущей сентенции, первоначально это начальный символ грамматики. Очередная сентенция получается заменой верхнего нетерминала стека.

 

Вход: КС-грамматика .

Выход: МП-автомат такой, что L (M) = L (G).

 

Шаг 1. Положить Q = { q }, q ₀ = q, Z = Æ, N = V_T È V_N, T = V_T, N ₀ = S.

Шаг 2. Для каждого правила вида (А ® ) , где сформировать магазинную функцию вида . Эти функции предписывают замещать нетерминал в вершине стека по правилу грамматики.

Шаг 3. Для каждого t сформировать магазинную функцию вида , которая выталкивает из стека символ, совпадающий с входным, и перемещает читающую головку. Эти функции обеспечивают опустошение стека.

 

Пример 5.1. Дана КС-грамматика:

G ({+, (,), a }, { S, A }, { S ® S + A | A, A ®(S) | a },{ S }). Последовательность построения МП-автомата будет иметь вид.

1) Q = { q }, q ₀ = q, T = {+, (,), a }, N = {+, (,), a, S, A }, N ₀ = S, Z = Æ.

2) F (q, , S) = (q, S + A), F (q, , S) = (q, A), F (q, , A) = (q,(S)); F (q, , A) = (q, a).

3) F (q, t, t) = (q, ) для каждого t Î{+, (,), a }.

 

Распознавание строки (а) построенным МП-автоматом представлено в таблице 5.1. Полученный МП-автомат является недетерминированным.

Таблица 5.1 – Распознавание МП-автоматом строки (а)

 

Номер конфигурации	Текущее состояние	Входная строка	Содержимое магазина
	q	(a)	S
	q	(a)	A
	q	(a)	(S)
	q	a)	S)
	q	a)	A)
	q	a)	a)
	q	)	)
	q

 

Алгоритм 5.3. Построение расширенного МП-автомата

по КС-грамматике

 

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

 

Вход: КС-грамматика .

Выход: расширенный МП-автомат такой, что L (M) = L (G).

 

Шаг 1. Положить Q = { q, r }, q ₀ = q, Z = { r }, N = V_T È V_N È {#}, T = V_T, N ₀ = #.

Шаг 2. Для каждого правила вида , где , сформировать магазинную функцию вида , предписывающую заменять правую часть правила в вершине стека нетерминалом из левой части, независимо от текущего символа входной строки.

Шаг 3. Для каждого терминала сформировать магазинную функцию вида , которая помещает символ входной строки в вершину стека, если там нет правой части правила, и перемещает читающую головку.

Шаг 4. Предусмотреть магазинную функцию для перевода автомата в заключительное состояние .

 

Пример 5.2. Для грамматики из примера 5.1 построить расширенный МП-автомат. Последовательность построения МП-автомата будет иметь вид.

1) Q = { q, r }, q ₀ = q, T = {+, (,), a }, N = {+, (,), a, S, A }, N ₀ = #, Z = r.

2) F (q, , S + A) = (q, S), F (q, , A) = (q, S), F (q, , (S)) = (q, A), F (q, , a) =(q, A).

3) F (q, t, ) = (q, t) для каждого t Î{+, (,), a }.

4) F (q, , # S) = (r, ).

 

Распознавание строки (а) расширенным МП-автоматом представлено в таблице 5.2. Полученный МП-автомат является детерминированным.

 

Таблица 5.2 – Распознавание расширенным МП-автоматом строки (а)

 

Номер конфигурации	Текущее состояние	Входная строка	Содержимое магазина
	q	(a)	#
	q	a)	#(
	q	)	#(a
	q	)	#(A
	q	)	#(S
	q		#(S)
	q		# A
	q		# S
	r

 

Постановка задачи к лабораторной работе № 5

 

Разработать программное средство, реализующее следующие функции:

а) ввод произвольной формальной грамматики и проверка ее на принадлежность к классу КС-грамматик;

б) построение МП-автомата по КС-грамматике;

в) построение расширенного МП-автомата по КС-грамматике.

Продемонстрировать разбор некоторой входной строки с помощью построенных автоматов для случая:

а) входная строка принадлежит языку исходной КС-грамматики и допускается МП-автоматом;

б) входная строка не принадлежит языку исходной КС-грамматики и не принимается МП-автоматом.

Индивидуальные варианты заданий представлены в таблице 4.1.

6 Лабораторная работа № 6. Моделирование функционирования распознавателя для LL (1) - грамматик

 

Цель: - закрепить понятие «LL (k) –грамматика», необходимые и достаточные условия LL (k) –грамматики;

- сформировать умения и навыки построения множеств FIRST (k, a) и FOLLOW (k, a), распознавателя для LL (1) - грамматик.

Основы теории

Определение 6.1. КС-грамматика обладает свойством LL (k) для некоторого k >0, если на каждом шаге вывода для однозначного выбора очередной альтернативы МП-автомату достаточно знать символ на верхушке стека и рассмотреть первые k символов от текущего положения считывающей головки во входной строке.

Определение 6.2. КС-грамматика называется LL (k) - грамматикой, если она обладает свойством LL (k) для некоторого k >0.

В основе распознавателя LL (k) - грамматик лежит левосторонний разбор строки языка. Исходной сентенциальной формой является начальный символ грамматики, а целевой – заданная строка языка. На каждом шаге разбора правило грамматики применяется к самому левому нетерминалу сентенции. Данный процесс соответствует построению дерева разбора цепочки сверху вниз (от корня к листьям). Отсюда и произошла аббревиатура LL (k): первая «L» (от слова «left») означает левосторонний ввод исходной цепочки символов, вторая «L» - левосторонний вывод в процессе работы распознавателя.

Определение 6.3. Для построения распознавателей для LL (k) - грамматик используются два множества:

- FIRST (k, a) – множество терминальных цепочек, выводимых из цепочки a Î(V_T È V_N)*, укороченных до k символов;

- FOLLOW (k, A) – множество укороченных до k символов терминальных цепочек, которые могут следовать непосредственно за A Î V_N в цепочках вывода.

Формально эти множества можно определить следующим образом:

- FIRST (k, a) = { w Î V_T* | $ вывод a Þ* w и | w | £ k или $ вывод a Þ* wx и | w | = k; x, a Î (V_T È V_N)*, k > 0};

- FOLLOW (k, A) = { w Î V_T * | $ вывод S Þ* aAg и w Î FIRST (k, g); a, g Î V*, A Î V_N, k >0}.

 

Теорема 6.1. Необходимое и достаточное условие LL (1) - грамматики

Для того чтобы грамматика G (V_N, V_T, P, S) была LL (1) - грамматикой необходимо и достаточно, чтобы для каждого символа А Î V_N, у которого в грамматике существует более одного правила вида А ®a₁ | a₂ |…| a _n, выполнялось требование:

 

FIRST (1, a _iFOLLOW (1, A)) Ç FIRST (1, a _jFOLLOW (1, A)) = Æ,

" i ¹ j,0< i £ n, 0< j £ n.

 

Т.е. если для символа А отсутствует правило вида А ®e, то все множества FIRST (1, a₁), FIRST (1, a₂),…, FIRST (1, a _n) должны попарно не пересекаться, если же присутствует правило А ®e, то они не должны также пересекаться с множеством FOLLOW (1, A).

Для построения распознавателей для LL (1) - грамматик необходимо построить множества FIRST (1, x) и FOLLOW (1, A). Причем, если строка х будет начинаться с терминального символа а, то FIRST (1, x)= a, и если она будет начинаться с нетерминального символа А, то FIRST (1, x)= FIRST (1, A). Следовательно, достаточно рассмотреть алгоритмы построения множеств FIRST (1, A) и FOLLOW (1, A) для каждого нетерминального символа А.

Алгоритм 6.1. Построение множества FIRST (1, A)

 

Для выполнения алгоритма необходимо предварительно преобразовать исходную грамматику G в грамматику G ¢, не содержащую e-правил (см. лабораторную работу № 4). Алгоритм построения множества FIRST (1, A) использует грамматику G ¢.

Шаг 1. Первоначально внести во множество первых символов для каждого нетерминального символа А все символы, стоящие в начале правых частей правил для этого нетерминала, т.е.

 

" А Î V_N FIRST ₀(1, A) = { X | A ® X a Î P, X Î(V_T È V_N),aÎ(V_T È V_N)^*}.

 

Шаг 2.Для всех А Î V_N положить:

FIRST_{i +1}(1, A) = FIRST_i (1, A) È FIRST_i (1, B), " В Î(FIRST (1, A)Ç V_N).

 

Шаг 3. Если существует А Î V_N, такой что FIRST_{i +1}(1, A) ¹ FIRST_i (1, A), то присвоить i = i +1 и вернуться к шагу 2, иначе перейти к шагу 4.

Шаг 4.Исключить из построенных множеств все нетерминальные символы, т.е.

 

" A Î V_N FIRST (1, A) = FIRST_i (1, A) _{\ N} .

 

Алгоритм 6.2. Построение множества FOLLOW (1, A)

 

Алгоритм основан на использовании правил вывода грамматики G.

Шаг 1.Первоначально внести во множество последующих символов для каждого нетерминального символа А все символы, которые в правых частях правил вывода встречаются непосредственно за символом А, т.е.

" A Î V_N FOLLOW ₀(1, A) = { X | $ B ® a AX b Î P, B Î V_N, X Î (V_T È V_N),

a, b Î(V_T È V_N)^*}.

 

Шаг 2.Внести пустую строку во множество FOLLOW (1, S), т.е.

 

FOLLOW (1, S) = FOLLOW (1, S)È{ e }.

 

Шаг 3.Для всех А Î V_N вычислить:

FOLLOW ¢ _i (1, A)= FOLLOW_i (1, A)È FIRST (1, B)," B Î(FOLLOW_i (1, A)Ç V_N).

 

Шаг 4.Для всех А Î V_N положить:

FOLLOW²_i (1, A)= FOLLOW¢_i (1, A)È FOLLOW¢_i (1, B),

" B Î(FOLLOW¢_i (1, A)Ç V_N), если $ правило B ®e.

 

Шаг 5.Для всех А Î V_N определить:

FOLLOW_{i +1}(1, A) = FOLLOW²_i (1, A)È FOLLOW²_i (1, B),

для всех нетерминальных символов BÎV_N, имеющих правило вида

B ® aA, a Î(V_T È V_N)^*.

 

Шаг 6.Если существует A Î V_N такой, что FOLLOW_{i +1}(1, A)¹ FOLLOW_i (1, A), то положить i:= i +1 и вернуться к шагу 3, иначе перейти к шагу 7.

Шаг 7.Исключить из построенных множеств все нетерминальные символы, т.е. " A Î V_N FOLLOW (1, A) = FOLLOW_i (1, A)_{\ N} .