Выполнение лабораторной работы

1. В соответствии с вариантом выбрать из табл. 7.2 исходную цепочку для синтаксического разбора.

2. На основе приведенной выше грамматики и ее правил вывода сформировать синтаксическое дерево разбора данного выражения, аналогичное дереву на рис. 7.2.

3. Зафиксировать цепочку вывода.

4. Зафиксировать последовательность используемых для вывода правил.

5. Сформировать цепочку вывода и последовательность правил для правостороннего вывода.

Таблица 7.2

№	АС	ВС
1	(c-b)-b*c+b	c*b-(b-c)-c
2	(b*(b+c))/c-b	c/(b*(c+b))-c
3	b+c-b/(b+c)	(c+b)/b-c+b
4	b*b+c-b/c	c/b+b*b
5	b/(c-b*c)-c	c-(c*b-c)/b
6	b+c/(c*(b-c))	(c-b)/(c+b)+b
7	(b+c)*(b-c)+b	b+(c-b)*(b+c)
8	(c-b)/(b+c)-b	b-(b+c)/(c-b)
9	c/b-(b+c)*b	b*(b+c)-b/c
10	b+c-b/(c+b)	(c+b)/b-c+b
11	(c+b-c+b)/c	c/(c+b-c+b)
12	(b+c-c)*(c-b)	(b-c)+(c-b+c)
13	(b+c*(b+c))*b	b*((c+b)*c+b)
14	(c-b*(b-c))/c	c/((b-c)*b-c)
15	b/(c-b)-b/c	c/b-(c-b)/b
16	b*c-(c-b*c)	b+c*b-(b-c)
17	b*c+(c+b/c)	b-c/((c+b)*b)
18	b/c-(b-c*b)	(c+b)/b-c+b
19	b/c-(b/c-c)	c/b-c+b*b
20	b/c+(c/b-c)	c-(c*b-c)/b
21	(c/b-c)-b/c	((c-b)*c)/c+b
22	(b/c+c)+c/b	b+(c-b)*(c+b)
23	(c+c*b)*b*c	b-(c+b)/(b-c)
24	(c*b-c/b)*(c+b)	b*(c+b)-b/c

Содержание отчета

1. Исходная цепочка;

2. Используемая грамматика;

3. Результаты синтаксического разбора «сверху вниз» и «снизу вверх».

Контрольные вопросы

1. Зачем продукции нумеруются?

2. При движении вниз дерево разбора строится слева направо ли справа налево?

3. Могут ли нетерминальные символы быть листьями дерева разбора?

4. Что является корнем дерева разбора?

5. Когда заканчивается построение дерева разбора?

Лабораторная работа №8

Нисходящее распознавание с подбором альтернатив

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

Введение

В предыдущей лабораторной работе дерево разбора (распознавания) строилось человеком на основе визуального анализа исходного предложения и набора правил вывода. В реальных трансляторах данная задача решается посредством некоторого автомата, на выходе которого выводится результат разбора. Существует несколько алгоритмов подобной процедуры. Одним из наиболее распространенных является нисходящее распознавание с подбором альтернатив.

Для его реализации используется распознаватель (рис. 8.1), включающий устройство управления (УУ в виде автомата) и два стека: стек L₁ автомата и дополнительный стек L₂. Данный автомат характеризуется одним основным состоянием q и дополнительным состоянием возврата b.

На вход распознавателя поступает текст из терминальных символов и считывающая головка в начальный момент находится в крайнем левом положении, т.е. напротив первого символа цепочки. также в этот момент в стеке L₁ находится целевой символ грамматики S.

В конечный момент стек L₁ пуст, а считывающая головка находится за последним символов входной цепочки.

Неформально работа рассматриваемого автомата включает два основных действия:

1. Если на верхушке основного стека L₁ находится нетерминальный символ А и в грамматике есть правило вида А  , то в стеке символ А можно заменить на цепочку  (рис. 8.2). Головка распознавателя при этом не сдвигается. Такой шаг распознавания называется подбором альтернатив.

2. Если на верхушке стека находится терминальный символ а  VT и он совпадает с текущим символом входной цепочки, то данный символ можно выбросить из стека и передвинуть головку считывания на один шаг вправо (рис. 8.3). Этот шаг называется выбросом.

Рассматриваемый автомат является недетерминированным, т.е., если набор продукций грамматики Р допускает правила вида А  ₁  ₂ ₃  . . ., то у автомата на данном шаге существует несколько альтернатив.

