Создание парсера для последовательности

Теперь, когда мы определили, как должен выглядеть язык последовательностей, нам нужно формализовать это в грамматике, а затем создать синтаксический анализатор для синтаксического анализа наших входных данных в абстрактное синтаксическое дерево.

Раньше в Определение языка последовательностей мы разрабатывали версию языка Sequence, которая нам понравилась, теперь нам нужно формализовать этот язык и построить для него синтаксический анализатор.

Язык в том виде, в каком мы его оставили, выглядит так:

Name "Sequence demo"
Actor User
Object Alpha
Object Bravo
Sequence Test
    User ask Alpha "A synchronous message"
    Alpha tell Bravo "An asynchronous message"
    Bravo replies Alpha "A response message"
    Alpha replies User """
        This is a multi-line
        message text!
        """

Для новых читателей Sequence - это крошечный предметно-ориентированный язык, используемый для описания диаграмм последовательностей. Я использую его как основу для серии сообщений в блогах, в которых рассказывается, как создать такой инструмент вместе с расширением Visual Studio Code. См. Исходный пост здесь.

Сканирование, лексирование, токенизация и синтаксический анализ

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

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

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

# Small piece of Sequence code
Sequence Test
    User ask Alpha "Hi"
# The fragment above is really just a sequence of characters: characters = ['S', 'e', 'q', 'u', 'e', 'n', 'c', 'e', ' ', 'T', 'e', 's', 't', '\n', ' ', ' ', ' ', ' ', 'U', 's', 'e', 'r', ' ', 'a', 's', 'k', ' ', 'A', 'l', 'p', 'h', 'a', ' ', '"', 'H', 'i', '"']
# Which gets converted into tokens
tokens = [
    { "type": "sequence", "lexeme": "Sequence" },
    { "type": "identifier", "lexeme": "Test" },
    { "type": "identifier", "lexeme": "User" },
    { "type": "ask", "lexeme": "ask" },
    { "type": "identifier", "lexeme": "Alpha" },
    { "type": "string", "lexeme": "Hi!" }
]
# We convert that into a tree structure of nodes (called AST)
tree = {
    "type": "root",
    "children": [
        {
            "type": "sequence",
            "value": "Test",
            "children": [
                {
                    "type": "interaction"
                    "value": "",
                    "children": [
                        {
                            "type": "source",
                            "value": "User",
                            "children": []
                        },
                        {
                            "type": "ask",
                            "value": "",
                            "children": []
                        },
                        {
                            "type": "source",
                            "value": "User",
                            "children": []
                        }, 
                        {
                            "type": "destination",
                            "value": "Alpha",
                            "children": []
                        },
                        {
                            "type": "message",
                            "value": "Hi!",
                            "children": []
                        }
                    ]
                } 
            ]
        }
    ]
}

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

Рукописный. Неудивительно, что вы пишете все части самостоятельно. Это может быть довольно сложно в зависимости от того, как построен ваш язык (левая рекурсия и т. Д.), Но также дает вам неограниченные возможности для обработки ошибок. Я рекомендую серию статей Руслана Спивака Давайте построим простой интерпретатор, если вы хотите узнать, как создать его самостоятельно.

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

Генератор синтаксического анализатора. Генератор синтаксического анализатора - это отдельная программа (фактически компилятор), которая генерирует синтаксический анализатор с учетом формального определения грамматики. Часто вы описываете свою грамматику в формате, напоминающем форму Бэкуса-Наура, и запускаете инструмент, который генерирует исходный код для парсера, который вы можете использовать в своей программе.

Я не буду объяснять лексическую теорию в этом посте, поскольку в Интернете доступно множество хороших статей, которые делают это лучше, чем я когда-либо мог. Вместо этого эта статья даст вам обзор и ссылку на небольшую реализацию с кодом, доступным на GitHub.

Генерация парсера

Для Sequence я остановился на генераторе парсеров, так как не хотел писать парсер вручную. Я выбрал ANTLR4, это один из самых известных генераторов парсеров. Он имеет активное сообщество, хорошую документацию (включая несколько книг) и генерирует довольно производительные парсеры.

ANTLR - это программа на Java, но она не ограничивается использованием Java вами, она может выводить генераторы на нескольких разных языках программирования, одним из которых является JavaScript. Поскольку расширения Visual Studio Code реализованы в TypeScript или JavaScript, это идеально подходит.

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

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

Определение грамматики в ANTLR также является DSL, а для языка Sequence урезанная версия определения грамматики выглядит так:

