Saturday, December 29, 2007

Как писать парсеры

Обычно парсеры языков программирования пишутся в виде грамматики, которая либо скармливается потом генератору, либо уже представляет собой код с использованием парсер-комбинаторов. К сожалению, если язык сложен, грамматика его тоже непроста. А сложным, надо сказать, становится любой язык, когда в него нужно добавить разумную обработку ошибок и восстановление после таковых, и при этом выдать какое-то достаточно вменяемое синтаксическое дерево на выходе. Ровно это необходимо для хорошей поддержки языка в IDE.

Поэтому в самой знакомой мне IDE парсеры пишутся обычно руками, рекурсивным спуском, скучно, занудно и однообразно (чего стоит один практически идентичный код, раскопированный для каждой бинарной операции). Восстановление после ошибок тогда получается достаточно несложно.

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

Итак, по старинной фортовской привычке мы начинаем с объявления данных кодом. Данные у нас - это поток токенов от лексера, вот они-то и будут кодом. У каждого токена будет свой собственный маленький кодик, вот такого вида:

interface TokenParser {
boolean parseToken(PrattBuilder builder);
}

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

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

Это была фортовская часть. Теперь к Пратту. Самый частый вариант токенпарсера, DefaultTokenParser, реализован заветами этого товарища, и умеет различать два случая вызова себя и делегировать всю работу одному из двух подпарсеров - соответствующих своих аргументов конструктора. Первый случай, "свежачок", когда токен встретился сразу же в билдеровском parse, слева от него ничего еще нет, у Пратта это зовется nud, у меня пока - PrefixParser (better name needed!!!). Второй случай, когда слева уже что-то есть, и там даже построился узел дерева с определенным типом, у Пратта - led, у меня пока - ProceedingParser (oh name...). Первое используется, когда по токену можно понять, какую конструкцию он начинает (унарная префиксная операция), второй - какую конструкцию он продолжает (инфиксная бинарная операция или много чего еще) или закачивает (унарная постфиксная операция).

У токена нечасто определены оба компонента, самый очевидный пример токена, умеющего и начинать и продолжать - "+" или "-". Если nud или led нужен, но отсутствует, генерируется ошибка. Токен, который мы анализировали, нам уже неинтересен, мы с него все, что хотели, получили, поэтому перед вызовом подпарсеров лексер сдвигается вперед. Оба подпарсера возвращают тип узла, который надо построить от стартового маркера до текущего места. Обычно алгоритм разбора токенпарсера по умолчанию получаются следующим: вызываем nud первого токена, а потом, пока не посинеем, вызываем led у текущих токенов.

Пример простого нуда на псевдоязыке:

unary(IElementType type, int priority) = fun (builder) ->
builder.parse(priority);
return type

И еще проще:

tokenElement(IElementType type) = fun (builder) ->
return type

Пример простого леда (бинарная левоассоциативная операция) почти дословно такой же:

binary(IElementType type, int priority) = fun (leftType, builder) ->
builder.parse(priority);
return type

Постфиксная операция еще проще:

postfix(IElementType type) = fun (leftType, builder) ->
return type

Распарсить простые выражения можно теперь с помощью весьма лаконичного кода:

NUMBER: priority=10, nud=tokenElement(NUMBER_LITERAL)
IDENTIFIER: priority=10, nud=tokenElement(QNAME)

"(": priority=10, nud=fun (builder: PrattBuilder) ->
builder.parse(0);
builder.assertToken(")");
return PARENTHESES

".": priority=9, led=binary(QNAME, 9)
"!": priority = 8, nud=unary(NEGATION, 8)

"+","-": priority=8,
nud=unary(ARITHMETIC_UNARY, 8),
led=binary(ARITHMETIC_BINARY, 6)
"*","/": priority=7, led=binary(ARITHMETIC_BINARY, 7)

Парсер, например, для сокращенного определения класса в Java лучше выражается через просто токенпарсеры:

