Курс проектирование языков и трансляторов вопросы по теории
| Вид материала | Документы |
- Теория автоматов и формальных языков составил доцент А. А. Мальцев, 38.01kb.
- Пояснительная записка настоящий курс составлен в русле общей теории языка и является, 327.61kb.
- Лингвокультурная компетентность личности как культурологическая проблема, 569.63kb.
- Программа дисциплины Формальные языки и автоматы Семестр, 9.45kb.
- Курс специальности «Математика», 7 семестр, 2011-2012 уч г., Одо требования к зачету, 39.3kb.
- На конференции будут рассматриваться вопросы: российский и зарубежный опыт использования, 34.77kb.
- Авторская речь как объясняющий фактор построения драматургического текста, 552.53kb.
- Восточные языки и культуры, 7340.53kb.
- Восточные языки и культуры, 7407.21kb.
- Программа курса составитель: проф. В. В. Красных вводные замечания курс «Этнопсихолингвистика, 154.08kb.
КУРС ПРОЕКТИРОВАНИЕ ЯЗЫКОВ И ТРАНСЛЯТОРОВ
ВОПРОСЫ ПО ТЕОРИИ
2010
1. Бэкусовы ноpмальные фоpмы. Контекстно-свободные
(КС) гpамматики и языки, пpимеpы. Pазновидности КС-гpамматик.
Выводы в КС-грамматиках, дерево вывода. Неоднозначные КС-грамматики,
примеры. Теоремы о распознавании пустоты КС-языков,
достижимости нетеpминалов и бесконечности КС-языков.
Пpиведенные КС-гpамматики. Операции над КС-языками, теоремы.
Класс КС-языков. Пеpесечение КС-языков.
2. Стековая память, автоматы с магазинной памятью (МП),
пpимеpы. Теорема о классе языков, допускаемых МП-автоматами.
Детеpминиpованные КС-языки, пpимеp недетеpминиpованного КС-языка.
Синтаксический анализ КС-языков. Сентенциальные фоpмы,
основа, деpевья вывода, пpимеpы. Тактики синтаксического анализа КС-языков.
Тpудоемкость синтаксического анализа, теоpема Эpли (обсуждение).
Специальные грамматики для построения линейных анализаторов.
3. Грамматики простого предшествования символов.
Алгоритм Флойда. Анализ анализа простого предшествования путем
проставления знаков по таблице, пример.
Построение МП-анализатора, пример.
Грамматики операторного старшинства.
Задача: составить таблицу старшинства операторов по грамматике.
4. Нисходящий синтаксический анализ, пример.
LL(1)-грамматики. Распознавание LL(1)-грамматик.
Правая рекурсия и факторизация.
Пример преобразования грамматики к виду LL(1).
Алгоритм построения нисходящего МП-анализатора: задача.
5. Анализ слева направо по Кнуту. Основа по Кнуту.
LR(k)-грамматики. Теорема Кнута для k=0 и k=1, доказательство
для частного случая. Пример: построение автомата Кнута.
6. LR(k)-грамматики, примеры (для k=0 и k>0) Распознавание LR(k)
грамматик при фиксированнном k и при произвольном k.
Свойства LR(k)-грамматик. Квадратичный и линейный LR(k)-анализ.
Класс языков, порождаемых LR(k)-грамматиками.
7. Неразрешимая проблема Поста. Проблема пустоты пересечения
КС-языков, теорема. Теорема о распознавании пустоты дополнения к КС-языкам,
ход доказательства. Проблема распознавания однозначности КС-грамматик.
Проблема эквивалентности КС-грамматик.
УКАЗАНИЯ по подготовке
Требуется знать по памяти все определения, все теоремы и все примеры,
приведенные в лекциях.
Требуется разобраться с доказательствами и уметь изложить
идею доказательств либо провести доказательство для простого
частного случая.
ПОСОБИЕ ДЛЯ ПОДГОТОВКИ
В.И.Сердобольский. Теория формальных языков. Синтаксический анализ
и трансляция. МИЭМ, библиотека.
См. также на URL serd-miem.narod.ru