peg 1.0.0

Command line tool for generating PEG parsers with support for event-based parsing.

peg

Command line tool for generating PEG parsers with support for event-based parsing.

Version: 1.0.0

Об этом программном обеспечении

Данное программное обеспечение не содержит публичного API поскольку оно является консольным приложением (средством командной строки).
Это средство предназначено для генерации исходного кода PEG парсеров.
Перед началом использования данного средства необходимо произвести его активацию при помощи пакетного менеджера pud.

Активация и использование

Для активации данного средства командной строки необходимо выполнить следующую команду:

dart pub global activate peg

После активации, для использования средства командной строки можно пользоваться следующей командой:

dart pub global run peg

Что из себя представляет исходный код сгенерированного парсера?

Исходный код сгенерированного парсера состоит из следующих частей:

• Исходный код класса парсера (генерируется из правил грамматики)
• Исходный код членов класса парсера (определяется грамматикой)
• Исходный код членов библиотеки (определяется грамматикой)
• Исходный код среды выполнения

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

• Обеспечение работоспособности парсера (например, директивы импорта)
• Расширение возможностей и оптимизация парсера за счет расширения возможностей экземпляра класса парсера

Как объявить грамматику?

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

Данный генератор генерирует сам себя из грамматики написанной с использованием собственного синтаксиса.
Для более детального ознакомления с синтаксисом рекомендуется ознакомится с синтаксисом грамматики, используемой для генерации данного парсера PEG.
https://github.com/mezoni/peg/blob/main/bin/peg_parser.peg

Объявление грамматики производится с использованием секций, наподобие секций для препроцессора, но, в тоже время, необходимо отметить, что предварительная обработка не производится и обработка (разбор) грамматики происходит в один этап.

Для объявление грамматики используются 3 секции:

• Секция для объявления директив и глобальных членов
• Секция для объявления членов экземпляров класса парсера
• Секция для объявления правил грамматики

Пример объявления грамматики:

%{

import 'foo.dart';

}%

%%

const SimpleParser();

%%

A = [A-Za-z] * ;

Грамматика должна содержать хотя бы одно правило, из чего следует, что использование секции для объявления правил грамматики является обязательным. Использование других секции не является обязательных и определяется реальными потребностями исходя из выбранного способа объявления грамматики.

Как объявить правила?

Объявление правила заключается в указании (в определенной последовательности) атрибутов правила и его тела и состоит из следующих элементов:

• Тип возвращаемого результата
• Метаданные
• Имя правила
• Символ =
• Выражение
• Символ ;

Тип возвращаемого результата и метаданные являются необязательными.
Для указания типа возвращаемого результата правила необходимо использовать синтаксис языка Dart.
Концепция метаданных отличается от принятой в языке Dart и используется исключительно в качестве инструкций для генератора парсера.

Пример объявления правила с типом результата и метаданными:

bool
@inline
False = 'false' Spaces { $$ = false; } ;

MapEntry<String, Object?>
@event
KeyValue = k:Key Colon v:Value { $$ = MapEntry(k, v); };

Как объявить выражения?

Ниже представлен перечень доступных выражений.

Наименование: Orderer choice
Оператор: /
Число операндов: 2 и более

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

Пример:

'abc' / 'def'

Наименование: Sequence
Оператор: не используется
Число операндов: 2 и более

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

Пример:

'abc' 'def'

Наименование: Optional
Оператор: ?
Число операндов: 1

Выполняет операнд и в случае, если выполнение операнда завершается успешно, то возвращается этот результат. Если выполнение операнда завершается неуспешно, то данное выражение завершается успешно и возвращается null.

'abc'?

Наименование: Zero or more
Оператор: *
Число операндов: 1

Циклически выполняет операнд до тех пор, пока выполнение операнда не завершится неуспешно. Во время выполнения помещает результаты выполнения операнда в список. После завершения выполнения цикла выражение завершается успешно и возвращается список результатов.

'abc'*

Наименование: One or more
Оператор: +
Число операндов: 1

Циклически выполняет операнд до тех пор, пока выполнение операнда не завершится неуспешно. Во время выполнения помещает результаты выполнения операнда в список. Если количество элементов в списке результатов не менее 1, то возвращается список результатов.

