Лабораторная работа 5. Синтаксический анализ. Восходящий разбор. Метод расширенного предшествования

Цель работы

Изучение метода расширенного предшествования для проектирования синтаксического анализатора.

Теоретические положения

Практическое применение метода простого предшествования ограничено неоднозначностью отношений предшествования, которые часто встречаются в грамматиках реальных языков программирования. Общего алгоритма приведения грамматики к грамматике предшествования не существует. Известны алгоритмы, позволяющие устранить указанную неоднозначность. К таким алгоритмам, в частности, относится метод стратификации. Но эти алгоритмами обладают недостатками: они, как правило, не гарантируют единственности правых частей правил модифициро ванной грамматики. Модифицированная грамматика значительно расширяется и теряет наглядность. По этой причине предпочтительнее исполь зование методов расширенного предшествования. Ниже рассмотрен метод расширенного предшествования (1, 2)(2, 1). Основная идея метода состоит в следующем.

Идея метода расширенного предшествования состоит в следующем. Пусть между символами S_jи S_j+1 существует неоднозначное отношение, например,

S_j < . S_j+1; S_j. = S_j+1

и требуется определить, какое отношение нужно взять в контексте

... S_jS_j+1S_j+2...

Если справедливо отношение <.и грамматика однозначна, то должно существовать правило, которое начинается символами S_j+1S_j+2..., то есть правило имеет вид:

U:: = S_j+1S_j+2...

Если такого правила не существует, то справедливым будет отношение . =.

Аналогично, если между символами S_j+1 и S_j+2 существуют отношения

S_j+1. =S_j+2; S_j+1 . > S_j+2

и требуется определить, какое отношение взять в контексте

... S_jS_j+1S_j+2,

то есть является ли S_j+1правым концом основы, то справедливым будет . > , если существует правило, которое оканчивается символами S_jS_j+1, то есть правило имеет вид:

U:: =... S_jS_j+1,

в противном случае надо брать другое отношение.

Для выделения правого конца основы заготавливается множество правых троек RT. Символы правых троек обозначим S₁S₂S₃. Эти тройки такие, что S₁S₂являются символами, заканчивающим какое-либо правило, а между символами S₂S₃ имеется неоднозначное отношение:

Тогда при разборе, если символы в приводимой строке S_l-1S_lS_l+1 равны символам одной из троек S₁S₂S₃, то справедливо × отношение . > .

В противном случае используются отношения . = или <..

Для выделения левого конца основы заготавливается множество левых троек LT, включающее тойки S₁'S₂'S₃'. Эти тройки такие, что S₂'S₃' начинают правую часть какого-либо правила, а символ S₁' образует с S₂' конфликтную пару.

Тогда, если

S_k-1S_kS_k+1 = S₁'S₂'S₃',

то необходимо брать отношение предшествования <.. В противном случае берется конфликтное отношение.

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

Составление множеств троек

Множество RT-правые тройки

а) просмотреть матрицу предшествования и найти пару символов S₂S₃, для которых существуют конфликтные отношения, включающие отношение . > ;

б) для каждой пары, выявленной в пункте а), просмотреть столбец S₂ матрицы предшествования и найти все символы S₁, связанные с S₂ отношением . =;

в) посмотреть порождающее правило. Если существует правило, которое заканчивается парой S₁S₂: U:: =... S₁S₂, то тройка S₁S₂S₃ записывается в множество правых троек.

Множество LT-левые тройки

а) просмотреть матрицу предшествования и найти пары символов S₁' и S₂', для которых существуют неоднозначные отношения, включающие отношение <.;

б) для каждой пары, определенной в пункте а), S₁' и S₂' просмотреть строку S₂' и найти все символы, связанные с ним отношением . =;

в) просмотреть все порождающие правила, и если существует правило, которое начинается символами S₂'S₃', т. е. правило U:: = S₂'S₃'..., то тройку S₁'S₂'S₃' записать в LT.

Пример.

Грамматика

Z:: =E#

E:: = E+T|T

T:: =T*F|F

F:: =(E)|i

Для данного примера неоднозначных отношений . > и . = между символами грамматики не существует, поэтому множество правых троек будет пустым.

Левые тройки: LT={ #E+, (E+, +T*}.

Задания на работу

Варианты заданий такие же как и в лабораторной работе N 4.

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

1) Когда используется метод (1, 2)(2, 1) предшествования?

2) Как составляется таблица левых троек?

3) Как работает распознаватель расширенного предшествования?

