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

Министерство образования Российской Федерации Государственное образовательное учреждение высшего профессионального образования СЕВЕРО-ЗАПАДНЫЙ ГОСУДАРСТВЕННЫЙ ЗАОЧНЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ Кафедра компьютерных технологий и программного обеспечения

ТЕОРИЯ ЯЗЫКОВ ПРОГРАММИРОВАНИЯ И МЕТОДЫ ТРАНСЛЯЦИИ

Рабочая программа Методические указания к изучению дисциплины Задание на контрольную работу

Факультет информатики и систем управления Направление и специальность подготовки дипломированного специалиста: 654600 - информатика и вычислительная техника 220100 - вычислительные машины, комплексы, системы и сети

Санкт-Петербург 2003

2

Утверждено редакционно-издательским советом университета УДК 681.3.06 Теория языков программирования и методы трансляции: Рабочая программа, методические указания к изучению дисциплины, задание на контрольную работу. – СПб.: СЗТУ, 2003. - 18 с. Методические указания составлены в соответствии с требованиями государственного образовательного стандарта высшего профессионального образования по направлению подготовки дипломированного специалиста 654600 ( специальность 220100 – «Вычислительные машины, комплексы, системы и сети») для дисциплины специализации (ДС) «Теория языков программирования и методы трансляции». Рабочая программа содержит перечень тем, подлежащих изучению, задание на контрольную работу и вспомогательный материал для ее выполнения. В приложении приведен алгоритм решения задачи лексического анализа, который является основой задания на контрольную работу. Рассмотрено на заседании кафедры компьютерных технологий и программного обеспечения (КТ и ПО) 9.06.2003г., одобрено методической комиссией факультета информатики и систем управления (ФИСУ) 17.11.2003 г.

Рецензенты: кафедра прикладной и компьютерной оптики СПбГИТМО ( О.В. Багдасарова, канд.техн.наук, доц. ); кафедра компьютерных технологий и программного обеспечения (Г.И.Анкудинов, д-р техн. наук, проф.) Составители: М.В. Копейкин, канд.техн.наук, доц.; Н.В. Рачева, доц.; Е.О. Шумова, доц.

© Северо-Западный государственный заочный технический университет, 2003

3

ВВЕДЕНИЕ Развитие современных программных систем (операционных оболочек) базируется на методах проектирования трансляторов и правилах формальных грамматик языков программирования. Курс – ознакомительный, но требующей хороших знаний основ программирования на алгоритмических языках, а также знаний особенностей языков Borland С++, Turbo C, воспринимать алгоритмически Borland Pascal, т.е. уметь читать исходный текст программы. 1. Содержание дисциплины 1.1. Рабочая программа

(объем курса 70 часов) 1.1.1. Введение в теорию языков программирования Определение языка программирования. Назначение. Классификация языков программирования. Словарь ключевых (зарезервированных) слов (символов). 1.1.2. Формальные грамматики Определение и назначение формальной грамматики. Иерархия формальных грамматик. Выбор грамматик для языков программирования. Метаязык. Бэкус-Науровая форма (БНФ). Назначение БНФ. Основные обозначения. Терминальные и нетерминальные символы. Рекурсивный метод построения предложений. Нисходящий и восходящий синтаксический анализ. Грамматики LL(1), и LR(0), LR(1). Особенности LL и LR - анализа. Примеры разбора предложений. 1.1.3. Процесс трансляции Определение транслятора. Этапы, фазы и проходы трансляции. Проектирование современных трансляторов. Интегрированные среды программирования (Integrated Development Environment - IDE). Назначение универсального промежуточного языка.

1.1.4. Этапы трансляции. Генерация кода Лексический анализ – сканер. Определение лексемы. Типы лексем, внешний и внутренний форматы. Синтаксический и семантический

4

анализ. Различные типы промежуточного кода. Оптимизация машиннонезависимого и машинного кодов. 1.1.5. Проектирование языковых интерпретаторов Определение. Особенности проектирования интерпретаторов. Алгебраические выражения. Определение приоритетов операций. Построение анализатора простых выражений Рекурсивно-нисходящий алгоритм разбора выражений. Принципы программной реализации интерпретаторов. Пример построения программного модуля разбора выражений и интерпретатора команд. 1.2. Тематический план лекций для студентов очно-заочной формы обучения

