Задачи по программированию по курсу ЯПиМТ: Методические указания по выполнению лабораторных работ для студентов экономико-математического факультета

Министерство образования Российской Федерации Ульяновский государственный технический университет

Т.Е.Родионова

ЗАДАЧИ ПО ПРОГРАММИРОВАНИЮ ПО КУРСУ ЯП И МТ по специальности 6571 “Прикладная математика” ”

Методические указания по выполнению лабораторных работ

Ульяновск 2001

2

УДК 681.3.06 (076) ББк 22.18я7 Р60 Родионова Т.Е.. Задачи по программированию по курсу ЯПиМТ: Методические указания по выполнению лабораторных работ для студентов экономикоматематического факультета. – Ульяновск: УлГТУ 2001. - 36 с. Методические указания содержат описание четырех лабораторных работ. Описание включает в себя теоретическую справку по рассматриваемой теме и индивидуальные задания для студентов. Рассматриваются вопросы использования в программах на языке программирования Си прерываний и обращений к видеопамяти, а также некоторые методы и средства проектирования и реализации трансляторов. Разработаны на кафедре прикладной математики и информатики. Могут быть использованы для подготовки к выполнению лабораторных и практических заданий по курсу “Языки программирования и методы трансляции”.

Рецензент – доцент кафедры ВТ УлГТУ В.Н. Арефьев Одобрено секцией методических пособий научно-методического совета университета

 Ульяновский государственный технический университет, 2001

3

СОДЕРЖАНИЕ ЛАБОРАТОРНАЯ РАБОТА 1. ПРОГРАММИРОВАНИЕ ПРЯМОГО ОБРАЩЕНИЯ К ОПЕРАТИВНОЙ ПАМЯТИ.

4

1.1. ОПЕРАТИВНАЯ ПАМЯТЬ. СТРУКТУРА АДРЕСНОГО ПРОСТРАНСТВА ОП ......4 1.2. ГЛОБАЛЬНЫЕ ПЕРЕМЕННЫЕ DOS...............................................................................5 1.3. ПРОГРАММИРОВАНИЕ ПРЯМОГО ОБРАЩЕНИЯ К ОП В TC ...............................5 1.4. ВАРИАНТЫ ЗАДАНИЙ .....................................................................................................7

ЛАБОРАТОРНАЯ РАБОТА 2. ПРЕРЫВАНИЯ MS-DOS

11

2.1. ПОНЯТИЕ ПРЕРЫВАНИЯ. ТИПЫ ПРЕРЫВАНИЙ ....................................................11 2.2. ПРЕРЫВАНИЯ СИСТЕМЫ ROM-BIOS........................................................................13 2.3 ИСПОЛЬЗОВАНИЕ ПРЕРЫВАНИЙ BIOS ДЛЯ РАБОТЫ С КЛАВИАТУРОЙ......15 2.4 ПРОГРАММНЫЕ СРЕДСТВА ДЛЯ ОБРАЩЕНИЯ К ПРЕРЫВАНИЯМ...................16 2.5 ВАРИАНТЫ ЗАДАНИЙ ....................................................................................................21

ЛАБОРАТОРНАЯ РАБОТА 3. ИЗУЧЕНИЕ ЭТАПА ЛЕКСИЧЕСКОГО АНАЛИЗА ТРАНСЛЯТОРОВ ЯЗЫКОВ ПРОГРАММИРОВАНИЯ

21

3.1. АРХИТЕКТУРА КОМПИЛЯТОРА .................................................................................21 3.2. ЛЕКСИЧЕСКИЙ АНАЛИЗ...............................................................................................22 3.3. ЗАДАНИЯ К ТЕМЕ ..........................................................................................................24

ЛАБОРАТОРНАЯ РАБОТА 4. ИЗУЧЕНИЕ ЭТАПА СИНТАКСИЧЕСКОГО АНАЛИЗА ТРАНСЛЯТОРОВ ЯЗЫКОВ ПРОГРАММИРОВАНИЯ 26 4.1. СИНТАКСИЧЕСКИЙ АНАЛИЗ ......................................................................................26 4.2. КОНТЕКСТНО-СВОБОДНЫЕ ГРАММАТИКИ ...........................................................26 4.3. СОДЕРЖАНИЕ ЗАДАНИЯ..............................................................................................32 4.4. ВАРИАНТЫ ЗАДАНИЙ ...................................................................................................33

СПИСОК ЛИТЕРАТУРЫ

35

4

ЛАБОРАТОРНАЯ РАБОТА 1. ПРОГРАММИРОВАНИЕ ПРЯМОГО ОБРАЩЕНИЯ К ОПЕРАТИВНОЙ ПАМЯТИ. 1.1. ОПЕРАТИВНАЯ ПАМЯТЬ. СТРУКТУРА АДРЕСНОГО ПРОСТРАНСТВА ОП

Одним из основных элементов компьютера, позволяющим ему нормально функционировать, является память. Внутренняя память компьютера - это место хранения информации, с которой он работает. Внутренняя память компьютера является временным рабочим пространством; в отличие от нее внешняя память, такая как файл на дискете, предназначена для долговременного хранения информации. Информация во внутренней памяти не сохраняется при выключении питания. Память компьютера организована в виде множества ячеек, в которых могут храниться значения; каждая ячейка обозначается адресом. Размеры этих ячеек и, собственно, типы значений, которые могут в них храниться, отличаются у разных компьютеров. Большинство современных компьютеров, и в том числе все персональные компьютеры, используют размер ячейки состоящей из 8 бит, или "байта". Байт позволяет хранить код одной буквы алфавита или одного символа. Так как IBM/PC использует ячейки памяти длиной восемь бит или один байт, в памяти могут храниться значения, которые можно выразить восемью битами. Это значения до двух в восьмой степени или 256. Для удобства манипулирования символьными данными компьютеру необходимо, чтобы коды символов преобразовывались в байтовые величины. Большинство компьютеров, включая IBM/PC, используют код ASCII, американский стандартный код для обмена информации. В коде ASCII числовые значения присваиваются всем обычно используемым символам, таким как буквы алфавита, строчные и заглавные, цифры, знаки пунктуации. Несколько кодов зарезервированы для управления, например, чтобы указать конец строки символов Таблицы стандартных кодов ASCII и расширенных кодов ASCII для IBM/PC можно найти во многих справочниках. Каждая ячейка памяти имеет адрес, который используется для ее нахождения. Адреса - это числа, начиная с нуля для первой ячейки, увеличивающиеся по направлению к последней ячейке памяти. Поскольку адреса - это те же числа, компьютер может использовать арифметические операции для вычисления адресов памяти. Архитектура каждого компьютера накладывает собственные ограничения на величину адресов. Наибольший возможный адрес определяет объем адресного пространства компьютера или то, какой объем памяти он может использовать. Адрес всегда хранится в двух двухбайтовых словах, называемых адресом сегмента и смещения. Сегмент - это участок памяти, имеющий длину 64 кБ и начинающийся с физических адресов (0,16,32,48,..). Смещение указывает, сколько байт от начала сегмента надо пропустить, чтобы добраться до нужного адреса. Фрагмент памяти в 16 байт называется параграфом. Таким образом, сегменты могут пересекаться.

5

Вычисление абсолютного адреса происходит на основе адреса сегмента и адреса смещения. Память компьютера используется для различных целей - часть ее занимает программа, другая часть используется для хранения данных, с которыми в данный момент работает программа. Помимо памяти, для временного хранения данных микропроцессор использует еще и регистры, что существенно ускоряет работу. Микропроцессор имеет четыре шестнадцатиразрядных регистра общего назначения, называемых AX, BX, CX и DX. Каждый из них может быть разделен на два восьмиразрядных регистра, указанием старшей (H-high) или младшей (L-low) части полного (X) регистра. Таким образом, восьмиразрядные регистры называются AH, AL,BH, BL, CH, CL, DH и DL. 1.2. ГЛОБАЛЬНЫЕ ПЕРЕМЕННЫЕ DOS

Некоторые из ячеек памяти, находящиеся в области памяти с адресами от 400 до 500, содержат т.н. глобальные переменные DOS. Информацию из этих ячеек можно получить, используя непосредственное обращение к ним. Адрес видеопамяти в текстовом режиме для цветного графического дисплея равен B800:0000. Размер видеопамяти:80*25*2=4000 байт. Одна строка дисплея описывается 2*80=160 байтами видеопамяти. Каждый символ экрана занимает 2 байта видеопамяти: первый байт хранит значение символа, второй - его атрибут (цвет фона, на котором изображен символ и цвет самого символа). Значение байта-атрибута удобно задавать шестнадцатеричным числом. Формирование байта-атрибута происходит по следующему правилу: Мерцание

