Формалки 12

Рекурсивные автоматы, они же РСМки, по-русски будут называться рекурсивным автоматом. Сейчас мы попробуем поговорить о, в каком-то смысле, семантике этого автомата. Примерно в тех же терминах, в каких мы говорили о семантике, то есть о работе конечного автомата. Там мы ввели понятие конфигурации и попытались описать работу автомата как переход между конфигурациями, пока он потихоньку подъедает строчку. Здесь попробуем сделать то же самое.

Для этого нам понадобится сперва немножко поговорить про интуицию того, что происходит. Давайте я нарисую тот пример, который у меня был. У меня было нулевое состояние, что-то типа $AN_1B$, и для $N_1$ у меня была какая-то вот такая штуковина $CSD$. Здесь, видимо, 4, 5. Что-то такое.

В принципе, мы можем начать... Давайте сразу предположим, что у меня есть какая-то цепочка входная. На самом начальном этапе мы можем смотреть на рекурсивный автомат как на обычный конечный автомат, и понимать, что в целом происходит что-то очень похожее на то, что должно происходить в конечном автомате. То есть, условно говоря, начинаем мы, видимо, со стартового состояния стартового бокса, и, соответственно, если мы видим переход по терминалу, и у нас в цепочке есть такой же терминал, ну, видимо, мы должны просто сесть и перейти в следующее состояние. В целом здесь действительно ничего более сложного происходить не будет.

А вот дальше мы находимся в каком-то состоянии, и у нас из него есть ребро, которое помечено нетерминалом. И нетерминалов у нас, очевидно, во входной цепочке, в общем-то, нет. Ну, как бы по определению практически. Значит, нужно с этим что-то делать. Чтобы понять, что с этим делать, можно попробовать посмотреть на вот эти конструкции как в каком-то смысле прообраз того, как бы вы писали синтаксический анализатор, если бы писали его руками через что-то похожее на рекурсивный спуск. Писали наверняка. Ну, по крайней мере, задачка наверняка такая была, а дальше уже вопрос писали или не писали.

Соответственно, у нас здесь получается что? Что у нас есть какая-то функция, которая должна распознавать нетерминал, то есть $A$. Вот буквально, пусть она от цепочки, она выглядит как? Не буду выписывать полностью, тем не менее: откусить терминальчик $a$, а потом вызвать функцию, соответствующую распознаванию нетерминала $N_1$ от остатка... ну ладно, здесь значит у нас что-нибудь про то, что $w$ — это на самом деле вот такое... ну соответственно и вот так... значит здесь у вас будет какой-то остаток от этого дела, два штриха, да. Ну и потом вы возьмете, вы проверите, что вот эта штука — это на самом деле, видимо, бэшка, за которой еще чего-то там. Соответственно, и для $N_1$ точно такая же.

На самом деле вот эти вот рекурсивные автоматы, они в каком-то смысле порождают вам практически код рекурсивного спуска, то есть какие-то функции, которые умеют друг друга вызывать. Буквально вот этот переход должен трактоваться как вызов функции, разбирающей $N_1$, на том, что здесь мы еще не доели, то есть эту буковку откусили и что-то осталось еще. Давайте здесь попробуем распознать. После того, как мы здесь завершились, мы должны перейти в состояние 2. Фактически, если говорить, вот здесь сейчас у нас возникнет стек.

Когда вы пишете рекурсивный способ, когда вы работаете с подвызовом процедурой, под функцией, у вас как раз возникает стэк вызовов, для того чтобы подрисовать возврат, сохранить. Я, понятно, упрощаю, не складываю туда ничего, что еще в стэк-фрейме лежит, но именно стэк как механизм работы с вызовами. Фактически ровно для этого нам стэк сейчас и понадобится, потому что фактически у нас двойка, ну это в адрес каком-то смысле возврата для произошедшего, вызова да, в состоянии 1.

Важно другое, что у вас вот здесь вот, на самом деле, практически вызовы. Поэтому у нас сейчас, во-первых, в конфигурации появился обещанный стэк. Без него нам будет тяжело обойтись, потому что мало ли, где у нас еще какие-нибудь терминалы были. А в остальном всё. То есть мы будем пользоваться стэком, как вы привыкли пользоваться стэком, для того чтобы хранить адреса возврата. Всё.

Значит, конфигурация у нас тогда, в отличие от автомата, это, собственно, текущее состояние, остаток цепочки и стэк. Давайте назовем стэк жирненькой буквой Q (хотя она конфликтует с состояниями).

Соответственно, и переход между конфигурациями у вас выглядит следующим образом. Всё та же история: вы находитесь в какой-то конфигурации, куда вы можете перейти. Вариантов несколько.

Первый вариант: если у вас есть переход в какое-то другое состояние и читается терминальный символ $w$, то, соответственно, вы переходите в конфигурацию вида $(q', w', \mathbf{Q})$, и со стеком ничего не произошло. Это тот самый шажок: вы просто взяли и откусили терминальный символ. Всё логично.

Второй вариант: если у вас в качестве элемента стека или символа [возможная ошибка распознавания: нетерминал $P$] — это как раз вызов, да, это вот эта вот ситуация, то, что у вас происходит. На цепочку вам в этот момент более-менее наплевать. Вы строите конфигурацию вида $(q_0, w, \text{новый_стэк})$, где $q_0$ — это стартовое состояние для подзадачи. То есть фактически вы вызвали функцию, всё, пришли в её начало. Буквально можно трактовать это как адреса вашему любимому ассемблеру, метки, не знаю, что угодно. А новый стэк — это вы, соответственно, адрес возврата на стэк запомнили. Всё.

