Теория языков и методы трансляции

Программа учебного курса ТЕОРИЯ ЯЗЫКОВ И МЕТОДЫ ТРАНСЛЯЦИИ специальная дисциплина в рамках стандарта по направлению подготовки инженера 654600 «Информатика и вычислительная техника» I.

Организационно-методический раздел.

1.1.Цели и задачи курса Цели курса - дать основные способы определения языка; - познакомить с основными подходами создания языковых процессоров на примере трансляторов. Задачи курса - показать необходимость методов создания трансляторов на современном этапе развития; -

рассмотреть основные подходы, алгоритмы и методы, лежащие в основе создания транслятора; закрепить полученный материал на примере создания интерпретатора.

1.2.Требования к уровню освоения содержания курса По окончании изучения указанной дисциплины студент должен -

иметь представление об основных методах синтаксического анализа ; о подходах при генерации объектного кода программы. знать этапы трансляции программы алгоритмы реализации лексического анализа эффективные алгоритмы синтаксического анализа основные подходы при реализации семантического анализа уметь создать язык программирования реализовать для него интерпретатор или транслятор.

1.3.Формы контроля Итоговый контроль. Для контроля усвоения дисциплины учебным планом предусмотрен экзамен по теоретической части и зачет по практической. Текущий контроль. В течение семестра выполняется практическая работа, которая состоит из двух частей: необходимо придумать язык программирования и реализовать для него интерпретатор. Проводится контрольная работа по теоретической

части. Выполнение указанных работ является обязательным для всех студентов, а результаты текущего контроля служат основанием для выставления оценок в ведомость контрольной недели на факультете. 2. Содержание дисциплины. 2.1.Новизна и актуальность курса Учебный курс концентрирует внимание на фундаментальных знаниях предметной области – способах задания языков, алгоритмах и методах, лежащих в основе всех основных этапов создания трансляторов. 2.2.Тематический план курса (распределение часов). Наименование разделов и тем Лекции 1. Введение 2. Общее представление о процессе трансляции 3. Лексический анализ 4. Синтаксический анализ 5. Контекстный анализ и генерация Итого по курсу:

6 2

Количество ЛабораторСеминар ные работы ы 6

часов Самостоятельная работа

Всего часов

10 2

24 4

3 19 6

6 20 4

10 20 10

19 59 20

36

36

52

124

2.3.Содержание отдельных разделов и тем. А) Теоретическая часть 1. Введение Место транслятора в программном обеспечении. Структура языка программирования. Синтаксис языка. Семантика языка. Лексемы. Понятия. Атрибуты. Области действия. 1.2.Способы описания языков. Грамматики. Классификация грамматик по Хомскому. Контекстно-свободные языки. Эквивалентные преобразования грамматик. Однозначность грамматики и языка. Набор допустимых преобразований. Достижимые свойства грамматик. Распознаватели. Конечные автоматы. Автоматы с магазинной памятью. 2. Общее представление о процессе трансляции Принципиальная схема трансляции. Построение абстрактной программы. Этап генерации. 3. Лексический анализ Функции лексического анализа. Реализация лексического анализатора в трансляторе. Функции расстановки 4. Синтаксический анализ Стратегии разбора. Методы синтаксического анализа. Нисходящий анализ. Неформальное описание нисходящего разбора. Алгоритм нисходящего разбора. Восходящий разбор. Неформальное описание восходящего разбора. Алгоритм восходящего разбора. Табличные методы синтаксического анализа. Алгоритм Эрли. Алгоритм Кока-Янгера-Касами. Синтаксический анализ без возвратов. LL(k)-грамматики. Предсказывающие алгоритмы разбора. Разбор для LL(1)-грамматик. Алгоритм рекурсивного спуска. Проверка LL(k)-условия. Детерминированный восходящий синтаксический анализ. LR(k)-грамматики. Грамматики предшествования. Грамматики

