Реферат: Макрос PegGrammar

Макрос PegGrammar

Версия: 1.0

Дата: 07.06.2011

Автор: ФИО: Чистяков Владислав Юрьевич; E-Mail: vc@rsdn.ru; Номер профиля на rsdn.ru:  73; Место работы: ООО «К-Пресс»; Должность: Директор;

Аннотация: Макрос PegGrammar – это макрос Nemerle, позволяющий добавлять в приложения парсеры, описываемые в нотации PEG.

Ключевые слова: Язык программирования; Nemerle; макрос, PEG, парсер, контекстно-свободный язык, контекстно-зависимый язык

Источник: Заголовок: RSDN Magazine #2-2010; Url: http://rsdn.ru/mag/main.htm

Обложка: http://rsdn.ru/mag/cover/mag0210.jpg

Macro PegGrammar

Версия: 1.0

Дата: 07.06.2011

Автор: ФИО: Chistyakov Vlad; E-Mail: vc@rsdn.ru; Номер профиля на rsdn.ru:  73; Место работы: “K-Press” Inc.; Должность: Director;

Аннотация: PegGrammar macro is a Nemerle macro, which allows to add to the application parsers, described in the PEG notation.

Ключевые слова: Programming language; Nemerle; macro, PEG, parcer, context-free language, context-dependent language



Назначение

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

Чтобы воспользоваться PegGrammar, нужно подключить к текущему проекту ссылку (обычную или Macro reference) на Nemerle.Peg.Macros.dll и ссылку на Nemerle.Peg.dll. Эти библиотеки идут в поставке компилятора, но учитывая, что PegGrammar в настоящее время все еще бурно развивается, лучше собирать эти библиотеки из исходников. Их код можно найти здесь.

Использовать макрос крайне просто:

[PegGrammar(Options = EmitDebugSources, СтартовоеПравило,

grammar

{

Правила

}

)]

public class Parser

{

Методы-обработчики для правил

}