И следующий вариант — это когда вы оказались в финальном состоянии, да, то есть если... Ну, как это, кто уже догадался, что нужно сделать? Ну, то есть итоговая конфигурация будет очень просто выглядеть, да, у вас здесь будет какое-то состояние. Давайте назовем его $p$. Цепочка у вас не поменялась. Ну и у вас будет новый стэк. Очевидно.

Конфигурация автоматного типа состоит из текущего состояния и содержимого стека, которая выглядит как пара из состояния $p$ и оставшегося содержимого стека $q'$, где $p$ — текущее состояние, а $q'$ обозначает оставшуюся часть стека.

Если вы оказались в финальном состоянии (при этом предполагается, что на стеке что-то было, и оттуда можно что-то снять), то это корректная ситуация. Другой хороший случай завершения работы — когда входная цепочка $w$ является пустым словом, а стек пуст. Это соответствует корректному завершению работы, цепочка принята, и все замечательно.

Возникают и другие ситуации, например, когда для нетерминала уже нет подходящего правила или бокса. Это соответствует чему-то некорректному, некоторому недостижимому состоянию. Если у вас для нетерминала нет бокса, то он как минимум не порождающий в той терминологии, которая была для нормальной формы Хомского (НФХ). Именно для этого мы, например, чистили грамматику. Понятно, что здесь у нас не НФХ, но тем не менее чистить грамматику иногда нужно для того, чтобы о таких некорректных случаях в процессе дальнейших рассуждений не думать.

Если же цепочка оказалась пустой, а на стеке ничего нет, мы доработали до конца, и все замечательно. Единственное, что нужно помнить: примерно как с недетерминированным конечным автоматом, все эти варианты (кроме, наверное, последнего) не являются взаимоисключающими. Ровно потому, что вы, в принципе, можете оказаться в финальном состоянии и должны попробовать вернуться обратно, но в этот же момент у вас есть переход по символу, и вы тоже в принципе должны его попробовать. Может получиться как некорректная ситуация, так и корректная. В этом смысле детерминизма нету, и вы должны проверять все возможные варианты.

Никто не мешает ради этих вариантов нарисовать какое-нибудь состояние, у которого есть и терминальный переход, и нетерминальный переход, и соответственно вы вынуждены попробовать так или эдак, если действовать формально. Понятно, что в какой-то момент мы можем методом пристального взгляда посмотреть и понять, что входная цепочка не может начинаться с какого-то символа, поэтому можно не пробовать, но мы пока не умеем никуда заглядывать и действуем совсем в лоб: видим нетерминал, значит надо попробовать вызваться, а дальше уже как пойдет — либо сломается, либо не сломается.

Поэтому реальная работа у вас начинается со стартовой конфигурации, и дальше вы работаете до тех пор, пока у вас где-то не встретится принимающая конфигурация. При этом у вас всегда может появляться множество конфигураций, потому что все эти сценарии не взаимоисключающие.

Для разбора примера возьмем чудесный рекурсивный автомат и выберем какую-нибудь более-менее тривиальную принадлежащую цепочку. Стартовая конфигурация выглядит следующим образом: мы находимся в нулевом состоянии, вся цепочка у нас на руках, а стек представляет собой пустой список.

Если действовать аккуратно, находясь в финальном состоянии, мы вообще говоря должны попробовать сделать pop. Здесь у нас будет некорректная ветка, потому что стек на сто процентов пустой, ничего там не попнется, ну и бог с ним. Поэтому стартовый переход содержит только переход в единичку, в результате чего мы получаем конфигурацию вида: символ съеден, состояние единичка, а стек не поменялся. Соответственно, здесь у нас вообще один вариант, есть только вызов. Что у нас происходит в вызове? Состояние меняется на стартовое состояние нашего вызываемого нетерминала, цепочка не меняется, мы в этот момент с ней ничего не сделали, а на стеке появился адрес возврата.

Находимся мы теперь здесь, и здесь у нас вообще говоря два варианта, то есть мы как раз получим множество конфигураций. Первое: мы находимся в финальном состоянии, мы можем сделать pop, то есть перейдем в конфигурацию со вторым состоянием, цепочка осталась на месте, а стек пустой. Вторая конфигурация: мы попробовали перейти по терминальному символу, соответственно, оказались в четвертом состоянии, от цепочки осталось db, а стек здесь не поменялся, так как это терминальный переход. Это как раз тот самый разговор про то, что мы должны все варианты рассматривать.

Дальше, формально мы должны обе конфигурации обработать. Первая приведет к некорректному завершению, потому что мы находимся во втором состоянии, а символы цепочки (c, ب [возможная ошибка распознавания: символ цепочки]) не смачились, мы упали, бог с ним. Но есть еще вторая конфигурация, здесь у нас снова вызов. В результате получается, что мы переходим в стартовое состояние, цепочка остается прежней, а на стек кладется адрес возврата — пятерочка, двоечка. Мы находимся в нулевом состоянии, и опять у нас вообще говоря два варианта. Первый — это сделать pop, то есть мы переходим в пятое состояние, цепочка на месте, на стеке двойка (используем правильные скобки). Второй вариант из нулевого состояния — попробовать сделать a-шку, но у нас ничего не получится, окей. Значит, здесь у нас слишком рано начало рисовать множество, но тем не менее фактически два варианта мы должны были обработать, один из них сломался.

