Как перестать бояться и полюбить синтаксический анализ?01.11.2016 10:48

Недавно мы написали синтаксический анализатор языка запросов 1С и его транслятор в обычный SQL. Это позволило нам выполнять запросы к 1С без участия 1С :) Минимальная рабочая версия на regexp-ах получилась недели за две. Ещё месяц ушёл на полноценный парсер через грамматики, разгребание нюансов структуры БД разных 1С-объектов и реализацию специфических операторов и функций. В результате решение поддерживает практически все конструкции языка, исходный код выложен на GitHub.

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

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

Мы задумались: как можно облегчить бухгалтерам жизнь?

Оказалось, что много проблем с отчётностью возникает из-за мелких ошибок в бухгалтерской базе:

• дубликаты контрагента или договора;
• дубликаты первичных документов;
• контрагент без ИНН;
• документ с датой из далёкого прошлого или будущего.

Выполнять эти запросы через стандартное COM апи 1С — не лучшая идея. Во-первых, это долго — обойти тысячу баз и запустить на каждой из них все запросы занимает 10 часов. Во-вторых, это существенно нагружает сервер 1С, которому обычно и так несладко живётся. Неприятно ради аудита замедлять текущую ежедневную работу людей.

Между тем, типичный запрос 1С выглядит так:

select
	doc.Дата as Date,
	doc.Номер as Number,
	doc.Организация.ИНН as Inn,
	doc.Контрагент.ИНН as CounterpartyInn,
	Представление(doc.Контрагент.ЮридическоеФизическоеЛицо) as CounterpartyType,
	doc.НазначениеПлатежа as Description,
	doc.СуммаДокумента as Sum
from Документ.ПоступлениеНаРасчетныйСчет doc
where
not doc.ДоговорКонтрагента.ПометкаУдаления
and doc.Проведен
and doc.видоперации = Значение(Перечисление.ВидыОперацийПоступлениеДенежныхСредств.ОплатаПокупателя)	
and ГОД(doc.Дата) = ГОД(&Now)

Реальных причин тому три:

1. Магические имена таблиц и колонок в базе. Это легко решается, так как 1С документирует их соответствие именам из запроса.
2. Вложенные свойства. Например, doc.Организация.ИНН в SQL соответствует left join двух табличек Документ.ПоступлениеНаРасчетныйСчет и Справочник.Организации.
3. Специфические для 1С операторы и функции, такие как Значение, Представление и Год. Их тоже нужно дополнительно транслировать в соответствующие конструкции СУБД.

Больше всего хлопот доставили вложенные свойства. 1С хранит их в связанных таблицах, поэтому приходилось исходное имя объекта в конструкции from заменять на подзапрос, в котором были все нужные left join-ы.

select
doc.Контрагент.ИНН
from Документ.ПоступлениеТоваровУслуг doc

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

select
	doc.gen0
from (select
	tContractor.inn gen0
from tDoc
left join tContractor on tDoc.contractorId = tContractor.id) doc

Использование regexp-ов оказалось верным решением, так как позволило быстро получить конечный результат и понять, что из всей этой затеи получается что-то полезное. Всем советуем proof of concept-ы и эксперименты делать именно так — максимально простыми подручными средствами. А что может быть проще и эффективнее при работе с текстами, чем regexp-ы?

Конечно, есть и недостатки. Первый и очевидный — это срезанные углы и ограничения синтаксиса. Regexp-ы для свойств и таблиц требовали расстановки псевдонимов в запросе и, вообще, могли случайно заматчиться с какой-нибудь другой конструкцией, например, константной строкой.

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

Так, например, выглядел код, который добавлял условие на равенство областей ко всем join-ам:

private string PatchJoin(string joinText, int joinPosition, string alias)
{
    var fromPosition = queryText.LastIndexOf("from", joinPosition, StringComparison.OrdinalIgnoreCase);
    if (fromPosition < 0)
        throw new InvalidOperationException("assertion failure");
    var tableMatch = tableNameRegex.Match(queryText, fromPosition);
    if (!tableMatch.Success)
        throw new InvalidOperationException("assertion failure");
    var mainTableAlias = tableMatch.Groups[3].Value;
    var mainTableEntity = GetQueryEntity(mainTableAlias);
    var joinTableEntity = GetQueryEntity(alias);
    var condition = string.Format("{0}.{1} = {2}.{3} and ", mainTableAlias,
        mainTableEntity.GetAreaColumnName(), alias, joinTableEntity.GetAreaColumnName());
    return joinText + condition;
}

Согласитесь, что такой вариант выглядит гораздо проще и понятнее предыдущего:

