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

Як часто, програмуючи чергову бізнес-фічу, ви ловили себе на думці: чи є на Землі люди, які пишуть бази даних, розпізнають обличчя на фотографіях, роблять фреймворки та реалізують цікаві алгоритми. Чому в моїй роботі все зводиться до перекладання з однієї таблиці БД в іншу, викликом 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.Номер Number as,
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-s
.

Приклад запиту
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-s і експерименти робити саме так — максимально простими підручними засобами. А що може бути простіше і ефективніше при роботі з текстами, ніж regexp-и?

Звичайно, є й недоліки. Перший і очевидний — це зрізані кути і обмеження синтаксису. Regexp-и властивостей і таблиць вимагали розстановки псевдонімів у запиті і, взагалі, могли випадково заматчиться з якою-небудь іншою конструкцією, наприклад, константною рядком.

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

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

private string PatchJoin(string joinText, int joinPosition, string alias)
{
var fromPosition = queryText.LastIndexOf("з", 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)
при застосуванні правил:
e1: E → E + E
e2: E → (E)
e3: 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",
представник(AstContext context, ParseTreeNode node)
{
//відповідає правилу E → number,
if (node.ChildNodes.Count == 1)
{
node.AstNode = node.ChildNodes[0].Token.Value;
return;
}
//правила виду E → E m 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("\r\nfrom ");
From.BuildSql(target);
foreach (var c in JoinClauses)
{
target.Append("\r\n");
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("\r\nfrom ");
Visit(selectClause.Source);
foreach (var c in selectClause.JoinClauses)
{
target.Append("\r\n");
Visit©;
}
}
}


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.

На дозвіллі радимо почитати:Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.