В PegGrammar используется PEG-нотация (http://en.wikipedia.org/wiki/Parsing_expression_grammar). Она очень похожа на расширенную нотацию Бэкуса-Наура (BNF), но имеет иную интерпретацию. В то время как BNF описывает язык, PEG описывает парсер языка (т.е. то, как надо разбирать строку, что несколько роднит PEG с регулярными выражениями).

PEG

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

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

Пример оператора приоритетного выбора:

simplExpr = num / parenthesesExpr / unaryMinus;

^ Грамматика PEG

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

// PEG-грамматика

Rule = Attributes? RuleName ReturnType? '=' OrderedChoice ";";

ExpandableRule = Attributes? OperatorRuleName ReturnType? ";";

ExpandRule = Attributes? OperatorRuleName "is" RuleName '=' OrderedChoice ";";


OrderedChoice = Sequence ('/' Sequence)*;

Sequence = PredicateRule+;

PredicateRule = ('!' / '&')? CardinalityRule;

CardinalityRule = SimpleRule ('?' / '+' / '*')?;

SimpleRule = '%' / Scope / RuleName (":" Precedence)? / Ranges / Char

/ String / '(' OrderedChoice ')' / Empty;

Ranges = '[' Range+ ']';

Range = Char ".." Char / UnicodeCategory;

// Выражения основанные на приоритетах – «операторы»

Operator = PrefixOperator / PrefixOperator / PostfixOperator;

PrefixOperator = String RuleName ":" Precedence;

PostfixOperator = RuleName ":" Precedence String;

SimpleOperator = OrderedChoice;

InfixOperator = RuleName ":" Precedence (String RuleName ":" Precedence)+;

Precedence = ['0' .. '9']+;


// PEG-грамматикаOrderedChoice = Sequence ('/' Sequence)*;

Sequence = PredicateRule+;

PredicateRule = ('!' / '&')? CardinalityRule;

CardinalityRule = SimpleRule ('?' / '+' / '*')?;

SimpleRule = '%' / FailureRecovery / Scope / RuleName / Range / Char

/ String / '(' OrderedChoice ')' / Empty;

Ranges = '[' Range+ ']';

Rang = Char ".." Char / UnicodeCategory// Общие конструкции

ReturnType = ':' NemerleType

RuleName = Identifier;

OperatorRuleName = Identifier;

Attribute = "Inline"

/ "InlineAllSubrules"

/ "Extensible"

/ FailureRecovery

/ '%' '(' MethodHandler ',' SkipRule ')'

/ '<' RuleName

/ '>' RuleName

/ "==" RuleName;

Attributes = '[' Attribute (',' Attribute)* ']'

MethodHandler = Identifier;

SkipRule = OrderedChoice;

FailureRecovery = "FailureRecovery" '(' MethodHandler ',' StopRule ',' SkipRule ')';


// «Область» позволяющая организовать транзцакции

ScopedRule = OrderedChoice;

ScopeName = Identifier;

Scope = ScopeName '{' ScopedRule '}';


// Восттановаление после обнаружения ошибок


SkipRule = ScopedRule;

MethodHandler = Identifier;

FailureRecovery = "FailureRecovery" '(' MethodHandler ',' SkipRule ')';

Здесь:

Identifier – корректный идентификатор Nemerle.

Char – корректный символьный литерал (например: 'A' или '\'') Nemerle.

String – корректный строковый литерал Nemerle.

NemerleType – описание типа в Nemerle (может включать указание пространства имен и парамеры типов).

UnicodeCategory – стандартные сокращения для Unicode-категорий (позволяют задать сразу целый класс символов).

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

SkipRule – правило позволяющее пропустить часть входных символов во время процедуры восстановления после обнаружения ошибки. Данное правило выполняется циклически пока не сопоставится правило StopRule или не будет обнаружен конец входной строки. Правила StopRule и SkipRule нужно рассматривать совместно. StopRule выполняет роль условия останова пропуска некорректного ввода, а SkipRule описывает минимальную грамматическую еденицу которую можно пропустить за раз.

^ Семантика PEG

Rule (Правило)

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

Пример:

Sequence = PredicateRule+;

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

E1 / E2 / ... / En

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

Как можно видеть из грамматики, OrderedChoice может иметь от одного до неограниченного количества подправил. Таким образом, последовательность (Sequence) является вырожденным случаем OrderedChoice.

Пример:

RuleName / Range / Char / String

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

E1 E2 ... En

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

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

Пример:

Char ".." Char

ScopeName '{' ScopedRule '}'

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

&E

!E

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

& – позитивный предикат. Возвращает успех, если идущее за ним правило успешно распознано, и неудачу в обратном случае.

! – негативный предикат. Возвращает успех, если идущее за ним правило потерпело неудачу при разборе, и неудачу в случае успешного разбора.

Пример:

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

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

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

E*

E+

E?

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

«*» – циклическое повторение разбора правила ноль или более раз. Заметьте, что данная конструкция всегда выполняется успешно (даже если E терпит неудачу).

«+» – циклическое повторение разбора правила один или более раз.

«?» – разбор правила ноль или один раз. Другими словами, необязательный разбор правила. Заметьте, что данная конструкция также всегда разбирается успешно.

Примеры:

PredicateRule+

('/' Sequence)*

ReturnType?

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

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

Примеры:

PredicateRule

Sequence

('?' / '+' / '*')

".."

['\u0000'..'\uFFFF']

'Z'

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

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

Примеры:

['0'..'9']

['\u0000'..'\uFFFF']

['A'..'Z', 'a' .. 'z', '\u037F' .. '\u1FFF']

[Lu, Ll, Lt, Lm, Lo, Nl]

ScopeName { Type* }

^ Символьный литерал

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

't'

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

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

"try"

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

't' 'r' 'y'

^ Attributes (Атрибуты)

Атрибуты позволяют задать дополнительную метаинформацию для именованного правила (Rule). На данный момент поддерживаются следующие атрибуты:

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

InlineAllSubrules – указывает, что все подправила должны быть раскрыты по месту.

Extensible – указывает, что данное правило является точкой расширения. Такие правила могут быть динамически (во время исполнения) расширены другими правилами. Данный атрибут может применяться только к правилам, содержащим невырожденный (т.е. состоящий более чем из одного вхождения) оператор приоритетного выбора (OrderedChoice), так как только он может быть расширен динамически. Точки расширения, совместно с областями видимости (Scope), можно использовать, чтобы создавать парсеры динамически-расширяемых языков (например, самого Nemerle). При этом Scope можно использовать для открытия и закрытия пространств имен, содержащих правила, расширяющие грамматику разбираемого языка, а атрибутом Extensible будут указываться те правила, которые будут динамически пополняться. Правила, помеченные атрибутом Extensible, превращаются макросом PegGrammar в массивы, которые можно пополнять динамически, и в которых правила сортируются в соответствии с их приоритетами (задаваемыми так же атрибутами).

FailureRecovery – позволяет задать «точку восстановления» после обнаруженной парсером ошибки. Данный атрибут применим к правилам, состоящим из непустого оператора приоритетного выбора (OrderedChoice). Если в грамматике не заданы точки восстановления или точки отсечения (о них см. ниже), то при обнаружении первой ошибки парсер прекращает разбор (так как все правила откатываются) и сообщает об ошибке. FailureRecovery позволяет указать, что данное правило не должно откатываться при обнаружении ошибки. Атрибут FailureRecovery задает метод-обработчик, который генерирует заглушку (AST-элемент, содержащий информацию об ошибке), а также правилао, позволяющие остановить процедуру восстановления, если обнаружена корректная входная строка для другого правила, и правило позволяющееее пропустить некорректные данные символы во входной строки. Эе, что позволяет парсеру продолжить разбор строки, даже если она частично не соответствует грамматике разбираемого языка (содержит ошибки). Это позволяет выявлять несколько ошибок сразу.

Например, в грамматике C# точка восстановления для правила statement может выглядеть следующим образом:

[FailureRecovery(statementRecovery, ("}" / statement / switchSection), (space+ / stringLiteral+ / block / [Any]))]

statement : Statement = labeledStatement

/ declarationStatement

/ embeddedStatement;

Здесь, правило «("}" / statement / switchSection)» позволяет остановить процедуру восстановления в случае, если далее следует закрывающая скобка (statement-ы могут быть вложены в блок), другой statement или switchSection (case или default из тела оператора switch).

Правило пропуска входного потока могло бы состоять из пропуска любых символов ([Any]), но это может привести к тому, что процедура восстановления «залезет» в комментарий, строковый литерал или вложенный блок, что может привести к преждевременному останову процесса восстановления, и как следствие, ряда дополнительных, неверных, сообщений об ошибках. Правила «space+» «stringLiteral+» и block позволяют пропустить данные конструкции целиком и тем самым не допустить появления фантомных сообщений об ошибках.


% – позволяет задать дополнительную информацию для точки отсечения. Сама точка отсечения задается тем же знаком «%» в теле правила. Как и FailureRecovery, точка отсечения предназначена для организации восстановления разбора входной строки после обнаружения в ней ошибки. В отличие от FailureRecovery, точки отсечения позволяют не только предотвратить откат разбираемого правила, но и принуждают парсер создать ветку AST, содержащую те элементы, что были разобраны к моменту обнаружения ошибки. Кроме того, точки отсечения отличаются от точек восстановления тем, что применимы только к правилам, состоящим из последовательностей (Sequence), а также тем, что восстановление в этих точках начинается только в случае, если парсер разобрал начальную часть правила (префикс), идущую до точки отсечения, что гарантирует, что откат не связан со штатным откатом правила (которое может случиться, например, в случае разбора пустого выражения). Точки отсечения позволяют добиться более качественного восстановления после обнаружения ошибок, так как более точно выявляют место ошибки, а также позволяют создать AST, содержащее часть данных, корректно введенных пользователем (что может быть использовано, например, в IntelliSense).

'<' RuleName, '>' RuleName, "==" RuleName – этот атрибут используется совместно с атрибутом Extensible для задания относительного приоритета правил. Правила, предназначенные для использования в точках расширения, должны помечаться этими атрибутами. Данные атрибуты будут использованы при сортировке подправил внутри расширяемого правила (помеченного атрибутом Extensible).

^ ExpandableRule (Расширяемое правила)

PegGrammar позволяет создавать расширяемые правила. Как видно из примеров

Правило может расширятся:

Статически – в рамках текущего парсера.

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

Примеры:

[DynamicExpandable]

expr : int;expression : Expression; // правило допускающее расширение извене // статически расширяемое правило


[DynamicExpandable]

typeDeclaration : TypeDeclaration; // статически расширяемое правило // правило допускающее расширение извен

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

^ ExpandRule (расширяющее правило)

Для того чтобы расширить правило нужно описать новое правило и указать после его имени «is» и имя расширяемого правила.

Примеры описания набора расширений для правила typeDecl (определенного в предыдущем разделе):

classDecl is typeDecl = modifiers? "class"s identifier "{"s body "}"s ";"?

structDecl is typeDecl = modifiers? "struct"s identifier "{"s body "}"s ";"?

enumDecl is typeDecl = modifiers? "enum"s identifier "{"s body "}"s ";"?

delegateDecl is typeDecl = modifiers? "struct"s identifier "{"s body "}"s ";"?

^ ПриоритетыСила связывания


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

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

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

Примеры описания набора расширений для правила expr:

num is expr = ['0'..'9']+ s;

parentheses is expr = '('s expr ')'s;


negation is expr = '-'s expr : 30; // префиксное унарное выражение

maxFunction is expr = "max"s '('s expr ')'s; // постфиксное унарное выражение


// инфиксные бинарные выражения

sum is expr = expr : 10 '+'s expr : 10;

sub is expr = expr : 10 '-'s expr : 10;

mul is expr = expr : 20 '*'s expr : 20;

div is expr = expr : 20 '/'s expr : 20;

listConcat is expr = expr : 20 21 "::"s expr : 2120; // право-ассоциативный!


Обратите внимание на то, что здесь задействованыа приоритетысила связывания. Это выглядит как леворекурсивная грамматика. Однако это нечто большее, так как одновременно задаются приоритеты и ассоциативность. Ассоциативность задается как разность между приоритетомсилой связывания крайнего левого расширяемого правила и крайнего правого. Если разница отрицательнаяположительная, то выражение получается право-ассоциативным В приведенном выше примере оператор "::" является право-ассоциативным. Если попытаться распознать приведенным выше парсером следующее выражение:

1 :: 2 :: 3

то оно будет интерпретировано как:

1 :: (2 :: 3)

В то же время выражение:

1 + 2 + 3

будет распознано как:

(1 + 2) + 3

Для вычисления выражений ассоциативность не важна, но она важна при построении AST.

^ Top Down Operator Precedence + PEG

Для поддержки приоритетов PegGrammar комбинирует основной алгоритма (рекурсивный нисходящий разбор с откатами и частичной мемоизацией), и алгоритма Top Down Operator Precedence (TDOP) открытого Vaughan Pratt. Этот алгоритм так же иногда называют Pratt-парсером (по имени автора). TDOP алгоритм позволяет разбирать выражения основываясь на приоритетах операторов и допускает левую рекурсию.

В PegGrammar в качестве выражений может выступать любое расширяемое правило. TDOP подразумевает, что его входной поток состоит из токенов (т.е. рассчитан работу с отдельным лексером). Это проблема для PegGrammar, так как он является безлексерным. Так же TDOP не может откатываться в случае проблем при разборе очередного правила, что не совместимо с идеологией PEG. Чтобы обойти этуи проблемуы выделением лексем перекладывается на плечи PEG (т.е. основного алгоритма)пришлось серьезно переработать алгоритм TDOP. В сущьности от него осталась только идея использовать силу связывания для управления приоритетами и ассациотивностью. Все правила расширения некого расширяемого правила разбиваются на два множетва. Постфиксные это правила которые начинаются на расширяемое правило и префиксные. При вызове расширяемого правила ему передается сила связывания справа. Разбор происходит следующим образом: Сначала последовательно производится попытка разобрать префиксные правила. Результат разбора используется дальше. Если ни одно из правил не сработало то разбр считается не удачным и происходит откат всего правила. В случае успеха производится разбор постфиксных правил чья сила связывания слева больше чем сила связывания справа переданая правилу. Также разбираемому постфиксному правилу передается результат полученный на предыдущей итерации. Разбор постфиксных правил продолжается до тех пор пока все правила не постигнет неудача. В этом случае результатом рабора будет результат предыдущей итерации. TDOP оперирует расширяемыми правилами как выражениями и операторами. При этом приоритеты для правил в теле которых в начале и/или конце идут рекурсивные обращения к тому же расширяемому правилу определяются указанными величинами. В примере выше mul имеет левый и правый приоритет 20expr : Expr;, listConcat левый приоритет 20, а правый 21. Если приоритет не задан, или в начале/конце не идет ссылки на расширяемое правило, то приоритет автоматически считается равным нулю. Так для правила negation левый приоритет равен нулю, а правый 20, а для правил num и parentheses как правый, так и левый приоритеты равные нулю.

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

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

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

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

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

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

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

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

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

[PegGrammar(Options = EmitDebugSources, 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(GetText(digit))

}

private unaryMinus(_ : NToken, _ : NToken, se : int) : int

{

-se

}

...

}

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

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

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

simplExpr : int = num / parenthesesExpr / unaryMinus / parenthesesExprError / simplExprError;

...

private simplExpr(se : int) : int

{

se

}

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

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

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

Типы параметров могут иметь тип NToken или пользовательский тип.

NToken – описывает результат разбора правила, не имеющего обработчика, то есть такого, для которого не формируется какого-либо значения. Для результатов разбора таких правил можно узнать только позиции начала и конца фрагмента текста, разобранного по данному правилу, и сам текст.

В таблице 1 приведено описание алгоритма определения типа параметра в зависимости от типа подправила, с которым сопоставляется данный параметр.

Таблица 1. Типы параметров.

Тип правила (вырожденные случаи не рассматриваются)

Пример

Тип

Примечание

Приоритетный выбор

E1 / E2 / E3

T1

T1 – Тип первого правила (E1). При этом типы всех правил должны совпадать. *

Последовательность

E1 E2 E3

T1 * T2 * T3

Кортеж, в котором Tn – тип правила En (т.е. тип соответствующего по порядку правила). *

Предикат

!E или &E




Параметр не объявляется.

Цикл

E* или E+

SCG.List[T]**

T – Тип описанный при декларации правила E. *

Необязательное правило

E?

option[T]

T – Тип описанный при декларации правила E. *

Ссылка на правило

E

T

T – Тип описанный при декларации правила E. *

*Если правило E не имеет в своем описании указания типа, то для типа параметра используется NToken. Обратите внимание, что NToken используется не в качестве параметра типа, а используется для указания всего типа параметра. Так происходит потому, что для правил, не имеющих обработчиков, можно получить информацию только о том, с каким участком исходной строки оно сопоставилось.

**^ SCG = System.Collections.Generic.

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

Для правила:

num : int = digit spaces;

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

private num(digit : NToken, _ : NToken) : int

{

int.Parse(GetText(digit))

}

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

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

Для правила:

unaryMinus : int = '-' spaces simplExpr;

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

private unaryMinus(_ : NToken, _ : NToken, se : int) : int

{

-se

}

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

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

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

Обработчик unaryMinus просто инвертирует знак этого значения и возвращает результат в качестве своего возвращаемого значения.

^ Игнорирование значения возвращаемого правилом

Для правила может быть задан тип «void». Это дает указание PegGrammar-у всегда игнорироать возвращаемое значение такого правила, что в свою очередь позволяет уменьшить количество неиспользуемых параметров в обработчиках и ускорить генерируемый парсер.

Например, приведенный выше код можно изменить следующим образом:

[PegGrammar(Options = EmitDebugSources, start,

grammar

{

any = ['\u0000'..'\uFFFF'];

digit = ['0'..'9']+;

spaces : void = ' '*;

num : int = digit spaces;

unaryMinus : int = '-' spaces simplExpr;

...

}

})]