7

цвет фона 6 5

4

цвет символа 3 2

1

0

Например, для вывода синих символов на белом фоне без мерцания можно сформировать следующее значение байта-атрибута 0х72h (0х - признак шестнадцатеричного числа). 1.3. ПРОГРАММИРОВАНИЕ ПРЯМОГО ОБРАЩЕНИЯ К ОП В TC

Пример 1: сформировать в переменной vid_mem начальный адрес области видеопамяти. char far *vid_mem; vid_mem = (char far *) 0xB8000000; Пример 2: организовать перемещение на экране курсора, используя глобальные ячейки DOS (адреса ячеек хранящих вертикальную и горизонтальную координаты курсора, даны в примере).

6

#include char far *p_x=(char far *) 0x00000450; char far *p_y=(char far *) 0x00000451; int i; void main(void) { clrscr(); *p_x=5; *p_y=5; for( i=1;i<=10;i++) { cputs("привет"); *p_y=*p_y+1; *p_x=i+5; } getch(); } Пример 3: используя прямое обращение к видеопамяти, вывести произвольную вертикальную строку. #include char far *vid_mem=(char far*)0xB8000000; int i; int x=10,y=10,attr=33; char *str="строка1\0"; char far*v; void main() { clrscr(); v=vid_mem; v+=(x*160)+y*2; for(i=0;*(str+i)!='\0';i++) { *v++=*(str+i); *v++=attr; } }

на экран

7 1.4. ВАРИАНТЫ ЗАДАНИЙ

В заданиях 1-24 вывод на экран осуществлять с помощью прямого обращения к видеопамяти. Библиотечные функции, реализующие вывод на экран (conio.h), к программному файлу не подключать. Содержательную часть задачи реализовать с помощью функции пользователя. Программа должна вызвать данную функцию несколько раз с различным набором аргументов. Вариант 1. Разработать функцию, реализующую горизонтальное меню в верхней строке экрана: вход: массив строк; выход: номер выбранной строки. Замечание 1. Число строк неограниченно. Если строки меню не размещаются на строке экрана, то формируется меню с меньшим числом строк. Остальная часть строк остается за кадром и доступ к ним осуществляется с помощью навигационных клавиш (т.е. осуществляется скроллинг строки). Замечание 2. Разместить строки меню так, чтобы они занимали полную строку экрана. Функция должна реагировать на клавиши: ←, →, Home, end, Enter. Вариант 2. Разработать функцию, реализующую вертикальное меню в центре экрана. вход: массив строк; выход: номер выбранной строки. Замечание 1. Число строк неограниченно. Если строки меню не размещаются экране, то формируется меню с меньшим числом строк. Остальная часть строк остается за кадром и доступ к ним осуществляется с помощью навигационных клавиш. Функция должна реагировать на клавиши: ↑, ↓, Enter, PdDn, PgUp. Вариант 3. Разработать функцию, реализующую запрос одной из альтернатив "ДА - НЕТ" и возвращающую номер выбранной альтернативы. ("ДА" - 1,"НЕТ" - 2"). Запрос организовать в форме вертикального меню в центре экрана с выбором с помощью навигационной клавиатуры. Вариант 4. Разработать функцию, реализующую запрос одной из альтернатив "ДА - НЕТ" и возвращающую номер выбранной альтернативы. ("ДА" - 1,"НЕТ" - 2"). Запрос организовать в форме горизонтального меню в центре экрана с выбором с помощью ввода первой буквы (либо "Д/D/д/d", либо "Н/N/н/n"). Вариант 5. Разработать функцию, входными данными для которой является массив из N строк. Функция должна вывести на экран строки в виде вертикального меню (координаты верхнего левого угла меню фиксированы). Выбор нужной строки осуществить с помощью навигационной клавиатуры. Функция должна возвращать номер выбранной строки. Замечание. Строки меню полностью умещаются на одном экране. Функция должна реагировать на клавиши: ↑, ↓, Enter, home (первая строка), end (последняя строка).

8

Вариант 6. Разработать функцию, организующую вывод в центр экрана "всплывающего" окна до заданных пределов. Процесс "всплытия" должен происходить с замедлением по времени, обеспечивающим наблюдение за ним. После завершения формирования окна вывести в него произвольную строку. Входными данными для процедуры являются предельные размеры окна и строка, выводимая в него. Функция должна (после всплытия окна) реагировать на клавиши: ←, →, ↑, ↓ и обеспечивать передвижение окна по экрану. Вариант 7. Разработать функцию, организующую вывод в центр экрана "выплывающего" из левой границы экрана окна до центра экрана. Процесс "всплытия" должен происходить с замедлением по времени, обеспечивающим наблюдение за ним. После завершения формирования окна вывести в него произвольную строку. Входными данными для функции являются размеры окна и строка, выводимая в него. Функция должна (после всплытия окна) реагировать на клавиши: ←, →, ↑, ↓ и обеспечивать изменение размера окна, enter - "центрирование" окна после изменения его размеров. Вариант 8. Разработать функцию, организующую вывод в заданное место экрана окна заданных размеров. Окно должно "проявляться" из отдельных частей (последовательность "проявления" частей - случайная, размеры частей - произвольны, но процесс "проявления" должен занимать не менее 10 этапов) c замедлением по времени. После нажатия <enter> окно должно также постепенно исчезать. Вариант 9. Разработать функцию, организующую вывод в заданное место экрана окна заданных размеров. Окно должно "проявляться" из отдельных горизонтальных "слоев" ("слои" проявляются в случайном порядке) c замедлением по времени. После нажатия <enter> окно должно также постепенно исчезать в порядке, обратном проявлению. Функция должна (после проявления окна) реагировать на клавиши: ←, →, ↑, ↓ и обеспечивать изменение размера окна. Вариант 10. Разработать функцию, организующую вывод в заданное место экрана окна заданных размеров. Окно должно "проявляться" из отдельных вертикальных "слоев" ("слои" проявляются в случайном порядке) c замедлением по времени. После нажатия <enter> окно должно также постепенно исчезать в порядке, обратном проявлению. Функция должна (после проявления окна) реагировать на клавиши: ←, →, ↑, ↓ и обеспечивать передвижение окна по экрану. Вариант 11. Разработать функцию, организующую вывод в центр экрана окна, “растущего” постепенно от минимального (с размерами 1*1) до заданных пределов. Процесс "роста" должен происходить с замедлением по времени, обеспечивающим наблюдение за ним. После завершения формирования окна вывести в него произвольную строку. Входными данными для функции являются предельные размеры окна и строка, выводимая в него. Функция должна (после формирования окна) реагировать на клавиши: ←, →, ↑, ↓ и обеспечивать передвижение окна по экрану. Вариант 12. Разработать функцию, организующую вывод в заданное место экрана окна заданных размеров. Окно должно "проявляться" из отдельных вертикальных "слоев"

9

