Не мог бы разработчик PEG парсера написать хоть какую-нибудь документацию?

Здравствуйте, Аноним, Вы писали:

А>Не мог бы разработчик PEG парсера написать хоть какую-нибудь документацию?

Хороший вопрос, меня он тоже в свое время интересовал.
Вообще советую взглянуть на демо-пример JSParser.

Здравствуйте, hardcase, Вы писали:

H>Здравствуйте, Аноним, Вы писали:

А>>Не мог бы разработчик PEG парсера написать хоть какую-нибудь документацию?

H>Хороший вопрос, меня он тоже в свое время интересовал.
H>Вообще советую взглянуть на демо-пример JSParser.

JSParser.

Здравствуйте, Аноним, Вы писали:

А>Не мог бы разработчик PEG парсера написать хоть какую-нибудь документацию?

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

Постораюсь в нескольких сообщениях накрапать что-то вроде описания, а потом оформлю это дело в более полноценную статью.

Итак...

Назначение

PegGrammar – это макро-атрибут уровня класса (применяемый к классам) предназначенный для автоматизации создаия парсеров (распознователей) различных формальных языков. Это могут быть как полноценные языки программирования (например, здесь: http://nemerle.googlecode.com/svn/nemerle/trunk/snippets/peg-parser/CSharp/CSharpParser/Parser.n вы моежете найти грамматику C#), так и простеньгие грамматики аля те, что обычно разбираются регулярными выражениями.
Использовать макрос крайне просто:

  [PegGrammar(СтартовоеПравило,
    grammar
    {
      Правила
    }
  )]
  public class Parser
  {
  }

В PegGrammar используется PEG-нотация (http://en.wikipedia.org/wiki/Parsing_expression_grammar). Она очень похожа на расширенную нотацию Бэкуса-Наура (BNF), но имеет иную интерпретацию. В то время как BNF описывает язык, PEG описывает парсер языка (т.е. то как надо разбирать строку).
PEG
В отличии от BNF PEG допускает только однозначные грамматики (грамматики имеющие одно дерево разбора). Это делает PEG отличным средством описания компьютерных языков, но не для естественных.
Более полную информацию о PEG вы можете получить по ссылке http://en.wikipedia.org/wiki/Parsing_expression_grammar. Здесь же я опишу только основные отличия от BNF. Первым и основным отличием является использование (в PEG) оператора приоритетного выбора «/» вместо оператора перечисления «|» в BNF. В двух словах – оператор перечисления описывает альтернативные подправила из которых состоит описываемое правило. При этом (для однозначного компьютерного языка) альтернативы не должны пересекаться с другдругом. Оператор приоритетного выбора же ведет себя иначе. Если строку удалось разобрать по первому правилу, то остальные (идущие после «/») правила игнорируются. Если строку не удалось разобрать по первому правилу, позиция разбора отматывается (производится backtracking, откат) на ту позицию в которой начался разбор первого подправила и произведится попытка разобрать строку по второму подправилу. Если строку удалось разобрать по второму правилу, то остальные правила, опять же, игнорируются. Если нет, то производится попытка разобрать строку по третьему правила, и так далее, пока не будут перебраны все варианты. Если строку не удалось разоборать ни по одному из подправил в списке преоритетного выбора, то разбора считается неудачным и производится попытка отката в во внешнем правиле. И так до тех пор пока строка или не будет разорбрана, или не будет произведен откан самого внешнего правила (при этом разбор считается неудачным).
Пример оператора приотитетного выбора:

simplExpr = num / parenthesesExpr / unaryMinus;

Грамматика PEG

В этом разделе описывается грамматика самого PEG (причем, в формате самого же PEG).

Rule            = RuleName ReturnType? '=' OrderedChoice;
OrderedChoice   = Sequence ('/' Sequence)*;
Sequence        = PredicateRule+;
PredicateRule   = ('!' / '&')? CardinalityRule;
CardinalityRule = SimpleRule ('?' / '+' / '*')?;
SimpleRule      = RuleName / Range / Char / String / '(' OrderedChoice ')' / Empty;
Ranges          = '[' Range+ ']';
Rang            = Char ".." Char / UnicodeCategory
ReturnType      = ':' NemerleType

Здесь:
RuleName – корректный идентификатор Nemerle.
Char – корректный символьный литерал (например: 'A' или '\'') Nemerle.
String – корректный строковый литерал Nemerle.
UnicodeCategory — стандартные сокращения для Unicode-категорий (позволяют задать сразу целый класс символов).
Семантика PEG

Rule (Правило)

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

Sequence        = PredicateRule+;

OrderedChoice (Приоритетный выбор)

Задает последовательность подправил по которым, поочередно, производится попытка разбора строки текущей позиции. В случае если одно строка в текущей позиции успешно распознается по одному из подправил, остальные подправила игнорируются. Если разпод по текущему подправилу терпит неудачу, производится откат позиции разбора в позицию которая была до начала разбора данного подправила и производится попытка разобрать строку по следующему подправилу, и так до успешного распознования или до исчерпания списка подправил (что расценивается как не успех разбора всего оператора приоритетного выбора).
Как можно видеть из грамматики OrderedChoice может иметь одного до неограниченного количества подправил. Таким образом последовательность (Sequence) является вырожденным случаем OrderedChoice.
Пример:

RuleName / Range / Char / String

Sequence (роследовательность)

Последовательность из одного (вырожденный случай) или более PredicateRule.
Пример:

Char ".." Char

PredicateRule (предикатное правило)

Состоит из необязательного предиката ('!' или '&') и идущего за ним CardinalityRule. Если предикат задан, то он делает идущее за ним подправило предикативным (эфимерным). Такое правило распознается только с делью дать ответ на вопрос можно ли продолжать дальнеший разбор. Информация о разборе предикативного подправила теряется.
Пример:

delimitedComment = "/*" (!"*/" any)* "*/";

Данный пример разбирает комментарий в стиле «C» — /* коментарий */. Здесь используется предикат «!», чтобы убедить, что разбираемый символ не является частью последовательности «*/» закрывающей коментарий.

CardinalityRule (управляющее правило)

Состоит из простого правила и необязательной управляющей конструкции. Всего поддерживается три управляющих конструции:
«*» — циклическое повторение разбора правила ноль или более раз. Заметьте, что даная конструкция всегда выполняется успешно.
«+» — циклическое повторение разбора правила один или более раз.
«?» — разбор правила ноль или один раз. Другими словами необязательный разбор правила. Заметьте, что даная конструкция всегда выполняется успешно.
Примеры:

PredicateRule+
ReturnType?
('?' / '+' / '*')?

SimpleRule (простое правило)

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

PredicateRule
Sequence
('?' / '+' / '*')
".."
['\u0000'..'\uFFFF']
'Z'

Ranges (диапазоны)

Список диапазонов символов или сокращений имен Unicode-категории.
Примеры:

['0'..'9']
['\u0000'..'\uFFFF']
['A'..'Z', 'a' .. 'z', '\u037F' .. '\u1FFF']
[Lu, Ll, Lt, Lm, Lo, Nl]

Строковый литерал

Задает последовательность символов. Например:

"try"

Этот пример эквивалентент следующему:

't' 'r' 'y'

А можно ли подключать и использовать уже ранее описаные грамматики? Т.е. инетресует модульность и повторное использование.

Здравствуйте, Ka3a4oK, Вы писали:

KK>А можно ли подключать и использовать уже ранее описаные грамматики? Т.е. инетресует модульность и повторное использование.

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

Здравствуйте, Ka3a4oK, Вы писали:

KK>А можно ли подключать и использовать уже ранее описаные грамматики? Т.е. инетресует модульность и повторное использование.

Пока что только если в виде partial-класса в разных частях которого описаны эти грамматики.

Но в принципе PEG в виду своей безлексерности позволяет хоть собирать грамматики из частей. Вопрос только в том как это синтаксически оформить.

Здравствуйте, VladD2, Вы писали:

Продолжение описания...

Семантические действия

Методы обработчики

Грамматика описывает парсер, но сам по себе парсер не более чем отвечает на вопрос соответствует ли входная строка данной грамматике или нет. Чтобы парсер делал нечто более полезное, например, выдавал AST (объектную модель описывающую код) для входной стоки нужно задать действия выполняемые при разбое тех или иных правил грамматики. Общепринятым подходом для решения этой задачи является вставка так называемых семантических действий внутрь грамматики. Такой подход имеет ряд существенных недостатков. Первый, и самый серьезный, грамматика разбавленная семантическими действиями разбухает и в итоге превращается трудную для изучения кашу. Кроме того встроенный код семантических действий обычно рассматривается генераторами парсеров как текст, что приводит к неудобству его создания и сопровождения. У этого подхода есть и другие проблемы. По этому в макросе PegGrammar был применен другой подход.

Семантические действия выделяются в отдельные методы класса к которому применен метаатрибут PegGrammar. Такие методы называются методы-обработчики. Можно рассматривать их как обработчики события «разобрано некоторое правило грамматики».

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

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

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

Пример правил и соответствующих методов-обработчиков (взято из примера Calculator: ):

[PegGrammar(start,
grammar
{  
  any                   = ['\u0000'..'\uFFFF'];
  digit                 = ['0'..'9']+;
  spaces                = ' '*;
  
  num                   : int = digit spaces;
  unaryMinus            : int = '-' spaces simplExpr;
  ...
 }
})]
public class CalcParser
{
  private num(digit : NToken, _ : NToken) : int
  {
    int.Parse(digit.GetText())
  }
  
  private unaryMinus(_ : NToken, _ : NToken, se : VToken[int]) : int
  {
    -se.Value
  }
  ...
}

Параметры методов-обработчиков

Каждый метод обработчик должен иметь параметры принимающие информацию о разобранных подправилах. Количество параметров зависит от того из чего состоит тело правила.

Если тело правила состоит из не вырожденного OrderedChoice, то обработчик должен принимать ровно один параметр тип которого должен быть совместим с типами возвращаемыми всеми элементами OrderedChoice.

simplExpr : int = num / parenthesesExpr / unaryMinus / parenthesesExprError / simplExprError;
...
private simplExpr(se : VToken[int]) : int
{
  se.Value
}

ПРИМЕЧАНИЕ
Скорее всего в дальнейшем такие обработчики вообще не придется описывать явно, так как макрос PegGrammar будет генерировать их автоматически.

В ином случае, то есть, если тело правила является вырожденным случаем OrderedChoice (OrderedChoice с одним элементом), тело правила можно рассматривать как Sequence. Для каждого элемента Sequence (верхнего уровня) должно быть объявлено по одному параметру. Если в Sequence только один элемент, то следует объявить один параметр. Если два — два, и так далее.

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

Типы параметров могут быть одного из двух перечисленных ниже типов:

• NToken — описывает результат разбора правила не имеющего обработчика и стало быть для которого не формируется какого-либо значения. Для результатов разбора таких правил можно узнать только позиции начала и конца фрагмента текста который был разобран по данному правилу и сам текст.
  
• VToken[T] — описывает результат возвращенный методом-обработчиком некоторого правила (тип которого задается в параметре типа) и информацию аналогичную той что описывает NToken.

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

Если подравило описывает значение возвращенное правилом для которого задан некоторый тип (а стало быть метод-обработчик возвращающий значение этого типа), то для описания типа параметра представляющего значение разбора этого подправила нужно использовать тип VToken[T], а в качестве параметра типа (T) следует передать тип соответствующий возвращаемому значению того правила на которое ссылается подправило для которого описывается параметр.

Возможно это сложно звучит, но на практике все довольно просто. Разберем пример приведенный выше.

Для правила:

  num                   : int = digit spaces;

создается метод-обработчик:

  private num(digit : NToken, _ : NToken) : int
  {
    int.Parse(digit.GetText())
  }

имеющий два параметра. Первый параметр представляет значение для первого подправила ссылающегося на правило digit (разбирающего число). Так как для правила digit не задано обработчика, используется тип NToken. Значение этого типа позволяет получить текст разобранного фрагмента. В данном обработчике этот текст передается функции int.Parse, которая преобразует его в целое число.

Второй параметр метода-обработчика «num» соответствует второму подправилу ссылающемуся на правило spaces (разбирающее необязательные пробельные символ). Это правило так же имеет обработчика, так что для описания параметра соответствующего ему используется тип NToken. Так как значение пробельных символов не интересно для решаемой задачи (для вычисления выражения), этот параметр игнорируется. Для того чтобы компилятор не выдавал предупреждения о неиспользуемом параметре его имя задается как «_».

Для правила:

unaryMinus : int = '-' spaces simplExpr;

Задается обработчик:

  private unaryMinus(_ : NToken, _ : NToken, se : VToken[int]) : int
  {
    -se.Value
  }

который имеет три параметра.

Первый параметр соответствует первому подправилу описывающему разбор литерала '-'. Так как это это подправило задано по месту (т.е. для него не создано отдельного именованного правило), для него не может быть и задан обработчик. Стало быть в качестве типа параметра содержащего информацию о разборе этого подправила нужно использовать тип NToken. Кроме того, так как информация о разборе литерала нам не интересна (нам важен только лишь сам факт, что он был разобран), данный параметр игнорируется.

Второй параметр соответствует подправилу «spaces». Его значение так же игнорируется. (думаю не стоит пояснять, что тип этого параметра должен быть NToken).

Третий параметр (se) соответствует подправилу ссылающемуся на правило «simplExpr». Так как для этого правила задан метод-обработчик возвращающий значение типа «int», тип данного параметра должен быть VToken[int].

Значение разобранное по правилу «simplExpr» может быть получено через поле Value. Обработчик unaryMinus просто инвертирует знак этого значения и возвращает результат в качестве возвращаемого значения.
Параметры для подправил типа CardinalityRule

Если подправило задает цикл (* или +), для описания параметров соответствующих им следует использовать тип System.Collections.Generic.List[T]. При этом параметр типа (T) должен иметь значение соответствующее типу подправила составляющего тело цикла. Если тело цикла является последовательностью подправил (Sequence), следует использовать кортеж типы элементы которого соответствуют типам подправил составляющих тело цикла (с учетом оберток VToken[T] и NToken).

Пример:

type LoopTokens = NToken * NToken * VToken[int];
...
mulOrDiv : int = simplExpr (('*' / '/') spaces simplExpr)*;
...
private mulOrDiv(se : VToken[int], lst : List[LoopTokens]) : int
{
  ...
}

Если подправило является необязательным (?), его тип должен быть обернут в тип option[T], где значение параметра типов (T) определяется по перечисленным выше правилам.

Пример:

mainRule : int = sumOrSub inputError?;
...
private mainRule(se : VToken[int], _ : option[VToken[int]]) : int
{
  se.Value
}

ПРЕДУПРЕЖДЕНИЕ
На сегодня оборачивать в option[T] требуется как VToken[T], так и NToken. Однако для NToken — это не имеет смысла, так как для необязательного правила которое не было разобрано NToken попросту содержит пустой диапазон (что указывает на то, что правило не было разобрано). По этому в будущем, скорее всего, для необязательные значения типа NToken не будет требоваться оборачивать в option[T].

Предикаты

На сегодня для предикатов требуется задавать параметры так же как и для обычных правил. Однако — это не более чем не доработка и в будущем она будет исправлена.

Здравствуйте, VladD2, Вы писали:

VD>

Ranges (диапазоны)

VD>Список диапазонов символов или сокращений имен Unicode-категории.
VD>Примеры:
VD>

VD>['0'..'9']
VD>['\u0000'..'\uFFFF']
VD>['A'..'Z', 'a' .. 'z', '\u037F' .. '\u1FFF']
VD>[Lu, Ll, Lt, Lm, Lo, Nl]
VD>

Краткие имена Unicode категорий допустимы только в диапазонах.
Полный список сокращений и их интерпретацию можно найти в описании перечисления UnicodeCategory в MSDN.

Здравствуйте, VladD2, Вы писали:

Продолжение описания...

Особенности использования PegGrammar

Левая рекурсия

PEG фактически описывает нисходящий рекурсивный парсер с откатами. Этот тип парсеров имеет одно ограничение. Без специальной доработки (негативно влияющей на производительность и сильно усложняющей парсер) парсеры этого типа не могут разбирать леворекурсивные грамматики.
Леворекурсивной грамматикой называют грамматику которая имеет леворекурсивные правила (прямые или нет). Например, следующая грамматика имеет левую рекурсию:

X = X '+' 1 / 1

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

X = 1 ('+' 1)*

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

Левая факторизация

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

3 * x + 3 * y

можно переписать как:

3 * (x + y)

Примерно тоже самое можно сделать и с правилами грамматики. Вместо:

A = X Y / X Z

можно записать:

A = X (Y / Z)

Эти правила будут разбирать одну и ту же грамматику, но во втором случае правило X будет разобрано только один раз.
Потенциально проблему экспоненциального роста затрат времени на прасинг можно решить с помощью мемоизации (с использованием алгоритма Packrat предложенного Фордом), но, к сожалению, прямое использование этого алгоритма ведет к серьезному увеличению постоянных затрат и линейному росту потребления памяти. Фактически таблица мемоизации должна содержать количество элементов равное произведению количества символов в разбираемой строке на количество правил грамматики, что слишком много для языков программирования.
Вместо мемоизации результата разбора все правил можно было бы мемоизировать результаты только отдельных правил, но это требует разработки эвристик выбора таких правил или введения ручного способа указания того какие правила требуется мемоизировать. В будущем мы планируем добавить подобные механизмы. Но пока что их нет и требуется производить левую факторизацию с целью устранения проблемных мест.

Оптимизации

На сегодня PegGrammar делает небольшой набор оптимизаций. Основной оптимизацией является инлайнинг правил грамматики. Это приводит к увеличению объема кода, но за счет устранения вызова методов приводит к заметному ускорению разбора.
Кроме того PegGrammar генерирует довольно оптимальный код, состоящий в основном из if-ов и присвоения одной целочисленной переменной (позиции парсинга). В генерируемом коде нет замыканий, классов и прочих высокоуровневых штуковин. Это положительно влияет на производительности парсер.
PegGrammar так же оптимизирует генерацию кода для ряда сочетаний правил, что уменьшат и ускоряет конечный код.
В дальнейшем планируется добавить ряд более сложных оптимизаций нацеленных на ускорение разбора и уменьшение объема генерируемого кода.
Основные планируемые оптимизации:
1. Генерация детерминированных конечных автоматов (ДКА) для терминальных (оперирующих с символами), не рекурсивных правил грамматики для которых не было задано методов-обработчиков. Это позволит довести скорость разбора нижнего уровня до скорости обеспечиваемой использованием рукописных лексеров, причем, при сохранении преимущества безлексерного подхода и соответствующих возможностей по модульному расширению грамматик.
2. Введение мемоизации для отдельных правил грамматики. Пока не ясно получится ли найти приемлемые эвристики которые позволят путем статического анализа грамматики выявлять правила требующие мемоизации. Если это удастся, то правила подлежащие мемоизации будут выявляться автоматически и PegGrammar будет обеспечивать оптимальную производительность в автоматическом режиме. Если же приемлемые эвристики найти не удастся, то будет добавлена возможность помечать отдельные правила как требующие мемоизации. PegGrammar будет генерировать код мемоизации и соответствующие проверки мемоизированных результатов при разборе помеченных правил.
3. Введение точек отсечения. Точки отсечения — это точки задаваемые автором грамматики которые позволят PegGrammar не производить откаты за пределы этих точек, что позволит обрезать таблицы мемоизации используемые для предотвращения портового разбора правил, а так же упростит выявление ошибок во входной строке.
Надеемся, что этот набор оптимизаций позволит довести скорость парсеров получаемых с использованием макроса PegGrammar до уровня обеспечиваемого лучшими рукописными парсерами. В прочем, и на сегодня скорость парсеров создаваемых с использованием PegGrammar весьма неплоха.
Естественно, мы будем рады услышать любые предложения и замечания относительно идей по оптимизации производительности парсеров генерируемых PegGrammar, как в прочем и любые другие.
Недоработки
PegGrammar очень молодой продукт, так что немудрено, что не все в нем еще работает как хотелось бы. Вот список известных проблем которые со временем будут устранены:
* PegGrammar формирует параметры методов-обработчиков для предикатных правил. Предикатные правила не влияют результат работы парсер, а всего лишь позволяют предотвратить неверные пути разбора. Стало быть результат их работы не должен быть доступен пользователю. Однако, на сегодня это не так и вам придется описывать параметры для предикатных подправил.
* Для необязательных подправил и подправил циклов типа «*» не возвращающих значение (описываемых с помощью NToken) на сегодня требуется описывать соответствующие параметры с использованием option[T]. Однако в этом нет смысла, так как NToken для не разобранного правила просто может содержать равные позиции начала и конца (то есть, пустой диапазон). Учитывая, что option[T] — это объект на создание которого тратится время и память, данное.
* На сегодня PegGrammar не позволяет вмешиваться в процесс работы парсера. Однако это не более чем недоработка, так как соответствующие механизмы заложены в проект. Так имеется механизм точек расширения который позволяет в некотором месте грамматики вставить другой парсер (рукописный или другой экземпляр сгенерированный PegGrammar). Кроме того в следует дать возможность отдельным правилам давать возможность считывать и модифицировать текущую позицию разбора. Это позволит производить ручной парсинг и/или сигнализировать о неудачном завершении разбора правила прямо из методов-обработчиков.
* На сегодня не решен вопрос и с модульностью. PEG-нотация обеспечивает великолепный потенциал для поддержки модульности грамматик. Это обеспечивается тем, что нет нужды в отдельном лексическом анализаторе. Любой парсер может иметь необходимые ему «лексические правила» (в кавычках потому, что в PEG нед даже деления на лексические и синтаксические правила). В будущем мы постараемся реализовать возможность подключения готовых грамматик к другим грамматикам и тем самым формирования более сложных грамматик из ряда более простых. Например, общие правила разбора выражений можно вынести в отдельную грамматику и подключать там где они нужны.