Формальные языки и синтаксический анализ

Общая информация
ЛекторА. Охотин
Семестросень 2009
Дата начала10.10.2009
Количество пар10
Язык курсарусский
Видеоhttp://video.yandex.ru/users/pdmicsclub/collection/5/
Аннотация Теория формальных языков изучает математические модели синтаксиса. Языки, естественные или искусственные, задаются формальными грамматиками, описывающими построение синтаксически правильных предложений. Руководствуясь грамматикой, алгоритм синтаксического анализа производит разбор предложений на данном языке. В курсе представлены математические основы формальных грамматик, с особенным упором на алгоритмы синтаксического анализа и их вычислительную сложность.

Общая литература к курсу:

Задачи для получения оценки за курс: (на тройку надо полностью решить две из пяти задач, на четвёрку --- три, на пятёрку --- четыре)
  • 1. Построить бесконтекстную грамматику для языка $ L=\{a^{k_1}b \ldots a^{k_\ell}b \mid \ell \geqslant 1, \; k_i \geqslant 0, \; \exists i: k_i=i\} $. Показать, что построенная грамматика неоднозначна.
  • 2. Построить однозначную булеву грамматику для языка $ L $ из первой задачи.
  • 3. Показать, что если языки $ K $ и $ L $ над алфавитом $ \{a, b\} $ --- линейные конъюнктивные (т.е., представимы конъюнктивной грамматикой с правилами вида $ A \to u_1 B_1 v_1 \& \ldots \& u_n B_n v_n $ и $ A \to w $), то язык $ KcL $ (где $ c $ --- дополнительный символ) --- тоже линейный конъюнктивный.
  • 4. Для произвольной булевой грамматики $ G $ построить алгоритм, который, получив на входе строку $ w $, будет определять, порождает ли $ G $ хотя бы один из циклических сдвигов строки $ w $. Время работы алгоритма должно быть не более чем кубическим от длины $ w $. (на пятёрку с плюсом: быстрее, чем кубическим) (на четвёрку сойдёт время $ n^{3.81} $, для этого нетрудно приспособить готовый алгоритм из лекций) (замечание: замкнуты ли булевы грамматики относительно циклического сдвига --- неизвестно)
  • 5. Доказать, что для конъюнктивных грамматик неразрешима следующая задача: по данной конъюнктивной грамматике над алфавитом $ \{a, b\} $ определить, порождает ли она в точности язык $ \{a^n b^n | n \geqslant 0\} $, или же какой-то иной язык. (на четвёрку --- то же самое для языка $ \{\epsilon\} $).
Примеры задач для дальнейших исследований (уровня хорошей дипломной работы или неплохой статьи, написанной аспирантом)
  • Рассмотреть LL(k) линейные булевы грамматики и проверить, могут ли они задать какой-либо язык, не представимый булевой формулой над LL(1) линейными бесконтекстными языками. (предположительно, нет)
  • Научиться строить однозначные конъюнктивные грамматики над однобуквенным алфавитом для широких классов языков. Для этого надо сперва обстоятельно изучить существующие теоремы о построении неоднозначных конъюнктивных грамматик (Еж, DLT 2007; Еж и Охотин, CSR 2007, STACS 2008).
  • Рассмотреть "магазинные автоматы с явными метками" (visibly pushdown automata, Алур и Мадхусудан, 2004) и научиться преобразовывать их к линейным конъюнктивным грамматикам.
Большая практическая задача
    Разработать практический генератор синтаксических анализаторов для булевых грамматик. Вся теория есть, алгоритмы построены, их правильность доказана, пробные реализации успешно работают. Осталось разработать и написать программу, которой было бы удобно пользоваться программистам.
Большие теоретические задачи (за каждую определена награда в 360 канадских долларов)
  • Научиться доказывать для некоторых языков, что эти языки не порождаются никакой булевой грамматикой.
  • Определить, замкнуты ли конъюнктивные языки относительно дополнения.

Лекции Подсказка: слайды, видеозапись и другие материалы лекции доступны со страницы лекции, попасть на которую можно, нажав на её название.

1. Лекция 1
(10.10.2009 - 17:20 - 18:55)
Языки вообще. Разбор естественных языков и языков программирования. Формальные языки и действия над ними. Понятие о регулярных выражениях и конечных автоматах. http://video.yandex.ru/users/pdmicsclub/view/17/
2. Лекция 2
(10.10.2009 - 19:05 - 20:40)
Бесконтекстные грамматики. Примеры. Определение бесконтекстных грамматик через языковые уравнения и через перезапись. Ограничения бесконтекстных грамматик. Свойства, которыми должны обладать формальные грамматики. Сложность известных алгоритмов разбора для бесконтекстных грамматик, их частных случаев и их обобщений. http://video.yandex.ru/users/pdmicsclub/view/18/
3. Лекция 3
(11.10.2009 - 11:15 - 12:50)
Замкнутость бесконтекстных языков относительно объединения, сцепления, звёздочки, циклического сдвига и пересечения с регулярными языками. Доказательство непредставимости языков бесконтекстными грамматиками: лемма накачки, непредставимость языка $ \{a^n b^n c^n \mid n \geqslant 0\} $. Разрешимость задачи пустоты и задачи принадлежности для бесконтекстных грамматик. http://video.yandex.ru/users/pdmicsclub/view/16/
4. Лекция 4
(11.10.2009 - 13:00 - 14:35)
Незамкнутость бесконтекстных языков относительно пересечения и объединения. Неразрешимость пустоты пересечения бесконтекстных грамматик. Конъюнктивные грамматики, определение через языковые уравнения и через перезапись. Примеры конъюнктивных грамматик для языков $ \{a^n b^n c^n \mid n \geqslant 0\} $, $ \{wcw \mid w \in \{a,b\}^*\} $ и $ \{a^{4^n} \mid n \geqslant 0\} $.

