Фио: Чистяков Владислав Юрьевич; e mail
Скачать 386.37 Kb.
|
Макрос PegGrammar
Macro PegGrammar
Назначение 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-грамматика 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 описывает минимальную грамматическую еденицу которую можно пропустить за раз. ^ Rule (Правило) Задает именованное правило разбора. Для именованного правила можно (и нужно) определить метод-обработчик, т.е. метод, который будет вызываться каждый раз, когда производится успешный разбор соответствующего правила. Пример: Sequence = PredicateRule+; ^ E1 / E2 / ... / En Задает последовательность подправил, по которым поочередно производится попытка разбора строки в текущей позиции. Если строка в текущей позиции успешно распознается по одному из подправил, остальные подправила игнорируются, а позиция смещается на число распознанных символов. При этом OrderedChoice сигнализирует об успехе разбора. Если разбор по текущему подправилу терпит неудачу, производится откат позиции разбора в позицию, предшествующую начала разбора данного подправила, и производится попытка разобрать строку по следующему подправилу, и так до успешного распознавания или до исчерпания списка подправил (что расценивается как неудача разбора всего оператора приоритетного выбора). Как можно видеть из грамматики, OrderedChoice может иметь от одного до неограниченного количества подправил. Таким образом, последовательность (Sequence) является вырожденным случаем OrderedChoice. Пример: RuleName / Range / Char / String ^ E1 E2 ... En Последовательность из одного (вырожденный случай) или более PredicateRule. Правила разбираются по очереди. Если разбор одного из правил терпит неудачу, разбор последовательности также считается неудачным, что приводит к откату разбора текущего правила. Пример: Char ".." Char ScopeName '{' ScopedRule '}' ^ &E !E Состоит из необязательного (в вырожденном случае) предиката ('!' или '&') и идущего за ним CardinalityRule. Предикат делает идущее за ним подправило предикативным (эфемерным). Такое правило распознается только с целью получения ответа на вопрос, можно ли продолжать дальнейший разбор. Информация о разборе предикативного подправила теряется, а текущая позиция не изменяется. & – позитивный предикат. Возвращает успех, если идущее за ним правило успешно распознано, и неудачу в обратном случае. ! – негативный предикат. Возвращает успех, если идущее за ним правило потерпело неудачу при разборе, и неудачу в случае успешного разбора. Пример: delimitedComment = "/*" (!"*/" any)* "*/"; Данный пример разбирает комментарий в стиле «C» – /* комментарий */. Здесь используется предикат «!», чтобы убедиться, что разбираемый символ не является частью последовательности «*/», закрывающей комментарий. ^ E* E+ E? Состоит из простого правила и необязательной управляющей конструкции. Всего поддерживается три управляющих конструкции:
Примеры: PredicateRule+ ('/' Sequence)* ReturnType? ^ Состоит из задания области (Scope), литерального выражения, диапазонов символов, ссылки на другое (именованное) правило, подправила любого типа, заключенного в скобки, или из пустого правила (не разбирающего ничего). Примеры: PredicateRule Sequence ('?' / '+' / '*') ".." ['\u0000'..'\uFFFF'] 'Z' ^ Список диапазонов символов или сокращений имен Unicode-категории. Примеры: ['0'..'9'] ['\u0000'..'\uFFFF'] ['A'..'Z', 'a' .. 'z', '\u037F' .. '\u1FFF'] [Lu, Ll, Lt, Lm, Lo, Nl] ScopeName { Type* } ^ Позволяет описать один символ. Например: 't' Строковый литерал Задает последовательность символов. Например: "try" Этот пример эквивалентен следующему: 't' 'r' 'y' ^ Атрибуты позволяют задать дополнительную метаинформацию для именованного правила (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). |
Добавить документ в свой блог или на сайт
Похожие:
 | Автор: фио: Чистяков Владислав Юрьевич; Номер профиля на rsdn ru: 73; Место работы: ООО «к-пресс»; Должность: Директор; e-mail | | Автор: фио: Чистяков Владислав Юрьевич; Номер профиля на rsdn ru: 73; Место работы: ООО «к-пресс»; Должность: Директор; e-mail |
| Автор: фио: Чистяков Владислав Юрьевич; Номер профиля на rsdn ru: 73; Место работы: ООО «к-пресс»; Должность: Директор; e-mail | | Автор: фио: Чистяков Владислав Юрьевич; Номер профиля на rsdn ru: 73; Место работы: ООО «к-пресс»; Должность: Директор |
| Направляющая организация (адрес, фио руководителя, контактный телефон, e-mail), если таковые имеются) | | Электронная почта (E-mail) является самой популярной и распространенной службой Internet в нашей стране |
| Владислав Окладников-художник-профессионал, мастер по искусственному камню, гипсу, бетону, чеканке, гнутому металлу, резчик по дереву.... | | Михаил Юрьевич Лермонтов великий русский поэт. Автор романтической драмы "Маскарад", знаменитых стихотворений "Бородино", "Смерть... |
| Конкурс исследовательских краеведческих работ Всероссийского туристско-краеведческого движения «Отечество» | | Фио, организации, должность, научная степень, звание, темы выступления, точные координаты для связи, включая адрес, домашний и рабочий... |