Написання компілятора LALR(1)-парсерів

Введення або навіщо потрібні синтаксичні аналізатори

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

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

Отже, навіщо ж комусь може знадобитися писати парсер і що це взагалі таке? Парсер - це код, який наділяє вхідний набір символів семантичним змістом. Тобто відбувається аналіз цих символів, і на основі цього аналізу програма розуміє як інтерпретувати ці літери та цифри. Простий приклад - «1+2», після або під час процесу парсингу знак "+" це не просто символ плюсу, але позначення бінарного оператора додавання, а в "+3" це унарний оператор знака числа. Більшості людей це очевидно, машині немає.

Два види парсерів

Ок, після усвідомлення важливості цієї технології, необхідно порушити питання про стандарти написання цього класу програм.

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

Перший підхід означає поділ аналізатора на дві частини - опис формату/схеми вхідної інформації та логіки, яка оперує вже не чистим потоком даних, а структурованим відповідно до схеми. Приклад:

Другий підхід простіше показати, ніжпояснити:

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

Переваги опису граматики:

Незважаючи на все це, і програмування «наживу» має низку своїх плюсів:

Поріг входу значно нижчий. Тобто практично будь-якому програмісту можна сказати — сиди пиши код, і парсер буде запрограмований у запропонованому стилі. Для складання формальної граматики потрібно мати нехай і невеликий, але все ж таки важливий, обсяг теорії — ази математичної логіки, розбиратися в побудові граматики, володіти інструментом генерації коду.
Незважаючи на те, що граматикою можна описати практично все, є винятки. Крім того, до них додається обмеженість інструментарію. Пряме написання коду має найвищу гнучкість.
Є ще зовсім крихітний плюс – все в одному місці. Тобто за нормальної організації програми можна виділяти ключові фрагменти логіки і відразу розуміти їх суть. У першому варіанті у нас практично два необхідні екрани - екран схеми + екран коду. Іноді слід перемикатися між ними для уточнення нюансів. Це не зовсім зручно. Але повторюся, це дуже невелика перевага, особливо якщо врахувати другий плюс роздільного кодування.

Структура парсера

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

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

Насамперед варто розібратися, що ж це за складові. Лексичний аналізатор отримує на вхід потік символів заданого алфавіту (літери, цифри, символи, що використовуються, etc). Далі він розбиває цей потік на комплексніші примітиви (такий ось оксюморон, так), так звані токени або термінали. Наприклад, замість послідовності цифр якоїсь довжини синтаксичний аналізатор отримує «Число» з атрибутом рівним значенню цього числа. Навіщо він потрібний поясню нижче. Далі синтаксичний аналізатор з урахуванням токенів і правил складання символів другого ієрархічного порядку (перший — токени), про нетерміналів, збирає дерево виведення. Ця АТД однозначно представляє структуру розпізнаних даних. І, нарешті, останній етап — це семантичний аналіз отриманого дерева та виконання бізнес-логіки. Саме цей етап представлений на першому лістингу.

Навіщо ж потрібен лексичний аналізатор, якщо він може бути інтегрований в синтаксичну частину? Адже яка різниця, який алфавіт отримувати — вихідний чи новий синтетичний. Відповідь досить очевидна — по-перше, це зазвичай звуження алфавіту, тобто спрощення семантики; по-друге, ми прибираємо один або навіть кілька нижніх рівнів дерева при збереженні його властивостей. Зрозуміло, що лексичний аналізатор не повинен брати на себе роль синтаксичного, а тим більше семантичного, тому на «1+2» він не повинен повертати 3, але найпростіші дії, такі як формування чисел цілком підходить. Трохи ускладнимо приклад, і подивимося надерево виведення у двох випадках. Заодно й покажу, що це за дерево таке тим, хто не зовсім зрозумів короткого пояснення.

Розбір йде вирази 12+34

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

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

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

LL проти LR, або слон проти кита

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

Виділяють дві групи аналізаторів - висхідні (LR) і низхідні (LL).

Свою назву вони беруть від методу побудови дерева виводу. Перший будує дерево знизу вгору, другий зверху вниз. Небагато зупинюся на цьому і наведу найтутупші алгоритми.

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

LL-парсер намагається зробити навпаки - для кожного вхідного символу вгадати, до якого правила він належить. Найбільш примітив це вибір з альтернатив (наприклад, EXPR може розвернутися в ADD або SIGN, тобто 2 альтернативи) за першим символом, і рекурсивний спуск з новим набором правил, які продукують нетермінали з обраного шляху. І так до тих пір, поки не правила не розкладуться до терміналів. Опис досить складне, в коді зрозуміти це буде набагато простіше:

Який синтаксичний аналізатор використовувати – справа смаку. Практично за характеристиками вони однакові. Гуляє байка про те, що в Радах використовували LL(x), а на Заході — LR(x), але не знаю, наскільки це правдиво. Особисто мені ідеологічно сподобався LR, детальніше про нього розповім у наступній частині.

PS: Важливість правильного написання парсерів можна помітити прямо у статті, глянувши на непідсвічену другу ділянку коду, яка обернена в той самий блок source, що і перший приклад.