Побудова парсерів в C#: від теорії до практики. Кейс Uklon про розбір Conditional Restrictions тегів в OSM

Вітаю всіх слухачів конференції! Ми готові розпочати. Сьогодні ми розглянемо тему побудови парсерів в C-Sharp. На початку розглянемо теорію та об'єкти для парсингу, а потім перейдемо до практичного аспекту - як саме це реалізувати. В якості прикладу практичного кейсу ми візьмемо розбір Conditional Restriction тегів в OSM. Обрано цей приклад через те, що я працював в команді MapService, яка спеціалізується на картографії та використовує SM як базу даних.

Ми обговоримо парсер-комбінатори та порівняємо їх з регулярними виразами та повноцінними парсерами. Також розглянемо Conditional Restriction теги в ОSM та визначимо їх складність, пояснимо вибір парсер-комбінаторів. У практиці ми розглянемо приклад паркової дороги в Києві з умовними обмеженнями. Це дозволить нам продемонструвати парсинг умов та їх обчислення. Зокрема, ми розглянемо тег Excess Conditioning, який вказує на перекриття дороги з понеділка по п'ятницю з 16:40 до 19:45, за винятком святкових днів (PH).

Узагальнюючи, наша мета - парсити значення тегу Conditioning, обчислювати його і визначати, чи є дорога відкритою чи закритою. Це важливо для побудови маршрутів, оскільки закрита дорога може призвести до скарг користувачів. А це, мов би, вже мінус до репутації компанії. Чому ми будуємо взагалі такі дороги? Навіщо? Не зрозуміло. Тому ми хочемо, відповідно, уникати таких рішень. Як нам, відповідно, розпарсити та обчислити ці теги? Що нам для цього потрібно?

Давайте спочатку розглянемо, як виглядають ці теги. Вони виглядають ось так. Я взяв приклад того, як можуть виглядати ці теги. Тут маємо restriction time, transportation mode, direction — це все неважливо. Просто там зірочка може бути кондішн. Ми вибираємо всі елементи, де є двокрапка і кондішн. Ось restriction value — тут теж зрозуміло. Це може бути швидкість або якісь умови. Далі варіант, може бути snow, або, наприклад, інші умови, пов'язані з тим, на що впливає обмеження. Задаються обмеження ось так.

Найцікавіший компонент — це кондішн, який задається специфікацією. Ця специфікація існує вже довгий час на сайті OpenStreetMap.org. Виглядає вона ось так. Здебільшого зрозуміло, але може здатися трошки складною через те, що є деяка неформальність. Тут важливий момент: є покращена версія цієї специфікації від автора, того, хто зібрав усі ці значення, можливо, від тегів кондішнів та намагався їх формалізувати. Ось. Тобто тут може бути коментар, або взагалі будь-які значення, тому що OSM — це народна карта, де може бути будь-яка інформація. Це додає відповідну складність, оскільки може бути все, що завгодно.

Тут також зазначено, що "can be evaluated sufficiently simple," але це не завжди правда. Формалізація цієї специфікації не є дуже простою через те, що вона неформальна. Те, що там намагалися формалізувати, це, так би мовити, рекомендація, і за нею не обов'язково слідкувати. Це важко виконати, оскільки карта є народною, і ніхто не буде перевіряти дотримання цієї формалізації. Тобто, ми повинні бути готові постійно додавати будь-які значення цих тегів і розширювати наш парсер, який буде відповідати за парсинг цих тегів. У нас повинна бути гнучкість у тому, щоб бути готовими до будь-яких можливих значень. Тобто, тут може бути що завгодно.

