Сообщений 59    Оценка 880        Оценить  
Система Orphus

Макрос PegGrammar

Автор: Чистяков Владислав Юрьевич
Источник: RSDN Magazine #2-2010
Опубликовано: 07.06.2011
Исправлено: 10.12.2016
Версия текста: 1.0
Назначение
PEG
Грамматика PEG
Семантика PEG
Rule (Правило)
OrderedChoice (Приоритетный выбор)
Sequence (последовательность)
PredicateRule (предикатное правило)
CardinalityRule (управляющее правило)
SimpleRule (простое правило)
Ranges (диапазоны)
Символьный литерал
Строковый литерал
Attributes (Атрибуты)
ExpandableRule (Расширяемое правила)
ExpandRule (расширяющее правило)
Сила связывания
Top Down Operator Precedence + PEG
Семантические действия
Методы обработчики
Параметры методов-обработчиков
Предикаты
Scope (области)
Особенности использования PegGrammar
Разбираемая строка должна быть загружена в память
Левая рекурсия
Левая факторизация
Оптимизации
Недоработки
Достоинства 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
    {
      Правила
    }
  )]
  publicclass 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;
Precedence         = ['0' .. '9']+;

// Общие конструкции
ReturnType        = ':' NemerleType
RuleName          = Identifier;
OperatorRuleName  = Identifier;
Attribute         = "Inline" 
                  / "InlineAllSubrules"
                  / "Extensible" 
                  / FailureRecovery
                  / '%''(' MethodHandler ',' SkipRule ')' 
                  / '<' RuleName
                  / '>' RuleName;
Attributes        = '[' Attribute (',' Attribute)* ']'
MethodHandler     = Identifier;
SkipRule          = OrderedChoice;
FailureRecovery   = "FailureRecovery"'(' MethodHandler ',' StopRule ',' SkipRule ')';

// «Область» позволяющая организовать транзакции
ScopedRule        = OrderedChoice;
ScopeName         = Identifier;
Scope             = ScopeName '{' ScopedRule '}';

Здесь:

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?

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

Примеры:

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

FailureRecovery – позволяет задать «точку восстановления» после обнаруженной парсером ошибки. Если в грамматике не заданы точки восстановления или точки отсечения (о них см. ниже), то при обнаружении первой ошибки парсер прекращает разбор (так как все правила откатываются) и сообщает об ошибке. 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 – этот атрибут используется совместно с атрибутом Extensible для задания относительного приоритета правил. Правила, предназначенные для использования в точках расширения, должны помечаться этими атрибутами. Данные атрибуты будут использованы при сортировке подправил внутри расширяемого правила (помеченного атрибутом Extensible).

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

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

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

Примеры:

[DynamicExpandable]
expr     : int;             // правило допускающее расширение извне 

typeDecl : 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 : 21 "::"s expr : 20; // право-ассоциативный!

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

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. Чтобы обойти эти проблемы пришлось серьезно переработать алгоритм TDOP. В сущьности от него осталась только идея использовать силу связывания для управления приоритетами и ассациотивностью. Все правила расширения некого расширяемого правила разбиваются на два множетва. Постфиксные это правила которые начинаются на расширяемое правило и префиксные. При вызове расширяемого правила ему передается сила связывания справа. Разбор происходит следующим образом: Сначала последовательно производится попытка разобрать префиксные правила. Результат разбора используется дальше. Если ни одно из правил не сработало то разбр считается не удачным и происходит откат всего правила. В случае успеха производится разбор постфиксных правил чья сила связывания слева больше чем сила связывания справа переданая правилу. Также разбираемому постфиксному правилу передается результат полученный на предыдущей итерации. Разбор постфиксных правил продолжается до тех пор пока все правила не постигнет неудача. В этом случае результатом рабора будет результат предыдущей итерации. Если приоритет не задан, или в начале/конце не идет ссылки на расширяемое правило, то приоритет автоматически считается равным нулю. Так для правила 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;
  ...
 }
})]
publicclass 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;
  ...
 }
})]
publicclass 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!», самыми сильными оптимизациями в нем оказались те, что устраняли излишнюю мемоизацию и уменьшали объем таблицы мемоизации, с которой алгоритм работает в отдельные моменты своей работы.

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

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

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

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

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

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

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

Недоработки

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

Данные недоработки, кроме последнего пункта, не так сложно устранить. Буквально перед публикацией этой статьи я был вынужден удалить несколько пунктов из этого списка, так как соответствующие недоработки были устранены в PegGrammar.

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

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

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

Достоинства PegGrammar


Рисунок 1. Отображение ошибок в граматике по мере редактирования (в реальном времени).


Рисунок 2. Переход к определению правила или к методу-обработчику.

