avva | только для программистов

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

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

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

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

Ключевых слов в языке, с точки зрения чистого синтаксиса, вообще нет. Практически нет и ключевых символов (можно сказать, что ";" вшито в качестве терминатора, но и это при желании можно будет обойти и переделать). Вместо этого все обычные ключевые слова (if, for, деклараторы переменных my и our, деклараторы кода sub и method, прагма use итд.), и совершенно все операторы (+ * == <=> cmp eq и что угодно еще, включая метаоператоры вида += итд.) определены обычными функциями Перла, вместе с информацией о том, какого рода это операторы с синтаксической точки зрения - например, * это оператор infix, а + есть два разных - infix и prefix, а $object.method есть пример применения postfix-оператора вызова метода к переменной $object, итд.

Функции, определяющие, что делают все операторы и ключевые слова Перла, называются по имени грамматической категории (таких около дюжины) и формы самого оператора. Например, функция '&infix:<+>' воплощает оператор +. Если в своей программе на Perl6 вы определите свою новую функцию с этим именем, то в поле ее определения (lexical scope; при желании ее можно импортировать в другие места итд.) оператор + будет означать ее вызов.

Ясно, однако, что что-то вроде "if" не может быть просто runtime-функцией под именем &statement_control:<if>, потому что не все "аргументы" такой функции должны выполняться перед ее вызовом. Поэтому все функции, воплощающие операторы, деляется на два вида: просто функции и макросы (macro). Макро вызывается во время компиляции исходной программы, и работает в это время; ее задача - совместить куски синтаксического дерева программы, которые она получает в виде аргументов, в что-то новое, воплощающее смысл данного макро. Например, макро 'if' возьмет условие и блок исполнения, и построит какую-то структуру для компилятора, чтобы он знал, что с этим делать. Макро 'sub' прочитает определение новой функции и попросит компилятор скомпилировать его код. Итд. В идеале все эти макросы будут написаны на самом Perl6, когда компилятор Perl6 будет написан на Perl6; пока этого нет, они могут быть написаны на языке, на котором воплощают Perl6.

Предыдущее описание само по себе не дает, подозреваю, достаточно ясной картины того, насколько совершенно все завязано на этот механизм определяемых программируемым образом операторов. Например, самые обычные скобки ( ) в множестве языков, как и в Перле, используются для группировки под-выражений, для передачи аргументов функции итд. Но в Perl6 скобки - всего лишь оператор &circumfix:<( )>, который в runtime ничего не делает со своими аргументами (или это макро, которое возвращает свои аргументы без изменения и вообще не попадает в runtime, можно и так), но благодаря заданному в его определении старшинству дает при парсировании исходного кода нужный эффект группировки. Все "скобочные" операторы: [], <>, {} итд. можно переопределить или определить новые, это всего лишь функции с именами, начинающимися на &circumfix:. Скобки, определяющие блок кода - {}, являются макро-оператором, который заставляет парсер прочитать все внутреннее тело блока по тем же правилам, а потом компилирует его. При желании можно переопределить их или оставить их смысл, но дать им другой внешний вид - это тривиально. Запятая, позволяющая делать список: (1,2,3) или просто 1,2,3 если старшинство того, что вокруг, позволяет - всего лишь infix-оператор, объединяющий свои аргументы в объект типа List - он даже не делает ничего специального во время компиляции, компилятор ничего не знает про "запятую" кроме того, что есть некая функция &infix:<,>. Обращение к члену массива - @a[0], скажем - пример еще одной категории, &post_cirfumfix:<[ ]>, т.е. "скобочный" оператор, который не создает выражение сам по себе, а служит постфиксом к другому выражению, @a в данном случае. Обычная строка в кавычках: 'foobar' - пример действия макро-оператора &quote:<'>, который "съедает" весь текст до следующего ' и делает из него нужный для компилятора синтаксический объект. Другой макрооператор - &quote:<"> - более умен и умеет распознавать имена переменных и даже куски кода внутри строки и правильно их парсировать путем рекурсивного вызова парсера.

Все это при желании можно менять, делать новым итд. Практически ничто не "вшито" в грамматику языка, кроме самого понятия грамматических категорий, операторы которых воплощаются функциями или макросами, и набора этих категорий, самые важные из которых я уже упомянул в примерах: &infix, &postfix, &prefix, &circumfix, &post_circumfix, &statement_control (такие вещи, как if и for), &statement_modifier (if или repeat в конце), &quote, &term (атомические конструкции типа чисел, обращений к переменным по именам, и предопределенных операторов без аргументов) итп.

Как работает парсинг с этих условиях, когда в любой момент может быть определен оператор в любой категории с любым именем (юникодным, кстати, так что нет никакой проблемы, например, определить infix-оператор "плюс" и пользоваться им вместо +) и любым старшинством? Старшинство новых операторов, кстати, можно указывать по отношению к существующим, делая их эквивалентными или более сильными или более слабыми по сравнению с данным. Плюс есть еще ассоциативность операторов одного старшинства, которую тоже можно задавать, и в которой кроме обычных левой и правой ассоциативности в Perl6 есть, например, такая замечательная вещь, как chaining associativity, что позволяет написать, скажем: if $x <= $y == $z <= $t и это будет значить именно то, что написано, т.е. все условия должны выполняться по цепочке. Как это работает? Во время прохода исходного текста парсер знает в каждый момент список операторов, определенный в данном лексическом scope'е (он отслеживает их определения оператором sub или их импортирование из других пакетов, пользуясь помощью компилятора в этом, возможно). Кроме того, парсер знает, в каждый данный момент, из какой категории может придти следующий токен исходного кода. Например, в позиции "начало утверждения" могут придти такие вещи, как число-литерал, или что-нибудь из категорий &quote, &prefix, &circumfix, &statement_control, или может быть whitespace (включая комментарии) но не может &postfix или &infix, например. А после оператора &circumfix (та же открывающая скобка), могут придти все те же, кроме statement_control. И так далее.