'abc'+

Наименование: Repetition
Операторы: {min,max} или {min,} или {,max} или {n}
Число операндов: 1

Примечание: Использование пробелов в теле оператора (то есть, между { и }) не допускается и будет приводить к синтаксическим ошибкам.

Пример неправильного использования:

[0-9A-Zza-Z]{1, 4}

Оператор {min,max}:

Циклически выполняет операнд не менее min и не более max раз. Во время выполнения помещает результаты выполнения операнда в список. Если (после завершения цикла) количество элементов в списке результатов не менее min, то возвращается список результатов.

[0-9A-Zza-Z]{1,4}

Оператор {min,}:

Циклически выполняет операнд не менее min раз. Во время выполнения помещает результаты выполнения операнда в список. Если (после завершения цикла) количество элементов в списке результатов не менее min, то возвращается список результатов.

[0-9A-Zza-Z]{2,}

Оператор {,max}:

Циклически выполняет операнд не более max раз. Во время выполнения помещает результаты выполнения операнда в список. После завершения выполнения цикла возвращается список результатов.

[0-9A-Zza-Z]{,4}

Оператор {n}:

Циклически выполняет операнд n раз. Во время выполнения помещает результаты выполнения операнда в список. Если (после завершения цикла) количество элементов в списке результатов равно n, то возвращается список результатов.

[0-9A-Zza-Z]{4}

Наименование: Literal
Оператор: не используется
Операнды: строковое значение, заключенное в одиночные кавычки

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

Сопоставляет входные данные в текущей позиции со строковым значением. Если сопоставление приходит успешно, то текущая позиция увеличивается на значение длины строкового значения и возвращается это строковое значение.

'abc'

Наименование: Character class
Оператор: не используется
Операнды: диапазоны символов, заключенный между [ и ] или [^ и ]

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

Операнд диапазоны символов, заключенный между [ и ]

Проверяет символ из входных данных в текущей позиции на предмет вхождения в один из указанных диапазонов. Если проверка приходит успешно, то текущая позиция увеличивается на значение длины текущего символа и возвращается текущий символ.

[0-9A-Za-z]

Операнд диапазоны символов, заключенный между [^ и ]

Проверяет символ из входных данных в текущей позиции на предмет невхождения в один из указанных диапазонов. Если проверка приходит успешно, то текущая позиция увеличивается на значение длины текущего символа и возвращается текущий символ.

[^0-9A-Za-z]

Наименование: Slice
Оператор: $
Число операндов: 1

Выполняет операнд и в случае, если выполнение операнда завершается успешно то возвращается текст, соответствующий начальной и конечной позиции операнда.

$([a-z])*

Наименование: Symbol
Оператор: не используется
Операнд: Имя правила

Выполняет операнд (правило, с указанным именем) и возвращает результат выполнения операнда.

$([a-z])*

Семантические переменные и акции

В данной реализации генератора парсеров PEG наиболее сложным выражением (для генерации) принято считать выражение Sequence.

Данное выражение (условно) разделяются на два типа:

• Последовательности выражений с одним выражением
• Последовательности выражений с более чем одним выражением

Возникает вполне закономерный вопрос: "Почему последовательность выражений с одним выражением является последовательностью?".
Краткий ответ на этот вопрос может звучать примерно так: "Потому что в текущей реализации только последовательность может иметь семантическую акцию".

И, поскольку, семантическая акция, в этом случае, не рассматривается, как самостоятельное выражение, то это позволяет сделать семантические акции полноценным аналогом функции map, с указанием типа возвращаемого результата.
Одновременно это позволяет реализовать вложенные выражения проще, за счет простого mapping.

Прежде чем объяснить принципы работы семантических переменных и акций, хотелось бы, объяснить принципы формирования результатов выполнения выражений Sequence.

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

Пример:

A = 'abc';

Тип возвращаемого значения String, значение - 'abc'.

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

Пример:

A = 'abc' 'def';

Тип возвращаемого значения (String, String), значение - ('abc', 'def').

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

Пример:

A = a:'abc';