grammar Sequence;
// Defines two custom tokens to deal with the
// whitespace significance, which is omitted
// from this example
tokens { INDENT, DEDENT }
// The root rule is where it all starts. This rule states what
// constructs that is allowed on the root level. The EOF
// indicates that the full input should be read and matched by
// the parser, else an error will be thrown.
root
    : NEWLINE* documentMeta definitions EOF
    ;
documentMeta 
    : documentName
    ;
documentName
    : DOCUMENT_NAME string NEWLINE?
    ;
definitions
    : (NEWLINE | actorDefinition | objectDefinition | sequenceDefinition)*
    ;
actorDefinition
    : ACTOR IDENTIFIER IS string NEWLINE? | ACTOR IDENTIFIER NEWLINE? ; objectDefinition
    : OBJECT IDENTIFIER IS string NEWLINE? | OBJECT IDENTIFIER NEWLINE?
    ;
sequenceDefinition
    : SEQUENCE IDENTIFIER sequenceBlock
    ;
sequenceBlock
    : NEWLINE INDENT sequenceMessage* DEDENT
    ;
sequenceMessage
    : IDENTIFIER (ASK|TELL|REPLIES) IDENTIFIER string NEWLINE? | IDENTIFIER (ASK|TELL|REPLIES) IDENTIFIER NEWLINE?
    ;
// String exposed as a grammar rule to make it testable directly
// without piggy-back on another rule. 
string
    : STRING
    ;
// Definition of string tokens
DOCUMENT_NAME : 'Name';
ACTOR         : 'Actor';
OBJECT        : 'Object';
IS            : 'is';
SEQUENCE      : 'Sequence';
ASK           : 'ask';
TELL          : 'tell';
REPLIES       : 'replies';
// Captures any word that is not a keyword. Keep this after
// the keywords are defined
IDENTIFIER
    : LETTER+ LETTERORDIGIT*
    ;
COMMENT
    : '#' .+? (NEWLINE | EOF) -> skip ;
STRING
    : (SINGLE_LINE_STRING | MULTI_LINE_STRING)
    ;
SKIPPING
    : SPACES -> skip ;
// A fragment itself will (cannot) be interpreted as a token
// it is only meant to be reused from other lexer rules.
fragment SPACES
    : [ \t]+
    ;
fragment LETTER
    : [a-zA-Z]
    ;
fragment LETTERORDIGIT
    : [a-zA-Z0-9]
    ;
fragment DIGIT
    : [0-9]
    ;
