Описание языка описания расширяемых парсеров «Nitra»

Nitra – это новое имя для продукта, ранее носившем рабочее название N2.

Nitra – это интегрированный набор средств, цель которого – облегчить создание языков программирования и DSL.

Работы над проектом Nitra ведутся в JetBrains около года. За это время нами создана первая подсистема проекта Nitra – подсистема генерации парсеров. От привычных многим генераторов парсеров наш продукт отличается главным образом следующим:

• Кроме парсера Nitra автоматически генерирует средства поддержки IDE (на сегодня подсветка и свертывание кода).
• Парсеры, созданные с помощью Nitra, являются динамически и статически расширяемыми.
• Язык описания парсеров Nitra, в отличие от BNF, описывает также и AST.

Достоинствами Nitra являются также:

1. Простой и информативный язык описания грамматик.
2. Отсутствие необходимости заниматься подгонкой грамматик под ограничения генератора.
3. Безлексерный парсер – позволяет легко разбирать языки с несколькими лексическими контекстами, такие как XML.
4. Поддержка постфиксных, инфиксных (бинарных), префиксных операторов и приоритетов операторов.
5. Достаточно высокая скорость парсинга (достаточная для использования в IDE).
6. Линейная зависимость времени парсинга от размера разбираемой строки.
7. Модульность. Модули могут находиться как в той же сборке, так и во внешних сборках.
8. Информативные сообщения об ошибках.
9. Возможность получить полную информацию об ошибке, а не только текстовое описание.
10. Автоматическое восстановление после обнаружения ошибки парсинга.
11. Удобный способ анализа AST. Код анализа AST выглядит как методы, объявленные в AST, непосредственно оперирующие именами подправил.
12. Поддержка неоднозначных грамматик (когда две ветви спарсили одинаковый набор токенов).
13. Автоматическое разрешение неоднозначностей.
14. Поддержка синтаксических предикатов.
15. Простой API парсера.
16. Средство тестирования и визуализации парсеров.
17. Полная поддержка Unicode и Unicode-категорий.
18. Интеграция с другими подсистемами Nitra (пока в разработке). Например, подсистемой символов и метаинформации.
19. Простая установка и легкость использования Nitra в своих проектах.

Поддерживаемые платформы

На сегодня Nemerle поддерживает разработку генераторов парсеров для платформы .Net. Однако в дизайн системы заложена относительно легкая возможность создания парсеров для других платформ. В том числе потенциально возможно генерировать код парсеров на чистом C или под виртуальную машину вроде LLVM или Java.

Принципы разработки

Разработка Nitra-парсера начинается с создания синтаксического модуля. Синтаксический модуль является единицей трансляции и инкапсуляции. Конечный парсер состоит из одного или нескольких синтаксических модулей.

В Nitra создание нового языка или расширения к существующему начинается с объявления нового синтаксического модуля (см. SyntaxModule). Модуль объявляется в .nitra-файле (см. ниже). Если вы используете VS, то можно воспользоваться шаблоном синтаксического модуля или шаблоном проекта Nitra (которые можно найти в пакете диалога создания проекта Nemerle).

Для начала объявим пустой синтаксический модуль Calc.

Строчный калькулятор разбирает выражения, состоящие из арифметических операторов («+», «-», «*», «/», «()», «^») и чисел. Nitra позволяет описать разбор операторов одним правилом. Кроме того, потребуется описать стартовое правило (с которого будет начитаться разбор) и правила разбора чисел. Вот как выглядит грамматика строчного калькулятора на Nitra:

Конструкция (аналогичная C#):

открывает синтаксический модуль Whitespaces из стандартной библиотеки Nitra.Core.dll, позволяя обращаться к объявленным в ней сущностям по не квалифицированным именам.

Первое правило - это стартовое правило:

Оно помечено атрибутом StartRule. Это приводит к тому, что для него генерируется специальная функция, позволяющая упростить его парсинг (Nitra создает расширяемые правила, что приводит к тому, что работать с ними нужно через рефлексию).

Атрибут ExplicitSpaces подавляет автоматическую расстановку пробельных правил (по умолчанию Nitra автоматически расставляет пробельные правила в нужных местах). Это требуется потому, что в начале стартового правила необходимо добавить пробельное правило (чтобы можно было начинать выражение с пробелов), а алгоритм автоматической расстановки пробельных правил вставляет их после правил.

Конструкция !Any – это отрицательный предикат (см. раздел RuleExpression.Not) проверяющий, что после успешно разобранного выражения не идет каких бы то ни было символов. Any – это правило, разбирающее любой (один) символ (см. раздел Модуль Whitespaces).

объявляет расширяемое правило Expr (см. раздел ExtensibleRule), описывающее арифметическое выражение. Арифметическое выражение состоит из бинарных операторов «+», «-», «*», «/», «()», «^», унарного оператора «-» и круглых скобок. У операторов есть приоритет и ассоциативность. Например, выражение: 2 + 3 * 4 при вычислении даст значение 14, так как приоритет оператора «*» выше чем у «+».

Разбор числа описывается правилами:

Более подробно о regex-правилах можно узнать из раздела RegexRule. Данные правила вложены в тело расширяющего правила (см. ExtensionRule) Number. Regex-правила удобны для разбора внутренностей токенов. Они быстры и экономны, так как переводятся в ДКА и не порождают AST.

Правило Digit разбирает цифры: 0, 1, 2, 3, 4, 5, 6, 7, 8 и 9. А правило Number разбирает число с необязательным значением после точки, например 123.987 или 42.

Nitra позволяет выражать понятие приоритета и ассоциативности операторов напрямую (а не эмулировать их с помощью набора правил). Nitra также позволяет выражать бинарные операторы через левую рекурсию, что более естественно для восприятия человека.

В Nitra введена специальная поддержка для описания операторов. Все операторы, которые будут использоваться совместно, должны быть описаны как расширения (см. ExtensionRule) одного расширяемого правила (см. ExtensibleRule). Для описания бинарного (или более арного) инфиксного оператора нужно описать правило, в котором оператор (т.е. некий литерал или другое правило описывающее оператор) будет находиться между двумя рекурсивными обращениями к текущему расширяемому правилу. Например, для оператора сложения нужно описать следующее расширяющее правило:

Приоритет оператора, при этом задается при помощи конструкции «precedence n». В данное время приоритет задается целочисленной константой. Чем выше ее значение тем выше приоритет. В дальнейшем мы заменим константы на задаваемые декларативно уровни приоритета. Их так же можно будет расширять динамически.

Если требуется право ассоциативный оператор, то к декларации приоритета нужно добавить конструкцию right-associative:

Ассоциативность определяет, как будут рассматриваться несколько идущих подряд операторов. Например, для левоассоциативного оператора «/» выражение:

будет рассматриваться как:

Если бы он был правоассоциативным, то это же выражение рассматривалось бы как:

Приведенная выше грамматика позволяет разобрать выражение. Полученный парсер можно загрузить в Nitra.Visializer или использовать из своего приложения. Однако он делает мало полезного. Давайте заставим наш парсер вычислять значения разбираемых выражений.

Это можно сделать разными путями. Можно получить AST и проанализировать его в коде C#-программы. Но для подобных задач в Nitra есть встроенное решение – методы объявляемы непосредственно на AST.

Ниже приведен вариант грамматики калькулятора, расширенный AST-методами:

Как видите, методы очень похожи на методы классов, но вместо классов они объявляются непосредственно в правилах. Более подробно о них можно узнать из раздела «RuleMethod, RuleMethodOverride и RuleMethodMissing».

описывает метод Value, не имеющий параметров и возвращающий значение типа double (тип System.Double из .Net). Тело метода состоит из единственного выражения:

В нем Expr – это обращение к полю AST, созданному на основании обращения к правилу Expr в теле правила. Так как у правила Expr тоже объявлен метод Value(), его можно вызвать. Результат его вычисления будет результатом вычисления метода Value у правила Start.

В AST-методах Nitra используется синтаксис Nemerle. Он похож на синтаксис C#, но имеет ряд отличий. Более подробно его можно изучить здесь. В будущем будет возможно описывать AST-методы на C#. Для понимания данных примеров достаточно знать, что в методах не требуется указывать ключевое слово return. Возвращаемым значением метода является результат последнего (или единственного) выражения. Кроме того, метод можно записывать в сокращенной форме (без фигурных скобок):

или в полной форме:

В первом случае после «=» должно идти единственное выражение. Во втором может идти несколько выражений, разделенных «;».

объявленная в теле расширяемого правила Expr, описывает абстрактный метод. Абстрактные и виртуальный методы можно описывать только в расширяемых правилах. Метод без тела (как в нашем примере) считается автоматически абстрактным. Если у метода определено тело, то он становится виртуальным.

Абстрактный метод должен быть в обязательном порядке переопределен в расширяющих правилах:

при переопределении не нужно описывать сигнатуру метода. Так как AST-методы в Nitra не поддерживают перегрузку, Nitra сможет найти описание сигнатуры в расширяемом правиле. Зато требуется написать ключевое слово «override». Это предохраняет от случайного перекрытия метода и устраняет неоднозначность между определением метода и вложенного правила.

В данном примере сначала происходит обращение к методу GetText. На вход ему передается имя поля Number. Это поле было сформировано, так как в теле правила было обращение к regex-правилу Number. Тип этого поля – NSpan. NSpan описывает диапазон текста. В данном случае это диапазон текста, соответствующего разобранному числовому значению. Метод GetText объявлен в одном из базовых классов AST (см. описание класса Located). Он возвращает текст, соответствующий переданному NSpan. Полученный текст передается в .Net-функцию double.Parse, которая преобразует текст в число с плавающей точкой (double). Таким образом, данный метод преобразует разобранное число в double.

Переопределение метода Value, объявленного в правиле, разбирающем оператор «+»:

получает значение обоих своих подвыражений и возвращает их сумму.

Так как в теле данного правила имеется два обращения к правилу Expr, имена полей, формируемые для них, получают целочисленный индекс (имена этих полей можно задать и явно, см. раздел RuleExpression.FieldName).

Аналогичным образом описаны переопределения и для остальных правил. Различия здесь только в выполняемых вычислениях, так что смысла их описывать нет.

Единственное, о чем осталось упомянуть – это о конструкции:

Эта конструкция задает значение, используемое, если в исходном коде (в данном случае в коде выражения) присутствует ошибка, вследствие которой парсер создал AST, в котором отсутствует узел, соответствующий подвыражению. Скажем, если написать выражение «2 + ».

После добавления AST-методов калькулятор можно использовать на практике. Вот так выглядит код его использования из приложения на C#:

Обратите внимание, что AST для выражения строится даже если произошла ошибка. О том, были ли ошибки парсинга, можно узнать обратившись к свойству parseResult.IsSuccess или проверив, что parseResult возвращает пустой список.

Теперь можно скомпилировать, запустить и потестировать калькулятор:

Пример расширения правила из импортируемого синтаксического модуля

Вы может расширять расширяемые правила, объявленные как в своем проекте, так и во внешних сборках. Ниже приведен пример из JsonParser, добавляющий разбор комментариев в стиле C к стандартному пробельному правилу, объявленному в библиотеке Nitra.Core.dll.

Здесь правило IgnoreToken объявлено в модуле Whitespaces, входящем в стандартную библиотеку:

Конструкция «extend token» позволяет расширить (добавить альтернативы) в правило, объявленное в другом модуле. Таким образом, к игнорируемым пробельным символам добавляются комментарии C и C++. Правила, описывающие комментарии, находятся в другом модуле из стандартной библиотеки – CStyleComments.

Описание языка Nitra

Файл .nitra

Nitra имеет свой файловый формат с расширением .nitra.

Содержимое .nitra-файла рассматривается как тело (NamespaceBody) неявного описанного (безымянного) глобального пространства имен. Пространства имен Nitra аналогичны пространствам имен C#.

Тело пространства имен (NamespaceBody)

Тело пространства имен Nitra может содержать ноль или более директив «using» (Using) и идущие за ними ноль или более деклараций верхнего уровня (NamespaceMember).

Директива «using» (Using)

Директивы using практически аналогичны директивам using в C# (см. § 9.4. спецификации C#). Они служат для сокращения имен.

UsingOpen позволяет «открыть» пространство имен, синтаксический модуль или тип. После этого к открытым символам можно будет обращаться с помощью короткого имени. Например:

UsingAlias позволяет задать псевдоним (alias) для типа или синтаксического модуля. Например:

Член пространства имен (NamespaceMember)

Пространства имен могут содержать объявления других пространств имен или синтаксических модулей.

Пространство имен (Namespace)

Пространство имен аналогично пространству имен C# (см. §9.2. спецификации C#).

SyntaxModule

Синтаксический модуль является единицей расширения. Парсер может состоять из одного или нескольких синтаксических модулей. Синтаксические модули могут:

• вводить новые правила и другие допустимые сущности (см. SyntaxModuleMember);
• использовать сущности, объявленные в других синтаксических модулях;
• расширять правила из других синтаксических модулей.

Синтаксические модули, к которым происходит обращение, могут быть расположены как в том же проекте, так и во внешней библиотеке.

SyntaxModuleMember

Маркер определяет фиктивное правило, имя которого может использоваться для задания дополнительной метаинформации в грамматике. Эта метаинформация может использоваться генераторами кода и подсистемами Nitra.

Маркеры из модуля PrettyPrint указывают pretty print-еру, что в месте их применения нужно:

• sm – напечатать пробел.
• i – увеличить отступ.
• d – уменьшить отступ.
• nl – напечатать символ(ы) конца строки и отступ от начала строки.
• inl – аналогично последовательному применению i и nl.

Маркеры из модуля Outline указывают, какие конструкции и как можно сворачивать в редакторе кода:

• outline_begin – начало сворачиваемого региона. Идущие спереди региона пробельные символы не включаются в регион.
• outline_end – конец сворачиваемого региона. Идущие позади региона пробельные символы не включаются в регион.
• outline_begin_before – начало сворачиваемого региона. Идущие спереди региона пробельные символы включаются в регион.
• outline_end_before – конец сворачиваемого региона. Идущие позади региона пробельные символы включаются в регион.
• outline_hiden – идущий следом регион должен быть свернут по умолчанию.

Такие правила не порождают AST. Вместо этого для них вычисляется соответствующий отрезок текста. В материализованном AST им соответствуют значения типа NSpan.

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

ПРЕДУПРЕЖДЕНИЕ

Не применяйте этот вид правил для определения сложных токенов вроде строк и комментариев. Это приведет к плохому автоматическому восстановлению после ошибок. Описывайте строки и комментарии как token-правила, содержимое которых может быть описано regex-правилами.

Тело (TokenRuleBody) может содержать вложенные токен-правила (TokenRule):

Данное правило описывает свойство JSON. Key и Value - это ссылки на другие правила, которые должны быть объявлены в том же синтаксическом модуле или импортированы из других модулей.

В теле (SimpleRuleBody) могут содержаться (подробнее см. SimpleRuleBodyMember):

• объявления других (вложенных) правил;
• псевдонимы для правил;
• методы.

Позволяет задать псевдоним для правила. Псевдоним решает две задачи:

1. Подставляет свое содержимое по месту, тем самым не создавая нового правила.
2. Определяет имя для поля в месте подстановки.

Данный пример задает псевдоним Name для правила Identifier. Теперь, если где-то в грамматике будет обращение к данному псевдониму:

то вместо Name будет подставлено обращение к правилу Identifier, но созданное в материализованном AST поле будет иметь имя «Name».

TokenLiteral позволяет описать имена для токенов, задаваемых непосредственно в грамматике с помощью литералов (в приведенном выше литералами являются: "literal", "=", "," и ";").

Если перед определением правила, в котором используется литералы, задать для этих литералов имена с помощью TokenLiteral, то для этих литералов будет создано поле с заданным именем.

Например, если задать

SpanClass позволяет задать класс подсветки. Это позволяет описать подсветку для своего языка или расширения к другому языку.

Описанный класс подсветки может быть задан правилу посредством атрибута SpanClass.

Если при описании класса подсветки указать регулярное выражение MatchTokens, то этот класс подсветки будет автоматически назначаться всем литералам, которые соответствуют (matched) регулярному выражению.

Например, следующие описание приводит к тому, что все литералы, состоящие из двух или более букв латинского алфавита, будут помечаться классом подсветки Keyword:

Пример применения задания подсветки для строк:

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

Вставляемое правило должно контролировать, что за ключевым словом не идет символов, входящих в состав идентификаторов. В противном случаем парсер будет ошибочно разбирать префиксы идентификаторов, совпадающие с ключевыми словами (например, «do» в doStaff, при условии, что «do» – ключевое слово). Для этого в состав указанного правила должен входить соответствующий предикат.

Например, следующее определение описывает, что после литералов, состоящих из строчных букв латинского алфавита, будет ставиться правило S:

Такое правило определено в модуле Whitespaces следующим образом:

Это правило проверяет, что текущий символ не является символом, допустимым внутри идентификатора, и затем распознает стандартное пробельное правило «s», объявленное в том же модуле.

Если разбор пробельных символов в вашем языке отличается от стандартных правил, вы можете объявить собственные версии правил s и S.

Описывает расширяемое правило.

Расширяемое правило позволяет ввести альтернативы.

Например, следующее правило вводит правило Key, состоящее из трех альтернатив: StringLiteral1, StringLiteral2 и Identifier:

Это правило аналогично следующему BNF-правилу:

ExtensibleRule позволяет описывать тела расширений по месту:

Расширяемое правило может вообще не содержать расширений:

Расширения можно добавить позднее. Например, в другом синтаксическом модуле, объявленном в отдельной сборке.

Расширяемое правило называется расширяемым, так как является точкой расширения грамматики. Любое расширяемое правило можно расширить (см. ExtendSyntax) в другом синтаксическом модуле. Причем синтаксический модуль расширяющий правило из другого модуля, может быть описан как в одной сборке с расширяемым, так и в отдельной сборке.

Расширение правил может производиться динамически. Расширение можно произвести как во время загрузки грамматики, так и непосредственно в процессе парсинга. Это позволяет динамически изменять грамматику языков, созданных на основе Nitra. Это полезно для создания языков с изменяемым синтаксисом (например, Nemerle), или для введения расширений в классические языки и DSL.

Тело ExtensibleRule. Как видно из грамматики, может состоять из точки с запятой (т.е. тело опущено) или блока, содержащего члены ExtensibleRule.

Члены, допустимые в ExtensibleRule (см. соответствующие описания). Как и в теле синтаксического модуля, в теле ExtensibleRule могут присутствовать описания правил (RuleAlias, RegexRule, TokenRule, VoidRule, SimpleRule, ExtensibleRule и ExtensibleTokenRule), а также объявление собственных расширений – ExtensionRule, и методы правил (RuleMethod, RuleMethodOverride и RuleMethodMissing).

RuleMethod – описывает методы, определяемые непосредственно на правиле. Такие методы могут получать информацию о правиле, на котором они определены, и о его подправилах. Методы могут вызывать другие методы, определенные как на том же правиле, так и на других правилах. Кроме того, результат вычисления таких методов может быть кэширован непосредственно в AST (создаваемом для правил).

RuleMethod могут манипулировать именами подправил для получения информации о них и вызова их методов.

Если RuleMethod объявлен на расширяемом правиле ExtensionRule, то порождается аналог виртуального метода (в терминах ООП). Если такой метод не имеет тела, то он автоматически считается абстрактным. Если тело есть – виртуальным.

Виртуальные методы могут (а абстрактные должны) быть переопределены в расширениях расширяемого правила. Это позволяет автору расширяемого правила абстрагировать метод от конкретных расширений, а авторам расширений – создавать конкретные реализацию метода для своих расширений.

При объявлении расширения нужно указать ключевое слово override (см. RuleMethodOverride). При этом сигнатуру переопределяемого метода указывать не нужно, так как для методов не поддерживается перегрузка.

RuleMethod позволяют осуществлять любые вычисления над результатом парсинга (AST). С их помощью можно осуществлять многопроходную трансляцию. Кэширование результатов методов (помеченных атрибутом Cached) позволяет разделить обработку на стадии, так как значения сохраняются непосредственно в AST.

Здесь Value возвращает текст, разбираемый подправилом IdentifierBody правила Identifier, а метод Parts возвращает список частей QualifiedIdentifier. QualifiedIdentifier состоит из одного или нескольких идентификаторов, разделенных точкой. Результат разбора цикла доступен через поле Names. Так как это цикл с разделителем, его результатом является кортеж (Tuple) из двух элементов. В первом элементе кортежа содержится список элементов (их AST), а во втором список разделителей (опять же их AST). Конструкция Names[0] позволяет обратиться к первому элементу кортежа. Далее стандартная функция Map (аналогичная функции Select из Linq) преобразует список, содержащий элементы AST в список строк. Значение для каждого элемента вычисляется посредством обращения к методу Value, описанному в правиле Identifier.

Зачастую разбираемый код может быть некорректным. При восстановлении после обнаружения ошибок парсер может создать суррогатные ветки AST для отсутствующих значений. При обращении к методам суррогатного AST будет выдано исключение. Чтобы предотвратить это, можно объявить специальную форму метода – RuleMethodMissing. У этой формы не может быть параметров. Она может только лишь возвратить некоторое значение по умолчанию. Именно это значение будет использоваться в случае отсутствия значения.

Пример виртуального метода:

И его использование:

Метод FirstChar – это встроенный метод. Он возвращает первый символ, разобранный правилом, переданным в качестве параметра.

Методы HexToChar и EscapeSequence – это обычные методы, описанные в том же проекте (в отдельном Nemerle-модуле):

RuleMethod-ы поддерживают один атрибут «Cached». Если он задан, то после первого выполнения метода его возвращаемое значение кэшируется (мемоизируется) в AST и становится доступно через свойство. Свойство будет иметь имя метода за вычетом стандартных префиксов:

Описывает параметр. В качестве имени может быть использован любой идентификатор. В качестве типа любой тип .Net (в том числе AST или тип символа Nitra).

Код на Nemerle. В дальнейшем, возможно, будет можно писать код на C#.

В коде методов правил можно обращаться к подправилам по их имени, так, будто для каждого подправила создано свойство. Так же можно обращаться к свойствам узла AST, соответствующего правилу, в котором объявлен метод. Доступ к членам узла AST можно осуществлять напрямую или через «this». Более подробную информацию об AST и его членах можно узнать в разделе Объект AST.

ExtendToken

Данная конструкция применяется, если нужно расширить расширяемый токен, определенный в другом синтаксическом модуле. BaseName задает имя правила, подлежащего расширению. Это имя может быть полностью квалифицированным, или простым, или частично квалифицированным, если синтаксический модуль, в котором определено расширяемое правило, открыт с помощью директивы using.

Данный пример расширяет IgnoreToken (игнорируемые правила) правилами комментариев в стиле C и C++.

Если имя расширяемого правила конфликтует с именами из текущего синтаксического модуля, то можно задать локальный псевдоним – Name.

Здесь Whitespaces.IgnoreToken – полностью квалифицированное обращение к правилу IgnoreToken из модуля Whitespaces, а LocalAlias – локальное имя. Это имя используется в качестве имени AST.

ExtendSyntax

Данная конструкция аналогична конструкции ExtendToken за тем исключением, что позволяет расширить расширяемое синтаксическое правило, а не токен.

RuleExpression

RuleExpression описывает тело syntax- или token-правила.

Описывает последовательность подправил. Последовательность может содержать два или более подправил.

В данном примере содержится три подправила:

• A
• B
• (C; ",")+

Утверждающий предикат. Предикат не приводит к разбору текста. Он всего лишь проверяет, может ли быть разобрано указанное в нем правило в данном месте. В случае успеха разбора подправила RuleExpression парсинг правила, в котором встретился предикат, продолжается дальше так, будто предиката не было. В случае неудачи происходит откат всего разбираемого правила.

Данное правило не формирует элементов AST.

В приведенном примере правило Block будет разобрано, только если в текущей позиции разбора находится символ '