Часть 1. Як, слон и древесная крыса
Jan. 10th, 2010 01:01 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
thedeemonПочти все классические книжки и курсы по компиляторостроению начинаются с приемов разбора текста. И, я смотрю, многие разработчики тоже начинают писать свои компиляторы с парсинга. Не делайте этого! Это имеет смысл, только если разбираемый язык дан свыше каким-нибудь уважаемым божеством, а жрецы уже написали к нему сутры, шастры и кандидатские диссертации с комментариями. В противном случае дизайн языка начинает подчиняться ограничениям используемых инструментов парсинга, а сформулировать нормально грамматику становится очень сложно. Да и в выборе инструментов легко ошибиться. Вот вам мой совет: сперва опишите язык в виде структуры данных (алгебраического типа, например), реализуйте логику самого компилятора (в процессе структура может не раз поменяться), и лишь потом из нее уже делайте текст, перевод такой структуры в грамматику уже прост и линеен.
В поставку Окамла входит генератор парсеров ocamlyacc, сделанный по образу и подобию сишного yacc'a. Раньше у меня был позитивный опыт использования ANTLR и ocamlyacc. Первый делал рекурсивный спуск и годился для языков, которые можно однозначно разобрать, читая слева-направо, что явно не подходит для Leo. Ocamlyacc же, казалось бы, такого ограничения не имеет, поэтому я выбрал его. Парсингом я сейчас занялся в последнюю очередь, когда остальные части компилятора были готовы, и имея уже готовую структуру языка в виде набора алгебраических типов, сделать из нее описание грамматики было очень просто. Сгенерил окамляком (или стоит говорить окамлякой? :) ) парсер, стал запускать и столкнулся вот с чем. В Leo определение функции и ее вызов очень похожи:
Тогда я подумал: у меня же есть парсер-комбинаторы! Нафиг як, я все сделаю на них! Взял свою библиотечку классических комбинаторов, начал описывать лексемы, но тут появилась идея получше. Ocamlyacc используется в связке c ocamllex, который мне уже сгенерил работающий лексер. Почему бы мне мои комбинаторы не применить к последовательности лексем вместо символов? Заменил
Как известно, парсер-комбинаторы работают методом рекурсивного спуска с откатами и описывают самый натуральный PEG. Сформулировать грамматику (вместе с действиями по построению AST) на них оказалось очень просто, разве что пришлось позаботиться о том, чтобы не возникало левой рекурсии, вроде E -> E + E. Пример получившегося кода:
Парсинг на комбинаторах решил проблему с различением определения и вызова функций, и все вроде бы заработало, но появилась другая проблема, о которой предупреждали британские ученые, - экспоненциальное время разбора. Вы когда-нибудь ездили на ленивом слоне? Он идет медленно и сильно раскачивается. И не идет по дороге, а блуждает во всех направлениях, которые сочтет интересными, но если они не совпадают с нужным, то погонщик слону говорит "не, нам не сюда". Так, перепробовав все варианты, слон оказывается в той точке, про которую не сказали "не сюда". Вот и парсер-комбинаторы так же, перепробуют все комбинации вариантов, пока какой-нибудь один из них не сработает. И после каждого отката начинают заново делать одну и ту же работу. Например, чтобы распарсить выражение 42, мой парсер будет думать: "это или нечто, являющееся первым слагаемым суммы, или разности, или просто нечто. В любом случае оно состоит из произведения или отношения или деления с остатком или ксора или просто чего-то, что в любом случае состоит из простого выражения, за которым идет .head, или простого выражения, за которым идет .tail, или только простого выражения, а оно в любом случае состоит из одного из еще 12 вариантов, один из которых начинается на число". Сколько раз будут сделаны попытки разобрать эти варианты? 12*3*5*3 = 540. Это мы всего-то разобрали выражение 42. А если оно внутри другого, умножайте еще. Вот и экспонента. Программа в пару строчек разбиралась быстро. В три строчки уже несколько секунд. Пять строчек я не дождался. Запомните, дети, такие парсер-комбинаторы годятся только для очень простых грамматик.
Но тут во всякую голову придет простая мысль: если проблема в том, что одна и та же работа делается пицот раз, почему бы не делать ее один раз и не запоминать результат. Мысль совершенно очевидная, однако в 2002 году кто-то на ней защитил диплом и дал особое название - Packrat, т.е. древесная крыса. Откуда взялось такое название, я так и не понял. Чтобы исправить проблему со временем разбора, достаточно добавить в наши комбинаторы мемоизацию. А для этих целей отлично подходят ленивые вычисления. Заменим simple_expr на форсинг ленивого вычисления, а само вычисление переименуем:
В процессе обнаружился еще один большой плюс такого способа. В какой-то момент, расширяя грамматику языка, я случайно создал левую рекурсию, но непрямую: выражение состоит из произведений, те из чего-то, что состоит из простых выражений, одно из них может быть стейтментом, а один из стейтментов может быть выражением. Обычные парсер-комбинаторы на таком просто виснут, зацикливаются. А при мемоизации через ленивые вызовы получается, что при форсировании ленивого значения идет обращение к нему самому. Такую ситуацию рантайм окамла отлавливает и бросает исключение. В результате можно сразу увидеть, где есть такой цикл и исправить его, убрав левую рекурсию из грамматики.
В итоге весь парсинг языкаПанкратом Packrat'ом занял 150 строк, т.е. менее 10% всего компилятора. Кстати, те 5 строк с обращением к модулю Lazy - это единственное место, где мне пригодились ленивые вычисления. Все остальное прекрасно делается со всей строгостью, сразу понятно что, когда и как происходит.
Дальше: Часть 2. Иллюзорный автомобиль
В поставку Окамла входит генератор парсеров ocamlyacc, сделанный по образу и подобию сишного yacc'a. Раньше у меня был позитивный опыт использования ANTLR и ocamlyacc. Первый делал рекурсивный спуск и годился для языков, которые можно однозначно разобрать, читая слева-направо, что явно не подходит для Leo. Ocamlyacc же, казалось бы, такого ограничения не имеет, поэтому я выбрал его. Парсингом я сейчас занялся в последнюю очередь, когда остальные части компилятора были готовы, и имея уже готовую структуру языка в виде набора алгебраических типов, сделать из нее описание грамматики было очень просто. Сгенерил окамляком (или стоит говорить окамлякой? :) ) парсер, стал запускать и столкнулся вот с чем. В Leo определение функции и ее вызов очень похожи:
f(x,y,z) = print(x+y+z) # это определение f(a,b,5) # это вызовПодобные конструкции ставили парсер в тупик. f(x,y,z) = print(x+y+z) он правильно разбирал как определение. f(5,a,b) он правильно разбирал как вызов. f(x), за которым не было =, тоже мог понять, что это вызов, но вот f(x,y) (когда аргументов несколько и первый состоит из букв) уже не мог. Заставить его понимать такие вызовы у меня так и не вышло. То ли мое LR-fu недостаточно хорошо (чтение логов и таблиц состояний LR-анализатора в попытках понять причину конфликтов и ошибок - прекрасное занятие для тех, кому наскучил обычный мазохизм), то ли дело в том, что окамляка - LALR(1) парсер, т.е. разрешающий свои сомнения подглядыванием на 1 лексему вперед, и одной лексемы тут мало.
Тогда я подумал: у меня же есть парсер-комбинаторы! Нафиг як, я все сделаю на них! Взял свою библиотечку классических комбинаторов, начал описывать лексемы, но тут появилась идея получше. Ocamlyacc используется в связке c ocamllex, который мне уже сгенерил работающий лексер. Почему бы мне мои комбинаторы не применить к последовательности лексем вместо символов? Заменил
type 'a parse_result = Parsed of 'a * char list | Failed;;на
type ('a, 'b) parse_result = Parsed of 'a * 'b list | Failed;;и сразу перешел на описание грамматики.
Как известно, парсер-комбинаторы работают методом рекурсивного спуска с откатами и описывают самый натуральный PEG. Сформулировать грамматику (вместе с действиями по построению AST) на них оказалось очень просто, разве что пришлось позаботиться о том, чтобы не возникало левой рекурсии, вроде E -> E + E. Пример получившегося кода:
and simple_expr s = ( (tok Lpipe >>> expr >>= fun e -> tok Lpipe >>> return (Leo.Length e)) ||| (tok Ldo >>> opt_terms >>> stmts >>= fun code -> opt_terms >>> tok Lend >>> return (Leo.Comp code)) ||| (tok Llcurly >>> opt_terms >>> stmts >>= fun code -> opt_terms >>> tok Lrcurly >>> return (Leo.Comp code)) ||| (tok Lif >>> condition >>= fun con -> then_ >>> expr >>= fun e1 -> p_opt None (else_ >>> expr >>= fun e2 -> return (Some e2)) >>= fun e2o -> return (Leo.If(con, e1, e2o)) ) ||| (tok Lnew >>> atype >>= fun ty -> tok Llbracket >>> expr >>= fun e -> tok Lrbracket >>> return (Leo.New(ty, e))) ||| (tok Lbackslash >>> p_list ident (tok Lcomma) >>= fun ps -> tok Lfollow >>> expr >>= fun e -> return(Leo.Lambda(ps, e))) ||| (ident >>= fun name -> tok Llparen >>> args >>= fun es -> tok Lrparen >>> return (if name="print" then Leo.Comp [Leo.Print(List.hd es)] else Leo.Call(name, es))) ||| (ident >>= fun name -> tok Llbracket >>> expr >>= fun e1 -> tok Ldot2 >>> expr >>= fun e2 -> tok Lrbracket >>> return (Leo.SubArr(name, Leo.SRange(e1, e2)))) ||| (ident >>= fun name -> tok Llbracket >>> expr >>= fun e -> tok Lrbracket >>> return (Leo.Arr(name, e))) ||| (ident >>= fun name -> return (Leo.Var name)) ||| (int_ >>= fun i -> return (Leo.Val i)) ||| (tok Llparen >>> expr >>= fun e -> tok Lrparen >>> return e) ) s and expr s = ( (product >>= fun e1 -> tok Lplus >>> expr >>= fun e2 -> return (Leo.Arith(Add, e1, e2))) ||| (product >>= fun e1 -> tok Lminus >>> expr >>= fun e2 -> return (Leo.Arith(Sub, e1, e2))) ||| product ) s and product s = ( (value >>= fun e1 -> tok Lmul >>> product >>= fun e2 -> return (Leo.Arith(Mul, e1, e2))) ||| (value >>= fun e1 -> tok Ldiv >>> product >>= fun e2 -> return (Leo.Arith(Div, e1, e2))) ||| (value >>= fun e1 -> tok Lmod >>> product >>= fun e2 -> return (Leo.Arith(Mod, e1, e2))) ||| (value >>= fun e1 -> tok Lxor >>> product >>= fun e2 -> return (Leo.Arith(Xor, e1, e2))) ||| value ) s and value s = ( (simple_expr >>= fun e -> tok Lhead >>> return (Leo.Head(e))) ||| (simple_expr >>= fun e -> tok Ltail >>> return (Leo.Tail(e))) ||| simple_expr ) s(это добрая половина всего парсера).
Парсинг на комбинаторах решил проблему с различением определения и вызова функций, и все вроде бы заработало, но появилась другая проблема, о которой предупреждали британские ученые, - экспоненциальное время разбора. Вы когда-нибудь ездили на ленивом слоне? Он идет медленно и сильно раскачивается. И не идет по дороге, а блуждает во всех направлениях, которые сочтет интересными, но если они не совпадают с нужным, то погонщик слону говорит "не, нам не сюда". Так, перепробовав все варианты, слон оказывается в той точке, про которую не сказали "не сюда". Вот и парсер-комбинаторы так же, перепробуют все комбинации вариантов, пока какой-нибудь один из них не сработает. И после каждого отката начинают заново делать одну и ту же работу. Например, чтобы распарсить выражение 42, мой парсер будет думать: "это или нечто, являющееся первым слагаемым суммы, или разности, или просто нечто. В любом случае оно состоит из произведения или отношения или деления с остатком или ксора или просто чего-то, что в любом случае состоит из простого выражения, за которым идет .head, или простого выражения, за которым идет .tail, или только простого выражения, а оно в любом случае состоит из одного из еще 12 вариантов, один из которых начинается на число". Сколько раз будут сделаны попытки разобрать эти варианты? 12*3*5*3 = 540. Это мы всего-то разобрали выражение 42. А если оно внутри другого, умножайте еще. Вот и экспонента. Программа в пару строчек разбиралась быстро. В три строчки уже несколько секунд. Пять строчек я не дождался. Запомните, дети, такие парсер-комбинаторы годятся только для очень простых грамматик.
Но тут во всякую голову придет простая мысль: если проблема в том, что одна и та же работа делается пицот раз, почему бы не делать ее один раз и не запоминать результат. Мысль совершенно очевидная, однако в 2002 году кто-то на ней защитил диплом и дал особое название - Packrat, т.е. древесная крыса. Откуда взялось такое название, я так и не понял. Чтобы исправить проблему со временем разбора, достаточно добавить в наши комбинаторы мемоизацию. А для этих целей отлично подходят ленивые вычисления. Заменим simple_expr на форсинг ленивого вычисления, а само вычисление переименуем:
and simple_expr = function h::tl -> Lazy.force (get1 h) | [] -> Failed and simple_expr_r s = ( (tok Lpipe >>> expr >>= fun e -> tok Lpipe >>> return (Leo.Length e)) ||| (tok Ldo >>> opt_terms >>> stmts >>= fun code -> opt_terms >>> tok Lend >>> return (Leo.Comp code)) ||| (tok Llcurly >>> opt_terms >>> stmts >>= fun code -> opt_terms >>> tok Lrcurly >>> return (Leo.Comp code)) ...Нашим комбинаторам все равно, списком чего представлена входная программа, поэтому представим ее не списком токенов (лексем), а списком элементов, хранящих как лексему, так и ленивые вызовы разбора нужных выражений, начиная с данной лексемы. Сначала хотел использовать туплы, но их рекурсивно определять нельзя, а вот алгебраический тип - можно. Хотел использовать массив, но парсинг разных выражений дает результаты разных типов, их в один массив засунуть нельзя. Остановился на таком варианте:
type ttoken = TT of token * (Leo.expr, ttoken) Parsercomb.parse_result Lazy.t (* simple_expr *) * (Leo.expr, ttoken) Parsercomb.parse_result Lazy.t (* expr*) * (Leo.statement, ttoken) Parsercomb.parse_result Lazy.t (* stmt *) * (Leo.lvalue, ttoken) Parsercomb.parse_result Lazy.t (* lvalue *) let prepare tok_list = List.fold_right (fun tk res -> let rec v = TT(tk, lazy(simple_expr_r vlst), lazy(expr_r vlst), lazy(stmt_r vlst), lazy(lvalue_r vlst)) and vlst = v::res in vlst) tok_list []Функция prepare берет список лексем и возвращает список ttoken'ов, содержащих эти лексемы и пока еще невызванные вызовы разбора выражений, стейтментов и пр., начиная с текущей лексемы. Тут делается прикольная магия с путешествием во времени: значение v содержит вызовы функций с аргументом-списком vlst, содержащим само v. Когда парсер работает, он вызывает функции для разбора выражений, стейтментов и пр., которые вызывают сохраненные в нашем списке ленивые функции разбора, а они работают ровно один раз - при первом обращении. Все следующие обращения к ним возвращают сохраненный результат. В итоге, если надо разобрать выражение 42, то когда парсер дойдет до мысли "а уж не простое ли это выражение?" и проверит ее, он запомнит результат и в мыслях "а уж не сумма ли это или, может, произведение" будет использовать этот результат, вместо повторения проверок. Причем нам необязательно мемоизировать абсолютно все правила грамматики, достаточно это сделать для самых ветвистых. В классическом packrat'e мемоизируется все и обещается линейное время разбора, но в моем случае мемоизации 4 правил оказалось достаточно, чтобы от "очень медленно" перейти к "мгновенно".
В процессе обнаружился еще один большой плюс такого способа. В какой-то момент, расширяя грамматику языка, я случайно создал левую рекурсию, но непрямую: выражение состоит из произведений, те из чего-то, что состоит из простых выражений, одно из них может быть стейтментом, а один из стейтментов может быть выражением. Обычные парсер-комбинаторы на таком просто виснут, зацикливаются. А при мемоизации через ленивые вызовы получается, что при форсировании ленивого значения идет обращение к нему самому. Такую ситуацию рантайм окамла отлавливает и бросает исключение. В результате можно сразу увидеть, где есть такой цикл и исправить его, убрав левую рекурсию из грамматики.
В итоге весь парсинг языка
Дальше: Часть 2. Иллюзорный автомобиль