(12 часов) 1. Определение языка программирования………………………… 2 часа 2. Формальные грамматики………………………………………… -“-“ 3. Процесс трансляции……………………………………………… -“-“ 4. Лексический и синтаксический анализ…………………………. -“-“ 5. Семантический анализ……………………………………………. -“-“ 6. Генерация кодов………..………………………………………… -“-“ 1.3. Перечень практических занятий

(8 часов) 1. Создание файла проекта в интегрированной среде Borland С++.

(2 часа) 2. Расширение списка команд Small BASIC. (2 часа) 3. Построение рекурсивных функций на языке С++. (4 часа) 2. Библиографический список Основной: 1. Хантер Р. Основные концепции компиляторов. /Пер. с англ.- М.: Издатель-ский дом “Вильямс”, 2002. 2. Шилдт Г. Теория и практика С++. /Пер. с англ. - СПб.: ВНV - СанктПетербург, 1996. Дополнительный: 3. Ахо А.В., Сети Р., Ульман Д.Д. Компиляторы: принципы, технологии и инструменты. М.: Издательский дом «Вильямс», 2001.

5

4. Кормен Т., Лейзерсон Ч., Ривест Р.. Алгоритмы: построение и анализ. М.: МЦНМО, 2000. 5. Шилдт Г. Самоучитель С++ 3-е изд./ Пер. с англ. – СПб.: BHV-СанктПетербург, 1998. 6. Кнут Д. Искусство пpограммиpования для ЭВМ. - М.: Миp, 1974. 7. Подбельский В.В., Фомин С.С. Программирование на языке Си. М.:Финансы и статистика, 1999. 8. Подбельский В.В. Язык Си++. - М.:Финансы и статистика, 1999. 9. Касаткин А.И., Вальвачев А.Н. От Turbo C к Borland C++. /Под ред. А.И.Касаткина. – Минск: Вышейшая школа, 1992. 10.Березин Б.И., Березин С.Б. Начальный курс С и С++. – М.: ДиалогМИФИ, 1996. 3. Методические указания к изучению дисциплины 3.1. Введение в теорию языков программирования

[1], c. 27-57 Языки программирования. Классификация. Исходный текст программы – формальная запись алгоритма. Алгоритм – преобразование исходных данных в требуемый результат за конечное число шагов. В основе любого языка заложен словарь. Элементами словаря являются слова, которые в теории формальных языков получили название символов. Зарезервированные (ключевые), или служебные слова (символы) пишутся согласно грамматике, выбранной при формировании словаря. Например, такие слова, как: GOTO, CHR, VAR и ряд других аббревиатур хотя и не соответствуют написанию естественного языка, но распространены в языках программирования. Исходный текст программы пишется, исходя из правил, заложенных в основе языка программирования. 3.2. Формальные грамматики

[1], c. 81-171 Определение формальной грамматики можно записать в виде четверки объектов G = ( N, T, P, S ), где N - множество нетерминальных символов, входящих в словарь; T - множество терминальных символов, входящих в словарь; P - множество правил грамматики, или продукций; S - элемент, выделенный из множества нетерминальных символов;

6

N ∩ T = Ø - дополнительное условие: ни один символ не может быть одновременно и терминальным, и нетерминальным. Для грамматики G = ( N, T, P, S ) язык L(G) есть множество всех цепочек из T*, выводимых с помощью S: L(G) = { w ⏐ S*⇒w, w∈T*}. Американский лингвист Хомский предложил четыре типа (класса) языков в зависимости от продукций, т.е. задания правил вывода предложений (конструкций), порождающих свою особую грамматику. Регулярная грамматика (тип 3). Все продукции из Р могут быть следующего вида: А→ВС либо А→С, где А,В∈N, С∈Т. Этот вид грамматики удобен для описания сканера лексического анализатора при проектировании транслятора. Контекстно-свободная грамматика (тип 2). Все продукции из Р могут быть представлены в следующем виде: А→w, где w∈ (N∪Т) и А∈N. Этот тип используется для описания большинства языков программирования. Контекстно-зависимая грамматика (тип 1). Все продукции из Р могут быть представлены в следующем виде: αАβ →αХβ , где А∈N, α,Х,β∈(N ∪Т). В этом варианте длина цепочек не имеет ограничений, т.е. в результате подстановок получаются цепочки неубывающей длины. Грамматика без ограничений (тип 0). В этом случае на правила подстановок не накладываются ограничения. К этому типу относятся все естественные языки. 3.3. Процесс трансляции

