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

Как часто, программируя очередную бизнес-фичу, вы ловили себя на мысли: есть же на Земле люди, которые пишут базы данных, распознают лица на фотографиях, делают фреймворки и реализуют интересные алгоритмы. Почему в моей работе всё сводится к перекладыванию из одной таблицы БД в другую, вызову http-сервисов, верстке html-формы и прочей «бизнес-лапше»? Может быть я занимаюсь чем-то не тем или работаю не в той компании?

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

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

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

С чего всё началось?

Мы работаем в крупной бухгалтерской компании Кнопка. У нас обслуживается 1005 клиентов, работают 75 бухгалтеров и 11 разработчиков. Наши бухгалтеры ведут учёт тысячи клиентских баз в системе 1С: Бухгалтерия. Для управления базами мы используем облачную технологию 1cFresh, данные для неё храним в PostgreSQL.

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

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

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

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

Перечисленные проблемы легко найти с помощью языка запросов 1С, поэтому появилась идея сделать автоматизированный аудит клиентских баз. Мы написали несколько запросов и стали выполнять их каждую ночь на всех базах 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)

Несмотря на то, что это очень похоже на SQL, такую штуку не получится просто так взять и запустить напрямую через БД.

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

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

Осознав всё это, мы написали утилиту, которая преобразовывает запрос с диалекта 1С в обычный SQL, запускает его параллельно на всех физических серверах PostgreSQL, результат объединяет и складывает в отдельную таблицу в MS SQL. В результате время сбора данных сократилось с 10 часов до 3 минут.

Регулярные выражения

В первой версии логику преобразования запроса мы реализовали целиком через regexp-ы. В COM апи 1С есть функция ПолучитьСтруктуруХраненияБазыДанных. Она возвращает информацию о том, каким таблицам и полям соответствуют объекты и свойства в 1С запросе. Используя несколько regexp-шаблонов, мы просто заменяли одни имена на другие. Этого удалось довольно легко достичь при условии, что все обращения к объектам и свойствам имели псевдонимы.

Больше всего хлопот доставили вложенные свойства. 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

Кроме переименования свойств и генерации left join-ов, транслятор применял ещё ряд преобразований. Так, например, все join-ы в исходном запросе приходилось снабжать дополнительным условием на равенство поля Область (area). Дело в том, что в одной базе данных PostgreSQL у нас живут несколько клиентских баз 1C, и данные одного клиента от данных другого отличаются специальным идентификатором, который 1С называет областью. В базе 1С создает ряд индексов по умолчанию. Все они первым компонентом ключа имеют область, так как все запросы выполняются в рамках одного клиента. Чтобы наши запросы использовали стандартные индексы, и чтобы не думать об этом при их написании, мы стали добавлять это условие автоматически при трансляции запроса.

Использование 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;
}

В коде хотелось иметь дело с объектной моделью исходного запроса, с ColumnReference и JoinClause, а вместо этого были только найденные regexp-ами подстроки и смещения в тексте запроса.

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

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
    };
}

Такая объектная модель называется Abstract syntax tree (AST).

AST

Интересно, что впервые AST у нас появилось не при парсинге исходного запроса, а наоборот, при форматировании результата в SQL. Дело в том, что логика конструирования подзапроса для вложенных свойств становилась довольно витиеватой, и для её упрощения (и в соответствии с SRP) мы разбили весь процесс на два этапа: вначале создаем дерево объектов, описывающих подзапрос, затем отдельно сериализуем его в SQL. В какой-то момент мы осознали, что это и есть AST, и для решения проблем с regexp-ами нужно просто научиться создавать его для исходного запроса.

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

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

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

В виде AST он выглядит так:

На рисунке узлы — экземпляры классов, стрелочки и подписи — свойства этих классов.

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

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"
    }
});

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

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

Грамматики

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

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

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

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

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

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

Символы, для которых определены правила вывода, называют нетерминалами. Символы, для которых не определены правила, и которые являются элементами языка — терминалами. Применяя правила, из нетерминалов можно получать строки, состоящие из других нетерминалов и терминалов, пока не останутся только терминалы. В примере выше E — это нетерминал, а символы +, -, *, / и number — терминалы, образующие язык арифметических выражений.

Существуют специальные инструменты — генераторы синтаксических анализаторов, которые по описанию языка, заданному в виде грамматики, умеют генерировать распознающий этот язык код. Самые известные из них — это 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;

Символ | означает, что может применяться любой из вариантов правила (логический or).
Символ + — конкатенация, символы должны следовать друг за другом.

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

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

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

e₁: E → E + E
e₂: E → (E)
e₃: E → number

соответствует такое Parse Tree:

Parse Tree не зависят от конкретного языка и в Irony описываются одним классом ParseTreeNode.

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; }
}

Свойства Left и Right имеют тип object, т.к. они могут ссылаться либо на число, либо на другой BinaryOperator:

Irony позволяет создать AST последовательно, поднимаясь от листьев к корню, одновременно с применением правил грамматики. Для этого на каждый нетерминал можно навесить делегат AstNodeCreator, который Irony вызовет в момент применения любого из сопоставленных этому нетерминалу правил. Этот делегат должен на основе переданного ParseTreeNode создать соответствующий ему узел AST и положить ссылку на него обратно в ParseTreeNode. К моменту вызова делегата все дочерние узлы Parse Tree уже обработаны и AstNodeCreator для них уже был вызван, поэтому в теле делегата мы можем пользоваться уже заполненным свойством AstNode дочерних узлов.

Когда мы таким образом доходим до корневого нетерминала, в его 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

Паттерн Visitor (или double dispatch) — один из самых сложных в GoF и, возможно поэтому, один из самых редко используемых. За свой опыт мы видели только одно активное его применение — для преобразования различных AST. Конкретный пример — это класс ExpressionVisitor в .NET, который неизбежно возникает, когда делаешь linq provider или просто хочешь немного подправить генерируемые компилятором expression tree.

Какую проблему решают 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("rnfrom ");
        From.BuildSql(target);
        foreach (var c in JoinClauses)
        {
            target.Append("rn");
            c.BuildSql(target);
        }
    }
}

Про этот код можно сделать два важных наблюдения:

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

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

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

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

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

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

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

Пример с сериализацией в SQL адаптируется следующим образом:

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("rnfrom ");
        Visit(selectClause.Source);
        foreach (var c in selectClause.JoinClauses)
        {
            target.Append("rn");
            Visit(c);
        }
    }
}


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

Название double dispatch вполне точно описывает эту схему:

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

Итого

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

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

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

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

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

Код бибилиотеки и примеры использования ждут вас на GitHub.

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

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

Автор: Кнопка

Источник