public class CalcParser

{

private num(digit : NToken) : int

{

int.Parse(GetText(digit))

}

private unaryMinus(_minus : NToken, se : int) : int

{

-se

}

...

}

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

^ Параметры для подправил типа «цикл»

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

Пример:

mulOrDiv : int = simplExpr (('*' / '/') spaces simplExpr)*;

...

private mulOrDiv(se : int, lst : List[NToken * NToken * int]) : int

{

...

}

Обратите внимание на то, что если у правила «spaces» указан тип void, то кортеж будет состоять из двух элементов (NToken * int), а не из трех.

^ Параметры для необязательных подправил

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

Пример:

mainRule : int = sumOrSub inputError?;

...

private mainRule(se : int, _ : option[int]) : int

{

se

}

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

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

Предикаты

Для предикатов не требуется задавать параметры, так как они не возвращают значения. Предикаты никогда не изменяют позицию разбора строки. Их цель – всего лишь ответить на вопрос, может ли (или не может, для предиката «!») в текущей позиции быть разобрано некоторое правило. В принципе, всегда можно написать грамматику без применения предикатов, но зачастую применение предикатов намного удобнее (делает грамматику проще).

Например, предикаты удобно использовать для распознавания комментариев языка C:

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

Данное правило распознает подстроку «/*» и затем ноль или более любых символов, но только если этот символ не начинает последовательность «*/» (что указывается посредствам предиката «!"*/"»). Если бы перед ссылкой на правило any не стоял предикат «!"*/"», то оно разобрало бы любые символы, включая «*», за которым следует «/». Это правило «не заметило» бы окончания комментария и не остановилось бы, пока не дошло до конца файла. Предикат «!» сигнализирует о неудаче, если идущее после него правило успешно сопоставляется. Это приводит к тому, что когда в текущей позиции встречается последовательность символов «*/», то выполнение правила «(!"*/" any)» заканчивается неудачей, что приводит к остановке цикла (описываемого правилом «*»). Далее распознается «"*/"», что приводит к успешному разбору всего правила delimitedComment.