Теперь мы находимся в пятом состоянии, видим только лишь терминальный переход, видим d, d съедаем, переходим в третье состояние, осталась ب [возможная ошибка распознавания: символ b] и на стеке двойка. Финальное состояние, переход по c есть. Уже не буду рисовать, понятно, что по c сломается, нарисую только работающую конфигурацию. Соответственно, происходит возврат, возвращаемся мы в адрес, который у нас был, поставили стек, запустим. Мы находимся здесь, видим b, переходим в конфигурацию: состояние ноль, цепочка пустая, стек пустой. Ура-ура, получилось, сработало, радость, счастье, принимается, цепочка — все хорошо. Прошу любить и жаловать, стек наконец-то появился, вас не обманули, вот она — стековая машина.

В целом вот у вас получился вычислитель, которому стек нужен, и можно аккуратно порассуждать, прийти к тому, что он необходимо нужен. Работает. В принципе вы уже можете взять и написать распознаватель для КС-языков. Единственная такая большая — она не единственная, но большая и, надеюсь, более-менее очевидная — проблема заключается в ситуациях, когда у вас возникнет более-менее реальный нетерминал. Давайте мы эту ситуацию создадим.

Дим, значит, я вот это все стираю. По вот этому примеру вопросы есть? Ну, более-менее, да, вроде очевидно. Значит, сейчас будет менее очевидная вещь. Ну, по крайней мере, как, приводящая к проблеме. Проблема-то очевидная, поэтому, возможно, и пример очевидный. Ну, более проблемный пример. Значит, сейчас. Сейчас. Мне, наверное, нужно. Сейчас подумаю, что мне надо. Да, наверное, мне достаточно вот такого автомата. Значит, 0 — стартовый, он же финальный. А здесь что-нибудь вот такое. Значит, ну и более-менее понятно, что это $A^*$ на самом деле, то есть все цепочки, включая пустую, из ашек. Ну давайте возьмем какую-нибудь не сильно большую цепочку. Попробуйте запустить, то есть опять же стартовая конфигурация более-менее понятна какая. Вперед! Что там будет дальше происходить? Опять же, уже на первом шаге у нас минимум два варианта: до первого скоб не сработает, второй с вызовом сработает. Ну здесь хорошо, пока. Соответственно, давайте я здесь пока нарисую, значит, у вас произошел вызов, соответственно, вы опять оказались в нулевом состоянии, цепочка осталась на месте, у вас получился не пустой стек, адрес возврата сюда. Соответственно, что дальше? Во-первых, у вас снова два варианта, и здесь уже, вообще говоря, сработают оба, правильно? Ну, если, в принципе, можете попробовать снять что-то со стека, вы получите, соответственно, единичку и пустой стек, а можете еще раз вызваться, да, то есть вы снова окажетесь в нулевом этом, и у вас будет такой стек. При этом на текущем этапе обе конфигурации вообще говоря жизнеспособны, то есть вот из конфигурации этой мы находимся в первом состоянии, видим ашку, мы съедаем ашку, оказываемся в нулевом состоянии, одна ашка, пустой стек. Значит, а из этой конфигурации, ну, как бы снова, мы да, находимся в нулевом состоянии, мы можем сделать pop, да, то есть перейти в единичку, а из единицы, и, соответственно, вы опять же можете снова вызваться, да, то есть сейчас, секунду, я допишу, чтобы не это, самому не запутаться, значит, цепочка останется той же, и вывод отсюда вызывается, значит, у вас единичек будет уже три. Вот это прям реально то первый, то есть у нас есть переход, в смысле двигаемся, скажем так, через символ $s$, и мы остаемся в том же состоянии, но при этом мы пушим на стек. Смотрите, действуем совершенно формально. Вы находитесь в состоянии, у возможность вас единственная — это сделать вызов. Что такое сделать вызов? Это перейти в стартовое состояние этого символа. Так случилось, что у вас self-recursive, сам себя вызывающий. Ну да, здесь все по вполне формальным соображениям так получается. И следующий, где-то здесь, такая же история, каждый раз просто функция сама себя вызвала, горе-то какое, вроде никакой проблемы. Вот, хорошо, можете попробовать еще немножечко порисовать, да, то есть, и попробовать заметить и сформулировать некоторую проблему со второй частью, может быть.

Лектор продолжает разбор конфигураций на доске, отмечая, что с первой конфигурацией можно попробовать сделать операцию pop, но ничего не выйдет, либо попробовать сделать вызов (call), и тогда что-то получится. Применяя операцию вызова к конфигурации, где мы находимся в единичке, ашка даёт единственный вариант перехода: мы снова перейдём в ноль, и у нас останется одна ашка. Лектор замечает, что эта конфигурация дублирует уже имеющуюся, поэтому одну из них можно убрать (лектор зачёркивает дублирующуюся конфигурацию на доске, чтобы было понятно, куда она исчезла — она исчезла потому, что сначала появилась, а потом выяснилось, что это дубликат).

