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

Лектор: Александр Охотин

Язык курса: русский

Краткое описание курса:
Теория формальных языков изучает математические модели синтаксиса. Языки, естественные или искусственные, задаются формальными грамматиками, описывающими построение синтаксически правильных предложений. Руководствуясь грамматикой, алгоритм синтаксического анализа производит разбор предложений на данном языке. В курсе представлены математические основы формальных грамматик, с особенным упором на алгоритмы синтаксического анализа и их вычислительную сложность.

Лекции:
1–2: суббота, 10 октября 2009 г. (17:20–20:40);
 3–5: воскресенье, 11 октября 2009 г. (11:15–17:10);
 Дополнительная: среда, 14 октября 2009 г. (11:15, в ауд 66 СПбГУ);
6–7: суббота, 17 октября 2009 г. (17:20–20:40);
 8–10: воскресенье, 18 октября 2009 г. (11:15–17:10).

Содержание лекций и литература к ним:

  • 1. Языки вообще. Разбор естественных языков и языков программирования. Формальные языки и действия над ними. Понятие о регулярных выражениях и конечных автоматах. (видеозапись)
  • 2. Бесконтекстные грамматики. Примеры. Определение бесконтекстных грамматик через языковые уравнения и через перезапись. Ограничения бесконтекстных грамматик. Свойства, которыми должны обладать формальные грамматики. Сложность известных алгоритмов разбора для бесконтекстных грамматик, их частных случаев и их обобщений. (видеозапись)
  • 3. Замкнутость бесконтекстных языков относительно объединения, сцепления, звёздочки, циклического сдвига и пересечения с регулярными языками. Доказательство непредставимости языков бесконтекстными грамматиками: лемма накачки, непредставимость языка $ \{a^n b^n c^n \mid n \geqslant 0\} $. Разрешимость задачи пустоты и задачи принадлежности для бесконтекстных грамматик. (видеозапись)
  • 4. Незамкнутость бесконтекстных языков относительно пересечения и объединения. Неразрешимость пустоты пересечения бесконтекстных грамматик. Конъюнктивные грамматики, определение через языковые уравнения и через перезапись. Примеры конъюнктивных грамматик для языков $ \{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. Равносильность двух определений конъюнктивных грамматик. Приведение конъюнктивной грамматики к нормальному виду: удаление пустых конъюнктов, удаление единичных конъюнктов. Алгоритм разбора Кокка--Касами-–Янгера, работающий за время $ O(n^3) $. (видеозапись)
  • Дополнительная лекция: Булевы грамматики. Хорошо обоснованная семантика. (слайды)

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

  • 6. Булевы грамматики, семантика единственного решения в сильном смысле. Примеры булевых грамматик для языков $ \{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.

  • 7. Узкое место алгоритма Кокка--Касами-–Янгера. Разбор через умножение матриц. Метод Штрассена умножения матриц за время $ 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.

  • 8. Однозначные грамматики. Лемма Огдена и доказательство существенной неоднозначности бесконтекстного языка $ \{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.

  • 9. Разбор бесконтекстных языков булевой схемой: алгоритм Брента--Гольдшлягера-–Риттера, строящий схему высоты $ 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.

  • 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.

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

Задачи для получения оценки за курс:

(на тройку надо полностью решить две из пяти задач, на четвёрку -–- три, на пятёрку -–- четыре)

  • 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 канадских долларов)

Прикрепленные файлыРазмер
boolean_spbsu_talk.pdf1.65 Мб
formal_grammars_pdmi_2010_05_22.pdf1016.51 кб