Навіть важко узагальнити всі ці приклади. Особливо мені сподобався жарт про "Sunrise Sunset, Beware of Sunburn," а також "Sunset Sunrise, Beware of Prime Bias." Це, звісно ж, жарт, і в Україні таких ситуацій немає. Таких жартів у нас не існує. Але, можливо, коли ми вийдемо на нові ринки, там з'являться якісь жартівливі теги, і нам доведеться якось їх обробляти. Тут є також межа у тіливі, але це серйозні ситуації, які також потрібно враховувати. Отже, як розпарсити значення цих тегів у кондишні? Ось, основне питання. Трошки теорії, трошки формалізації цієї задачі.

Ми маємо рядок тексту, це значення, і його потрібно перетворити у структуру даних. Як це робиться? Це робиться за допомогою парсерів. Отже, в загальному випадку, це звичайна функція, яка приймає рядок і повертає структуровані дані. Якщо у нас є кілька парсерів, кожен відповідає за свій фрагмент результату. Як їх комбінувати та отримати фінальний результат? Для цього нам потрібно використовувати парсер-комбінатор. Комбінатори-парсери це функції вищого порядку, які приймають один чи декілька парсерів і повертають новий парсер. Знизу вгору підхід рекомендує будувати парсери. Ми виділяємо маленький фрагмент рядка, будуємо парсер для нього, а потім комбінуємо їх, щоб отримати фінальний результат. Таким чином, ми можемо легко створювати різноманітні комбінації парсерів. За допомогою парсер-комбінаторів їх об'єднали у пів. Більші шматочки. Відповідно, виникла якась структура.

Ці структури ще можна об'єднати за допомогою парсер-комбінаторів. І ось так воно об'єднується, об'єднується, об'єднується, поки ми не розпарсимо все, що нам потрібно. Використовується це так. Тобто, знову ж таки, тепер замість парсера там може бути будь-яка складна структура цих парсерів. Це будь-яке складне дерево. Ми подаємо нашому парсеру рядок. Він, відповідно, використовує цей парсер-комбінатор, який передає цей рядок спочатку першому парсеру, потім видає результат. Або другому можна влаштувати, комбінувати. Якщо не спрацював перший парсер, тоді передаємо результат другому парсеру. І ось так воно проходиться по всім парсерам. І врешті-решт повертається до початку, до нашого самого першого парсера, який видає структуру.

Як ми будемо цю структуру використовувати? Це може бути що завгодно. Оскільки ми пишемо на C#, то зазвичай ми просто видаємо якийсь C#-клас в результаті. Ось і все. Тобто, якщо узагальнити, парсер-комбінатори - це техніка створення складних парсерів за допомогою комбінування простих парсерів. Все це просто об'єднання в декількох парсерах. Далі це об'єднання також можна поєднувати з іншими об'єднаннями. І це все буде називатися парсер-комбінаторами.

Ось і все. Відповідно, чому це таке прикольне? Які у нього переваги? Дуже важливі в контексті наступного відео, наступної доповіді. Гнучкість - ми можемо зібрати все, що завгодно, використовуючи декілька простих парсерів. І ці декілька простих парсерів насправді не будуть у нашій бібліотеці, в якій ми використовуємо. Тобто, за допомогою цих парсерів ми можемо розпарсити будь-що. За допомогою регулярних виразів, наприклад, можна розпарсити HTML. А за допомогою цих парсер-комбінаторів ми можемо розпарсити HTML. Зазвичай це не потрібно, але для ілюстрації прикладів і так далі.

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

Але тут досвідчені глядачі можуть запитати: 'Але ж у нас є регулярка. Вони ж по суті роблять те саме.' Вони беруть шматочок цих текстів і ніби його пасуть. Чому не регулярні вирази? Давайте подумаємо. По-перше, чому б їх не використовувати? Вони швидкі. У останніх версіях .NET їм дуже багато уваги приділили, і вони стали дуже швидкими. Вони нативно підтримуються мовою C#. В принципі, всі їх знають. Якщо подивитися на специфікацію, теоретично можна спарсити всі ці значення регулярками. Але, ну, також є складність специфікації.