fragment SINGLE_LINE_STRING
    : '"' (. | ~[\r\n"])*? '"' | '\'' (. | ~[\r\n'])*? '\''
    ;
fragment MULTI_LINE_STRING
    : '"""' (.)*? '"""' | '\'\'\'' (.)*? '\'\'\''
    ;

Лексические правила указаны в UPPER-CASE, а грамматика должна начинаться с lower-case символа. Помимо этого, я думаю, что ANTLR-грамматика в этом примере довольно проста для понимания. (ANTLR имеет довольно много функций, я использую только самые простые).

Полная грамматика доступна на parser/Sequence.g4

Обратная связь

Я не рекомендую сразу определять всю грамматику, я утверждаю, что вам следует использовать TDD для своего языка, как и для любой другой реализации. Цикл, который я использовал для разработки этого языка, был:

1. Реализуйте тест для новой языковой конструкции
2. Обновите файл грамматики ANTLR новой конструкцией
3. Сгенерируйте новый парсер (т.е. используйте компилятор ANTLR для генерации исходного кода)
4. Проведите свои тесты

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

Использование синтаксического анализатора, сгенерированного ANTLR

Сгенерируйте анализатор последовательности, выполнив следующие команды:

# The following command use the alias defined when installing ANTLR $ antlr4 -Dlanguage=JavaScript ./parser/Sequence.g4
# Which is the equvivalent of this command
$ java -Xmx500M -cp "/usr/local/lib/antlr-4.7-complete.jar:$CLASSPATH" org.antlr.v4.Tool -Dlanguage=JavaScript ./parser/Sequence.g4

ANTLR выведет исходный код для парсера рядом с тем местом, где находится файл .g4. В случае с Sequence вы можете найти их в каталоге ./parser/.

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

Дерево синтаксического анализатора очень похоже на абстрактное дерево синтаксиса, но ближе к реальным токенам. Например. круглые скобки могут быть включены в дерево синтаксического анализатора для обозначения начала списка, но не включены в AST (который может содержать только List и ListItems).

import * as antlr4 from 'antlr4';
import { SequenceLexer } from '../parser/SequenceLexer';
import { SequenceParser } from '../parser/SequenceParser';
const chars = new antlr4.InputStream(source);
const lexer = new SequenceLexer(chars);
const tokens = new antlr4.CommonTokenStream(lexer);
const parser = new SequenceParser(tokens);
parser.buildParseTrees = true;
// Initiate the parsing, and begin with the root rule. const parserResult = parser.root();

Для Sequence есть два места, где используется сгенерированный синтаксический анализатор, один раз для точки входа в src/index.js нашего компилятора (транспилятор, генератор или как вы его могли бы назвать). И еще одно место находится в тестовых утилитах по адресу __tests__/test-utils.js, чтобы мы могли тестировать отдельные грамматические правила.

Одна приятная особенность сгенерированного синтаксического анализатора заключается в том, что доступны все правила грамматики. Обратите внимание на звонок parser.root() выше? Это проанализирует ввод в соответствии с грамматикой, определенной root в .g4 файле. Это позволяет очень легко писать тесты только для части вашей грамматики.

Например. если бы мы должны были написать тест, чтобы убедиться, что определение актера может быть успешно проанализировано, мы могли бы сделать так, чтобы тест анализировал только ввод, используя грамматику, определенную в parser.definitions() (или если бы мы хотели быть еще более конкретными parser.actorDefinition().

Модульный тест

Иногда я пишу модульные тесты только для грамматики - это дает преимущество наличия ранних тестов, которые не содержат ошибок или двусмысленности в определении грамматики (файлы .g4), но требуют некоторого дублирования тестов.

В других случаях я тестирую как грамматический синтаксический анализ, так и построение AST в одном тесте. Единственное преимущество состоит в том, что вам нужно писать меньше тестов.

Для начала я рекомендую использовать отдельные модульные тесты для разбора грамматики без использования собственного кода.

Вот пример небольшого сообщения из __tests__/grammar/definitions-grammar.spec.js, в котором утверждается, что определение субъекта может быть проанализировано (нацеленное на одно правило грамматики, как описано ранее):

const parse = (src) => createParser(src, false).definitions(); 
describe('parse single Actor definition', () => {
    let result;
    beforeEach(() => {
        result = parse( 'Actor Jane\n' + '');
    });
    it('should parse without errors', () => {
        expect(result.parser._syntaxErrors).toEqual(0);
    });
    it('should have "Jane" as the symbol name', () => {
        expect(result.children[0].children[1].symbol.text)
            .toEqual('Jane');
    });
});

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

Ошибки и предупреждения

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

const chars = new antlr4.InputStream(source);
const lexer = new SequenceLexer(chars);
const tokens = new antlr4.CommonTokenStream(lexer);
const parser = new SequenceParser(tokens);
parser.buildParseTrees = true;
// Remove the standard error listener since we do not want to
// print to stdout, but to capture the errors ourself to present
// a nice and tidy error message for the end-user. parser.removeErrorListeners();
lexer.removeErrorListeners();
// Register our listener used to build the AST while the parsing
// is being done.
const errorListener = new AntlrErrorListener(); // <--
parser.addErrorListener(errorListener);
// Initiate the parsing, and begin with the root rule.
const parserResult = parser.root();

Построение вашего абстрактного синтаксического дерева

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

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

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

Для Sequence необходимо всего несколько типов узлов, ниже их определение в JavaScript.

/**
 * The root node represents the sequence document, containing the
 * meta-data information, actors and the defined sequence flows.
 */
export class RootNode extends Node { ... }
/**
 * The declaration of the document name.
 *
 * Name "My sequence flow"
 */
export class NameNode extends Node { ... }
/** 
 * Represents an identifier of something (e.g. a sequence or a
 * participant).
 *
 * E.g. the name of the actor is an identifier
 *
 * Actor Alice
 */
export class IdentifierNode extends Node { ... }
/**
 * The definition of an actor, where the string at the end is
 * the description.
 *
 *   Actor Alice is "A user"
 */
export class ActorNode extends NodeWithIdentifier { ... }
/**
 * The definition of an object, where the string at the end is
 * the description.
 * 
 *   Object Bob is "A fake system"
 */
export class ObjectNode extends NodeWithIdentifier { ... }
/**
 * A Sequence of messages between one or more participants.
 * This is what makes * a sequence diagram.
 *
 *   Sequence Hello
 *     Alice tell Bob "Sudo, make me a sandwich"
 *     Alice tell Charlie "Hello"
 */
export class SequenceNode extends NodeWithIdentifier { ... }
/**
 * The message that is exchanged by two participants, both of
 * which are refered to by their identifiers (names).
 *
 *   Alice ask Bob "Sudo, make me a sandwich"
 */
export class MessageNode extends Node { ... }
/**
 * Represents a string value, that can either be from a single
 * line or a multi-line string. This is what is between the
 * quotes in a message.
 *
 *   Alice ask Bob "Sudo, make me a sandwich"
 */
export class StringNode extends Node { ... }

Если вам интересно, посмотрите файл src/ast.js, чтобы получить полное представление о том, как выглядят узлы AST.

Посетите свое дерево парсеров

Итак, как именно это наше дерево синтаксического анализатора преобразовать в AST?

При генерации синтаксического анализатора ANTLR также генерирует прослушиватель, который определяет методы enter и exit для всех определенных правил грамматики. Если вы откроете файл parser/SequenceListener.js, вы увидите набор методов, объявленных в прототипе SequenceListener, которые выглядят так:

// Enter a parse tree produced by SequenceParser#actorDefinition. SequenceListener.prototype.enterActorDefinition = function(ctx) { };
// Exit a parse tree produced by SequenceParser#actorDefinition. SequenceListener.prototype.exitActorDefinition = function(ctx) { };

Поскольку мы не хотим трогать сгенерированный код, мы не изменяем этот файл напрямую, вместо этого мы объявляем наш собственный IntSequenceListener, который является производным от этого файла. Затем создается экземпляр слушателя и регистрируется в парсере в коде, который устанавливает парсер (который к настоящему времени должен быть знаком).

// Register our listener used to build the AST while the
// parsing is being done.
const errorListener = new AntlrErrorListener();
const listener = new IntSequenceListener();
parser.addErrorListener(errorListener); parser.addParseListener(listener);
// Initiate the parsing, and begin with the root rule.
const parserResult = parser.root();

ANTLR вызовет метод enter с содержимым дерева синтаксического анализатора в качестве аргумента, когда он запускает синтаксический анализ этого правила грамматики, и exit после того, как это правило, и все его внутренние правила были разобраны. Т.е. часто будут вызовы enter для других узлов до того, как текущий будет exit-ed.

Давайте посмотрим на порядок вызовов для небольшого примера:

Name "foo"

Вырезав только интересную часть определения грамматики:

root
    : NEWLINE* documentMeta definitions EOF
    ;
documentMeta
    : documentName
    ;
documentName
    : DOCUMENT_NAME string NEWLINE?
    ;
string
    : STRING
    ;

1. Первое правило грамматики - это грамматика root, поэтому выполняется вызов listener.enterRoot(...).
2. Name "foo" будет соответствовать грамматике documentMeta, выполняется вызов listener.enterDocumentMeta(...)
3. В документе Meta используется documentName грамматика, выполняется вызов listener.enterDocumentName(...).
4. Мета документа использует грамматику string для соответствия "foo", выполняется вызов listener.enterString(...)
5. Строка использует только лексические токены, никаких дополнительных вызовов не производится.
6. Звонок на listener.exitString(...) сделан
7. Звонок на listener.exitDocumentName(...) сделан
8. Звонок на listener.exitDocumentMeta(...) сделан
9. Звонок на listener.exitRoot(...) сделан

Наш слушатель IntSequenceListener хранит внутренний стек (или Array в JavaScript), куда он подталкивает все узлы по мере их входа, при выходе каждый узел присоединяется к своему родителю, образуя таким образом дерево.

Это так просто.

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

Sequence реализует этот слушатель в том же файле, в котором мы определяем наши узлы AST, в src/ast.js

Ввод и вывод

AST также легко протестировать: вы просто анализируете ввод и проверяете наличие ожидаемых узлов на выходе - побочного эффекта нет.

Разница в том, что AST (по крайней мере, для Sequence) не может обрабатывать дельту или ветвь кода Sequence, как это используется для грамматического модульного теста. Вместо этого тестируется основная запись программы, в которой используется root грамматика, поэтому вы должны указать «полные» описания последовательностей в своем тесте.

Тесты AST расположены по адресу __tests__/ast/ast.spec.js

Выводы

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

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

Парсер и компиляторы действительно хорошо подходят для TDD, все дело в вводе и выводе.

Следующим шагом является использование сгенерированного AST и проверка его семантической правильности, а не только синтаксиса, что известно как статический анализ или семантический анализ.

Удачного взлома!

Первоначально опубликовано на markuseliasson.se.