Парсер строки: Подход к синтаксическому анализу через концепцию нарезания строки / Хабр

Парсеры, обработка текста. Просто о сложном. CFG, BNF, LL(k), LR(k), PEG и другие страшные слова

Наверное, каждому программисту приходилось сталкиваться с задачами вида «прочитать что-то в формате А и произвести с ним некие манипуляции». Будь то json, логи nginx, cfg, sql, yaml, csv или что-то еще. Хорошо, когда можно воспользоваться библиотекой, однако, по разным причинам, это удается не всегда. Тогда и встает вопрос создания собственного парсера для заданного формата. И это, как говорят англичане, часто оказывается PITA (болью в …). В этой статье я постараюсь облегчить эту боль. Кому интересно, добро пожаловать.

Введение

Итак, вопрос, о чём же конкретно эта статья? Здесь я постараюсь помочь читателю с наименьшими потерями выходить из ситуации, когда надо разобрать какой-то текстовый формат, а библиотекой воспользоваться не получится. То есть решать абсолютно конкретную задачу общими средствами.

Сразу оговорюсь, тема сама по себе мало того, что ОЧЕНЬ непростая, так еще и до невозможности обширная и все охватить в рамках одной статьи просто не получится. Поэтому я начну от общего и буду переходить к частному, конкретно в этой статье давая скорее обзор инструментария (который, однако, может использоваться для решения вполне конкретных задач парсинга), чем погружаться вглубь концепций. Возможно, если читатели будут заинтересованы, статья превратится в цикл, в котором я могу раскрыть какие-то конкретные вопросы более подробно.

Написать её я решил потому, что имеющаяся по теме информация разрознена и зачастую не полна, на русском источников вообще очень мало, а те что есть, подразумевают достаточно приличное знакомство читателя с весьма специфической математикой. Поэтому, чтобы далекий от темы читатель не испытывал боль от сознания своей (мнимой) неполноценности, я и решил попытаться описать эту тему максимально просто.

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

Основные понятия

Перед разговором по теме стоит определиться с основными понятиями, чтобы не было разночтений. Это глоссарий данной статьи. Он может совпадать с общепринятой терминологией, но вообще говоря, не обязан, поскольку показывает картину, формирующуюся в голове автора.
Итак:

• входной символьный поток (далее входной поток или поток) — поток символов для разбора, подаваемый на вход парсера
• parser/парсер (разборщик, анализатор) — программа, принимающая входной поток и преобразующая его в AST и/или позволяющая привязать исполняемые функции к элементам грамматики
• AST(Abstract Syntax Tree)/АСД(Абстрактное синтаксическое дерево) (выходная структура данных) — Структура объектов, представляющая иерархию нетерминальных сущностей грамматики разбираемого потока и составляющих их терминалов. Например, алгебраический поток (1 + 2) + 3 можно представить в виде ВЫРАЖЕНИЕ(ВЫРАЖЕНИЕ(ЧИСЛО(1) ОПЕРАТОР(+) ЧИСЛО(2)) ОПЕРАТОР(+) ЧИСЛО(3)). Как правило, потом это дерево как-то обрабатывается клиентом парсера для получения результатов (например, подсчета ответа данного выражения)
• CFG(Context-free grammar)/КСГ(Контекстно-свободная грамматика) — вид наиболее распространенной грамматики, используемый для описания входящего потока символов для парсера (не только для этого, разумеется). Характеризуется тем, что использование её правил не зависит от контекста (что не исключает того, что она в некотором роде задает себе контекст сама, например правило для вызова функции не будет иметь значения, если находится внутри фрагмента потока, описываемого правилом комментария). Состоит из правил продукции, заданных для терминальных и не терминальных символов.
• Терминальные символы (терминалы) — для заданного языка разбора — набор всех (атомарных) символов, которые могут встречаться во входящем потоке
• Не терминальные символы (не терминалы) — для заданного языка разбора — набор всех символов, не встречающихся во входном потоке, но участвующих в правилах грамматики.
• язык разбора (в большинстве случаев будет КСЯ(контекстно-свободный язык)) — совокупность всех терминальных и не терминальных символов, а также КСГ для данного входного потока. Для примера, в естественных языках терминальными символами будут все буквы, цифры и знаки препинания, используемые языком, не терминалами будут слова и предложения (и другие конструкции, вроде подлежащего, сказуемого, глаголов, наречий и т.п.), а грамматикой собственно грамматика языка.
• BNF(Backus-Naur Form, Backus normal form)/БНФ(Бэкуса-Наура форма) — форма, в которой одни синтаксические категории последовательно определяются через другие. Форма представления КСГ, часто используемая непосредственно для задания входа парсеру. Характеризуется тем, что определяемым является всегда ОДИН нетерминальный символ. Классической является форма записи вида:
  <определяемый символ> ::= <посл.1> | <посл.2> | . . . | <посл.n>
  
  Так же существует ряд разновидностей, таких как ABNF(AugmentedBNF), EBNF(ExtendedBNF) и др. В общем, эти формы несколько расширяют синтаксис обычной записи BNF.
• LL(k), LR(k), SLR,… — виды алгоритмов парсеров. В этой статье мы не будем подробно на них останавливаться, если кого-то заинтересовало, внизу я дам несколько ссылок на материал, из которого можно о них узнать. Однако остановимся подробнее на другом аспекте, на грамматиках парсеров. Грамматика LL/LR групп парсеров является BNF, это верно. Но верно также, что не всякая грамматика BNF является также LL(k) или LR(k). Да и вообще, что значит буква k в записи LL/LR(k)? Она означает, что для разбора грамматики требуется заглянуть вперед максимум на k терминальных символов по потоку. То есть для разбора (0) грамматики требуется знать только текущий символ. Для (1) — требуется знать текущий и 1 следующий символ. Для (2) — текущий и 2 следующих и т.д. Немного подробнее о выборе/составлении BNF для конкретного парсера поговорим ниже.
• PEG(Parsing expression grammar)/РВ-грамматика — грамматика, созданная для распознавания строк в языке. Примером такой грамматики для алгебраических действий +, -, *, / для неотрицательных чисел является:
  Value ← [0-9]+ / '(' Expr ')'

Product ← Value (('*' / '/') Value)*

Sum ← Product (('+' / '-') Product)*

Expr ← Sum

И наконец мы закончили с основными понятиями. Перейдем к выбору способа разбора.

Варианты разбора

Когда мы сталкиваемся с задачей создания парсера, решение сводится, как правило, к 4 основным вариантам:

• Решать задачу в лоб, то есть анализировать посимвольно входящий поток и используя правила грамматики, строить АСД или сразу выполнять нужные нам операции над нужными нам компонентами. Из плюсов — этот вариант наиболее прост, если говорить об алгоритмике и наличии математической базы. Минусы — вероятность случайной ошибки близка к максимальной, поскольку у вас нет никаких формальных критериев того, все ли правила грамматики вы учли при построении парсера. Очень трудоёмкий. В общем случае, не слишком легко модифицируемый и не очень гибкий, особенно, если вы не имплементировали построение АСД. Даже при длительной работе парсера вы не можете быть уверены, что он работает абсолютно корректно. Из плюс-минусов. В этом варианте все зависит от прямоты ваших рук. Рассказывать об этом варианте подробно мы не будем.
• Используем регулярные выражения! Я не буду сейчас шутить на тему количества проблем и регулярных выражений, но в целом, способ хотя и доступный, но не слишком хороший. В случае сложной грамматики работа с регулярками превратится в ад кромешный, особенно если вы попытаетесь оптимизировать правила для увеличения скорости работы. В общем, если вы выбрали этот способ, мне остается только пожелать вам удачи. Регулярные выражения не для парсинга! И пусть меня не уверяют в обратном. Они предназначены для поиска и замены. Попытка использовать их для других вещей неизбежно оборачивается потерями. С ними мы либо существенно замедляем разбор, проходя по строке много раз, либо теряем мозговые клеточки, пытаясь измыслить способ удалить гланды через задний проход. Возможно, ситуацию чуть улучшит попытка скрестить этот способ с предыдущим. Возможно, нет. В общем, плюсы почти аналогичны прошлому варианту. Только еще нужно знание регулярных выражений, причем желательно не только знать как ими пользоваться, но и иметь представление, насколько быстро работает вариант, который вы используете. Из минусов тоже примерно то же, что и в предыдущем варианте, разве что менее трудоёмко.
• Воспользуемся кучей инструментов для парсинга BNF! Вот этот вариант уже более интересный. Во-первых, нам предлагается вариант типа lex-yacc или flex-bison, во вторых во многих языках можно найти нативные библиотеки для парсинга BNF. Ключевыми словами для поиска можно взять LL, LR, BNF. Смысл в том, что все они в какой-то форме принимают на вход вариацию BNF, а LL, LR, SLR и прочее — это конкретные алгоритмы, по которым работает парсер. Чаще всего конечному пользователю не особенно интересно, какой именно алгоритм использован, хотя они имеют определенные ограничения разбора грамматики (остановимся подробнее ниже) и могут иметь разное время работы (хотя большинство заявляют O(L), где L — длина потока символов). Из плюсов — стабильный инструментарий, внятная форма записи (БНФ), адекватные оценки времени работы и наличие записи БНФ для большинства современных языков (при желании можно найти для sql, python, json, cfg, yaml, html, csv и многих других). Из минусов — не всегда очевидный и удобный интерфейс инструментов, возможно, придется что-то написать на незнакомом вам ЯП, особенности понимания грамматики разными инструментами.
• Воспользуемся инструментами для парсинга PEG! Это тоже интересный вариант, плюс, здесь несколько побогаче с библиотеками, хотя они, как правило, уже несколько другой эпохи (PEG предложен Брайаном Фордом в 2004, в то время как корни BNF тянутся в 1980-е), то есть заметно моложе и хуже выглажены и проживают в основном на github. Из плюсов — быстро, просто, часто — нативно. Из минусов — сильно зависите от реализации. Пессимистичная оценка для PEG по спецификации вроде бы O(exp(L)) (другое дело, для создания такой грамматики придется сильно постараться). Сильно зависите от наличия/отсутствия библиотеки. Почему-то многие создатели библиотек PEG считают достаточными операции токенизации и поиска/замены, и никакого вам AST и даже привязки функций к элементам грамматики. Но в целом, тема перспективная.

Решаем задачу парсинга

Пойдем по-порядку, варианты brute-force и regexp пропускаем.

BNF

Вот и настало время чуть подробнее остановиться на алгоритмах разборщика, вернее на используемых ими грамматиках. Итак, наиболее часто встречаются GLR (до O(L^3) или до O(L^4), как говорят некоторые источники (antlr)), LR, LALR и LL — все в пределах O(L). Наибольшей “прожорливостью” обладает GLR — она способна лучше обрабатывать неоднозначности грамматики, но за счет этого и более медленна. То есть если рассматривать “размер” класса обрабатываемых парсером грамматик(назовем его мощностью парсера), то при прочих равных, мощности распределятся так GLR > LR > LALR > SLR > LL. Потребление ресурсов, соответственно, близко к обратному. Но вернемся к грамматикам.

Составление или поиск грамматики для LR-парсера в целом достаточно просто и высок шанс, что составленный вами “на коленке” BNF будет спокойно воспринят парсером и обработан. Главное, грамматика должна быть полной, то есть описывать все возможные ситуации входного потока, кроме того попробуйте сами понять навскидку, можно ли зная k следующих символов (в зависимости от выбранного LR-парсера) однозначно определить, какое именно правило должно применяться.

Для LR-парсера могут возникать конфликты следующего вида:

1. Перенос-свертка (shift-reduce): NT ::= x NT | x. Где длина x > k. Решается так: NT ::= xK; K ::= K | e
2. Свертка-свертка (reduce-reduce):
   NT :: = e

A ::= NT

B ::= NT

D ::= B u v | A u w, где длина u > k
   
   Решается так:
   R ::= Au

J ::= Bu

D ::= Rw | Jv

Для LL-парсера характерны конфликты вида (необходимо, но не достаточно, их переформулировать, по запросу могу остановиться на LL(k) грамматиках подробнее в следующей статье):

Левая рекурсия: NT ::= NT x | y, где x, y — произвольные строки терминалов/не терминалов, но y не начинается с NT

Пример: E ::= E + T | T. Можно переформулировать, как:

E ::= T Z

Z ::= ‘+’ TZ | x

Левая факторизация: NT ::= ax | ay, где a — строка длины > k нашего парсера. Решается еще проще: NT ::= aC; C = x|y

Итак, что мы будем решать?

Ну, допустим, это будет простой калькулятор:

OPERATOR        ::= "+ "| "-" | "*" | "/"
    STMT            ::= "(" STMT ")" | STMT OPERATOR STMT | FLOAT | INT
    FLOAT           ::= INT "." INT
    INT             ::= (POSITIVE_DIGIT INT | DIGIT ) | DIGIT
    POSITIVE_DIGIT  ::= "1"|"2"|"3"|"4"|"5"|"6"|"7"|"8"|"9"
    DIGIT           ::= POSITIVE_DIGIT | "0"

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

Пробуем найти нативное Python-решение, находим их много.

