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

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

Під час створення дашбордів чи інших інформаційних панелей, може виникати необхідність у конфігурації під окремого клієнта, або у наданні клієнту чи аналітику можливості обирати, як відображати дані. Я — Володимир Міхав, аспірант, 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

+

*

(

)

$

E

E→TR

E→TR

R

R→+TR

R→e

R→e

T

T→FY

T→FY

Y

Y→e

Y→*FY

Y→e

Y→e

F

F→id

F→(E)

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

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


id+id$

id+id$

id+id$

id+id$

E

TR

FYR

idYR

idR

id+TR

id+FYR

id+idYR

id+idR

id+id

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

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

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

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

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

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

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

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

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


Нетермінал

Вхідний символ

id

op

(

)

$

E

E→idF

E→(E)

F

F→opE

F→e

F→e

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

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

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

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

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

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

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

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

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

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

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

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

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

Підсумок

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

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

👍НравитсяПонравилось8
В избранноеВ избранном4
LinkedIn
Допустимые теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter
Допустимые теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter

Вот что не понятно:
Откуда такое рвение изобретать колёса?
Но ведь есть же Антлер, Як, Бизон и ещё с три десятка по меньшей мере парсеров и генераторов, описав на несколько десятков строк грамматику, можно сэкономить месяц работы...
Эх, велосипедостроители!
Рекомендую ANTLR4, как самый вменяемый, удобный и практичный инструмент

en.m.wikipedia.org/...​/Recursive_descent_parser

Завжди парсери пишу за допомогою цього підходу.

Для простих граматик, BNF практично в сліпу можна переписати в код, що його парсить.

Для чогось складнішого, думаю, є сенс дивитись генератори.

Зачем делать руками парсер, если есть ANTLR с таргетами для всех распространенных языков?

ANTLR не всесилен, мягко говоря.

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

Так ничто не всесильно, но если к тебя есть инструмент покрывающий 90% задач, нужно иметь остальные 10% чтобы его не использовать. В калькуляторе формул этого нет

Щодо того, що у алгоритма Дійкстри є труднощі з унарними операціями та функціями — не згоден.

Треба дуже трохи модифікацій і унарні операції прекрасно реалізовуються як оператори з найвищим приорітетом. Головне не мати однакових постфіксних та інфіксних операторів.

А виклик функцій — як спеціальний оператор. Функції з одним операндом взагалі можна представити, як унарні оператори, але зі всіма наслідками унарних операторів.

«Книга дракона» у загальному випадку не кращий варіант.

1) Вона не дає плавного початкового входу у тематику.

2) Вона занадто концентрується на тому, що навіть розробнику таких синтаксичних аналізаторів не потрібно у >90% випадків.

3) Вона ігнорує багато нових актуальних технологій, як, наприклад, PEG.

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

Тут треба якусь в рази більш базову книгу, але щоб вона давала гарний стартовий базис.

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

По-современному имеет смысл стартовать с готовых примеров кода на какой-нибудь классический калькулятор с их разбором:
1) Рукопашный нисходящий на 5 операциях и только целых числах;
2) Пратта;
3) Рукопашный восходящий без сокращения набора состояний (показать отработку рестартуемой машины состояний);
4) Рукопашный восходящий с сокращением набора состояний (2 достаточно, остальное в стеке);
5) Добавить переменные — скаляры и мапы.

К каждой по паре несложных задач — типа, подправить приоритеты, расширить на чтение плавающих (пусть даже внутри sscanf для собственно перевода в число...)

Догнать примерами на автоматизированных средствах (bison, ANTLR).

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

Я бы все таки математические формализмы дал бы сразу, учитывая что там их совсем немного.

1) Рукопашный нисходящий на 5 операциях и только целых числах;

А что тут можно разбирать?

Я бы все таки математические формализмы дал бы сразу, учитывая что там их совсем немного.

Вот после первого примера можно и формализм вводить. Но именно что он должен быть согласован с реальным примером.
И на нём уже показать, как фокус типа «почему 2+3*4 не может быть понят как (2+3)*4» реализуется одновременно и в теории, и на практике.

А что тут можно разбирать?

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

Я обращал внимание на твои посты. Они разнообразны по тематике и глубоки.
Можешь поделиться каким образом ты пришёл к этому, с твоей точки зрения? Например, если это непрерывное обучение, то как именно ты это делаешь?

Можешь поделиться каким образом ты пришёл к этому, с твоей точки зрения?