Автомат реализует левосторонний вывод, посему в грамматике не должно быть левых рекурсий А  ...  А ..., так как автомат может войти в бесконечный цикл.

При разборе распознаватель должен хранить информацию о пройденном пути (какие альтернативы и на каком шаге были выбраны).

Более формально данный распознаватель предполагает:

1. Входная цепочка имеет вид  = a₁a₂ ... a_n,   = n.

2. Все альтернативы для нетерминальных символов вида А  ₁  ₂ ₃  . . . _k пронумерованы.

3. В алгоритме есть дополнительное состояние back (назад), предназначенное для возврата назад к уже прочитанной части цепочки.

4. Для хранения уже перебранных альтернатив используется дополнительный стек L₂, в котором может храниться следующая информация:

• символы а  VT входного языка автомата;

• номера продукций, т.е. символы вида А_j (A  VN, A_j - j-я альтернатива для данного нетерминального символа).

Основной стек L₁.

Оба стека представляются в виде цепочки. Но в стек L₁ символы помещаются слева, а в L₂ - справа. Теперь текущее состояние распознавателя на каждом шаге описывается четверкой (К, i, L₁, L₂),

где К = {k, b};

i - положение считывающей головки во входной цепочке символов  (1<nn+1);

L₁ - содержимое основного стека автомата;

L₂ - содержимое дополнительного стека.

Начальное состояние распознавателя: (k, 1, S, ), где S - целевой символ грамматики.

Алгоритм распознавания включает шесть разновидностей шагов:

В1 (разрастание). Реализуется переход вида (k, i, A, )  (k, i, _j, A_j)

Такой шаг выполняется, если наверху L₁ нетерминальный символ А (рис. 8.4) и выбирается первая альтернатива А^j  _j. Очевидно, что этот вариант должен быть первым при запуске разбора.

В2 (успешное сравнение). Реализуется переход вида (k, i, а, )  (k, i+1, , а), если наверху стека символ а  VТ и этот же символ является текущим во входной строке (см. рис. 8.5).

В3 (завершение). Если текущее состояние имеет вид (k, i, ,  (состояние k и стек L₁ пуст)) то проводится анализ на предмет завершения алгоритма. Если считывающая головка вышла за пределы входной строки, то алгоритм распознавания успешно завершен (рис. 8.6). В противном случае надо возвращаться назад. Имеет место переход (k, i, , )  (b, i, , ).

В4 (неуспешное сравнение). Реализуется переход вида (k, i, а, )  (b, i, a, ), если наверху стека символ аVТ, но текущим во входной строке является другой терминальный символ (рис. 8.7). В этом случае надо идти назад.

В5 (возврат по входу). Надо идти назад. Реализуется переход вида (b, i, , a)  (b, i-1, a, ).

В6 (другая альтернатива). Здесь возможны три подварианта.

а) Переход вида (b, i, _j, A^j)  (k, i, _j+1, A^j+1), если имеет место продукция _(А_j+1), т.е. не перебраны все варианты продукций у нетерминального символа. (Переход к другой продукции);

б) Выдача сигнала об ошибке, если А = S и не существует больше альтернатив для S.

в) Последний вариант - переход в состояние (b, i, _j, A^j)  (k, i, А, ): пройдены все возможные альтернативы для данного нетерминального символа и теперь надо возвращаться к нетерминальному символу слева, чтобы потом подняться еще выше назад (рис. 8.9).

Если распознавание завершилось успешно, то в стеке L₂ будет сохранен весь пройденный путь.

В качестве примера работы данного распознавателя рассмотрим начало нисходящего разбора предложения, проанализированного в предыдущей лабораторной работе. Естественно, что сохраняется введенная грамматика и нумерация ее продукций. Перечень первых двадцати шагов распознавателя, состояние распознавателя на каждом шаге и комментарий, объясняющий выбор разновидности шага, представлены в табл. 8.1. При этом надо помнить, что исходное состояние распознавателя описывается четверкой (k, 1, S, ).

Таблица 8.1