1. Используем parglare. Это библиотека/cli-tool на Python, реализующий LR/GLR парсер c достаточно широким спектром возможностей (инлайн-функции, приоритизация, деревья, внятный анализ грамматики, визуализатор КА, получающегося при обработке грамматики).

   pip install parglare

   
   Переформулируем наш калькулятор так, как просит parglare

   OPERATOR        : "+ "| "-" | "*" | "/" | =
       STMT            : "(" STMT ")" | STMT OPERATOR STMT | FLOAT | INT
       FLOAT           : INT "." INT
       INT             : (POSITIVE_DIGIT INT | DIGIT ) | DIGIT
       POSITIVE_DIGIT  : "1"|"2"|"3"|"4"|"5"|"6"|"7"|"8"|"9"
       DIGIT           : POSITIVE_DIGIT | "0"

   
   Достаточно? Сохраним в calc.pg и воспользуемся cli-tool

   pglr --debug check calc.pg
   Error in file "/home/survivor/tests/calc.pg" at position 1,42 => "" | "/" | *=\nSTMT    ". Expected: Name or StrTerm or RegExTerm
   

   
   Упс! кажется, что-то лишнее. Бинго! я зачем-то вставил | = после “/” (нет, я-то знаю, откуда он там (но к теме статьи это не относится) ). Главное в том, что программа нам четко на это указала. Далее после исправления программа поругается еще на отсутствие; в конце обозначения нетерминала и на скобочку в правиле INT. Переформулированный вариант будет выглядеть так:

   STMT            : "(" STMT ")" | STMT OPERATOR STMT | FLOAT | INT;
   OPERATOR        : "+ "| "-" | "*" | "/";
   FLOAT           : INT "." INT;
   INT             : POSITIVE_DIGIT INT | POSITIVE_DIGIT DIGIT | DIGIT;
   POSITIVE_DIGIT  : "1"|"2"|"3"|"4"|"5"|"6"|"7"|"8"|"9";
   DIGIT           : POSITIVE_DIGIT | "0";

   
   В итоге, pglr все нравится и он нам скажет:

   Grammar ok! 

   
   НО:

   There are 4 Shift/Reduce conflicts.
   Either use 'prefer_shifts' parser mode, try to resolve manually or use GLR parsing.
   There are 7 Reduce/Reduce conflicts.
   Try to resolve manually or use GLR parsing.
   

   
   Ну, а выше по выводу debug можно прочитать их красивое (и понятное) описание. Ну что ж, давайте подумаем. Во первых, давайте не будем самыми умными и выкинем нафиг positive_digit. Если кто-то напишет 0034 — во первых, он сам себе злобный буратино, а во вторых, большинство ЯП, в том числе Python при конвертации этого в число не скажут нам ничего и просто выдадут 34. Прекрасно, это сильно поможет. Во-вторых, нафиг отсюда разделение на int/float, для простоты предположим что все числа с плавающей точкой. Также, pglr понимает регулярные выражения в BNF, воспользуемся этим. Получим:

    STMT            : "(" STMT ")" | STMT OPERATOR STMT | FLOAT;
   OPERATOR        : "+ "| "-" | "*" | "/";
   FLOAT           : /\d+(\.\d+)?/;

   
   и по-прежнему

   There are 4 Shift/Reduce conflicts.
   Either use 'prefer_shifts' parser mode, try to resolve manually or use GLR parsing.

   
   Ну, как бы то ни было, грамматика

   *** GRAMMAR ***
   Terminals:
   +  EOF ) ( FLOAT STOP * / - \d+(\.\d+)? EMPTY
   NonTerminals:
   OPERATOR S' STMT
   Productions:
   0: S' = STMT STOP
   1: STMT = STMT OPERATOR STMT
   2: STMT = ( STMT )
   3: STMT = FLOAT
   4: OPERATOR = + 
   5: OPERATOR = -
   6: OPERATOR = *
   7: OPERATOR = /

   
   Попробуем реально распарсить что-нибудь.

   from parglare import Grammar
   from parglare import Parser
   
   grammar = Grammar.from_file(‘calc.pg’)
   parser = Parser(grammar, build_tree=True, prefer_shifts=True)
   result = parser.parse('1 + 2 / (3 - 1 + 5)')

   
   Получаем:

   result
   <NonTerm(start=0, end=19, sym=STMT)>

   
   можем получить result.children и далее по дереву. Можем заодно подсчитать итоговое выражение, но делать это здесь не будем. Важно, что мы получили доступ к дереву объектов, для терминальных символов так же их “значение” и можем делать с этим все, что пожелаем.

   Если мы хотим поправить конфликтные ситуации, как еще можно разрешить конфликты грамматики?

   Есть несколько вариантов:

   • Решить задачу переформулировав грамматику
     
     Например, так:

     STMT : TERM | STMT ADDOP TERM ;
     TERM : FACTOR | FACTOR MULOP FACTOR ;
     FACTOR : "(" STMT ")" | NUMBER;
     ADDOP : "+" | "-";
     MULOP : "*"|"/"; 
     NUMBER: /\d+(\.\d+)?/;

     
     Как видим, задача усложнилась, но не слишком. Тем более, если мы будем делать разбор именно такого дерева, нам будет проще.

   • Использовать средства самого parglare

     В этом случае решение более частное, но в ряде случаев более удобное. Parglare предоставляет хороший инструментарий для приоритезации правил, к примеру, для арифметических выражений можно выставить приоритет операции и ассоциативность (с какой стороны выполняется данная операция — слева направо или справа налево) чем приоритет выше, тем операция выполнится раньше (относительно остальных), к примеру, наша грамматика в такой нотации может выглядеть вот так:

     STMT :  STMT ADDOP STMT {1, left}
     	|  STMT MULOP STMT {2, left}
     | "(" STMT ")" | NUMBER;
     ADDOP : "+" | "-";
     MULOP : "*"|"/"; 
     NUMBER: /\d+(\.\d+)?/;

     
     Парсится, но работает не правильно. Например, для

     1 + 2 / (3 - 1 + 5)

     получаем (при не-древовидном парсинге)

     ['1', u'+', ['2', u'/', [u'(', ['3', u'-', ['1', u'+', '5']], u')']]]

     
     что, очевидно, не соответствует ожидаемому результату:

     ['1', u'+', ['2', u'/', [u'(', [['3', u'-', '1'], u'+', '5'], u')']]]

   
   Мораль — лучше использовать стандартные описанные в BNF моменты. Блестящие и прикольные штуки блестят и прикольны, но не всегда работают. Или я не умею их готовить. А большинство библиотек парсинга — имеют версию alpha | beta.

   По словам автора об этом баге, он происходит из-за того, что, по сути своей, ассоциативность (left) парсера на уровне алгоритма означает — предпочитать reduce, а не shift. То есть, по сути, если есть возможность “обрубить” правило, или продолжить в его рамках — лучше обрубить. Поскольку парсинг идет слева направо, это и означает левую ассоциативность. Причина же ошибки в том, что не определена приоритетность для правил внутри ADDOP/MULOP, что ломает все правило.

   Однако, даже если мы зададим приоритетность (например:

   ADDOP: “+” {1}

| “-” {1}), работать все равно не будет, уже из-за другой ошибки.

   Напоследок пример с инлайн-функциями, привязываемыми непосредственно к правилам, из документации parglare.

   from parglare import Parser, Grammar
   
   grammar = r"""
   E: E '+' E  {left, 1}
   | E '-' E  {left, 1}
   | E '*' E  {left, 2}
   | E '/' E  {left, 2}
   | E '^' E  {right, 3}
   | '(' E ')'
   | number;
   number: /\d+(\.\d+)?/;
   """
   
   # Define inline functions bound to grammar rule
   actions = {
       "E": [lambda _, nodes: nodes[0] + nodes[2], # for rule[0]  “+”
             lambda _, nodes: nodes[0] - nodes[2], # for rule[1]  “-”
             lambda _, nodes: nodes[0] * nodes[2], # for rule[2]  “*”
             lambda _, nodes: nodes[0] / nodes[2], # for rule[3]  “/”
             lambda _, nodes: nodes[0] ** nodes[2], # for rule[4]  “^”
             lambda _, nodes: nodes[1], # for rule[5]  “()” - just get the middle
             lambda _, nodes: nodes[0]],  # for rule[6]  just get node
       "number": lambda _, value: float(value), # for rule - convert to float
   }
   
   g = Grammar.from_string(grammar)
   parser = Parser(g, debug=True, actions=actions)
   
   result = parser.parse("34 + 4.6 / 2 * 4^2^2 + 78")
   
   print("Result = ", result)
   
   # Output
   # -- Debuging/tracing output with detailed info about grammar, productions,
   # -- terminals and nonterminals, DFA states, parsing progress,
   # -- and at the end of the output:
   # Result = 700.8

2. Дальше попробуем standalone-инструмент ANTLR.

   Установка довольно простая, для linux это

   $ cd /usr/local/lib
   $ curl -O http://www.antlr.org/download/antlr-4.7.1-complete.jar
   $ export CLASSPATH=".:/usr/local/lib/antlr-4.7.1-complete.jar:$CLASSPATH"
   $ alias antlr4='java -Xmx500M -cp "/usr/local/lib/antlr-4.7.1-complete.jar:$CLASSPATH" org.antlr.v4.Tool'
   $ alias grun='java org.antlr.v4.gui.TestRig'

   
   Для того, чтобы работать на python2, нужно еще доустановить

   pip install antlr4-python2-runtime

   
   Дальше попробуем сделать для него грамматику. У него чуть отличается формат, поэтому двойные кавычки заменим на одинарные и чуть перепишем регулярное выражение, а так же добавим обозначение для WS, который в предыдущем инструменте задавался по умолчанию. Левую рекурсию в нашем случае можно устранить просто переписав на правую.

   Важный момент! В ANTLR есть правила парсера и грамматические правила. К появлению узла в результирующем AST ведут правила парсинга. Кроме того, существует некоторое различие, что можно/нельзя в грамматических/правилах парсинга. В частности, в правилах парсинга нет регулярных выражений. Кроме того, парсер должен получить входное правило, стартовый нетерминал (вообще, все несколько сложнее, но в нашем случае вполне хватает и этого). Вообще, стоит заметить, что ANTLR имеет довольно мощный синтаксис, так же поддерживает инлайн функции (пусть и несколько в ином формате) и “не попадающие в дерево” нетерминалы и кое-что еще. В итоге, наша грамматика выглядит так:

   grammar calc;
   stmt : term | term addop stmt ;
   term : factor | factor mulop factor ;
   factor : '(' stmt ')' | NUMBER;
   addop : '+' | '-';
   mulop : '*'|'/'; 
   NUMBER: [0-9]+|[0-9]+.[0-9]+;
   WS : [ \t\r\n]+ -> skip ;

   
   Файл при этом называется calc.g4 (Это важно! название файла должно совпадать с названием грамматики внутри).

   Создадим java-парсер.

   antlr4 calc.g4
   javac calc*.java
   grun calc stmt -gui

   
   Дальше даем ему какой-то инпут (например, 1 + 2 / (3 - 1 + 5)) и нажимаем конец строки (ctrl-d на *nix, ctrl-z на windows) и смотрим на результат. Нам показали красивое дерево разбора, еще и интерактивное. Можно посмотреть, покрутить узлы, подумать, экспортировать в качестве картинки.

   Создадим python2-парсер:

   antlr4 -Dlanguage=Python2 calc.g4

   Далее, мы можем навесить на грамматику листенеры и наслаждаться.

   import sys
   from antlr4 import *
   from calc_bakLexer import calc_bakLexer
   from calc_bakListener import calc_bakListener
   from calc_bakParser import calc_bakParser
   
   
   class StmtPrinter(calc_bakListener):
       def __init__(self):
           self.map_results = {}
           self.result = 0
   
       def exitStmt(self, ctx):
           print("Oh, a stmt! {}".format(ctx.getText()))
   
   
   
   def main(argv):
       input = FileStream(argv[1])
       print(input)
       lexer = calc_bakLexer(input)
       stream = CommonTokenStream(lexer)
       parser = calc_bakParser(stream)
       tree = parser.stmt()
       printer = StmtPrinter()
       walker = ParseTreeWalker()
       walker.walk(printer, tree)
   
   if __name__ == '__main__':
       main(sys.argv)

   
   … Наслаждаться неправильно работающей программой. Вернее, правильно, но неожиданно.

   python ./calc_antlr_min.py ./example.antlr 
   1 + 2 / (3 - 1 + 5)
   
   Oh, a stmt! 5
   Oh, a stmt! 1+5
   Oh, a stmt! 3-1+5
   Oh, a stmt! 2/(3-1+5)
   Oh, a stmt! 1+2/(3-1+5)
   

   
   Как видно, ассоциативность здесь “правая”. А операции сложения-вычитания, умножения-деления — левые. Я честно пытался несколько дней (sic!) найти решение (разумеется, я занимался этим не все время, но в сумме убил на это часов 12-15). Маркеры ассоциативности, кучи мануалов, переформулирование грамматики…. Не получилось. Я уверен, что решение есть. Более того, пример грамматики калькулятора есть здесь. Но я хотел найти своё решение, по возможности, в терминах общей грамматики. В конце концов, целью было НАУЧИТЬСЯ, а не решить задачу.

   И я признаю свою неудачу. Да, задача решаема. Но пользуясь только документацией и поиском на общие темы, мне её решить не удалось. Причины… Во-первых, исключая книгу по ANTLR, доступные в сети источники не отличаются подробностью и выразительностью. Во-вторых, в сети масса материалов по разным (не совместимым) версиям ANTLR. Нет, я все понимаю, развитие и прочее. Но почему-то в процессе знакомства с инструментом у меня сложилось ощущение, что о понятии обратной совместимости автор даже не слышал. В общем, грустно.

   Update

   
   Как верно замечено, одна голова хорошо, а две лучше.
   
   Переформулирование грамматики с право-ассоциативной на левую выполняется буквально «щелчком пальцев» (Спасибо Valentin Nechayev netch80 за дополнение) — нужно всего лишь заменить

   stmt : term | term addop stmt ;
   

   
   на

   stmt : term | stmt addop term ;
   

   
   Левую рекурсию в данном случае ANTLR обрабатывает без вопросов (видимо, благодаря каким-то оптимизациям). Вывод простых листенеров в этом случае

   python ./calc_antlr_min.py ./example.antlr 
   1 + 2 / (3 - 1 + 5)
   
   Oh, a stmt! 1
   Oh, a stmt! 3
   Oh, a stmt! 3-1
   Oh, a stmt! 3-1+5
   Oh, a stmt! 1+2/(3-1+5)

PEG

По сути, являются упрощенной формой BNF, но знать об этом программисту, в целом, не обязательно. В отличие от BNF, изначально больше похожи на регулярные выражения. По сути, можно было бы сказать, что это BNF с возможностью использовать регулярные выражения “по стандарту” (причем, что приятно, не только внутри нетерминальной строки, но и в некоторой степени в самом выражении (PEG поддерживает конструкции вида A = B ( X C)* или, к примеру Z = R (K)?, читаемые как “A состоит из B и любого количества повторений X и C, стоящих последовательно” и “Z состоит из R и следующего за ним K 0 или 1 раз”). Но, на мой взгляд, это все же не главное. Главное в том, что PEG изначально спроектирован, как грамматики ПАРСЕРА. А с какой главной проблемой сталкиваются парсеры, в том числе BNF? Неоднозначность выбора! Для решения этой проблемы в PEG присутствует замечательный оператор последовательного или “/”. В отличие от оператора “|”, который описывает равнозначные альтернативы, “/” четко указывает порядок разрешения правила. Например, A / B / C / D указывает: сравнить с A, если не подходит, сравнить с B, если не подходит, сравнить с C и т.д. По этой причине, оперирование PEG-грамматиками ПРОЩЕ. И еще, рекомендация — если вам безразличен порядок выполнения сравнения, лучше писать “/”. Это уменьшит количество неоднозначных для парсера ситуаций. Однако, как и с любым инструментом, с этим следует обращаться с осторожностью.
Еще, будьте внимательны, создатели PEG-парсеров ещё более подвержены желанию понимать стандарт так, как им хочется, поэтому лексика разных реализаций может существенно различаться.

Итак, перейдем к практике.

Используем Arpeggio от автора parglare:

pip install arpeggio

Дальше разбираемся с документацией и узнаем, что рекомендованным для работы с AST для этой библиотеки является шаблон посетитель (visitor), весьма похожий на рекомендованный в ANTLR слушатель (listener). К счастью, здесь для всего эксперимента мне хватило часа, все оказалось не сложно:

from arpeggio.cleanpeg import ParserPEG
from arpeggio import PTNodeVisitor, EOF, visit_parse_tree
# Setting up our simple grammar
calc_grammar = """
number = r'\d+(\.\d+)?'
factor = number / "(" stmt ")"
term = factor (mulop factor)*
stmt = term (addop term)*
addop = "+" / "-"
mulop = "*" / "/"
calc = stmt EOF
"""

#Creating a visitor class to calculate the result
class CalcVisitor(PTNodeVisitor):

    def visit_number(self, node, children):
        return float(node.value)

    def visit_factor(self, node, children):
        # Children are list-like structure of VISITED node results
        # visits are made from depth to top
        return children[0]

    def visit_term(self, node, children):
        # For such rules you may use, for example children["factor"]
        # Though, you need to know, that children["factor"] is a list of ALL
        # factor's of this term
        if len(children) == 1:
            return children[0]
        else:
            res = children[0]
            for i in xrange(len(children) / 2):
                if children[2 * i + 1] == '*':
                    res *= children[2 * (i + 1)]
                else:
                    res /= children[2 * (i + 1)]
            return res

    def visit_stmt(self, node, children):
        if len(children) == 1:
            return children[0]
        else:
            res = children[0]
            for i in xrange(len(children) / 2):
                if children[2 * i + 1] == '+':
                    res += children[2 * (i + 1)]
                else:
                    res -= children[2 * (i + 1)]
            return res

# Don’t forget about root rule for your parser, as it will be produced as
# a parsing result
parser = ParserPEG(calc_grammar, "calc")
input_expr = "(4-1)*5+(2+4.67)+5.89/(1.2+7)"
print(input_expr)
parse_tree = parser.parse(input_expr)

result = visit_parse_tree(parse_tree, CalcVisitor(
    #debug=True
))
print(result)
input_expr = "1 + 2 / (3 - 1 + 5)"
print(input_expr)
parse_tree = parser.parse(input_expr)

result = visit_parse_tree(parse_tree, CalcVisitor(
    #debug=True
))
print(result)

При запуске выведет следующее:

python ./calc_arpeggio.py 
(4-1)*5+(2+4.67)+5.89/(1.2+7)
22.3882926829
1 + 2 / (3 - 1 + 5)
1.28571428571

Если есть желание посмотреть, как посетитель обходит дерево, можно раскомментировать debug

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

Общие выводы

На самом деле, выводов несколько:

• Не так страшен чёрт, как его малюют. Создание парсера с помощью инструмента, дело, в общем, посильное. Достаточно изучить общие принципы и потратить полдня на изучение конкретного инструмента, после чего в дальнейшем все уже будет намного проще. А вот велосипеды изобретать — не надо. Особенно, если вам не особенно важна скорость парсинга и оптимизации.
• Грамматики имеют собственную ценность. Имея перед глазами грамматику, гораздо проще оценить, будут ли при использовании составленного по ней парсера возникать ошибки.
• Инструмент можно найти всегда. Возможно, не на самом привычном языке, но почти на всех они есть. Если не повезло, и его все-таки нет, можно взять что-нибудь легко используемое (что-то на js, python, lua или ruby — тут уж кому что больше нравится). Да, получится “почти stand-alone в рамках проекта”, но в большинстве случаев этого достаточно.
• Все инструменты (немного) различаются. Иногда это “:” вместо “=” в BNF, иногда различия более обширны. Не надо этого пугаться. В крайнем случае, переделка грамматики под другой инструмент займет у вас минут 20. Так что если есть возможность достать где-то грамматику, а не писать её самому, лучше это сделать. Но перед использованием все равно лучше её проверьте. Все мы люди, всем нам свойственно ошибаться…
• При прочих равных, лучше используйте более “разговорчивый” инструмент. Это поможет избежать ошибок составления грамматики и оценить, что и как будет происходить.
• Если для вас в первую очередь важна скорость разбора, боюсь, вам придется либо пользоваться инструментом для C (например, Bison), либо решать проблему “в лоб”. Так же, следует задуматься о том, нужен ли вам именно парсинг (об этом стоит задуматься в любом случае, но в случае скоростных ограничений — особенно). В частности, для многих задач подходит токенизация — разбиение строки на подстроки с использованием заданного разделителя или их набора. Возможно, это ваш случай.

Заключение

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

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

Как и обещал, несколько полезных ссылок по теме статьи:

• В википедии, на английском (на русском статьи существенно меньше):
  СFG
  BNF
  LL
  LR
  PEG
• Если кому-то нужно более серьёзное чтиво, тоже для человека “без математического бекграунда”, могу посоветовать книгу А. Аxo, Дж. Ульман “Теория синтаксического анализа, перевода и компиляции”. Есть, например, здесь. При желании находится достаточно легко, в русском переводе.

Аппликативные парсеры на Haskell / Хабр

Когда я только начинала осваивать Haskell, меня очень раздражало повсеместное использование сложных абстракций вместо каких-то конкретных решений. Мне казалось, что гораздо лучше всегда следовать принципу KISS и писать велосипеды с использованием элементарных конструкций языка, чем разбираться во всех этих классах типов, чтобы где-то в итоге написать одну якобы удобную конструкцию.

Мне не хватало хорошего примера, где бы окупались усилия, потраченные на освоение «матчасти». Для меня одним из самых удачных таких примеров оказались парсеры. Теперь я довольно часто рассказываю про них, когда у меня спрашивают, для каких распространённых задач можно красиво использовать Haskell.

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

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

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

Для тех, кто на Haskell никогда не писал, но хочет понять, что здесь происходит, рекомендую сначала посмотреть на соответствующую страницу на Learn X in Y minutes. В качестве отличной русскоязычной книги для начинающих советую «О Haskell по-человечески» Дениса Шевченко.

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

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

Классы типов в Haskell не имеют ничего общего с классами в С++ и прочих объектно-ориентированных языках. Если проводить аналогию с ООП, то классы типов скорее напоминают перегрузку методов и функций.

Классы определяют, какие действия можно совершать с объектами тех типов, которые входят в класс. Например, все числа можно сравнивать на равенство, но упорядочить можно все, кроме комплексных, а функции в общем случае сравнить вообще нельзя. Класс типов, которые можно сравнивать, называется Eq, упорядочить — Ord (типы не обязательно должны быть числовыми). То, что можно напечатать, переведя в строку, принадлежит к классу Show, у него есть «противоположенный» класс Read, который определяет, как преобразовывать строки в объекты нужного типа.

Для набора стандартных классов типов (таких как Eq, Show, Read …) можно попросить компилятор реализовать нужный функционал стандартным образом, используя ключевое слово deriving после определения типа:

data Point = Point
    { xCoord :: Float
    , yCoord :: Float
    } deriving (Eq, Show)

Можно определять свои классы типов:

class PrettyPrint a where
  pPrint :: a -> String

Здесь PrettyPrint — имя класса, a — переменная типа. После ключевого слова where следует список так называемых методов класса, т.е. функций, которые могут быть применены к объектам, имеющим тип из этого класса.

Для того, чтобы обозначить принадлежность типа данных к классу, используется следующая конструкция:

instance PrettyPrint Point where
  pPrint (Point x y) = "(" ++ show x ++ ", " ++ show y ++ ")"

Язык позволяет указывать ограничения на классы типов, к которым должны относиться аргументы функции:

showVsPretty :: (Show a, PrettyPrint a) => a -> (String, String)
showVsPretty x = (show x, pPrint x)

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

>>> showVsPretty (Point 2 3)
("Point {xCoord = 2.0, yCoord = 3.0}","(2.0, 3.0)")

>>> showVsPretty "str"
error:
    No instance for (PrettyPrint [Char]) arising from a use of ‘showVsPretty’

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

Для описания одного результата работы парсера подойдёт кортеж из двух элементов (String, a), где a — переменная типа, которая может обозначать любой пользовательский тип.

Поскольку парсер разбирает строку по каким-то правилам, опишем его как функцию, принимающую на вход строку и возвращающую список результатов:

newtype Parser a = Parser { unParser :: String -> [(String, a)] }

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

parseString :: String -> Parser a -> Maybe a
parseString s (Parser p) = case (p s) of
    [("", val)] -> Just val
    _           -> Nothing

Простейшие парсеры

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

Начнём с разбора одного символа, который должен удовлетворять предикату. Если входная строка пуста, то и результатом работы является пустой список. В противном случае проверяем значение предиката на первом символе строки. Если вернулось значение True, то результатом разбора является этот символ; возвращаем его вместе с остатком строки. В противном случае разбор также оканчивается неудачей.

predP :: (Char -> Bool) -> Parser Char
predP p = Parser f
  where
    f "" = []
    f (c : cs) | p c = [(cs, c)]
               | otherwise = []

Теперь мы можем написать парсер, принимающий конкретный символ в начале строки. Для этого используем только что написанную predP и передадим ей в качестве аргумента функцию, сравнивающую свой аргумент с нужным нам символом:

charP :: Char -> Parser Char
charP char = predP (\c -> c == char)

Следующий простейший случай: парсер, принимающий только определённую строку целиком. Назовём его stringP. Функция внутри парсера сравнивает входную строку с нужной и, если строки равны, возвращает список из одного элемента: пары из пустой строки (на входе больше ничего не осталось) и исходной. В противном случае разбор не удался, и возвращается пустой список результатов.

stringP :: String -> Parser String
stringP s = Parser f
  where
    f s' | s == s' = [("", s)]
         | otherwise = []

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

skip :: (Char -> Bool) -> Parser ()
skip p = Parser (\s -> [(dropWhile p s, ())])

Следующие два парсера очень похожи друг на друга. Оба проверяют префикс входной строки, только первый в случае успеха возвращает этот префикс, а второй — пустой кортеж, т.е. позволяет пропустить произвольную строку в начале входа. Для реализации используется функция isPrefixOf, определённая в модуле Data.List.

prefixP :: String -> Parser String
prefixP s = Parser f
  where
    f input = if s `isPrefixOf` input
                then [(drop (length s) input, s)]
                else []

skipString :: String -> Parser ()
skipString s = Parser f
  where
    f input = if s `isPrefixOf` input
                then [(drop (length s) input, ())]
                else []

Чуть позже мы рассмотрим более простую реализацию последней функции и избавимся от дублирования кода.

Парсер как функтор

Можно выделить целый класс типов-контейнеров, для которых верно следующее: если известно, как преобразовывать объекты внутри контейнера, то можно преобразовывать и сами контейнеры. Простейший пример — список в качестве контейнера и функция map, которая есть практически во всех высокоуровневых языках. Действительно, можно пройтись по всем элементам списка типа [a], применить к каждому функцию a -> b и получить список типа [b].

Такой класс типов называется Functor, у класса есть один метод fmap:

class Functor f where
  fmap :: (a -> b) -> f a -> f b

Предположим, что мы уже умеем разбирать строки в объекты некоторого типа a, и, кроме того, знаем, как преобразовать объекты типа a в объекты типа b. Можно ли сказать, что тогда есть парсер для объектов типа b?

Если выразить это в виде функции, то она будет иметь следующий тип:

(a -> b) -> Parser a -> Parser b

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

instance Functor Parser where
  fmap :: (a -> b) -> Parser a -> Parser b
  fmap f (Parser p1) = Parser p2
    where
      p2 :: String -> [(String, b)]
      p2 s = convert (p1 s)
      convert :: [(String, a)] -> [(String, b)]
      convert results = map (\(s, val) -> (s, f val)) results

У функции fmap есть удобный инфиксный синоним: fmap f x == f <$> x.

Если в качестве аргумента fmap использовать функцию, просто заменяющую свой первый аргумент на новое значение, то получим ещё одну полезную операцию, которая уже реализована для всех функторов даже в двух экземплярах (они отличаются только порядком аргументов):

(<$) :: Functor f => a -> f b -> f a
($>) :: Functor f => f a -> b -> f b

Помните парсер, который пропускает определённую строку (skipString)? Теперь можно его реализовать следующим образом:

skipString :: String -> Parser ()
skipString s = () <$ prefixP s

Комбинации парсеров

В Haskell все функции по умолчанию каррированы и допускают частичное применение. Это значит, что функция от n аргументов — это на самом деле функция от одного аргумента, возвращающая функцию от n-1 аргументов:

cons :: Int -> [Int] -> [Int]
cons = (:)

cons1 :: [Int] -> [Int]
cons1 = cons 1 -- функция cons применена частично

Применим функцию от трёх аргументов к какому-нибудь значению внутри парсера, используя fmap. Типы будут такие:

f :: c -> a -> b
p :: Parser c
(fmap f p) :: Parser (a -> b)

Получился парсер функции?! Конечно, возможна ситуация, когда во входной строке действительно находится представление функции, но хотелось бы иметь возможность применять эту функцию, а точнее комбинировать парсеры Parser (a -> b) и Parser a, чтобы получить Parser b:

applyP :: Parser (a -> b) -> Parser a -> Parser b

Тип этой функции очень похож на тип fmap, только сама функция, которую нужно применить, также находится в контейнере. Это даёт интуитивное понимание того, как должна выглядеть реализация функции applyP: получить функцию из контейнера (как результат применения первого парсера), получить значения, к которым должна применяться функция (результат применения второго парсера) и «запаковать» преобразованные с помощью этой функции значения обратно в контейнер (создать новый парсер). В реализации будем использовать list comprehension:

applyP :: Parser (a -> b) -> Parser a -> Parser b
applyP (Parser p1) (Parser p2) = Parser f
    where f s = [ (sx, f x) | (sf, f) <- p1 s,  -- p1 применяется к исходной строке
                              (sx, x) <- p2 sf] -- p2 применяется к строке, оставшейся после предыдущего разбора

Существует класс Applicative, у которого есть метод с таким же прототипом. Второй метод класса называется pure и используется для того, чтобы «завернуть» или «поднять» (lift) значение, в том числе функциональное. В случае реализации для парсера функция pure добавляет свой аргумент в результат работы парсера, не изменяя при этом входную строку.

class Functor f => Applicative f where
  pure :: a -> f a
  (<*>) :: f (a -> b) -> f a -> f b

instance Applicative Parser where
  pure x = Parser (\s -> [(s, x)])
  pf <*> px = Parser (\s -> [ (sx, f x) | (sf, f) <- unParser pf $ s,
                                          (sx, x) <- unParser px $ sf])

Функция applyP — это и есть <*> из класса Applicative. Типы, принадлежащие к этому классу, называются аппликативными функторами.

Для аппликативных функторов реализованы две вспомогательные функции, которые будут нам полезны:

(*>) :: f a -> f b -> f b
(<*) :: f a -> f b -> f a

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

Комбинируя <$> и <*>, можно создавать очень удобные конструкции. Рассмотрим следующий тип данных:

data MyStructType = MyStruct
  { field1 :: Type1
  , field2 :: Type2
  , field3 :: Type3
  }

Конструктор значений MyStruct — это тоже функция, в данном случае она имеет тип Type1 -> Type2 -> Type3 -> MyStructType. С конструктором можно работать как и с любой другой функцией. Предположим, что для типов полей структуры уже написаны парсеры:

parser1 :: Parser Type1
parser2 :: Parser Type2
parser3 :: Parser Type3

С помощью функции fmap можно частично применить MyStruct к первому из этих парсеров:

parserStruct' :: Parser (Type2 -> Type3 -> MyStructType)
parserStruct' = MyStruct <$> parser1

Попробуем дальше применять функцию, которая теперь находится «внутри» парсера. Для этого уже нужно использовать <*>:

parserStruct'' :: Parser (Type3 -> MyStructType)
parserStruct'' = parserStruct' <*> parser2

parserStruct :: Parser MyStructType
parserStruct = parserStruct'' <*> parser3

В итоге мы получили парсер для всей структуры (конечно, здесь используется предположение, что в исходной строке представления её полей идут подряд). То же самое можно сделать в одну строчку:

parserStruct :: Parser MyStructType
parserStruct = MyStruct <$> parser1 <*> parser2 <*> parser3

Такие конструкции будут часто встречаться в примере использования.

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

data Operand
  = IntOp Int
  | IdentOp String

Если мы уже умеем разбирать целые числа и идентификаторы (например, как в языке С), то нам нужен один парсер для операндов который может разобрать одно или другое. Этот парсер представляет собой альтернативу из двух других, поэтому нам нужна функция, умеющая комбинировать парсеры таким образом, чтобы результаты их работы объединялись. Результатом работы парсера является список, а объединение списков — это их конкатенация. Реализуем функцию altP, комбинирующую два парсера:

altP :: Parser a -> Parser a -> Parser a
altP (Parser p1) (Parser p2) = Parser (\s -> p1 s ++ p2 s)

Тогда парсер операнда можно реализовать, используя эту функцию (здесь предполагается, что parserInt и parserIdent уже где-то описаны:

parserOperand :: Parser Operand
parserOperand = altP parserIntOp parserIdentOp
  where
    parserIntOp = IntOp <$> parserInt
    parserIdentOp = IdentOp <$> parserIdent

Конечно, и для альтернатив уже придумали отдельный класс, который так и называется Alternative. В нём есть ещё один метод, empty, описывающий нейтральный элемент для операции альтернативы. В нашем случае это парсер, который никогда ничего не разбирает, т.е. всегда возвращает пустой список результатов. Для парсера реализация методов класса Alternative выглядит так:

class Applicative f => Alternative f where
  empty :: f a
  (<|>) :: f a -> f a -> f a

instance Alternative Parser where
  empty = Parser (const [])
  px <|> py = Parser (\s -> unParser px s ++ unParser py s)

Операция <|> — это и есть функция altP, только в инфиксной записи, которую удобнее использовать, комбинируя несколько парсеров подряд.

Для всех типов в этом классе реализованы две функции, some и many типа f a -> f [a]. Каждая из них может быть выражена через другую:

some v = (:) <$> v <*> many v
many v = some v <|> pure []

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

Теперь у нас всё готово для того, чтобы написать свой парсер, например, для простых арифметических выражений со следующей грамматикой:

 expr      ::= constExpr | binOpExpr | negExpr
 const     ::= int
 int       ::= digit{digit}
 digit     ::= '0' | ... | '9'
 binOpExpr ::= '(' expr ' ' binOp ' ' expr ')'
 binOp     ::= '+' | '*'
 negExpr   ::= '-' expr

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

Примеры правильной записи выражений:

"123"
"-(10 + 42)"
"(1 + ((2 + 3) * (4 + 5)))"

Примеры неправильной записи:

" 666 "
"2 + 3"
"(10  * 10)"

Объявим необходимые типы данных (само выражение и бинарная операция):

data Expr = ConstExpr  Int
          | BinaryExpr Expr Operator Expr
          | NegateExpr Expr

data Operator = Add | Mul

Можно приступать к разбору! Само выражение состоит из трёх альтернатив. Так и запишем:

-- expr ::= constExpr | binOpExpr | negExpr
exprParser :: Parser Expr
exprParser = constParser <|> binParser <|> negParser

Константа — целое положительное число. В нашем типе данных оно «завёрнуто» в конструктор, поэтому мы не можем использовать парсер для целого числа напрямую, но можем применить fmap, чтобы получить значение нужного типа.

-- const ::= int
constParser :: Parser Expr
constParser = ConstExpr <$> intParser

Целое число, согласно грамматике, представляется как непустая последовательность цифр. Для разбора одной цифры используем вспомогательную функцию predP и предикат isDigit из модуля Data.Char. Теперь для построения парсера для разбора последовательности цифр используем функцию some (не many, потому что должна быть хотя бы одна цифра). Результат работы такого парсера возвращает список всех возможных вариантов разбора, начиная с самой длинной записи. Например, если входная строка «123ab», список результатов будет следующим: [("ab", "123"), ("3ab", "12"), ("23ab", "1")]. Нам нужно разобрать самую длинную последовательность цифр и преобразовать её к типу Int. Целиком реализация выглядит следующим образом:

-- int   ::= digit{digit}
-- digit ::= '0' | ... | '9'
intParser :: Parser Int
intParser = Parser $ \s -> let res = unParser (some digitParser) s in
  case res of
      [] -> []
      ((rest, i) : xs) -> [(rest, read i)]
  where
    digitParser = predP isDigit

Следующий вариант записи выражения — применение бинарной операции. Согласно грамматике, во входной строке сначала должна идти открывающая скобка, первый операнд, пробел, символ операции, ещё один пробел, второй операнд и закрывающая скобка. Для разбора отдельных символов (скобок и пробелов) используем функцию charP. Операнды — это выражения, а для их разбора парсер уже есть (exprParser). Для разбора символа бинарной операции опишем вспомогательный парсер чуть ниже. Остаётся аккуратно скомбинировать этот набор парсеров. В начале и в конце выражения должны быть скобки: нужно это проверить, но сам результат отбросить. Для этого используем *> и <*:

binParser :: Parser Expr
binParser = charP '(' *> ??? <* charP ')'

Между этими парсерами для скобок должно происходить конструирование выражения с помощью конструктора BinaryExpr и парсеров для выражения и операции. Не забудем про пробелы вокруг символа операции, используя тот же метод, что и для скобок. Эта часть выглядит следующим образом:

BinaryExpr <$> exprParser -- первый операнд
           <*> (charP ' ' *> binOpParser <* charP ' ') -- операция, окружённая пробелами
           <*> exprParser -- второй операнд

Подставим это выражение вместо знаков вопроса:

-- binOpExpr ::= '(' expr ' ' binOp ' ' expr ')'
binParser :: Parser Expr
binParser =
  charP '(' *>
    (BinaryExpr <$> exprParser
                <*> (charP ' ' *> binOpParser <* charP ' ')
                <*> exprParser
    )
  <* charP ')'

Бинарная операция — это либо символ +, который разбирается в значение Add, либо *, который разбирается в Mul:

-- binOp ::= '+' | '*'
binOpParser :: Parser Operator
binOpParser = plusParser <|> multParser
  where
    plusParser = charP '+' $> Add
    multParser = charP '*' $> Mul

Осталась самая простая часть грамматики, отрицание выражения. С символом - поступаем так же, как со скобками и пробелами. Далее применяем конструктор NegateExpr к результату рекурсивного разбора:

-- negExpr ::= '-' expr
negParser = charP '-' *> (NegateExpr <$> exprParser)

Итак, все части парсера реализованы. Код во многом напоминает грамматику и полностью совпадает с ней по структуре.

Исходный код доступен на GitLab: https://gitlab.com/fierce-katie/applicative-parsers-demo.

Там проще оценить его объём и степень выразительности, поскольку комментариев гораздо меньше. Проект можно собрать утилитой Stack и запустить примитивный интерпретатор, использующий парсер, который мы написали:

$ stack build
$ stack exec demo-parser

Тем, кто хочет потренироваться дальше самостоятельно, могу посоветовать следующее:

• Грамматику можно всячески улучшить, например, допускать ведущие и висячие пробелы, добавить новые операции и т.д.
• Парсер переводит строку во внутреннее представление выражения. Это выражение можно вычислить и преобразовать интерпретатор так, чтобы он печатал не результат разбора а результат вычисления.
• Изучить возможности библиотек parsec, attoparsec, applicative-parsec и optparse-applicative, попробовать их применить.

Спасибо за внимание!

1. Learn Haskell in Y minutes
2. Денис Шевченко. «О Haskell по-человечески»
3. Библиотека parsec
4. Библиотека attoparsec
5. Библиотека applicative-parsec
6. Библиотека optparse-applicative

Дополняя SQL. Часть 1. Сложности парсинга. Истории о доработке ANTLR напильником / Хабр

Публикую на Хабр оригинал статьи, перевод которой размещен в блоге Codingsight.

Что будет в этой статье?

Более пяти лет работаю в компании, что занимается разработкой линейки IDE для работы с базами данных. Начиная работу над этой статьей я и не представлял как много интересных историй получится вспомнить, потому когда закончил получил более 30 страниц текста. Немного подумав, я сгруппировал истории по тематике, а статью разбил на несколько.

По мере публикации буду добавлять ссылки на следующие части:
Часть 1. Сложности парсинга. Истории о доработке ANTLR напильником
Часть 2. Оптимизация работы со строками и открытия файлов
Часть 3. Жизнь расширений для Visual Studio. Работа с IO. Необычное использование SQL
Часть 4. Работа с исключениями, влияние данных на процесс разработки. Использование ML.NET

За время работы произошло много интересного: мы нашли несколько багов в .NET, оптимизировали некоторые функции во много раз, а некоторые лишь на проценты, что-то делали очень круто и с первого раза, а что-то у нас не получалось даже после нескольких попыток. Моя команда занимается разработкой и поддержкой языковых функций IDE, главная из которых автодополнение кода. Отсюда и название цикла статей. В каждой их частей я буду рассказывать несколько историй: некоторые об успехах, некоторые о неудачах.

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

Для тех кому интересна лишь часть из этого и просто для удобной навигации содержание статьи:

Содержание

Кто я?

На эту работу я пришел джуном с совсем небольшим опытом. Я, как и многие, пришел в программирование потому что хотел делать игрушки. Несколько даже вполне успешно сделал. О разработке одной даже писал вот здесь. Недавно, кстати, воскресил ее на другом сервере. Была еще дюжина игр, сделанных или заброшенных на разных этапах готовности. Кроме игр, до получения этой работы, я успел выполнить несколько проектов на фрилансе. Самым крупным из них было приложение для социальных сетей представлявшее собой футбольный портал с турнирными таблицами, данными по игрокам и возможностью оповещать пользователей о финальном счете или забитых голах через SMS. Делалось это почти 10 лет назад. Тогда со смартфонами ходили далеко не все, а кто ходил все чаще без интернета или с трижды проклятым EDGE на котором-то и текстовый сайт открыть было не всегда возможно. Так что идея мне казалась годной.

Как-то так выходило, что помимо игр меня еще и тянуло создавать разный тулинг для себя или других разработчиков. Временами он оказывался близким к тому, что чуть позже мне пришлось делать на работе. Например, одним из проектов, что я делал изучая Win32 API была программа подсвечивающая XML код в Rich Edit Control. Кроме этого была возможность выгрузить код с подсветкой в BMP, HTML или модные тогда на разных форумах BB-коды.

Другим проектом, оказавшимся чертовски близким к тому, чем мне довелось заниматься на работе оказалась программа анализирующая код на С/С++ и строящая по нему блок-схему. Блок-схема строго соответствовала требованиям одного преподавателя в университете. Сделана она была топорно, в лоб, с нулевым знанием теории синтаксического анализа, а работала исключительно на моем дрянном характере. Несколько лет спустя, очищая компьютер от старого хлама, я наткнулся на нее и не смог удалить, потому выложил на github ради истории.

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

Какие сложности?

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

Десктопная разработка

Возможно это даже и не сложность, ведь это уже очень зрелая сфера в которой не так много неизвестного, библиотеки стабильны, best-practice известны. Эта особенность нашего проекта здесь, потому что я, как и многие другие программисты, падок на новизну, а новизна сейчас вся ушла в web. Были дни, когда во время дождя, я забирался на подоконник, укрывшись пледом, с кружкой какао, и думал о redis, react, highload и распределенных системах, что где-то там прямо сейчас разрабатываются без меня. Другая сторона этой проблемы в том, что и без того непросто описать знакомым разработчикам за пивом какую-то сложность проекта, а когда вы работаете над приложениями, что функционируют по фундаментально разным законам, это становится еще сложнее.

Парсинг SQL и диалектов

Мне и до этой работы доводилось писать небольшие парсеры для разных языков. Какое-то время я вел курсы по .NET. Некоторым группам, в качестве дополнительного задания, в рамках темы “строки”, предлагал написать собственный простой парсер JSON. Только вот SQL и его разновидности это далеко ни XML и ни JSON разработанные, чтобы быть одинаково понятными парсерам и людям. Более того, SQL синтаксически сложнее даже чем С/С++, с его множеством накопленных за долгую историю функций. SQL устроен иначе, его пытались сделать похожим на естественный язык, довольно успешно, кстати. В языке несколько тысяч (в зависимости от диалекта) ключевых слов. Часто для того, чтобы отличить одно выражение от другого, нужно подсмотреть на два и более слов(tokens) вперед. Этот подход называется lookahead. Существует классификация парсеров по тому, как далеко они умеют подглядывать вперед: LA(1), LA(2), или LA(*), что означает, что парсер может заглянуть так далеко вперед как это только может потребоваться, чтобы определить правильную ветку. Иногда необязательный конец одной конструкции(clause) внутри одного SQL-statement совпадает с началом другой, тоже необязательной: такие ситуации существенно усложняют парсеры. Воду в огонь подливает T-SQL, в котором точка-с-запятой не является обязательной, а возможное, но не обязательное окончание некоторых SQL-statement может конфликтовать с началом других.

Все еще не верите? Существует механизм описания формальных языков через грамматики. Грамматикой называют код на одном языке, который описывает другой. Из грамматики часто можно сгенерировать парсер с помощью того или иного инструмента. Наиболее известными инструментами и языками описания грамматики являются YACC и ANTLR. Парсеры сгенерированные YACC используются прямо в движках MySQL, MariaDB, PostgreSQL. Можно было попробовать взять их прямо из открытых исходников и на их основе разрабатывать code completion и прочие функции завязанные на анализе SQL. Причем такая реализация получала бы бесплатные в плане разработки обновления, а парсер бы вел себя гарантировано идентично движку базы. Так почему же мы используем ANTLR? Он качественно поддерживает C#/.NET, для работы с ним есть неплохие инструменты, его синтаксис значительно легче читать и писать. Синтаксис ANTLR оказался так удобен, что microsoft, с недавнего времени использует его в официальной документации C#.

Вернемся к моему доказательству сложности SQL, в сравнении с другими языками, по части парсинга. Для этого хочу сравнить размеры грамматик для разных языков доступных публично. В dbForge мы используем свои грамматики, они полнее тех, что доступны публично, но, к сожалению, сильно засорены вставками C# кода для поддержки разных функций, об этом подробнее в параграфе “Синтаксический анализ без деревьев” раздела “Ошибки”.

Ниже приведены размеры грамматик для разных языков:

JS — 475 строк парсер + 273 лексер = 748 строк
Java — 615 строк парсер + 211 лексер = 826 строк
C# — 1159 строк парсер + 433 лексер = 1592 строки
С++ — 1933 строки

MySQL — 2515 строк парсер + 1189 лексер = 3704 строки
T-SQL — 4035 строк парсер + 896 лексер = 4931 строка
PL SQL — 6719 строк парсер + 2366 лексер = 9085 строк

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

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

Это не все, ведь нам нужно не просто распарсить несколько файлов на SQL. Мы ведь делаем IDE, а значит должны работать на неполных или невалидных скриптах. Даже если вы пишете свои скрипты без ошибок, возможно вы их пишете непоследовательно, вряд ли скрипт валиден на протяжении всего процесса его разработки. Я, например, сначала пишу “SELECT FROM”, после чего буду рад списку доступных таблиц. Когда выберу таблицу, я переставлю каретку на SELECT, нажму на пробел и буду ждать список колонок из этой конкретной таблицы. Это очень простой пример, но он показывает, что парсер обеспечивающий работу Code Completion в IDE не может падать с исключением встречая невалидный скрипт. Нам пришлось придумать немало трюков, чтобы обеспечить корректную работу подсказки на многих подобных сценариях, но пользователи все еще присылают разные сценарии работы с незаконченными скриптами, а значит нам приходится придумывать новые трюки.

Предикатные войны

При парсинге кода, иногда, случаются такие ситуации, когда по следующему слову непонятно какую из двух альтернатив выбрать. Иногда достаточно подсмотреть на строго определенное количество слов вперед и можно будет однозначно выбрать альтернативу. Механизм разрешения такого рода неточностей называется в ANTLR lookahead. Метод парсера в этом случае строится как вложенная цепочка if-ов, каждый из которых заглядывает на одно слово дальше. Ниже пример грамматики порождающий неопределенность этого вида.

rule1:
    'a' rule2 | rule3
    ;

rule2:
    'b' 'c' 'd'
    ;

rule3:
    'b' 'c' 'e'
    ;

В середине rule1, уже пройдя token ‘a’, парсеру придется заглянуть на 2 token’а вперед, чтобы выбрать по какому правилу идти. Еще раз эта проверка будет сделана внутри правила. Эту грамматику можно переписать так, чтобы этого lookahead не было, к сожалению от таких оптимизаций часто страдает структура, а прирост производительности сравнительно не высок.

Для разрешения более сложных неопределенностей существуют более сложные механизмы. Один из них это механизм синтаксических предикатов (synpred) в ANTLR3.

На помощь он приходит в тех случаях, когда, например, не обязательное завершение одной clause пересекается с началом необязательной другой идущей следом. Предикатом, в терминах ANTLR3, называют сгенерированный метод, что совершает виртуальный проход по тексту в соответствии с одной из альтернатив и в случае успеха возвращает истину, такое завершение предиката называют успешным. Виртуальный проход еще называют проход в режиме backtracking. Если предикат отработал успешно, то совершается реальный проход. Проблемой это становится тогда, когда внутри одного предиката начинается другой, тогда один участок может быть пройден и сотню и тысячу раз.

Рассмотрим упрощенный пример. Есть 3 точки неопределенности (A,B,C).

1. Парсер входит в A, запоминает положение в тексте, начинает виртуальный проход 1-го уровня.
2. Парсер входит в B, запоминает положение в тексте, начинает виртуальный проход 2-го уровня.
3. Парсер входит в C, запоминает положение в тексте, начинает виртуальный проход 3-го уровня.
4. Парсер успешно завершает виртуальный проход 3-го уровня, возвращается на 2й и проходит С заново.
5. Парсер успешно завершает виртуальный проход 2го уровня, возвращается на 1й и проходит B и С заново.
6. Парсер успешно завершает виртуальный проход, возвращается и совершает реальный проход по A, B и С.

Таким образом все проверки внутри C будут выполнены 4 раза, B — 3 раза, A — 2 раза. А что если подходящая альтернатива вторая или третья в списке? Тогда на каком-то из этапов какой-то из предикатов завершиться неудачей, положение в тексте откатится и начнет выполнение другой предикат.

Неоднократно разбирая причину зависания приложения мы натыкались на случаи, когда “хвост” synpred был выполнен несколько тысяч раз. Synpred’ы особенно проблематичны в рекурсивных правилах. К сожалению, по своей природе, SQL рекурсивен, чего стоит хотя бы возможность использовать подзапрос почти везде. Иногда с помощью разных трюков и ухищрений получается вывернуть правило так, чтобы предикат ушел.

Очевидно, что synpred имеет негативное влияние на производительность. На каком-то этапе пришлось поставить их популяцию под четкий контроль. Проблема только в том, что при написании кода грамматики появление synpred может быть неочевидным. Более того иногда изменение одного правила приводит к появлению предиката в другом. Это невозможно контролировать вручную. Для контроля численности предикатов мы написали нехитрую регулярку, что вызывалась специальным MsBuild Task’ом. Если число предикатов отличалось от числа указанного в отдельном файле, то Task обрывал сборку и сообщал об ошибке. Видя такую ошибку, разработчик должен был несколько раз переписать код правила, пытаясь избавится от лишних предикатов, возможно, привлечь к проблеме других разработчиков. Если появление предиката неизбежно, то разработчик обновляет количество предикатов в соответствующем файле. Изменение в этом файле привлекают дополнительное внимание на ревью.

В редких случаях, мы даже писали собственные предикаты на C#, чтобы обойти те, что генерирует ANTLR. К счастью, такой механизм тоже есть.

Крутые велосипеды решения

Наследование грамматик

После анонса любых изменений в каждой из поддерживаемых нами СУБД начинается наша работа по их поддержке. Почти всегда отправной точкой в этом будет поддержка синтаксических конструкций в грамматике. Для каждого диалекта SQL мы пишем собственную грамматику, это порождает некоторое повторение кода, но в конечном счете это проще, чем искать общее между ними. Еще пару лет назад MySQL и MariaDB были очень похожи, написание отдельных грамматик было нецелесообразно. Потому те немногие конструкции, что были в MariaDB, но не было в MySQL мы поддерживали в грамматике MySQL. В этом был неприятный момент: для пользователя MySQL мы могли подсказать конструкции, что были бы не валидными. В последние года MariaDB и MySQL стали сильно расходиться с точки зрения синтаксиса и не только. Стало очевидным, что неправильно поддерживать два разных языка в рамках одной грамматики.

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

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

Приятным в разработке инструментом ANTLR делает тулинг — есть расширение для VS, есть ANTLRWorks. Внедряя механизм наследования не хотелось бы терять эту возможность. Только как тогда указать базовую грамматику? Можно придумать какую-то конвенцию по именованию файлов, но это уж совсем не очевидно. Еще одним вариантом могло быть указание такой дополнительной информации в отдельном файле, но даже сейчас, набирая эти строки, я почувствовал вонь этого решения. Выходом стало указание базовой грамматики, в грамматике наследника в формате ANTLR-комментария. Все инструменты просто проигнорируют этот текст, а мы без проблем сможем вытянуть интересующий нас код.

Требования были сформированы, настало время их реализовывать. Мы написали MsBuild Task, который был встроен в общую систему сборки как pre-build-action. Task выполнял работу препроцессора ANTLR грамматики, генерируя результирующую грамматику из базовой и наследуемой. Результирующая грамматика уже обрабатывалась самим ANTLR. Если в грамматике-наследнике встречалось правило с тем же именем, что и в родительской, базовое правило переименовывалось: к его имени после нижнего подчеркивания добавлялось имя родительской грамматики. По такому имени к нему можно было обратиться в наследнике.

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

Еще один постпроцессинг ANTLR

Во многих языках программирования, если слово является ключевым, то использовать его в качестве имени объекта уже нельзя. В SQL, в зависимости от диалекта, от 800 до 3000 ключевых слов. Большинство из них тесно связаны с предметной областью, к тому же не все вводились сразу, поэтому запрет на использования их всех в качестве имен объектов встретил бы шквал негодования. В SQL вводится понятие резервированных и не резервированных ключевых слов. Нельзя назвать объект так же как резервированное ключевое слово(SELECT, FROM etc) не квотируя его, как не резервированное(CONVERSATION, AVAILABILITY etc) — можно. Такое поведение усложняет разработку парсера. На момент лексического анализа контекст неизвестен, но парсер требует разные номера для идентификатора и ключевого слова. Для решения этой проблемы мы добавили еще один постпроцессинг к ANTLR парсеру. Постпроцессинг заменяет все явные проверки на идентификатор, на вызов специального метода. В этом методе реализована более хитрая проверка. Если на вход подан идентификатор и дальше ожидается идентификатор, то все отлично, но если на вход подается нерезервированное ключевое слово, то его нужно дополнительно проверить. Дополнительная проверка заключается в том, что метод осматривается в текущем контексте в поиске веток, где это нерезервированное ключевое слово может использоваться именно как ключевое слово и если таких веток нет, значит здесь оно может быть применено как идентификатор.

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

Ошибки

Синтаксический анализ без деревьев

Результат работы парсера, как правило — синтаксическое дерево. Синтаксическое дерево(абстрактное или конкретное) представляет собой структуру данных отражающую текст программы через призму формальной грамматики. Если вы захотите реализовать редактор кода с автодополнением для языка, что недавно придумали, изучив вопрос, вы скорее реализуете примерно следующий алгоритм:

1. Распарсить текст в редакторе. Получить синтаксическое дерево.
2. Найти узел под кареткой. Сопоставить его с грамматикой. Узнать какие ключевые слова и типы объектов будут доступны в точке.

Грамматику в этом случае удобно представить в виде графа или конечного автомата.

К сожалению, на момент начала разработки IDE ANTLR существовал в своей третьей версии. Четвертая версия переписана с нуля и кардинально отличается от третьей, по прохождению кода парсером будет автоматически сгенерировано дерево разбора без единой дополнительной строчки. В третьей версии существовал механизм при помощи которого можно было подсказать ANTLR как построить дерево, но пользоваться им было не слишком приятно. Более того, многие примеры и статьи по этой теме предлагали использовать механизм actions для выполнения кода в момент прохождения парсером правила. Этот механизм невероятно удобен и позволяет очень быстро начать получать результаты. К сожалению, это решение привело к большим архитектурным проблемам с развитием продукта и увеличению сложности поддержки новой функциональности. Дело в том, что в одном файле, в файле грамматики, начали скапливаться actions связанные с большим количеством разной функциональности, которые хорошо было бы разнести по разным сборкам. В дальнейшем мы смогли разнести обработчики самих действий по разным сборкам, реализовав довольно хитрый вариант паттерна subscriber-notifier, но сами вызовы, с передачей необходимой информации, все еще загромождают нам грамматику, усложняют поддержку новой функциональности и накладывают серьезные и неприятные ограничения на архитектуру.

Но все не так очевидно, как может показаться. Дело в том, что ANTLR3 работает значительно быстрее ANTLR4. По нашим измерениям отличия примерно в 6 раз. Кроме того, синтаксическое дерево для больших скриптов могло бы занимать много места в оперативной памяти, а до тех пор пока нам приходится выживать в 32 битном адресном пространстве Visual и SqlServer Management студий это может быть критично.

Заключение

Промежуточные итоги могут быть следующими:

• ANTLR мощный инструмент для построения парсеров
• Его преимущество над другими это инструменты, удобный синтаксис, большое количество поддерживаемых языков
• ANTLR4 был переписан с нуля и предполагает отличную от третьей версии работу с парсером
• Всегда есть способ взять от ThirdParty библиотек немного больше чем они дают
• SQL специфичный язык, построение парсеров для него — непростая задача
• Парсинг кода для задач связанных с построением IDE имеет свои особенности: нужно учитывать работу на незакноченных или невалидных скриптах

До встречи в следующей части!

Парсинг почтовых адресов из строки на C# / Хабр

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

Все бы хорошо, только засада в том, что исходные адреса клиентов были забиты в виде простой строки типа «Китежград, ул.Волшебная 22 дом кв.15». То есть, с одной стороны, о почтовых индексах никто слыхом не слыхивал, с другой же, текстовое поле ввода предлагает широкий простор для самовыражения и народно-прикладного творчества.

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

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

Для начала посмотрел в сторону Томита-парсера, но после знакомства с многостраничным конфигом примера, позволяющего по тексту определить, в каком городе кто живет (http://api.yandex.ru/tomita/doc/dg/concept/example.xml), оптимизма несколько поубавилось, но укрепилось желание написать какой-нибудь свой велосипед.

Естественно, с достаточно жесткими ограничениями на входные данные, при которых будем продолжать изыскания:

1. Адрес всегда написан без опечаток: «проспект Арфографии» пусть останется на совести вводящего.
2. Запись адреса ведется от максимально общего элемента (область) до максимально частного (номер квартиры).
3. С учетом пункта 2, забиваем болт на слова-подсказки типа «область», «улица», «проспект», «дом». Так что если в городе есть и проспект Телепузиков, и улица имени их же, то уловить столь тонкую грань мы не сможем. С учетом редкости подобной ситуации и наличием права на ошибку – вполне себе рабочий вариант.

Далее я озадачился поиском источника данных, из которого смог бы черпать сведения по почтовым индексам. Как оказалось, на сей день КЛАДР – это уже вчерашний день, ФИАС рулит (http://fias.nalog.ru). Загрузив оффлайновую копию этой базы, я принялся изучать предоставляемые ею возможности.

Особо заинтересовали меня там две таблицы: ADDROBJ – в ней хранится древовидный список всех адресных объектов, начиная с субъекта РФ и заканчивая улицей, и HOUSE<номер региона> – где хранятся номера домов с привязкой к записям в ADDROBJ вместе с их индексами. Хранящейся в этих двух таблицах информации достаточно для достижения обеих целей: проверки правильности парсинга адреса (если удалось найти адрес в базе данных, значит, мы его распознали верно), а так же для определения почтового индекса.

В голове начал вырисовываться алгоритм:

1. Разделяем строку почтового адреса на адресные элементы. Под адресным элементом подразумеваю то, запись о чем можно найти в виде строки таблицы ФИАС-а: район, город, улица, дом, а так же номер квартиры.
   1. К безусловным разделителям адресных элементов относятся точки, запятые, точки с запятой, слэши.
   2. К условным разделителям относится дефис/тире, если адресный элемент после дефиса является числом. Например в «переулок Депрессии, 38а-117» дефис является разделителем, а в «г. Усть-Зажопинск» – нет.
   3. Пробел может являться разделителем, а может и не быть им. Так в «Восьмого марта д.15» пробел между «Восьмого» и «марта», очевидно, не должен делить элементы, а между «марта» и «д.» – должен. Самый простой вариант в лоб – составить все возможные варианты разделения адресных элементов пробелами и продолжать дальнейшую работу алгоритма с каждым из них в отдельности.

2. Такие адресные элементы, как «улица» («ул»), «область» («обл») и так далее полностью выкусываются.
3. Начиная с самого первого элемента, все они последовательно прогоняются по базе ФИАС.
   1. Если элемент находится в базе, то запоминается его GUID и LEVEL (уровень в иерархии), при этом следующий элемент ищем с бОльшим значением LEVEL и фиксированным PARENTGUID равным GUID предыдущего найденного элемента.
   2. Если не найдено элемента по заданному PARENTGUID, пытаемся построить цепочку, включающую промежуточные элементы.
   3. Первоначальный поиск ведется в таблице ADDROBJ, как только ищем следующий после улицы элемент (LEVEL улицы равен 7), переключаемся на таблицу домов HOUSEXX.
   4. Если адресный элемент не найден, просто игнорируем его.

4. Побеждает вариант (а их по итогам шага 1.3. может быть несколько), у которого получилось самая длинная распознанная цепочка.
5. Для порядку она достраивается по таблице ADDROBJ до самого верха. Это нужно потому, что, например, в исходной адресной строке не было указано области и района, а сразу город.
6. Дальше немного схитрим. Номером квартиры считается последний адресный элемент (если он не был распознан как номер дома), а корпусом, строением, литерой и всем прочим – адресные элементы между распознанным номером дома и номером квартиры. Можно было бы построить более детальный анализ – таблица HOUSEXX это позволяет – но мне показалось это излишним хотя бы потому, что вряд ли почтовые индексы будут различны для домов «113» и «113 ст.1 корп 4 лит.Ж».

Алгоритм получился эмпирическим, наивным, предусматривающим не все возможные ситуации… Но для ограничений по скорости реализации и обширным правам на ошибку – он выглядел вполне удовлетворительным. Сочинить и реализовать его удалось примерно за 1 вечер.

Для привычки и удобства работы перегнал таблицы ADDROBJ и HOUSEXX из DBF в MS SQL (как их можно легко отконвертировать, прочел здесь: http://blogs.technet.com/b/isv_team/archive/2012/05/14/3497825.aspx).

В результате получился класс AddressParser, забирающий на входе строку адреса и выдающий в ответ экземпляр класса Address. В конструктор AddressParser можно подавать собственную реализацию IKnwonAddressComparator, если текущая реализация, заточенная на MS SQL чем-то не устраивает.

По скорости парсинга получилось что-то около 2-5 адресов в секунду. Плохо, но все лучше, чем ручками. Основная проблема: серьезное количество вариантов для проверки, генерируемое пунктом 1.3. По-хорошему, этот момент стоит полностью переписать, используя базу адресов уже на этом этапе для проверки существования адресных элементов. В качестве промежуточного варианта можно ограничить количество вариантов неким значением.

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

Распределение по ошибкам получилось следующее:

• 37% — опечатки. Как правило, банальные пропуски-добавления букв: «Киирова», «Москв»…
• 21% — использование сокращений: «К.Маркса», «Р.Люксембург»…
• 42% — отсутствие домов в базе ФИАС, и, в результате, невозможность определить индекс и завалидировать всю цепочку. Весьма неожиданная для меня причина, хотя многие пишут, что ФИАС все еще сыроват для промышленного применения

Какие выводы можно сделать?

Если нужно, как и мне, невысокое качество парсинга и низкая скорость – можно использовать.

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

Производительность – это отдельная песня, которой, учитывая элементарную и неоптимальную реализацию – так же можно заняться. Первый кандидат здесь – умное разбиение по пробелам.

Но все это – уже совсем другая история.

Исходные коды можно загрузить отсюда: https://yadi.sk/d/muzi9b6qZ8DWh

Тестовую MS SQL базу с домами по 38 и 78 регионам можно взять здесь: https://yadi.sk/d/ERXyDXv7Z8Dab

Парсим русский язык / Хабр

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

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

"Мама мыла раму":

(предложение
    (именная гр. (сущ мама))
    (глаг. гр. (глаг мыла)
        (именная гр. (сущ раму)))
    (. .)))

Это называется синтаксическим деревом предложения. В графическом виде его можно представить следующим образом (в упрощенном виде):

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

На хабре уже было несколько статей про парсинг предложений (1, 2), а на конференции Диалог даже проводятся соревнования парсеров. Однако, в этой статье я хотел бы рассказать о том как же именно парсить русский язык, заместо сухой теории.

Проблемы и задачи

Итак, зачем я хочу парсить русский язык и почему это является нерешенной проблемой? Во-первых, парсить человеческие языки (в отличие от компьютерных) сложно из-за большого количества неоднозначностей (напр. омонимия), исключений из правил, новых слов и пр. Во-вторых, большое количество разработок и исследований существует для английского языка, но гораздо меньше для русского. Найти открытый парсер для русского практически невозможно. Все существующие наработки (например, ЭТАП, ABBYY и прочие) закрыты для публики. Тем не менее, для любой серьезной задачи анализа текстов необходимо иметь синтаксический парсер.

Немного теории

Несмотря на то, что это практическая статья, а не теоретическая, мне необходимо дать немного теории, чтобы знать, чем мы будем заниматься. Итак, пусть у нас есть простое предложение «Мама мыла раму.» Что мы хотим получить в качестве результата от парсера? Существует большое количество моделей, описывающих человеческие языки, из которых я бы выделил две наиболее популярных:

1. Грамматика составляющих (constituency grammar)
2. Грамматика зависимостей (dependency grammar)

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

• разбиваем предложение на именную и глагольную группы
• именную группу разбиваем на существительное (мама)
• глагольную группу на глагол (мыла) и на вторую именную группу
• вторую глагольную группу на существительное (раму)

Чтобы разобрать предложение использую грамматику составляющих, можно воспользоваться парсерами формальных языков (про это было много статей на хабре: 1, 2). Проблема будет впоследствии в снятии неоднозначностей, т.к. одному и тому же предложению будут соответствовать несколько синтаксических деревьев. Однако, самая большая проблема заключается в том, что грамматика составляющих не очень хорошо подходит для русского языка, т.к. в русском языке порядок слов в предложении зачастую можно менять местами, не меняя смысла. Для русского нам лучше подойдет грамматика зависимостей.

В грамматике зависимостей порядок слов не важен, т.к. мы хотим лишь знать от какого слова зависит каждое слово в предложении и тип этих связей. На примере это выглядит так:

В данном предложении «мама» зависит от глагола «мыть» и является субъектом, «рама» также зависит от глагола «мыть», но является «объектом». Даже если мы поменяем порядок слов в предложении, связи все равно останутся теми же. Итак, от нашего парсера мы хотим получить список зависимостей для слов в предложении. Это может выглядеть так:

"Мама мыла раму":

субъект(мама, мыла)
объект(раму, мыла)

На этом с теорией закончим и перейдем к практике.

Существующие подходы

Существует два основных подхода при создании синтаксического парсера:

1. Метод, основанный на правилах (rule based)
2. Машинное обучение с учителем (supervised machine learning)

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

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

1. слово («мама») в именительном падеже, женском роде и единственном числе должно зависеть от глагола («мыла») в единственном числе, прошедшем времени, женском роде и тип связи должен быть «субъект»
2. слово («раму») в винительном падеже должно зависеть от глагола и тип связи должен быть «объект»

В системе может быть много подобных правил, а также анти-правил, которые указывают, когда НЕ нужно проставлять связи, например, если у существительного и глагола различаются род или число, то между ними нет связи. Также существуют правила третьего типа, которые указывают какую пару слов следует предпочесть, если возможны несколько вариантов. Например, в предложении «мама мыло окно»: и «мама», и «окно» могут выступать в качестве субъекта, однако, мы можем предпочесть предстоящее глаголу слово, чем последующее.
Данный подход очень ресурсоемок, т.к. для создания парсера требуется хорошая команда лингвистов, которые должны буквально описать весь русский язык. Поэтому нам более интересен второй подход — машинное обучение с учителем.

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

1	Мама	сущ.им.ед.жен.	2	субъект
2	мыла	глаг.ед.жен.прош	0	-
3	раму	сущ.вин.ед.жен.	2	объект

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

1. номер слова в предложении (1)
2. словоформа (мама)
3. грамматические категории (сущ.им.ед.жен.)
4. номер главного слова (2)
5. тип связи (субъект)

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

Обучаем парсер

Есть несколько открытых парсеров, которые можно обучить для работы с русским языком. Вот два, которые я пробовал обучать:

1. MST Parser, основанных на задаче нахождения минимального остовного дерева
2. MaltParser, основан на машинном обучении (хотя и MST Parser тоже, но там немного другая идея)

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

> wget http://maltparser.org/dist/maltparser-1.7.1.tar.gz
> tar xzvf maltparser-1.7.1.tar.gz
> cd maltparser-1.7.1

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

Чтобы обучить новую языковую модель нам потребуется размеченный корпус. Для русского существует на данный момент только один синтаксически размеченный корпус — СинТагРус, который входит в состав НКРЯ. Мне удалось получить доступ к СинТагРус на условиях нераспространения и исследовательских целей. Корпус представляет собой набор текстов размеченных в формате XML:

<S>
<W DOM="2" FEAT="S ЕД МУЖ ИМ НЕОД" LEMMA="КАБИНЕТ" LINK="предик">Кабинет</W>
<W DOM="_root" FEAT="V НЕСОВ ИЗЪЯВ ПРОШ ЕД МУЖ" LEMMA="ОТЛИЧАТЬСЯ">отличался</W>
<W DOM="2" FEAT="S ЕД ЖЕН ТВОР НЕОД" LEMMA="СКРОМНОСТЬ" LINK="2-компл">скромностью</W>,
<W DOM="3" FEAT="A ЕД ЖЕН ТВОР" LEMMA="ПРИСУЩИЙ" LINK="опред">присущей</W>
<W DOM="4" FEAT="S ЕД МУЖ ДАТ ОД" LEMMA="СЕМЕН" LINK="1-компл">Семену</W>
<W DOM="5" FEAT="S ЕД МУЖ ДАТ ОД" LEMMA="ЕРЕМЕЕВИЧ" LINK="аппоз">Еремеевичу</W>.
</S>

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

Кабинет 		S.m.nom.sg      2       предик
отличался       	V.m.real.sg     0       ROOT
скромностью     	S.f.ins.sg      2       2-компл
присущей        	A.f.ins.sg      3       опред
Семену  		S.dat.m.sg      4       1-компл
Еремеевичу      	S.dat.m.sg      5       аппоз

В документации говорится, что для обучения парсера его необходимо запустить со следующими параметрами:

> java -jar maltparser-1.7.1.jar -c russian -i /path/to/corpus.conll -m learn
-с название модели (на выходе получится файл russian.mco)
-i входной файл - размеченный корпус
-m режим работы, в данном случае это learn - обучение

Однако, я запускал обучение с дополнительными аргументами:

> java -Xmx8000m -jar maltparser-1.7.1.jar -c russian -i /path/to/corpus.tab -if appdata/dataformat/malttab.xml -m learn -l liblinear
-Xmx8000m увеличиваем доступную память
-if appdata/dataformat/malttab.xml изменяем формат входных данных на malttab (по умолчанию парсер использует формат CoNLL, но он сложнее)
-l liblinear используем для обучения линейные SVM вместо более медленной библиотеки LIBSVM

В итоге мы получим файл russian.mco, который содержит обученную модель и необходимые конфигурационные данные. Теперь у нас есть все (ну или почти все), что нужно, чтобы парсить русские тексты.

Парсим русский язык

Запуск парсинга производится следующим образом:

> java -jar maltparser-1.7.1.jar -c russian -i /path/to/input.tab -o out.tab -m parse
-с название нашей модели
-i входной файл, который необходимо распарсить
-o выходной файл, куда будет записан результат
-m parse режим парсинга

Единственное, что нам нужно для парсинга произвольного текста — это скрипт, который бы подготовил текст в формат malttab. Для этого скрипт должен:

1. Разбить текст на предложения (сегментация на предложения)
2. Разбить каждое предложение на слова (токенизация)
3. Определить грамматические категории для каждого слова (морфологический анализ)

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

Я произвел обучение на 1/6 части СинТагРус и получил модель для русского языка, которую вы можете попросить для личных целей. Чтобы ею воспользоваться, нужно чтобы грамматические категории совпадали с теми, которые использовал я при обучении модели.

Данная модель показала точность (accuracy) в 78,1%, что довольно таки неплохо и для большинства целей вполне подходит. Модель, обученная на всем корпусе дает точность в 79,6%.

Заключение

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

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

Я выложил простое онлайн демо, которое, пока не упало, выглядит так:

Весь код (кроме корпуса) доступен здесь: github.com/irokez/Pyrus

В заключение я хотел бы поблагодарить НКРЯ, а в частности ИППИ РАН за предоставление доступа к СинТагРус.

Умный парсер числа, записанного прописью / Хабр

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

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

Для ленивых:

Ссылка на проект github: ссылка.

В данном разделе будут описаны использованные алгоритмы. Осторожно, много букв!

Постановка задачи

По работе мне требуется распознать текст из печатного документа, сфотографированного камерой смартфона/планшета. Из-за соглашения о неразглашении информации я не могу привести пример фотографии, но суть в том, что в документе имеется таблица, в которой записаны некие показатели числом и прописью, и эти данные необходимо прочитать. Парсинг текста прописью необходим как дополнительный инструмент валидации, чтобы убедиться, что число распознано верно. Но, как известно, OCR не гарантирует точного распознавания текста. Например, число двадцать, записанное прописью, может быть распознано как «двадпать» или даже как «двапать». Нужно это учесть и извлечь максимальное количество информации, оценив величину возможной ошибки.

Примечание. Для распознавания текста я использую tesseract 4. Для .NET нет готового NuGet-пакета четвертой версии, поэтому я создал такой из ветки основного проекта, может кому пригодится: Genesis.Tesseract4.

Базовый алгоритм парсинга числа

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

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

Итак, возьмем небольшое число, например «сто двадцать три». Оно состоит из трех слов (токенов), каждому из которых соответствует число, все эти числа суммируются:

"сто двадцать три" = сто + двадцать + три = 100 + 20 + 3 = 123

Пока все просто, но копнем глубже, например рассмотрим число «двести двенадцать тысяч сто пять».

"двести двенадцать тысяч сто пять" = (двести + двенадцать) × тысяч + (сто + пять) = 212 * 1.000 + 105 = 212.105.

Как видим, когда в числе присутствуют тысячи (а также миллионы и прочие степени тысячи), число делится на части, состоящие из локального маленького числа, в примере выше – 212, и множителя (1000). Таких фрагментов может быть несколько, но все они идут по убыванию множителя, например, за тысячей не может последовать миллион или еще одна тысяча. Это верно также и для частей маленького числа, так за сотнями не могут последовать сотни, а за десятками — десятки, поэтому запись «сто пятьсот» неверна. Характеристику, относящую два токена к одному типу, назовем уровнем, например, токены «сто» и «триста» имеют один уровень, и он больше, чем у токена «пятьдесят».

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

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

Теперь перейдем к парсингу. Заведем четыре величины:

1. Глобальный уровень (globalLevel). Указывает, какой уровень был у последнего множителя. Изначально не определен и необходим для контроля. Если мы встретим токен-множитель, у которого уровень больше или равен глобальному, то это ошибка.
2. Глобальное значение (globalValue). Общий сумматор, куда складывается результат результат перемножения локального числа и множителя.
3. Локальный уровень (localLevel). Указывает, какой уровень был у последнего токена. Изначально не определен, работает аналогично глобальному уровню, но сбрасывается после обнаружения множителя.
4. Локальное значение (localValue). Сумматор токенов, не являющихся множителями, т.е. чисел до 999.

Алгоритм выглядит следующим образом:

1. Разбиваем строку на токены с помощью регулярки «\s+».
2. Берем очередной токен, получаем информацию о нем из образца.
3. Если это множитель:
   • Если задан глобальный уровень, то убеждаемся, что он больше или равен уровню токена. Если нет – это ошибка, число некорректно.
   • Устанавливаем глобальный уровень на уровень текущего токена.
   • Умножаем величину токена на локальное значение и добавляем результат к глобальному значению.
   • Очищаем локальное значение и уровень.

4. Если это не множитель:
   • Если задан локальный уровень, то убеждаемся, что он больше или равен уровню токена. Если нет – это ошибка, число некорректно.
   • Устанавливаем локальный уровень на уровень текущего токена.
   • Прибавляем к локальному значению величину токена.

5. Возвращаем результат как сумму глобального и локального значений.

Пример работы для числа «два миллиона двести двенадцать тысяч сто восемьдесят пять».

Результатом будет 2.212.185.

Умный парсинг

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

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

Я выделил три вида ошибок, с которыми столкнулся в процессе работы:

1. Замена символов на другие со схожим начертанием. Например, буква «ц» почему-то заменяется на «п», а «н» на «и» и наоборот. При использовании третьей версии tesseract возможна замена буквы «о» на ноль. Эти ошибки, навскидку, самые распространенные, и требуют тюнинга под конкретную библиотеку распознавания. Так так принципы работы tesseract версий 3 и 4 имеют кардинальные различия, поэтому и ошибки там будут разными.
2. Слияние токенов. Слова могут сливаться воедино (обратного пока не встречал). В комбинации с первой ошибкой порождает демонические фразы типа «двапатьодин». Попробуем раздраконить и таких монстров.
3. Шум – левые символы и фразы в тексте. К сожалению, здесь мало что можно сделать на данный момент, но перспектива есть при сборе достаточно весомой статистики.

При этом сам алгоритм разбора, описанный выше, почти не меняется, главное различие в разбиении строки на токены.

Но начнем со сбора небольшой статистики использования букв в токенах. Из 33 букв русского языка при написании неотрицательных целых чисел используются только 20, назовем их хорошими буквами:

авдеиклмнопрстцчшыья

Остальные 13, соответственно, назовем плохими буквами. Максимальный размер токена при этом составляет 12 символов (13 при счете до квадриллионов). Подстроки длиной больше этой величины нужно разбивать.

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

Небольшой ликбез: расстояние Левенштейна – частный случай алгоритма Вагнера-Фишера, когда стоимость вставки, удаления и замены символов статичны. В нашей задаче это не так. Очевидно, что если в подстроке мы встречаем плохую букву, то ее нужно заменить на хорошую, а вот заменять хорошую на плохую крайне нежелательно. Вообще говоря, нельзя, но ситуация зависит от конкретной задачи.

Для описания стоимости вставки, удаления и замены символов я создал такую таблицу: ссылка на таблицу с весами. Пока она заполнена методом трех П (пол, палец, потолок), но если заполнить ее данными на основе статистики OCR, то можно значительно улучшить качество распознавания чисел. В коде библиотеки присутствует файл ресурсов NumeralLevenshteinData.txt, в который можно вставить данные из подобной таблицы с помощью Ctrl+A, Ctrl+C и Ctrl+V.

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

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

• Уровень ошибки. Вещественное число от 0 (ошибки нет) до 1 (токен некорректен), означающее, насколько хорошо токен был сопоставлен с образцом.
• Признак использования токена. При разборе строки с вкраплениями мусора, часть токенов будет отброшена, для них данный признак выставляться не будет. При этом итоговая величина ошибки будет считаться как среднее арифметическое от ошибок использованных токенов.

Алгоритм анализа токенов:

1. Пытаемся найти токен в таблице как есть. Если находим – все хорошо, возвращаем его.
2. Если нет, то составляем список возможных вариантов:

3. Пытаемся сопоставить токен с образцом с помощью алгоритма Вагнера-Фишера. Данный вариант состоит из одного токена (сопоставленного образца) и его ошибка равна лучшему расстоянию, поделенному на длину образца.

   Пример: токен «нуль» сопоставляется с образцом «ноль», при этом расстояние равно 0.5, т.к. стоимость замены плохой буквы «у» на хорошую «о» равна 0.5. Общая ошибка для данного токена будет 0.5 / 4 = 0.125.

4. Если подстрока достаточно большая (у меня это 6 символов), пытаемся поделить ее на две части минимум по 3 символа в каждой. Для строки в 6 символов будет единственный вариант деления: 3+3 символа. Для строки в 7 символов – уже два варианта, 3+4 и 4+3, и т.д. Для каждого из вариантов вызываем рекурсивно эту же функцию анализа токенов, заносим полученные варианты в список.

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

   Пример: токен «двапать» имеет прямое сопоставление с образцом «двадцать», ошибка 0.25. Кроме того, лучшим вариантом деления является «два» + «пять» стоимостью 0.25 (замена «а» на «я»), ухудшенная искусственно до 0.35, в результате чего предпочтение отдается токену «двадцать».

5. После составления всех вариантов выбираем лучший по минимальной сумме ошибок участвующих в нем токенов. Результат возвращаем.

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

Алгоритм в двух словах для тех, кому было лень читать текст выше

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

Заточка алгоритма под конкретную задачу

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

Дальнейшее улучшение

У существующего алгоритма есть и недоработки:

1. Контроль падежей. Строки «две тысячи» и «два тысячей» будут с нулевой ошибкой распознаны как 2000. В моей задаче контроль падежей не требуется, он даже вреден, но если вам нужна такая функция, это решается введением дополнительного флага в токен, отвечающего за падеж следующего токена.
2. Отрицательные числа. Вводится дополнительный токен «минус» с особой обработкой. Ничего сложного, но не забудьте, что буква «у» является плохой, и не встречается в числительных, нужно будет изменить ее весовые характеристики или надеятся, что она не изменится в процессе OCR.
3. Дробные числа. Решается заменой типа long на double и введением токенов «десятых», «сотых» и т.п… Не забудьте пересмотреть весы букв.
4. Распознавание чисел, введенных пользователями. Т.к. при вводе текста вручную мы чаще всего допускаем ошибки, связанные с переТСановкой сиВМолов, следует добавить эту операцию в алгоритм Вагнера-Фишера.
5. Поддержка других языков. Вводим новые токены, расширяем таблицу весов.
6. Обработка мусора. В некоторых документах на данные налезает печать, качество изображением может быть плохим, ячейка может быть банально пустой. В этом случае в строку попадает мусор, который нужно как-то чистить. Лучшее, что я могу предложить на данный момент – производить предварительную обработку документа перед OCR. Мне очень сильно помогло удаление линий таблицы и заливка их цветом, близким к цвету свободного пространства ячейки. Это не решило все проблемы, но улучшило качество распознавания текста с документов, где таблица имела искривления из-за помятости документа или криворукого фотографа. В идеале стоит доворачивать саму ячейку и распознавать ее отдельно, если у вас, конечно, вообще имеется таблица.

В проекте есть пример консольного приложения, бегущего по файлу samples.txt с примерами для парсера. Вот скриншот результатов:

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

Что касается последнего раздела, мне всегда было интересно, сколько же это – «дофига». Также программа дала вполне себе адекватный ответ, сколько нужно принимать на посошок (я не употребляю, но все же) и даже точно определила значение древнерусского слова «тьма». И да, в вывод не вошла еще одна мера, которую воспитание добавить не позволило, но программа считает, что она равна тысяче =)

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

Сама библиотека написана под .NET Standart 2.0 и C# 7.x, а алгоритмы легко переводятся на другие языки.

На случай возможного расширения библиотеки добавлю состав важных составляющих парсера чисел прописью (пространство имен Genesis.CV.NumberUtils):

• RussianNumber.cs – непосредственно парсер
• RussianNumber.Data.cs – файл с описанием токенов
• RussianNumber.ToString.cs – конвертер числа в текст прописью
• RussianNumberParserOptions.cs – опции парсера
• NumeralLevenshtein.cs – реализация алгоритма Вагнера-Фишера
• NumeralLevenshteinData.txt – ресурс, данные весов букв

Использование:

• RussianNumber.ToString(value) – преобразование числа в текст
• RussianNumber.Parse(value, [options]) – преобразование текста в число

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

Понравилась статья? Посмотрите другие:

Эффективный парсинг на С/С++ | WASM

Эта идиома предложена Джеймсом Коплином (James Coplien), который назвал ее «виртуальным
конструктором». Что делает следующий перегруженный оператор new?

Код (Text):

1. class Foo {

2. public:

3.      void* operator new(size_t, void* p) { return p; }

4. };

На первый взгляд — ничего; пустая трата времени. Но так ли это? Что произойдет в следующем
фрагменте?

Код (Text):

1. union U {

2.     Foo foo;

3.     Bar bar;

4.     Banana banana;

5. };

6. U whatIsThis;

Компилятор С++ не может определить, какой конструктор следует вызывать для whatIsThis —
Foo::Foo(), Bar::Bar() или Banana::Banana(). Разумеется, больше одного конструктора
вызывать нельзя, поскольку все члены занимают одно и то же место в памяти, но без инструкций от вас
не может выбрать нужный конструктор. Как и во многих других ситуациях, компилятор поднимет
руки; он сообщает об ошибке и отказывается принимать объединение, члены которого имеют
конструкторы. Если вы хотите, чтобы одна область памяти могла инициализироваться несколькими
различными способами, придется подумать, как обмануть компилятор. Описанный выше «пустой»
конструктор подойдет лучше всего.
unsigned char space[4096];
Foo* whatIsThis = new(&space[0]) Foo;
Фактически происходит то, что в С++ происходить не должно — вызов конструктора. При этом память
на выделяется и не освобождается, поскольку оператор new ничего не делает. Тем не менее,
компилятор С++ сочтет, что это новый объект, и все равно вызовет конструктор. Если позднее вы
передумаете и захотите использовать ту же область памяти для другого объекта, то сможете снова
вызвать хитроумный оператор new и инициализировать ее заново.
При создании объекта оператором new компилятор всегда использует двухшаговый процесс:
1. Выделение памяти под объект.
2. Вызов конструктора объекта.
Этот код запрятан в выполняемом коде, генерируемом компилятором, и в обычных ситуациях второй
шаг не выполняется без первого. Идиома виртуального конструктора позволяет надеть повязку на глаза
компилятору и обойти это ограничение.

Нажмите, чтобы раскрыть…

Синтаксический анализатор строк в C и C #

Переполнение стека

1. Около

2. Продукты

3. Для команд

1. Переполнение стека
   Общественные вопросы и ответы

2. Переполнение стека для команд
   Где разработчики и технологи делятся частными знаниями с коллегами

3. Вакансии
   Программирование и связанные с ним технические возможности карьерного роста

4. Талант
   Нанимайте технических специалистов и создавайте свой бренд работодателя

5. Реклама
   Обратитесь к разработчикам и технологам со всего мира

6. О компании

Загрузка…

.

Бесплатный онлайн-анализатор URL-адресов / разделитель строк запроса

Этот простой инструмент позволяет анализировать URL-адрес на отдельные компоненты, например схему, протокол, имя пользователя, пароль, имя хоста, порт, домен, субдомен, tld, путь, строку запроса, хэш и т. Д.
Он также разбивает строку запроса в удобочитаемый формат и выполняет декодирование параметров.

Этот инструмент использует библиотеку URI.js, разработанную Родни Ремом.

Чтобы узнать больше о структуре URL-адреса, ознакомьтесь с разделом «Объяснение URL-адресов» на этой странице.

URL частей

Разъясненные URL

Что такое URI?

Унифицированные идентификаторы ресурсов (URI) используются для идентификации «имен» или «ресурсов».Они бывают двух видов: URN и URL. Фактически, URI может быть как именем, так и указателем!

Что такое URL?

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

Что такое URN?

Унифицированные имена ресурсов — это идентификаторы ресурсов.Они не зависят от местоположения и используют схему urn :.

Каков синтаксис URI?

 схема: часть-специфическая-схема? Запрос # фрагмент 

Примеры из RFC:
• ftp://ftp.is.co.za/rfc/rfc1808.txt
• http://www.ietf.org/rfc/rfc2396.txt
• ldap: // [2001: db8 :: 7] / c = GB? ObjectClass? One
• новости: comp.infosystems.www.servers.unix
• тел: + 1-816-555-1212
• телнет: // 192.0.2.16: 80/
• урна: оазис: имена: спецификация: docbook: dtd: xml: 4.1.2

Каков синтаксис URL-адреса?

 схема: // имя пользователя: пароль@subdomain.domain.tld: порт / путь / имя-файла.suffix? Строка-запроса # хэш 

Примеры:
• http://www.google.com
• http: // foo: [email protected]/very/long/path.html? P1 = v1 & p2 = v2 # подробнее
• https://secured.com:443
• ftp: // ftp.bogus.com/~some/path/to/a/file.txt

Каков синтаксис URN?

 urn: namespame-identifier: строка, зависящая от пространства имен 

Примеры из Википедии:
• Урна: isbn: 0451450523
• урна: ietf: rfc: 2648
• урна: uuid: 6e8bc430-9c3a-11d9-9669-0800200c9a66

Что такое «информация пользователя» в URL-адресе?

Часть userinfo URL-адреса состоит из имени пользователя и / или пароля .Они не являются обязательными и используются для аутентификации. Информация о пользователе имеет формат имя пользователя: пароль и следует за ним.
символом @ и хостом. Пароль не является обязательным, часто пользовательский интерфейс предлагает ввести пароль.

Примеры:
• ftp: // имя пользователя: пароль @ host.com /
• ftp: // имя пользователя @ host.com /

Что такое «авторитет» в URL-адресе?

Авторитет URL состоит из информации пользователя , имени хоста и порта .Информация о пользователе и порт не являются обязательными. Когда порт отсутствует, предполагается порт по умолчанию для конкретной схемы.
Например, порт 80 для http или 443 для https.

Примеры:
• имя пользователя: [email protected]/
• subdomain.domain.com
• www.superaddress.com:8080

Что такое «фрагмент» в URL-адресе?

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

Пример:
• http://www.foo.bar/?listings.html # section-2

Что такое «путь» в URL-адресе?

Путь URL-адреса состоит из сегментов, которые представляют собой структурированную иерархию. Каждый сегмент отделяется символом /. Вы можете думать о пути как о структуре каталогов.

Пример:
• http://www.foo.bar / segment1 / segment2 / some-resource.html
• http://www.foo.bar /image-2.html ? W = 100 & h = 50
• ftp://ftp.foo.bar / ~ john / doe ? W = 100 & h = 50

Что такое «строка запроса» в URL-адресе?

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

Примеры:
• http: // www.foo.bar/image.jpg ? высота = 150 и ширина = 100
• https://www.secured.com:443/resource.html ? Id = 6e8bc430-9c3a-11d9-9669-0800200c9a66 # some-header

.