Parsing Tutorial

Введение в разбор строк (применительно к СП).

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

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

===
Прежде чем начать, необходимо знать некоторые основные понятия: язык, алфавит, терминалы/нетерминалы, грамматика (регулярная и контекстно-свободная, выше не понадобятся), порождение (a.k.a. выведение). Лично мне понравились вот эти две статьи: http://habrahabr.ru/post/177109 http://habrahabr.ru/post/177701 , но подойдет любое пособие по теории формальных языков, их тысячи. Необязательно понимать все, достаточно лишь перечисленных выше определений.

===
Далее мы будем писать грамматики в расширенных БНФ (формах Бэкуса-Наура). "Расширяются" они, вводя новые обозначения:

# Комментарий.
A ::= B*               # A порождает любое количество B (включая ноль).
A ::= B+               # A порождает один или более B.
A ::= B?               # A порождает ноль или один B.
A ::= B (C* | D+) C? E # Все это можно комбинировать, используя скобки.

===
Дерево разбора - дерево, показывающее, из каких символов (терминальных и нетерминальных) состоит строка. Например, пусть есть грамматика:

number ::= digit+ # Число - это одна или более десятичных цифр.
innerList ::= '[' (number (',' number)*)? ']' # Список - это последовательность чисел, разделенных запятыми (возможно, пустая), заключенная в квадратные скобки.
outerList ::= '{' innerList* '}' # Внешний список - это последовательность внутренних списков, заключенная в фигурные скобки.

Тогда строке "{[42,85,2][32][012,3][]}" будет соответствовать дерево разбора на рис. 1.

Абстрактное синтаксическое дерево (abstract syntax tree, AST) - дерево, очень похожее на дерево разбора, из которого удалено "все лишнее", т. е. те символы (в основном, терминальные), которые нужны только для правильного разбора строки и не несущие иной полезной нагрузки. AST для той же строки представлено на рис. 2.

===
Фактически, алгоритм решения любой строковой задачи можно записать следующим образом:
1. Составить по словесному описанию грамматику.
2. Перевести грамматику в код, который по строке строит AST.
3. Выполнить над AST требуемые в задаче операции и вывести ответ.

Возьмем какую-нибудь несложную задачу и проделаем алгоритм над ней. Например:

"""
В единственной строке задано арифметическое выражение с целыми числами, бинарными +-*/, унарными +- и скобками (), также в строке может содержаться произвольное количество пробелов. Вычислить и вывести результат. Если выражение некорректно, вывести "SyntaxError". Если происходит деление на ноль, вывести "ZeroDivisionError". Все числа (включая промежуточные результаты) целые, по модулю строго меньше 2**31. Деление целочисленное (дробная часть отбрасывается).
"""

Пара пояснений:
Некоторый оператор (назовем его @) называется бинарным, если он принимает два операнда (по обе стороны от него): X @ Y.
Оператор ! называется унарным, если у него только один операнд. При этом унарные операторы могут быть префиксными (!X) или постфиксными (X!).
Оператор @ обладает более высоким приоритетом, чем ^, если X ^ Y @ Z == X ^ (Y @ Z).
Оператор @ называется левоассоциативным, если X @ Y @ Z == (X @ Y) @ Z (вычисляется слева направо), или правоассоциативным, если X @ Y @ Z == X @ (Y @ Z) (справа налево).

В этой задаче у нас есть только унарные префиксные и бинарные левоассоциативные. Пусть у бинарных "+-" будет приоритет, равный 1, у "*/" - 2, а у унарных "+-" - 3 (как правило, унарные операторы обладают наивысшим приоритетом).

===
Итак, пункт первый - составление грамматики. Первым, прямолинейным решением могло бы быть что-нибудь такое (забудем пока про пробелы, позже будет показано, что с ними делать):

expr ::= number
       | expr '+' expr
       | expr '-' expr
       | expr '*' expr
       | expr '/' expr
       | '+' expr
       | '-' expr
       | '(' expr ')'

number ::= digit+

Т. е. выражение - это либо одиночное число, либо сумма двух выражений, либо разность и т. д. Проблема в том, что такая грамматика неоднозначна, т. е. по одной строке может быть построено несколько различных деревьев разбора (рис. 3 и 4 для строки "1+2*3"). Проще говоря, наша грамматика никак не учитывает приоритет и ассоциативность.

Видоизменим ее следующим образом:

expr ::= prio1
prio1 ::= prio2 ('+' prio2 | '-' prio2)*
prio2 ::= prio3 ('*' prio3 | '/' prio3)*
prio3 ::= ('+' | '-')* prio4
prio4 ::= number | '(' prio1 ')'
number ::= digit+

Здесь группе операций с одинаковым приоритетом соответствует один нетерминал. Чтобы стало понятней, приведу пару примеров: "1+2*3" (рис. 5), "(2+1--4+5/+2)+---+30" (рис. 6).

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

===
Если кто-то еще помнит, целью разбора строки является получение абстрактного синтаксического дерева (AST) и работа с ним. Деревья же разбора строятся лишь мысленно и нужны для лучшего понимания происходящего. Самое время подумать, какие типы узлов может содержать AST:

1. Number. Возвращает одно фиксированное число.
2. Add. Складывает значения двух своих потомков.
3. Sub. Вычитает из значения левого потомка значение правого.
4. Mul. Перемножает значения потомков.
5. Div. Делит значение левого потомка на значение правого.
6. Pos. (Унарный плюс). Возвращает значение единственного потомка неизменным.
7. Neg. (Унарный минус). Возвращает значение единственного потомка, изменив знак.

AST последних двух примеров изображены на рис. 7 и 8. Имея на руках такое дерево, для решения задачи достаточно запросить значение в корне - ответ рекурсивно посчитается и вернется. Здорово, правда? Осталось только понять, как по имеющейся грамматике (строки 69 - 74 этого файла) и типам узлов (83 - 89) построить AST.

Использовать для этого мы будем изумительно простой алгоритм, который называется "метод рекурсивного спуска". Далее прошу читать комментарии к коду: http://ideone.com/nZVUmo

===
Вот и все, что я хотел рассказать по поводу разбора строк. Еще раз, в строке 32 алгоритм, который подойдет для решения 99% олимпиадных задач на строки.

Буду рад выслушать вопросы и ответить на них.

P. S. Рисунки в формате DOT (GraphViz): http://pastebin.com/rQsyu8Bw