Макрос PegGrammar

Вид материала

Документы

Содержание SCG = System.Collections.Generic. Игнорирование значения возвращаемого правилом Параметры для подправил типа «цикл» Параметры для необязательных подправил Scope (области) Особенности использования PegGrammar Левая рекурсия Левая факторизация

Подобный материал:

• План Введение. Начало пути. Редактирование, удаление, переименование и назначение макросов, 283.36kb.
• Программирование действий– Макросы Функция, 304.28kb.
• Русская доктрина андрей Кобяков Виталий Аверьянов Владимир Кучеренко (Максим Калашников), 11986.64kb.
• Тема урока: Создание макросов в Microsoft Excel, 33.61kb.
• Шаг 1 Первый макрос, 909.7kb.
• Этот макрос написан на языке Visual Basic для программы Microsoft Word. Он предназначен, 28.77kb.

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» нужно ввести предикат, который проверит, что за ключевым словом не следует символ, который может быть использован в теле идентификатора.

Scope (области)

PEG не годится для распознавания грамматик, которые не могут в общем случае быть описаны с помощью контекстно-свободных грамматик. Например, чтобы понять является ли некоторое выражение в C++ объявлением переменной, нужно знать, является ли некоторый идентификатор типом. В C++ (как и его предшественнике C) требуется, чтобы все типы были объявлены перед использованием. Это может быть осуществлено или физическим размещением типов (или typedef) перед их использованием или описанием преддеклараций (например, «class A;») перед первым использованием типов. Таким образом, чтобы разобрать примитивную конструкцию C++ вроде «X Y();» нужно знать, какие типы были объявлены перед ней.

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

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

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

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

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

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

Первый должен иметь сигнатуру:

SomeScopeBegin() : void

или:

SomeScopeBegin() : bool

А второй сигнатуру:

SomeScopeEnd(isOk : bool) : void

или:

SomeScopeEnd(isOk : bool) : bool

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

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

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

Разбираемая строка должна быть загружена в память

Особенностью данной реализации является то, что разбираемая строка должна быть загружена в память (быть представлена в виде типа System.String). Это требование возникло вследствие того, что PEG поддерживает откаты (за счет использования операторов приоритетного выбора) и неограниченное заглядывание вперед (за счет использования предикатов). Это приводит к тому, что самым эффективным способом организации работы со строкой становится индексация (или использование указателей, если язык реализации таковые поддерживает). Позиция (в парсере генерируемом PegGrammar) описывается целым числом (int). При этом откат позиции сводится к изменению этого числа. Этим же числом определяется и информация о том, что при разборе некоторого правила парсер потерпел неудачу. При этом значение позиции становится отрицательным (равным -1). Использование только одного целого числа, как для описания позиции, так и для идентификации успеха или неудачи разбора правила позволяет сделать парсер таким быстрым.

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

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

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

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

Леворекурсивной грамматикой называют грамматику, которая имеет леворекурсивные правила (прямые или нет). Например, следующая грамматика имеет левую рекурсию:

X = X '+' 1 / 1

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

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

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

X = 1 ('+' 1)*

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

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

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

Из школьной алгебры мы знаем, что выражение:

3 * x + 3 * y

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

3 * (x + y)

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

A = X Y / X Z

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

A = X (Y / Z)

Эти правила будут разбирать одну и ту же грамматику, но во втором случае правило X будет разобрано только один раз.

На самом деле, правила показанные выше будут мемоизированны, так как PegGrammar поддерживает мемоизацию для последнего использования правила, но в более сложных случаях (например, в случае грамматики «X X Y / X X Z»), могут появиться откаты, которые могут привести к «проседанию» производительности.

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

Оптимизации

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

Кроме того PegGrammar генерирует довольно неплохой (с точки зрения производительности) код, состоящий в основном из if и присвоения одной целочисленной переменной (позиции парсинга). В генерируемом коде нет замыканий, классов и прочих высокоуровневых штуковин. А релиз-версии вместо структурных условных операторов используются goto. Все это положительно влияет на производительность парсера.

Мемоизация результатов разбора правил для одной позиции в исходном тексте позволяет избежать многократного разбора одних и тех же правил. Например, если вы занимаетесь разбором C#-подобного языка программирования, у вас могут быть подобные правила:

classRule = customAttribut? modifiers? "class"S ...;

structRule = customAttribut? modifiers? "struct"S ...;

enumRule = customAttribut? modifiers? "enum"S ...;

method = customAttribut? modifiers? ...;

property = customAttribut? modifiers? ...;


cmassMember = classRule / structRule / enumRule / method / property;

то вам не нужно производить левую факторизацию этих правил и создавать нечто вроде

cmassMember = customAttribut? modifiers? ("class"S / "struct"S / "enum"S / ...) ...

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

Кстати, наши эксперименты показали, что полная мемоизация, в соответствии с алгоритмом Packrat, хотя в теории и дает линейную скорость парсинга, но на практике неприменима. Дело в том, что Packrat приводит к высоким затратам на мемоизацию и проверку мемоизированного состояния. Объем памяти, требуемый для мемоизации состояния, равен произведению числа правил в грамматике на длину разбираемой строки и на размер структур данных, используемых для мемоизации. Как показала практика генератора парсеров «Rats!», самыми сильными оптимизациями в нем оказались те, что устраняли излишнюю мемоизацию и уменьшали объем таблицы мемоизации, с которой алгоритм работает в отдельные моменты своей работы.

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

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

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

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

Также на скорость разбора благотворно действует компиляция получаемого парсера в «Release» (вследствие инлайнинга методов и других оптимизаций, производимых jit-компилятором .NET).

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

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