Використання парсер-комбінаторів в C#: від теорії до практики

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

Усім привіт. Чи виникала у вас колись задача перетворення сирого тексту в чітко структуровані, гарно типізовані дані? Звісно виникала, всі ми як девелопери маємо справу хоча б з одним форматом даних (JSON, XML, YAML тощо). Для цих форматів є купа готових та якісних інструментів. Але що робити, якщо готового інструменту немає? Якщо формат нестандартний, більше того, це взагалі примітивна мова задання обмежень?

Мене звуть Юрій Науринський, я .NET/C# Technical Lead команди MapService в Uklon. Розповім вам про техніку побудови високоякісних інструментів для перетворення примітивних даних в структуровані та покажу це на прикладі, з яким стикнувся під час, здавалося би, простої задачі обчислення часу перекриття доріг. Я розкажу вам про парсер-комбінатори.

Постанова задачі

Взагалі в нас є два варіанти: почати з сухої теорії або з цікавого практичного прикладу. Почнемо зверху вниз — з практики. І поступово, за шматочками, зберемо наявні умови, а з них і задачу.

Як ви вже напевно здогадалися, команда MapService займається чимось, пов’язаним з картографією. А конкретно — пошуком адрес (автокомплітом) та побудовою маршрутів. Під час покращення якості побудові маршрутів ми й стикнулись з один моментом, про який краще розказати на прикладі.

У Києві є така чудова вулиця під назвою «Паркова дорога» з вельми цікавими правилами руху: в робочі дні в години пік односторонній: до центру — 7:15–10:45, із центру — 17:15–19:45. Це треба врахувати під час побудови маршрутів, інакше в часи одностороннього руху маршрут, який потенційно може містити цю вулицю, буде будуватись абсолютно некоректно.

OSM

Ми використовуємо OSM, тож трохи контексту, як там влаштовано зберігання інформації. У нас є 3 ключових складові:

● node
— одна точка;
● way
— набір точок;
● relation
— абстрактне відношення, яке може містити в собі в довільній комбінації довільні node, way, relation.

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

Наразі, ми маємо таку інформацію:

  • в нас є тег access:conditional;
  • він містить в собі інформацію про те, чи перекрита дорога, чи ні, і в який час.

Conditional restrictions теги

Це біль. Як взагалі задати інформацію про те, чи перекрита дорога, чи ні, і в який час? Для цього в OSM був придуманий спеціальний синтаксис:

<restriction-type>[:<transportation mode>][:<direction>]:conditional = <restriction-value> @ <condition>[;<restriction-value> @ <condition>]

access:conditional=no @ (Mo-Fr 16:40-19:45; PH off), який ми вже бачили є типовим прикладом:

  • access - <restriction-type> — що саме ми обмежуємо (в цьому випадку проїзд через дорогу);
  • <transportation mode> — пропущено, бо, вважається, що це обмеження діє на всі можливі транспортні засоби, які можуть рухатися цією дорогою (звичайні автомобілі, вантажівки, автобуси тощо);
  • <direction> — пропущено, дорога перекрита в обидва напрямки (і тут немає сенсу це використовувати, бо дорога і так одностороння);
  • conditional — обов’язковий суфікс;
  • no - <restriction-value> — ні, при заданих умовах проїзд через дорогу недоступний (а якби було yes, було б навпаки);
  • (Mo-Fr 16:40-19:45; PH off) - <condition> — умова, за якої діє обмеження.

Ще декілька прикладів:

  • maxspeed:conditional=130 @ (19:00-06:00)
  • maxspeed:conditional=120 @ (06:00-20:00); 100 @ (22:00-06:00)
  • motor_vehicle:conditional=delivery @ (Mo-Fr 06:00-11:00,17:00-19:00;Sa 03:30-19:00)

Наче нескладно, регулярка в поміч! Не зовсім. Диявол криється в значеннях <condition>.

Специфікація є ось тут. Діаграма синтаксису виглядає так:

Це тільки початок. Дозволю собі процитувати автора специфікації:

Grammar for time domain values
  • Is compatible with the proposals examples (except the time is obligatory).
  • Covers all values I found (as formal expression is possible at all).
  • The very common plain text conditions can be expressed as «...» comments.
  • Can be evaluated sufficiently simple.

Відчуваєте тут щось підступне?

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

