Программа спецкурса «Методы трансляции» icon

Программа спецкурса «Методы трансляции»


Смотрите также:
Учебное пособие для студентов...
Учебно-методический комплекс по языки программирования и методы трансляции наименование...
«Теория языков программирования и методы трансляции»...
Программа вступительного экзамена по специальности 05. 13. 18 Математическое моделирование...
Рабочая учебная программа спецкурса св. В...
Программа спецкурса для студентов специальности 1-31 03 06 экономическая кибернетика...
Программа спецкурса по английскому языку «Диалог с друзьями»...
Программа спецкурса «Лекарственные растения Ставропольского края»...
Программа курса «Методы построения трансляторов»...
Программа спецкурса “Древнерусская книжность и духовная культура”...
Экзаменационные вопросы по спецкурсу «Методы трансляции»...
Программа спецкурса для магистрантов Москва: мгу, 2002...



Загрузка...
скачать

Программа спецкурса «Методы трансляции»

(1-й семестр)



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

I. ВВЕДЕНИЕ


  1. Место трансляторов в структуре программного обеспечения. [5-3.1, 2-1.1]

  2. Структура языка: лексика, синтаксис, семантика, прагматика. [5-2.2+5:7, 1-1.1, 2-1.2]

  3. Общее представление о трансляции:

    1. Типы трансляторов: компилятор, интерпретатор, конвертор. [5-3.2]

    2. Этапы трансляции. Компоненты транслятора. [5-4, 1-1.2] Промежуточные представления программы в процессе трансляции. [2-4] Однопроходная и многопроходная схемы трансляции.
^

