Табличный транслятор многочленов

Пользуясь выработанным форматом таблицы переходов, заполним ее для распознавателя многочленов. Имея ввиду, что должен выполняться не только синтаксический анализ, но и трансляция многочлена, предусмотрим в таблице графу «Процедура», в которой будем записывать номер семантической процедуры. Эта процедура будет вызываться при совпадении входного символа и символа в таблице. Если указан нулевой номер семантической процедуры, вызов не происходит (или процедура  не выполняет никаких действий). Некоторые состояния добавляются в таблицу лишь для того, чтобы предусмотреть в нужные моменты выполнение необходимых семантический процедур (например, состояния 1, 6, 25).

Таблица 4.

Сост.	Символ	Переход	Ошибка	Вызов	Читать	Проц.	Примечание
Многочлен
1	Л	2	-	-	-	3	Обнуление коэффициента
2	+	5	-	-	+	4
3	-	5	-	-	+	4
4	Л	5	-	-	-	5	Нет знака спереди
5	Л	12	-	+	-	0	На 1-е слагаемое
6	Л	7	-	-	-	6	После 1-го слагаемого
7	+	10	-	-	+	4	Начало цикла
8	-	10	-	-	+	4
9		0	+	-	-	7	Выход
10	Л	12	-	+	-	0	На слагаемое
11	Л	7	-	-	-	6	Конец цикла
Слагаемое
12	Ц	15	-	-	-	0
13	x	21	+	+	+	10	a=1
14	Л	0	-	-	-	9	После степени
15	Л	25	-	+	-	0	На целое
16	Л	17	-	-	-	8	После целого
17	x	19	-	-	+	0
18	Л	0	-	-	-	11	k=0
19	Л	21	-	+	-	0	На степень
20	Л	0	-	-	-	9	Конец слагаемого

Окончание табл.4

Перед выполнением перехода с возвратом необходимо запомнить номер состояния, в которое автомат должен возвратиться. Недостаточно использовать для этого отдельную переменную, способную хранить номер только одного состояния. Поскольку вызовы могут быть вложенными. Это соответствует стековой дисциплине (LIFO). Для запоминания номера состояния перед выполнением перехода используется стек.

Реализация стека

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

Структуру данных назовем стеком, если:

1. Определены:

a. тип данных, содержащихся в стеке (обозначим tData);

b. процедуры инициализации стека : Init (var S: tStack);

c. процедура добавления элемента в стек Push(var S: tStack: D: tData);

d. процедура извлечения элемента из стека: Pop (var S: tStack: D: tData);

2. Процедуры Push и Pop подчиняются дисциплине LIFO.

Можно представить два основных варианта реализации стека. В первом элементы хранятся в массиве, во втором – в списке. Запишем процедуры, предназначенные для работы со стеком, для первого случая.

Элементы помещаются в стек начиная с первой ячейки массива. Число элементов, находящихся в данный момент в стеке, будем хранить в переменной SP. Массив элементов и SP будут полями записи типа tStack.

const

    nmax = …; {Предельный объем стека}

type

    tStack = record

              a: array [1..nmax] of tData;

              SP: onteger;

end;

Запрограммируем теперь инициализацию стека, которая сводится к обнулению указателя и реализацию процедур, выполняющих добавление и извлечение элементов.

procedure Init (var S:tStack);

begin

    S.SP :=0;

end;

procedure Push (var S: tStack: D: tData);

begin

    if S.SP<nmax then begin

              S.SP := S.SP+1;

              S.a[S.SP] :=D;

              end

    else

              Error (‘Переполнение стека’);

end;

procedure Pop(var S: tStack: D: tData);

begin

    if S.SP > 0 then begin

              D:= S.a[S.SP];

              S.SP := S.SP – 1;

              end

    else

              Error(‘Стек пуст’)

end;

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

Запишем теперь функции, позволяющие проверять состояние стека (стек не пуст или не полон).

function NotEmpty (S: tStack): Boolean;

begin

    NotEmpty := S.SP >0;

end;

function NotFull (S: tStack): Boolean;

begin

    NotFull := S.SP < nmax;

end;

LL(1) – драйвер

Программу, которая выполняет распознавание, интерпретируя таблицу, называют драйвером. Для реализации драйвера будем использовать таблицу, тип которой определен как массив из записей.

tSynTable = array [1..n] of record

    Ch :char; {Символ}

    Go :integer; {Переход}

    Err :Boolean; {Ошибка}

    Call :Boolean; {Вызов}

    Read :Boolean; {Читать}

    Proc: integer; {Процедура}

end;

Драйвер использует следующие переменные:

T: tSynTable; {Таблица}

Ch: char; {Текущий символ}

Err: integer; {Признак ошибки}

Stack: tStack; {Стек}

i: integer; {Номер состояния}

Приведенный текст программы – драйвера не включает часть, которая заполняет таблицу перед началом работы. Программа также содержит и другие условности, касающиеся обозначений произвольного символа и цифр в таблице.

ResetText;

Init(Stack);

Push(Stack, 0);

Err := 0;

i := 1;

repeat

    if (Ch=T[i].Ch) or (T[i].Ch = Любой) or

    (T{i}.Ch = Цифра) and (Ch in [‘0’..’9’]);

    than begin

              if T[i].Proc <> 0 then Proc(T[i].Proc);

              if T[i].Read then NextCh;

              if T[i].Go = 0 then

                       Pop(Stack, i)

              else begin

                       if t[i].Call then Push(Stack, i+1);

                       i:= T[i].Go;

              end;

              end

    else if T[i].Err then

              Err:=i

    else

              i:=i+1;

