Шаги и участие в реализации синтаксического анализатора (в .Net - и в этом случае XPath 2.0)

Question

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

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

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

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

Теперь шаги разборе и то, что я, как правило, охватывают:

1. Lex - Разбор - Сокращения: FsLex/FsYacc. Сначала я не буду полностью покрывать ВСЕ Xpath 2.0, но, по крайней мере, все, что XPath 1.0 может сделать + немного больше.
2. Sematic анализ - Я не уверен, о том, сколько есть в этом
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 который содержит код для разбора и прохода.Я думаю, это было бы хорошим началом или ссылкой :-)

Ваши ответы будут оценены.

Answer 1

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

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

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

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

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

Answer 2

Для решения вашего третьего конкретного вопроса в книге Дракона нет упоминания о библиотеках парсинга парсеров (PEG)/Packrat parser/parser combinator, которые сейчас весьма ярости, особенно когда речь заходит о функциональных языках. См., Например, FParsec.

Answer 3

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

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

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

Существовали несколько областей, которые необходимо сделать для реализации этого:

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

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

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

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

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

Возможно, вы смотрите на работу за месяц, за все лишние кусочки работы, которые не попадают непосредственно в эти категории.

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

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

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

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