("слои" проявляются в случайном порядке) c замедлением по времени. После нажатия <enter> окно должно также постепенно исчезать в порядке, обратном проявлению. Функция должна (после проявления окна) реагировать на клавиши ↑, ↓ и обеспечивать: изменение цвета окна (<стрелка_вверх>) и изменение цвета экрана за пределами окна (<стрелка_вниз>). Вариант 13. Разработать функцию, организующую вывод в центр экрана "выплывающего" из левой границы экрана окна до центра экрана. Процесс "всплытия" должен происходить с замедлением по времени, обеспечивающим наблюдение за ним. После завершения формирования окна вывести в него произвольную строку. Входными данными для функции являются размеры окна и строка, выводимая в него. Функция должна (после всплытия окна) реагировать на клавиши ←, → и обеспечивать изменение цвета: цвета окна ( →) и изменение цвета строки ( ←). Вариант 14. Разработать функцию, входными данными для которой является массив из N строк. Функция должна вывести на экран строки в виде вертикального меню (координаты верхнего левого угла меню фиксированы). Первая буква строк меню должна быть выделена другим цветом. Выбор нужной строки осуществить как с помощью навигационной клавиатуры, так и нажатием первой буквы строки меню. Функция должна возвращать номер выбранной строки. Замечание. Строки меню полностью умещаются на одном экране. Функция должна реагировать на клавиши: ↑, ↓ , Enter, home (первая строка), end (последняя строка). Вариант 15. Разработать функцию, входными данными для которой является массив из N строк. Функция должна вывести на экран строки в виде горизонтального меню (координаты верхнего левого угла меню фиксированы). Первая буква строк меню должна быть выделена другим цветом. Выбор нужной строки осуществить как с помощью навигационной клавиатуры, так и нажатием первой буквы строки меню. Функция должна возвращать номер выбранной строки. Замечание. Строки меню полностью умещаются на одном экране. Функция должна реагировать на клавиши: ←, →, Enter, home (первая строка), end (последняя строка). Вариант 16. Разработать функцию, реализующую запрос одной из альтернатив "ДА - НЕТ" и возвращающую номер выбранной альтернативы. ("ДА" - 1,"НЕТ" - 2"). Запрос организовать в форме горизонтального меню в центре экрана с выбором с помощью ввода первой буквы (либо "Д/д/D/d", либо "Н/н/N/n"). Программа - заглушка должна обратиться к функции и вывести номер выбранной альтернативы. Вариант 17. Разработать функцию, входными данными для которой является массив из 5 строк вида: "F1 - XXX","F2 - XXX",...,"F5 - XXX", где XXX - произвольная комбинация символов. Процедура должна вывести на экран строки в виде горизонтального меню (координаты верхнего левого угла меню фиксированы). Выбор нужной строки осуществить с помощью выбора нужной функциональной клавиши. Изображение функциональной клавиши выполнить цветом, отличным от цвета остальных символов строки. Функция должна возвращать номер выбранной строки.

10

Вариант 18. Разработать функцию, входными данными для которой является массив из 5 строк вида: "F1 - XXX","F2 - XXX",...,"F5 - XXX", где XXX - произвольная комбинация символов. Функция должна вывести на экран строки в виде вертикального меню (координаты верхнего левого угла меню фиксированы). Выбор нужной строки осуществить с помощью выбора нужной функциональной клавиши. Изображение функциональной клавиши выполнить цветом, отличным от цвета остальных символов строки. Функция должна возвращать номер выбранной строки. Вариант 19. Разработать функцию, выводящую в текстовом режиме в центре экрана фигуру в форме лестницы вниз:

Число ступеней и размер лестницы являются входными данными функции. После формирования фигуры программа должна реагировать на клавиши - ← , → и обеспечивать изменение цвета экрана внутри фигуры ( →) и изменение цвета экрана за пределами фигуры ( ←). Вариант 20. Разработать функцию, выводящую в текстовом режиме в центре экрана фигуру в форме лестницы

Число ступеней и размер лестницы являются входными данными функции. После формирования фигуры программа должна реагировать на клавиши HOME и END и обеспечивать изменение цвета экрана внутри фигуры (HOME) и изменение цвета экрана за пределами фигуры (END). Вариант 21. Разработать функцию, выводящую в текстовом режиме в центре экрана фигуру в форме лестницы вниз (см. вариант 19). Число ступеней и размер лестницы являются входными данными функции. После формирования фигуры программа должна реагировать на клавиши ←, → и обеспечивать передвижение по экрану фигуры. Вариант 22. Разработать подпрограмму-функцию, выводящую в текстовом режиме в центре экрана фигуру в форме лестницы (см. вариант 20). Число ступеней и размер лест-

11

ницы являются входными данными функции. После формирования фигуры программа должна реагировать на клавиши HOME и END и обеспечивать передвижение фигуры по экрану: HOME - вверх, END - вниз. Вариант 23. Разработать функцию, выводящую на экран в текстовом режиме в центре экрана фигуру (см. вариант 20). Число ступеней и размер лестницы являются входными данными функции. После формирования фигуры программа должна реагировать на клавиши PgUp и PgDn и обеспечивать передвижение фигуры по экрану: PgUp - вверх, PgDn - вниз. Вариант 24. Разработать функцию, выводящую на экран в текстовом режиме в центре экрана замкнутую фигуру в форме лестницы вверх. Число ступеней и размер фигуры являются входными данными функции. После формирования фигуры программа должна реагировать на клавиши ←, → и обеспечивать передвижение фигуры по экрану. ЛАБОРАТОРНАЯ РАБОТА 2. ПРЕРЫВАНИЯ MS-DOS 2.1. ПОНЯТИЕ ПРЕРЫВАНИЯ. ТИПЫ ПРЕРЫВАНИЙ

Компьютер должен обладать способностью реагировать на события, происходящие вне его микропроцессора, например воспринимать информацию, вводимую с клавиатуры. Существует два способа организации такой реакции. Один способ состоит в постоянном ожидании события. Такой способ называется "сканированием" или "опросом", и такой опрос может занимать большую часть времени компьютера. Другой способ позволяет компьютеру спокойно выполнять свою работу, пока не произойдет событие, требующее его внимания. Такой подход называется использованием "прерываний". Использование прерываний позволяет наиболее эффективно организовать работу компьютера, поскольку время центрального процессора не расходуется вхолостую на ожидание. Прерывание - это кратковременное приостановка текущей процедуры программы, позволяющая выполнить другую процедуру. После завершения прерывания прерванная программа продолжает выполняться так, как будто бы ничего не происходило. Эти две процедуры могут быть несвязанными - и прерывание не окажет никакого воздействия на прерванную процедуру. Они могут быть взаимозависимы - прерванная программа может быть модифицирована процедурой обработки прерывания. Прерывание может быть вызвано внешним по отношению к выполняемой программе событием или в результате действий самой программы. Прерывание может быть вызвано аппаратно или командой из программы. Механизм прерывания работает следующим образом: каждому из основных типов прерываний присвоен свой номер. Например, прерывание таймера имеет номер 8, гибкие диски, используют номер 14. В самом начале оперативной памяти IBM/PC хранится таблица с адресами программ, которые должны вызываться при возникновении различных прерываний. Эти адреса иногда называются векторами прерываний. Прерывание с номером 0 имеет вектор, хранящийся в ячейке с нулевым адресом, прерывание 1 имеет свой вектор в ячейке 4 и так далее. Когда происходит прерывание номер "X", вектор,

12

хранящийся по адресу 4*X, загружается в регистры адреса программы, т.е., регистры CS и IP, и компьютер начинает выполнять программу обслуживания прерывания, которая размещается по этому адресу. Когда обработка прерывания заканчивается, программа обработки возвращает управление программе, которая выполнялась в момент возникновения прерывания, с помощью специальной команды IRET или "возврат из прерывания". Чтобы такой возврат мог быть выполнен, необходимо сохранить в стеке текущие адреса программы до загрузки в регистры CS и IP вектора прерывания. В компьютере PC имеется 256 различных прерываний, с номерами от 0 до 0хff. Для хранения их адресов зарезервирована память с адресами от 0 до 0х400. Некоторые из прерываний определены для использования процессором. Например, прерывание 0 возникает при делении на 0. Другие определены для вызова функций BIOS, третьи - для использования ДОС. Иногда бывает необходимо, чтобы работа процессора не прерывалась, например, при выполнении какой-либо критической операции. Для этого у микропроцессора имеется специальная команда, которая позволяет отложить обслуживание прерываний, запоминая их, и парная ей команда, восстанавливающая нормальный режим обслуживания прерываний. Когда прерывания запрещаются, запрос прерываний не теряется, он запоминается и будет обслуживаться, как только будут разрешены прерывания. Обычно прерывания не запрещаются на сколько-нибудь продолжительное время. Прерывания допустимо запрещать лишь на очень короткие промежутки времени, необходимые для выполнения некоторых внутренних операций процессора, состоящих из небольшого числа команд. Типичным примером таких операций, которые не могут быть прерваны на полпути, может служить загрузка нового набора значений в регистры сегментов. Поскольку эти регистры необходимы для правильной работы любой программы, нарушение согласованности загрузки в них значений может привести к полной неразберихе, поэтому необходимо запретить прерывания на время загрузки в них новых адресов. Существуют три типа прерываний, которые получили названия аппаратных, логических и программных. Между ними нет принципиальной разницы, но использование разделяет их на три отдельных категории. Аппаратные прерывания вырабатываются устройствами, требующими внимания процессора. В IBM/PC таких прерываний несколько. Во-первых, имеется так называемое немаскируемое прерывание, используемое для сообщения об отказе питания, оно имеет номер 2. Далее, прерывание 8 используется таймером, номер 9 - клавиатурой и 14 - контролером гибких дисков. Имеется также семь зарезервированных номеров прерываний, 6, 7, с 10 по 13 и 15, которые могут быть использованы в дальнейшем, если возникнет необходимость в дополнительных аппаратных прерываниях. Два из этих семи прерываний уже нашли свое назначение, прерывание 12 зарезервировано для адаптера связи, а прерывание 15 - для интерфейса устройства печати. Логические прерывания формируются самим процессором, когда он встречает какое-либо необычное условие. Таких прерываний предусмотрено четыре. Прерывание 0

13

возникает при попытке деления на ноль. Прерывание 1 используется для управления пошаговым режимом работы микропроцессора, при котором команды выполняются по одной. Это прерывание выставляется отладчиками для пошагового выполнения программ. Прерывание 3 вырабатывается командой установки "контрольных точек", которая также используется при отладке. Прерывание 4 формируется при возникновении условия переполнения, например, если результат арифметической операции не помещается в регистр. Таким образом, четыре логических прерывания распадаются на две пары: одна для арифметических операций (деление на ноль и переполнение) и вторая для отладки программ (шаговый режим и контрольные точки). Программы прерывания вызываются как процедуры другими программами. Для вызова процедуры программа должна знать ее адрес, а вызываемая процедура может не знать адреса вызывающей программы, поскольку механизм вызова автоматически генерирует адрес возврата, который будет использован вызываемой программой после завершения ее выполнения. Программные прерывания обеспечивают такую возможность путем выработки прерывания самой программой. Например, если программе необходимо вычислить время дня, ей совершенно не требуется знать адрес программы подсчета времени - достаточно знать только, что программа подсчета времени дня запускается программным прерыванием 26. Программные прерывания используются для вызова всех служебных функций, представляемых обычным пользователям. Эти функции включают все процедуры системы BIOS и ПЗУ и служебные процедуры ДОС. 2.2. ПРЕРЫВАНИЯ СИСТЕМЫ ROM-BIOS.

BIOS (Basic Input/Output System - базовая система ввода/вывода) расположена в ROM (read-only memory - постоянное запоминающее устройство - ПЗУ) и частично в файле, который загружается при загрузке компьютера (загружаемый BIOS). Доступными для пользователя является область памяти ROM_BIOS. Существует всего 12 прерываний ROM-BIOS, распадающихся на 5 групп: шесть из двенадцати прерываний обслуживают определенные периферийные устройства, два дают отчет об оборудовании компьютера, одно работает с часами и календарем, одно выполняет операции по печати экрана и два прерывания переводят компьютер в совершенно иное состояние, запуская ROM-BIOS и системную программу начального запуска. Как мы в дальнейшем увидим, большинство прерываний относятся к группе служебных подфункций, которые выполняют большую часть работы. Например, прерывание 16 (16ричное 10), связанное с выдачей изображения, имеет 16 подфункций, выполняющих все от установки режима изображения до изменения размеров курсора. Подфункция вызывается с помощью обращения к прерыванию, управляющему ею, и задания в регистре АН номер подфункции. Как правило, если подпрограмма-прерывание возвращает какой-либо простой результат, то этот результат остается в регистре АХ; это применимо как к BIOS, так и к языкам программирования.

14 Обработка изображений реализована прерыванием с номером 16 или 10h. Это многофункциональное прерывание. Каждая функция этого прерывания имеет свой номер, по которому она может быть вызвана. Номер функции при вызове прерывания заносится в регистр AH. Таблица 2.1. Служебные функции выдачи изображения

Номер функции 10 с.с. 16 с.с. 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 A 11 B 12 C 13 D 14 E 15 F 19 13

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

Пpавила вызова этих функций приведены в следующих таблицах. Таблица 2.2. Регистры, используемые для установки позиции курсора с помощью служебной функции 2 Номер функции АН = 2

Параметры

DH = номер строки DL = номер колонки ВН = номер страницы (для графических режимов устанавливается в 0)

15

Таблица 2.3. Регистры, используемые для чтения положения служебной функции 3 Номер функции АН = 3

курсора с помощью

Параметры

DH = номер строки DL = номер колонки ВН = номер страницы (для графических режимов устанавливается в 0) СН = начальная строка растра для курсора CL = конечная строка растра для курсора

Таблица 2.4. Регистры, используемые для записи символа и атрибута текста с помощью служебной функции 9 Номер функции АН = 9

Параметры

AL = записываемый на экран символ ASCII BL = записываемый на экран атрибут символа ВН = номер активной страницы дисплея (в графических режимах не нужен) СХ = число выводов символа с атрибутом

Таблица 2.5. Регистры, используемые для записи символа с помощью служебной функции 10 Номер функции АН = 10

Параметры

AL = записываемый на экран символ ASCII BL = атрибут цвета для графических режимов ВН = номер активной страницы дисплея (в графических режимах не нужен) СХ = число записей символа

2.3 ИСПОЛЬЗОВАНИЕ ПРЕРЫВАНИЙ BIOS ДЛЯ РАБОТЫ С КЛАВИАТУРОЙ

Функции для работы с клавиатурой вызываются с помощью прерывания 22(16). Этих функций всего три; они имеют номера от 0 до 2. Как и для всех других функций ROM-BIOS, при вызове функции номер для работы с клавиатурой задается в регистре АН. Процедура 0 возвращает очередной набранный на клавиатуре символ. Если символ уже находится в буфере ROM-BIOS, то он возвращается немедленно. В противном слу-

16

чае процедура ожидает, пока он не будет набран. Каждый символ клавиатуры возвращается в виде пары байтов, называемых главным и вспомогательным байтами. Главный байт, возвращаемый в AL, равен либо 0 для специальных символов, соответствующих, например, функциональным клавишам, либо коду ASCII для обычных ASCII-символов. Вспомогательный байт, возвращаемый в АН, представляет собой либо идентификатор специального символа, либо скэн-код стандартной клавиатуры PC для ASCII-символов (см табл.2.17). Таблица 2.6. Три служебных функции ROM-BIOS доступа к клавиатуре

Функция 0 1 2

Описание

Прочитать с клавиатуры следующий символ Получить ответ о готовности символа Получить состояние клавиши переключения регистров

Если при вызове процедуры 0 в буфере клавиатуры нет ни одного символа, то процедура ждет, пока он не появится, что, естественно, приостанавливает программу. Следующая рассматриваемая нами процедура, позволяет программе проверять ввод с клавиатуры, не приостанавливая своего исполнения. В противоположность тому, что излагается в некоторых версиях технического руководства IBM, процедуры 0 и 1 можно использовать для ввода как обычных ASCII-символов, так и специальных символов, отвечающих, например, функциональным клавишам. 2.4 ПРОГРАММНЫЕ СРЕДСТВА ДЛЯ ОБРАЩЕНИЯ К ПРЕРЫВАНИЯМ

Для описания регистров, используемых при обращении к прерываниям, в пользовательской ТС-программе в библиотеке DOS.H создан специальный тип REGS. struct WORDREGS { unsigned int ax,bx,cx,dx,si,di,cslag,flags; } struct BYTEREGS { unsingred char al,ah,bl,bh,cl,ch,dl,dh; } union REGS{ struct WORDREGS x; struct BYTEREGS h; } В этом случае в пользовательских программах для применения прерываний нужно описать переменную с указанным типом данных. Описатель UNION означает наложение памяти при хранении переменных, перечисленных в различных списках шаблона. Это наложение можно изобразить следующей схемой:

17

0 1

AX AL

AH

BX BL

BH

Таким образом, каждый байт двухбайтного регистра, например AX, имеет свое имя и доступен для самостоятельного обращения. Пример обращения к полям регистровой переменной r: r.x.ax=5; r.h.ah=2; Замечание. ТС позволяет обращение к регистрам без предварительного описания соответствующих переменных. Имена таких регистров необходимо записывать большими буквами и предварять символом подчеркивания.

Например, _AX=5; _Ah=2; Для обращения к прерыванию в TC (библиотека Dos.h) существует несколько функций. Рассмотрим их синтаксис. 1) void geninterrupt(int intr_num) Макрокоманда geninterrupt вызывает программное прерывание, номер которого задан параметром intr_num. Состояние всех регистров после вызова прерывания зависит от конкретного прерывания. Пример 1: Вывод символа * в позицию 80,25. #include #include <dos.h> void writechar(char ch); /* прототип функции */ int main(void) { clrscr(); gotoxy(80,25); writechar('*'); getch(); return 0; } /* выводится символ в текущую позицию курсора */ /* с использованием видео BIOS для того, чтобы избежать*/

