Этапы и участие в реализации парсера (in.Net - а в данном случае XPath 2.0)

В отсутствие каких-либо хороших бесплатных реализаций XPath 2.0 для .Net build на Linq to XML я подумал о реализации своей собственной (также для опыта). Но просто чтобы быть ясным (и не строить что-то, что существует) это реализации XPath 2.0, которые я нашел:

  • Saxon .Net
  • машина запросов - у меня были проблемы с этим-исключения с примерами
  • XQSharp - может и хороший, но коммерческий (один разработчик ~300 $)

Теперь я хочу немного подумать о том, как трудно реализовать некоторые выражения языка, такие как XPath 2.0. Я нашел эту ссылку, которая имеет выражение EBNF для XPath 2.0: http://www.w3.org/TR/2007/REC-xpath20-20070123/#id-grammar и я думаю сделать его в F# с комбинацией fslex/fsyacc.

Мой фон (субъективный): я играл с этими инструментами раньше, но только для некоторых простых выражений и очень простого программирования язык. Кроме того, я прочитал большую часть книги Dragon и аппелирует современную реализацию компилятора в ML - но, к сожалению, я не применил теорию на практике во время чтения. Я изучал компьютерные науки в течение года, где я закончил курсы с теорией о бывшем finite automaton, CFL и алгоритмы, но я был разработчиком в течение многих лет до университета (несколько лет с профессиональной работой-back-end веб-сайтов в основном).

Теперь о шагах разбора и о том, к чему я стремлюсь. обложка:

  1. Lex-Parsing-Reductions: FsLex/FsYacc. Сначала я не буду должным образом охватывать все Xpath 2.0, но, по крайней мере, все, что может сделать XPath 1.0 + немного больше.
  2. семантический анализ - я не уверен в том, как много в этом есть
  3. оптимизация-я не склонен покрывать это (по крайней мере, не на первых порах)
  4. фактический обход и т. д.
  5. ...?

Теперь, конкретные вопросы в дополнение к вышесказанному:

  1. насколько это сложно чтобы сделать парсер такого размера? исходя из моего прошлого, смогу ли я это сделать?
  2. есть ли какие-либо важные шаги, которые я пропустил в отношении XPath 2.0 в частности?
  3. есть ли какая-либо технология, которую я пропустил; должен ли я охватить больше, чем просто XPath 2.0 и XDocument и т. д. чтобы можно было сделать парсер?

Для ясности: я хочу сделать парсер выражений XPath 2.0 и пройти XDocument и т. д. с этим разобранным выражением лица. Что я думаю в сочетании является запросом двигатель.

Обновление: я нашел это: http://www.w3.org/2007/01/applets/xpathApplet.html который содержит код для разбора и обхода. Я думаю, что это было бы хорошим началом или ссылкой : -)

Ваши ответы будут оценены по достоинству.
3 6
parsing .net xpath f#

3 ответа:

Я реализовал парсер XPath 2.0 полностью в XSLT 2.0 три года назад.

Я использовал свой LR Parsing Framework в FXSL и это было не так уж трудно. Грамматика довольно большая - 209 правил, если я хорошо помню. Я использовал модификацию YACC (сделанную мной), которую я называю Yaccx для создания таблиц синтаксического анализа в формате XML. Это входные данные для общий парсер LR, написано на языке XSLT.

Ибо на такой проект нужно выделить не менее 6 месяцев полного рабочего дня, может быть, 1 год . Сложность заключается в реализации огромной библиотеки функций (F & O).

Кроме того, XPath не является автономным языком - он должен быть размещен на другом языке . По этой причине я не использовал этот парсер для чего-либо значимого, так как у меня не было доступа, влияния и возможности изменить существующий язык хостинга.

Итак, будьте готовы ко всему этому. трудности.

4

Я являюсь одним из разработчиков XQSharp, поэтому у меня есть опыт в этой области. XQSharp фактически начал свою жизнь как реализация XPath, прежде чем мы расширили его для поддержки XQuery.

Наша первоначальная реализация заняла у нас около 6 месяцев, хотя это было не единственное, над чем мы работали в то время.

После этого времени у нас была реализация, которая была завершена. Было много областей, в которых это не было полностью согласовано, где стандартные методы .NET не выполнялись. ведите себя точно так же, как требует спецификация. Некоторые примеры этого связаны с преобразованием значений в строки и из них, регулярными выражениями, большим количеством юникодных вещей, проблемами с .NET-представлениями XML (например, обработкой xml:base) и так далее.

Для этого необходимо было сделать несколько шагов:

Разбор : Сам парсер был простым и в основном генерировался из EBNF в спецификации. Я бы оценил, что это первоначально представляло несколько недель работы.

Модель Данных : Как представлены данные. Для того чтобы иметь полную реализацию XPath, необходимо реализовать множество новых типов данных (например, xs:gDay). В нашем случае все наши элементы являются производными от базового типа, и все наши выражения возвращают перечислители этих типов. Вы также должны быть в состоянии определить, соответствует ли тип элемента определенному типу XPath. Мы поддерживали статическую типизацию и осознание схемы с самого начала, без этот раздел, вероятно, становится тривиальным, но вы все еще смотрите на несколько недель работы.

Выражения / Абстрактное Синтаксическое Дерево Это модель самого выражения. Мы использовали документ формальной семантики XQuery для создания отображения из различных конструкций XPath (например, осей и предикатов) в более простой основной Граммер (который заканчивается огромным количеством let, для выражений if и typeswitch!). В нашей первоначальной реализации все это выражения имели методы оценки и поэтому были конечным представлением выражения. В нашем случае все выражения также имели методы проверки типов, но это можно пропустить изначально (основная цель этих методов-оптимизация). Создание всех этих выражений снова заняло несколько недель.

Функции Как указал предыдущий комментатор, библиотека функций для XPath довольно велика. На реализацию всей библиотеки XPath ушло несколько месяцев.

Статика Анализ Требуется небольшой объем статического анализа. Ссылки на переменные и вызовы функций должны быть привязаны к правильным переменным и функциям. Большинство реализаций XPath основаны на стеке, поэтому для назначения указателей (или индексов) всем переменным требуется этап выделения стека. Этот статический анализ занял неделю или две. Книга Дракона должна очень хорошо настроить вас, чтобы решить большинство этих проблем.

Вы, вероятно, смотрите на еще один месяц работы для всех дополнительные части работы, которые не попадают непосредственно в эти категории.

После всей этой работы у нас осталась в основном функциональная реализация XPath; но она была слишком медленной для реального использования в реальном мире (возможно, в 100 раз медленнее, чем XPath 1 в .NET). так что после этого наступает забавная работа - оптимизация.

Доведение двигателя до 100% соответствия и добавление оптимизаций, вероятно, заняло еще 12-18 человеко-месяцев (хотя мы, вероятно, немного переборщили с оптимизацией!), но тем самым точка мы уже сделали переход к реализации XQuery.

Мой совет был бы начать с решения подмножества XPath (возможно, только передние оси и очень ограниченная библиотека функций), и вы могли бы собрать реализацию за месяц или два, но серьезная реализация XPath2 будет большой инвестицией во времени.

Убедитесь, что вы используете XPathNavigator для представления узла, так как он имеет методы, такие как SelectChildren, которые могут использовать преимущества индексов в базовых представлениях (например, XPathDocument).

4

Чтобы ответить на ваш третий конкретный вопрос, в книге Dragon нет упоминания о синтаксическом анализе Грамматик выражений (PEGs) / Packrat parsers / parser combinator libraries, которые сейчас в моде, особенно когда речь заходит о функциональных языках. См., например, FParsec .

3