Висновки, які ми зробили з досвіду використання специфікації:

  • Специфікація неформальна!
  • Це лише набір рекомендацій!
  • Ми повинні бути готові до обробки будь-яких значень тегів.
  • Повинна бути гнучкість в додавнні обробки нових значень тегів.

Запам’ятаємо два останні пункти, вони допоможуть обрати нам шлях до успіху. А що потім? Потрібно цю інформацію перетворити на щось, що зрозуміє наш рушій побудови маршрутів — OSRM.

OSRM

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

25296,25295,24
34491,34494,3
1283974,2387,3

Формат дуже простий: стартовий ідентифікатор way, кінцевий ідентифікатор way, швидкість в кілометрах на годину. Іншими словами, задаємо ребро дорожнього графа обома його вершинами та швидкість на ньому.

Як це пов’язано з перекриттям доріг? Дуже просто — якщо передати швидкість нуль, тоді дорога перекрита.

Задача

Отже задача полягає в тому, щоб виконати три простих кроки.

Хоча кроки перший і останній також доволі цікаві (вартує окремої статті?), наразі ми сконцентруємось на тому кроці, заради чого ми використовуємо парсер-комбінатори: дізнатись з кожному тегу, чи перекрита дорога, чи ні.

Розвʼязання задачі

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

Дещо формалізуємо задачу. У нас є неструктуровані сирі дані — значення тегу з суфіксом :conditional (наприклад no @ (Mo-Fr 16:40-19:45; PH off)).

Потрібно повернути звичайний bool. Трохи обміркувавши задачу, розбиваю її далі на такі кроки:

Добре, тепер в нас є два послідовних кроки розвʼязання задачі, ідемо далі за ними.

Парсинг

Теорія

Що це слово взагалі означає?

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

Поки що не дуже зрозуміле визначення. Насправді я впевнений, що ви вже стикалися з парсерами раніше (JSON, наприклад). Але що, якщо я скажу вам, що парсери можна... поєднувати між собою?

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

Парсер-комбінатори виходять на сцену:

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

Типовим підходом є побудова дерева парсерів знизу вверх — з примітивних маленьких шматочків і далі вверх драбиною складності:

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

На практиці можливість практично довільної комбінації парсерів дає фантастичну гнучкість в побудові практично будь-яких парсерів. А гнучкість нам дуже потрібна...

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

  • натурально випливає з природи парсер-комбінаторів;
  • можемо використовувати вже кимось написані парсери;
  • можемо ділитись своїми парсерами;
  • перевикористаність потужно зростає до небес;
  • у результаті композиції ми отримуємо гарантовано валідний парсер. Вельми зручно використовувати систему типів для забезпечення комфорту своєї роботи!

Отже через феноменальну гнучкість та перевикористаність ми обрали підхід з побудовою свого парсера за допомогою парсер-комбінаторів для парсингу значень тегів умовних обмежень.

Альтернативні варіанти парсингу значень тегів умовних обмежень.

Мені дуже сподобався вираз з цієї статті — «Регулярки незбагненні!». Що це значить? Усе дуже просто: коли ви дивитесь на регулярний вираз, чи можете ви одразу сказати, що він робить? Цікаво дізнатись вашу думку, пишіть в коментарях.

Так от, є підозра, що таких надлюдей небагато, тому і вважається, що регулярки write-only — простіше написати нову, ніж редагувати стару!

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

Питання залишається лише одне — воно того варте? Вирішувати лише вам, але пам’ятайте, що у світі завжди є щось більше ніж «комфортні» та звичні регулярки...

Більш просунуті читачі можуть сказати, що варто написати свій самописний парсер, і, насправді, якщо пошукати, то самописні парсери й попадаються (приклад 1, приклад 2, це ще не всі можливі), але:

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

Отже оптимальним варіантом для нас залишилися лише парсер-комбінатори. Можливо, ви бачите інші варіанти?

Практика

Настав час перейти до практики. Як ця вся суха теорія виглядає в реальному коді?

Ми використовуємо мову програмування C#. Залишилося тільки визначитися, яку бібліотеку парсер-комбінаторів обрати. Вибір є: це Sprache, Pidgin, FParsec. Ми обрали Pidgin — швидкий, гнучкий, невеликий. Насправді підійде будь-яка з них, базові принципи роботи незмінні. Різниця лише у специфіці використання.

Парсинг

Для прикладу оберемо таке значення тегу:

