Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
Форум программистов > Функциональные языки: общие вопросы > [CamlP4] О лексерах, парсерах и CamlP4 |
Автор: Sardar 6.1.2006, 17:25 | ||||||
Полученный автомат как направленный граф в скриптовом языке держать и использовать эффективно не получиться, всё равно окажуться реги быстрее ![]()
Это уже полноценные парсеры, не путаем с лексерами - генератор потока символов для синтаксического анализатора. |
Автор: Void 6.1.2006, 17:36 | ||||
Спасибо, я понимаю разницу между лексическим и синтаксическим анализом ![]() По поводу XML (да простит меня setq и все остальные, что я занимаюсь пропагандой в неподобающем разделе ![]()
Чем больше я вожусь с OCaml и CamlP4 в частности, тем больше убеждаюсь, что для задач парсинга пока ничего лучше не придумано ![]() |
Автор: Sardar 6.1.2006, 18:16 | ||
Млин ну почему такой убийственный синтаксис у большинства "редких" языков... ![]() На счёт XML, задача не читать XML как поток элементов, а как поток событий твоей логики. Обычно многие вещи сериализуем в XML, только эти вещи не всегда DOM деревья по определению, а обьект с точно известным структурой, его нужно "разбудить" из ранее записанного файла. WDDX не подходят, т.к. файл составляеться человеком, а человеку приятно работать с вещами имеющими смысл в контексте задачи, а не <var><number><string> и т.д. SAX парсер выполняет роль лексического анализатора, далее чем угодно превращаем поток "open element", "close element", "character data" (остальное игнорируем) в поток событий "делай XXX". Xорошо бы увидеть пример такого на OCaml. У меня это базовый класс SaxAnalyzer и его потомки, дефинирующие автомат и реализующие методы "делай XXX", PHP. А вообще жестокий offtop это всё, 2модератор хорошо бы тему поделить ![]() |
Автор: Void 6.1.2006, 18:28 | ||||||||
Дело привычки ![]() (http://flint.cs.yale.edu/cs421/case-for-ml.html - ППКС)
Ну так легче наверное написать собственную тонкую обертку над высокоуровневым чтением XML, чем вручную парсить его ![]()
Хачу форум, где это не будет оффтопом! ![]() Добавлено @ 18:28 Sardar Мне показалось, или твое сообщение изменилось? Давно хотел обратиться к модераторам с просьбой не пользоваться возможностью редактировать сообщения, не оставляя следов ![]()
Попробую. |
Автор: setq 6.1.2006, 19:01 |
да. пожалуй пора делить. вы где предпочетаете продолжить дискуссию: в Питоне или в Разном? |
Автор: Void 6.1.2006, 19:16 |
setq По-моему, к Питону тема имеет минимальное отношение. |
Автор: Void 6.1.2006, 23:27 |
Sardar Можно привести минимальный примерчик XML, который надо распарсить, и что по нему желательно сделать? SAX-парсеров для OCaml достаточно, как оберток над C-библиотеками (expat, libxml), так и нативных, но мне интересно, обязательна ли здесь event-driven модель? |
Автор: Sardar 7.1.2006, 03:49 | ||||||
Привычка у меня набить пост, отправить, а потом в первые минуты корректировать и убирать ошибки... ![]() Вот реальный:
А собрать это дело нужно в ассоциативный (id-ключ) список контейнеров resource, каждый из которых содержит ассоциативный (name-ключ) список scheme, каждая схема это массив обьектов part. Идея в том что бы по запросу: $map->buildURL({имя ресурса}, [{параметры}=>{значение}...]); Генерить ссылки, simple как обычные URL, под схемой rewrite красивые ЧПУ. Сразу приведу свой код загрузчика:
Громоздко, но работает ![]() Кстати почти всё у меня в текущем проекте лежит в XML, удобно очень для человека. В то же время читать это при каждом запросе не очень приятно, потому все прочитанные XML кешируються в нативный для PHP формат (функцией serialize). В результате компромис между удобством и эффективностью ![]() |
Автор: Sardar 7.1.2006, 04:16 | ||
Сам SaxAnalyzer, базовый абстрактный класс.
|
Автор: Sardar 7.1.2006, 05:09 | ||
Не понял что есть "type inference", это вроде обьявление переменной, не указывая типа, а её тип точно определяеться по операторам что ты используешь, операторы для разных типов разные (для целых одни, для вещественных другие, строки третьи и т.д.) ? По моему это большая лажа... Также я понял списки могут хранить значения только одного типа... Мне после скриптового мира сложно понять как с таким ограничением жить... На счёт библиотек это явное ИМXО автора, считаю либы в Java хорошим примером как нужно вообще либы делать, сюда же припишем модульность. По словам автора ML (OCaml) это язык для работы со сложными структурами данных(списки, деревья и т.д.), при чём всё это реализованно в языке. Основной способ работы с данными в языке это рекурсивные функции. Вообще звучит очень не плохо, когда нужно реализовать сам компилер, но что будет когда встанут такие задачи как зачитать файл, удобная работа с бинарными файлами(считать смещения и генерить байты самим не есть удобно), работа по сети, вычисление в несколько потоков на нескольких процах (хотя это функциональный язык, тут by design распаралеллить выполнение можно), высокоуровневая работа с памятью (фантомные обьекты, сериализация, свопить по запросу и т.д.), да вообще много задачь встанет на пути построения компилера, помимо самой логики компилера... ![]() |
Автор: Void 7.1.2006, 14:26 | ||||||||||
Ага, вижу ![]()
Ну-ну... Хиндли и Милнер отнюдь не дураками были. Разные операторы - это действительно иногда неудобно, но и эта проблема вполне решается - см. type classes в Haskell. После некоторого привыкания наоборот раздражает необходимость везде писать явные определения типов.
Плата за типобезопасность. Тем не менее, вариантные типы выражаются легко и удобно.
Библиотеки имелись в виду именно работающие со структурами данных. В принципе, да, ничего действительно выдающегося в них нет - но эти библиотеки по крайней мере не хуже существующих сегодня аналогов в других языках. По поводу модульности: это писалось в 1998 году, никакими дженериками тогда и не пахло, и экспортировать из модуля полиморфные функции не мог ни один ИЯ (Ада, maybe?). А аналогов функторам по-прежнему нет.
А в чем проблема? Средстав для работы с бинарным файлами есть в любых языках.
Стандартная сериализация произвольных данных в OCaml есть. Явное управление памятью затруднено (GC как никак), так что если стоит задача жесткой экономии памяти при компиляции, то будут затруднения. Но предполагается, что на этапе программирования основной логики мы выиграли столько времени по сравнению с традиционными языками, что есть возможность и потюнить ![]() Я отнюдь не считаю, что OCaml - идеальный язык. О нет. В нем есть масса вещей, которые мне не нравятся и даже раздражают. Это касается и принципов языка, и особенностей единственной существующей реализации от INRIA. Но конкретно в области парсинга и создания DSL большинство из этих неудобств не проявляются. |
Автор: Cr@$h 7.1.2006, 17:32 | ||
Может F# понравится еще больше -- посмотри http://research.microsoft.com/projects/ilx/fsharp.aspx. Разработан Microsoft. Интересно, что для "функционального" языка, а F# -- это от functional, был выбран фирмой именно OCalm, а не что-то из семейства LISP'а или Mirand'ы. Естественно, OCalm не только функциональный (декларативный, как я люблю употреблять), но и императивный и даже ООП-язык! |
Автор: Void 7.1.2006, 19:12 | ||
Cr@$h Спасибо, F# я смотрел уже давно. Вещь интересная, но до оригинального OCaml кое в чем не дотягивает, увы. Добавлено @ 19:12
Зато автор GHC - лучшего компилятора Haskell - работает в Microsoft ![]() Но OCaml действительно наиболее практичный из ныне существующих декларативных языков, не считая Erlang, занимающего свою особую нишу. |
Автор: Void 8.1.2006, 13:48 | ||||||||||
Итак, как и обещал, разбор XML на OCaml. Сразу скажу, что если бы это было реальное приложение, я бы взял более надежный и проверенный временем парсер XML для OCaml - PXP, например. А так это получается proof of concept декларативного разбора XML. Я не реализовал разворот переменных окружения в default и перекодировку не-ASCII символов. В остальном все вроде работает одинаково. Документации тоже нет, но названия функций и исключений вроде говорят сами за себя. Модуль Util. То, что его пришлось написать, целиком на совести автора OX ![]() Интерфейс:
Реализация:
Собственно основной модуль Urlbuilder. Интерфейс:
Реализация:
Пример использования:
|
Автор: Sardar 10.1.2006, 05:28 |
Ого... у меня обычно получаеться читать код на не знакомом языке сразу и без проблем, но такой код... млин убил целый вечер, потому сначала о языке ![]() Возможно буду говорить глупости, прошу прощения, впервые вижу OCaml и вообще с подобными мозгодробильными вещами не знаком ![]() OCaml ставят как функциональный язык ООП "фичами". Как то не проходит "workaround" чувство, как будто OOП притянуто за уши. По коду вижу обьектов "нет", есть классы/модули с функциями принимающими обьекты своих типов, так и C можно назвать ООП языком... Синтаксис убойный, особено добило отсутсвие явной return операции, надо постоянно думать что последнее выражение и есть возвращаемое, если я правильно понял... В сборке строк flatten_parts вижу Buffer.create 32, это случайно не ограниченный по размеру буффер? Тогда PHP рулит ![]() И Hashtbl.create принимает аргумент число, это что, количество ковшей или максимальная длина ключа? Здесь PHP рулит, он лимитов вроде не имеет ![]() Вся прога это туева хуча closures, что правильно, это же функциональный язык. А в практическом плане, проц не любит прыжки по коду, как эффективно тогда исполняеться код? Вся сила как я понял в match ... with конструкции, что очень загадочна, т.к. принимает строки, типы и даже... собсно <scheme name=name> _+ as parts </> что это? Не строка, видел что строки (по крайней мере один символ) в кавычках должны быть. Также не хороший это парсер если парой пробелов больше между <scheme и name и он не сможет найти. match принимает слева XML, видать какая то либа, что логику поиска и реализует, а match "перевызовет" эти функции из XML. А что тогда возвращаеться и вообще что это в языке <...>, какая то особая структура? Млин теперь вопросов море(конкретно возможности match и её возможные формы), а разбираться с OCaml нет времени/возможности, да и язык своим синтаксисом не приятен. Особено добило правило именования, нафига сокращать имя хеш-таблицы и писать функции/замыкания через '_'... не привычно ![]() |
Автор: Void 10.1.2006, 12:23 | ||||||||||||||||||||||||
Не то чтобы за уши... Говорят, ООП в OCaml появилось, чтобы Didier Remy защитил диссертацию ![]()
Слово "нет" можно без кавычек ![]() Вообще, ООП в OCaml достаточно интересное... Отношение наследования (is-a) нет, есть отношение subtyping'а (like-a); все методы всегда виртуальны. Т.е. получается такая статическая утиная типизация. Впрочем, без лишних разговоров пример ООП на OCaml (прим.: private здесь эквивалентно protected в C++/Java):
Да, для любого оператора это так.
Нет, это всего лишь начальный размер буфера, он растет по мере необходимости.
Это тоже начальное число ковшей, хинт для создания хэш-таблицы.
Слышу ли я это от любителя скриптовых языков? ![]()
Нет, при всей своей мощи pattern matching с типами, к сожалению, не работает ![]()
Вот! В этом-то вся фишка ![]() Но CamlP4 с таким же успехом можно использовать и для создания собственных пасеров, не привязанных к бэкэнду OCaml. Грамматика CamlP4 - это в конечном счете всего лишь функция, преобразующая поток лексем в значение любого типа. Чтобы работать, как синтаксическое расширение, она должна возвращать описанный в специальном модуле тип AST OCaml, но это совсем не обязательно. Впрочем, опять-таки лучше привести пару строк кода; итак, мини-калькулятор на CamlP4:
Теперь, думаю, понятно, почему Spirit вызывает у меня улыбку ![]() CamlP4 в состоянии разбирать LL(1) грамматики, автоматически производить факторизацию правил, устранение леворекурсивности и заботиться о приоритетах и ассоциативности операторов. Собственно, вернемся к XML ![]() ![]() Да, забыл сказать, лишние пробелы, естественно, не помеха, парсер отнюдь не берет конструкции из кода буквально.
В базовой форме (без расширений) match декомпозирует любые значения, кроме функций (ну это понятно) и объектов (наверное, чтобы не нарушать инкапсуляцию?).
Вот тут немного не понял ![]() P. S. Прошу прощения, только сейчас заметил, что код escaped_xml_string скопировал вместе с фатальной ошибкой: незавершенная &...; последовательность приводит к unhandled exception Not_found. Уже поправил. |
Автор: Void 14.1.2006, 00:40 | ||
Guest Послушайте, не стоит здесь разговаривать в таком тоне.
С любым? За 10 минут? Если честно, мне - слабо. Хотя я считаю, что синтаксис - дело вторичное, и предпочитаю видеть его расширяемым. |
Автор: sergejzr 19.1.2006, 03:33 |
[offtop] Ребят, а почему у нас не подсвeчивается OCalm? Если пишется столько кода, надо бы и подсвртку для него сообразить, не правда ли? ![]() |