К главным достоинствам PegGrammar можно отнести:

  1. «Шаговая доступность». Подключить PegGrammar к проекту не сложнее, чем использовать библиотеку регулярных выражений.
  2. Высокая скорость работы (при компиляции в Release). По имеющимся данным PegGrammar обгоняет не только многие парсеры полученные с помощью других генераторов парсеров, но и некоторые рукописные парсеры авторы которых выставляют скорость как одно из главных достоинств своих продуктов. Так реализация парсера JSON созданная с помощью PegGrammar оказалась примерно на треть быстрее аналогичного парсера из Json.NET.
  3. Относительно легкая отладка полученного парсера (по сравнению с парсерами, использующими конечные автоматы).
  4. Отсутствие разделения на парсер и лексический анализатор. Вся грамматика (или ее часть) задается в одном месте и использует один и тот же формализм – PEG.
  5. Использование PEG-нотации. PEG очень выразителен, и легче понимается людьми (особенно работавшими с регулярными выражениями), так как описывает парсер языка, а не грамматику.
  6. PegGrammar обеспечивает удобные, быстрые и качественные средства обеспечения восстановления после обнаружения ошибок.
  7. Благодаря тому, что PegGrammar предоставляет концепцию областей видимости (Scopes), он позволяет разбирать ряд контекстно-зависимых грамматик вроде грамматик языков C, C++ или Nemerle.
  8. Высокая декларативность, обеспечиваемая отделением грамматики от семантических действий, упрощает разработку и сопровождение грамматик.
  9. Поддержка IDE. На сегодня в VS доступен (через контекстное меню) переход к определению правила, переход с правил к методам-обработчикам и обратно. Кроме того, доступны обычные для любого кода Nemerle свертка (folding) регионов и разнесение методов-обработчиков по разным файлам (за счет использования partial-классов). Это позволяет удобно структурировать правила и методы-обработчики и легко находить их. Также в IDE доступны сообщения об ошибках в грамматике, сообщения о несоответствии сигнатур обработчиков правил самим правилам. Все сообщения об ошибках выводятся как в консоль при компиляции, так и доступны в виде всплывающих подсказок в соответствующих местах грамматики. Кроме того, все генерируемые публичные методы классов, реализующих парсер, становятся доступны через IntelliSense, что позволяет писать использующий их код так, как будто парсер уже существует.
  10. Динамическая расширяемость. Точки расширения позволяют контролируемо и без значительной потери производительности динамически расширять грамматику разбираемого языка. Это позволяет использовать PegGrammar для разбора языков с расширяемым синтаксисом (например, Nemerle). Собственно, мы планируем использовать технологии, отработанные в PegGrammar (включая код), для реализации новой версии Nemerle, которая позволит снять большую часть ограничений на расширение синтаксиса.
  11. Тот факт, что PegGrammar реализован в виде макроса Nemerle, позволил реализовать ряд возможностей, отсутствующих в традиционных генераторах парсеров, реализованных в виде внешних DSL («ANTLR», «Rats!», Coco/R и т.п.). Так, PegGrammar производит анализ методов-обработчиков, сравнение типов их аргументов и возвращаемого значения с правилами. Это позволяет: а) выявлять несоответствие между методами-обработчиками и соответствующими им правилами грамматики, б) генерировать развернутые сообщения об ошибках и указывать, какие сигнатуры должны быть у методов-обработчиков.
  12. Использование PEG в качестве формализма и метод рекурсивного парсера с откатами и частичной мемоизацией позволяет создавать парсеры для широкого класса языков, в который входят практически все современные языки программирования, а также такие языки как HTML, XML и TeX, т.е. компьютерных языков и форматов, не относящихся к языкам программирования. Наличие в PEG предикатов и практически неограниченных (но строго формализованных) откатов позволяет создавать парсеры практически любых компьютерных языков без дополнительных ухищрений (не прибегая к ручному разбору).
  13. То, что семантические действия отделены от грамматик (вынесены в методы-обработчики), упрощает работу с грамматикой и ее развитие.
  14. PegGrammar полностью поддерживает Unicode. Вы можете задавать символьные классы в виде Unicode-категорий, использовать Unicode-литералы (строки и символы), а так же использовать Unicode в самой грамматике.

Литература

  1. http://en.wikipedia.org/wiki/Parsing_expression_grammar
  2. http://nemerle.org/Macros
  3. Robert Grimm, New York University, Better Extensibility through Modular Syntax
  4. http://pdos.csail.mit.edu/~baford/packrat/
  5. Sérgio Medeiros, Roberto Ierusalimschy, Department of Computer Science PUC-Rio, Rio de Janeiro, Brazil, A Parsing Machine for PEGs


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