?

Log in

No account? Create an account
только для программистов - Поклонник деепричастий [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

только для программистов [ноя. 17, 2006|05:40 am]
Anatoly Vorobey

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

СсылкаОтветить

Comments:
Страница 1 из 2
<<[1] [2] >>
From: (Anonymous)
2006-11-17 04:08 am
use это не прагма
use это 'BEGIN {require; import}'
(Ответить) (Thread)
From: ex_ex_ex_gr
2006-11-17 04:11 am
Серёж, это и есть прагма :)
(Ответить) (Parent) (Thread)
From: ex_ex_ex_gr
2006-11-17 04:10 am
Видимо, решили довести идею до абсурда.
Очень интересный пост, спасибо.
(Ответить) (Thread)
[User Picture]From: avva
2006-11-17 04:20 am
Я бы не сказал, что это абсурд. У меня есть серьезные сомнения по этому поводу, потому что в реальной практике я очень редко вижу пользу от переопределения операторов в языках. Но дизайнеры Perl6 очень постарались, наряду со всей этой синтаксической регулярностью, сделать так, чтобы обычный набор контрольных средств и операторов, который наверняка будут использовать 99.999% пользователей языка, был одновременно вполне "перловым" по духу, во многом более мощным и удобным по сравнению с Perl5, и, наконец, еще более DWIM-ным по сравнению с предыдущими перлами. Пожалуй, DWIMness - один из самых важных, а может и самый важный принцип Перла, и в этом смысле Perl6 оправдывает надежды, несомненно.
(Ответить) (Parent) (Thread)
From: ext_17976
2006-11-17 04:16 am
Спасибо большое. Прочитал с интересом и удовльствием.
(Ответить) (Thread)
From: selfmade
2006-11-17 04:25 am
Программирование программирования. То о чём так долго говорили большевики, свершилось.
(Ответить) (Thread)
[User Picture]From: yurri
2006-11-17 06:09 am
Я всё тужусь вспомнить, где ещё это пытались реализовать - точно был (есть?) какой-то более-менее применимый (не лабораторный) язык с подобными же свойствами.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: yurvor
2006-11-17 04:43 am
Типа, С++, только скриптовый :)

Спасибо, было интересно читать.
(Ответить) (Thread)
[User Picture]From: yurri
2006-11-17 06:08 am
Ничего общего с C++.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: onodera
2006-11-17 06:02 am
О, International Obfuscated Perl Code Contest теперь выходит на whole new уровень запутанности.
(Ответить) (Thread)
From: 9000
2006-11-17 06:58 am
Более того: становится бессмысленным ;)
(Ответить) (Parent) (Thread)
[User Picture]From: ygam
2006-11-17 06:10 am
По-моему, chaining associativity было в Альфе, новосибирском диалекте Алгола-60.

Почему у меня в голове столько мусора?
(Ответить) (Thread)
[User Picture]From: eterevsky
2006-11-17 07:18 am
В Питоне есть для равенств и сравнений.
(Ответить) (Parent) (Thread)
From: ex_feuerbach769
2006-11-17 06:54 am
Очень интересно, спасибо.
А то что-то про Perl6 мне на глаза попадаются только сообщения вроде "изменился синтаксис такого-то оператора".
(Ответить) (Thread)
[User Picture]From: eterevsky
2006-11-17 07:21 am
Спасибо, действительно интересно. Из языков, в которых можно перенастраивать свой синтаксис мне вспоминается только TeX, но он, конечно, гораздо слабее.
(Ответить) (Thread)
[User Picture]From: bamsic
2006-11-17 07:56 am
Но Вам не кажется, что возможность подменять все и вся приводит к абсолютной нечитабельности кода?
Ведь есть шкала: <Отлично читабельный/Сильно ограниченный>....<Нечитабельный/Позволяющий все>.
Можно сравнить, например, BASIC и С++, в первом, глядя на программу сразу можно определить, что в программе делается (естественно в случае разумно составленной программы), во втором, уже требуется некоторое время чтобы разобраться потому, что конструкция a+b может значить что угодно - зависит от сущности этих a и b...
Я к тому, что свою же программу через некоторое время будет не возможно разобрать.
(Ответить) (Thread)
From: 9000
2006-11-17 09:12 am
Несмомненно. Это если неправильно подойти к использованию этих возможностей.

А если правильно -- то вопроса не возникает. Скажем, операция "+", будучи определена для строк или множеств, не вызывает вопросов :) А кто определяет "+" неинтуитивно, тот сам себе злобный буратина.

Беда, конечно, в том, что с кодом таких буратин потом иногда приходтся работать.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: oleg_bunin
2006-11-17 08:30 am
Отличный пост!
Спасибо!
(Ответить) (Thread)
[User Picture]From: nm_work
2006-11-17 09:00 am
оччень интересный пост, спасибо.

чисто лексическое: вы таки определитесь, парсинг, парсировка или парсирование :)

а для объектов можно переопределять операторы внутри самого модуля, где описан объект?

т.е. чтоб можно было бы создавать объекты, кторые имеют свои собственные операторы.

скажем чтоб можно было бы записать

Thread {
блок-кода-для-выполнения-в-отдельном-потоке;
};

это чисто гипотетически йприме, может даже неудачный.
(Ответить) (Thread)
[User Picture]From: avva
2006-11-17 09:09 am
Трудно определиться, да :)

С объектами и специальными для них операторами все очень мило. Во-первых, есть умный runtime-диспатч вызова функции, у которой может быть много воплощающих кандидатов, в соответствии с ее аргументами. Например, если у вас есть класс Foo, вы можете определить оператор &infix:<+> (Foo $x, Any $y) {...}, и теперь любой вызов + с объектом вашего класса слева автоматически вызовет ваш +, а не обычный. Если вы в определение добавите "is commutative", это сразу заработает на "справа" тоже. Это работает для всех операторов и вообще любых функций, определенных как multi sub, а не просто sub (т.е. обычная функция, sub - частный случай, про который заранее известно, что не будет других кандидатов; но все встроенные операторы определены как multi sub, позволяя их легко переопределять для конкретных классов аргументов).

Тот пример, который вы приводите, тоже можно сделать, ага. Специальные операторы могут быть локальными внутри определенного класса. Собственно, они могут быть просто методами класса, и все, что их отличает от других методов - "грамматическое" имя. Скобки {...} вообще говоря строят объект класса Code, который является closure, его так же можно держать в руках, как и все остальное, и можно передавать куда угодно и потом выполнить, когда захочется.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: cousin_it
2006-11-17 09:27 am
Синтаксис можно менять?

А знаки доллара перед переменными можно убрать?
(Ответить) (Thread)
[User Picture]From: mstone
2006-11-17 09:38 am
Афт Спасибо! Крайне полезный и познавательный пост. Я всегда потешался над нелепой фобией тех, кому перегрузка операторов кажется злом, делающим программы нечитабельными. Разруха-то, понятно, не в сортирах, а в головах. Но от такой синтаксической свободы всё равно становится немного не по себе.
(Ответить) (Thread)
[User Picture]From: dimad
2006-11-17 09:40 am
спасибо за информацию :) Как раз сейчас интересуюсь возможностями perl 6 и parrot.
(Ответить) (Thread)
Страница 1 из 2
<<[1] [2] >>