Тип возвращаемого значения String, значение - 'abc'.
Использование семантической переменной, в данном случае, не влияет не тип результата, потому что последовательность, для формирования результата, содержит один элемент.

Пример:

A = a:'abc' b:'def';

Тип возвращаемого значения (String a, String b), значение - (a: 'abc', b: 'def').

A = OpenBrace v:Value CloseBrace';

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

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

Пример использования семантической акции без переменных:

bool
False = 'false' Spaces { $$ = false; } ;

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

Пример использования семантической акции с переменных:

MapEntry<String, Object?>
KeyValue = k:Key Colon v:Value { $$ = MapEntry(k, v); };

В вышеуказанном примере, в семантической акции используются переменные для формирования конечного результата, что, по своей сути, работает аналогично функции функции map(KeyType k, ValueType v).

Также, при использовании семантических акций, можно использовать тип результата значения семантических акций.

Пример использования семантической акции с указанием типа результата:

KeyValue = k:Key Colon v:Value <MapEntry<String, Object?>>{ $$ = MapEntry(k, v); };

Пользовательская обработка ошибок

Несмотря на то, что, во время разбора, парсер генерирует ошибки, использование, определенных разработчиком, сообщений об ошибках может в значительной мере улучшить восприятие информации об причинах возникновения ошибок.
Для этих целей предусмотрен специальный вид акции (блока исходного кода), который предназначен для указания специального обработчика формирования ошибок.
Основная цель - это предоставить возможность регистрировать определенные ошибки и предоставить возможность удалять (скрывать) вложенные ошибки, возникающие в период действия обработчика.
Обработчик ошибок может быть определен только для выражения Sequence.
Объявление обработчика ошибок состоит из следующих элементов:

• Строка ~{
• Исходный код обработчика
• Символ }

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

Пример создания ошибки ErrorExpectedTags вместо ошибки ErrorUnexpectedCharacter

Integer = v:IntegerRaw
  ~{
    if (state.failPos == state.pos) {
      removeLastErrors();
      state.failAt(state.failPos, const ErrorExpectedTag(['integer]));
    }
  } ;

IntegerRaw = v:$[0-9] { $$ = int.parse(v); } ;

Пример создания ошибки ErrorMessage вместо ошибки ErrorUnexpectedCharacter

HexNumber = HexNumberRaw
  ~{
    removeLastErrors();
    state.failAt(state.failPos, ErrorMessage(state.pos - state.failPos, 'Expected 4 digit hex number'));
  } ;

int
@inline
HexNumberRaw = v:$([0-9A-Za-z]{4}) { $$ = int.parse(v, radix: 16); } ;

Метаданные

Метаданные - это инструкции для генератора. Метаданные не являются обязательными.
Метаданные можно указывать при объявлении правил, указывая их перед наименование правила.

Примеры указания метаданных.

@inline
Foo = 'foo' ;

В текущей версии поддерживаются следующие инструкции:

• @event
• @inline
• @memoize

Инструкция @event позволяет указать генератору о том, что для данного правила, при разборе данных, необходимо осуществлять вывоз методов beginEvent и endEvent. Вызов этих методов фактически позволяет осуществить Event-based parsing.

Инструкция @inline позволяет указать генератору о том, что исходный код данного правила не должен создавать отдельный метод в классе парсера и должен быть сгенерирован в виде кода, встроенного в метод, который вызывает данное правило.

Инструкция @inline в текущей версии не реализована.

Оптимизация генерируемого кода

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

Фрагменты кода (code snippets)

SeparatedList1

List<ElemType>
SeparatedList1 = h:Elem t:(Sep v:Elem)* { $$ = [h, ...t] } ;

SeparatedList

List<ElemType>
SeparatedList =
    h:Elem t:(Sep v:Elem)* { $$ = [h, ...t] }
  / '' { $$ = []; } ;

List<ElemType>
SeparatedList = v:SeparatedList1 { $$ = v ??= []; } ;

Eof

Eof = !. ;

TakeWhile

TakeWhile = $[0-9]* ;

TakeWhile1

TakeWhile1 = $[0-9]+ ;

SeparatedPair

SeparatedPair = k:Key Sep v:Value { $$ = (k, v); } ;