Формальные грамматики 2014 — различия между версиями
Okhotin (обсуждение | вклад) (→Лекция 11: Разбор сверху вниз) |
Okhotin (обсуждение | вклад) (→Содержание лекций) |
||
Строка 101: | Строка 101: | ||
=== LR(k) анализ и детерминированные языки === | === LR(k) анализ и детерминированные языки === | ||
− | === | + | === Обобщённый LR; автоматы, управляемые входом === |
+ | |||
+ | === Вычислительная сложность разбора === | ||
=== Разрешимость свойств грамматик === | === Разрешимость свойств грамматик === |
Версия 09:54, 24 сентября 2014
Курс «Формальные грамматики»: сентябрь 2014 г., 15 лекций, лектор: Александр Охотин (университет Турку, Финляндия).
Содержание
- 1 Содержание лекций
- 1.1 Лекция 1: Введение, регулярные языки
- 1.2 Лекция 2: Обыкновенные грамматики
- 1.3 Лекция 3: Свойства обыкновенных грамматик
- 1.4 Лекция 4: Представления обыкновенных грамматик
- 1.5 Лекция 5: Конъюнктивные грамматики
- 1.6 Лекция 6: Однозначные грамматики
- 1.7 Лекция 7: Линейные грамматики
- 1.8 Лекция 8: Многокомпонентные грамматики, логика FO(LFP)
- 1.9 Лекция 9: Табличные алгоритмы синтаксического анализа
- 1.10 Лекция 10: Табличные алгоритмы синтаксического анализа (окончание)
- 1.11 Лекция 11: Разбор сверху вниз
- 1.12 LR(k) анализ и детерминированные языки
- 1.13 Обобщённый LR; автоматы, управляемые входом
- 1.14 Вычислительная сложность разбора
- 1.15 Разрешимость свойств грамматик
- 2 Упражнения
Содержание лекций
Лекция 1: Введение, регулярные языки
Математические модели синтаксиса. Формальные языки. Детерминированные и недетерминированные конечные автоматы, регулярные выражения, их равносильность. Примеры. Замкнутость относительно основных действий. Нерегулярные языки.
Файл:Formal grammars 2014 lecture 1.pdf
Лекция 2: Обыкновенные грамматики
Обыкновенные формальные грамматики (в терминологии Хомского, «бесконтекстные»). Определения через перезапись строк, через деревья разбора, через логический вывод и через языковые уравнения. Равносильность определений. Примеры грамматик. Замкнутость относительно объединения, конкатенации, звёздочки, а также циклического сдвига.
Файл:Formal grammars 2014 lectures 2 3 4.pdf (редакция от 16 сентября, добавлены все недостающие разделы)
Лекция 3: Свойства обыкновенных грамматик
Замкнутость относительно пересечения с регулярными языками. Языки, не представимые грамматиками. Лемма накачки, лемма Огдена. Грамматики над односимвольным алфавитом. Нормальный вид Хомского.
Лекция 4: Представления обыкновенных грамматик
Нормальный вид Грейбах. Нормальный вид Розенкранца. Теорема Хомского--Шюценберже о представлении обыкновенных языков через язык Дика. Теорема Грейбах о «самом сложном языке».
Лекция 5: Конъюнктивные грамматики
Определения конъюнктивных грамматик через логический вывод, перезапись термов, деревья разбора и языковые уравнения. Примеры грамматик: wcw, объявление перед использованием, степени четвёрки. Приведение к нормальному виду Хомского. Понятие о булевых грамматиках.
Файл:Formal grammars 2014 lecture 5.pdf
Лекция 6: Однозначные грамматики
Неоднозначность в естественных языках и языках программирования. Комбинаторные и аналитические методы доказательства существенной неоднозначности.
Файл:Formal grammars 2014 lecture 6.pdf
Лекция 7: Линейные грамматики
Обыкновенные линейные грамматики, лемма накачки для них. Линейные конъюнктивные грамматики и клеточные автоматы, их равносильность. Лемма Терье.
Файл:Formal grammars 2014 lecture 7.pdf
Лекция 8: Многокомпонентные грамматики, логика FO(LFP)
Грамматики обёртывания пар и грамматики надстройки деревьев (tree-adjoining grammars). Логика первого порядка над позициями в строке FO(LFP), представление грамматик в этой логике. Алгоритм проверки истинности формул логики FO(LFP) как прототип алгоритмов синтаксического анализа.
Файл:Formal grammars 2014 lecture 8.pdf
Лекция 9: Табличные алгоритмы синтаксического анализа
Алгоритм Кокка-Касами-Янгера. Использование умножения матриц для ускорения алгоритма. Умножение матриц по методу Штрассена и по методу Арлазарова и др.
Файл:Formal grammars 2014 lectures 9 10.pdf (всё есть, но многoe нуждаeтся в редактировании; новая редакция будет позднее)
Лекция 10: Табличные алгоритмы синтаксического анализа (окончание)
Разбор через умножение матриц (алгоритм Валианта). Разбор однозначных грамматик за квадратичное время. Разбор для грамматик обёртывания пар.
Лекция 11: Разбор сверху вниз
LL(k) анализ для обыкновенных грамматик, рекурсивный спуск. Удаление пустых правил из LL-грамматик. Языки, не представимые LL-грамматиками. Теорема Розенкранца--Стирнса о регулярном объединении LL-языков.
Файл:Formal grammars 2014 lecture 11.pdf
LR(k) анализ и детерминированные языки
Обобщённый LR; автоматы, управляемые входом
Вычислительная сложность разбора
Разрешимость свойств грамматик
Упражнения
Задание 1: к 22 сентября
- Построить обыкновенную грамматику для языка всех палиндромов: . Показать, как строка выводится с помощью перезаписи строк. Показать, что эта же строка принадлежит наименьшему решению системы языковых уравнений, построив несколько шагов последовательности .
- Доказать, что не существует обыкновенной грамматики для языка
- Построить конъюнктивную грамматику для языка .
- Построить однозначную обыкновенную грамматику для языка
- Является ли язык линейным конъюнктивным?
- Пусть --- язык Дика над алфавитом . Существует ли грамматика обёртывания пар для языка ?
- Построить грамматику 1-го порядка для языка .