Работа с типом String (сравнение строк)

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Контрольная работа

Тема:

"Работа с типом String (сравнение строк)"

Воткинск 2010

Введение

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

Преобразования программы выполняется в несколько этапов (фаз), взаимосвязь между которыми отображена на рисунке 1.

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Рисунок 1. Основные этапы (фазы) обработки программы компилятором

1. Лексический анализ

Лексический анализатор представляет собой модуль разбора текста программы. Разбор происходит в зависимости от имеющихся у него в памяти терминальных символов и правилами определения типов данных. Каждый язык имеет свои ограничения по типам данных, допущения и особенности создания (строения) конструкций, применению операторов и т.п.

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

Синтаксический анализ - это процесс, в котором исследуется цепочка лексем и устанавливается, удовлетворяет ли она структурным условиям, явно сформулированным в определении синтаксиса языка.

Синтаксический разбор - это построение дерева грамматического разбора. Методы грамматического разбора разбиваются на два класса восходящие и нисходящие.

Кроме этого, алгоритмы синтаксического (грамматического) разбора делят на синтаксически-ориентированные и синтаксически-неориентированные. Синтаксически-ориентированные алгоритмы являются универсальными для некоторого семейства языков и переход к распознаванию предложений другого языка выполняется путем смены грамматики, т.е. грамматика играет роль некоей «программы» распознавания предложений языка.

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

После того как синтаксис программы проанализирован, последним шагом процесса компиляции является генерация объектного кода. Генерация объектного кода - это перевод компилятором внутреннего представления исходной программы в результирующую объектную программу на языке ассемблера или непосредственно на машинном языке (машинных кодах).

2. Постановка задачи

У нас есть компилятор, который может обрабатывать конструкции на урезанном языке Pascal.

Описание языка:

Основные символы языка - буквы, цифры и специальные символы - составляют его алфавит.

Учебный компилятор распознает только:

* 26 латинских строчных и 26 латинских прописных букв: A..Z, a..z.

* 10 цифр - 0 1 2 3 4 5 6 7 8 9

* знаки операций: + - * / = < > <> <= >=:=

* ограничители:., ` () {}:;

* символ пробела

* служебные (зарезервированные) слова и операторы:

PROGRAM, VAR, BEGIN, INTEGER, STRING, END, READ, WRITE, IF, THEN, ELSE, FOR, TO, DO, WHILE, UNTIL, REPEAT, AND, OR, NOT.

Компилятор может выводить данные на дисплей и получать их от пользователя, корректно обрабатывать цикл со счетчиком (for-to-do), цикл с предусловием (while), цикл с постусловием (repeat-until); также он может работать с целым (Integer) и строковым (String) типом данных, а также с некоторыми логическими операторами. Но компилятор не может работать с метками, а в частности с оператором безусловного перехода GoTo.

Для того, чтобы решить поставленную задачу, мне необходимо выяснить, из каких частей состоит этот компилятор:

Компилятор состоит из трех основных частей:

1. Модуль лексического анализа.

2. Модуль синтаксического и семантического анализов.

3. Модуль генерации кода.

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

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

Распознавание по таблицам происходит следующим образом:

Сканер в процессе анализа текста программы выделяет один из элементов текста (лексему) и сравнивает с каждым зарезервированным словом. Если такой символ найден, то сканер передает синтаксическому анализатору код лексемы и её значение. Например: если сканер находит зарезервированное слово «Program», он передаст синтаксическому анализатору - тип лексемы равной 3 и её значение «Program».

В случае если этот элемент не является зарезервированным словом, проверяется, является ли он идентификатором (первый символ обычно буква, остальные могут быть либо буквой, либо цифрой), если такой определен, то сканер передаст синтаксическому анализатору тип лексемы равной 2 и её имя.

Выходные данные, сформированные сканером, передаются на следующую стадию обработки - синтаксический анализ.

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

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

Генерация объектного кода выполняется после того, как выполнен синтаксический анализ программы и все необходимые действия по подготовке к генерации кода: распределено адресное пространство под функции и переменные, проверено соответствие имен и типов переменных, констант и функций в синтаксических конструкциях исходной программы и т.д.

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

3. Решение задачи

компилятор преобразование программа лексический

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

<сравнение>:= <factor> <условие> <factor>

<условие> := = | <> // для сравнения двух переменных строкового типа.

Я создал следующую процедуры:

{Синтаксический анализ}

procedure CmpStr;

begin

StrExpression;

CodeAssign1 ('bufstr2');

{Если лексема является одним из знаков отношения вызываем соответствующую процедуру}

if (Token = 35) or (Token = 47) then begin

Push; {Процедура генерации кода}

case Token of

35: StrEqual; {Вызов процедуры осуществляющей разбор операций отношения (=)}

47: StrNotEqual; {Вызов процедуры осуществляющей разбор операций отношения (<>)}

else EmitLn (' pop AX');

end;

end;

end;

procedure StrEqual;

begin

Scan; {Запрос лексемы}

StrExpression;

StrSetEqual; {Процедура генерации кода}

end;

procedure StrNotEqual;

begin

Scan; {Запрос лексемы}

StrExpression;

StrSetNEqual; {Процедура генерации кода}

End.

{Генерация кода}

procedure StrSetEqual;

begin

Emitln ('mov SI, 0');

Emitln ('m_'+inttostr(met)+':');

Emitln ('mov DL,_bufstr1 [si]');

Emitln ('cmp DL,_bufstr2 [si]');

Emitln ('jne m_'+inttostr (met+1));

Emitln ('cmp DL, «$» ');

Emitln ('je m_'+inttostr (met+3));

Emitln ('inc si');

Emitln ('cmp si, 255');

Emitln ('jng m_'+inttostr(met));

Emitln ('m_'+inttostr (met+3)+':');

Emitln ('mov AX, 1');

Emitln ('jmp m_'+inttostr (met+2));

Emitln ('m_'+inttostr (met+1)+':');

Emitln ('mov AX, 0');

Emitln ('m_'+inttostr (met+2)+':');

inc (met, 4);

end;

procedure StrSetNEqual;

begin

Emitln ('mov SI, 0');

Emitln ('m_'+inttostr(met)+':');

Emitln ('mov DL,_bufstr1 [si]');

Emitln ('cmp DL,_bufstr2 [si]');

Emitln ('jne m_'+inttostr (met+1));

Emitln ('cmp DL, «$» ');

Emitln ('je m_'+inttostr (met+3));

Emitln ('inc si');

Emitln ('cmp si, 255');

Emitln ('jng m_'+inttostr(met));

Emitln ('m_'+inttostr (met+3)+':');

Emitln ('mov AX, 0');

Emitln ('jmp m_'+inttostr (met+2));

Emitln ('m_'+inttostr (met+1)+':');

Emitln ('mov AX, 1');

Emitln ('m_'+inttostr (met+2)+':');

inc (met, 4);

end;.

4. Описание тестовых примеров

program Primer;

var

{Описание переменных}

S1, S2: String;

begin

write ('Vvedite 1 stroku');

read(S1);

write ('Vvedite 2 stroku');

read(S2);

if S1=S2 then

write ('Stroki ravni')

else

write ('Stroki otlichni');

read(S1);

end.

Проверка работоспособности

Вывод

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

Список источников

1. Бек Л. Введение в системное программирование: Пер. с англ. - М.: Мир, 1988. - 448 с.

2. Юров В. Assembler: Учебник. - СПб. и др.: Питер, 2000. - 622 с.

Размещено на Allbest.ru