until (i=0) or (Err<>0);

Предполагается, что процедура Proc способна выполнять семантическую процедуру с заданным номером.

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

Реакция на синтаксическую ошибку при использовании табличного анализатора может быть организована достаточно просто. При обнаружении ошибки цикл анализа немедленно прекращается, а переменная Err при этом содержит номер состояния, в котором произошла ошибка. Значение Err однозначно определяет тип ошибки. Сообщения об ошибке могут быть помещены в отдельную графу таблицы, в те строки, которые содержат «+» в столбце «Ошибка». Кроме синтаксических необходимо обрабатывать ошибки, которые обнаруживаются семантическими процедурами. Одно из решений, позволяющих не менять программу-драйвер, - присваивать переменной Err отрицательное значение при обнаружении ошибки семантической процедуры.

Порядок выполнения работы

1. Построить синтаксические диаграммы для заданной конструкции.

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

3. Построить синтаксическую таблицу и реализовать табличный LL(1) – анализатор.

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

Варианты заданий

1. Арифметическое выражение. Элементами выражения являются имена переменных, вещественные числа, функции (названия функций произвольные), знаки арифметических операций, круглые скобки. Вычислить выражение.

2. Сумма – последовательность натуральных чисел и имен, разделенных знаками плюс и минус. Возможен знак перед первым слагаемым. Считая, что имена обозначают неизвестные запросить у пользователя их значения и вычислить сумму. Значение одной и той же переменной, встречающейся в выражении больше одного раза, должно запрашиваться только один раз.

3. Сумма вещественных чисел. Вычислить сумму.

4. Квадратное уравнение с целыми коэффициентами. Найти корни уравнения.

5. Сумма обыкновенных дробей. Вычислить сумму.

6. Произведение вида , где  - целые числа. Программа запрашивает значение X и вычисляет произведение.

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

8. Сумма произведений – последовательность слагаемых, представляющих собой произведение нескольких операндов. Операнды – имена. Программа запрашивает вещественные значения, входящих в выражение переменных и вычисляет значение суммы. Значение каждой переменной вводится лишь однажды.

9. Последовательность, записанных через запятую элементов двухмерных массивов. Индексы – натуральные числа. Считается, что все массивы имеют размер 10*10, программа проверяет корректность задания индексов и формирует текст программы на Паскале, которая заполняет все массивы, имена которых встретились в выражении, случайными целыми числами; элементам, встретившимся в выражении должны быть присвоены нулевые значения. Сгенерированная программа должна распечатывать содержимое всех этих массивов.

10. Числовой ряд вида , где  - натуральные числа. Вычислить точную сумму ряда. Результат представить в виде обыкновенной дроби.

11. Отношение Операнд  Операнд, где Операнд – целое или имя;  - знак отношения (<, >, =, <>, >=, <=). Полагая, что имена – это идентификаторы целочисленных переменных, программа запрашивает их значения и проверяет истинность отношения.

12. Бесскобочное арифметическое выражение с функциями. Все операнды – однобуквенные имена. Аргументы функций записываются в скобках. Спрашивая у пользователя вещественное значение каждой переменной и значение каждой функции при заданном числовом значении аргумента, программа – интерпретатор вычисляет выражение.

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

1. Сравните восходящий и нисходящий распознаватели. Какими преимуществами и недостатками обладает каждый из этих методов?

2. Какой цели служит преобразование правил КС-грамматик? Всегда ли это преобразование ведет к упрощению правил?

3. На алгоритме какого распознавателя основан метод рекурсивного спуска? Можно ли реализовать распознаватель по методу расширенного рекурсивного спуска для грамматики, содержащей левую рекурсию?

4. За счет чего класс LL(1)-грамматик является более широким, чем класс КС-грамматик?

5. На каком алгоритме основана работа распознавателя для LL(k)-грамматики?

Список литературы

1. Молчанов А.Ю. Системное программное обеспечение: Учебник для вузов – СПб.: Питер, 2006. - 396с.

2. Молчанов А.Ю. Системное программное обеспечение. Лабораторный практикум – СПб.: Питер, 2005. - 284с.

3. Свердлов С.З. Языки программирования и методы трансляции: Учебное пособие – СПб.: Питер, 2007. – 638 с.

Составитель СТРОКИНА Юлия Германовна

ПОСТРОЕНИЕ СИНТАКСИЧЕСКОГО АНАЛИЗАТОРА

Методические указания

к лабораторной работе по дисциплине

 «Системное программное обеспечение»

Подписано в печать         . Формат 60х84 1/16 .

Бумага офсетная. Печать плоская. Гарнитура Times New Roman Cyr.

Усл. печ. л. 1,9 . Усл.кр.-отт. 1,9.Уч.-изд. л. 1,8 . 

Тираж 100 экз. Заказ. №

ГОУ ВПО Уфимский государственный авиационный технический университет

Центр оперативной полиграфии УГАТУ

450000, Уфа - центр, ул. К. Маркса, 12  

Федеральное агентство по образованию

Государственное образовательное учреждение

высшего профессионального образования

Уфимский государственный авиационный технический университет

Кафедра вычислительной техники и защиты информации

ПОСТРОЕНИЕ СИНТАКСИЧЕСКОГО АНАЛИЗАТОРА

Методические указания к лабораторной работе

по дисциплине

 «Системное программное обеспечение»

Уфа 2008