простого предшествования. Грамматики слабого предшествования. Грамматики операторного предшествования. 5. Контекстный анализ и генерация 5.1. Контекстный анализ Идентификация. Простейшая реализация идентификации. Атрибутная индукция. 5.2. Генерация Промежуточные (внутренние) представления программы. Представление в виде ориентированного графа. Трехадресный код. Лианеаризованные представления. Общая схема генерации. Представление структур данных. Генерация выражений и оператора присваивания. Генерация простых выражений. Учет составных переменных и вызовов функций. Генерация управления вычислениями. Генерация условного оператора. Генерация операторов перехода. Генерация подпрограмм и обращений к ним. Распределение памяти. Статическое распределение. Регулярное (магазинное) распределение. Динамическое распределение. Б) Практические занятия В рамках единого задания на семестр «Разработка интерпретатора для созданного языка программирования» необходимо: 1. Разработать язык программирования (привести грамматику и описание семантики) 2. Реализовать лексический, синтаксический и семантический анализы. 3. Реализовать интерпретацию построенного внутреннего представления программы. Перечень примерных контрольных вопросов и заданий для самостоятельной работы – см. раздел 3.1 (задания для контрольных работ), см. раздел 3.2 (вопросы для подготовки к экзамену). 2.

Учебно-методическое обеспечение дисциплины

Разработано учебное пособие по курсу лекций Задания для контрольных работ(рефератов) 1) Для заданной грамматики и цепочки применить один из алгоритмов синтаксического анализа и дать ответ на вопрос о принадлежности цепочки языку порожденному данной грамматикой. Если ответ положительный по построить дерево вывода. 2) Привести алгоритм преобразования КС грамматики в грамматику в нормальной форме Хомского с использованием допустимого набора преобразованийю Образцы вопросов для подготовки к экзамену Раздел 1. 1) Дать определение грамматики. 2) На чем основана классификация грамматик по Хомскому. 3) По правилам грамматики определить ее тип по классификации Хомского. Раздел 2 4) Уметь нарисовать принципиальную схему трансляции и рассказать суть каждого из этапов.. Раздел 3. 5) Основные способы реализации лексического анализа. 6) Способы поиска при реализации лексического анализа. Раздел 4.

7) Знать и уметь изложить все алгоритмы синтаксического анализа. Раздел 5. 8) Идентификация? 9) Атрибутная индукция? 10) В чем основная причина необходимости семантического анализа. 11) Генерация простых выражений. 12) А что такое простое выражение при генерации? 13) Распределение памяти при генерации. Список основной и дополнительной литературы 0. Черноножкин С. К. Методы трансляции. Новосибирск, НГУ, 1995 . 1. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. - М.: Мир, 1978, т. 1,2. 2. Агафонов В.Н. Синтаксический анализ языков программирования - Новосибирск, НГУ, 1981. 3. Грис Д. Конструирование компиляторов для цифровых вычислительных машин. - М.: Мир, 1975 4. Пратт Т. Языки программирования: разработка и реализация. - М. Мнр: 1979 5. Хантер Р. Проектирование и конструирование компиляторов. - М.: Финансы и статистика, 1984. 6. Касьянов В.П., Поттосин И.В. Методы трансляции. - Новосибирск: НГУ. 1978. 7. Касьянов В.Н., Поттосин И.В. Технология трансляции. -- Новосибирск: НГУ 1979 8. Касьянов В.II., Поттосин И. В. Автоматизация построения трансляторов. Новосибирск: НГУ, 1983 9. Касьянов В. Н., Поттосин И. В. Методы построения трансляторов. - Новосибирск: Наука, 1986. 10. Серебряков В.А. Лекции по конструированию компиляторов. - М.: ВЦ РАН, 1994. 11. Кнут Д.Е. Искусство программирования для ЭВМ. Т.З Сортировка и поиск. - М.: Мир, 1978. Программу подготовил к.ф.-м.н., доцент

Черноножкин С.К.

Программа утверждена на заседании Ученого совета факультета информационных технологий Новосибирского государственного университета 18 декабря 2003 г., протокол заседания №16. Декан ФИТ НГУ, д.ф.-м.н.

М.М.Лаврентьев