№ п/п	Шаг	Комментарий	Распознаватель (К, i, L1, L2)
1	2	3	4
1	1	Поскольку самое начало, то выбирается первая альтернатива на основе варианта 1 (разрастание)	(k,1,T,11)
2	1	Дальнейшее движение вниз (разрастание)	(k,1,Е,1131)
3	1	Самый нижний набор альтернатив (разрастание)	(k,1,(S),113151)
4	4	Терминальный символ цепочки с и верхушка стека ( не совпадают (неуспешное сравнение). Поэтому надо возвращаться назад. Далее могут быть варианты 5 и 6. Но в действительности 6, так как справа в L2 номер альтернативы 51	(b,1,(S),113151)

Таблица 8.1 Продолжение

1	2	3	4
5	6а	Есть возможность движения вправо по набору альтернатив (переход к другой продукции). В результате меняем (S) на с	(k,1,c,113152)
6	2	Текущий символ во входной цепочке и символ на верхушке стека L1 совпали (успешное сравнение). Символ с убирается в стек L2. В стеке L1 стало пусто. Поэтому далее надо провести проверку на окончание анализа.	(k,2,,113152с)
7	3	Попытка завершения (завершение). Но i < n, поэтому надо снова возвращаться, т.е. возможны варианты 5 или 6. Но здесь выбирается вариант 5, так как внизу стека L2 находится терминальный символ.	(b,2,,113152с)
8	5	Просто сдвиг во входной цепочке на один символ влево и возвращение с в стек L1 (возврат по входу).	(b,1,с,113152)
9	6а	Поскольку в правиле 5 еще не все альтернативы перебраны, то берётся следующая продукция по правилу 6а (переход к другой продукции), т.е. переход к символу b. Наверху L1 терминальный символ, поэтому далее проводится попытка сравнения.	(k,1,b,113153)
10	4	Имеет место неуспешное сравнение, так как сравниваются символы с и b. В результате снова надо возвращаться назад. Правило 5 не подходит (нет в конце L1 терминального символа). Поэтому надо выбирать правило 6, а поскольку все альтернативы в правиле вывода 5 уже перебраны, то выбирается вариант 6в.	(b,1,b,113153)
11	6в	Надо возвращаться назад по дереву альтернатив (другая альтернатива).	(b,1,Е,1131)
12	6а	Выбор другой альтернативы на более высоком уровне (переход к другой продукции)	(k,1,ЕF,1132)
13	1	Снова попытка движения вниз (разрастание)	(k,1,(S)F,113251)
14	4	Поскольку наверху стека L1 терминальный символ, то проводится попытка сравнения, которое оказывается неуспешным. Снова надо выбирать варианты 5 или 6. Выбирается 6 (другая альтернатива) и подвариант 6а (переход к другой продукции), так как справа у L2 стоит не последняя альтернатива	(b,1,(S)F,113251)
15	6а	Смена продукции (переход к другой продукции). Поскольку наверху L1 снова терминальный символ, то надо снова проводить сравнение	(k,1,сF,113252)
16	2	Успешное сравнение, так как текущий символ во входной цепочке и символ наверху L1 совпадают	(k,2,F,113252с)
17	1	Поскольку наверху L1 стоит нетерминальный символ, проводится разрастание	(k,2,*Е,113252с41)

Таблица 8.1 Продолжение

1	2	3	4
18	4	Поскольку наверху L1 теперь стоит терминальный символ, то надо проводить сравнение (варианты 2 или 4). В данном случае имеет место неуспешное сравнение, так как сравниваются символы * и +. В результате меняется состояние k на b.	(b,2,*Е,113252с41)
19	6a	Смена продукции (переход к другой продукции), поскольку не все варианты с номером 4 перебраны. Поскольку наверху L1 оказывается терминальный символ, то дальше надо снова проводить сравнение	(k,2,/F,113252с42)
20	4	Сравнение оказывается неуспешным (сравниваются / и +). Снова надо выбирать варианты 5 или 6. Выбирается 6 (другая альтернатива) и подвариант 6а (переход к другой продукции), так как справа у L2 стоит не последняя альтернатива.	(b,2,/F,113252с42)

Полное описание последовательности данного разбора представлено в работе [1].

На множестве продукций грамматики проводится трассировка использованных правил (рис. 8.10)

1: S  T; S  TR

1₁ 1₂

2: R  +T; R  -T; R  +TR; R  -TR

2₁ 2₂ 2₃ 2₄

3: T  E; T  EF

3₁ 3₂

4: F  *E; F  /E; F  *EF; F  /EF

4₁ 4₂ 4₃ 4₄

5: E  (S); E  c; E  b

5₁ 5₂ 5₃

Рис. 8.10