[1], c. 11-26 Транслятор - это программа-переводчик, предназначенная для преобразования исходного текста в объектный модуль, доступный для восприятия ЭВМ, т.е. машинный код. Любой транслятор выполняет следующие функции: • анализ исходного текста программы на выявление синтаксических ошибок; • генерацию выходной (рабочей) программы(объектного модуля) на язык команд конкретного процессора (генерация может происходить в два этапа: сначала до уровня команд ассемблера, затем до машинного кода); • распределение памяти для размещения программы в машинных кодах (выделение физических адресов участков памяти для каждого

7

фрагмента программы, для таблиц переменных, констант, массивов и других объектов). При проектировании трансляторов выделяются две системы (два подхода к процессу трансляции): компилирующая и интерпретирующая. Компилирующая система просматривает весь текст от начала до конца и в случае отсутствия синтаксических ошибок преобразует в машинный код. Интерпретирующая, или интерпретатор преобразует текст построчно (по командам) с непосредственным выполнением вне зависимости от последующих конструкций(предложений) языка. Лексический анализатор - это наиболее простая часть компилятора для проектирования. Предложения (конструкции) формируются из лексем. Предложения исходной программы поступают на вход компилятора в виде последовательности лексем. Лексема - нечто неделимое, которое рассматривается как единица (объект) языка. Это могут быть и ключевые слова, и имена переменных, и символы операций и т.д. Синтаксический и семантический анализаторы выполняют сложную алгоритмическую работу по выделению составных частей из исходного текста программы с целью формирования ее внутреннего представления под полным синтаксическим и семантическим контролем. Синтаксический анализ выполняется по правилам формальной грамматики. Семантический анализ (проверка на содержание предложения или, если проще сказать, смысл) является наиболее трудной задачей для программной реализации. Семантика тесно связана с подготовкой и генерацией машинных команд. Результатом синтаксического анализатора является последовательность тетрад (четверок): код операции, два операнда и результат. 3.4. Этапы трансляции. Генерация кода

[1], c. 173-223 Логически процесс трансляции разделяется на два этапа: анализа и синтеза. Этап анализа (здесь анализируется исходный текст), как правило, имеет три отдельные фазы: - лексический анализ; - синтаксический анализ; - семантический анализ. Этап синтеза (здесь генерируется машинно-ориентированное представление кода программы) состоит из следующих (всех перечисленных или выборочных) фаз: - генерация машинно-независимого кода; - оптимизация машинно-независимого кода; - распределение памяти;

8

- генерация машинного кода; - оптимизация машинного кода. Большинство современных трансляторов производят промежуточный код, что делает их независимыми от типа процессора. UIL (Universal Intermediate Language) – некий универсальный язык для всех языков на любую машину пока не создан. Но в роли UIL используются Р-код для Паскаля, байт-код для JAVA, язык С (С++) также часто выполняет такую задачу (например, транслятор для языка Clipper написан на С). 3.5. Проектирование языковых интерпретаторов

[2], c.90 –124, c.317 –367 В области профессиональной деятельности узкий круг специалистов, тесно связанный с программированием, принимает непосредственное участие в создании и модификации полных трансляторов. Но в практической работе часто такие знание бывают необходимы: - для формирования интерактивной среды; - для разработки эффективных отладочных средств; - для организации режима запросов к базам данных. Для проектирования интерпретатора очень важным вопросом являются правила разбора выражений. Строгие правила алгебры и использование рекурсивного подхода позволяют упростить решение этой задачи. 4. Задание на контрольную работу Разработать программу по выполнению лексического анализа для языка программирования, удовлетворяющего ниже перечисленным требованиям, где n – последняя цифра и m – предпоследняя цифра шифра. Упрощенный язык программирования должен обязательно включать: 1. Оператор присваивания "=" и только одну из следующих арифметических операций: + * / ++