Apr,Jun-Aug,Dec 10:00-15:00; Mo-We,Fr 08:00-12:00,13:00-17:30; Sa 08:00-12:00; PH 09:00-12:00

Вираз обчислюється зліва направо, кожне правило розділене крапкою з комою, кожне — перекриває попереднє. Порядок обчислення правил виглядає так:

● У квітні, з червня до серпня, в грудні — робочі години з 10 до 15
— це виходить для усіх днів.
Але з понеділка до середи та в п’ятницю робочі години 8–12 та 13–17.
● У суботу робочі години 8–12.
● Під час свят робочі години 9–12
— є два типи свят:
— PH — Public Holidays — звичайні свята;
— SH — School Holidays — шкільні канікули.

Оскільки правила перекривають попередні, тоді правильним є те, що якщо свято припадає, наприклад, на вівторок, то робочі години тільки з 9 до 12. Або для будь-якого місяця в суботу робочі години 8–12. Звісно, якщо на цю суботу не припадає свято — тоді робочі години 9–12.

Є чудовий сайт, який наочно показує, чи попадає момент часу в задане тегом обмеження. Декілька прикладів:

Час їсти слона! Тестовий вираз виглядає ось так:

Apr,Jun-Aug,Dec 10:00-15:00; Mo-We,Fr 08:00-12:00,13:00-17:30; Sa 08:00-12:00; PH 09:00-12:00

З яких шматочків він взагалі складається? Використовуємо підхід «знизу вверх» та аналізуємо. Перше, що спадає на думку — це час. Примітивний шматочок часу: 10:00. Консультуємось зі специфікацією та визначаємо, які є можливі значення часу.

Нічого екстраординарного ми не побачили, можна сміливо парсити. Перш за все, треба розпарсити двокрапку:

Char — це вже вбудований в Pidgin-парсер. Пам’ятаємо про композиційність! Далі є різні варіанти парсингу годин та хвилин:

  • задати кожне можливе значення для години / хвилини;
  • знайти щось спільне, щоб використати один парсер для обох елементів.

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

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

Зверніть увагу на тип Parser<char, int>. Це буквально те, що було в теорії. На вхід — сирі дані, тобто послідовність токенів (тобто послідовність літер). На виході — структуровані дані — число. На мою думку, найбільший буст до читабельності дає нестандартне використання LINQ Query syntax, як у наступному прикладі, який парсить уже повноцінний рядок годин та хвилин.

Цікаво, як вам читабельність цього синтаксису? Так, це незвично виглядає. LINQ Query syntax взагалі-то для IEnumerable призначений, але за своєю суттю — це синтаксичний цукор, який можна використати для своїх потреб. Детальніше про цей трюк із синтаксисом можна почитати, наприклад, тут.

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

  1. Використовуючи вже відомий нам парсер TwoDigitNumberParser, отримуємо години.
  2. Наступним елементом ми обов’язково повинні розпарсити двокрапку! Сенсу використовувати її значення немає ніякого, можна замінити, наприклад, на нижнє підкреслення. Але, на жаль, C# не сприймає нижнє підкреслення в LINQ Query Syntax як wildcard змінну, тому їх доводиться нумерувати. Це, мабуть, єдиний мінус до читабельності. Чи не єдиний?
  3. Далі обов’язково ідуть хвилини.
  4. Перевіряємо, чи валідне число ми взагалі отримали для годин та хвилин.
  5. Створюємо кортеж з уже перевірених чисел, які означають години та хвилини.

Важливий момент, який варто зауважити. Що буде, якщо наш парсер намагатиметься розпарсити такий рядок: 10.00? Очевидно, що рядок розпарсити не вийде. Парсер розпарсить години, далі зустріне точку, хоча очікувалась двокрапка. Це зупинка процесу парсингу та повертання помилки. Далі процес парсингу не піде (але є можливість це підправити). У типах ця помилка не виявляється, вона схована всередині парсеру.

Наче нескладно? Їмо далі.

Наступним базовим елементом є день тижня. Наприклад Mo, We, Fr:

Виглядає примітивно. Що спільного у всіх днів тижня? Це завжди рядок з двох символів.

Тоді треба робити парсер за аналогією з парсером годин та хвилин? На практиці ж ми зробили трохи хитріше. У C# насправді вже є чудовий enum під назвою DayOfWeek:

