Saturday, January 5, 2008

Развлекся

Есть у нас в Идее язык по имени QL, эдакая упрощенная версия SQL, диалекты которой используются в EJB и Hibernate. На вид несложный, однако в парсере периодически приходится туговато. Парсер, естественно, написан рекурсивным спуском, двумя с половиной разными людьми, и выглядит достаточно страшно. Я, в качестве добровольного каникулярного развлечения, попытался написать то же самое с использованием Праттовского метода. Тожесамовость измеряется duck-критерием: есть 141 тест, и на них нужно выдавать такое же дерево, что и старый парсер. В код старого парсера я смотрел нечасто, поэтому то, что незатестировано, соответственно, не воспроизведено.

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

Код парсера занимает меньше места: 1032 строки в старом против 620 в новом. При этом есть 14 стандартных постфиксных субпарсера и 21 инфиксный, все они выражаются здесь одной строчкой, в оригинальном парсере - побольше (строчек 5 в среднем, я думаю).

Читать новый парсер и проще и сложнее одновременно. Сложнее потому, что он необычен, непривычен, и потому, что нужно очень хорошо себе представлять стек исполнения во время парсинга многих токенов. В рекурсивном спуске обычно хватает названия метода, парсящего текущий нетерминал, и, может быть, каких-нибудь флажковых параметров. Здесь периодески нужно знать, какие узлы слева уже построились, и при построении каких узлов процесс парсинга вызывался рекурсивно. Самая жестокая моя проверка в этой области звучит так: если наш токен парсится первым в этом стековом фрейме, в следующем слева от нас есть запятая, перед которой мы распарсили декларацию переменной, то идентификатор мы парсим как TypeReference. А иначе (тоже не всегда) - как ReferenceExpression.

Теперь почему читать проще. Потому что поток управления проще. Интереса ради я сравнил количество управляющих ключевых слов, которые смог придумать. Итак:

keyword old new
------------------------------
if >107 57
else if 28 1
else 12 6
while (все) 16 15
while (true) 3 11 (типа простой цикл)
break 6 11
for (java 5) 0 3
return 65 35

Переменные 47 37
Вызовы mark() 28 13


Максимальный уровень блочной вложенности в новом парсере 4, в старом - 7 (к счастью, только в одном месте, в среднем же примерно одинаково).

Вообще, конечно, Пратту такое и не снилось. Он статью писал вообще-то даже не про парсеры, а про языки. Что если придумать язык, который таким вот парсером парсится легко и без проблем, то и человеку он будет совсем понятным. А когда нетерминалы не определяются одним-единственным токеном однозначно, то это есть плохо и непонятно. Отсюда мораль - QL - это не самый понятный для человека язык (согласен, особенно joins).

5 comments:

Konstantin.Solomatov said...

А вот если бы ты написал бы язык для написания парсеров на MPS, то все было бы намного проще :-)

Konstantin.Solomatov said...

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

Peter said...

МПС бы, сдается мне, не очень сильно помог бы. Ровно по той причине, что код получается практически недекларативный. Декларативным бы он был, если бы язык был читабелен по Пратту. А тут надо ошибки обрабатывать, восстанавливаться, и вообще. Одни joinы распарсить - мерзость полнейшая, декларативно такое я вообще себе не представлю.

И, кстати, декларативный код очень сложно дебажить.

Тестировать надо исключительно затем, чтобы не сломать. Сломать рекурсивный спуск довольно просто, сломать этот новый метод - вообще как нефиг делать.

Konstantin.Solomatov said...

Я неправильное слово использовал. Не сделать декларативным, а сделать Domain Specific, то есть заDSL-ить.

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

Peter said...

DSL - это правильно, а то особенности синтаксиса анонимных классов в Жаве меня достали. Без них все было бы намного короче.

Но вряд ли в MPS, ибо все-таки хочется, чтобы парсер жил в Идее и был ее частью, а я с трудом себе представляю это с MPS.

С восстановлением да, примерно так оно и есть, только вот в коде оно почему-то каждый раз выглядит чуть-чуть по-разному :). Кстати, а дебажить DSL, думаешь, просто?