Парсинг, валідація та обчислення формул за допомогою LL(1) граматики

Під час створення дашбордів чи інших інформаційних панелей, може виникати необхідність у конфігурації під окремого клієнта, або у наданні клієнту чи аналітику можливості обирати, як відображати дані. Я — Володимир Міхав, аспірант, Full-Stack розробник і техлід у компанії Onix-Systems, і у цій статті я поділюся з вами власним досвідом зі створення backend-у для таких систем.

Відеовиклад матеріалу

Чому це може бути складно?

Для створення динамічної інформаційної панелі нам необхідно надати користувачу можливість описати, як саме він хоче перетворити оригінальні дані. Найпростіший варіант як це можна реалізувати — використати інтерпретовану мову запитів або програмування. Найбільш яскравим представником мов запитів у цьому випадку є SQL. Klipfolio — компанія, що пропонує адаптивні дашборди як сервіс — використовує саме SQL. Серед інтерпретованих мов програмування варто звернути увагу на Lua. Це мова програмування, добре відома розробникам ігор та модів для них. Її основна перевага полягає у тому, що багато мов програмування мають бібліотеки для інтеграції з Lua, тож розпочати буде доволі легко.

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

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

Кроляча нора

Більшість читачів бачили, або принаймні чули про фільм «Хакери» 1995 року. В одному із епізодів згадується книга, яка значно полегшує розробку інтерпретатора — це «Компілятори: принципи, технології та інструменти», яку також називають «Книга дракона». До того, як переходити до алгоритмів, описаних у цій книзі, я б радив ознайомитися із простішими алгоритмами, а саме:

Алгоритм сортувальної станції (shunting-yard algorithm)

Алгоритм сортувальної станції був описаний Едсгером Дейкстрою у 1961 і використовувався для розбору програм, написаних мовою Algol 60. Він дає можливість перетворювати інфіксний запис формули (x+y*z) на постфіксний (xyz*+) або, як його ще називають, у зворотню польську нотацію. Такий запис значно зручніший для комп’ютера, оскільки він дає можливість обчислити значення функції використовуючи лише стек.

Алгоритм складається з наступних кроків:

1. Розбити формулу на операнди (змінні та числа) та оператори.
2. Для кожного елемента формули:
   1. Якщо це операнд — то занести його у стек результату
   2. Якщо це оператор:
      1. Якщо пріоритет поточного оператора менший за пріоритет останнього оператора (наприклад — після *), то перенести усі елементи зі стеку операторів до стеку результату.
      2. Занести поточний оператор до стеку операторів.
3. Перенести усі елементи зі стеку операторів до стеку результату.

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

LL(1) граматика

Увага! Матеріал може виявитися складним для людей, які не працювали із граматиками або теорією алгоритмів. Якщо в цьому пункті щось незрозуміло, можеш сміливо переходити до наступного.

LL(1) розшифровується наступним чином:

• L — left to right: рядок аналізується зліва направо;
• L — leftmost derivation: кожен наступний рядок формується шляхом заміни найлівішого нетермінала із правила;
• 1 — для прийняття рішення аналізатору досить проглядати рядок на один токен вперед.

LL(1) граматики належать до одних із найпростіших, але при цьому їхніх можливостей більш ніж достатньо для нашої задачі. Ці граматики мають певні обмеження, наприклад, у них не може бути ні лівої рекурсії, ні неоднозначності, але у нашому випадку це не проблема.

У таблиці нижче наведено приклад граматики із «Книги дракона». Для її розуміння необхідно ввести певні визначення:

• id — будь-яка змінна;
• op — будь-який оператор;
• $ — символ кінця рядка;
• e — порожній символ, означає що нетермінал потрібно просто видалити;
• E — нетермінал, з якого починається розбір;

Ця граматика описує формули з додаванням і множенням. Значення в комірках цієї таблиці показують, як саме нам слід заміняти нетермінали під час розбору. Якщо комірка порожня, то такий перехід неможливий і у формулі є помилка.

Спробуємо розібрати формулу id+id. У таблиці нижче наведено покроковий розбір.

Як бачите, це доволі просто — потрібно виконувати заміну, описану в комірці на перетині рядка з найлівішим нетерміналом і стовпчика з поточним символом. Таким чином ми можемо розбирати формулу на частини і будувати абстрактне синтаксичне дерево (AST), а також знаходити помилки у формулі в процесі розбору (так само як це робить IDE).

Розбір формули на частини

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

• список операторів та функцій має бути попередньо заданим;
• назви змінних та функцій мають починатися з літери;
• назви змінних та функцій не можуть включати символи, які є операторами;
• список функцій має бути попередньо заданим;
• оскільки ми працюємо з даними з відомою схемою, то список змінних теж відомий.

