|
ИСТИНА |
Войти в систему Регистрация |
ФНКЦ РР |
||
Формальные языки и грамматикиучебный курс
- Автор: Борисенко Владимир Витальевич
- Год создания: 2023
- Организация: МГУ имени М.В. Ломоносова
- Описание: Определение формального языка и формальной грамматики. Иерархия грамматик Хомского. Примеры контекстно зависимых и контекстно свободных языков. Левые и правые выводы в КС-языках, синтаксические деревья, лемма о разрастании. Неоднозначные и однозначные грамматики, пример существенно неоднозначного языка. Нормальная форма Хомского для КС-грамматик. Автоматные языки и право/леволинейные грамматики. Регулярные языки и теорема Клини совпадении классов регулярных и автоматных языков. Недетерминированные и детерминированные конечные автоматы, алгоритм построения детерминированного конечного автомата, эквивалентного недетерминированному. Алгоритм минимизации детерминированного КА и изоморфизм всех минимальных ДКА, задающих данный язык. Алгоритмически разрешимые и неразрешимые проблемы теории формальных языков. Задача разбора как задача, противоположная выводу. Основные типы алгоритмов разбора: рекурсивный, или нисходящий, или LL(1)-разбор. Критерий того, что КС-грамматика допускает LL(1)-разбор. Избавление от непосредственной рекурсии. Восходящий, или LR(1)-разбор, или разбор на конечном автомате со стеком (МП-автомате). Понятие LR-процесса. Построение системы состояний и переходов для LR(0) и LR(1)-разбора, алгоритм работы LR(1)-парсера. Использование утилит LEX и YACC для реализации LR(1)-парсера при написании компиляторов.
- Добавил в систему: Борисенко Владимир Витальевич
Преподавание курса
- 16 сентября 2024 - 30 декабря 2024 Борисенко Владимир Витальевич
- МГУ имени М.В. Ломоносова, Механико-математический факультет
- обязательная, по выбору (спецкурс), лекции, 28 часов
- Автор: Борисенко Владимир Витальевич