Теория формальных языков и компиляторов (ВИ-01) — Вопросы к экзамену
Вопросы к экзамену по курсу «Теория формальных языков и компиляторов»
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. Регулярные выражения.
Пример задачи
Дан язык: L={a+b*}.
1. Привести примеры 5 строк из этого языка.
2. Построить граф.
3. Построить конечный автомат K={S, Σ, s0, δ, F}. Определить, является ли он детерминированным.
4. Построить табличное представление функции переходов δ.
5. Определить последовательность состояний автомата при разборе цепочки α=aabbb и реакцию автомата на эту цепочку.
6. Построить грамматику, порождающую данный язык. Определить класс грамматики по Хомскому.