Комбінувати ці регулярки, якщо ви коли-небудь стикалися з цим, а може і ні, але якщо стикнетеся, то зрозумієте, що комбінувати регулярки — це жахливо. Дуже складно. І якщо щось піде не так при парсингу, ви не знаєте, що саме сталося. Так? Тоді, як це в парсер-комбінаторах, там зазвичай бібліотека надає можливості відслідковування того, де саме вас трапилася помилка при парсингу. Знову ж таки, нам важко додавати нові випадки значень тегів. Куди їх додавати? Як їх скомбінувати? Знову ж таки, виникає багато питань, на які ми не дуже хочемо відповідати. Ще й те, що там є найбільш просунений парсер. Він самописний.

Чому б не написати свій самописний парсер? Насправді, це можна зробити, але це складно. І знову ж таки, немає формальної специфікації. Немає цієї специфікації , яка призначена для дорослих парсерів. І як його потім підтримувати — теж не дуже зрозуміло. Тому ми вирішили піти таким напрямком. Простим шляхом. Отже, використовуємо парсер-комбінатори. Ми використовуємо бібліотеку Pigeon для парсер-комбінаторів. Вона легка, швидка і гнучка, як обіцяє автор. Ви також можете використовувати будь-яку іншу бібліотеку.

Базові принципи однакові для всіх цих бібліотек. Так що, будь ласка, обирайте будь-яку. Тут також є інші бібліотеки. Ви можете їх використовувати. Тут будуть приклади саме для Pigeon. Поїхали. Візьмемо такий вираз для прикладу. Практика. У нас є гігантський рядок тексту, який ми повинні розпарсити. Що тут головне? Головне, що вираз обчислюється зліва направо. Ділиться на правила, які розділені крапкою з комою. Також правило прикриває попереднє. Тобто, що це означає? Це означає, що не дивлячись на всі ці попередні умови, три штуки на публічні свята. Ми завжди, там, дорога відкрита з 9 до 12. Все. Тобто, всі інші можна не враховувати.

Але врешті-решт, це все розпарсимо і подивимося. Як це парсити? Якщо подивитися на таке синтаксичне дерево для прикладу. Ось тут є новий приклад для першої частинки, першого правила. У нас є тайм-домейн. Це все описується тайм-домейном. Все, що розділено крапкою з комою, - це "Normal Room". Ось. Далі, відповідно, якщо розділено комою, - це "Sequence". Відповідно, якщо там тире, то - "Range". Наприклад, "Range" від червня до серпня. Або, наприклад, від 10 до 15 години дня. Ось. І, відповідно, час також розписується. Тобто, нам потрібно перетворити наш цей вираз, цей рядок тексту, у таке синтаксичне дерево за допомогою парсу. А далі це синтаксичне дерево обчислити за допомогою якогось нашого кастомного обчислення. Що далі?

Далі. Як це ми парсуємо? Знову ж таки, підхід знизу вгору. Тобто, ми беремо найменшу частинку. Найменша частинка у нас - це година та хвилина. Ось. Тобто, насправді, тут специфікації AVAR - це від 0 до 24. Можна зробити простіше. От. Тут діджит, наберіть, парсер розпарсити як діджит. Тобто, цифра. Багато цифр. Потім ми це все... Тут трошки налізло на презентацію. Але потім ми просто перевіряємо, чи вона влазить в рамки це число, яке розпарсуємо. Тобто, чи воно там більше, ніж... Ну, більше дорівнює 0. Чи менше дорівнює 24. От. І потім парсимо його. Ось. Далі цей тайм-парсер, що він робить? Він бере парсер спочатку годину. Потім роздільник - це двокрапка. І потім хвилина. Хвилина - це... Насправді, вона також його парсить так само, як і години. Тобто, універсальний стовпчик. Ось це розпарсити. Годину або хвилину. Потім використовуємо в парсері вищого порядку. Парсер-конфінатор. Такий тайм-парсер. Потім перевіряємо, чи це валідний час. Якщо він валідний, повертаємо у кортеж. Година-хвилина. Все. Дуже просто.