18

/* прокрутки экрана при выводе в позицию (80,25)

*/

void writechar(char ch) { struct text_info ti; /* шаблон text_info описан в conio.h*/ gettextinfo(&ti); /* захватить текущие установки текста */ _AH = 9; /* прерывание 0х10, подфункция 9 */ _AL = ch; /* выводимый символ */ _BH = 0; /* видео-страница */ _BL = ti.attribute;/* видео-атрибут */ _CX = 1; /* коэффициент повторения */ geninterrupt(0x10);/* вывод символа */ } 2) int int86(int intno,union REGS *inregs, union REGS *outregs); Функция int86 вызывает программное прерывание процессора 8086, номер прерывания указан в аргументе intno. Перед выполнением программного прерывания функция копирует содержимое регистров из inregs в сами регистры. После возврата из прерывания функция копирует текущие значения регистров в outregs. Если установлен флаг переноса, то это значит, что произошла ошибка. Отметим, что inregs может указывать на ту же структуру, что и outregs.

Функция int86 возвращает значение регистра AX после за-

вершения программного прерывания. Если флаг переноса установлен (outregs -> x.cflag != 0), то есть произошла ошибка, то данная функция присваивает глобальной переменной _doserrno код ошибки. Пример 2: Вывод слова “Привет”.