I I. ЛЕКСИКО-СИНТАКСИЧЕСКИЙ РАЗБОР


  1. Формальные языки:

    1. Определение. [1-0.2, 3-1.1] Проблемы разрешимости и конечности языка.

    2. Способы задания языков: перечисление, формулы над множествами, порождающие грамматики, распознаватели. [1-2.1]

    3. Представление языков системой операций над множествами: операции пересечения, объединения, дополнения, конкатенации языков. [1-0.2.3, 3-1.1]

    4. Порождающие (формальные) грамматики. [1-2.1.2, 2-2, 3-1.2, 5-2.8, 6-2.2]

      1. Общее определение: алфавиты терминалов и нетерминалов, множество продукций.

      2. Классификация грамматик по Хомски: регулярные (праволинейные), контекстно-свободные, контекстно-зависимые, общего вида. [1-2.1.3, 2-2.1, 3-1.3, 5-2.8.3]

      3. Отношение непосредственного вывода, его замыкания. Вывод по грамматике. Лево- и правосторонний выводы. [1-2.4.1] Язык, порождаемый грамматикой. Проблемы представимости языка грамматикой и эквивалентности грамматик.

      4. Дерево разбора; крона и сечение (сентенциальная форма). Представление вывода цепочки деревом разбора. Проблема неоднозначности вывода. [1-2.4.1, 2-2.2/2.3.1, 3-3.1, 5-2.8.5, 6-2.4]

      5. Нисходящий (развертка) и восходящий (свертка), лево- и правосторонний методы разбора. [1-3.4.1:3, 2-6.1, 5-6.1] Возможность и проблемы реализации нисходящего левостороннего разбора методом рекурсивного спуска. [2-9.2.2, 6-4.2]

    5. Автоматы-распознаватели. [1-2.1.4, 2-3, 5-5.1]

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

      2. Алгоритм работы автомата-распознавателя: начальное и допускающие состояния; конфигурация; такт работы; результат.

      3. Детерминированные и недетерминированные автоматы: определение; особенности функционирования. Детерминированное моделирование недетерминированного автомата. Проблема детерминизации.

      4. Специальные классы автоматов:

  • Разновидности внутренней памяти (память состояния, магазин(ы)); моделирование конечной памяти расширенным множеством состояний и переходов. Конечные и магазинные автоматы.

  • Наличие выходной ленты; автоматы-преобразователи.

      1. Отношение вывода, индуцированное шагом автомата; его замыкания. Язык, допустимый автоматом. Проблема представимости языка автоматом.

      2. Возможность реализации универсального таблично-управляемого детерминированного автомата заданного класса.

    1. Метасинтаксические нотации для пользовательской спецификации синтаксиса языков: БНФ, РБНФ, синтаксические диаграммы.

  1. Регулярные языки. [1-2.2, 3-2, 6-3.1]

    1. Регулярные грамматики (РГ).

      1. Определение. Примеры.

      2. Особенности дерева вывода по РГ.

    2. Конечные автоматы (КА). [1-2.2.3, 2-3.1, 3-2.2]

      1. Определение. Работа КА. Примеры. Характеристика возможностей класса КА, обусловленных отсутствием внутренней памяти.

      2. Детерминированные и недетерминированные КА. Теорема о детерминизации; совпадение классов НКА- и ДКА-языков.

    3. Регулярные множества (РМ) и регулярные выражения (РВ). [1-2.2.1, 3-2.1]

      1. Определения. Соответствие РВ  РМ.

    4. Совпадение классов РГ, ДКА, НКА, РМ и РВ. Теорема Клини. Определение регулярного (Р-) языка. Примеры регулярных языков. [1-2.2.2:4, 3-2.3]

    5. Лемма о разрастании для Р-языков. Примеры нерегулярных языков. [1-2.3.2]

    6. Теорема Майхилла-Нерода о единственном минимальном КА (без док-ва). [1-2.3.1] Проблемы разрешимости, пустоты и конечности РЯ, эквивалентности РГ. [1-2.3.4]

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

    1. Представление исходной программы в виде цепочки символов. Реализация уровня абстракции от физического представления текста.

    2. Лексическая структура программы:

  • лексемы и разделители, их виды и особенности в различных языках;

  • проблемы распознавания: контекстное, резервирование; просмотр вперед.

    1. Описание типовых лексем средствами Р-языков.

    2. Сканер (лексический анализатор); функции сканера; прямой и непрямой методы работы. [1-3.3.2:3, 2-5.1/2, 5-5.2/3/14.2.2/3]

    3. Токены. Лексическая свертка программы (явная и неявная). Способы организации таблиц имен и констант: методы буферизации и хеширования. [2-5.2.1, 6-3.2]

    4. Автоматизация построения лексического анализатора:

      1. Алгоритм построения нисходящего левостороннего Р-распознавателя по детерминированной РГ методом рекурсивного спуска.

      2. Программирование универсального ДКА со входной таблицей переходов.

      3. Обзор существующих средств: LEXX.

  1. Контекстно-свободные (КС-) языки.

    1. Контекстно-свободные грамматики (КСГ). [1-2.4, 5-2.8.4, 6-4.1]

      1. Определение. Примеры.

      2. Неразрешимость проблем эквивалентности и однозначности КСГ. [1-2.6.3, 1-2.6.5]

    2. Достижимые свойства и эквивалентные преобразования КСГ: [1-2.4.2, 2-2.3, 3-3.2, 5-2.8.5]

  • Исключение внешнего и внутреннего правил.

  • Исключение внешних, внутренних и циклических тупиков (бесполезных и недостижимых символов). Проблема пустоты КС-языка.

  • Исключение -правил. Обобщенная (неукорачивающая) КСГ.

  • Исключение цепных правил. Приведенная КСГ.

  • Исключение левой рекурсии. [1-2.4.4]

  • Приведение к нормальной (бинарной) форме Хомского. [1-2.4.3]

      1. Лемма о разрастании для КС-языков. Примеры не-КС-языков. [1-2.6.1, 3-3.2]

    1. Магазинные автоматы (МА). [1-2.5, 2-3.2, 3-3.3, 5-6.2]

      1. Определение. Работа МА. Примеры. Характеристика возможностей класса МА, обусловенных наличием магазина. [1-2.5.1]

      2. Детерминированные и недетерминированные МА. Примеры. Проблема совпадения классов НМА- и ДМА-языков. [1-2.5.1/4]

      3. Расширенные МА; моделирование средствами обычных МА. [1-2.5.2.]

    2. КС-язык, как решение системы уравнений на множествах.

      1. Переход от грамматики к системе уравнений на множествах. Решение в форме неподвижной точки. [1-2.4.5]

      2. Свойства замкнутости КС-, ДКС- и Р-языков относительно операций. [1-2.3.3/2.6.2, 3-3.4]

    3. Совпадение классов КС- и НМА-языков. [1-2.5.3, 3-3.4]

  1. Методы синтаксического разбора для КСГ общего вида.

    1. Недетерминированный разбор по КСГ.

      1. Построение НМА, моделирующего нисходящий левосторонний (НЛ-) разбор по КСГ (из теоремы п.4.4). [1-3.4.2]

      2. Построение НМА, моделирующего восходящий правосторонний (ВП-) разбор по КСГ. [1-3.4.3]

    2. Детерминированный разбор с возвратами по КСГ. Детерминированное моделирование недетерминированного разбора: дерево вариантов; обход (перебор с возвратами); моделирование на 2-МА. Оценка сложности. [1-4.1, 2-7.1/2, 5-6.3/4]

    3. Табличный разбор без возвратов по КСГ.

      1. Алгоритм Кока-Янгера-Касами: метод динамического программирования для НЛ-разбора. Оценка сложности. [1-4.2.1, 2-8.2]

      2. Алгоритм Эрли: метод «горизонтального» левостороннего разбора. Оценка сложности. [1-4.2.2, 2-8.1, 5-6.5.1:4]

  2. Методы синтаксического разбора для специальных КСГ.

    1. Идеи для построения алгоритмов разбора линейной сложности. [1-5.введ]

    2. LL(k)-грамматики и НЛ-разбор. [1-5.1, 2-9.1, 6-4.3:5]

      1. Определение LL(k) и строгой LL(k). Примеры.

      2. Соотношение классов LL(k). Проблемы разрешимости. [2-9.2.3]

      3. Свойства однозначности, нелеворекурсивности.

      4. Методы приведения грамматики к LL(k). [1-5.1.3]

      5. Множества LEFTk, FOLLOWk, LOOKAHEADk; их построение. Практические условия для проверки LL(k)-свойства и для выбора правила развертки при разборе. [1-5.1.1/3/6]

      6. Построение k-предсказывающего ДМА-преобразователя для НЛ- LL(k)-разбора. Оценка сложности. [1-5.1.2/4/5, 2-9.2, 5-14.3.1]

    3. Схема таблично-управляемого ВП-разбора типа «перенос-свертка». Примеры реализации. Конфликты типа «перенос-свертка» и «свертка-свертка» при ВП-разборе. Оценка сложности. [1-5.2.1, 1-5.3.1]

    4. Грамматики предшествования и ВП-разбор. [1-5.3, 2-9.4, 5-6.4.3]

      1. Отношения предшествования Вирта-Вебера; их роль в ВП-разборе.

      2. Грамматики простого [1-5.3.2, 2-9.4.1], слабого [1-5.3.4, 2-9.4.2] и операторного [1-5.4.3, 2-9.4.3] предшествования:

  • Свойство однозначности.

  • Настройка ВП-разбора «перенос-свертка» для каждого класса.

  • Способ устранения конфликтов для каждого класса.

  • Примеры.

    1. LR(k)-грамматики и ВП-разбор. [1-5.2, 2-9.3, 5-14.3.3, 6-5]

      1. Определение LR(k). [1-5.2.2]

      2. Соотношения классов LR(k) и их подклассов. Особенности случая k=0. [1-5.4.5]

      3. Доопределение схемы ВП-разбора «перенос-свертка» для LR(k)-анализатора. Управляющие LR(k)-таблицы. Оценка сложности. [1-5.2.2, 5-6.5.5/6]

      4. Множество EFFk. LR(k)-ситуации. Характеристическое свойство LR(k). [1-5.2.3]

      5. Cистема множеств допустимых LR(k)-ситуаций; построение канонической системы множеств [1-5.2.3, 5-14.3.3.2].

      6. Практические условия для проверки LR(k)-свойства и для выбора правила развертки при разборе. [1-5.2.4]

      7. Построение управляющих LR(k)-таблиц для универсального LR(k)-анализатора. Примеры. Свойства канонического LR(k)-анализатора. [1-5.2.5, 5-14.3.3.3]

      8. Оптимизация LR(k)-анализаторов. [1-7.3]

    2. Подкласс SLR(k). Построение SLR(k)-таблиц. Особенности SLR(k)-грамматик. [1-7.4.1]

      1. Подкласс LALR(k). Построение LALR(k)-таблиц. Особенности LALR(k)-грамматик. [1-7.4.2]

  1. Автоматизация построения синтаксических анализаторов.

    1. Программирование НЛ- LL(1)-анализатора методом рекурсивного спуска (на примере). Иллюстрация «вертикальной» схемы построения транслятора: примеры приложения к задачам генерации внутреннего представления, трансляции, интерпретации.

    2. Программирование и недостатки универсальных таблично-управляемых НЛ- и ВП- анализаторов.

    3. «Генератор компиляторов»: СС(G) = CG для LR-грамматик. Обзор существующих средств: YACC, BISON.

