Крім регулярних виразів: Вступ до синтаксичного аналізу безконтекстних граматик

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

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

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

  • Теги HTML / XML відкриття / закриття
  • відкрити / закрити фігурні дужки {/} мовами програмування
  • відкрити / закрити дужки в арифметичних виразах

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

Розбір математичних виразів

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

Наприклад, розглянемо вираз: (2 + (3 * (7–4)))

Зверніть увагу, що структура арифметичного виразу є фактично деревом:

 + / \ 2 * / \ 3 - / \ 7 4

Структура дерева, створена в результаті запуску синтаксичного аналізатора CFG, називається деревом синтаксичного аналізу .

Опис безконтекстних граматик

Існує два популярних способи вираження граматики CFG:

  1. Розширена форма Бахуса-Наура (EBNF) - описує CFG з точки зору правил виробництва . Це правила, які при застосуванні можуть генерувати всі можливі юридичні фрази мовою.
  2. Граматика вибору синтаксичного аналізу (PEG) - описує CFG з точки зору правил розпізнавання . Це правила, які можна використовувати для відповідності дійсних фраз у мові.

Формалізм PEG має перевагу перед EBNF, оскільки відображення в парсер є однозначним і може бути легко автоматизовано.

Далі наведено простий ПЕГ, піднятий зі сторінки Вікіпедії, що описує математичні формули, що застосовують основні чотири операції до невід’ємних

цілі числа.

Expr ← SumSum ← Product ((‘+’ / ‘-’) Product)*Product ← Value ((‘*’ / ‘/’) Value)*Value ← [0–9]+ / ‘(‘ Expr ‘)’

Простою англійською мовою ми можемо прочитати це як:

  • Expr є Sum
  • Sumє Productслід нуль або більше суб-моделі , які складаються з «+» або «-» , а потімProduct
  • Productє Valueслід нуль або більше суб-моделі , які складаються з «*» або «/» , за яким слідValue
  • Valueє або одним, або кількома членами набору символів {0, .. 9}, або це відкрита дужка “(“ після якої Exprі закриваюча дужка “)”.

Генератори синтаксичного аналізу проти аналізу бібліотек

Припускаючи, що ви не той тип людей, який любить винаходити колесо (не те, що в цьому щось не так), як правило, існує два варіанти створення парсера:

1. Використовуйте генератор синтаксичного аналізатора - інструмент, який генерує вихідний код синтаксичного аналізатора на основі абстрактного визначення синтаксичного аналізатора. Деякі популярні приклади в JavaScript включають Jison, PEG.js, nearley та ANTLR.

2. Використовуйте бібліотеку синтаксичного аналізу - бібліотеку, яка дозволяє виражати правила аналізу як API. Деякі приклади в JavaScript включають Myna, Parsimmon та Chevrotain.

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

Написання синтаксичних аналізаторів у TypeScript / JavaScript за допомогою бібліотеки аналізу Myna

Нещодавно проект, над яким я працював (мова Heron), вимагав розбір бібліотеки, яка могла працювати в браузері. Мені здалося, що складність та накладні витрати існуючих бібліотек занадто великі. Враховуючи, що я мав попередній досвід написання синтаксичного аналізу бібліотек на C ++ та C #, я вирішив написати бібліотеку парсера під назвою Myna за допомогою TypeScript.

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

Наступний приклад з репозиторію Myna GitHub:

Від конкретного дерева синтаксису (CST) до дерева абстрактного синтаксису (AST)

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

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

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

У Myna AST генерується шляхом створення вузлів із правил, позначених astвластивістю. Технічно ця властивість повертає нове правило, яке має внутрішній набір властивостей, що вказує синтаксичному аналізатору створити вузол синтаксичного аналізу в дереві синтаксичного аналізу.

Використання сформованого дерева абстрактного синтаксису Myna

Ось приклад використання визначеного Myna синтаксичного аналізатора в “Node.JS” для обчислення арифметичного виразу:

Заключні слова

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

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

Якщо вам цікаво, як Myna застосовується до більш складного сценарію, погляньте на мову програмування Chickadee. Це повністю реалізовано в TypeScript і залежить лише від бібліотеки парсингу Myna. Chickadee - це крихітна мова програмування, розроблена спеціально для того, щоб допомогти людям дізнатися про методи впровадження мов програмування.

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