Для второй конфигурации история похожая, но здесь мы можем сделать и вызов, и pop. В результате применения операции pop мы можем перейти в единичку и получить состояние, которого у нас ещё не было. Лектор сверяется с записями на доске, уточняет, какой именно pop был применён, проверяет вторую зачеркнутую конфигурацию и констатирует, что пока всё находится на своих местах.

Затем лектор задаёт аудитории вопрос, кто уже почувствовал неприятности: некоторые конфигурации не заканчиваются и продолжают порождаться. Происходит недетерминизм в полный рост, множество конфигураций разрастается. Некоторые из них начинают дублироваться, но нужно помнить, что это именно множество. Для обхода этого множества можно замутить обход в ширину, веря, что какая-то из конфигураций приведёт нас к успеху. Однако, если вы не обладаете даром предвидения, вы можете слишком часто выбирать конфигурацию, которая наращивает стек вызовов и ничего не меняет.

Здесь возникает аналогия с левой рекурсией, о которой уже шла речь при обсуждении рекурсивного спуска. Фактически, если происходит вызов без изменения цепочки, стек постоянно растет, содержимое не меняется, и без дополнительных манипуляций с этим ничего нельзя поделать. Проблема заключается в том, что когда мы говорили про работу конечных автоматов в терминах конфигураций, любую конфигурацию можно было обрабатывать не больше одного раза (в том смысле, что если её уже обработали, то больше не надо). Хочется сказать то же самое и здесь, и в принципе это было бы правдой — не просто так лектор зачёркивал дубликаты. Но штука в том, что в конфигурациях появляется злостная штука под названием стек, которая имеет неприятное свойство расти.

Расти, пока его не остановят, а в некоторых случаях он может просто не останавливаться. Поэтому возможны ситуации, когда постоянно появляются новые конфигурации, если смотреть на них как на незатейливые структуры данных. Если смотреть на стек просто как на линейный стек — неважно, как список он реализован или как что-то еще, — структурное сравнение здесь работать не будет. Эту проблему пока просто обозначим, а как с ней бороться, будет рассказано чуть позже.

Важный для нас момент — просто заметить, откуда она взялась, и жить с этим, понимая, что мы можем написать фактически распознаватель для контекстно-свободных языков (в транскрипте: контекста свободных языков), но с некоторыми ограничениями на грамматике и на RSM соответственно. То есть не всегда оно будет работать так прямо в лоб и очевидно, как нам хотелось бы. Хотя тезис о том, что мы хотим работать так, чтобы каждую конфигурацию нужно было обрабатывать не больше одного раза, является правильным, просто конфигурации должны быть немножко не такими. О том, какими именно они должны быть, пойдет речь позже.

Хорошо, с RSM немножко побаловались, поняли, как они работают, и поняли, в чем может быть проблема. Коль скоро мы далеко от нормальной формы Хомского не ушли, она нам сейчас как раз наконец-то понадобится для формальных соображений. Поговорим снова про RSM — точнее, не про нее, [неясный фрагмент].

А теперь поговорим про лемму о накачке. История сейчас будет ровно такая же. Мы с вами попробуем ее сконструировать, понять, откуда берутся все детали ее формулировки, и поможет нам в этом нормальная форма Хомского. Можно без нее, но это, по крайней мере, один из, на мой взгляд, осознаваемых достаточно хорошо способов получить лемму о накачке. Значит, смотрите. Мы знаем, как всегда, мы начнем с того, что у нас есть какой-то контекстно-свободный язык, также как для леммы о накачке про регулярные языки мы начинали с того, что у нас есть регулярный язык. Это значит, что мы можем построить какую-нибудь грамматику для этого языка, которая находится в нормальной форме Хомского.

Раз у нас есть грамматика в нормальной форме Хомского, то мы можем взять какую-то цепочку и найти вывод этой цепочки в этой грамматике. Очевидно, мы эту цепочку взяли из языка, значит, какой-то вывод существует. На предыдущей паре мы говорили, что если вывод существует, то, в принципе, так или иначе мы можем дерево вывода какое-то построить. Мы можем построить какое-то дерево вывода, где в кроне у нас наша цепочка, в корне у нас $S$, ну и здесь что-то происходит. Причем, благодаря тому, что мы потребовали, чтобы грамматика была в нормальной форме Хомского, мы более-менее хорошо представляем, что у нас здесь происходит, в том смысле, что все внутренние узлы обязательно имеют ровно двух сыновей, а в конце у нас какая-нибудь история о том, что нетерминал породил терминал. Эпсилон-цепочку, кстати, да, вот здесь нам удобнее сказать, что либо вариант с эпсилоном мы отдельно проверили, либо забыли про него, то есть считаем, что здесь что-то содержательное происходит. А внутри мы знаем, что у нас обязательно какие-то такие конструкции, то есть любой внутренний узел с двумя сыновьями, причем оба нетерминалы. Соответственно, теперь мы будем действовать следующим образом. Вот чего я хочу добиться. Я хочу добиться следующего эффекта. Берем какой-нибудь путь в

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

Зачем это нужно? Если есть такая конструкция, то очевидно, что здесь у нас тоже имеются какие-то элементы и два поддерева болтаются. Анализируя эту ситуацию, лектор отмечает, что фактически найден аналог того самого цикла, который находили в автомате при построении леммы о накачке для регулярных языков. Там говорилось, что если в автомате есть цикл (а если взяли достаточно длинную цепочку, она обязательно проходит по циклу), то этот цикл можно брать и размножать. Здесь строится примерно такая же конструкция: эту историю можно вырезать и вставлять обратно.

