Оригинальная статья написана Габриэле Томассетти (большое ему спасибо)
Это статья, аналогичная предыдущей, которую мы написали: Парсинг в Java, поэтому введение такое же. Перейдите к главе 3, если вы ее уже читали.
Если вам нужно разобрать язык или документ из JavaScript, есть три основных способа решить проблему:
- использовать существующую библиотеку, поддерживающую этот конкретный язык: например, библиотеку для синтаксического анализа XML.
- создание собственного парсера вручную
- инструмент или библиотека для создания парсера: например ANTLR, который вы можете использовать для создания парсеров для любого языка
Использовать существующую библиотеку
Первый вариант лучше всего подходит для хорошо известных и поддерживаемых языков, таких как XML или HTML. Хорошая библиотека обычно включает также API для программного создания и изменения документов на этом языке. Обычно это больше того, что вы получаете от базового парсера. Проблема в том, что такие библиотеки не так распространены и поддерживают только самые распространенные языки. В других случаях вам не повезло.
Создание собственного пользовательского парсера вручную
Возможно, вам придется выбрать второй вариант, если у вас есть особые потребности. И в том смысле, что язык, который вам нужно проанализировать, не может быть проанализирован с помощью традиционных генераторов синтаксического анализатора, или у вас есть определенные требования, которые вы не можете удовлетворить с помощью обычного генератора синтаксического анализатора. Например, потому что вам нужна максимально возможная производительность или глубокая интеграция между различными компонентами.
Инструмент или библиотека для создания синтаксического анализатора
Во всех остальных случаях по умолчанию должен использоваться третий вариант, поскольку он наиболее гибкий и требует меньшего времени разработки. Поэтому в этой статье мы сконцентрируемся на инструментах и библиотеках, соответствующих этому варианту.
Примечание. Текст в цитате, описывающий программу, взят из соответствующей документации
Инструменты для создания парсеров
Мы увидим:
- Инструменты, которые могут генерировать парсеры, которые можно использовать из JavaScript (и, возможно, из других языков)
- Библиотеки JavaScript для создания парсеров
Инструменты, которые можно использовать для генерации кода для парсера, называются генераторами парсеров или компилятором-компилятором. Библиотеки, создающие синтаксические анализаторы, известны как комбинаторы синтаксических анализаторов.
Генераторы парсеров (или комбинаторы парсеров) нетривиальны: вам нужно время, чтобы научиться их использовать, и не все типы генераторов парсеров подходят для всех типов языков. Поэтому мы подготовили список самых известных из них с кратким введением к каждому из них. Мы также концентрируемся на одном целевом языке: JavaScript. Это также означает, что (обычно) сам парсер будет написан на JavaScript.
Перечислить все возможные инструменты и библиотеки синтаксического анализатора для всех языков было бы отчасти интересно, но не так полезно. Это потому, что вариантов будет слишком много, и мы все потеряемся в них. Сосредоточившись на одном языке программирования, мы можем провести сравнение яблок с яблоками и помочь вам выбрать один вариант для вашего проекта.
Что нужно знать о парсерах
Чтобы этот список был доступен всем программистам, мы подготовили краткое объяснение терминов и понятий, с которыми вы можете столкнуться при поиске парсера. Мы не пытаемся дать вам формальные объяснения, а даем практические объяснения.
Структура парсера
Парсер обычно состоит из двух частей: лексера, также известного как сканер или токенизатора, и собственно синтаксического анализатора. Не все парсеры используют эту двухэтапную схему: некоторые парсеры не зависят от лексера. Они называются анализаторами без сканирования.
Лексер и синтаксический анализатор работают последовательно: лексер сканирует ввод и выдает соответствующие токены, синтаксический анализатор просматривает токены и выдает результат синтаксического анализа.
Давайте посмотрим на следующий пример и представим, что мы пытаемся разобрать математическую операцию.
437 + 734
Лексический анализатор просматривает текст и находит «4», «3», «7», а затем пробел «». Задача лексера - распознать, что первые символы составляют один токен типа NUM. Затем лексер находит символ '+', который соответствует второму токену типа PLUS , и, наконец, он находит другой токен типа NUM.
Анализатор обычно объединяет токены, созданные лексером, и группирует их.
Определения, используемые лексерами или синтаксическим анализатором, называются правилами или продукцией. Правило лексера будет указывать, что последовательность цифр соответствует токену типа NUM, в то время как правило синтаксического анализатора будет указывать, что последовательность токенов типа NUM, PLUS, NUM соответствует выражению.
Бесссканированные синтаксические анализаторы отличаются тем, что они обрабатывают исходный текст напрямую, а не обрабатывают список токенов, созданный лексером.
Сейчас обычным явлением являются наборы, которые могут генерировать как лексер, так и синтаксический анализатор. В прошлом вместо этого было более распространено комбинировать два разных инструмента: один для создания лексера, а другой для создания синтаксического анализатора. Так было, например, в случае почтенной пары lex & yacc: lex создал лексер, а yacc - синтаксический анализатор.
Дерево синтаксического анализа и абстрактное дерево синтаксиса
Есть два термина, которые связаны между собой и иногда используются как взаимозаменяемые: дерево синтаксического анализа и абстрактное дерево синтаксиса (AST).
Концептуально они очень похожи:
- они оба являются деревьями: есть корень, представляющий весь анализируемый фрагмент кода. Затем есть меньшие поддеревья, представляющие части кода, которые становятся меньше, пока в дереве не появятся отдельные токены.
- разница заключается в уровне абстракции: дерево синтаксического анализа содержит все токены, которые появились в программе, и, возможно, набор промежуточных правил. Вместо этого AST представляет собой отполированную версию дерева синтаксического анализа, в которой удаляется информация, которая могла быть получена или не важна для понимания фрагмента кода.
В AST некоторая информация теряется, например, комментарии и символы группировки (круглые скобки) не отображаются. Такие вещи, как комментарии, для программы излишни, а символы группировки неявно определяются структурой дерева.
Дерево синтаксического анализа - это представление кода, более близкое к конкретному синтаксису. Он показывает множество деталей реализации парсера. Например, обычно правило соответствует типу узла. Дерево синтаксического анализа обычно преобразуется пользователем в AST, возможно, с некоторой помощью генератора синтаксического анализа.
Графическое представление AST выглядит так.
Иногда вы можете захотеть создать дерево синтаксического анализа, а затем получить из него AST. Это может иметь смысл, потому что дерево синтаксического анализа легче создать для анализатора (это прямое представление процесса синтаксического анализа), но AST проще и легче обрабатывать с помощью следующих шагов. Под следующими шагами мы подразумеваем все операции, которые вы можете захотеть выполнить с деревом: проверка кода, интерпретация, компиляция и т. Д.
Грамматика
Грамматика - это формальное описание языка, которое можно использовать для распознавания его структуры.
Проще говоря, это список правил, определяющих, как может быть составлена каждая конструкция. Например, правило для оператора if может указывать, что оно должно начинаться с ключевого слова «if», за которым следуют левая скобка, выражение, правая скобка и оператор.
Правило может ссылаться на другие правила или типы токенов. В примере с оператором if ключевое слово «if», левая и правая круглые скобки были типами лексемы, а выражение и оператор были ссылками на другие правила.
Наиболее часто используемый формат для описания грамматик - это форма Бэкуса-Наура (BNF), которая также имеет множество вариантов, включая расширенную форму Бэкуса-Наура. Преимущество расширенного варианта состоит в том, что он включает простой способ обозначения повторов. Типичное правило грамматики Бэкуса-Наура выглядит так:
<symbol> ::= __expression__
<symbol> обычно нетерминальный, что означает, что он может быть заменен группой элементов справа, __expression__. Элемент __expression__ может содержать другие нетерминальные символы или терминальные. Терминальные символы - это просто те символы, которые нигде в грамматике не появляются как <symbol>. Типичным примером терминального символа является строка символов, например «класс».
Леворекурсивные правила
В контексте парсеров важной особенностью является поддержка леворекурсивных правил. Это означает, что правило может начинаться со ссылки на себя. Эта ссылка может быть также косвенной.
Рассмотрим, например, арифметические операции. Дополнение можно описать как два выражения (я), разделенных знаком плюса (+), но выражение также может содержать другие дополнения.
addition ::= expression '+' expression multiplication ::= expression '*' expression // an expression could be an addition or a multiplication or a number expression ::= addition | multiplication |// a number
Это описание также соответствует нескольким сложениям, таким как 5 + 4 + 3. Это потому, что его можно интерпретировать как выражение (5) («+») выражение (4 + 3). И тогда саму 4 + 3 можно разделить на две составляющие.
Проблема в том, что такие правила нельзя использовать с некоторыми генераторами парсеров. Альтернативой является длинная цепочка выражений, которая также учитывает приоритет операторов.
Некоторые генераторы парсеров поддерживают прямые леворекурсивные правила, но не косвенные.
Типы языков и грамматики
В основном нас интересуют два типа языков, которые можно анализировать с помощью генератора синтаксического анализа: обычные языки и контекстно-свободные языки. Мы могли бы дать вам формальное определение в соответствии с иерархией языков Хомского, но это было бы бесполезно. Давайте вместо этого рассмотрим некоторые практические аспекты.
Регулярный язык может быть определен серией регулярных выражений, в то время как контекстно-свободный язык требует чего-то большего. Простое практическое правило состоит в том, что если грамматика языка имеет рекурсивные элементы, это не обычный язык. Например, как мы уже говорили в другом месте, HTML не является обычным языком. Фактически, большинство языков программирования являются контекстно-свободными.
Обычно какому-то языку соответствует такая же грамматика. То есть существуют обычные грамматики и контекстно-свободные грамматики, которые соответствуют, соответственно, обычным и контекстно-свободным языкам. Но что еще больше усложняет ситуацию, существует относительно новый (созданный в 2004 году) вид грамматики, называемый Parsing Expression Grammar (PEG). Эти грамматики столь же мощны, как и контекстно-свободные, но, по словам их авторов, они описывают языки программирования более естественно.
Различия между PEG и CFG
Основное различие между PEG и CFG состоит в том, что порядок выбора имеет значение в PEG, но не в CFG. Если существует много возможных допустимых способов синтаксического анализа ввода, CFG будет неоднозначным и, следовательно, неправильным. Вместо этого с PEG будет выбран первый применимый вариант, и это автоматически решит некоторые двусмысленности.
Еще одно отличие состоит в том, что PEG использует синтаксические анализаторы без сканирования: им не нужен отдельный лексер или фаза лексического анализа.
Традиционно и PEG, и некоторые CFG не могли работать с леворекурсивными правилами, но некоторые инструменты нашли обходные пути для этого. Либо путем изменения основного алгоритма синтаксического анализа, либо путем автоматического переписывания леворекурсивного правила нерекурсивным способом. У любого из этих способов есть свои недостатки: либо он делает сгенерированный парсер менее понятным, либо ухудшает его производительность. Однако с практической точки зрения преимущества более простой и быстрой разработки перевешивают недостатки.
Если вы хотите узнать больше о теории синтаксического анализа, вам следует прочитать Руководство по синтаксическому анализу: алгоритмы и терминология.
Генераторы парсеров
Базовый рабочий процесс инструмента-генератора синтаксического анализатора довольно прост: вы пишете грамматику, которая определяет язык или документ, и вы запускаете инструмент для создания синтаксического анализатора, который можно использовать из вашего кода JavaScript.
Синтаксический анализатор может выдать AST, который вам, возможно, придется пройти самостоятельно или вы можете пройти с дополнительными готовыми к использованию классами, такими как Listeners или Visitors. Некоторые инструменты вместо этого предлагают возможность встраивать код в грамматику, который будет выполняться каждый раз, когда соблюдается определенное правило.
Обычно вам нужна библиотека времени выполнения и / или программа для использования сгенерированного синтаксического анализатора.
Обычный (Lexer)
Инструменты, анализирующие обычные языки, обычно называются лексерами.
Лексер
Lexer - это лексер, который утверждает, что смоделирован после flex. Хотя более справедливым описанием был бы короткий лексический анализатор, основанный на RegExp. Документация кажется минимальной, всего несколько примеров, но все это составляет 147 строк кода, так что на самом деле она всеобъемлющая.
Тем не менее, в нескольких строках удается поддерживать несколько интересных вещей, и он кажется довольно популярным и простым в использовании. Во-первых, он поддерживает RingoJS, платформу JavaScript поверх JVM. Другой - интеграция с Jison, клоном Bison в JavaScript. Если вы умерите свои ожидания, это может быть полезным инструментом.
Здесь нет грамматики, вы просто используете функцию для определения шаблона RegExp и действия, которое должно выполняться при совпадении с шаблоном. Итак, это нечто среднее между генератором лексера и комбинатором лексера. Вы не можете комбинировать различные функции лексера, как в комбинаторе лексера, но этот лексер создается только динамически во время выполнения, поэтому он также не является правильным генератором лексера.
var lexer = new Lexer;
var chars = lines = 0;
lexer.addRule(/n/, function () {
lines++;
chars++;
});
lexer.addRule(/./, function () {
chars++;
});
lexer.setInput("Hello World!n Hello Stars!n!")
lexer.lex();
Контекст Бесплатно
Давайте посмотрим на инструменты, которые генерируют контекстно-свободные парсеры.
ANTLR
ANTLR - отличный генератор парсеров, написанный на Java, который также может генерировать парсеры для JavaScript и многих других языков. Также существует бета-версия для TypeScript от того же разработчика, который делает оптимизированную версию C #. ANTLR основан на новом алгоритме LL, разработанном автором и описанном в этой статье: Адаптивный анализ LL (*): возможности динамического анализа (PDF).
Он довольно популярен благодаря множеству полезных функций: например, версия 4 поддерживает прямые леворекурсивные правила. Однако реальная добавленная стоимость обширного сообщества - это большое количество доступных грамматик.
Он предоставляет два способа обхода AST вместо встраивания действий в грамматику: посетителей и слушателей. Первый подходит, когда вам нужно манипулировать элементами дерева или взаимодействовать с ними, а второй полезен, когда вам просто нужно что-то сделать, когда правило соблюдается.
Типичная грамматика разделена на две части: правила лексера и правила синтаксического анализатора. Деление является неявным, поскольку все правила, начинающиеся с заглавной буквы, являются правилами лексера, а правила, начинающиеся со строчной буквы, являются правилами парсера. В качестве альтернативы, грамматики лексера и парсера могут быть определены в отдельных файлах.
грамматика простая;
базовый :
grammar simple; basic : NAME ':' NAME ; NAME : [a-zA-Z]* ; COMMENT : '/*' .*? '*/' -> skip ;
Если вам интересно узнать, как использовать ANTLR, вы можете заглянуть в этот гигантский учебник по ANTLR, который мы написали. Если вы готовы стать профессиональным разработчиком ANTLR, вы можете купить наш видеокурс Создание профессиональных синтаксических анализаторов и языков с использованием ANTLR. Курс преподается с использованием Python, но исходный код также доступен на JavaScript.
ПНГ
APG - это синтаксический анализатор с рекурсивным спуском, использующий вариант Augmented BNF, который они называют Superset Augmented BNF. ABNF - это особый вариант BNF, разработанный для лучшей поддержки протокола двунаправленной связи. APG также поддерживает дополнительные операторы, такие как синтаксические предикаты и пользовательские функции сопоставления.
Он может генерировать парсеры на C / C ++, Java и JavaScript. Поддержка последнего языка кажется более совершенной и актуальной: в нем есть еще несколько функций, и он был обновлен совсем недавно. Фактически, в документации говорится, что он разработан, чтобы иметь внешний вид JavaScript RegExp.
Поскольку он основан на ABNF, он особенно хорошо подходит для синтаксического анализа языков многих технических спецификаций Интернета и, по сути, является предпочтительным синтаксическим анализатором для ряда крупных телекоммуникационных компаний.
Грамматика APG очень понятна и понятна.
// example from a tutorial of the author of the tool available here // https://www.sitepoint.com/alternative-to-regular-expressions/ phone-number = ["("] area-code sep office-code sep subscriber area-code = 3digit ; 3 digits office-code = 3digit ; 3 digits subscriber = 4digit ; 4 digits sep = *3(%d32-47 / %d58-126 / %d9) ; 0-3 ASCII non-digits digit = %d48-57 ; 0-9
Джисон
Jison генерирует восходящие парсеры в JavaScript. Его API похож на API Bison, отсюда и название.
Несмотря на название, Jison также может заменять flex, поэтому вам не нужен отдельный лексер. Хотя вы можете использовать его или создать свой собственный лексер. Все, что вам нужно, это объект с функциями setInput и lex. Он лучше всего распознает языки, описанные грамматиками LALR (1), хотя также имеет режимы для LR (0), SLR (1).
Сгенерированный синтаксический анализатор не требует компонента среды выполнения, вы можете использовать его как отдельное программное обеспечение.
У него достаточно хорошая документация с несколькими примерами и даже раздел, где можно опробовать свои грамматики в Интернете. Хотя иногда он полагается на руководство Bison, чтобы покрыть отсутствие собственной документации.
Грамматика Jison может быть введена в пользовательском формате JSON или в формате Bison. Оба требуют, чтобы вы использовали встроенные действия, если вы хотите что-то сделать при совпадении с правилом. Следующий пример представлен в настраиваемом формате JSON.
// example from the documentation
{
"comment": "JSON Math Parser",
// JavaScript comments also work
"lex": {
"rules": [
["s+", "/* skip whitespace */"],
["[0-9]+(?:.[0-9]+)?b", "return 'NUMBER'"],
["*", "return '*'"],
["/", "return '/'"],
["-", "return '-'"],
["+", "return '+'"],
[..] // skipping some parts
]
},
"operators": [
["left", "+", "-"],
["left", "*", "/"],
["left", "UMINUS"]
[..] // skipping some parts
],
"bnf": {
"expressions": [["e EOF", "return $1"]],
"e" :[
["e + e", "$$ = $1+$3"],
["e - e", "$$ = $1-$3"],
["- e", "$$ = -$2", {"prec": "UMINUS"}],
["NUMBER", "$$ = Number(yytext)"],
[..] // skipping some parts
]
}
}
Он очень популярен и используется многими проектами, включая CoffeeScript и Handlebars.js.
Неарли
nearley использует алгоритм синтаксического анализа Эрли, дополненный оптимизацией Joop Leo, для легкого анализа сложных структур данных. Nearley сверхбыстрый и очень мощный. Он может анализировать буквально все, что вы в него бросаете.
Алгоритм Эрли разработан для простой обработки всех грамматик, включая леворекурсивные и неоднозначные. По сути, его главное преимущество в том, что он никогда не должен выходить из строя катастрофически. С другой стороны, он может быть медленнее, чем другие алгоритмы синтаксического анализа. Почти сам также способен обнаруживать некоторые двусмысленные грамматики. Он также может выводить несколько результатов в случае неоднозначного ввода.
Грамматика Неарли записывается в .ne файле, который может включать собственный код. Правило может включать встроенное действие, которое в документации называется функцией постобработки. Вы также можете использовать собственный лексер.
# from the examples in Nearly
# csv.ne
@{%
var appendItem = function (a, b) { return function (d) { return d[a].concat([d[b]]); } };
var appendItemChar = function (a, b) { return function (d) { return d[a].concat(d[b]); } };
var empty = function (d) { return []; };
var emptyStr = function (d) { return ""; };
%}
file -> header newline rows {% function (d) { return { header: d[0], rows: d[2] }; } %}
# id is a special preprocessor function that return the first token in the match
header -> row {% id %}
rows -> row
| rows newline row {% appendItem(0,2) %}
row -> field
| row "," field {% appendItem(0,2) %}
field -> unquoted_field {% id %}
| """ quoted_field """ {% function (d) { return d[1]; } %}
quoted_field -> null {% emptyStr %}
| quoted_field quoted_field_char {% appendItemChar(0,1) %}
quoted_field_char -> [^"] {% id %}
| """ """ {% function (d) { return """; } %}
unquoted_field -> null {% emptyStr %}
| unquoted_field char {% appendItemChar(0,1) %}
char -> [^nr",] {% id %}
newline -> "r" "n" {% empty %}ca
| "r" | "n" {% empty %}
Еще одна интересная особенность заключается в том, что вы можете создавать собственные токены. Вы можете определить их с помощью библиотеки токенизации, литерала или тестовой функции. Функция тестирования должна возвращать истину, если текст соответствует этому конкретному токену.
@{%
var print_tok = {literal: "print"};
var number_tok = {test: function(x) {return x.constructor === Number; }}
%}
main -> %print_tok %number_tok
Nearley включает инструменты для отладки и понимания вашего парсера. Например, Unparser может автоматически генерировать случайные строки, которые ваш анализатор считает правильными. Это полезно для проверки вашего парсера на случайный шум или даже для генерации данных из схемы (например, случайного адреса электронной почты). Он также включает инструмент для создания SVG железнодорожных диаграмм: графического представления грамматики.
Парсеру Nearley требуется среда выполнения Nearley.
Документация Nearley - это хороший обзор того, что доступно, а также есть сторонняя игровая площадка, где можно попробовать грамматику в Интернете. Но вы не найдете полного объяснения всех функций.
ПЭГ
После парсеров CFG пора увидеть парсеры PEG, доступные для JavaScript.
Навес
Canopy - компилятор парсера, ориентированный на Java, JavaScript, Python и Ruby. Он берет файл, описывающий грамматику выражения синтаксического анализа, и компилирует его в модуль синтаксического анализатора на целевом языке. Сгенерированные синтаксические анализаторы не зависят от самого Canopy во время выполнения.
Он также обеспечивает легкий доступ к узлам дерева синтаксического анализа.
Грамматика Canopy имеет удобную функцию использования аннотации действий для использования пользовательского кода в анализаторе. Практически. вы просто пишете имя функции рядом с правилом, а затем реализуете функцию в своем исходном коде.
// the actions are prepended by %
grammar Maps
map <- "{" string ":" value "}" %make_map
string <- "'" [^']* "'" %make_string
value <- list / number
list <- "[" value ("," value)* "]" %make_list
number <- [0-9]+ %make_number
Файл JavaScript, содержащий код действия.
var maps = require('./maps');
var actions = {
make_map: function(input, start, end, elements) {
var map = {};
map[elements[1]] = elements[3];
return map;
},
[..]
};
Ом
Ohm - генератор парсеров, состоящий из библиотеки и предметно-ориентированного языка
Грамматики Ом определены в настраиваемом формате, который может быть помещен в отдельный файл или в строку. Однако парсер создается динамически, а не с помощью отдельного инструмента. В этом смысле он больше похож на библиотеку парсеров, чем на традиционный генератор парсеров.
Вспомогательная функция для создания AST включена в число дополнительных функций.
В Ohm грамматика определяет язык, а семантические действия указывают, что делать с допустимыми входными данными на этом языке
Грамматика полностью отделена от смысловых действий. Это упрощает переносимость и читаемость, а также позволяет поддерживать разные языки с одинаковой грамматикой. На данный момент Ohm поддерживает только JavaScript, но в будущем планируется добавить больше языков. Таким образом, типичная грамматика становится понятной и удобочитаемой.
Arithmetic {
Exp
= AddExp
AddExp
= AddExp "+" PriExp -- plus
| AddExp "-" PriExp -- minus
| PriExp
PriExp
= "(" Exp ")" -- paren
| number
number
= digit+
}
Семантические действия можно реализовать с помощью простого API. На практике это работает как шаблон посетителя с той разницей, что легче определить больше групп семантических действий.
var semantics = g.createSemantics().addOperation('eval', {
Exp: function(e) {
return e.eval();
},
AddExp: function(e) {
return e.eval();
},
AddExp_plus: function(left, op, right) {
return left.eval() + right.eval();
},
AddExp_minus: function(left, op, right) {
return left.eval() - right.eval();
},
PriExp: function(e) {
return e.eval();
},
PriExp_paren: function(open, exp, close) {
return exp.eval();
},
number: function(chars) {
return parseInt(this.sourceString, 10);
},
});
var match = g.match('1 + (2 - 3) + 4');
console.log(semantics(match).eval());
Для поддержки отладки Ом имеет текстовую трассировку и (в процессе работы) графический визуализатор. Вы можете увидеть работу графического визуализатора и проверить грамматику в интерактивном редакторе.
Документация не так уж и плоха, хотя вам нужно зайти в каталог doc, чтобы найти ее. Учебника нет, но есть несколько примеров и справочная информация. В частности, в документации предлагается прочитать хорошо прокомментированный Математический пример.
PEG.js
PEG.js - это простой генератор парсеров для JavaScript, который производит быстрые парсеры с отличным отчетом об ошибках.
PEG.js может работать как традиционный генератор синтаксического анализатора и создавать синтаксический анализатор с помощью инструмента или может генерировать его с использованием грамматики, определенной в коде. Он поддерживает различные загрузчики модулей (например, AMD, CommonJS и т. Д.).
В PEG.js есть удобный онлайн-редактор, который позволяет написать грамматику, протестировать сгенерированный синтаксический анализатор и загрузить его.
Грамматика PEG.js обычно записывается в .pegjs файле и может включать встроенные действия, настраиваемый код инициализации и семантические предикаты. То есть функции, которые определяют, активировано конкретное совпадение или нет.
// example from the documentation
{
function makeInteger(o) {
return parseInt(o.join(""), 10);
}
}
start
= additive
additive
= left:multiplicative "+" right:additive { return left + right; }
/ multiplicative
multiplicative
= left:primary "*" right:multiplicative { return left * right; }
/ primary
primary
= integer
/ "(" additive:additive ")" { return additive; }
integer "integer"
= digits:[0-9]+ { return makeInteger(digits); }
Документация достаточно хороша, есть несколько примеров грамматик, но нет учебных пособий. Популярность проекта привела к разработке сторонних инструментов, таких как инструмент для создания железнодорожных диаграмм, и плагинов, например, для генерации парсеров TypeScrypt.
Восковой глаз
Waxeye - генератор парсеров, основанный на синтаксическом анализе грамматик выражений (PEG). Он поддерживает C, Java, Javascript, Python, Ruby и Scheme.
Waxeye может облегчить создание AST путем определения узлов в грамматике, которые не будут включены в сгенерированное дерево. Это очень полезно, но недостатком Waxeye является то, что он генерирует только AST. В том смысле, что нет возможности автоматически выполнить действие при сопоставлении узла. Вы должны пройти и выполнить то, что вам нужно, вручную.
Одним из положительных побочных эффектов этого ограничения является то, что грамматики легко читаются и чисты. Они также не зависят от какого-либо языка.
// from the manual
calc <- ws sum
sum <- prod *([+-] ws prod)
prod <- unary *([*/] ws unary)
unary <= '-' ws unary
| :'(' ws sum :')' ws
| num
num <- +[0-9] ?('.' +[0-9]) ws
ws <: *[ tnr]
Особенностью Waxeye является то, что он дает некоторую помощь в объединении различных грамматик, а затем способствует модульности. Например, вы можете создать общую грамматику для идентификаторов, которые обычно похожи на многих языках.
Waxeye имеет отличную документацию в виде руководства, в котором объясняются основные концепции и способы использования инструмента для всех поддерживаемых языков. Есть несколько примеров грамматик.
Waxeye вроде сохраняется, но активно не развивается.
Комбинаторы синтаксического анализатора
Они позволяют вам создавать синтаксический анализатор просто с помощью кода JavaScript, комбинируя различные функции сопоставления с образцом, которые эквивалентны правилам грамматики. Обычно они считаются наиболее подходящими для более простого анализа. Учитывая, что это просто библиотеки JavaScript, вы можете легко внедрить их в свой проект: вам не нужен какой-либо конкретный шаг генерации, и вы можете написать весь свой код в своем любимом редакторе. Их главное преимущество - возможность интеграции в ваш традиционный рабочий процесс и IDE.
На практике это означает, что они очень полезны для всех обнаруживаемых вами мелких проблем синтаксического анализа. Если типичный разработчик сталкивается с проблемой, которая слишком сложна для простого регулярного выражения, эти библиотеки обычно являются решением. Короче говоря, если вам нужно создать синтаксический анализатор, но вы на самом деле этого не хотите, комбинатор синтаксического анализатора может быть вашим лучшим вариантом.
Бенну, Парджс и Парсиммон
Bennu - это библиотека комбинаторов парсеров Javascript, основанная на Parsec. Библиотека Bennu состоит из основного набора синтаксических комбинаторов, реализующих интерфейсы Fantasy Land. Также поддерживаются более продвинутые функции, такие как подробный обмен сообщениями об ошибках, настраиваемое состояние синтаксического анализатора, мемоизация и инкрементный запуск немодифицированных синтаксических анализаторов.
Все библиотеки вдохновлены Parsec. Бенну и Парсиммон - самые старые, а Бенну - более продвинутый. У них также есть обширная документация, но у них нет учебника. Бенну вроде сохраняется, но активно не развивается.
Пример из документации.
var parse = require('bennu').parse;
var text = require('bennu').text;
var aOrB = parse.either(
text.character('a'),
text.character('b'));
parse.run(aOrB, 'b'); // 'b'
Parsimmon - небольшая библиотека для написания больших парсеров, состоящих из множества маленьких парсеров. API основан на parsec и Promises / A +.
Parsimmon - самый популярный из трех, он стабилен и обновляется.
Ниже приводится часть примера JSON.
let whitespace = P.regexp(/s*/m);
let JSONParser = P.createLanguage({
// This is the main entry point of the parser: a full JSON value.
value: r =>
P.alt(
r.object,
r.string,
[..]
).thru(parser => whitespace.then(parser)),
[..]
// Regexp based parsers should generally be named for better error reporting.
string: () =>
token(P.regexp(/"((?:.|.)*?)"/, 1))
.map(interpretEscapes)
.desc('string'),
[..]
object: r =>
r.lbrace
.then(r.pair.sepBy(r.comma))
.skip(r.rbrace)
.map(pairs => {
let object = {};
pairs.forEach(pair => {
let [key, value] = pair;
object[key] = value;
});
return object;
}),
});
///////////////////////////////////////////////////////////////////////
let text = // JSON Object
let ast = JSONParser.value.tryParse(text);
Parjs - это JavaScript-библиотека комбинаторов синтаксического анализатора, аналогичная по принципу и дизайну подобным Parsec и, в частности, его адаптации F # FParsec.
Она также похожа на библиотеку parsimmon, но намерена превзойти ее.
Parjs всего несколько месяцев, но он уже достаточно развит. Он также имеет то преимущество, что он написан на TypeScript.
У всех библиотек есть хорошая документация, но Parjs великолепен: он объясняет, как использовать парсер, а также как создавать с его помощью хорошие парсеры. Есть несколько примеров, в том числе следующие по форматированию строк.
/**
* Created by lifeg on 04/04/2017.
*/
import "../setup";
import {Parjs, LoudParser} from "../src";
//+ DEFINING THE PARSER
//Parse an identifier, an asciiLetter followed by an asciiLetter or digit, e.g. a12b but not 1ab.
let ident = Parjs.letter.then(Parjs.letter.or(Parjs.digit).many()).str;
//Parse a format token, an `ident` between `{` and `}`. Return the result as a Token object.
let formatToken = ident.between(Parjs.string("{"), Parjs.string("}")).map(x => ({token: x}));
//Parse an escaped character. This parses "`{a}" as the text "{a}" instead of a token.
//Also escapes the escaped char, parsing "``" as "`".
//Works for arbitrary characters like `a being parsed as a.
let escape = Parjs.string("`").then(Parjs.anyChar).str.map(x => ({text: x.substr(1)}));
//Parse text which is not an escape character or {.
let text = Parjs.noCharOf("`{").many(1).str.map(x => ({text: x}));
//The parser itself. Parses either a formatToken, e.g. {abc} or an escaped combo `x, or text that doesn't contain `{.
//Parses many times.
let formatParser = formatToken.or(escape, text).many();
//This prints a sequence of tokens {text: "hello, my name is "}, {token: name}, {text: " and I am "}, {token: " years old}, ...
console.log(formatParser.parse("hello, my name is {name} and I am {age} years old. This is `{escaped}. This is double escaped: ``{name}."));
Библиотеки JavaScript, относящиеся к синтаксическому анализу
Есть также несколько других интересных библиотек, связанных с синтаксическим анализом, которые не входят в общую категорию.
Библиотеки JavaScript, разбирающие JavaScript
Есть один особый случай, которым можно управлять более конкретным образом: случай, когда вы хотите проанализировать код JavaScript в JavaScript. В отличие от того, что мы обнаружили для Java и C #, здесь нет однозначного выбора: есть много хороших вариантов для синтаксического анализа JavaScript.
Три самых популярных библиотеки: Acorn, Esprima и UglifyJS. Мы не собираемся говорить, какой из них лучше, потому что все они кажутся потрясающими, обновленными и хорошо поддерживаемыми.
Одним из важных отличий является то, что UglifyJS также является набором инструментов для управления / сжатия / украшения, а это значит, что он также имеет много других применений. С другой стороны, он единственный, который поддерживает только до версии ECMAScript 5. Еще одна вещь, которую следует учитывать, это то, что только esprima имеет документацию, достойную проектов такого масштаба.
Интересные библиотеки синтаксического анализа: Chevrotain
Chevrotain - это очень быстрый и многофункциональный JavaScript LL (k) Разбор DSL. Его можно использовать для создания парсеров / компиляторов / интерпретаторов для различных случаев использования, начиная от простых файлов конфигурации и заканчивая полноценными языками программирования.
Есть еще один интересный инструмент синтаксического анализа, который не подходит для более распространенных категорий инструментов, таких как генераторы синтаксического анализатора или комбинаторы: Chevrotain, синтаксический анализатор DSL. Синтаксический DSL работает как нечто среднее между комбинатором синтаксического анализатора и генератором синтаксического анализатора. Вы определяете грамматику в коде JavaScript напрямую, но с использованием API (Chevrotain), а не стандартного синтаксиса, такого как EBNF или PEG.
Chevrotain поддерживает многие расширенные функции, типичные для генераторов синтаксического анализатора: такие как семантические предикаты, отдельные лексический анализатор и синтаксический анализатор, а также определение грамматики (необязательно), отделенное от действий. Действия могут быть реализованы с использованием посетителя, и, таким образом, вы можете повторно использовать одну и ту же грамматику для нескольких проектов.
Ниже приводится частичный пример грамматики JSON из документации. Как видите, синтаксис более понятен разработчикам, не имеющим опыта в синтаксическом анализе, но немного более подробен, чем стандартная грамматика.
const { CstParser, Lexer, createToken } = require("chevrotain")
// ----------------- lexer -----------------
const True = createToken({ name: "True", pattern: /true/ })
const False = createToken({ name: "False", pattern: /false/ })
const Null = createToken({ name: "Null", pattern: /null/ })
const LCurly = createToken({ name: "LCurly", pattern: /{/ })
const RCurly = createToken({ name: "RCurly", pattern: /}/ })
const LSquare = createToken({ name: "LSquare", pattern: /\[/ })
const RSquare = createToken({ name: "RSquare", pattern: /]/ })
const Comma = createToken({ name: "Comma", pattern: /,/ })
const Colon = createToken({ name: "Colon", pattern: /:/ })
const StringLiteral = createToken({
name: "StringLiteral",
pattern: /"(?:[^\\"]|\\(?:[bfnrtv"\\/]|u[0-9a-fA-F]{4}))*"/
})
const NumberLiteral = createToken({
name: "NumberLiteral",
pattern: /-?(0|[1-9]\d*)(\.\d+)?([eE][+-]?\d+)?/
})
const WhiteSpace = createToken({
name: "WhiteSpace",
pattern: /[ \t\n\r]+/,
group: Lexer.SKIPPED
})
const allTokens = [
WhiteSpace,
NumberLiteral,
StringLiteral,
LCurly,
RCurly,
LSquare,
RSquare,
Comma,
Colon,
True,
False,
Null
]
const JsonLexer = new Lexer(allTokens)
// ----------------- parser -----------------
class JsonParser extends CstParser {
// Unfortunately no support for class fields with initializer in ES2015, only in esNext...
// so the parsing rules are defined inside the constructor, as each parsing rule must be initialized by
// invoking RULE(...)
// see: https://github.com/jeffmo/es-class-fields-and-static-properties
constructor() {
super(allTokens)
// not mandatory, using $ (or any other sign) to reduce verbosity (this. this. this. this. .......)
const $ = this
// the parsing methods
$.RULE("json", () => {
$.OR([
{ ALT: () => $.SUBRULE($.object) },
{ ALT: () => $.SUBRULE($.array) }
])
})
$.RULE("object", () => {
$.CONSUME(LCurly)
$.OPTION(() => {
$.SUBRULE($.objectItem)
$.MANY(() => {
$.CONSUME(Comma)
$.SUBRULE2($.objectItem)
})
})
$.CONSUME(RCurly)
})
$.RULE("objectItem", () => {
$.CONSUME(StringLiteral)
$.CONSUME(Colon)
$.SUBRULE($.value)
})
$.RULE("array", () => {
$.CONSUME(LSquare)
$.OPTION(() => {
$.SUBRULE($.value)
$.MANY(() => {
$.CONSUME(Comma)
$.SUBRULE2($.value)
})
})
$.CONSUME(RSquare)
})
$.RULE("value", () => {
$.OR([
{ ALT: () => $.CONSUME(StringLiteral) },
{ ALT: () => $.CONSUME(NumberLiteral) },
{ ALT: () => $.SUBRULE($.object) },
{ ALT: () => $.SUBRULE($.array) },
{ ALT: () => $.CONSUME(True) },
{ ALT: () => $.CONSUME(False) },
{ ALT: () => $.CONSUME(Null) }
])
})
// very important to call this after all the rules have been defined.
// otherwise the parser may not work correctly as it will lack information
// derived during the self analysis phase.
this.performSelfAnalysis()
}
}
// ----------------- wrapping it all together -----------------
// reuse the same parser instance.
const parser = new JsonParser()
module.exports = {
jsonTokens: allTokens,
JsonParser: JsonParser,
parse: function parse(text) {
const lexResult = JsonLexer.tokenize(text)
// setting a new input will RESET the parser instance's state.
parser.input = lexResult.tokens
// any top level rule may be used as an entry point
const cst = parser.json()
return {
cst: cst,
lexErrors: lexResult.errors,
parseErrors: parser.errors
}
}
}
Это очень быстро, быстрее, чем любая другая библиотека JavaScript, и может конкурировать с пользовательским парсером, написанным вручную, в зависимости от движка JavaScript, на котором он работает. Вы можете увидеть цифры и получить более подробную информацию о тесте разбора библиотек, разработанном автором библиотеки.
Он также поддерживает функции, полезные для отладки, такие как создание железнодорожных диаграмм и настраиваемые отчеты об ошибках. Есть также несколько функций, которые полезны для создания компилятора, интерпретаторов или инструментов для редакторов, таких как автоматическое исправление ошибок или синтаксическая поддержка содержимого. Последний означает, что он может предлагать следующий токен при определенных входных данных, поэтому его можно использовать в качестве строительного блока для функции автозаполнения.
Это еще не все, Chevrotain даже предоставляет собственный двигатель для внешнего использования. Это означает, что вы можете создать свою собственную библиотеку синтаксического анализа поверх Chevrotain. Например, вы можете создать свой собственный формат для грамматики, а затем использовать движок Chevrotain для синтаксического анализа. Он даже дает вам бесплатные функции проверки ошибок, такие как обнаружение неоднозначных альтернатив, левая рекурсия и т. Д.
У Chevrotain есть отличная и хорошо организованная документация с учебником, примерами грамматики и справочником. Также есть аккуратный онлайн-редактор / игровая площадка.
Chevrotain написан на TypeScript.
Резюме
Как мы уже говорили в родственной статье о синтаксическом анализе в Java и C #, мир парсеров немного отличается от обычного мира программистов. В случае с JavaScript этот язык также живет в мире, отличном от любого другого языка программирования. Между его разработчиками настолько разный уровень компетенции, что вы можете найти лучших из них, работающих с людьми, которые просто не знают, как собрать сценарий. И оба хотят разобрать вещи.
Итак, для JavaScript есть инструменты, которых немного по всему этому спектру. У нас есть серьезные инструменты, разработанные учеными для своих курсов или в ходе их обучения, вместе с гораздо более простыми инструментами. Некоторые из них стирают границы между генераторами парсеров и комбинаторами парсеров. И у всех есть свое место. Еще одна сложность заключается в том, что, хотя обычно комбинаторы синтаксического анализатора зарезервированы для более простого использования, в JavaScript это не всегда так. Вы можете найти очень мощные и сложные комбинаторы синтаксического анализатора и гораздо более простые генераторы синтаксического анализатора.
Итак, с помощью JavaScript, более чем когда-либо, мы не можем однозначно рекомендовать одно программное обеспечение другому. То, что лучше для пользователя, может оказаться не лучшим для кого-то другого. И все мы знаем, что наиболее технически правильное решение может не быть идеальным в реальной жизни со всеми ее ограничениями. Поэтому мы хотели поделиться тем, что узнали о лучших вариантах синтаксического анализа в JavaScript.
Мы хотели бы поблагодарить Shahar Soel за то, что он сообщил нам о Chevrotain и предложил некоторые необходимые исправления.
Больше контента на plainenglish.io