A. Okhotin, “Conjunctive grammars”, Journal of Automata, Languages and Combinatorics, 6:4 (2001), 519--535. А. Охотин, “Конъюнктивные грамматики и системы языковых уравнений”, Программирование, 28:5 (2002), 3--11.
5. Лекция 5
(11.10.2009 - 15:35 - 17:10)
Равносильность двух определений конъюнктивных грамматик. Приведение конъюнктивной грамматики к нормальному виду: удаление пустых конъюнктов, удаление единичных конъюнктов. Алгоритм разбора Кокка-Касами-Янгера, работающий за время $ O(n^3) $.

Дополнительная лекция: Булевы грамматики. Хорошо обоснованная семантика.

V. Kountouriotis, Ch. Nomikos, P. Rondogiannis, “Well-founded semantics for Boolean grammars”, Information and Computation, 207:9 (2009), 945--967.

application/pdf icon
boolean_spbsu_talk.pdf
http://video.yandex.ru/users/pdmicsclub/view/39/
6. Лекция 6
(17.10.2009 - 17:20 - 18:55)
Булевы грамматики, семантика единственного решения в сильном смысле. Примеры булевых грамматик для языков $ \{a^i b^j c^j \mid i \neq j, j \neq k, i \neq k\} $ и $ \{ww \mid w \in \{a,b\}^*\} $. Нормальный вид булевых грамматик. Алгоритм Кокка-Касами-Янгера в редакции для булевых грамматик.

A. Okhotin, “Boolean grammars”, Information and Computation, 194 (2004) 19-48.

http://video.yandex.ru/users/pdmicsclub/view/24/
7. Лекция 7
(17.10.2009 - 19:05 - 20:40)
Узкое место алгоритма Кокка--Касами--Янгера. Разбор через умножение матриц. Метод Штрассена умножения матриц за время $ O(n^{\log_2 7}) $.

L. G. Valiant, “General context-free recognition in less than cubic time”, Journal of Computer and System Sciences, 10:2 (1975), 308--314; A. Okhotin, “Fast parsing for Boolean grammars: a generalization of Valiant's algorithm”, TUCS TR 953, принято на DLT 2010.

http://video.yandex.ru/users/pdmicsclub/view/31/
8. Лекция 8
(18.10.2009 - 11:15 - 12:50)
Однозначные грамматики. Лемма Огдена и доказательство существенной неоднозначности бесконтекстного языка $ \{a^i b^j c^j \mid i=j $ или $ j=k\} $. Разбор однозначных булевых грамматик за время $ O(n^2) $.

A. Okhotin, “Unambiguous Boolean grammars”, Information and Computation, 206:9--10 (2008), 1234--1247.

http://video.yandex.ru/users/pdmicsclub/view/25/
9. Лекция 9
(18.10.2009 - 13:00 - 14:35)
Разбор бесконтекстных языков булевой схемой: алгоритм Брента--Гольдшлягера--Риттера, строящий схему высоты $ O(\log^2 n) $ с $ O(n^6) $ элементами. Реализация алгоритма на машине Тьюринга с использованием $ O(\log^2 n) $ бит памяти. Понятие P-полного языка, P-полнота задачи о значении схемы. Булева грамматика для P-полного языка.

R. P. Brent, L. M. Goldschlager, “A parallel algorithm for context-free parsing”, Australian Computer Science Communications, 6:7 (1984), 7.1--7.10; W. Rytter, “On the recognition of context-free languages”, FCT 1985, LNCS 208, 315--322; R. E. Ladner, “The circuit value problem is log space complete for P”, SIGACT News, 7:1 (1975), 18--20; A. Okhotin, “A simple P-complete problem and its representations by language equations”, MCU 2007, 267--278.

http://video.yandex.ru/users/pdmicsclub/view/23/
10. Лекция 10
(18.10.2009 - 15:35 - 17:10)
Рекурсивный спуск для бесконтекстных грамматик, его обобщение для конъюнктивных и булевых грамматик. Достижение линейного времени выполнения. Понятие об обобщённом LR-разборе.

A. Okhotin, “Recursive descent parsing for Boolean grammars”, Acta Informatica, 44:3--4 (2007), 167--189; M. Tomita, “An efficient augmented context-free parsing algorithm”, Computational Linguistics, 13:1 (1987), 31--46. A. Okhotin, “Generalized LR parsing algorithm for Boolean grammars”, International Journal of Foundations of Computer Science, 17:3 (2006), 629--664.

http://video.yandex.ru/users/pdmicsclub/view/27/
Ваша оценка: Пусто Средняя: 5 (3 голосов)
Share |