Зачем и о чём. Рано или поздно в своей работе мы сталкиваемся с задачами сложной обработки текста, требующих распознавания каких-либо языковых понятий: форматирование кода по принятым правилам, проверка соответствия названий подпрограмм, переменных, постоянных каким-то соглашениям, разбор конфигурационных файлов, а то и усовершенствование используемых языков программирования путём написания препроцессоров. Эти задачи встречаются довольно часто, но как правило предлагаемое решение подразумевает изучение довольно тяжеловесных инструментов. Как правило, это YACC или что-то подобное. После изучения, что это означает для написания кода, обычно выясняется, что предлагаемый подход мало того, что плохо стыкуется с тем, как мы обычно разрабатываем наши программы. В итоге в лучшем случае задача откладывается "до лучших времён", а в худшем - пишется код "к случаю" на основе регулярных выражений, а то и просто подсчитывающий разность числа открывающих и закрывающих скобок. Нижеследующее - попытка рассказать о более простых подходах, которые возможно воплотить самостоятельно в том виде, в котором это может быть удобно. Постановка задачи. Исследователи естественных языков обратили внимание на то, что задача понимания языка легко распадается на распознавание и осмысление, истолкование. Так, многим известны следующие отрывки, воспринимающиеся как написанные русским языком, но совершенно бессмысленные с обыденной точки зрения: "Глокая куздра штеко будланула бокра и курдячит бокрёнка." "Кудматая бокра штеко будланула тукастенького бокрёночка." "Глокая куздра штеко кудланула бокра и курдячит бокрёнка." "Калушата присяпали и Бутявку стрямкали. И подудонились. А Калуша волит: <<Оее! Оее! Бутявка-то некузявая!>>" "Варкалось. Хливкие шорьки Пырялись по наве, И хрюкотали зелюки, Как мюмзики в мове." Эти примеры показывают, что под языком скорее следует понимать множество предложений, которые его составляют, а то смысловую часть рассматривать отдельно. В естественном случае предложения языка следуют каким-то правилам, которые мы называем грамматическими. Именно так мы и будем понимать нашу задачу: определить, следует ли заданная строка заданному набору правил. Контекстно-свободные грамматики. Для простоты мы пропустим чересчур сложные правила и перейдём сразу к таким, которые достаточно просты для работы и достаточно сложны, чтобы описывать почти все наиболее часто встречаемые языки. Для этого введём несколько строгих понятий. Мы рассматриваем строки, последовательности конечной длины (возможно - нулевой), составленные из конечного набора знаков. Знаками не обязательно являются буквы, пробелы и знаки препинания, это могут быть целые слова, точки и тире, октеты бит или даже сетевые пакеты обозримого числа видов. Соответственно, мы можем распознавать не только язык, похожий на естественный, но и язык Морзе, язык сетевых пакетов и даже язык сетевых протоколов, где предложениями являются осмысленные сеансы связи. Последовательности знаков мы обозначаем символами. Терминальный символ соответствуют ровно одному знаку определённого вида. "Терминальный" здесь означает, что символ не имеет подробного внутреннего строения в понятиях грамматики. Нетерминальные символы могут соответствовать пустым строкам, а также последовательностям (конечной длины) других символов. Правила - это законы того, какие строки символов соответствуют нетерминальным символам. Для контекстно-свободных грамматик правила записываются в виде: S -> _, если символу может соответствовать пустая строка, и S -> S_0 ... S_{n-1}, где S_0 ... S_{n-1} - терминальные или нетерминальные символы. Как работает КСГ Подразумевается, что контекстно-свободная грамматика работает следующим образом. 1. Существует выделенный начальный символ S^{(0)}, исполняющий обязанность понятия "предложение" или "слово." 2. Мы создаём строку, состояющую из начального символа: S^{(0)} 3. Мы выбираем произвольный нетерминальный символ из нашей строки S^{(k)}_0 ... S^{(k)}_i ... S^{(k)}_{l} выбираем любое правило, "раскрывающее" этот символ S^{(k)}_i = S -> S_0 ... S_n и заменяем в строке выбранный символ согласно выбранному правилу. S^{(k)}_0 ... S^{(k)}_{i-1} S_0 ... S_n S^{(k)}_{i-1} ... S^{(k)}_{l} Если правило производит пустую строку, то это соответствует простому удалению нетерминала. 4. Повторяем предыдущий шаг до тех пор, пока в строке встречаются нетерминальные символы. Как только получаем строку, не содержащую нетерминальных символов, мы получаем строку, являющуюся "предложением" или "словом" языка. Метод Унгера. Каждое правило S -> S_0 ... S_{n-1} имеет прямое истолкование: входная подстрока от точки p_0 до точки p_n следует правилу, если существует разбиение на подстроки точками p_1 ... p_{n-1}, так что p_0 <= p_1 <= ... <= p_{n-1} <= p_n, где подстроки описываются соответствующими символами, подстрока между точками p_0 и p_1 описывается символом S_0, подстрока между точками p_1 и p_2 описывается символом S_1 ... подстрока между точками p_{n-1} и p_n описывается символом S_{n-1}. Под "точкой" здесь понимается место между двумя следующими знаками, а также перед самым первым и после самого последнего. Подстрока между точками p_0 и p описывается символом S, если существует правило S -> S_0 ... S_{n-1}, описывающее эту подстроку. Подстрока между точками p_0 и p описывается терминальным символом T, если p = p_0 + 1 и терминальный символ соответствует знаку между этими точками. Подстрока между точками p_0 и p описывается правилом S -> _, где _ обозначает пустую строку, если p = p_0. Строка принадлежит языку, если она описывается начальным символом. Изложенное выше можно записать формально и более наглядно: r(S -> S_0 ... S_{n-1}, w, p_0, p_{n-1}) := 0 <= p_0 <= ... <= p_{n-1} <= l & s(S_0, w, p_0, p_1) & s(S_1, w, p_1, p_2) ... & s(S_{n-1}, s, p_{n-1}, p_n), s(S, w, p_0, p) := r(S -> S_0 ... S_{n-1}, w, p_0, p), r(S -> _, w, p_0, p) := p = p_0, s(T, w, p_0, p) := t(S) & p = p_0 + 1 & w[p_0] ~ T, где w - заданная строка, l - её длина, w[i] - i-й (отсчитывая с нуля) знак строки, символ T - терминальный. Так как целочисленные переменные ограничены неравенством 0 <= p <= l, возможно решить эти "уравнения" перебором. Более того, эти определения уже записаны в виде поиска по конечному пространству: r(S -> _, w, p_0, p) := p = p_0, r(S -> S_0 ... S_{n-1}, w, p_0, p_{n-1}) := {(p_0, ..., p_{n-1}) in [0,l]^n | 0 <= p_0 <= ... <= p_{n-1} <= l & s(S_0, w, p_0, p_1) & s(S_1, w, p_1, p_2) ... & s(S_{n-1}, w, p_{n-1}, p_n)} /= O. s(T, w, p_0, p) := p = p_0 + 1 & w[p_0] ~ T. s(S, w, p_0, p) := r(S -> S_0 ... S_{n-1}, w, p_0, p). Единственное, за чем надо следить, это за возможностью ухода в бесконечную рекурсию. Однако это легко предотвратить, достаточно запомнить при входе в процедуру, что мы уже сопоставляем заданный символ с заданной подстрокой и вернуть "нет" при повторном входе. Это соответствует обрубанию рекурсии вида A -> B A C, где B сопоставляется с пустой строкой. Очевидно, что ответ для A в таком случае может дать лишь какое-то другое правило, а для текущего ответ уже известен, и этот ответ - "нет." Обратим внимание, что раз уж мы запоминаем, сопоставляли ли мы символ с подстрокой, то мы можем запомнить и итог этого сопоставления. Это намного улучшает скорость распознавания, так как мы постоянно сопоставляем одни и те же символы с одними и теми же подстроками. Собственно, вот эта небольшая оптимизация и является причиной того, почему алгоритм Унгера почти не упоминается в учебной литературе, кроме как с примечанием "очень медленный." Дело в том, что эта оптимизация превращает алгоритм, требующий экспоненциального времени, в алгоритм, требующий полиномиального времени, что делает его вполне отвечающим сложности задачи. Использование "мемоизации," запоминания результатов вычислений для ... Комбинаторы парсеров Алгоритм Унгера, конечно, хорош, но всё же посмотрим, как мы его можем улучшить. Прежде всего обратим внимание на то, что мы можем вычислить конец подстроки, сопоставляемой с заданным символом, по её началу, то есть мы можем рассматривать p и s как отображения, дающие итогом множества возможных концов подстрок, сопоставляющихся с символом или правилом: r'(R, w, p_0) = {p | r(R, w, p_0, p)}, s'(S, w, p_0) = {p | s(S, w, p_0)}. или r'(S -> S_0 ... S_{n-1}, w, p_0) := {p | r(S -> S_0 ... S_{n-1}, w, p_0, p)}. s'(S, w, p_0) := {p | s(S, w, p_0, p)}. Исходные предикаты выражаются через принадлежность множеству: r(S -> S_0 ... S_{n-1}, w, p_0, p) <=> p <- {p | r(S -> S_0 ... S_{n-1}, w, p_0, p)}. s(S, w, p_0, p) <=> p <- {p | s(S, w, p_0, p)}. Тогда наши условия можно переписать в виде: r'(S -> _, w, p_0) = {p | r(S -> _, w, p_0, p)} = {p | p = p_0} = {p_0}. r'(S -> S_0 ... S_{n-1}, w, p_0) = {p | r(S -> S_0 ... S_{n-1}, w, p_0, p)} = {p_n | 0 <= p_0 <= ... <= p_{n-1} <= l & s(S_0, w, p_0, p_1) & s(S_1, w, p_1, p_2) ... & s(S_{n-1}, w, p_{n-1}, p_n)} = {p_n | p_1 <- s'(S_0, w, p_0) & p_2 <- s'(S_1, w, p_1) ... & p_n <- s'(S_{n-1}, w, p_{n-1})} В последнем выражении мы можем распознать повторяющийся мотив: {y | x <- X & y <- f(x)} = U {f(x) | x <- X} = u(m(f, X)), где m(f, X) - поточечное отображение множества X, u(Y) - объединение множества множеств. После введения этих очевидных обозначений, мы приходим к r'(S -> S_0 ... S_{n-1}, w, p_0) = {p_n | p_1 <- s'(S_0, w, p_0) & p_2 <- s'(S_1, w, p_1) ... & p_n <- s'(S_{n-1}, w, p_{n-1})} = u(m((p +-> s(S_{n-1}, w, p)), {p_{n-1} | p_1 <- s'(S_0, w, p_0) & p_2 <- s'(S_1, w, p_1) ... & p_{n-1} <- s'(S_{n-2}, w, p_{n-2})})) = u(m((p +-> s'(S_{n-1}, w, p)), u(m((p +-> s'(S_{n-2}, w, p)), ... u(m((p +-> s'(S_1, w, p)), s'(S_0, w, p_0))))))) Это можно обобщить ещё дальше, если заметить, что f(x) = u({f(x)}) = u(m(f, {x})), откуда s'(S_0, w, p_0) = u(m((p +-> s'(S_0, w, p)), {p_0})). Тогда r'(S -> S_0 ... S_{n-1}, w, p_0) = u(m((p +-> s'(S_{n-1}, w, p)), u(m((p +-> s'(S_{n-2}, w, p)), ... u(m((p +-> s'(S_1, w, p)), u(m((p +-> s'(S_0, w, p)), {p_0})))))))). Выглядит устрашающе, но если присмотреться, это обычная композиция функций вида z_i(x) := u(m((p +-> s'(S_i, w, p)), x)) r'(S -> S_0 ... S_{n-1}, w, p_0) = (z_{n-1} o ... o z_0)({p_0}). Для символов мы получаем: s'(T, w, p_0) = {p | s(T, w, p_0, p)} = {p | p = p_0 + 1 & w[p_0] ~ T}, то есть s'(T, w, p_0) = {p_0}, когда w[p_0] ~ T, и s'(T, w, p_0) = {} в противном случае s'(S, w, p_0) = {p | s(S, w, p_0, p)} = {p | r(S -> S_0 ... S_{n-1}, w, p_0, p)} = {p | p <- r'(S -> S_0 ... S_{n-1}, w, p_0)} = U {r'(S -> S_0 ... S_{n-1}, w, p_0)} Итого, мы получили способ, как по грамматике построить набор взаимнорекурсивных функций, сопоставляющих символы и правила. Более того, можно пойти дальше и ввести две операции, комбинирующие распознаватели так, что правилу S -> S_0 ... S_{n-1} соответствует распознаватель r" = s"_0 * ... * s"_{n-1}, а распознаватель символа S комбинирует все относящиеся правила: s = r"_0 + ... + r"_{m-1}. К примеру, если мы распознаём функциями вида r', отображающими точку во множество точек, то (r'_A * r'_B)(p) = u(m(r'_B, r'_A(p))) = u(m(r'_B, u(m(r'_A, {p})))). (r'_1 + r'_2)(p) = u({r'_1(p), r'_2(p)}) = r'_A(p) U r'_B(p). Если же мы распознаём функциями вида r', отображающими множество точек во множество точек, то (r'_A * r'_B)(P) = u(m(r'_B, u(m(r'_A, P)))). (r'_1 + r'_2)(P) = u({u(m(r'_1, P)), u(m(r'_2, P))}) = u(u(m(r'_1, P)), u(m(r'_2, P))) = m(r'_1, P) U m(r'_2, P). УСТРАНЕНИЕ ЛЕВОЙ РЕКУРСИИ! GLL. Этот способ описан в "turning failures into list of successes" Монады? Этот способ страдает от сваливания в бесконечную левую рекурсию сильнее. Устранение левой рекурсии возможно, но непросто. Мы вернёмся к этому чуть позже. А пока... Обратим внимание на то, что как правило нам не нужны неоднозначности, так как они порождают неопределённость. Если мы видим, что какая-то словосочетание началось, то мы хотим точно, однозначно знать, где оно заканчивается. Из этого следует, что функции r'(R, w, p) и s'(S, w, p) возвращают множества из одного элемента либо пустые. Последнее обстоятельство очень сильно упрощает написание кода, так как позволяет использовать более простые типы данных (опциональный тип, где поддерживается), что в особенности на языках с плохой поддержкой сложных типов данных. Детерминистский подход, PEG. Несмотря на то, что однозначные грамматики сильно упрощают жизнь, остаётся вопрос висящего "иначе:" if a = 0 then if b = 0 then this else that может быть разобрано как if a = 0 then (if b = 0 then this) else that или как if a = 0 then (if b = 0 then this else that) Вопрос о принадлежности "иначе" возникает из-за неоднозначности грамматик, содержащих такие правила: statement = "if", expression, "then", statement, "else", statement; statement = "if", expression, "then", statement. Подобная неоднозначность разрешается обычно правилом наиболее длинной подстроки: при возникновении неоднозначности первенство отдаётся наиболее длинной подстроке, которая может быть распознана. Однако в грамматике так, как мы её определили, не существует понятия первенства: все правила равны и действуют одновременно и одинаково. Если же посмотреть с другой стороны, то чуть выше мы пришли к такой записи правил распознавания, которые описывают язык не хуже прежних: s = (s_A * s_B) + (s_C * s_D). Эта запись допускает определение "+" иначе, чем через объединение множеств, важно то, чтобы оно было чем-то похоже. В частности, мы можем отбросить второе значение, если удовлетворены первым. Если мы определим "+" таким образом, то получим, что (s_A + s_B)(p) = s_A(p), если s_A(p) /= {} (s_A + s_B)(p) = s_B(p), если s_A(p) = {}. LL(1).