"public", "static", etc.: priority = -100,
tokenParser = fun (builder) ->
builder.advance();
return true;
"class": priority=-100,
tokenParser = fun (builder) ->
builder.finishPrefix(MODIFIER_LIST);
builder.advance();
builder.assertToken(IDENTIFIER);
if (builder.assertToken(EXTENDS)) {
builder.advance();
builder.parse(9);
}
builder.assertToken("{");
builder.parse(-90);
builder.assertToken("}");
return JAVA_CLASS

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

В данный момент на праттовской основе (только, увы, в синтаксисе Java) в достаточной степени написан парсер для языка шаблонов FreeMarker, и процесс мне нравится. Парсер получается более прямолинейный, проверок условий в нем намного меньше, чем в обычном рекурсивном спуске. Это можно рассматривать как паттерн Visitor, он же полиморфизм, мы вместо делания многочисленных проверок на тип вызываем абстрактный метод у самого типа.

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

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

Еще особенность, уж не знаю, достоинство или недостаток. При написании парсера надо думать. Этот парсер не совсем похож на грамматику, и не пишется на автомате, глядя на таковую. Скорее всего, такие парсеры тоже можно генерировать по грамматике, для этого надо только погрузиться в соответствующую науку. Но это уже совсем другая история.

Saturday, December 22, 2007

Запруды

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

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

Пришлось пользоваться враждебным Эклипсом, под которым есть камль-плугин, который умеет в собственной эклипсовской консоли (с, о счастье, настраиваемой кодировкой!) писать output программы. Круто. После пары часов траха с эклипсом и настройки подхвата им стандартных и не очень (OUnit) библиотек, наконец, удалось скомпилить и запустить прогу из трех исходных файлов, и тут настал окончательный сокрушительный удар судьбы. Камль не поддерживает юникод. То есть, абсолютно. Символьный тип в нем занимает один байт. А моей проге по большому счету все равно, из чего состоят обрабатываемые ею последовательности, главное, чтобы это что-то членилось на составные части предсказуемым образом. А если в строке записаны символы из UTF-8 или еще чего похуже, то члениться она в абстрактной камлевой программе будет уже способом, несовместимым с общепризнанным.

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

Можно все писать на Scheme. Забавный язычок такой, интересно было бы с ним поэкспериментировать. Правда, IDE для него, хоть и сильно удобнее камлевого топлевела, все же смущает MDIшностью своего интерфейса. Еще я так до сих пор не до конца привык к динамической типизации. И, что самое главное, под имеющуюся у меня Схему нет большого количества библиотек общего назначения. В жизни вообще нужно не очень много утилит, но вот SortedSet и SortedMap были бы неплохи. Да и просто Set тоже... В чистом виде я их под Схему не нашел.

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

Monday, December 3, 2007

peter-mac:~ peter$

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

Процесс организован следующим образом. Сидит лингвист, смотрит на какой-нибудь неправильный промтовый перевод, размышляет. Придумывает новое правило, которое все разом возьмет и полечит. Идет к программисту, объясняет правило, программист это дело кодит. Далее есть 18М тестовых текстов (или текстовых тестов?), на которых прогоняются старый и новый варианты, и просматриваются отличия (hopefully их немного). Если отличия случились в плохую сторону, лингвист идет думать дальше, иначе изменения принимаются.

Если я все правильно понял, весело быть программистом в ПроМТе. Сидишь, никого не трогаешь, приходят к тебе красивые девушки и рассказывают про правила какого-нибудь экзотического языка. Кругозор, понимаешь, расширяют. Кайф!

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

Расследование показало, что при добавлении какого-нибудь нового языка к системе подсаживается специально обученная группа экспертов, которые долго думают, а потом ее расширяют так, чтобы она нормально угадывала парадигмы и из этого языка. А именно, дописывают еще пару сотен правил. Возникает резонный вопрос - а нафига? Можно же сделать еще более умную систему, которая будет сама на основе примеров выводить те самые правила, которые сейчас в нее забиваются руками! Причем именно для данной задачи (вывод парадигмы) это, по идее, должно быть достаточно просто. И, по счастливому совпадению, это ровно та задача, про которую я туплю уже некоторое время. Так что вот, надо решать.