#include <stdio.h> #include #include <dos.h> #define VIDEO 0x10 void movetoxy(int x, int y) { union REGS regs; regs.h.ah = 2; /* устанавливает позицию курсора */ regs.h.dh = y; regs.h.dl = x; regs.h.bh = 0; /* видео страница 0 */ int86(VIDEO, ®s, ®s); } int main(void)

19

{ clrscr(); movetoxy(35, 10); printf("Привет\n"); return 0; } Рассмотрим еще несколько примеров вызова прерываний. Пример 3: Установить курсор в положение (14,1) на экране дисплея. #include <dos.h> void main(void) { int x,y; union REGS r; r.h.ah=2; r.h.dl=1; r.h.dh=14; r.h.bh=0; int86 (0x10,&r,&r); } Пример 4: Прочитать символ с экрана, расположенный под курсором. Алгоритм реализован с помощью пользовательской функции.

void readchar(x,attr) char *x,*attr; { union REGS r; r.h.ah=8; r.h.bh=0; int86 (0x10,&r,&r); *attr=r.h.ah; *x=r.h.al; }

Пример 5: Вывести символ 'a' на экран на место, указанное курсором. Алгоритм реализован с помощью пользовательской функции. writechar(x,attr) int x, attr;

20

{ union REGS r; r.h.ah=9; r.h.bh=0; r.h.dl=x; r.h.bl=attr; r.x.cx=1; int86 (0x10,&r,&r); } Пример 6: Очистить экран. #include <dos.h> void main(void) { r.h.ah=6; r.h.al=0; r.h.bh=0x7; r.h.cx=0; r.h.cl=0; r.h.dh=24; r.h.dl=79; int86 (ox10,&r,&r); } Пример 7: Составить функцию вывода строки в центре экрана, красными буквами на зеленом фоне с мерцанием, вертикально.

main() { char buffer[]="строка1\0"; int x,y,attr; char *buf=buffer; attr=4+16*2+127; x=10;y=10; do while (*buf!='\0') { goto_xy(x,y); writechar(*buf,attr); buf++; y++; } } Пример 8: Ввести символ с клавиатуры.

21 Фрагмент программы c использованием функции getch() из библиотеки Conio.h.

char c; c=getch(); if(c==0) getch(); ................. Фрагмент программы c использованием прерывания 16h

char c; union REGS r; r.h.ah:=1; intr(0x16,&r,&r); if (r.h.al==0) c=r.h.ah; else c=r.h.al;

2.5 ВАРИАНТЫ ЗАДАНИЙ Решить задачи, приведенные в конце главы 1, с использованием прерываний ROM-BIOS. Библиотеки Crt и Conio.h к программному файлу не присоединять.

ЛАБОРАТОРНАЯ РАБОТА 3. ИЗУЧЕНИЕ ЭТАПА ЛЕКСИЧЕСКОГО АНАЛИЗА ТРАНСЛЯТОРОВ ЯЗЫКОВ ПРОГРАММИРОВАНИЯ Цель работы: Изучить методы построения лексических сканеров на основе конечных автоматов и формальных грамматик. 3.1. АРХИТЕКТУРА КОМПИЛЯТОРА Исходная программа, написанная на некотором языке программирования, есть не что иное, как цепочка знаков. Программа, которая переводит программу с языка высокого уровня в эквивалентную ей объектную называется транслятором. Если происходит перевод в машинные коды, то транслятор называется компилятором. Компилятор превращает эту цепочку знаков в цепочку битов - объектный код. Очень удобно процесс компиляции разделить логически на несколько последовательных этапов:

препроцессирование; лексический анализ; синтаксический анализ; генерация кода; оптимизация программы. Рассмотрим более подробно этап лексического анализа. Программа, которая выполняет этот этап называется лексический анализатор или сканер. Сканер переводит текст исходной программы из последовательности символов или строк в последовательность -

22

лексем. Лексема - минимальный элемент языка программирования. Для заданного языка программирования число типов лексем предполагается конечным. После того как лексемы распознаны, информация о некоторых из них собирается и записывается в одной или нескольких таблицах. Лексический анализ может быть осуществлен за один просмотр исходного текста. После него программа приобретает промежуточную форму. Во время лексического анализа обнаруживаются и отмечаются лексические ошибки. На этой же фазе отбрасываются также и комментарии. 3.2. ЛЕКСИЧЕСКИЙ АНАЛИЗ

При лексическом анализе распознаются три типа лексических единиц: терминальные символы, возможные идентификаторы и литералы. Сначала все лексические единицы сравниваются с элементами таблицы терминальных символов. В случае совпадения помещаются в таблицу стандартных символов. Каждый стандартный символ содержит указатель на таблицу, элементом которой является соответствующая лексическая единица и его индекс внутри этой таблицы. После того как лексическая единица классифицирована как "возможный идентификатор", опрашивается таблица идентификаторов, если такого в таблице еще нет, то создается новый элемент. Остальная информация в таблицу заносится последующими фазами. Числа, строки символов заключенные в кавычки и другие самоопределенные данные классифицируются как "литералы". Информация о них заносится в таблицу литералов. В отличие от идентификаторов литералы позволяют определить их атрибуты. Рассмотрим пример построения описанных таблиц при компиляции следующей программы:

main() { int a; char * b=".dat"; a=a+2; }

Таблица терминальных символов(TRM). Символ 1 2

; (

Разделитель

Другие

Таблица стандартных символов. Тип

Индекс

TRM TRM

5 2

Строка программы main (

23

3 4 5 6 7 8 9 10 11 12 13 …

) , main int { } = + * char " …

…

…

…

…

…

…

TRM TRM TRM IDN TRM TRM TRM IDN TRM TRM LTR TRM IDN TRM IDN TRM LTR TRM TRM …

3 7 6 1 1 12 11 2 9 13 1 13 1 9 1 10 2 1 8 …

) { int a ; char * b = " .dat " a = a + 2 ; } …

Таблица идентификаторов ( IDN). Таблица литералов (LTR). Имя 1 a 2 b

Атрибуты … …

Литерал .dat 2

Основание 10 c.c.

Формат char int

Точность 4 …

Другие … …

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

24

Номер блока …

Число переменных в блоке …

Указатели на эти идентификаторы …

Лексический сканер должен учитывать области видимости и кодировать их по-разному. 3.3. ЗАДАНИЯ К ТЕМЕ

Содержание задания: Разработать программу лексического сканирования и анализа для заданных языка программирования и типов лексем. Программа должна построить заданные таблицы и на их основе преобразовать анализируемую программу, заменив искомые лексемы на мнемонические имена. Мнемонические имена должны генерироваться так, чтобы любая лексема заменялась уникальным именем, а имя отражало ее тип (например, I1 - первая лексема целого типа). Разработать лексический сканер, реализующий следующие действия: Вариант 1: По аналогии с таблицей идентификаторов построить таблицу используемых в программе на языке Си типов данных. Найденные типы заменить мнемоническими именами. Учитывать типы данных созданные с помощью typedef . Вариант 2: По аналогии с таблицей идентификаторов построить таблицу используемых в программе на языке Паскаль типов данных. Найденные типы заменить мнемоническими именами. Учитывать типы данных, созданные с помощью TYPE . Вариант 3: Построить таблицу используемых в программе на языке Паскаль имен переменных. Найденные типы заменить мнемоническими именами. Учитывать типы данных, созданные с помощью TYPE . Вариант 4: Построить таблицу используемых в программе на языке Си имен переменных. Найденные типы заменить мнемоническими именами. Учитывать типы данных, созданные с помощью typedef . Вариант 5: Построить таблицу литералов, используемых в программе на языке Си. Найденные литералы заменить мнемоническими именами. Вариант 6: Построить таблицу литералов, используемых в программе на языке Паскаль. Найденные литералы заменить мнемоническими именами. Вариант 7: Построить таблицу меток, используемых в программе на языке Си. Найденные метки заменить мнемоническими именами. Вариант 8: Построить таблицу меток, используемых в программе на языке Паскаль. Найденные метки заменить мнемоническими именами. Вариант 9: По аналогии с таблицей идентификаторов построить таблицу операторов, используемых в программе на языке Си. Найденные операторы заменить мнемоническими именами. Вариант 10: По аналогии с таблицей идентификаторов построить таблицу операторов, используемых в программе на языке Паскаль. Найденные операторы заменить мнемоническими именами.

