Chevrotain, библиотека для создания синтаксических анализаторов с открытым исходным кодом, представляет собой отличный инструмент, который обеспечивает чистое решение для создания многих видов синтаксических анализаторов на JavaScript, не требуя генерации кода во время выполнения. В этой статье я расскажу, как использовать Chevrotain для создания простого предметно-ориентированного языка (DSL), который управляет воображаемой платформой умных лампочек. К концу этой статьи мы создадим синтаксический анализатор и интерпретатор, который сможет запускать программу, подобную приведенной ниже, для настройки нашего смоделированного состояния лампочки:
alias green #00ff00 alias blue #0000ff alias delay 600 brightness 75 on wait delay color green wait delay color blue wait delay off
Если вы просто хотите сразу перейти к исходному коду, вот суть.
Реализация языка в Chevrotain состоит из трех компонентов (хотя два могут быть объединены): лексический анализатор, отвечающий за получение входной строки и преобразование ее в список токенов; синтаксический анализатор, который определяет правила построения допустимых операторов из токенов, сгенерированных лексером, и применяет эти правила для создания синтаксического дерева входной программы; и интерпретатор / посетитель, который просматривает сгенерированное синтаксическое дерево для выполнения программы.
Хотя функциональные возможности посетителя могут быть встроены в анализатор для повышения производительности, в этой статье эти проблемы будут рассмотрены отдельно и будут использоваться встроенные в Chevrotain функциональные возможности CST Visitor. Для целей этой статьи мы будем собирать DSL в один файл. Для удобства обслуживания более крупные проекты Chevrotain, вероятно, следует разделить на несколько файлов.
Начиная
Chevrotain доступен как модуль npm и может быть установлен с npm install chevrotain в каталоге вашего проекта. Предположим, что наш исходный файл находится в каталоге с установленным Chevrotain. Во-первых, нам нужно импортировать chevrotain, а также два модуля из этого пакета:
Лексер
Далее нам нужно настроить наш лексер. Помните, что задача лексера состоит в том, чтобы взять ввод и разделить его на токены, которые могут быть использованы анализатором. Для этого нам нужно создать определения токенов для каждой строки, разрешенной в языке. Мы начнем с создания массива для хранения наших типов токенов (которые в конечном итоге будут переданы конструктору лексического анализатора) и вспомогательной функции для создания новых токенов из параметров и их вставки в наш массив токенов.
Теперь мы можем определить все символы, разрешенные в нашем языке. Для целей нашего DSL пробелы не имеют значения. Поскольку токены обрабатываются лексером по порядку, добавление токена для идентификации и пропуска пробелов в первую очередь сделает наш лексер более эффективным.
Вы можете видеть, что определение токена - это объект с именем, шаблоном регулярного выражения и (необязательно) группой. Следуя соглашениям в примерах Шевротена, ключевые слова обозначаются в UpperCamelCase, а буквальные значения - в UPPERCASE. Lexer.SKIPPED - это специальная группа, которая заставляет токен пропускаться и не обрабатываться. Мы не будем группировать какие-либо другие токены в этом примере.
Затем мы можем определить все ключевые слова на нашем языке:
Чтобы мы могли распознавать буквальные значения в программе, мы добавляем определения токенов для чисел и шестнадцатеричных цветов, а также токен идентификатора для использования с ключевым словом alias:
Наконец, мы можем создать экземпляр нашего нового лексера из базового класса, предоставленного Chevrotain, используя наш список токенов.
Парсер
Следующий компонент, который нам нужно создать, - это парсер. Chevrotain предоставляет почти все, что нам нужно для этого, в классе Parser, поэтому все, что нам нужно сделать, чтобы получить работающий синтаксический анализатор, - это предоставить набор правил, определяющих синтаксис допустимых операторов на нашем языке. Все, что нам нужно сделать в парсере, происходит в конструкторе, поэтому мы начнем с расширения класса Parser и добавления некоторого шаблона в его конструктор.
Поскольку правила синтаксического анализатора определяются с использованием метода класса usingthis в конструкторе, присвоение this $ - это соглашение, рекомендованное в документации Chevrotain, чтобы не вводить this снова и снова - это чисто личное предпочтение, и я рекомендую его. Вызов $.performSelfAnalysis() (this.performSelfAnalysis()) применяет правила, которые мы определим и требуется для работы парсера.
Давайте рассмотрим грамматику нашего языка и определим первое правило для нашего синтаксического анализатора. Какая единица высшего уровня должна пониматься как ввод? Одним из ответов будет программа, сумма всех частей ввода. Из чего сделана программа? Можно сказать, что программа состоит из серии операторов. В нашем определении парсера Chevrotain это можно выразить так (весь пример кода, показывающий правила парсера, следует понимать как находящийся в constructor нашего нового класса LightParser и должен быть определен до вызова $.performSelfAnalysis()):
Здесь мы определяем правило под названием program, которое содержит множество (ноль или более) statement субправил. Что такое заявление? Наш язык можно понять как серию команд, поэтому предположим, что оператором может быть любая из них:
Обратите внимание, что $.OR принимает массив объектов, а не имя и функцию типа $.RULE. Свойство ALT объекта, переданного в $.OR, является обычным блоком правил синтаксического анализатора и может содержать любое количество вызовов методов класса синтаксического анализатора, хотя в этом случае мы просто вызываем несколько эксклюзивных подправил.
Теперь нам нужно определить правила для каждого из подправил, которые мы объявили для нашего правила statement. Первые два, on и off, очень просты:
Здесь мы впервые представляем метод $.CONSUME. $.CONSUME указывает, что это правило ожидает встретить конкретный токен. Наши предыдущие два правила (program и statement) были нетерминальными правилами, поскольку каждое из них вызывает субправила. onStatement и offStatement (и остальные операторы в нашей грамматике) являются терминальными правилами, поскольку они потребляют токены без вызова каких-либо дополнительных подправил (и в результирующем синтаксическом дереве дочерние узлы не создаются). Остальные правила аналогичны onStatement и offStatement, но каждое из них потребляет несколько токенов подряд и, для некоторых потребляемых токенов, может позволить этому токену быть нескольких типов:
Наконец, как только мы добавили все наши правила и закончили расширение класса Chevrotain Parser, мы создадим экземпляр нашего парсера, дадим ему несколько токенов из ввода, используя наш лексер (помните, что пробелы не имеют значения в нашем языке, поэтому мы можем поместить его в одну строку), создать синтаксическое дерево, вызвав точку входа в синтаксический анализатор, которым в данном случае является program, и выполнить некоторую базовую обработку ошибок:
Посетитель / переводчик
Теперь, когда у нас есть синтаксическое дерево, представляющее структуру нашей программы, мы хотим иметь возможность что-то с ним делать. Chevrotain предоставляет BaseCstVisitor класс, который мы можем расширить для создания нового класса посетителей, специфичного для нашего синтаксического анализатора. Chevrotain также предоставляет класс BaseCstVisitorWithDefaults, но, поскольку мы в любом случае хотим реализовать каждое правило, начнем с чистого листа. Мы начинаем с получения базового класса от нашего парсера и его расширения; мы также настроим состояние для нашей смоделированной лампочки в ее конструкторе.
Как и в случае с парсером, мы должны вызвать класс super в верхней части нашего конструктора, а также нужно вызвать this.validateVisitor(). У нашей лампочки есть несколько состояний, и мы также добавляем к экземпляру свойство scope для хранения любых свойств, созданных с помощью нашего ключевого слова alias. У нашего класса интерпретатора будет метод экземпляра для каждого правила, которое мы определили в нашем синтаксическом анализаторе. Каждый метод принимает текущий context узла синтаксического дерева, в котором они находятся, и может возвращать значение (хотя в нашей реализации нет методов интерпретатора, возвращающих значения). Как и в случае с парсером, мы можем начать с program и statement:
Грамматика нашего синтаксического анализатора утверждает, что программа содержит множество операторов, поэтому наш program посетитель перебирает свои дочерние операторы (из context.statement) и посещает каждый из них (вызывает соответствующий метод посетителя на каждом дочернем узле). Обратите внимание, что любой дочерний узел context всегда является массивом, если он присутствует (и null в противном случае); даже если грамматика определяет program как содержащий единственный statement, context.statement из program все равно будет массивом с одним элементом. Поскольку наша грамматика говорит, что оператор - это одно из любого количества возможных выражений, мы можем увидеть, не является ли какое-либо из них нулевым, и посетить это. Когда this.visit вызывается для массива узлов, он посещает первый из них.
Следующие утверждения, которые мы определим для нашего посетителя, onStatement и offStatement, просты. Когда эти утверждения достигнуты, мы хотим соответствующим образом изменить состояние лампочки. Для всех операторов, которые изменяют состояние лампочки, мы также выходим из системы некоторые сообщения, чтобы увидеть, что произошло:
Следующие операторы также влияют на состояние лампочки, но, как определено в нашей грамматике, принимают аргументы, которые могут быть либо буквальным значением, либо идентификатором, используемым с alias. Поскольку мы знаем, что каждый оператор будет иметь только один или другой, мы можем проверить наличие идентификатора и использовать значение, хранящееся в this.scope в этом ключе, если он существует, или использовать переданное буквальное значение. Обратите внимание, что каждый дочерний узел имеет свойство image, которое содержит буквальную строку, преобразованную в токен.
Последний оператор, который нам нужно определить, - это aliasStatement, который ведет себя очень похоже на другие, но устанавливает свойство на this.scope вместо его получения:
Наконец, мы можем создать новый экземпляр нашего интерпретатора и заставить его посетить синтаксическое дерево, которое мы создали в предыдущем разделе:
Были сделаны! Если мы запустим завершенный файл с помощью узла, мы должны увидеть выполнение нашей программы:
$ node demo.js setting green to #00ff00 setting blue to #0000ff setting delay to 600 brightness was 100 setting brightness to 75 turning light on (light was off) waiting 600 setting color to #00ff00 (color was #ffffff) waiting 600 setting color to #0000ff (color was #00ff00) waiting 600 turning light off (light was on)
Заключение
Надеюсь, это продемонстрировало, что Chevrotain - чрезвычайно мощный инструмент для создания языков, с которым также на удивление легко начать работать. Если эта статья вдохновила вас на что-то интересное с Chevrotain, сообщите мне об этом на jeremy at knack dot com или на https://twitter.com/Overlapping!
