close

Вход

Забыли?

вход по аккаунту

?

6 (2)

код для вставкиСкачать
РОСЖЕЛДОР
Федеральное государственное бюджетное образовательное
учреждение высшего профессионального образования
"Ростовский государственный университет путей сообщения"
(ФГБОУ ВПО РГУПС)
Лабораторная работа По дисциплине
"Системное программное обеспечение"
На тему
"Рекурсивный спуск для арифметического выражения"
Вариант №13
№6
Выполнил:
Ст-т Лысак В.В.
Гр. АИ-3-026
Проверил:
Пр-ль Жуков В.В.
Г. Ростов-на-Дону
2013 г.
Рекурсивный спуск
Метод рекурсивного спуска (англ. Recursive descent parser) - алгоритм синтаксического анализа, реализуемый путём взаимного вызова парсящих процедур, соответствующих правилам контекстно-свободной грамматики или БНФ. Применения правил последовательно, слева-направо поглощают токены, полученные от лексического анализатора. Это один из самых простых алгоритмов парсинга, подходящий для полностью ручной реализации.
Варианты реализации:
Предсказывающий парсер
Для парсеров этого типа нужна подходящая КС-грамматика, конкретно LL(k) грамматика, позволяющая по очередному токену или токенам однозначно выбрать (предсказать) один из альтернативных вариантов раскрытия каждого нетерминала.
Такой парсер работает за линейное время.
Вариантом является LL-парсер - реализация предсказывающего парсера с автоматическим построением "таблицы предсказания", определяющей по заданному нетерминалу и очередному токену подходящее правило для раскрытия нетерминала.
Парсер с возвратом
Вместо предсказания парсер просто пытается применить все альтернативные варианты правил по порядку, пока одна из попыток не увенчается успехом.
Такой парсер может потребовать экспоненциального времени работы, и не всегда гарантирует завершение, в зависимости от грамматики. Уязвим для левой рекурсии
В нашем случае используется предсказывающий парсер.
Цель работы
создать программу, которая осуществляет выполнение алгоритма рекурсивного спуска для следующей грамматики:
Алгоритм построения процедур.
Для построения процедур просматривается правая часть правила для каждого нетерминала.
Если встречается нетерминальный символ, то вызывается процедура для этого символа. Если она завершается без ошибки, то в исходном тексте фраза для этого терма закрыта, и все семантические действия тоже выполнены.
Если встречается терминальный символ, он сравнивается с очередным символом входной строки. Если они совпадают, этот символ просто закрывается. Указатель смещается на один шаг вправо. Если не совпадают, то это синтаксическая ошибка и трансляция прекращается.
Если встречается метасимвол:
Если встречается итерация {, то организуется цикл while, в который помещается все, что заключено в {}. Условием входа в цикл является то, что очередной символ не принадлежит множеству Follow для этого нетерминала.
Если встречается альтернатива ( | ), то организуется оператор if или несколько вложенных операторов if. Число ветвей должно быть на единицу больше, чем альтернатив. Условие для входа в ветвь - принадлежность текущего символа множеству First для этой альтернативы, а последняя ветвь Else соответствует синтаксической ошибке.
Код программы (pascal)
PROGRAM SPO_6;
VAR x:string;
i:integer;
flag:boolean;
fff:text;
//процедура обработки ошибок
PROCEDURE ERROR(error_type:integer);
BEGIN
if error_type=1 then writeln('expected end of file....');
if error_type=2 then writeln('invalid character!');
if error_type=3 then writeln('expected closing parenthesis...');
x[i]:='#';
END;
//процедура E с вызовом подпрограммы T, описанную далее PROCEDURE T;
forward;
PROCEDURE E;
BEGIN
T;
while not((x[i]='#') or (x[i]=')')) do
if x[i]='+' then begin i:=i+1;T;end
else if x[i]='-' then begin i:=i+1;T;end
else begin ERROR(1); flag:=false; end;
END;
//процедура T с вызовом подпрограммы F, описанную далее PROCEDURE F;
forward;
PROCEDURE T;
BEGIN
F;
while not((x[i]='#') or (x[i]=')') or (x[i]='+') or (x[i]='-')) do
begin
if x[i]='*' then begin i:=i+1;F;end
else if x[i]='/' then begin i:=i+1;F;end
else begin ERROR(1); flag:=false; end;
end;
END;
//процедура F
PROCEDURE F;
BEGIN
if x[i]='I' then i:=i+1
else if x[i]='(' then begin
i:=i+1;
E;
if x[i]=')' then i:=i+1
else begin ERROR(3); flag:=false; end;
end
else begin ERROR(2); flag:=false; end;
END;
//работа с исходным файлом и завершение с выводом
BEGIN
flag:=true;
assign (fff,'original.txt');
reset (fff);
read (fff,x);
i:=1;
E;
if flag=true then
writeln ('correct line');
close (fff);
END.
Выполнение
Пример №1:
(((((I)))))#
correct line
Пример №2:
I*I/(I+I-I+I)#
correct line
Пример №3:
I*I/(I+I-I+I#
expected closing parenthesis...
Пример №4:
A+I#
invalid character!
Пример №4:
I+I+I+I+I
expected end of file....
Документ
Категория
Рефераты
Просмотров
12
Размер файла
27 Кб
Теги
1/--страниц
Пожаловаться на содержимое документа