25

Вариант 11: По аналогии с таблицей идентификаторов построить таблицу операций, используемых в программе на языке Си. Найденные операции заменить мнемоническими именами. Вариант 12: По аналогии с таблицей идентификаторов построить таблицу операций, используемых в программе на языке Паскаль. Найденные операции заменить мнемоническими именами. Вариант 13: По аналогии с таблицей идентификаторов построить таблицу пользовательских функций, используемых в программе на языке Си. Найденные функции заменить мнемоническими именами. Вариант 14: По аналогии с таблицей идентификаторов построить таблицу пользовательских функций, используемых в программе на языке Паскаль. Найденные функции заменить мнемоническими именами. Вариант 15: Построить таблицу используемых в программе на языке Си имен переменных с учетом блочной структуры программы. Найденные имена заменить мнемоническими именами. Учитывать типы данных, созданные с помощью typedef . Вариант 16: Построить таблицу используемых в программе на языке Паскаль имен переменных с учетом блочной структуры программы. Найденные имена заменить мнемоническими именами. Учитывать типы данных, созданные с помощью TYPE . Вариант 17: Построить таблицу литералов, используемых в программе на языке Си, с учетом блочной структуры программы. Найденные имена заменить мнемоническими именами. Вариант 18: Построить таблицу литералов, используемых в программе на языке Паскаль, с учетом блочной структуры программы. Найденные литералы заменить мнемоническими именами. Вариант 19: Построить таблицу используемых в программе на языке Си имен переменных с учетом их описаний внутри разных функций. Найденные имена заменить мнемоническими именами. Учитывать типы данных, созданные с помощью typedef . Вариант 20: Построить таблицу используемых в программе на языке Паскаль имен переменных с учетом их описаний внутри разных функций. Найденные имена заменить мнемоническими именами. Учитывать типы данных, созданные с помощью TYPE . Вариант 21: Построить таблицу литералов, используемых в программе на языке Си, с учетом их описаний внутри разных функций. Найденные имена заменить мнемоническими именами. Вариант 22: Построить таблицу литералов, используемых в программе на языке Паскаль с учетом их описаний внутри разных функций. Найденные литералы заменить мнемоническими именами. Вариант 23: По аналогии с таблицей идентификаторов построить таблицу используемых в программе на языке Си типов данных с учетом их описаний внутри разных функций. Найденные типы заменить мнемоническими именами. Учитывать типы данных, созданные с помощью typedef . Вариант 24: По аналогии с таблицей идентификаторов построить таблицу используемых в программе на языке Паскаль типов данных с учетом их описаний внутри разных

26

функций. Найденные типы заменить мнемоническими именами. Учитывать типы данных, созданные с помощью TYPE .

ЛАБОРАТОРНАЯ РАБОТА 4. ИЗУЧЕНИЕ ЭТАПА СИНТАКСИЧЕСКОГО АНАЛИЗА ТРАНСЛЯТОРОВ ЯЗЫКОВ ПРОГРАММИРОВАНИЯ Цель работы: изучить функции синтаксического анализатора, методы построения контекстно-свободных грамматик, построить синтаксический анализатор для заданного фрагмента языка программирования. 4.1. СИНТАКСИЧЕСКИЙ АНАЛИЗ

В процессе синтаксического анализа исследуется цепочка лексем и устанавливается, удовлетворяет ли она структурным условиям языка, явно сформулированным в определении синтаксиса языка. Программа, реализующая этот этап, называется синтаксическим анализатором, или парсером. Последовательность лексем рассматривается как предложения контекстно-свободного языка. На этом же этапе выявляются синтаксические ошибки. Функции парсера - распознать основные конструкции языка и вызвать соответствующие программы интерпретации, которые будут генерировать промежуточную форму для этих конструкций. В качестве источника входной информации используется таблица стандартных символов. Синтаксические правила исходного языка (редукции) содержатся в таблице редукций. Алгоритм синтаксического анализа следующий: стек, содержащий таблицу стандартных символов, сравнивается со стеком, содержащим таблицу редукций. Если сравнение успешное – вызывается программа интерпретации, и верхушка стека изменяется. Во время фазы интерпретации дополняется таблица идентификаторов. Формально результатом этого этапа является дерево вывода, однако оно обычно не строится явно – для дальнейших этапов компилятора достаточно последовательности примененных при разборе правил. 4.2. КОНТЕКСТНО-СВОБОДНЫЕ ГРАММАТИКИ Контекстно-свободные грамматики играют главную роль при формальном описании и изучении синтаксиса языков программирования. Этому способствует то, что, с одной стороны, средствами к-с грамматики удается достаточно полно описать синтаксическую структуру языков программирования, а, с другой стороны, достаточно хорошо разработаны алгоритмы распознавания к-с языков, которые составляют основное содержание блока синтаксического анализатора.

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

27

зывают также распознавателем, так как она распознает только цепочки рассматриваемой грамматики. Если в процессе вывода цепочки правила грамматики применяются только к самому левому нетерминалу, говорят, что получен левый разбор цепочки. Аналогично определяется правый разбор цепочки. Различают два класса алгоритмов разбора контекстно-свободных грамматик: - низходящий; - восходящий. К первому классу относятся те, которые строят деревья выводов, начиная с корня и вершин, соответствующих наиболее крупным синтаксическим единицам. В этом случае входная цепочка просматривается многократно. Этот класс алгоритмов наиболее универсален, к нему относятся LL-грамматики. Одним из широко известных и легко реализуемых детерминированных методов разбора сверху – вниз является рекурсивный спуск. Такой анализатор содержит по одной рекурсивной процедуре для каждого нетерминала. Каждая такая процедура осуществляет разбор фраз, выводимых из нетерминала. Процедура сообщает, с какого места данной программы следует начать поиск фразы, выводимой из рассматриваемого нетерминала. Процедура сравнивает программу в указанном месте с правыми частями правил для нетерминала и вызывает по мере необходимости другие процедуры. Большое количество контекстно-свободных языков можно описать с помощью LL(k) – грамматики, по которой можно построить детерминированный синтаксический анализатор, работающий по принципу сверху – вниз. Две буквы L означают, что строки разбираются слева направо и используются левые выводы. Цифра k означает количество предварительно просмотренных символов. Пример 1: Рассмотрим LL(1) - грамматику: (1) (2) (3) (4)

S S A A

→ → → →

aAS b a bSA

Работой алгоритма разбора руководит управляющая таблица, в которой содержатся:

-

правая часть применяемого правила; маркер выброса символа из стека; маркер допуска цепочки символов; маркер ошибки. Столбцы управляющей таблицы озаглавливаются терминалами данной грамматики с учетом пустой

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

28

S A a b $

a aAS a Выброс Ошибка Ошибка

b b bSA Ошибка Выброс Ошибка

E Ошибка Ошибка Ошибка Ошибка Допуск

С помощью этой таблицы проанализируем входную цепочку a b b a b . В стеке находится маркер конца стека и начальный символ S. Таблица разбора цепочки имеет вид: Входная цепочка abbab abbab bbab bbab bab bab ab ab b b e

Содержимое стека S$ aAS$ AS$ dSAS$ SAS$ bAS$ AS$ aS$ S$ b$ $

Применяемое правило 1 1 1,4 1,4 1,4,2 1,4,2 1,4,2,3 1,4,2,3 1,4,2,3,2 1,4,2,3,2

Действие

Выброс A→ b S A Выброс S→ b Выброс A→ a Выброс S→ b Выброс Допуск

