Задача разбора. Разновидности алгоритмов разбора. Домино де Ремера. Общая схема распознавателя. Классификация распознавателей по типам. Примеры

Вид материала

Задача

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

Подобный материал:

• Программа курса лекций «Математические методы и модели исследования операций», 27.98kb.
• Последовательность и образцы синтаксического разбора Порядок разбора словосочетания, 412.38kb.
• Андрияновой Наталии Анатольевны 5 класс Русский язык Тема: Корни с чередованием букв, 96.91kb.
• Д. С. Осипенко Понятие алгоритма. Примеры алгоритмов. Свойства алгоритмов. Способы, 96.46kb.
• «Понятие об алгоритме. Примеры алгоритмов. Свойства алгоритмов. Типы алгоритмов, построение, 84.9kb.
• 07. 08. 02 день заезда 08. 08., 17.83kb.
• Урок русского языка по теме «морфологический разбор наречия», 46.56kb.
• Положение о порядке служебного расследования, разбора и учета нарушений безопасности, 967.32kb.
• Список произведений для аналитического разбора на экзаменационных испытаниях (гак), 23.13kb.
• Построение и анализ комбинаторных алгоритмов, 62.76kb.

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

(лето 2011 года)

1. Определение транслятора, компилятора, интерпретатора. Входной язык, целевой язык, язык реализации. T-диаграммы. Кросс-трансляторы. Автоматическое построение компилятора и его частей. Самокомпилятор. Раскрутка. Примеры раскрутки.
   
2. Структура транслятора. Многопроходные и однопроходные трансляторы. Таблицы транслятора. Компиляция «на лету». Cхема трансляции программ в .NET. Примеры.
   
3. Трансляторы с языка ассемблера (ассемблеры). Конструкция простого двухпроходного ассемблера. Особенности построения интерпретаторов. Примеры.
   
4. Виртуальные машины, ее архитектура и реализация. Язык ассемблера виртуальной машины. Программирование в коде виртуальной машины. Примеры.
   
5. Цепочки символов и операции над ними. Языки, их классификация. Синтаксис и семантика языка. Способы определения языка. Примеры.
   
6. Формальное определение грамматики. Четыре типа грамматик по Н. Хомскому. Сентенции и сентенциальные формы. Примеры.
   
7. Способы задания грамматик. Форма Бэкуса-Наура. Расширенная форма Бэкуса-Наура. Примеры.
   
8. Вывод. Цепочки вывода. Дерево вывода. Методы построения дерева вывода. Примеры.
   
9. Эквивалентность и однозначность грамматик. Проверка однозначности и эквивалентности грамматик. Различные типы конфликтов в неоднозначных грамматиках и их разрешение. Примеры.
   
10. Задача разбора. Разновидности алгоритмов разбора. Домино де Ремера. Общая схема распознавателя. Классификация распознавателей по типам. Примеры.
    
11. Назначение и особенности построения таблиц идентификаторов. Построение таблиц идентификаторов по методу бинарного дерева, xеш-функции и хеш-адресация, комбинированные способы построения таблиц идентификаторов. Примеры.
    
12. Основные задачи лексического анализа. Назначение лексического анализатора (сканера). Принципы и проблемы построения лексических анализаторов. Примеры.
    
13. Виды и значения лексем. Токены, шаблоны, лексемы. Атрибуты токенов. Лексические ошибки. Определение и распознавание токенов. Примеры.
    
14. Регулярные и автоматные грамматики и языки. Пример автоматного языка. Граф автоматной грамматики. Дерево разбора в автоматной грамматике. Примеры.
    
15. Детерминированные (Д) и недетерминированные (Н) конечные автоматы (КА). Преобразование НКА в ДКА. Таблица переходов ДКА. Минимизация КА. Автоматы с магазинной памятью (МП-автоматы). Примеры.
    
16. Программная реализация автоматного распознавателя. Использование конечного автомата для распознавания автоматного языка. Примеры.
    
17. Регулярные выражения и регулярные множества. Эквивалентность регулярных выражений и автоматных грамматик. Регулярные языки и их свойства. Расширенная нотация для регулярных выражений. Примеры.
    
18. Табличный LL(1)-анализатор. Принципы построения, область применения. Примеры.
    
19. Автоматизация построения лексических анализаторов. Утилита Lex. Примеры.
    
20. КС-грамматики в нормальной форме Хомского, КС-грамматики в нормальной форме Грейбах. Примеры.
    
21. Виды КС-грамматик: S, Q, LL и LR грамматики. Грамматики предшествования. Грамматики простого и операторного предшествования. Примеры.
    
22. Однозначность КС-грамматики. Левосторонний и правосторонний вывод. Нисходящий и восходящий разбор КС-языков. Общий алгоритм распознавания КС-языков. Самовложение в КС-грамматиках. Примеры.
    
23. Алгоритмы распознавания КС-языков. Требование детерминированного распознавания. Распознающий автомат для КС-языков. Примеры.
    
24. Синтаксические диаграммы КС-языков. Определение языка с помощью синтаксических диаграмм. Примеры.
    
25. Преобразование КС-грамматик: удаление бесплодных и недостижимых символов, устранение λ-правил, аннулирующих и цепных правил, устранение левой рекурсии. Цель преобразования КС-грамматик. Приведенные грамматики. Примеры.
    
26. Синтаксический анализ КС-языков методом рекурсивного спуска. Левосторонний разбор по методу рекурсивного спуска. Расширенные варианты метода рекурсивного спуска. Рекурсивный спуск и табличный анализатор. Примеры.
    