Литература


Основная:

  1. А.Ахо, Дж.Ульман. Теория синтаксического анализа, перевода и компиляции. Том 1. Синтаксический анализ. – М., Мир, 1978.

  2. С.К. Черноножкин. Методы трансляции. – Новосибирск, НГУ, 1995.

  3. В.Н.Касьянов. Лекции по теории формальных языков, автоматов и сложности вычислений. – Новосибирск, НГУ, 1995.

Дополнительная:

  1. В.Дж.Рейуорд-Смит. Теория формальных языков. Вводный курс. – М., Радио и связь, 1988.

  2. В.Н.Касьянов, И.В.Поттосин. Методы построения трансляторов. – Новосибирск, Наука, 1986.

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


Программу подготовил

н.с. ИСИ СО РАН В.А.Цикоза




Скачать 74.75 Kb.
оставить комментарий
Дата29.09.2011
Размер74.75 Kb.
ТипПрограмма спецкурса, Образовательные материалы
Добавить документ в свой блог или на сайт

хорошо
  1
Ваша оценка:
Разместите кнопку на своём сайте или блоге:
rudocs.exdat.com

Загрузка...
База данных защищена авторским правом ©exdat 2000-2017
При копировании материала укажите ссылку
обратиться к администрации
Анализ
Справочники
Сценарии
Рефераты
Курсовые работы
Авторефераты
Программы
Методички
Документы
Понятия

опубликовать
Загрузка...
Документы

Рейтинг@Mail.ru
наверх