private void PatchJoin(SelectClause selectClause, JoinClause joinClause)
{
    joinClause.Condition = new AndExpression
    {
        Left = new EqualityExpression
        {
            Left = new ColumnReferenceExpression
            {
                Name = PropertyNames.area,
                Table = selectClause.Source
            },
            Right = new ColumnReferenceExpression
            {
                Name = PropertyNames.area,
                Table = joinClause.Source
            }
        },
        Right = joinClause.Condition
    };
}

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

Для примера рассмотрим такой запрос:

select p.surname as 'person surname'
from persons p
where p.name = 'иван'

Такую объектную модель можно собрать через код следующим образом:

var table = new TableDeclarationClause
{
    Name = "PersonsTable",
    Alias = "t"
};
var selectClause = new SelectClause
{
    FromExpression = table,
    WhereExpression = new EqualityExpression
    {
        Left = new ColumnReferenceExpression
        {
            Table = table,
            Name = "name"
        },
        Right = new LiteralExpression
        {
            Value = "иван"
        }
    }
};
selectClause.Fields.Add(new SelectFieldExpression
{
    Expression = new ColumnReferenceExpression
    {
        Table = table,
        Name = "surname"
    }
});

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

Поэтому мы решили написать свой парсер. Синтаксические анализаторы обычно начинают делать с описания грамматики того языка, который требуется распознать. Формальная грамматика — классический инструмент описания структуры языков программирования. Её основу составляют правила вывода, то есть рекурсивные определения каждой языковой конструкции.

Например, такими правилами можно описать язык арифметических выражений:

E → number | (E) | E + E | E - E | E * E | E / E

• любое число (number) — это выражение (E);
• если выражение заключено в скобки, то всё это, вместе со скобками — тоже выражение;
• два выражения, соединенные арифметической операцией, так же составляют выражение.

Существуют специальные инструменты — генераторы синтаксических анализаторов, которые по описанию языка, заданному в виде грамматики, умеют генерировать распознающий этот язык код. Самые известные из них — это yacc, bison и antlr. Для C# есть менее распространённая библиотека Irony. Про неё уже была небольшая статья на Хабре, а вот пост Скотта Хансельмана про неё.

Основная фишка библиотечки Irony в том, что правила грамматики можно описывать прямо на C#, используя перегрузку операторов. В итоге получается вполне симпатичный DSL, по форме очень похожий на классическую форму записи правил:

var e = new NonTerminal("expression");
var number = new NumberLiteral("number");
e.Rule = e + "+" + e | e + "-" + e | e + "*" + e | e + "/" + e | "(" + e + ")" | number;

Irony разделяет понятия Parse Tree и Abstract Syntax Tree.

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

Например, выражению 1+(2+3) при применении правил:

e1: E → E + E
e2: E → (E)
e3: E → number

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

Например, AST для грамматики выше может состоять всего из одного класса BinaryOperator:

public enum OperatorType
{
    Plus,
    Minus,
    Mul,
    Div
}
public class BinaryOperator
{
    public object Left { get; set; }
    public object Right { get; set; }
    public OperatorType Type { get; set; }
}

Когда мы таким образом доходим до корневого нетерминала, в его AstNode образуется корневой узел AST, в нашем случае — SqlQuery.

Для грамматики арифметических выражений выше AstNodeCreator может выглядеть так:

var e = new NonTerminal("expression",
delegate(AstContext context, ParseTreeNode node)
{
    //соответствует правилу E → number,
    if (node.ChildNodes.Count == 1)
    {
        node.AstNode = node.ChildNodes[0].Token.Value;
        return;
    }
    //правила вида E → E op E
    if (node.ChildNodes[0].AstNode != null && node.ChildNodes[2].AstNode != null)
    {
        node.AstNode = new BinaryOperator
        {
            Left = node.ChildNodes[0].AstNode,
            Operator = node.ChildNodes[1].FindTokenAndGetText(),
            Right = node.ChildNodes[2].AstNode
        };
        return;
    }
    //правило со скобками
    node.AstNode = node.ChildNodes[1].AstNode;
});

Итак, с помощью Irony мы научились конструировать AST по исходному запросу. Остался лишь один большой вопрос — как эффективно структурировать код для преобразования AST, ведь в конечном счете из исходного AST нам нужно получить AST результирующего SQL запроса. В этом нам поможет паттерн Visitor.

Какую проблему решают visitor-ы?
Самая естественная и необходимая вещь, которую часто приходится делать при работе с AST — это превращать его в строку. Возьмем к примеру наш AST: после замены русских имён таблиц на английские, генерации left join-ов и преобразования 1С-операторов в операторы БД, на выходе нам нужно получить строку, которую мы сможем отдать на выполнение в PostgreSQL.

Возможный вариант решения этой задачи таков:

internal class SelectClause : ISqlElement
{
    //...
    public void BuildSql(StringBuilder target)
    {
        target.Append("select ");
        for (var i = 0; i < Fields.Count; i++)
        {
            if (i != 0)
                target.Append(",");
            Fields[i].BuildSql(target);
        }
        target.Append("\r\nfrom ");
        From.BuildSql(target);
        foreach (var c in JoinClauses)
        {
            target.Append("\r\n");
            c.BuildSql(target);
        }
    }
}

• все узлы дерева должны иметь метод BuildSql, чтобы рекурсия работала;
• метод BuildSql на SelectClause перевызывает BuildSql на всех дочерних узлах.

Это означает, что если следовать той же структуре кода, что и выше, то мы должны будем:

• добавить метод AddAreaToJoinClause во все узлы дерева;
• его реализации на всех узлах, кроме JoinClause, должны будут пробросить вызов своим потомкам.

Visitor-ы решают эту проблему за счёт следующего:

• Логические операции перестают быть методами на узлах, а становятся отдельными объектами — наследниками абстрактного класса SqlVisitor (см. рисунок ниже).
• Каждому типу узла соответствует отдельный метод Visit в базовом SqlVisitor-е, например, VisitSelectClause(SelectClause clause) или VisitJoinClause(JoinClause clause).
• Методы BuildSql и AddAreaToJoinClause заменяются на один общий метод Accept.
• Каждый узел реализует его путем проброса на соответствующий метод на SqlVisitor-е, который приходит параметром.
• Конкретные операции наследуются от SqlVisitor и переопределяют только те методы, которые им интересны.
• Реализации методов Visit в базовом SqlVisitor-е просто перевызывают Visit для всех дочерних узлов, за счёт этого устраняется дублирование кода.

internal interface ISqlElement
{
    void Accept(SqlVisitor visitor);
}


internal class SqlVisitor
{
    public virtual void Visit(ISqlElement sqlElement)
    {
        sqlElement.Accept(this);
    }


    public virtual void VisitSelectClause(SelectClause selectClause)
    {
    }
    //...
}


internal class SqlFormatter : SqlVisitor
{
    private readonly StringBuilder target = new StringBuilder();


    public override void VisitSelectClause(SelectClause selectClause)
    {
        target.Append("select ");
        for (var i = 0; i < selectClause.Fields.Count; i++)
        {
            if (i != 0)
                target.Append(",");
            Visit(selectClause.Fields[i]);
        }
        target.Append("\r\nfrom ");
        Visit(selectClause.Source);
        foreach (var c in selectClause.JoinClauses)
        {
            target.Append("\r\n");
            Visit(c);
        }
    }
}


internal class SelectClause : ISqlElement
{
    //...
    public void Accept(SqlVisitor visitor)
    {
        visitor.VisitSelectClause(this);
    }
}

• Первый dispatch происходит в классе SqlVisitor при переходе от Visit к Accept на конкретном узле, в этот момент становится известен тип узла.
• Второй dispatch следует за первым при переходе от Accept на узле к конкретному методу на SqlVisitor, здесь становится известна операция, которую нужно применить к выбранному узлу.

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

Практический результат для компании заключается в сокращении скорости получения данных с 10 часов до 3 минут. Это позволило нашим аналитикам быстро ставить эксперименты и проверять гипотезы о бизнесе клиентов и работе бухгалтеров. Это особенно удобно, так как клиентов у нас много, а их базы распределены между пятью физическими серверами PostgreSQL.

Резюмируя всё вышесказанное:

1. Ставьте эксперименты и получайте proof of concept максимально быстро и дешево.
2. Ставьте амбициозные цели, и двигайтесь к ним маленькими шагами, постепенно дотачивая инструмент до нужного состояния.
3. Для большинства задач уже есть готовое решение, или хотя бы фундамент.
4. Синтаксический анализ и грамматики применимы в обычных бизнес-приложениях.
5. Решайте конкретную задачу, а общее решение придёт само.

На досуге советуем почитать:

• 99,99% задач не имеют решения потому, что люди не верят в это
• Зачем команда Джоэла Спольски написала собственный компилятор?
• Пост Скотта Хансельмана о библиотеке Irony

Комментарии (5)

• Bonart

  1 ноября 2016 в 09:19

  0

  ↑

  ↓

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

  • gusev_p

    1 ноября 2016 в 09:41

    0

    ↑

    ↓

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

  • gusev_p

    1 ноября 2016 в 09:49

    0

    ↑

    ↓

    все, разобрался с parser combinator-ами, выглядит клево, да 

    • Bonart

      1 ноября 2016 в 10:15

      0

      ↑

      ↓

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

• gusev_p

  1 ноября 2016 в 09:40 (комментарий был изменён)

  0

  ↑

  ↓

  не туда