Чтобы пояснить, как мы пришли к такой ситуации и чего мы хотим, а также как дальше производить накачку, лектор предлагает более простую картинку. У нас есть какой-то путь, есть нетерминал [в транскрипте «тирачик»], который соответствует какому-то поддереву. У нас есть снова он же, соответствующий тоже какому-то поддереву.

В результате получаются «штаны», которые можно пририсовать. Здесь очевидно будет существовать такой же путь, которым снова все заткнули. Фактически получается какая-то штука... стирая «штаны», лектор обозначает части как $x, y, z$, и эти две штучки можно очевидным образом размножать. Собственно, в этом и заключается идея накачки. Точно так же их можно удалить — удалить полностью эти штаны и подвесить треугольничек сюда, и все будет хорошо.

Лектор переходит к вопросу о том, как из теоретико-графовых соображений можно оценить длину цепочки и высоту дерева вывода, проводя аналогию с конечными автоматами. В автоматах брались цепочки, которые длиннее количества вершин, из чего следовало, что такой цепочке соответствует путь, заходящий в цикл.

Здесь рассуждение строится похожим образом: требуется понять, как найти достаточно длинную цепочку и какая у нее будет оценка на длину, чтобы заработала необходимая конструкция. Отталкиваться нужно от ситуации, когда в дереве вывода почти наверняка существует путь, в котором повторяется какой-то нетерминал. Предложение использовать большее количество нетерминалов дает слишком слабую оценку.

Лектор напоминает, что требование НФХ (нормальной формы Хомского) введено не просто так, так как оно очень сильно упрощает оценку, позволяя понять, как устроено дерево, у которого все внутренние узлы имеют ровно двух сыновей. Если мощность множества нетерминалов равна $N$, то нужно оценить высоту дерева. Рассматривая дерево как частный случай графа, а именно бинарное дерево, требуется найти его самую пессимистичную высоту — несбалансированное бинарное дерево (вырожденное в цепочку). Высота этого дерева должна быть больше, чем количество нетерминалов, потому что тогда на пути где-то обязательно придется продублировать хотя бы какой-то нетерминал, иначе конструкция не сработает. Исходя из того, что высота самого плохого несбалансированного бинарного дерева должна быть больше количества нетерминалов, цепочка должна иметь соответствующую степень длины (плюс-минус один, как было в регулярных языках).

Эту конструкцию в принципе можно построить и без требования НФХ, но тогда для правил произвольной длины в правой части полезет «лютая комбинаторика». Такие доказательства можно встретить в достаточно древних книжках, но сейчас пришли к тому, что использование нормальных форм проще, что иллюстрирует их нужность для упрощения рассуждений.

Итак, если грамматика хорошая (и в ней должна быть рекурсия, иначе ничего не выйдет), то при выборе достаточно длинной цепочки с неизбежностью возникает необходимость строить такую конструкцию, при которой появляется возможность производить «накачку» (pumping).

При формулировке леммы о накачке для контекстно-свободных грамматик получается конструкция вида $x^n y z^n$, или с использованием греческих букв, например, $\alpha x^n y z^n \beta$. Из общих соображений можно требовать, чтобы $n$ было больше либо равно нулю, потому что, как уже обсуждалось ранее, можно вырезать «штаны», подклеить треугольник наверх, и все всё равно сработает.

Для любого контекстно-свободного языка существует константа $k$ такая, что для любой цепочки этого языка, длина которой строго больше $k$, существует разбиение цепочки на пять частей: $\alpha, x, y, z$ и $\beta$ (так что цепочка представляется как $\alpha x y z \beta$), обладающее определенными свойствами. Главное свойство заключается в том, что при одновременном «накачивании» частей $x$ и $z$ в одинаковой степени $n$ (то есть при рассмотрении цепочки вида $\alpha x^n y z^n \beta$), полученная цепочка также принадлежит нашему языку для любого $n \ge 0$.

Как и в лемме о накачке для регулярных языков, на эти кусочки необходимо наложить содержательные ограничения, чтобы избежать вырожденных случаев и бессмысленных результатов. Например, если не накладывать ограничений, можно было бы накачивать всё подряд с помощью пустой цепочки $\varepsilon$, что привело бы к не очень содержательным выводам. Чтобы избежать этого, на длину накачиваемых частей накладываются ограничения, в частности, длина произведения $x$ и $z$ должна быть больше нуля ($|xz| > 0$). Если же один из этих кусочков имеет нулевую длину, то фактически получается лемма о накачка для регулярных языков, поскольку регулярные языки являются частным случаем контекстно-свободных, и в этом случае тоже всё работает нормально.

Вариации формулировок леммы о накачке в разных книжках могут немного отличаться, поэтому важно понимать, откуда они взялись и зачем нужны. По сути, все эти вариации возникают из попыток избежать вырожденных случаев, когда пустым кусочком пытаются что-то накачать.