Еще одним примером того, где помогают предикаты, является разбор идентификаторов. Например, вот так может выглядеть правило разбора идентификатора в C#:

identifier : Identifier = !keyword "@"? identifierBody s;

Предикат «!keyword» нужен, так как любое ключевое слово также удовлетворяет правилам разбора идентификаторов. Предикат предотвращает разбор ключевых слов по правилу идентификаторов.

Правило keyword также должно содержать в себе предикат:

keyword = ("abstract" / "as" / "base" / "bool" / "break"

/ "byte" / "case" / "catch" / "char" / "checked"

/ "class" / "const" / "continue" / "decimal" / "default"

/ "delegate" / "do" / "double" / "else" / "enum"

/ "event" / "explicit" / "extern" / "false" / "finally"

/ "fixed" / "float" / "for" / "foreach" / "goto"

/ "if" / "implicit" / "in" / "int" / "interface"

/ "internal" / "is" / "lock" / "long" / "namespace"

/ "new" / "null" / "object" / "operator" / "out"

/ "override" / "params" / "private" / "protected" / "public"

/ "readonly" / "ref" / "return" / "sbyte" / "sealed"

/ "short" / "sizeof" / "stackalloc" / "static" / "string"

/ "struct" / "switch" / "this" / "throw" / "true"

/ "try" / "typeof" / "uint" / "ulong" / "unchecked"

/ "unsafe" / "ushort" / "using" / "virtual" / "void"

/ "volatile" / "while" ) !identifierPartCharacters;

Дело в том, что в коде может встретиться идентификатор вроде abstractFactory, то есть содержащий в качестве префикса имя одного из ключевых полей. Чтобы парсер не распознал такой префикс как ключевое слово, в правило «keyword» нужно ввести предикат, который проверит, что за ключевым