27. Синтаксический анализатор. Его назначение. Принципы работы распознавателей с возвратом. Нисходящий распознаватель с подбором альтернатив. Восходящий распознаватель на основе алгоритма «сдвиг—свертка». Нисходящие распознаватели КС-языков без возвратов. Примеры.
    
28. LL(k) и LL(1) - грамматики. Левая и правая рекурсия. SLR(1) и LALR(1)-грамматики. Примеры.
    
29. Синтаксический разбор для LR(0)-грамматик. Синтаксический разбор для LL(1)-грамматик. Табличный LL(1)-анализатор. Примеры.
    
30. Перевод арифметических выражений в польскую запись. Алгоритм вычисления выражений в польской записи. Алгоритм Э. Дейкстры трансляции выражений в польскую запись (метод стека с приоритетами). Примеры.
    
31. Грамматика и синтаксический анализ арифметических выражений. Интерпретация выражений. Контекстный анализ. Контекстный анализ модуля выражений операторов. Примеры.
    
32. Включение действий в синтаксис. Семантические процедуры. Пример разработки синтаксического анализатора заданных конструкций языка С++.
    
33. Автоматизация построения синтаксических анализаторов (генератор анализаторов YACC). Грамматики и YACC. Примеры.
    
34. Синтаксические распознаватели на основе грамматик предшествования. Примеры.
    
35. Анализ потока управления. Граф потока управления. Доминирование. Глубинное остовное дерево. Основные виды фрагментов графа потока управления и их свойства. Примеры.
    
36. Анализ потоков данных. Достижимые определения и живые переменные. Формализация задач анализа потоков данных. Итеративный алгоритм для решения задач анализа потоков данных. Примеры.
    
37. Промежуточные языки и причины их использования в компиляторах: атрибутные деревья разбора; прямая и обратная польская запись; триады/тетрады; RTL. Примеры.
    
38. Формы промежуточного представления программы. Унификация промежуточного представления. Основные черты промежуточного представления, используемого в .NET (MSIL). Примеры.
    
39. Семантический анализ. Его назначение и этапы. Внутреннее представление. Семантические таблицы. Семантический анализатор. Семантическое дерево выражения. Примеры.
    
40. Общие принципы генерации кода. Синтаксически управляемый перевод. Работа с таблицами. Идентификация лексических единиц языков программирования. Примеры.
    
41. Управление памятью и сборка мусора с точки зрения разработчика компилятора. Менеджеры памяти. Управление кучей. Подсчет ссылок и разметка памяти. Статическое и динамическое связывание. Стековый механизм управления памятью. Дисплей памяти процедуры (функции). Стековая организация дисплея памяти. Управление памятью в .NET. Примеры.
    
42. Трансляция описаний. Трансляция списка импорта. Распределение памяти. Назначение адресов переменным. Примеры.
    
43. Выбор инструкций при генерации кода. Постановка задачи выбора оптимальных инструкций. Генератор кода. Генерация кода для выражений. Генерация кода для операторов. Примеры.
    
44. Трансляция процедур без параметров, с параметрами-значениями, параметрами-переменными и локальными переменными. Трансляция процедур-функций. Примеры.
    
45. Контроль типов данных при трансляции. Идентификация. Простые и сложные структуры данных. Выравнивание границ данных. Память для типов данных (RTTI-информация). Трансляция линейных массивов. Примеры.
    
46. Исключительные ситуации и их обработка. Обработка ошибок при трансляции. Примеры.
    
47. Общие принципы оптимизации кода. Виды оптимизирующих преобразований. Представления программы, используемые в оптимизирующих преобразованиях. Примеры оптимизирующих преобразований. Машинно-зависимые методы оптимизации. Примеры.
    
48. Оптимизация линейных участков программы. Оптимизация вычисления логических выражений. Оптимизация циклов. Оптимизация передачи параметров в процедуры и функции. Примеры.
    
49. Понятие и структура современной системы программирования. Интегрированные среды разработки. Функции текстовых редакторов в системах программирования. Компилятор как составная часть системы программирования. Примеры.
    
50. Компоновщик. Назначение и функции компоновщика. Загрузчики и отладчики. Функции загрузчика. Библиотеки подпрограмм как составная часть систем программирования. Статические и динамические библиотеки подпрограмм. Ресурсы пользовательского интерфейса. Редакторы ресурсов. Примеры.
    

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

1. Молчанов А.Ю. Системное программное обеспечение. – СПб.: Питер, 2010 г.

2. Молчанов А.Ю. Системное программное обеспечение. Лабораторный практикум – СПб.: Питер, 2005 г.

3. Вояковская Н.Н., Москаль А.Е., Булычев Д.Ю., Терехов А.А. Разработка компиляторов. Учебный курс Интернет-Университета Информационных технологий t.ru

4. Гагарина Л.Г., Кокорева Е.В. Введение в теорию алгоритмических языков и компиляторов. – М.: ИД «Форум», 2009 г.

5. Свердлов С. З. Языки программирования и методы трансляции. – СПб.: Питер, 2007 г.

6. Ахо А., Компиляторы: принципы, технологии и инструментарий / А. Ахо (и др.).– М.: Издательский дом «Вильямс», 2008 г.

7. Карпов Ю.Г. Основы построения трансляторов. – СПб.: «БХВ-Петербург», 2005 г.