4) Когда метод предшествования (1, 2)(2, 1) не устраняет неоднозначности отношений?

Лабораторная работа 6. Генерация объектного кода

Цель работы

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

Теоретические положения

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

Генерация команд выполняется следующим образом. Пусть значение результата текущей операции находится в аккумуляторе. Для упрощения далее рассматривается целочисленная двухбайтовая арифметика компьютера IBM PC\AT и в качестве аккумулятора используется регистр общего назначения AX. Операторы и операнды польской записи просматриваются последовательно слева направо. Каждый раз, когда обнаруживается операнд, в стек заносится а его описание. Когда же встречается операция, то генерируются команды для ее выполнения. При этомв качестве описаний операндов используются два верхних описания встеке, затем эти два описания выталкиваются из стека, а в стек заносится описание результата. Бинарный оператор всегда применяется к двум верхним операндам стека, поэтому если в каком-либо элементестека описано значение, находящееся в аккумуляторе, то перед генерацией команд для бинарной операции необходимо сгенерировать команду, которая запомнит содержимое аккумулятора во временной переменной. Для фиксации значения аккумулятора вводится глобальная переменная АСС типа STRING. Значение переменой АСС во время компиляциисоответствует состоянию аккумулятора во время выполнения программыименно в тот момент, когда выполнится последняя сгенерированнаякоманда. Если АСС содержит строку ' ', аккумулятор свободен, впротивном случае в АСС содержится имя переменной или временного значения, находящегося в аккумуляторе (после того, как сгенерированная команда будет выполнена при работе программы). В элементе стека записывается имя 'АСС', чтобы указать, что значение операнда находится в аккумуляторе. Когда в польской цепочке встречается имя операнда выполняются следующие действия: - если второй элемент стека (следующий за верхним) содержит'АСС', то образовать новую временную переменную Тi, сгенерироватькоманду MOV Ti, AX и занести имя Тi в этот элемент стека; - занести имя операнда из польской цепочки на вершину стека. Таким образом, только в двух верхних элементах стека можетоказаться описание значения, находящегося в аккумуляторе. Чтобы сгенерировать команды (если это необходимо), которыезагружают во время выполнения программы переменную X или Y в аккумулятор, должна быть вызвана процедура GETINACC (X, Y). В этой процедуре используются два параметра, чтобы в случае коммутативнойоперации предотвратить генерацию команд записи операнда в аккумулятор, если он уже там находится. Учитывая то, что переменные X и Yнаходятся в двух верхних элементах стека операндов, они принимаютцелочисленные значения 0 или 1. Сами же имена переменных записаны вполе имени соответствующего элемента стека. Процедура GETINACC() имеет возможность занесения только одного операнда для случая некоммутативной операции. В этом случае врезультате вызова GETINACC(X, 0) должны генерироваться команды сохранения содержимого аккумулятора и занесения X в аккумулятор. Кроме этого процедура GETINACC() формирует команды, которые сохраняют содержимое аккумулятора, если в данный момент аккумулятор не пуст.

Далее приведен пример работы генератора команд объектного кода для программы, записанной на языке PASCAL.

Исходный текст программы на языке PASCAL

f: =a*(a*b+c-c*d)

Польская запись.

f a a b * c + c d * - *: =

Объектный код.

MOV AX, a

MOV BX, b

IMUL BX

ADD AX, c

MOV _t0, AX

MOV AX, c

MOV BX, d

IMUL BX

MOV _t1, AX

MOV AX, _t0

SUB AX, _t1

MOV BX, a

IMUL BX

MOV f, AX

Для формирования сгенерированного кода по правилам АССЕМБЛЕРА IBM PC используются функции codesg() и datasg().

Порядок формирования объектного кода может быть следующим. Вначале вызывается функция codesg(), которая формирует текст, соответствующий начальным директивам определения логического сегмента кода, затем формируются машинные команды, семантически сответствующие исходной программе, а далее вызывается функция datasg() для формирования необходимых команд и директив АССЕМБЛЕРА, завершающих сегмент кода, а также для формирования логических сегментов данных и стека.

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

Построить программу генерации объектного кода для:

- оператора присваивания языка С (тетрады), целочисленные вы

ражения;

- оператора присваивания языка С (тетрады), логические выражения;

- оператора присваивания языка С (триады), целочисленные выражения;

- оператора присваивания языка С (триады), логические выражения;

- оператора присваивания языка С (польская запись), целочисленные выражения;

- оператора присваивания языка С (польская запись), логические выражения;

- оператора цикла FOR языка C;