( сложение n=0, n=7), ( вычитание n=1, n=8), ( умножение n=2, n=9), ( деление n=3), ( логическое сложение n=4),

9

** %%

( логическое умножение ( сложение по модулю 2

n=5), n=6).

2. Один из следующих операторов: оператор цикла, если m=0, либо m=9, построенный в соответствии с предложенным синтаксисом конструкции: DO <имя параметра цикла>=m,n BEGIN <тело цикла> END; оператор цикла, если m=1, либо m=8, построенный в соответствии с предложенным синтаксисом конструкции: FOR <имя параметра цикла>=m TO n <тело цикла> NEXT; оператор цикла, если m=2, либо m=7, построенный в соответствии с предложенным синтаксисом конструкции: FOR <имя параметра цикла>=m TO n DO BEGIN <тело цикла> END; условный оператор, если m=3, либо m=6, построенный в соответствии с предложенным синтаксисом конструкции: IF <условие> THEN BEGIN <операторы> END; здесь <условие> задается одной из форм: ab; оператор процедуры, если m=4, либо m=5, построенный в соответствии с предложенным синтаксисом конструкции: PROCEDURE <имя процедуры> BEGIN <тело процедуры> END для вызова процедуры используется оператор CALL <имя процедуры>; 3. Оператор вывода переменных WRITE ( <список переменных через запятую> ); 4. Программа языка имеет структуру VAR <список переменных через запятую >: INTEGER BEGIN <операторы программы> END При выполнении контрольной работы в качестве образца можно использовать демонстрационную модель лексического анализатора, написанную на языке ПАСКАЛЬ. На фазе лексического анализа необходимо выделить лексемы, закодировать их и поместить в таблицу идентификаторов. Для этого

10

необходимо выделить символы операций, имена переменных и служебные слова, которые определены в задании на контрольную работу. 5. Пример программы на лексический анализ Предположим, по выбранному варианту будем иметь следующий вид исходного текста: var a,b,c : integer; begin a=10-c*b/2; end Данный исходный текст необходим для проверки правильности составленной программы. Программа должна быть написана языке С++. Для самостоятельной работы предлагается изучить алгоритм по тексту работающей программы, написанной на языке Паскаль и протокол результата выполнения лексического анализа. Program stud_work; { ЛЕКСИЧЕСКИЙ АНАЛИЗАТОР таблица кодов лексем _____________________ Лексема Код _____________________ var 1 begin 2 end 3 read 4 write 5 integer 6 + 100 101 * 102 / 103 = 104 ( 105 ) 106 , 107 : 108 ; 109 0 - тип служебных слов и перечисленных выше операций ident 200 – тип идентификаторов const 300 – тип констант

11

} Const kT=6; { 6 - количество служебных слов: var, begin, end, read, write, integer} n_str=500; { предельный размер исходного текста в символах, включая пробелы } n_ident=20; { ограничение на количество служебных слов + переменных } n_lex=100; { ограничение на общее число лексем } Type TS=string[10]; { длина имени лексемы не превышает 10 символов} Var a_text : array[1..n_str] of char; { входная программа - посимвольное представление исходного текста } LL : array[1..n_lex] of integer; { массив внутренних кодов лексем - результат лексического анализа } TT : array[1..n_lex] of integer; { массив типов для каждой лексемы исходного текста } VV : array[1..n_ident] of TS; { таблица идентификаторов } in_text : text; { текстовой файл программы } out_int : file of integer; { выходной файл кодов лексем с указанием типа } out_ident : file of TS; { выходной файл идентификаторов: служебные слова и переменные } prt : text; { файл для размещения протокола выполнения программы } n_text : integer; { счетчик длины массива a_text } nL : integer; { счетчик длины массива LL } nT : integer; { счетчик длины массива TT } i : integer; { вспомогательная переменная } { Начальная установка, заполнение таблицы идентификаторов всеми служебными словами, предварительно зарезервированными в таблице кодов лексем } procedure ust; begin VV[1]:='var'; VV[2]:='begin'; VV[3]:='end'; VV[4]:='read'; VV[5]:='write';

