СИСТЕМНОЕ ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ: ВОПРОСЫ К ЭКЗАМЕНУ 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) ОК-грамматики. Примеры работы.