Далі розбір здійснюється за символом у поточній позиції та тим, що ми очікуємо зараз знайти у рядку. Якщо ми очікуємо знайти оператора, то необхідно перевірити, чи належить поточний символ хоча б одному оператору. Якщо ми очікуємо змінну, то потрібно оцінити поточний символ:

• якщо це цифра, то це має бути число, і ми маємо повністю його прочитати;
• якщо це не літера, то потрібно перевірити, чи це унарний оператор;
• якщо це літера, то потрібно підібрати назву функції чи змінної, яку можна розташувати у цій позиції рядка.

Таким чином ми можемо розбити формулу на частини і перейти до побудови абстрактного синтаксичного дерева.

Побудова абстрактного синтаксичного дерева

На першому етапі можна вважати, що формула може складатися лише зі змінних, операторів та дужок. У цьому випадку для нашої граматики достатньо двох нетерміналів.

Цього достатньо для того, щоб відтворити функціональність алгоритму сортувальної станції. У такому вигляді граматика розпізнає дужки, але щоб гарантувати коректність розбору та правильно врахувати пріоритет операцій у дужках, я раджу мати лічильник відкритих/закритих дужок і перевіряти чи він дорівнює нулю по завершенню розбору.

За успішного розпізнавання кожного елементу (змінної чи оператора), ми повинні додати цей елемент до абстрактного синтаксичного дерева. Завдяки тому, що ми використовуємо LL граматику з ліворекурсивним виведенням, ліве піддерево завжди буде завершеним і не може змінюватися. Додаючи новий елемент, необхідно враховувати його пріоритет: пріоритети вузлів мають зростати від кореня до листків, а листками виступають змінні та константи.

Розбір формул із функціями відрізняється тим, що кожен параметр функції — це окрема формула. У своїй реалізації я додав стек контекстів, який дозволяє розпочати розбір внутрішньої формули без рекурсивних викликів. По закінченню розбору функції необхідно перевірити, чи співпадає кількість параметрів із опису функції з тим, що було фактично отримано. В абстрактне синтаксичне дерево функція додається як піддерево, коренем якого є функція, а його нащадками — дерева параметрів.

Валідація формули

Завдяки тому, що нам відомі типи змінних, ми можемо перевірити формулу на невідповідність типів до її фактичного обчислення. Ми маємо уникати таких ситуацій, як віднімання рядка від числа або ділення на булеве значення. Для успішної перевірки у всіх операторів та формул має бути вказано, які типи вони приймають та який тип має результат виконання. Наприклад, оператори порівняння вимагають, щоб обидва операнди мали однаковий тип, а результат має булевий тип.

Для валідації типів нам необхідно пройти дерево від листків до кореня, імітуючи виконання і використовуючи типи змінних замість їх значення. В результаті або виконання буде перерване через невідповідність типів, або в корені дерева ми отримаємо тип результату виконання формули. Це дуже корисно, оскільки дозволяє перевірити, чи може ця формула бути застосована у певному контексті. Наприклад, якщо ця формула використовується для формування умови для запиту до бази даних, то тип результату має бути булевим.

Обчислення значення формули

Обчислення значення формули схоже з валідацією, але має свої особливості. Наприклад, в операції ділення необхідно перевіряти, чи не ділимо ми на нуль, і опрацьовувати цю ситуацію — створювати виключення або ж пропустити ділення. Певно, головним недоліком цього підходу є те, що у формулу можна передати лише один кортеж даних, тож немає можливості порівнювати кортежі між собою або використовувати агрегаційні функції напряму, для цього необхідно здійснювати підготовку даних.

Якщо ж формула використовується для побудови частини SQL запиту, то, окрім ситуації із діленням, необхідно обережно опрацьовувати рядки. У деяких випадках, наприклад, при створенні MATERIALIZED VIEW, у нас немає можливості використати підстановку змінних, тому існує ризик SQL-ін’єкції. Для уникнення цієї ситуації, я використав перетворення рядка у Hex-представлення, яке підставляється у запит і декодується при виконанні запиту. Завдяки цьому ми можемо гарантувати, що рядок не може бути сприйнятий як частина SQL-інструкції.

Приклади застосування

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

Альтернативи

Якщо з якоїсь причини ви не хочете/не можете написати власний парсер і працюєте з PHP, ви можете використати Symfony ExpressionLanguage Component, який надає схожий функціонал, але в цілому має менше можливостей, і його буде значно складніше розширювати за потреби.

Підсумок

Існує декілька різних методів, що дозволяють описувати маніпуляції над даними без прямого втручання у код додатку. Універсального варіанту немає, кожен має свої переваги і недоліки. Але різноманітність підходів дає можливість працювати над більшим спектром проблем.

Я раджу ознайомитися із «Книгою дракона». Навіть якщо вам не треба буде розробляти власні парсери, це допоможе краще розуміти синтаксис мов, з якими ви працюєте.

Підписуйтеся на Telegram-канал «DOU #tech», щоб не пропустити нові технічні статті