namespace System;
public enum DayOfWeek
{
    Sunday = 0,
    Monday = 1,
    Tuesday = 2,
    Wednesday = 3,
    Thursday = 4,
    Friday = 5,
    Saturday = 6,
}

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

Логіка роботи:

  1. Парсимо рядок літер.
  2. Намагаємося з рядка літер отримати день тижня.
  3. Фільтруємо по властивості — вдалося / не вдалося.
  4. Створюємо селектор дня тижня (про селектори трохи згодом в розділі про обчислення).

Трохи дисклеймеру: що за IsSome та ValueUnsafe()? Ми використовуємо бібліотеку language-ext, це властивість та метод типу Option, за деталями відсилаю до своєї доповіді.

Рухаємось далі! Що ще нам треба розпарсити? Свята? Легко!

Примітивно.

Єдине питання — що таке CIString? Це означає, що ми парсимо рядок, і регістр символів цього рядка нас не хвилює, підійдуть обидва. Ми можемо дозволити собі розкіш приймати як валідне значення рядок pH, наприклад. Або Ph. У нашому контексті — яке точно свято, а не індикатор кислотності / лужності, наприклад.

Як щодо місяців?

Тут, на жаль, ніяк не схитруєш. Або ми не знайшли спосіб? Тому просто прописали всі значення місяців в окремій колекції.

Знову парсимо рядок і шукаємо серед відомих значень те, яке розпарсили. Якщо валідно, тоді нам пощастило.

Надто примітивно? Час більш абстрактних речей.

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

Усі діапазони з прикладу:

Jun-Aug 10:00-15:00 Mo-We 08:00-12:00 13:00-17:30 08:00-12:00 09:00-12:00

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

Діапазон насправді дуже простий — це всього лише початок та кінець зі специфічними роздільниками діапазонів.

Алгоритм роботи парсера діапазонів:

1. Отримуємо парсер елементу діапазону.
2. Отримуємо функцію-фабрику створення структурованих даних з діапазону.
3. Отримуємо функцію перевірки валідності діапазону:
1. ми ж не можемо задати те, що вівторок іде перед понеділком;
2. насправді можемо, і це окремий біль під час обчислення умов, тому поки таку можливість не підтримуємо.
4. Використовуючи зручний, приємний на вигляд та дотик LINQ Query syntax, парсимо наш діапазон.

Як виглядає парсер Dash — залишу на ваші роздуми. (Корисно писати статті, тільки зараз помітив, що цей парсер насправді повинен називатися Hyphen).

У чому тут міць та привабливість?

Міць. Цей код працює для всіх можливих діапазонів. Діапазон місяців? Будь ласка! Днів тижнів чи часу? Дайте два! Хочеться взагалі супер гнучкості? Ніщо не заважає її додати! (Крім системи типів, звичайно).

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

Є ще один гарний наочний приклад використання парсер-комбінаторів — послідовності. Це звичайна колекція елементів, розділених комою. Усі послідовності з прикладу:

Apr,Dec 08:00-12:00,13:00-17:30

Ще один абстрактний парсер-комбінатор:

Алгоритм роботи парсера послідовностей:

  1. Отримуємо парсер роздільника послідовностей. Взагалі це кома, але по специфікації може бути і крапка з комою в залежності від того, що за послідовність.
  2. Отримуємо парсер елементу послідовності.
  3. Отримуємо функцію-фабрику створення послідовності з її елементів.

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

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

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

Згадаємо наш тестовий вираз:

Apr,Jun-Aug,Dec 10:00-15:00; Mo-We,Fr 08:00-12:00,13:00-17:30; Sa 08:00-12:00; PH 09:00-12:00

Тут чотири правила:

  1. Apr,Jun-Aug,Dec 10:00-15:00
  2. Mo-We,Fr 08:00-12:00,13:00-17:30
  3. Sa 08:00-12:00
  4. PH 09:00-12:00

Парсер правила відповідає за кожне з вище перелічених правил. Не буду навантажувати тим, що за внутрішні парсери використовуються; нас цікавить, що таке Try та Or.

Or — не вдалося розпарсити першим парсером? Не страшно, спробуємо наступним! Іншими словами, парсимо першим парсером або другим.