Работает лемма о накачке для контекстно-свободных языков точно так же, как и для регулярных языков: с её помощью можно доказывать, что какой-то конкретный язык не является контекстно-свободным, то есть показывать отрицательный результат и подтверждать, что иерархия языков не вырождена и в классе КС-языков есть что-то содержательное. В качестве упражнения рекомендуется рассмотреть классические неконтекстно-свободные языки (например, язык вида $a^n b^n c^n$, где $n \ge 0$), для которых можно попробовать аккуратно доказать с помощью этой леммы, что они не являются контекстно-свободными.

С этим более-менее, наверное, тоже. Ну, всё. Ту-ту-ту-ту-ту-ту-ту-ту-ту-ту-ту-ту-ту-ту-ту, и нам кажется, пора потихоньку переходить

Лекция переходит к алгоритмам синтаксического анализа. Слушатели уже должны быть знакомы с этой областью с разных сторон: в параллели идет курс по компиляторам, где Дмитрий Сергеевич должен был что-то про это рассказывать, а до этого при написании интерпретаторов тоже приходилось заниматься разбором текста. Существуют как инструменты для синтаксического анализа, основанные на алгоритмах, так и соответствующие библиотеки и рантаймы.

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

В качестве примеров таких инструментов можно назвать ANTLR, Yacc (у которого есть куча реинкарнаций, таких как Kamahlang, FsYacc, Bison и им подобные). Генераторов на самом деле миллион. Тот же Tree-sitter изначально создавался именно как инструмент для синтаксического анализа, а дальше оброс примочками для навигации, создания фронтендов для средств разработки и так далее. Все эти инструменты действуют по более-менее понятной истории: на входе подается какая-то грамматика, происходит что-то чудесное, и на выходе получается то, что пока можно назвать «парсером» в кавычках. Это жаргонное слово, которое пока ни о чем не говорит, и нужно аккуратно раскрывать, что на самом деле генерируется. В обывательском понимании это некоторая функция, которой можно скормить текст программы и получить структурное представление — например, дерево разбора. Здесь возникают тонкости с тем, что дерево разбора — это не обязательно дерево вывода и так далее. Лекция будет двигаться к этому постепенно: прямо сегодня речь не пойдет об алгоритмах, которые лежат под капотом у этих инструментов, но будут обсуждаться близкие темы.

Сейчас важно понимать, что алгоритмы, о которых пойдет речь (даже те, про которые будет сказано, что они применяются в инструментах синтаксического анализа), в своем «чистом» виде крайне редко применяются в реальных инструментах. Ситуация примерно такая же, как с регулярными выражениями: любая библиотека поддерживает классические выражения, а сверху — еще миллион расширений, примочек и прочего, чтобы пользователю было удобно и спокойно с этим жить. С синтаксическим анализом такая же история. Если взять классический алгоритм синтаксического анализа из учебника и попробовать построить с его помощью синтаксический анализатор для хоть какого-то реалистичного языка программирования, очень быстро станет понятно, что это была плохая затея — по разным причинам, о которых тоже пойдет речь.

Лектор предостерегает от комментариев в духе: «Я смотрел LL(1) анализатор на Питоне, и он совсем не так работает, в нем есть вот это и вот это». Возможно, действительно рассказывается какая-то вариация, но банальная ситуация заключается в том, что если реализовать LL(1) как есть по книжке или учебнику, пользоваться им будет практически невозможно. Поэтому нет ничего страшного в том, что увиденный где-то алгоритм умеет еще что-то странное. К этому разговору еще вернутся после разбора алгоритмов, чтобы появилась почва для более детального анализа, сравнения и пояснений, почему в реальной жизни все немножко сложнее, чем пишут в учебниках. Но заранее стоит предупредить о существовании таких вещей. Начать планируется с совсем простых вещей.

Начнем мы с воспоминаний о том, как выглядит наша задача. Решать мы сразу будем нашу любимую задачку достижимости для начала. По классике нам нужно слово с пути из $v$ в $u$, оно должно принадлежать языку, и при этом у нас есть стартовые и финальные вершины. И теперь мы знаем, что это у нас контекстно-свободный язык. То же самое мы можем сказать про пути, то есть сказать, что хотим такие пути, чтобы...

И мы возвращаемся к старому нашему разговору о том, почему вообще такую задачу имеет смысл решать, можем ли мы как-то в этом случае представить ответ, и что нам нужно для того, чтобы мы могли это сделать. Давайте вы попробуете подумать, вспомнить и рассказать мне, что нам нужно для того, давайте с конца начнем, эту задачу суметь хоть как-то решить.

Хорошо, давайте все-таки начнем издалека. Проблема у нас вот с этой задачей какая? Найти путь — это наша задача. У нас там есть существенная проблема с тем, что вот эта вот штука может быть, вообще говоря, бесконечной. В регулярках та же самая история. Мы обошлись тем, что мы таки поняли, почему мы можем нормальное описание ответа для этой задачи составить, потому что там вот некоторые свойства замечательные соблюдаются. Мы даже поняли, как эту пешку представить. Еще раз, проблема в том, что мы, решая задачу поиска всех путей, почти неизбежно натыкаемся на то, что путей может быть бесконечное количество.

И в случае с регулярными языками у нас возникли некоторые соображения по поводу того, почему это на самом деле не проблема, и мы понимаем, как все это множество путей описать. Не как построить, я поэтому говорю, что про алгоритм пока рано говорить. Так вот, какие соображения нам нужны, чтобы понять, что мы вот эту пэшку можем каким-то разумным образом представить? Про пересечение языков правильная мысль возникла, она здесь в принципе уместна. Можно от нее отталкиваться, но ее нужно доразвить. Хоть какие-нибудь мысли?