В первую очередь чтение разнообразных потоков живых обсуждений тематики, которая близка к тому, над чем сейчас работаю, и/или интересна иначе. Сейчас это почти полностью форумы (типа хабра, RSDN, нескольких других; DOU таки меньше), раньше были usenet конференции. Любой зацепивший момент оценивается, сколько сказано нового/незнакомого/неожиданного, гуглится и при необходимости уточняется в обсуждении там же. Именно живые обсуждения дают то, чего тупо не замечаешь при каком-нибудь чтении документации или книг.
Книги по сравнению с этим это уже суженная конкретика — они тоже нужны, но чтобы понять, какую книгу читать, надо понять, что и как интересует.
Существенно:
1. Объём участия в этом — грубо говоря, полчаса-час в день в среднем. Не напрягаться, но и не пропускать.
2. Стараться находить полезное и отфильтровывать явный мусор — в смысле левых дискуссий, или на бесполезные темы, или в таком стиле, что не будет никакого конструктива. К первому пример — вечные споры на DOU где сыр слаще, ко второму — форумы какого-нибудь ixbt, где 99% сил участников уходит на то, как бы заковыристее облить собеседника помоями. Комьюнити важнее базового ресурса в разы, если не в десятки раз.
3. Участие в любом споре должно быть принципиально конструктивным — для получения ответа на нужные вопросы. Флейм имеет смысл только если он стимулирует собеседника уточнить сказанное или открыть что-то новое.
В случае частично вражеских ресурсов (хабр/RSDN/etc.) принципиально ограничиваться только техническими вопросами. Помнить, что мы победим, а в гугле всё останется и переводчики только будут улучшаться;)
4. Формулирование ответа очень помогает структурированию своего понимания и поиску пробелов в нём.
5. Продвигаться в понимании написанного другими относительно мелкими шагами с проверками — чтобы, в частности, не терять время на попытки расшифровать что-то заведомо ошибочное. Не напрягаться в этом;)
Остальное — по мере накопления опыта в этом процессе.
Возможно, тут влияет стиль собственной памяти. Про это ничего точно не скажу — я не спец по живым нейросетям ;)
Самое полезное — снятие прежних стереотипов. Например, вот пару минут назад увидел по соседству — argv[0] может быть пустым и это штатно разрешено. Даже если это было в документах явно сказано, обычно этот кусок или не читался (типа, что там может быть нового?), или не замечалось. На практике такого ни разу не видел. Хоть это и мелочь, но куда-то надо сложить и чтобы всплыло в нужный момент. Такие неожиданности появляются обязательно в среднем где-то раз в месяц.

Не согласен. Это классическая книга где даётся хорошая теор. база

Это классическая книга где даётся хорошая теор. база

«Классическая» — согласен.

«Хорошая теор. база» — уже нет. Потому что база должна быть достаточно современная и для чего-то реального. А реальность — это когда уже самые простые движки регэкспов по POSIX (а тем более адванснутые типа PCRE или C++ regex) уже не укладываются в «регулярные грамматики» Хомского (ибо backreferences), в обычные context-free укладываются разве что школьные разработки уровня классического Паскаля, но не C, а C++ компилятор вообще должен содержать кусок интерпретатора.
И что про это говорит книга дракона? Ничего. Даже версия 2008 года.

Или например где хотя бы упоминание SSA? Сейчас все передовые компиляторы на нём (а это полностью переломало почти всю генерацию кода). В GCC он пошёл в районе 2001, да? Книга 2008 года — игде?
Где PEG, на котором сейчас масса новых разработок?

И в общем это неудивительно — первая версия вышла когда? 1978. А дальше только дополняли по мелочи не ломая общую структуру.

Кстати, и к теме статьи оно относится косвенно, потому что в книге много про LR, но мало про LL. И неудивительно — Запад в основном разрабатывал LR. LL любили больше в СССР, но далеко не ушли (так что когда Теренс Парр выпустил LL(inf) средство, была масса офигения).

Если что, у меня в бумаге два издания и в электронном виде — три, есть на чём сравнить.

А реальность — это когда уже самые простые движки регэкспов по POSIX (а тем более адванснутые типа PCRE или C++ regex) уже не укладываются в «регулярные грамматики» Хомского (ибо backreferences), в обычные context-free укладываются разве что школьные разработки уровня классического Паскаля, но не C, а C++ компилятор вообще должен содержать кусок интерпретатора.

Ну всё таки база — это база, а не про то как часто и широко оно используется

Ну всё таки база — это база, а не про то как часто и широко оно используется

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

Для создания собственного DSL через ANTLR/bison/etc. нужны самые простые принципы (которые в драконе ещё вылавливать надо среди шума) и опыт работы с конкретным средством (например для flex+bison я больше времени тратил на связь компонентов, чем на собственно грамматику — flex построен ужасно, лучше вообще выбросить его и взять re2c).
Простые построения лучше учить из изданного по Аппелю, хотя отличный пример калькулятора есть даже у Страуструпа в его учебнике C++.
А вот для написания компилятора вся книга безнадёжно отстала — её нужно дополнить как минимум Мучником и SSA book, ну и вообще подписаться на материалы ACM.
Дракон в результате остаётся раскрученным «чемоданом без ручки».
Ну и зачем такая «база»?
Книги 40-летней давности (а в основе она такая) не годятся: всё изменилось. Надо писать с нуля вообще не опираясь на прошлый образец. Кстати, это и другой «базы» касается — TAoCP.

Кстати, это и другой «базы» касается — TAoCP

Тут, так би мовити, палка в двох кінцях. З одного боку TAoCP — це не та книга, з якої варто починати, і частина інформації справді застаріла; з іншого — там все ще можна знайти цікаві специфічні речі. Наприклад, я готував модуль для роботи з Binary Decision Diagram, базуючись на четвертому томі.

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

Ну или просто генератор парсеров, типа ANTLR взять, скормить ему грамматику и не париться.

И хвататнуть зависимость от ANTLR runtime даже для самых простых задач

скормить ему грамматику и не париться

Как минимум нужно убедится что грамматику можно распарсить LL(1) парсером (или привести к такому виду).

«Зло» — это слишком нагруженное слово. Я бы сказал «недостаток».

Подписаться на комментарии