Try — пам’ятаєте, як я казав: якщо не вдалося щось розпарсити, то можна спробувати ще раз? Саме для таких випадків і призначений Try. Парсер працює посимвольно, Try всього лише повертає позицію парсинга на той символ, з якого ми починали парсити невалідний вираз. Це означає, що можна спробувати розпарсити вираз ще раз, це якраз чудово працює в комбінації з Or.

Фінальний парсер для всього виразу:

Дерево синтаксичних елементів для тестового виразу (трохи спрощене для зручності):

Ми буквально побудували дерево парсерів знизу вверх, комбінуючи прості елементи в складніші. Сам виклик парсеру виглядає ось так:

Лаконічно. Єдине що — незрозуміло, це що за тип зрештою виходить?

Result<TimeDomain> якраз інкапсулює в собі два можливих результати парсингу: успішний, де повертаються сформовані нами структуровані дані, та неуспішний, де повертається інформація про помилку. Залишилось тільки сказати декілька слів про обчислення тимчасових умов.

Обчислення

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

Як тоді буде виглядати якийсь селектор? Розглянемо на прикладі діапазону часу (нагадаю приклад 08:00–12:00):

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

Спрощено для стислості. Звісно, ми пишемо все як імутабельні класи!

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

Ідентифікатор — номер дня тижня. Можна за цим ідентифікатором задати відношення порядку, чітко сказати, який день тижня більший чи менший за інший. Зручно, просто, ефективно.

Як буде виглядати селектор для послідовності? Ось його основна частинка:

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

Тестування

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

Тут чудово показує себе TDD — спочатку розписали всі тестові випадки, потім пишемо для них парсер. Як ідея на подумати: є ще варіант тестувати парсери за допомогою property tests.

Висновки

Інколи регулярних виразів просто недостатньо, а складні задачі валяються на дорозі. Парсер-комбінатори — ефективна та зручна на практиці техніка парсингу складних неструктурованих даних.

Практичні поради

— Парсер будується один раз, використовується багато разів.

— Піклуєтеся про перформанс? Міряйте — мені, наприклад, достатньо, а вам? Відповідь можна отримати тільки практичними замірами.

— Є різні варіанти, як можна розпарсити навіть найпростіше значення:

• обирайте найпростіший з точки зору readability та supportability;
• це зазвичай LINQ Query syntax;
• але пам’ятайте про свої вимоги щодо перформансу.

Корисні посилання

👍ПодобаєтьсяСподобалось7
До обраногоВ обраному9
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

я конечно небольшой спец в парсерах, но мне кажется что правильнее было бы назвать статью «Методика разбора строки при помощи..... », а не «парсеры». при слове «парсер» мне лично в голову приходят yacc/byson/antr/javacc

я конечно небольшой спец в парсерах, но мне кажется

От саме цьому

при слове «парсер» мне лично в голову приходят yacc/byson/antr/javacc

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

От саме цьому

Єто біла ирония :)

Звісно що концепція складніша у розумінні ніж швиденько наляпати на antlr, але має свої плюси.

Ну, я «наляпал» на антлр грамматику для Постгре (не без ошибко, проотвечался в некоторіх местах с precendency), так что парсинг строки я худо бедно понять, наверное, смогу. Да и с прочими парсерами тоже немного работал, тоже для парсинга скл кода разніх производителей.

Насчет «имеет свои плюсі» — не спорю, вероятно для простіх случаев примитивній ручной парсер будет значительно более єффективнім, нежели «комбайн» того же антлр (которій в 4й версии куда более мощній — но сложній и медленній, по сравнению с 3м)
Просто хотелось чуть большей точности в описании.

Искренне надеюсь что не слишком ущемил Ваш пафос :)

Єто біла ирония :)

якщо пропускати тег то так завжди і буде

Насчет «имеет свои плюсі» — не спорю, вероятно для простіх случаев примитивній ручной парсер будет значительно более єффективнім, нежели «комбайн» того же антлр (которій в 4й версии куда более мощній — но сложній и медленній, по сравнению с 3м)

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

Искренне надеюсь что не слишком ущемил Ваш пафос :)

так я ж знав кому відповідав, нічого іншого і не очікувалось))

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

Вот это уже звучит разумно,
Это имело бы смысл озвучить в статье.
Потому как если у нас есть «парсеры из коробки» разных уровней сложности — это это прекрасно.
К примеру, сейчас я пишу себе вспомогательные скрипты для тестирования неважно чего. Мне приходится парсить лог файлы тестирования. ПОКА ЧТО мне более чем хватает регулярок
Но может случится так, что перестанет хватать
и тогда — или совсем врукопашную парсить (не хочется) или заводить комбайн антлр — не хочется еще больше, т.к. гемор еще тот
но если есть некое «промежуточное» решение — это было бы просто великолепно!

