Фио: Чистяков Владислав Юрьевич; e mail




Скачать 362.91 Kb.
НазваниеФио: Чистяков Владислав Юрьевич; e mail
страница1/4
Дата публикации27.05.2014
Размер362.91 Kb.
ТипДокументы
literature-edu.ru > Авто-обзор > Документы
  1   2   3   4
Макрос PegGrammar

Версия: 1.0

Дата: 18.02.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

Дата: 18.02.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(СтартовоеПравило,

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;

Attribute = "Inline"

/ "InlineAllSubrules"

/ "Extensible"

/ FailureRecovery

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

/ '<' RuleName

/ '>' RuleName

/ "==" RuleName;

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

MethodHandler = Identifier;

SkipRule = OrderedChoice;

FailureRecovery = "FailureRecovery" '(' MethodHandler ',' SkipRule ')';
// Область позволяющая организовать транцакции

ScopedRule = OrderedChoice;

ScopeName = Identifier;

Scope = ScopeName '{' ScopedRule '}';
// Восттановаление после обнаружения ошибок
SkipRule = ScopedRule;

MethodHandler = Identifier;

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

Здесь:

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

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

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

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

Семантика 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-элемент, содержащий информацию об ошибке), а также правило, позволяющее пропустить некорректные данные во входной строке, что позволяет парсеру продолжить разбор строки, даже если она частично не соответствует грамматике разбираемого языка (содержит ошибки). Это позволяет выявлять несколько ошибок сразу.

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

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

Добавить документ в свой блог или на сайт

Похожие:

Фио: Чистяков Владислав Юрьевич; e mail iconЛитература русского зарубежья 1,2 доц. Чистяков А. В. 625

Фио: Чистяков Владислав Юрьевич; e mail iconНа тему: «Приглашение на бал» Выполнили: ученики 7 «А» Е. Р. Каримова
Челябинск, Свердловский проспект, 24 телефон/факс 791-64-21, e-mail: chel137@mail ru

Фио: Чистяков Владислав Юрьевич; e mail icon678230, Верхневилюйский улус, с. Верхневилюйск, ул. Героя Васильева,...
«Модернизация базовых общеобразовательных учреждений путем организации в них дистанционного обучения»

Фио: Чистяков Владислав Юрьевич; e mail iconE-mail: phoenixgroup3@mail ru Экскурсии и активные выходные барнаул в лицах
Образованные и состоятельные горные инженеры завели отнюдь не провинциальный уклад жизни. Просвещённое руководство строили не только...

Фио: Чистяков Владислав Юрьевич; e mail iconValeev d@mail ru yakovenko alexey@mail ru Раскрытие корпоративной информации через сеть интернет
Данная тенденция проявляется в использовании икт в корпоративном управлении, вопросах раскрытия информации, осуществления межбанковских...

Фио: Чистяков Владислав Юрьевич; e mail iconФио учителя, подготовившего участника

Фио: Чистяков Владислав Юрьевич; e mail iconМбдоу «центр развития ребёнка детский сад №50» № фио

Фио: Чистяков Владислав Юрьевич; e mail iconАрхетипическое Исследование Сновидений Владислав Лебедько Евгений...
«Самопознание составляет свою собственную цель и не имеет конца… Не существует иной цели, кроме самого акта созидания души, поэтому...

Фио: Чистяков Владислав Юрьевич; e mail iconФио протокол №1 от «29»
Настоящая рабочая программа по литературе для 11 а,б классов средней (полной) общеобразовательной школы создана на основе

Фио: Чистяков Владислав Юрьевич; e mail iconШаблоны для сочинения
В тексте автор рассказывает о Таким образом (фио писателя или публициста) поднимает проблему

Литература


При копировании материала укажите ссылку © 2015
контакты
literature-edu.ru
Поиск на сайте

Главная страница  Литература  Доклады  Рефераты  Курсовая работа  Лекции