12

VV[6]:='integer'; nT:=kT; nL:=0; end; { ввод исходного текста } procedure input; var a : char; { один символ } begin assign(in_text,'prim.lex'); { связь файловой переменной с файлом } {prim.lex – произвольно выбранное имя файла, имя расширения указывает, что текст файла предназначен для лексического анализа } reset(in_text); { открытие файла для чтения } n_text:=0; while not eof(in_text) do begin read(in_text,a); n_text:=n_text+1; a_text[n_text]:=a; end; end; { формирование результатов в виде файлов: cod.lex,ident.lex } procedure out; var i : integer; begin assign(out_int,'cod.lex'); rewrite(out_int); assign(out_ident,'ident.lex'); rewrite(out_ident); write(out_int,nL,nT); for i:=1 to nL do write(out_int,LL[i],TT[i]); for i:=1 to nT do write(out_ident,VV[i]); end; { Распознавание буквы - true(1), иначе false(0) } function bukva(a : char): integer; var k,kz : integer; begin k:=ord(a); { ord - фунция дает код символа в ASCII } if ( k>=64 ) and ( k<=90 ) or ( k>=96 ) and ( k<=122 ) then kz:=1 else kz:=0;

13

bukva:=kz; end; { Распознавание цифры - true(1), иначе false(0) } function cifra( a : char) : integer ; var k,kz : integer; begin k:=ord(a); if ( k>=48 ) and ( k<=57 ) then kz:=1 else kz:=0; cifra:=kz; end; { Размер идентификатора (количество символов, входящих в образование имени лексемы), где начало i, конец k } function l_ident( i : integer):integer; var k:integer; begin k:=i; while ( bukva(a_text[k])=1 ) or ( cifra(a_text[k])=1 ) do k:=k+1; k:=k-1; l_ident:=k; end; { Размер цифровой константы ( начало i, конец k ) } function l_const ( i : integer ) : integer; var k:integer; begin k:=i; while cifra(a_text[k])=1 do k:=k+1; k:=k-1; l_const:=k; end; { Определение типа и кода лексемы ( строки str ), если данной лексемы нет в таблице служебных слов (массив - VV), тогда она добавляется в массив VV } procedure ttin( kk :integer; str : string; var kod,typ : integer ); var k,i : integer; begin

14

{ поиск в таблице VV } k:=0; for i:=1 to nT do if str=VV[i] then k:=i; { идентификатор имеется в таблице VV } if k<=kT then begin kod:=k; typ:=0; end; { служебные слова } if k>kT then begin kod:=k; typ:=kk; end; { имя переменной } { идентификатора нет в таблице, тогда он добавляется } if k=0 then begin nT:=nT+1; VV[nT]:=str; kod:=nT; typ:=kk; end; end; { лексический анализ } procedure lexan; var i,j,k,kod,typ : integer; a: char; str : string; begin i:=0; while i<=n_str do begin i:=i+1; a:=a_text[i]; if ord(a) > 32 then begin if bukva(a)=1 then { если a - буква, то может быть только идентификатор } begin k:=l_ident(i); str:=''; for j:=i to k do str:=str+a_text[j]; ttin(200,str,kod,typ); nL:=nL+1; LL[nL]:=kod; TT[nL]:=typ; i:=k; end; { если a - цифра, то далее может быть только цифровая константа } if cifra(a)=1 then begin k:=l_const(i); { цифровая константа } str:=''; for j:=i to k do str:=str+a_text[j];

15

