thedeemon: (Default)
В текущем проекте на haXe нужно читать из сети AVI файл и по мере его загрузки разбирать и декодировать. Для начала для простых тестовых файлов был сделан простой разбор в лоб, но быстро стало понятно, что такой подход не масштабируется - объем кода быстро растет, а логика по нему сильно размазывается. Захотелось декларативного описания разбираемого формата, вспомнил про парсер-канабинакомбинаторы. Но они работают там, где весь необходимый инпут уже есть, для загружаемого постепенно нужно их готовить по-другому. Посмотрел было на проект reactive parsing (RxParsers), но там под тоннами бойлерплейта найти здравую мысль оказалось очень сложно, а автор честно признался, что парсер-комбинаторы видел впервые и как работает его проект сам толком не понимает. В общем, сделал я свое решение, простое и удобное.
Read more... )
thedeemon: (Default)
Некоторое время назад меня пытались убедить, что Окамл недостаточно хорош для парсер-комбинаторов, потому что стоит попытаться добавить в парсеры состояние, как тут же возникают трудности, связанные с нехваткой полиморфизма. Проблема там вот в чем. Мой вариант простых парсеров не содержал состояния, и парсером там была функция типа char list -> 'a parse_result, где тип результата выглядел так:

type 'a parse_result = Parsed of 'a * char list | Failed

В определенном смысле какое-то состояние в таких парсерах есть - это текущая позиция в разбираемом тексте, определяемая неразобранным остатком текста, возвращаемым в случае успеха. Для разбора контекстно-зависимых грамматик иногда хочется, чтобы парсер имел какое-то дополнительное состояние. Например, при разборе текста на С++ хорошо бы помнить имена описанных ранее классов, чтобы понимать, что означает some_name(42). Расширим наше определение парсера и добавим передачу произвольного состояния:

type ('res, 'state) parse_result =  
  Parsed of 'res * ('state * char list) | Failed

Read more... )
thedeemon: (Default)
"Сломался меч о пресс
При совершеньи харакири.
Проклятый цигун!"


К сравнению парсеров добавил Boost.Spirit 2.2 (из boost 1.42), там подсистема парсер-комбинаторов называется Qi (Ци). Порадовался лаконичности описания грамматики. Повеселился, глядя как компиляция маленького примера отнимает 20 секунд и 400 мегов памяти. Скорость парсинга оказалась чуть хуже классических комбинаторов на Окамле со списками, если не считать время на создание исходного списка, а только сам парсинг. 18 МБ/с. Поскольку это мой первый опыт со Spirit'ом, я мог все сделать неправильно и медленно, поэтому обращаюсь к общественности с той же просьбой: глянуть код (менее сотни строк) и подсказать, где я налажал. Как минимум, есть подозрение насчет неиспользования skip-parser'a. Код выложил здесь. Компилировал в VS2005.
thedeemon: (Default)
Помня о том, какое бурление вызвало сравнение скорости Лиспа с другими языками в прошлом номере ПФП, прошу помощи зала не допустить несправедливости. Я сейчас доделываю сравнение скорости разных методов парсинга, сделал вариант на Хаскеле на базе Parsec2, и получившаяся скорость мне совсем не нравится. До этого на Хаскеле не писал, поэтому наверняка мог сильно налажать. Исходник (~70 строк) выложил здесь.
Суть программы - чтение карты формата OpenStreetMap и вычисление ее реальных границ - минимальных и максимальных значений широты и долготы встреченных точек. Собирал ее с GHC 6.8.3 и 6.10.1, Parsec 2.1.0.1, команда для сборки:
ghc -O2 -package parsec bounds.hs -o bounds

Сейчас скорость получается около 3 МБ/с.
Пример простой карты тут. Скорость тестировал на карте Сингапура (архив 1.2 МБ).

Прошу более опытных товарищей глянуть на исходник и указать на явные косяки. Можно ли заметно ускорить программу без сильных изменений описанной там грамматики?
thedeemon: (Default)
Почти все классические книжки и курсы по компиляторостроению начинаются с приемов разбора текста. И, я смотрю, многие разработчики тоже начинают писать свои компиляторы с парсинга. Не делайте этого! Это имеет смысл, только если разбираемый язык дан свыше каким-нибудь уважаемым божеством, а жрецы уже написали к нему сутры, шастры и кандидатские диссертации с комментариями. В противном случае дизайн языка начинает подчиняться ограничениям используемых инструментов парсинга, а сформулировать нормально грамматику становится очень сложно. Да и в выборе инструментов легко ошибиться. Вот вам мой совет: сперва опишите язык в виде структуры данных (алгебраического типа, например), реализуйте логику самого компилятора (в процессе структура может не раз поменяться), и лишь потом из нее уже делайте текст, перевод такой структуры в грамматику уже прост и линеен.
Read more... ) Запомните, дети, такие парсер-комбинаторы годятся только для очень простых грамматик.

Но тут во всякую голову придет простая мысль: если проблема в том, что одна и та же работа делается пицот раз, почему бы не делать ее один раз и не запоминать результат. Мысль совершенно очевидная, однако в 2002 году кто-то на ней защитил диплом и дал особое название - Read more... )
В итоге весь парсинг языка Панкратом Packrat'ом занял 150 строк, т.е. менее 10% всего компилятора. Read more... )
thedeemon: (Default)
Я летом писал про классические парсер-комбинаторы на Окамле и жаловался, что у меня не получилось сделать рекурсивные, вроде такого:

let rec p_exp =  p_char 'a' ||| (p_char '(' >>> p_exp >>> p_char ')')

Такой парсер должен разбирать строки 'a', '(a)', '((a))' и т.д., но ругаться на '((a)'.

При попытке компиляции приведенной строчки выдавалось малоинформативное сообщение This kind of expression is not allowed as right-hand side of `let rec'. Оказывается, все очень просто. В правой части let rec может быть очень ограниченный набор конструкций, если они содержат одно из рекурсивно определяемых имен. Одна из поддерживаемых - fun. Все начинает компилироваться и правильно работать, если обернуть правую часть в нее:

let rec p_exp = fun s -> (p_char 'a' ||| (p_char '(' >>> p_exp >>> p_char ')')) s
thedeemon: (office)
На днях в качестве эксперимента реализовал на OCaml идею оптимизирующих парсер-комбинаторов.
На одном ядре 2.33 GHz и тестовой задачке с рсдн получилось 35 МБ в секунду, что существенно быстрее обычных парсер-комбинаторов на Окамле и даже вроде бы быстрее чем С++ / Boost.Spirit.

Profile

thedeemon: (Default)
Dmitry Popov

September 2017

S M T W T F S
     12
3456789
10111213141516
17181920212223
24252627282930

Syndicate

RSS Atom

Most Popular Tags

Style Credit

Expand Cut Tags

No cut tags
Page generated Sep. 26th, 2017 07:22 am
Powered by Dreamwidth Studios