Хорошо, давайте. У меня есть граф — это то, с чем мы работаем, где пути ищем. У меня есть какой-то язык, он тут даже написано, что он контекстно-свободный.

Лекция начинается с вопроса о том, как можно представить бесконечное множество языков конечным образом и можно ли вообще это сделать. На примере регулярных языков эта задача была успешно решена благодаря тому, что регулярный язык представляется в виде конечного автомата, а задача распознавания решается эффективно, что делает понятным представление бесконечного языка.

Далее рассматривается операция пересечения контекстно-свободного языка (КС-языка) и регулярного языка. Возникает вопрос о том, каким классом языков является результат пересечения КС-языка и регулярного. Как отмечается, пересечение контекстно-свободного языка и регулярного языка всегда является контекстно-свободным языком. Это утверждение составляет содержание теоремы о замкнутости контекстно-свободных языков относительно пересечения с регулярными. Данный результат является содержательным утверждением теоремы Бар-Хиллела, датируемой примерно 1960-ми годами.

Подобно тому, как это делалось для регулярных языков, в дальнейшем алгоритмы строятся таким образом, чтобы служить конструктивным доказательством этой теоремы. Хотя теорема имеет и теоретическое доказательство, в ней явно строится стековая машина, которая распознает соответствующий язык. В качестве описания полученного языка можно использовать рекурсивные автоматы, контекстно-свободные грамматики или другие привычные инструменты для работы с КС-языками. Объект, с помощью которого представляется ответ, остается в рамках уже известных описаний контекстно-свободных языков, с которыми удобно работать. Этот общий принцип лежит в основе класса рассматриваемых задач и позволяет переходить к построению конкретных алгоритмов.

Рассматривая связь между контекстно-свободными грамматиками и графами, можно отметить, что линейный вход представляет собой частный случай графа. Строку можно рассматривать как простейший граф, где позиции заменены на вершины, а рёбра помечены символами. Благодаря этому большинство подходов в данной области являются обобщением классических алгоритмов синтаксического анализа.

Важным аспектом при работе с грамматиками в контексте анализа кода является размер самой грамматики. В отличие от регулярных выражений, где пользовательский запрос обычно предполагается маленьким, что позволяет делать автомат детерминированным, минимизировать его и выполнять другие преобразования, с грамматиками ситуация обстоит иначе. Хотя иногда рассматриваются небольшие и аккуратные грамматики, с которыми можно свободно работать, зачастую размер грамматики оказывается сопоставим с размером самого графа.

Оценивать размер грамматики можно по-разному: например, по количеству нетерминалов или, что является более точным показателем, по количеству продукций в какой-либо нормальной форме, поскольку для одного нетерминала можно придумать миллион продукций. Подобные масштабные грамматики возникают, например, в задачах статического анализа кода. В качестве примера можно привести межпроцедурный анализ, когда в программе есть несколько функций, которые вызывают друг друга.

Если проанализировать межпроцедурный граф и пути исполнения программы, становится очевидно, что разумные пути выглядят так, где вызовы и возвраты сбалансированы, образуя парные конструкции («скобочки»). При корректном построении программы не предполагается ситуация, когда происходит вызов в одном месте, а возврат — в совершенно другое. Для корректного анализа необходимо различать все вызовы и возвраты. В результате возникает грамматика со скобочными конструкциями вида $C_1 S R_1 S$, $C_2 S R_2 S$ и так далее для всех проиндексированных вызовов, с добавлением пустого слова ($\varepsilon$) в конце. Таким образом, размер получающейся грамматики напрямую пропорционален количеству вызовов в программе, а поскольку программы активно используют межпроцедурные вызовы, размер грамматики может оказаться огромным.

Если в случае с регулярными ограничениями основная сложность обычно заключалась именно в размере графа, в то время как автомат оставался маленьким, то при работе с контекстно-свободными грамматиками в анализе кода это правило работает не всегда, и размером грамматики пренебречь не удастся.

После обсуждения размера грамматики лектор переходит к разработке первого, самого простого алгоритма, решающего задачу достижимости. Алгоритм будет существенно опираться на то, что грамматика для нашего языка находится в ослабленной нормальной форме Хомского (в транскрипте ошибочно названа «формой Холмского»). К путям мы вернемся чуть позже, а сейчас займемся достижимостью.

Граф мы представим, как в прошлый прошлой лекции, набором матриц смежности, то есть у нас сразу будет булева декомпозиция. Наблюдение, которое нам потребуется, заключается в следующем. Если у нас в грамматике есть правило вида $A \rightarrow a$ (где $a$ — терминал), это значит, что мы, видя какое-то ребро с терминалом $a$, сразу можем его преобразовать в ребро с нетерминалом $A$. То есть тут никакой магии не требуется.

Давайте сразу договоримся, что у нас в графе, который мы дальше будем обрабатывать, на ребрах будут на самом деле множества нетерминалов. Почему? Потому что в грамматике нас никто не страхует от объектов, где для одного и того же терминала в правой части есть несколько правил с разными левыми частями. И в нормальной, и в ослабленной нормальной форме нигде не сказано, что не может быть двух таких правил. Соответственно, для всех нетерминалов, у которых в правой части соответствующий терминал, мы преобразуем ребра таким образом. Это был первый шаг.

