22:40 

Вопросы по ЛОИ

Префект
Во всем виноват - староста.
Вопросы к экзамену по курсу «Лингвистические основы информатики»
Весенний семестр, 2009 г.

1. КС-грамматики и языки. Вывод. Дерево вывода. Левосторонний и правосторонний вывод. Неоднозначные грамматики и языки.
2. Теорема о подстановке и ее следствия.
3. Теорема о накачке и ее следствия.
4. Теорема об Е-свободной грамматике.
5. Распознавание КС-языков методом динамического программирования.
6. Преобразования КС-грамматик: устранение левой рекурсии, левая факторизация.
7. МП-автоматы. Варианты распознавания. ДМПА и НМПА, их неэквивалентность.
8. Распознаваемость КС-языков МП-автоматами.
9. Идея синтаксического анализа. Два способа анализа. Использование МП-автомата для нисходящего анализа.
10. Множества FIRSТ, FОLLОW и SЕLЕСT. Алгоритмы их построения.
11. Построение управляющей таблицы МП-автомата. LL(1)-грамматики.
12. НисходящиЙ анализ методом рекурсивного спуска.
13. Идея восходящего анализа. Основа. Свертка. Обрезка левого куста. Метод перенос-свертка. Положение текущей основы в стеке. Конфликты перенос-свёртка и свёртка-свёртка.
14. 0тношения предшествования. Правило распознавания основы по отношениям предшествования.
15. Языки выражений и операторные грамматики. Отношения операторного предшествования. Анализ приоритета операторов.
16. Таблицы приоритетов. Распознавание ошибок. Граф приоритетов. Функции приоритета.
17. Схема LR-анализа. Состояния. Функции ACTION и GОТО.
18. Активные префиксы. LR(0)-пункты. Теорема об LR(0)-автомате.
19. Следствия из теоремы об LR(0)-автомате.
20. Анализ на основе LR(0)-автомата. SLR-анализ.
21. LR(1)-автомат. Канонический LR-анализ. LALR(1)-анализ.
22. Использование неоднозначных грамматик в LR-анализе. Примеры неоднозначностей, разрешимых при LR-анализе. Обработка синтаксических ошибок.
23. Наследуемые и синтезируемые атрибуты грамматических символов. Атрибутная грамматика. Граф зависимости. Топологическая сортировка.
24. Синтаксическое дерево, даг. Атрибутная грамматика для построения дага. Проверка существования узла.
25. S-атрибутные грамматики. Реализация при восходящем анализе.
26. L-атрибутные грамматики. Вычисление атрибутов при обходе в глубину. Схемы трансляции.
27. Устранение левой рекурсии из схемы трансляции.
28. Реализация транслятора, совмещённого с нисходящим анализатором.
29. L-атрибутные грамматики: вычисление при восходящем анализе. Маркеры. Доступность атрибутов в стеке.
30. Примеры атрибутных грамматик, не вычислимых в ходе синтаксического анализа.
31. Виды семантических проверок. Ошибки, не распознаваемые при компиляции.
32. Базовые типы, конструкторы и выражения типа. Представление выражения типа дагом. Эквивалентность выражений типа.
33. Атрибутная грамматика для проверки типов.
34. Преобразование выражений типа. Полиморфизмы.

URL
   

Сообщество имени П.Г.Конторовича™

главная