От хто знає, там, хто був на моїх попередніх виступах, що це монодична поведінка. Дуже важливо розуміти, що воно... Наприклад, якщо йому не вдалося розпарсити роздільник, то воно не піде далі. Воно не буде далі там парсити хвилину, перевіряти, чи це валідний час чи ні. Воно там просто вийде з повної середини. Тобто цей парсер, він насправді із середини. Відповідно, далі, якщо ми будемо розбирати наші складові, це може бути день тижня. День тижня, знову ж таки, задається в документації, як послідовний рядок рядків. Ми зробили трошки краще. Тобто, знову ж таки, це може бути довільна кількість літер, але ця довільна кількість літер, вона повинна розпарситися з живим внутрішнім парсером, який перевіряє, чи це дійсно день тижня чи ні. Відповідно, паблік холіді, ми його жорстко задовольняємо, це ISI string, це там внутрішній парсер бібліотеки Pidgin, який просто парсить рядок. І цей рядок PH, якщо це у нас, відповідно, PH паблік холідей, ми створюємо паблік холідей селектори. Оці селектори, паблік холідей селектор, бібліотека селектор, це наше таке представлення синтетичного дитинства. Далі. Epper, Ofep або Jum, знову ж таки, місяці, та практично так само є на парсері. Це декілька літер. Перевіряємо, чи воно відповідає умові, що це дійсно місяць.

Якщо так, то "select", якраз таки, перетворює ці декілька літер в, відповідно, назву місяця. Хто пам'ятає, то "select", це ніби функція меблів, перетворює з одного значення в інше. Тут воно використовується в такому комплексі. Отже, відповідно. Далі, розповім про парсинг діапазонів, "range". Тобто, тут цікаве те, що ми, якраз таки, використовуємо - тут точно показано, що комбінація цих парсерів є функцією вищого порядку, що ми на хід приймаємо наш "start-end" парсер, потім приймаємо функції "create range" і "is valid range". Тобто, чіткий діапазон взагалі. Це щось, що має початок, роздільник, в якості роздільника ми вибрали дефіс, тобто це дефіс, і кінець. Хоча, так і кінець, вони парсяться одним і тим самим парсером, що логічно. І далі нам потрібно перевірити, чи це взагалі валідний "range". Тобто, не можна забрати "range" не з 10 до 15, а з 15 до 10. Тобто, це буде якось дивно. Далі вже створюємо, відповідно, цей "range", спеціальну функцію. І далі нам потрібно ще розпарсити "sequence". Це "sequence", тобто, послідовність.

Як парсується послідовність? Тут трошки я подивився, як це розпарсити відповідно функціональних мов програмування. Там "list", він задається як початок з першої лінії та наступної лінії будь-які. Тобто, воно тут задається так само: "first" і "rest". Тут відповідно "before", "separated", "before", "before", "skip", "let's space". Це все спеціально зроблено так, щоб воно розпарсувало такі тривіальні випадки, коли "sequence" це, наприклад, один елемент або два елементи. І далі ми створюємо нашу "sequence" за допомогою такої функції, яку ми передаємо в цей парсинг. Все. Відповідно далі. Далі у нас не дуже багато часу розповідати. Розписувати весь парсер. Але я сподіваюся, що ви зрозуміли принцип. Принцип полягає в тому, що ми будуємо наш парсер для якоїсь дуже маленької частинки. Побудували так купу парсерів для цих маленьких частинок. А далі їх відповідно поєднуємо. І коли ми доходимо так до найвищої точки, до наших правил. Тобто там правил може бути різні види. Конкретно тут три види. Нам довелось виділити це "open-rule", "single-selector", "public-only", "take-off". Не дуже важливо, що це таке. Конкретно тут приклад був для того, щоб показати, що таке "try" та "or".

