Примерный перечень экзаменационных вопросов

по курсу " Теория формальных языков и компиляторов",

2013/2014 учебный год

1	Формальные языки, основные понятия.
2	Этапы процесса трансляции, промежуточные формы представления программы
3	Лексический анализ. Основные функции. Понятия слова и лексемы, их сходство и различие
4	Процедурная модель лексического анализатора. Особенности алгоритма обработки слов
5	Автоматная модель лексического анализатора: стадии разработки и функционирования
6	Конечные автоматы без памяти, основные понятия, детерминированность и недетерминированность КА
7	Эквивалентность конечных автоматов, понятие истории работы КА, виды эквивалентности КА
8	Оптимальность конечных автоматов без памяти
9	Способы определения лексики формальных языков. Первичные регулярные выражения
10	Регулярные выражения и системы регулярных выражений
11	Преобразование системы регулярных выражений в недетерминированный конечный автомат
12	Задача преобразования недетерминированного автомата в детерминированный оптимальный конечный автомат, структура алгоритма ее решения
13	Устранение пересечения множеств символов разметки столбцов
14	Ликвидация всех недетерминированностей одним алгоритмом
15	Удаление тупиковых и недостижимых состояний
16	Оптимизация управляющей таблицы лексического акцептора
17	Преобразование не полностью определенного КА в полностью определенный
18	Взаимодействие лексического анализатора с синтаксическим и семантическим анализаторами. Структура информационных таблиц транслятора
19	Последовательная и упорядоченная организация информационных таблиц, алгоритмы поиска и дополнения, временные оценки
20	Рандомизированная организация информационных таблиц, алгоритмы поиска и дополнения, временные оценки
21	Синтаксический анализ, основные понятия и функции
22	Формальные грамматики, основные понятия
23	Понятие цепочки, предложения, непосредственного вывода и вывода. Соотношение между грамматиками и языками
24	Деревья грамматического разбора, их свойства и связь с задачами синтаксического анализа
25	Классификация формальных грамматик
26	Свойства формальных грамматик: рекурсивность левая, правая и общая, однозначность
27	Аннулируемые, недостижимые и бесплодные нетерминалы, алгоритмы их определения
28	Отношения между символами. Понятие символа-предшественника. Алгоритм определения множества предшественников символа и цепочки символов
29	Понятие символа-последователя. Алгоритм определения множества непосредственных последователей для символов грамматики
30	Алгоритм определения множеств символов, которые могут быть последними в цепочках, выводимых из нетерминалов. Вычисление множеств последователей
31	Нисходящие методы синтаксического анализа, основные идеи
32	Понятие множеств выбора правил грамматики с одним нетерминалом в правой части. Определение LL(1)-грамматик
33	Процедурная реализация рекурсивного спуска для LL(1)-грамматик
34	Автоматная реализация рекурсивного спуска. Состав клетки управляющей таблицы автомата с несколькими состояниями
35	Преобразование LL(1)-грамматики в управляющую таблицу автомата с несколькими состояниями
36	Преобразование LL(1)-грамматики в автомат с одним состоянием, управляемый входным символом и содержимым стека
37	Восходящие методы синтаксического анализа, основные идеи
38	Конфликты свертка/свертка и перенос/свертка. Развитие основной идеи восходящего анализа, восходящий автомат с несколькими состояниями
39	Операции сдвига и свертки восходящего синтаксического автомата с несколькими состояниями
40	Понятие конфигурации и его связь с понятием состояния восходящего акцептора и его операциями
41	Построение таблицы конфигураций по грамматике
42	Преобразование таблицы конфигураций в управляющую таблицу восходящего акцептора. Выявление конфликтов. Понятие LR(0)-грамматик
43	Разрешение конфликтов методом использования полных множеств последователей. Понятие SLR(1)-грамматик
44	Понятие ожидаемого правого контекста и расширенной конфигурации. Правила определения правого контекста для расширенных конфигураций
45	Метод использования правого контекста для предотвращения конфликтов при построении управляющей таблицы. LR(1)-грамматики и автоматы
46	LALR(1)-грамматики и автоматы
47	Эквивалентные преобразования грамматик
48	Нейтрализация ошибок при синтаксическом анализе.
49	Понятие постфиксной записи, преобразование выражений в ПФЗ.
50	Преобразование управляющих операторов в постфиксную запись.
51	Семантический анализ, основные задачи и понятия. Операции и данные, адреса и значения, l-value и r-value
52	Тетрады и триады, алгоритм преобразования ПФЗ в последовательность тетрад