- оператора цикла WHILE языка С.

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

1) Какие машинные команды можно исключить из объектного кода на этапе генерации?

2) Для чего используется глобальная переменная ACC?

3) Какие отличия формирования объектного кода из разных внутренних форм программы?

4) Каким образом можно сгенерировать объектный код из синтаксического дерева алгебраического выражения?

5) Каким образом формируется логический сегмент кода при генерации если его размер превышает 64К?

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

1. Зубков С.В. Assembler для DOS, Windows и UNIX. - М.: ”Питер”, 2004. – 640 с. (618.3 З-913)

2. Рудаков П.И., ФиногеновК.Г. Язык ассемблера: уроки программирования. – М.: ДИАЛОГ-МИФИ, 2001. -640 с.

3. Сорокина С.И., Тихонов А.Ю. Программирование драйверов и систем безопасности: Учебное пособие. – СПб.: БХВ-Петербург, М.: Издатель Молгачева С.В., 2003. – 256 с.

4. Гульев И.А. Создаем вирус и антивирус. – М.: ДМК, 1999.- 304 с. (683.3 Г 943 )

5. Безопасность в Windows XP. Готовые решения сложных задач защиты компьютеров: Пер. с англ. / Вебер Крис, Бадур Гэри – СПб: ООО " ДиаСофтЮП", 2003, -464 с. (681.3 В26)

6. Грушо А.А., Тимонина Е.Е. Теоретические основы защиты информации. –М.: Издательство Агенства «Яхтсмен», 1996.

7. Жельников В. Криптография от папируса до компьютера. – М.: ABF, 1997.

8. Касперский Е. Компьютерные вирусы: Что это такое и как с ними бороться. – М.: СКПресс, 1998. – 288 с.

9. Данкан Р. Профессиональная работа в MS-DOS: Пер. с англ. – М.: Мир, 1993.-599 с.

10. Юров В., Хорошенко С. Assembler: Учебный курс-СПб: Издательство Питер, 1999. – 672 с.

11. Джордейн Р. Справочник программиста персональных компьютеров IBM PC, XT AT: Пер. с англ. – М.: Финансы и статистика, 1992. 544 с.

12. Фролов А.В., Фролов Г.В. Библиотека системного программиста. Т. 18. MS-DOS для программиста. - М: ДИАЛОГ-МИФИ, 1995. – 256 с.

13. Фролов А.В., Фролов Г.В. Библиотека системного программиста. Т. 19. MS-DOS для программиста. - М: ДИАЛОГ-МИФИ, 1995. – 256 с.

14. Теоретические основы компьютерной безопасности: Учебное пособие для вузов / Девянкин П.Н., Михальский О.О., Правиков Д.И. и др. – М.: Радио и связь, 2000. – 192 с.

15. Программно-аппаратные средства обеспечения информационной безопасности. Защита программ и данных: Учебное пособие для вузов/ Белкин П.Ю., Михальский О.О., Першаков А.С. и др. - М.: Радио и связь, 2000. – 192 с.

16. Программно-аппаратные средства обеспечения информационной безопасности. Защита в операционных системах: Учебное пособие для вузов/ Проскурин В.Г., Крутов С.В., Мацкевич И.В. - М.: Радио и связь, 2000. – 168 с.

17. Романец Ю.В., Тимофеев П.А., Шаньгин В.Ф. Защита информации в компьютерных системах и сетях. – 2–е изд. – М.: Радио и связь, 2001.

18. Завгородний В. И. Комплексная защита информации в компьютерных системах: Учеб. пособие. – М.: Логос; ПБОЮЛ Н.А.Егоров, 2001.

19. Мельников В.В. Защита информации в компьютерных системах. – М.: Финансы и статистика; Электронинформ, 1997.

20. Мельников В.В. Основы теории защиты информации в автоматизированных системах // Вопросы защиты информации. – 2000. – №3.

21. Мельников В.В. «Безопасность информации в автоматизированных системах».–М.: Финансы и статистика, 2003.

22. MSDN. Win32 Software Developer Kit

23. The Microsoft Windows 2000 Driver Development Kit

24. Хелен Кастер. Основы Windows NT и NTFS. Пер. с англ. - М.: Издательский отдел «Русская редакция», 1996.

25. Джеффри Рихтер.Windows для профессионалов: Программирование для Windows 95 и Windows NT 4 на базе Win32 API. Пер. с англ. -М.: Издательский отдел «Русская редакция», 1997.

⇐ Предыдущая 1 23