Почнемо з "or". "Or", він, як би те, що я казав. Ми пробуємо розбирати за допомогою парсера "open-rule". Якщо не виходить, то йдемо до парсера "single-selector", парсера "open-rule". Якщо це також не працює, то йдемо до "public-only", "take-off". Якщо і цей парсер не вдається, то, значить, ми не можемо розібрати це все.

Тоді ще потрібен "try". "Try" - це backtracking. Тобто що це таке? Якщо ми, наприклад, спробували розібрати наше правило і не вдалося, то без "try" ця уявна каретка в нашому парсингу залишиться там, де не вдалося розібрати. "Try" відкатить назад до початку виразу, який потрібно розібрати. Це така штука, яка добре показує себе в поєднанні з "or". Без "try" воно не працює, оскільки ми просто написали парсер "open-rule", "or" наступний, "or" наступний парсер. Отже, це взагалі не розбирає нічого, бо воно спотикнулося вже на першому парсері. І далі пішло би, але вже є якась плутанина. Так що нам потрібно відкатитись назад, коли там можуть бути дані, які можуть дати можливість наступним двом парсерам.

У результаті ми отримуємо "time-domain" парсер. Що це таке? Виглядає він дуже просто. Це, як би, послідовність наших парсерів, ось цих "normal-rule" парсерів, які були на попередньому слайді. Вони розділені "normal-rule" сепараторами - крапкою з комою, і перед цією крапкою з комою ще, після наїждження, можуть бути ще пробіли. Тобто цих "normal-rule" має бути хоча б один. І відповідно ми створюємо нашу структуру "time-domain-create". Як це все обчислюється? Все це обчислюється дуже просто. Знову ж таки, у нас кожен елемент - це селектор, і в нього є метод "isSatisfiedBy". Тобто як це виглядає? Повертається таке синтаксичне дерево. У його корені викликається "isSatisfiedBy". І все далі воно перевіряє по всіх його нащадках, чи задовольняють вони умови. Відповідно, вони задовольняють умову. Саме це дерево задовольняє умову тільки тоді, коли всі його нащадки задовольняють свою умову.

Відповідно, є декілька порад щодо того, як це все використовувати. Парсер у нас будується один раз і використовується багато разів. Тобто ви бачили, public, static, read-only - це воно і є. Ми один раз пробуємо розібрати і використовуємо багато разів. Є різні варіанти, як можна розібрати. Навіть це є найпростішим прикладом. Наприклад, візьмемо назви місяців. Як їх можна розібрати? Можна використовувати тупий спеціал. Можна використовувати так, як ми зробили. Парсимо спочатку як рядок, а потім перевіряємо, чи цей рядок підходить до назв місяців. Також є різні нюанси щодо синтаксису.

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

Тут також чудово виявляється Test-Driven Development (TDD). Ми спочатку написали тезу, тобто тест нашого парсера. А потім вже написали сам парсер. Написали тест на парсер-комбінатор. Створили парсер-комбінатор. І так поступово, з частин цих парсерів, парсер-комбінаторів, ми отримали наш повноцінний парсер. Тобто, якщо загалом розглядати це, то виявляється, що такі складні задачі виявляються досить простими на дорозі. Отже, це насправді досить складний випадок, з яким ми стикнулися, принаймні, на дорозі. Але що тут може відбуватися? Це просто рядок, а на практиці цей рядок може бути будь-яким. І потрібно щось з цим робити. І регулярних виразів для цього просто недостатньо.

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

Тут я також порекомендую кілька посилань. По-перше, це інша лекція від Олексія Голуба про парсер-комбінатор для JSON. Це цікаво подивитися. І серія постів від Скотта Влашина про розуміння парсер-комбінаторів. Він повністю написав свою власну бібліотеку парсер-комбінаторів. Також цікаво для ознайомлення. Дякую за увагу.