ttin(300,str,kod,typ); nL:=nL+1; LL[nL]:=kod; TT[nL]:=typ; i:=k; end; { если a - не буква и не цифра, то далее может быть только операция } if ( bukva(a)<>1 ) and ( cifra(a)<>1 ) then begin { проверка на код операции } case a of '+': kod:=100; '-': kod:=101; '*': kod:=102; '/': kod:=103; '=': kod:=104; '(': kod:=105; ')': kod:=106; ',': kod:=107; ':': kod:=108; ';': kod:=109; end; typ:=0; nL:=nL+1; LL[nL]:=kod; TT[nL]:=typ; end; end; end; { end of while } end; { основная программа } begin ust; { начальная установка } input; { ввод программы } lexan; { лексический анализ } assign(prt,'prot.txt'); { con - вывод на экран, prot.txt – произвольное имя файла для записи протокола выполнения программы } rewrite(prt); writeln(prt,' Количество лексем=',nL, ' Количество идентификаторов и констант=',nT); writeln(prt); writeln(prt,' Результат работы лексического анализатора'); writeln(prt);

16

writeln(prt,' Исходная программа'); for i:=1 to n_text do write(prt,a_text[i]); writeln(prt); writeln(prt); writeln(prt,' тип лексемы : код лексемы'); for i:=1 to nL do begin write(prt,TT[i]:3,':',LL[i]:3,' '); if i mod 4 = 0 then writeln(prt); end; writeln(prt); writeln(prt); writeln(prt,' Таблица идентификаторов и констант'); for i:=1 to nT do write(prt,VV[i],' '); writeln(prt); writeln(prt,' Конец протокола'); close(prt); out; end. При желании данный текст может быть набран и оттранслирован в среде Borland Pascal версии 7.0. 6. Протокол результата лексического анализа Представленный ниже протокол, сформированный в виде текстового файла, отражает процесс выполнения лексического анализа для конкретного варианта разбора исходного текста по кодам и типам лексем.

Количество лексем=21 Количество идентификаторов и констант=10 Результат работы лексического анализатора Исходная программа var a,b,c : integer; begin a=c-b*b/2; end

17

тип лексемы : код лексемы 0: 1 0:107 0:109 200: 9 200: 8 0: 3

200: 7 200: 9 0: 2 0:101 0:103

0:107 0:108 200: 7 200: 8 300: 10

200: 8 0: 6 0:104 0:102 0:109

Таблица идентификаторов и констант var begin end read write integer a b c 2 Конец протокола Подобный результат может быть получен для любого варианта. Контрольная работа считается выполненной и правильно оформленной при наличии титульного листа, текста задания, выбранному по своему шифру, исходной программы на языке С++ и протокола, подтверждающего работоспособность представленной программы.

18

Содержание

Введение………………………………………………………………….….3 1. Содержание дисциплины………………………………………….……3 1.1 Рабочая программа…………………………………..……….….. …...3 1.1.1 Введение в теорию языков программирования..……….….. …...3 1.1.2 Формальные грамматики………………………..……….….. …...3 1.1.3 Процесс трансляции……………………………..……….….. ….. 3 1.1.4 Этапы трансляции. Генерация кода……………..……….….. …..3 1.1.5 Проектирование языковых интерпретаторов…..……….….. ….. 3 1.2 Тематический план лекций для студентов очно-заочной формы обучения…………………………………………………………….….4 1.3 Перечень практических занятий………………………………….…..4 2. Библиографический список………………………………………….….4 3. Методические указания к изучению дисциплины………………….….5 3.1 Введение в теорию языков программирования………………….…..5 3.2 Формальные грамматики………………………………………….…. 5 3.3 Процесс трансляции……………………………………………….…. 6 3.4 Этапы трансляции. Генерация кода……………………………….….7 3.5 Проектирование языковых интерпретаторов…………………….…..7 4. Задание на контpольную pаботу…………………………………….….7 5. Пример программы на лексический анализ……………………….……9 6. Протокол результата лексического анализа……………………….…..15 Редактор М.Ю.Комарова Сводный темплан 2003 г. Лицензия ЛР N 020308 от 14.02.97 ____________________________________________________________ Подписано в печать Формат 60х84 1/16 Б.кн.-журн. П.л. 1.0 Б.л. 0.5 РПТ РИО СЗТУ Тираж 100 Заказ ___________________________________________________________ Северо-Западный государственный заочный технический университет РИО СЗТУ, член Издательско-полиграфической ассоциации вузов Санкт-Петербурга 191186, Санкт-Петербург, ул. Миллионная, 5