СИСТЕМНОЕ ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ: ВОПРОСЫ К ЭКЗАМЕНУ

1) Компьютерная обработка текстов. Таблицы кодировки 7/8-битные. 
2) Транслитерация кирилицы латиницей. Unicode, UCS, UTF-7/8/16. 
3) Способы задания языка. Грамматики. Выводимая цепочка. НФБН. 
4) Вывод цепочки. Левый (правый) вывод. Однозначность грамматики. Дерево 
   разбора.
5) Постфиксная (обратная польская) запись. Левая рекурсия и ее устранение. 
   Рекурсивный спуск. Пример компилятора рекурсивного спуска.
6) Иерархия Хомского. Способы задания регулярных языков. Регулярные множества.
7) КА. ДКА и НКА. Преобразование НКА в ДКА.
8) Минимизация КА. Лемма о разрастании для регулярных языков. Программа 
   Lex/Flex. Свойства регулярных языков. Регулярные множества.
9) Стековый (магазинный) КА. Контекстно-свободные языки. Построение НМКА по 
    заданной грамматике и наоборот. Лемма о разрастании для КС-языков.
10) Преобразование КС-языков. Удаление бесполезных символов и правил. 
    Удаление $\epsilon$-правил.  Устранение циклов и цепных правил. Устранение 
    левой рекурсии.
11) Нормальные формы Хомского и Грейбаха для КС-языков. Назначение алгоритмов 
    Кока-Янгера-Касами и Ерли, их свойства. LL(k)-языки и грамматики. 
12) Множества FIRST и FOLLOW. Алгоритм работы анализатора. Пример 
    LL(1)-разбора.
13) Разбор снизу-вверх. Сдвиг-свертка. Грамматики простого и операторного 
    предшествования. 
14) LR(k)-языки и грамматики. Схема работы LR(k)-анализатора.
15) Пример LR(1)-разбора. SLR(1) и LALR(1) языки. 
16) Построение канонических LR(1)-таблиц. 
17) Построение SLR(1) и LALR(1)-таблиц. Программа Yacc/Bison. Устранение 
    конфликтов. GLR-грамматики.
18) Синтаксически управляемая трансляция.
19) Организация вызова подпрограмм и прерываний. Команды ассемблера CALL, 
    INT, RET, ENTER и LEAVE. Регистры SP и BP. Соглашения паскаля и си.
20) Отладка и профилирование программ.
21) Пример создания простой программы-калькулятора [yacc/bison].
22) Поддержка односимвольных переменных [yacc/bison].
23) Поддержка функций и констант [yacc/bison].
24) Генерация кода [yacc/bison].
25) Поддержка операторов [yacc/bison].
26) Поддержка определения новых поддпрограмм [yacc/bison].
27) Система восстановления после ошибок и поддержка работы с символьными 
    строками [yacc/bison].
28) Системы версионного контроля. Основные особенности.
29) Программа subversion.
30) Программы для управления проектами.
31) Использование языка пролог для работы с КС-языками.
32) ОК-грамматики. Примеры работы.