В каждый момент парсер знает набор категорий, из которых он может ожидать следующего токена. Из всех этих категорий он выбирает ту, которая дает самый длинный токен (the longest token rule) и считает это следующим токеном. Например, если парсет видит "123", то только одна из категорий откликнется на призыв - категория &quote, и найдет токен ". После него только одна категория откликнется - числа-литерала, и найдет 123. Потом закроется " предыдущего оператора, и так далее. Но это простой вариант. Интереснее, когда может быть конфликт. Скажем, есть оператор for (из категории &statement_control) и функция fortitude(); если в коде написано "fortitude(...", то обе категории вернут кандидатов, но функция победит, ее токен длиннее. Это довольно тривиальный пример, но задумайтесь над тем, что эти имена вообще говоря могут быть почти любыми юникодными строками (без whitespace), и ясно, что такое разрешение конфликтов может оказаться необходимым.

Самое интересное, что все это устроено так, что парсеру вообще никогда не нужно, после выбора токена, делать backtracking (после того, как я это осознал, я понял, что мой первоначальный замысел достаточно стандартного рекурсивного top-down парсера никуда не годится). Формально говоря, парсер делает backtracking, но только во время выбора токена - например, если есть оператор 'foo' и оператор 'foobar', то во время парсирования текста 'foob3' парсеру необходимо отмотать обратно символ b, после того, как он увидит, что следующий символ 3 не позволяет продолжить казавшийся возможным оператор foobar. Но это очень простой с точки зрения абстракции уровень backtracking'а, только на уровне выбора атомического токена. После того, как токен выбран, парсер никогда не "передумает". Если что-то дальше с ним не пойдет, это все, ошибка в исходнике, а не "попробуем другую возможность". Это позволяет сделать парсировку весьма элегантной и быстрой (на это я надеюсь, по крайней мере - посмотрим), сохраняя при этом огромную экспрессивную мощь определяемых операторов.

Сегодня я занимался достаточно чем-то, что обычно во время написания компиляторов оставляют на расправу автоматическим подручным средствам вроде yacc (которые, конечно, тут неприменимы) - а именно, привод выражения к дереву парсировки с учетом правил старшинства и ассоциативности. Предположим, я уже справился с проблемой чтения нового токена (который может быть атомическим термином типа числа, а может - оператором), и все токены по мере чтения кидаю на какой-то стэк; теперь мне нужно разобраться, какие операторы к чему относятся. Про каждый из них я знаю его старшинство и его природу (infix, postfix, prefix - для простоты остановлюсь на этих). Самый простой метод решения вопроса, который мне пришел в голову - рекурсивный проход по стэку и привод его к postfix-нотации (сначала аргументы, потом оператор) с учетом старшинства. Но в моем случае я не могу так поступить, потому что мне в принципе нужно уметь решать, что идет к чему (если я могу это решить), еще до того, как я закончу читать все выражение. Ясно, что если я вижу, скажем, 2+3 *, то я еще не знаю, на что действует +, но если я вижу 2*3+, я уже сейчас могу токены 2,*,3 на стэке заменить на один токен вида *(2,3). И мне это нужно сделать в тот момент, когда я увижу этот +, потому что если этот + - макро-оператор, мне, возможно, надо вызвать его прямо сейчас, и сказать ему что-то умное о том, что ожидает его с левой стороны. Так или иначе, суть в том, что ситуация следующая: вот у меня в руке прочитанный только что новый токен, и я могу либо задвинуть его в стэк, либо пройтись по стэку и попробовать его "ужать" с учетом старшинства/ассоциативности моего токена (если это оператор). С этим "ужиманием" у меня чуть голова не разболелась, потому что в принципе хоть и кажется простым, если добавить к этому префикс- и постфикс-операторы со своими уровнями старшинства, все как-то неприятно усложняется. Вот я иду справа налево по стэку, и надо разбираться, в зависимости от того, что я вижу, могу я сократить или нет, и разные виды операторов означают разное количество аргументов и с разных сторон - много разных случаев, и как-то тяжело это продумать.

Но потом мне в голову пришла простая, наверное, но достаточно удобная идея: я могу сделать вид, что префикс оператор, скажем !$x, якобы является инфикс-оператором с "пустым" левым членом: "nil ! $x", причем у этого инфикс-оператора уровни старшинства разные с двух сторон: вправо у него старшинство, как у исходного префиксного !, а влево, к пустому операнду, у него максимальное возможное старшинство (это гарантирует, что он точно 'захватит' именно и только его). Точно так же постфиксный оператор - всего лишь инфиксный оператор с пустым правым аргументом, в сторону которого у него максимально возможное старшинство. Если я представлю все так, внезапно все сильно упрощается и мой стэк всегда будет просто чередованием: терм оператор терм оператор терм... Его уплотнение теперь выглядит следующим образом: я начинаю с только что прочитанного оператора данного старшинства, и иду влево: читаю терм и еще один оператор; если его старшинство меньше того, что у меня в руках, останавливаюсь - не могу сократить; если больше - рекурсивно вызываю уплотнение начиная с него; если равно - смотрю на ассоциативность и решаю соответственно, могу уплотнить или нет. Все подробности до мельчайших деталей тут я не продумал, но, кажется, это все же просто и можно сесть и написать.