КомбинАторный Синтаксический анализ - I

Витя сказал, что кто-то чего-то не понял и попросил что-нибудь написать :) Ну, за мной не заржавеет.

!!! Все умные мысли в этом и следующих нескольких постах принадлежат aa5779, который вёл семинар. Я только обработал и изложил. !!!

"КомбинАторный" от слова "комбинатор", ударение на А. Помните Остапа Бендера? Но он тут почти не при чём.

1. Комбинаторы

Первое, что нужно понять - что такое комбинаторы. Это очень просто. Это такие штуки, которые можно просто комбинировать друг с другом.

1.1. Примеры

Несколько штучек:

• Электрический. Провода, выключатели, лампочки. С соблюдением несложных правил они хорошо и просто сопрягаются друг с другом (правило в данном случае одно: что угодно можно соединить с проводом; а, например, выключатель с выключателем напрямую - нельзя), образуют единую систему, которая как-то функционирует. Чтобы она функционировала со смыслом, нужны отдельные усилия, но это не важно.


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


• Пластилин... Нет, пластилин не подходит. Почему - объясню ниже.


• Лингвистический-словообразовательный-I. Ну, понятно, да? Корни, приставки, суффиксы. Приставки в начале, суффиксы в конце... Как обычно, главное - состыковать, о том чтобы был смысл нужно думать отдельно. И не здесь :)


• Лингвистический-словообразовательный-II. Движемся ближе к телу. Комбинатором будет не суффикс-приставка-корень, а действие. Действие типа <добавить в конец суффикс 'ок'> или <добавить в начало приставку 'пере'>. Этим комбинаторам нужны какие-то входы - чтобы было к чему добавлять. Комбинатору <корень 'дуб'> ничего не нужно. Для построения слов с несколькими корнями нужно несколько комбинаторов слияния типа <соединить первое и второе, вставить между ними 'о'>. Несложно построить из таких комбинаторов какое-нибудь слово, например передубомедвежок. Корень 'дуб', корень 'медвеж', объединяем, добавляем в начало приставку, а в конец суффикс. Видите, как полезно?

Ну и наконец математический пример. Математические функции - вполне себе комбинаторы. Например, введя функции:

mul(x, y) = x*y
add(x, y) = x + y
neg(x) = -x
inv(x) = 1/x

можно записать выражение a/b + c*d - e/(h - g) в виде

add(
    add(
        mul(a, inv(b)),
        mul(c, d)
    ),
    neg(
        mul(e, 
            inv(add(h, neg(g)))
        )
    )
)

Я, конечно, не решусь сказать, что это проще читать :) Но это точно проще вычислять, потому что это выражение синтаксически единообразно. Нам не нужно думать о приоритете операторов (сначала умножить, потом сложить), не нужно думать о количестве параметров, не нужно знать, что делают операции. Нужно только вызвать их.

1.2. Обобщения

Почему не подходит пластилин и почему всё, что подходит комбинировать просто? Просто - потому что комбинаторы просты и всегда одинаковы. Кирпич - всегда кирпич, синус - всегда синус. В отличие от йогуртов, все кирпичи полезны в одинаковой степени (при одинаковом способе употребления) - потому что модель проще гораздо: бац - и готов. Внутреннее устройство комбинатора совершенно не важно при его использовании. Важно, что есть стандартный способ соединения. Важно, сколько у него дырок и сколько пупырышков (входных и выходных параметров). И важно, что в какое место комбинатор не сунь, его поведение (значение на выходе) зависит только от значений входных параметров, и больше ни о чего. И, конечно, мы не можем снаружи никак изменить это поведение. Только очень могучий шаман может изменить значение синуса в указанной точке.

Итого, требования к простоте:

• семантическая независимость от контекста.


• стандартный интерфейс ("синтаксическая независимость")

Дальше, несложно заметить, что комбинируя комбинаторы, мы опять получаем комбинаторы (корабли лавировали, лавировали, да не вылавировали :)). Ну действительно:

• Сколько элементов конструктора вместе не соединяй, результат имеет стандартные пупырышки, стандартные дырочки для них, ведёт себя просто, постоянно - значит комбинатор.


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


• С функциями этот фокус вообще в школе проходят :)

1.3. Комбинаторы высших порядков

Движемся от материальных примеров ко всё более абстрактным. Рассмотрим нашу недлинную эволюцию:

• В первых примерах комбинаторы были чем-то, что можно пощупать: лампочки, кирпичики, суффиксы.


• Следующий этап - комбинаторы, являющиеся вычислительными процессами: <добавить в конец суффикс 'ок'>, вычислить синус. Примерно с этого этапа можно было начинать жаловаться что "началась жосткая математика".

Но до сих пор аргументами и результатами (входами и выходами) наших комбинаторов было что-то достаточно материальное: слово, последовательность символов, число. Пора ломать стереотипы. Следующий этап абстрагирования - комбинаторы, входами и/или выходами которых являются комбинаторы.

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

• Автоматическая фабрика, выпускающая роботов. Самый "материальный" пример, но не очень жизненный.


• А вот создание одной программы другими это ежедневная программистская реальность. Программы, создающие программы это компиляторы. Ну, ещё есть всякие генераторы скриптов и т.п. С приниманием на вход сложнее, хотя можно вспомнить плагины, dll и прочий COM. Но это уже немного натянутый пример.


• Возвращаясь к электрической цепи. Розетка это универсальное гнездо, к которому подключаются комбинаторы типа пылесоса и холодильника, преобразующие ток во что-то полезное. Это можно рассматривать так, что розетка - комбинатор, принимающий на вход ток и "полезный комбинатор". Её задача - правильно вызвать комбинатор, переданный ей в параметре. Хороший пример, проблема только в "можно рассматривать": это не самая естественная модель для такой ситуации :)


• Люди - не совсем комбинаторы. Но.. Рожающие женщины :) Они, очевидно, порождают. А мужики? А они, гм, принимают комбинатор на вход.. и возвращают новый комбинатор, отличающийся от старого свойством "беременна" :) [натяжка, натяжка, даже передёрг я бы сказал.. но пусть будет :)]

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

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

Хорошо, написали такую штуку. После чего обнаружили, что в нашем ущербном частном случае мы не можем написать обычный комбинатор, который будет принимать два параметра, и возвращать значение "кто из них больше". Потому что нам обязательно нужно сравнивать как-то хитро. Например, все строки сравниваются лексикографически .. кроме строк, совпадающих с именами детей пользователя, они должны быть всегда на первом месте. Как зовут детей пользователя мы заранее не знаем и прошить их в код не можем. Передать их комбинатору через параметры тоже не можем: мы его даже не вызываем, он вызывается изнутри комбинатора-сортировщика. От глобальных переменных и прочей ереси комбинатор не должен зависеть по определению (семантическая независимость от контекста!).. В общем, остаётся только генерировать комбинатор на ходу. Правда, генерируем мы его по некоторому шаблону, подставляя в нужные места список имён. Но тем не менее это уже круто.

Вот примерно так работают комбинаторы высшего порядка.

1.4. Ненужное добавление

В рамках семинара - вам это не нужно знать :) Но вообще, комбинаторы это одна из моделей вычислений. Скорее всего, Тьюринг-полная. На эту тему есть большая теория, которой я, конечно, не знаю. Есть несколько стандартных комбинаторов (Y, K, I, кажется), на которых вся строится... Но в данном случае это всё правда не важно :)

---

Продолжение:

2. Контекстно-свободные языки и грамматики
3. Собственно комбинаторный синтаксический анализ
4. Оптимизация