Второй шаг касается правил вида $A \rightarrow \varepsilon$ (где $\varepsilon$ — пустая строка). Таких правил тоже может быть несколько, так как в ослабленной нормальной форме мы не требуем, чтобы только из $S$ выводился эпсилон. Соответственно, мы в каждую вершину добавляем петлю для всех таких нетерминалов. Мы считаем, что пустой путь из вершинки выводим, в принципе, это логично.

Дальше у нас получился граф, метки которого — это множества нетерминалов. То есть наша матрица смежности имеет вид, где элементы — это множества. И дальше мы будем работать уже с такой матрицей, соответственно, с булевой декомпозицией такой матрицы, преобразуя ее в набор булевых матриц.

Оставшиеся правила у нас все выглядят как бинарные продукций вида $A \rightarrow B C$. То есть все, что у нас осталось в грамматике — это только такие товарищи. Правила с терминалами и эпсилон-правила мы все раскидали фактически на этапе препроцессинга и дальше про них вспоминать не будем. Соответственно, у нас есть граф, подготовленный таким образом.

На ребрах графа располагаются какие-то множества нетерминалов. Чтобы понять идею алгоритма, рассмотрим конструкцию, в которой на ребрах между вершинами находятся множества нетерминалов. Требуется сделать заключение о том, существует ли какой-то путь на выводе слова, вдоль которого выводимого из какого-то другого множества нетерминалов.

Если в первой позиции содержится какой-нибудь нетерминал $a$, а во второй — какой-нибудь нетерминал $b$, и в грамматике есть правило вида $C \to ab$, то в результате на переходе будет присутствовать нетерминал $c$. Весь этот путь из нетерминала $c$ можно вывести, а само правило находится в грамматике.

Эта базовая мысль чем-то напоминает классическое транзитивное замыкание: если из $a$ достижимо $b$, а из $b$ достижимо $c$, то из $a$ достижимо $c$. Только здесь мы еще не забываем подглядывать в грамматику. Алгоритм будет построен ровно на этом наблюдении: нам нужно взять матрицу смежности и посчитать ее транзитивное замыкание, но в какой-то очень алгебраической хитрой структуре, которая не забывает подглядывать в грамматику. Фактически нам нужно построить то, что договорились называть полукольцом, хотя здесь оно полукольцом в строгом смысле являться не будет. Для этого нужно определить две операции, которые действуют на множествах нетерминалов, чтобы затем с их помощью посчитать транзитивное замыкание и реализовать описанную конструкцию.

Решением задачи будет являться транзитивное замыкание матрицы смежности, в ячейках которой лежат множества нетерминалов. Чтобы определить транзитивное замыкание, нужно построить структуру, похожую на полукольцо, чтобы нормально определить историю с возведением в степень. Идея транзитивного замыкания остается прежней: если из $a$ достижимо $b$, а из $b$ достижимо $c$, то из $a$ достижимо $c$, но с дополнительным условием подглядывания в грамматику. Обе эти операции оперируют над множествами.

Операция сложения над множествами нетерминалов представляет собой просто объединение. Если есть несколько вариантов, они просто объединяются, что аналогично картинке, которая рисовалась при пояснении умножения матриц. Плюсик отвечает за агрегацию всех возможных вариантов.

Умножение множеств — это не пересечение. Произведение одного множества на другое строится как множество таких нетерминалов, для которых выполняется условие, что $N_i$ принадлежит $Q_1$, а $N_k$ принадлежит $Q_2$. Если есть еще какой-то вариант, приводящий к $Q_3'$, то для построения общего результата нужно просто посчитать объединение этих множеств.

На вопрос о том, что не так с умножением, следует ответ, что оно не ассоциативно. После этого лектор просит студентов показать, почему именно оно не ассоциативно.

Умножение не является ассоциативным. Это означает, например, что не будет работать быстрое возведение в степень, из банального того, что нам, как людям, строящим алгоритм, полезно и неприятно. Почему эта операция не ассоциативна? На самом деле вещь очень простая. Вам нужно построить какую-то грамматику, точнее — набор правил, и построить три множества такие, что результат ассоциативного соединения не равен сам себе при изменении порядка применения операций. Порисуйте немножко, как это. В этом смысле неассоциативность доказывать очень просто: контрпримера достаточно одного привести. Это если доказывать ассоциативность, надо эти аксиомы аккуратно вспомнить, попытаться аккуратно их доказать.

Конкретный пример. Еще раз: неассоциативность — просто подобрать какой-то маленький пример такой вот конструкции. Конкретная грамматика, конкретные множества, в которых вот это не работает.

Соответственно, я вам подскажу еще одну страшную вещь про эту операцию: она еще и коммутативной не является. В общем, у нас умножение, ну такое, типа умножение курильщика, с ним вообще ничего не сделаешь, печальное, унылое. Ваша задача — показать, что это умножение не ассоциативно и не коммутативно. Через неделю после летучки с этого начнем.

Опять же, некоммутативность, слава богу, тоже показывается легко. Нужно подобрать пример: два множества поменяли местами (грамматику тоже зафиксировали), и оба на — другой результат. Не бог весть какая задача, но тем не менее. Все, с этого места продолжим. Подумайте, почему умножение у нас таким плохим получилось.