я думаю, автору неплохо было бы вставить ваш комент в «заключение» — чтобы были хотя бы ключевые слова на тему «куда смотреть». Это пригодилось бы, и мне, и другим
И было бы неплохо давать расшифровку абревиатур — они привычны для авторам, а вот мне (и многим читателям) пришлось поломать голову — «о чем это мы» ©

я думаю, автору неплохо было бы вставить ваш комент в «заключение» — чтобы были хотя бы ключевые слова на тему «куда смотреть». Это пригодилось бы, и мне, и другим
И было бы неплохо давать расшифровку абревиатур — они привычны для авторам, а вот мне (и многим читателям) пришлось поломать голову — «о чем это мы» ©

це дійсно провтик автора що він пішов у теорію та приклади написання власного «лісапеда»

Parser combinator це ключове слово для пошуку.

Parser combinator це ключове слово для пошуку.

Для теории? Вполне модет быть
Для практики? тут скорее нужно всё таки «parsec, fparsec»

Ну, я «наляпал» на антлр грамматику для Постгре (не без ошибко, проотвечался в некоторіх местах с precendency), так что парсинг строки я худо бедно понять, наверное, смогу.

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

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

yacc/byson/antr/javacc

Це не парсери, а генератори парсерів. Наприклад, Comparation of parser generators

Комбінатор парсерів, монадічний парсер це досить стала термінологія: Parser Combinator (wiki)

Це не парсери, а генератори парсерів.

если біть точнім — то да, конечно.

Комбінаторний парсер, монадічний парсер це досить стала термінологія.

Вполне может біть, не буду спорить
Но если писать статью на какую-то тему, то следует расчитівать на то, что её придут читать люди которые понятия не имеют о вещах, которые «ну, это уже устоялось». Для меня вот это нечто новое, поэтому некоторые вещи вызывают вопросы
но вообще написать статью так, чтобы она не вызывала вопросов и была целиком последовательная и последовательно раскрывала тему без необходимости забегать вперёд, без «тёмных» мест или без излишнего разхяснения общеизвестных (?) деталей — это занятие сложное и не для слабонервных.

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

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

Але одна з проблем парсер-генераторів, яка ніяк не описана у статі, це комбінаторний вибух (читай швидкодія), на деяких вводах для парсінгу нам треба буде перебрати дуже забагато варіантів (try). Тому часто трюки на кшталт

let parser = (++) <$> string "HT" <*> (string "TP" <|> string "ML") :: CharParser st String
працюють швидше.
Проблема генератора парсера полягає у тому, що граматика має бути контексно-вільною... А от якщо брати текст, який приходить зовні, то там часто ніяких гарантій немає.

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

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

Мається на увазі щось типу yacc?
Як варіант, якщо в вас є досвід використання, цікаво було б послухати.

Скільки ця вулиця крові попила

Радує технічний контент на форумі а не всяка маргінальщина

Цікаво скільки би ви часу і бюджету зекономили якби обрали екосистему де є готові ліби для osm парсингу(швиде гугління показало ще усюди майже крім .net) — js/python/java etc.. :)

Тести у вас не дуже зручні і продумані.
1. тест кейси не будуть зрозумілі для людини яка не знає протоколу;
2. у вас якщо відвалится якийсь конкретно парсер то відвалюється одразу декілька тестів,
3. для ассертів ви використовуєте вихід(серіалізовована строка) який не використовується системою для вашої логіки напряму(структуровані типизовані рули) — те що ви б мали тестувати.

Ця ліба не має пітримки того що описано у статті як я бачив, але я детально не вивчав АПІ. навідміну від інших екосистем:
pypi.org/...​-opening-hours-humanized
github.com/...​ng-hours/opening_hours.js

Це бібліотека для вичитки osm.pbf файлів, яку ми теж використовуємо в своїх проектах.

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

Ні, все ж таки парсери на Haskell писати набагато краще, менше boilerplate. Дуже багато шуму.

Згоден, але знову таки тут питання про взагалі іншу мову програмування, екосистему, підтримку, тощо...

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