Получаем, что цепочка допущена. Алгоритм анализа входной цепочки следующий: на каждом шаге определяется аванцепочка ( это цепочка из k символов впереди) и верхний символ стека. По этим данным определяется элемент управляющей матрицы. Возможны следующие варианты действий: верхний символ магазина заменяется цепочкой (применение правой части правила) и к списку применяемых правил добавляется новый номер правила; верхний символ стека совпадает с текущим входным символом, следовательно, он выбрасывается из магазина; входная цепочка пуста и стек пуст, то работа прекращается, и цепочка считается допущенной; при возникновении ошибки разбор прекращается, и выдается сообщение об ошибки. Ко второму классу относятся распознаватели, которые, читая входную цепочку строят ее дерево вывода начиная с вершин, соответствующих наиболее мелким конструкциям, и кончая корнем. В этом случае детерминированный разбор реализуется в терминах “сдвиг” и “свертка”. Сдвиг – это перенос символа из

29 входной цепочки в магазин(стек), а свертка – применение к вершине магазина какого-либо правила грамматики. Проблема в этом случае состоит в выборе между сдвигом и сверткой и в выборе правила для свертки. LR-грамматика и грамматики предшествования, наиболее часто используемые из грамматик восходящего разбора. LR(k) – грамматикой называется грамматика, при использовании которой в качестве основы для анализатора все конфликты типа сдвиг – свертка и свертка – свертка можно разрешать на основании уже прочитанного текста и фиксированного числа предварительно просматриваемых символов. Буква L показывает, что строки читаются слева направо, а R – что получается правосторонний разбор. На практике k принимает значение 0 или 1. Читая входную цепочку слева направо, анализатор пытается свернуть ее в начальный символ. Шаг алгоритма состоит в считывании цепочки, расположенной в верхней части магазина, чтобы выяснить, образуют ли верхние символы правую часть какого-нибудь правила. Если это так, то производится свертка, заменяющая эти символы левой частью того самого правила. Если свертка невозможна, то в магазин переносится следующий входной символ и процесс продолжается. Рассмотрим пример LR(0) – грамматики. При разборе строки LR(0) языка аванцепочка не используется. Просмотренные символы правила, расположенные левее текущей позиции (обозначается “_”) называют активным префиксом. (1) S → aSS (2) S → b При рассмотрении LR – грамматик используют “пополненные грамматики”. Добавляем новый начальный символ и получаем следующую грамматику: (1) S′ → S (2) S → aSS (3) S → b

Выпишем для пополненной грамматики множества ситуаций, допустимых для различных активных префиксов. 0 V(e)

[S′ → _S], [S → _aSS], [S → _b]

1 V(a)

[S → a_SS], [S → _aSS], [S → _b]

2 V(b)

[S → b_]

3 V(S)

[S′ → S_]

4 V(aS)

[S → aS_S], [S → _aSS], [S → _b]

5 V(aSS) [S → aSS_] Если текущая позиция стоит перед S , то во множество ситуаций входят все ситуации с правилами для S. Если во множестве ситуаций правила не закончены, то дальнейшее действие – сдвиг. После сдвига в состоянии 1 возможны следующие активные префиксы: aa, aS,ab. Когда правило закончено ( состоянии 2 и 5), необходима свертка. Состояние 3 говорит о получении начального символа, следовательно, разбор закон-

30 чен. Множество ситуаций конечно, так как получаемые в дальнейшем с помощью сдвига активные префиксы будут повторять уже описанные ситуации. Построенное множество ситуаций называется канонической LR(0) –системой. В ней нет конфликтов типа сдвиг-свертка и свертка-свертка. По данным состояниям можно осуществлять разбор предложений языка и ,следовательно, грамматика обладает свойством LR(0). Составим управляющую таблицу для LR(0) разбора. Количество строк в таблице равно числу состояний, количество столбцов – число терминалов и нетерминалов в грамматике плюс три. Первый столбец – номер состояния, далее столбец с активным префиксом, затем столбец действия по данному состоянию. Далее следует несколько столбцов для задания переходов по символам правил. Для вышеуказанного примера таблица имеет следующий вид: Префикс

Действие

Переход a

b

S

0

e

сдвиг

1

2

3

1

a

сдвиг

1

2

4

2

b

свертка (1)

r

r

r

3

S

допуск

r

r

r

4

aS

сдвиг

1

2

5

5

aSS

свертка (2)

r

r

r

В начале работы в стеке содержится фиктивный элемент с состоянием V(0). В процессе работы по текущему состоянию (вершине стека) выбирается действие. Если действие “сдвиг”, то очередной символ из входной строки помещается в стек. По текущему состоянию и этому символу вычисляется новое состояние, которое записывается на вершину стека. Если действие “свертка”, то из стека извлекается нужное количество символов. По состоянию на новой вершине стека и полученному при свертке нетерминалу вычисляется новое состояние, которое вместе с нетерминалом записывается на вершину стека. Грамматики предшествования являются подклассами LR(k) – грамматик. При разборе данного типа грамматик используется понятие “основа цепочки”. Основа правовыводимой цепочки – это ее любая подцепочка, которая является правой частью некоторого правила, причем после замены ее левой частью этого правила, тоже получается правовыводимая цепочка. Таким образом, если цепочку αβω можно свернуть в цепочку αAω с помощью правила A→β, то β - основа цепочки αβω. Для грамматики предшествования границы основы правовыводимой цепочки можно определить с помощью некоторых отношений между символами, входящими в эту цепочку. Используются три отношения предшествования: •> - конец основы, выполняется между последним символом цепочки β и первым символом цепочки ω; <• - начало основы, выполняется между последним символом цепочки α и первым символом цепочки β; =• - выполняется между смежными символами основы. Итак, основу правовыводимой цепочки грамматики простого предшествования можно выделить, просматривая эту цепочку слева направо до тех пор, пока впервые не встретится отношение конца цепочки. Для нахождения левого конца основы надо возвращаться назад, пока не встретится отношение начала осно-

31 вы. Полученная цепочка и будет искомой основой. Этот процесс продолжается до тех пор, пока входная цепочка не свернется к начальному символу. Грамматика является грамматикой простого предшествования, если она приведенная, не содержит еправил, и для любой пары символов выполняется не более одного отношения предшествования. Рассмотрим грамматику, состоящую из правил: S→aSSbc В качестве начала и конца цепочки используются маркеры # или $. Найдем отношения предшествования. 1) =• Просматриваем правые части правил, получаем a =• S, S =• S, S =• b. 2) <•

Ищем в правых частях правил пары смежных символов ХС, таких что Х находится в отноше-

нии <• с самым левым символом цепочки, выводимой из С. Рассмотрим пару aS, получим a <• a, a <• c. Рассмотрим пару SS, получим S <• a,

S <• c. Рассмот-

рим начальный маркер, получим $ <• a, $ <• c. 3) •> Ищем в правых частях правил пары смежных символов СХ. Затем ищем символы Y, которые могут оказаться на правом конце цепочки, выводимой из С за один или более шагов, и терминалы d, которые могут находиться в начале цепочки, выводимой из Х за нуль и более шагов. В нашем случае это пары: SS: b •> a, b •> c, c •> a, c •> c; Sb: b •> b, c •> b; конечный маркер: b •> $, c •> $. Построим таблицу для этих отношений. Это квадратная матрица, строки и столбцы которой помечены терминалами , нетерминалами и маркером (начала или конца цепочки). Пустая ячейка таблицы соответствует состоянию ошибки. S

a

b

c

S

=•

<•

=•

<•

a

=•

<•

$

<•

b

•>

•>

•>

•>

c

•>

•>

•>

•>

$

<•

<•

Так как в одной ячейки управляющей таблицы записано не более одного отношения предшествования, то это грамматика предшествования, кроме того правые части всех правил различны, следовательно это грамматика простого предшествования. Построение алгоритма разбора. Символ $ будем использовать в качестве маркера для стека и правого концевого маркера входной цепочки. Действие f(x,a) зависит от верхнего символа стека и самого левого символа необработанной части входной цепочки. f(x,a) – перенос (сдвиг), если х <• a или х =• а. f(x,a) – свертка, если х •> a. f(x,a) – ошибка в противоположных случаях. f($S$) – допуск цепочки.

