← All posts tagged XML

Macil
Haskell XML Кто о чём, а вшивый — о бане, в смысле, об очередной модели XML.
Если мы рассмотрим XML как цепочку символов StartTag a, EndTag a, Content a (или как говорят в соответствующей литературке — SAX), то совсем нетрудно будет заметить что он относится к классу языков сбалансированных скобок, т.е. не является регулярным.
Это не является проблемой самой по себе: мы всегда можем построить КА для разбора конкретной цепочки, и даже множества цепочек... Чем, собственно говоря, и занимаемся путём ваяния XML-схем различной степени упоротости.
А если есть способ? Нет понятно дело, можно перейти на новый уровень, взять МП-автомат и невозбранно юзать контекстно-свободные грамматики. Но тогда мы теряем всю алгебраическую вкусноту, присущую регулярным языкам... А в реальном мире алгебраические свойства регулярных языков куда важнее, чем возможность допускать более «широкие» множества цепочек!
Нет. Именно способ разбирать языки сбалансированных скобок, сохраяняя при этом все свойства регулярных языков. Как оказалось — есть!
Интуитивным объяснением почему КА не может разбирать языки сбалансированных скобок является отсутствие «памяти» . А если эту память можно присобачить?
Встречайте: Nested Word Automata (автоматы вложенных цепочек), а точнее его практическую реализацию Visibly Pushdown Automata.
Идея в том, что данный автомат жрёт три разных типа символов: «call» — обозначается как <a, «internal» — обозначается как a и «return» — обозначается как a>. Соответственно и функция переходов распадается на три: для символов «call» принимает текущее состояние и входящий call-сивол и возвращает следующее состояние и сивол который нужно засунуть на вершину стека, для «internal» принимает текущее состояние и входящий internal-символ и возвращает следующее состояние (т.е. как обычный КА), для «return» принимает текущее состояние, входящий internal-символ и символ с вершины стека и возвращает следующее состояние.
Т.е. в резултате мы получили класс МП-автомата, который не может за один символ запихивать и выпихивать символ из стека. Это повлияло на количество распознаваемых языков, но позволило сохранить свойства регулярных языков!
Более того, если у нас есть дерево t(a, b(c, d), e), то мы его можем закодировать как цепочку <t <a a> <b <c c> <d d> b> <e e> t>, т.е. ровно по такому же принципу как это делают SAX-парсеры.
За последний десякток лет была масса исследований на эту тему. С подборкой можно ознакомиться
madhu.cs.illinois.edu
cis.upenn.edu
Основополагающя статья Adding nesting structure to words: cis.upenn.edu
Слайды: cis.upenn.edu (с них лучше начать).

А теперь пара вопросов касательно первотега:
1. Неоднократно слышал что applicative-парсеры описывают регулярные языки. Где можно об этом почитать?
2. Кто-нибудь сталкивался с реализациями МП-автоматов на Х-е? Будут полезны также всякие LR/GLR/LALR реализации.

P.S.: Сабж применяется не только к XML, и вообще первоначально применялся для анализа программ, отсюда и call- и return- терминология.
Macil
? Haskell XML lexing Есть одна ебанутая спецификация, которая требует отдельные 0x0D заменять на 0x0A, а пары 0x0D 0x0A заменять на 0x0A. И пусть меня закидают ссаными тряпками, я вообще не вкуриваю как это сделать.
Не, ясен пень, нужно сварганить простейший конечный автомат (вернее, трансдюсер), который будет разбивать поступающие на вход байтстринги на более мелкие байтстринги (ленивые, без копирования). А вот как это сделать в реале?
Перейти на стринги, перейти на текст? Важна даже не столько вычислительная сложность. Важно чтобы реализация как можно меньше сношала сборщик мусора.
Обойти — не вариант. Во-первых, такое поведение — MUST. Во-вторых, без реализации такого поведения к чертям полетит вся кошер^W каноничность.
Macil
Haskell XML Если закодировать XML-дерево в бинарное с помощью техники FCNS, то получившийся результат прекрасно ложится на обычный комбинаторный парсер: комбинатор get (получить следующий токен) разбивается на два: fc (получить следующего «ребенка») и ns (получить следующего «брата»), т.е. пойти влево по дереву или пойти вправо. Понятно дело, что в реальном мире всё несколько сложнее: нужно парсить атрибуты, не давать парсить надмножество XML, парсит не well-formed документы, стримить документы и т.д. Но все базовые свойтва остаются.
Умные люди вообще считают что если закодировать XML бинарным деревом, то задачи валидации/навигации сведутся к SAT, и выдвигают туеву хучу вариантов реализации.
Есть и другая техника кодирования: карринг (или как её называют в TATA, extension encoding). Но почему-то я не нашел ни одной статьи по этому поводу.
Macil
Haskell XML Оказывается у Вадлера есть несколько весьма интересных публикаций по второтегу! А сам он принимал участие в рабочей группе W3C XML Query от компании Avaya. Охренеть!
Macil
Haskell XML validation Камрады, кажется я наконец ущучил как сформулировать задачу валидации XML, а заодно и JSON!
Дано: порождающая грамматика g, дерево t полученное из дерева x, которое производит парсер XML. Нужно проверить что дерево t может быть порождено g.

Тогда задача будет состоять из двух этапов:
1. Описать преобразование x -> t, т.е. XMLTree -> OurDomainTree. Это задача обычного парсера, с самой обычной КС-грамматикой. ЧСХ, на этом этапе будет задетекчены практически все возможные ошибки XML, собранного printf, а именно: отсутствующие аттрибуты, нарушение формата аттрибутов, левые теги, левые аттрибуты.
2. Проверить что дерево t может быть порождено g.

Как я понимаю, для «сферического XML в вакууме», будет достаточно самой обычной КС-грамматики, причем в LR(1) форме (рекурсивно, снизу-вверх и так далее...). Подойдет, наверно, и PEG. А в некоторых случаях и вообще регулярные грамматики. Например, моя задача ничего кроме Нетерминал/нетерминал/.../терминал не предусматривает.

Более того, грамматика g послужит железобетонной базой для определения катаморфизмов для t.

Вопрос, что можно почитать по п. 2? Может быть кто-то что-то похожее уже делал?