32 Функция свертки зависит от верхней части стека, включающей основу и еще одного символа ниже нее. Оставшаяся необработанная часть входной цепочки на свертку не влияет. Грамматика операторного предшествования – это приведенная контекстно-свободная грамматика без е-правил, в которой правые части правил не содержат смежных нетерминалов. Операторная грамматика является грамматикой операторного предшествования, если между любыми двумя терминальными символами выполняется не более одного отношения предшествования. Для грамматик операторного предшествования отношения задаются на множестве терминалов плюс маркер начала (конца), игнорируя нетерминалы. Рассмотрим отношения: a =• b , если есть правило A→…ab… или A→…aBb… a <• b , если есть правило A→…aB и B→b… или B→Cb… a •> b , если есть правило A→…Bb… и B→…a или B→…aC $ <• a , если есть правило S→Ca… или S→a… a •> $ , если есть правило S→…aC или S→…a Пример: рассмотрим грамматику арифметических формул S→S + T | T T→T * E | E E→(S) | a Управляющая таблица имеет следующий вид: (

a

*

+

)

$

)

•>

•>

•>

•>

a

•>

•>

•>

•>

*

<•

<•

•>

•>

•>

•>

+

<•

<•

•>

•>

•>

•>

(

<•

<•

<•

<•

=•

$

<•

<•

<•

<•

Алгоритм разбора цепочки по управляющей таблице аналогичен предыдущему. Отыскивая самую левую основу, распознаватель для грамматики операторного предшествования не обращает внимания на нетерминалы приводимой основы. Нетерминалы могут учитываться только семантическими подпрограммами. Поэтому правила, содержащие только нетерминалы в правых частях, можно не включать в таблицу правил. 4.3. СОДЕРЖАНИЕ ЗАДАНИЯ Сначала необходимо составить грамматику для заданного языка и получить управляющую таблицу. Затем, используя описанные выше алгоритмы разбора, разработать программу синтаксического анализа предложений заданного языка. Программа – распознаватель должна работать в режиме интерпретации одного предложения. Цель программы – идентификация правильных предложений языка и диагностика ошибок.

33 4.4. ВАРИАНТЫ ЗАДАНИЙ Язык арифметических выражений в инфиксной форме с операциями сложения, вычитания, умножения, деления без скобок, с операндами в форме идентификаторов и целых констант. Вариант 1: Язык арифметических выражений в инфиксной форме с операциями сложения, вычитания, умножения, деления со скобками, с операндами в форме идентификаторов и целых констант. Вариант 2: Язык арифметических выражений с операциями языка Си ( +, −, ∗, /, + +, − −, %), без скобок, с операндами в форме идентификаторов и констант (целых, с фиксированной и плавающей запятой). Вариант 3: Язык арифметических выражений с операциями языка Си ( +, −, ∗, /, + +, − −, %), со скобками, с операндами в форме идентификаторов и констант (целых). Вариант 4: Язык арифметических выражений в префиксной форме с операциями сложения, вычитания, умножения, деления без скобок, с операндами в форме идентификаторов и целых констант. Вариант 5: Язык арифметических выражений в постфиксной форме с операциями сложения, вычитания, умножения, деления без скобок, с операндами в форме идентификаторов и целых констант. Вариант 6: Язык арифметических выражений в инфиксной форме с операциями сложения, вычитания, умножения, деления без скобок, с операндами в форме идентификаторов и целых констант и функциональных выражений с несколькими аргументами. Аргумент функционального выражения – идентификатор. Вариант 7: Язык арифметических выражений в инфиксной форме с операциями сложения, вычитания, умножения, деления без скобок, с операндами в форме идентификаторов и целых констант и функциональных выражений с несколькими аргументами. Аргумент функционального выражения – вышеописанное выражение. Вариант 8: Язык логических выражений с операциями .NOT. , .OR. , .AND. , без скобок, с операндами в форме идентификаторов, константами .TRUE. , .FALSE. и операциями отношений в синтаксисе ФОРТРАНа (.GE. , .LE. , .NE. , .EQ. , .GT. , .LT.). Вариант 9: Язык выражений с операциями логики языка Си, со скобками, с операндами в форме идентификаторов, логическими константами, операциями отношений. Вариант 10: Язык выражений с побитовыми операциями логики языка Си, без скобок, с операндами в форме идентификаторов и целыми константами ( в двоичной, восьмеричной, десятичной и шестнадцатеричной формах). Вариант 11: Язык адресных выражений языка Си с операциями ссылок ( &, ∗), без скобок, с операндами в форме идентификаторов и элементов массива. Вариант 12: Язык адресных выражений языка Си с операциями ссылок ( ∗, &, →), со скобками, с операндами в форме идентификаторов. Вариант 13: Язык выражений с побитовыми операциями логики языка Си, со скобками, с операндами в форме идентификаторов и целыми константами ( в двоичной форме). Вариант 14: Язык выражений с операциями логики языка Си, без скобок, с операндами в форме идентификаторов, операциями отношений. Операции отношений включают в себя двухоперандные арифметические выражения с идентификаторами и целыми константами. Вариант 15: Язык арифметических выражений в инфиксной форме с операциями сложения, вычитания, умножения, деления со скобками, с операндами в форме идентификаторов и элементов массива. Вариант 16: Язык функциональных выражений. Каждая функция имеет один аргумент. Аргументами являются идентификаторы, элементы массива и константы.

34 Вариант 17: Язык функциональных выражений с произвольным количеством аргументов и неограниченной вложенностью. Аргументы – идентификаторы: f(g(x,e(y,z))). Вариант 18: Язык арифметических выражений в постфиксной форме с операциями сложения, вычитания, умножения, деления без скобок, с операндами в форме идентификаторов и элементов массива. Вариант 19: Язык арифметических выражений в префиксной форме с операциями сложения, вычитания, умножения, деления без скобок, с операндами в форме идентификаторов и элементов массива. Вариант 20: Язык арифметических выражений с одноместными операциями языка программирования Си (++, --, =, +=, -=, *=, /=, %=), с операндами в форме идентификаторов и элементов массива. Вариант 21: Язык арифметических выражений в инфиксной форме с операциями сложения, вычитания, умножения, деления без скобок, с операндами в форме идентификаторов и элементов массива. Вариант 22: Язык арифметических выражений в инфиксной форме с операциями сложения, вычитания, умножения, деления со скобками, с операндами в форме идентификаторов и элементов массива. Вариант 23: Язык выражений в синтаксисе Си, включающий присваивание, префиксный и постфиксный инкремент и декремент, сложение, вычитание, умножение, деление, с операндами в форме идентификаторов и констант. Вариант 24: Язык выражений в синтаксисе Си, включающий присваивание, префиксный и постфиксный инкремент и декремент, сложение, вычитание, умножение, деление, с операндами в форме идентификаторов и функциональных вызовов. Допустимы вызовы функций с произвольным количеством аргументов в форме идентификаторов.

35

СПИСОК ЛИТЕРАТУРЫ 1.

Грис Д. Конструирование компиляторов для цифровых вычислительных машин: Пер. с англ. – М.:Мир, 1975.

2.

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

3.

Керниган Б., Ритчи Д. Язык программирования Си: Пеp. с англ. - М.: Финансы и статистика, 1985. (Приведены расширения языка/ Авторы: В.А. Кашкарова, Н.Н.Артамоненкова).

4.

Ноpтон П. Пеpсональный компьютеp фиpмы IBM и опеpационная система MS-DOS: Пеp. с англ. М.: Радио и связь, 1992.

5.

Уинеp У. Язык ТУРБО СИ: Пеp. с англ. М.: Миp, 1991.

6.

Язык "СИ" для пpофессионалов/ По матеpиалам книги Г.Шилдта - М.: И.В.К.-СОФТ, 1992.

7.

Хантер Д. Проектирование и конструирование компиляторов. – М.:Финансы и статистика, 1984.

8.

Меркулова Т.А., Ярушкина Н.Г. Программирование

на языках высокого уровня с использованием

прерываний MS-DOS: Учебное пособие для студентов учебных направлений – Ульяновск: УлГТУ, 1997. 9.

Ярушкина Н.Г., Евсеева О.Н. Конструирование трансляторов для языков программирования высокого уровня: Сборник лабораторных работ. – Ульяновск:УлГТУ, 1994.

Учебное издание РОДИОНОВА Татьяна Евгеньевна Задачи по программированию по курсу ЯП и МТ Редактор Н.А.Евдокимова Подписано в печать 20.07.01. Формат 60х84/16. Бумага писчая. Усл. печ. л. 2,09. Уч.- изд. л. 2,00. Тираж 100 экз. Заказ . Ульяновский государственный технический университет. 432027, Ульяновск, Сев. Венец, 32. Типография УлГТУ, 432027, Ульяновск, Сев. Венец, 32.