Короткий погляд на роботу Tree Walk Інтерпретаторів

Вступ

🤔 Як запустити цей файл?

Уявіть, що нам дали файл з таким кодом:

let a = 2;   
let b = a * 2;   
console.log("Рішення: ", b);

Як ми маємо зрозуміти цей набір тексту?! 🤯

Ось тут на допомогу приходить інтерпретатор! 🎉

🌟 Завдання інтерпретатора

Основне завдання інтерпретатора — перетворити цей незрозумілий текст на щось, що комп'ютер може виконати. 🖥️✨ Як це відбувається? За допомогою 3 кроків:

Крок 1️⃣: Сканування та токенізація

Перше, що ми повинні зробити — це відсканувати текст і розбити його на токени. 🔍 Токен — це найменша значуща частина коду. Уявіть, що це будівельні блоки програми:

• Ключові слова (наприклад, let, function)
• Літери (наприклад, числа, як 2, рядки, як "hello")
• Ідентифікатори (наприклад, імена змінних, як a, b)
• Оператори (наприклад, =, *)

У будь-якій мові програмування токени зазвичай мають:

1. Тип (наприклад, IDENTIFIER, NUMBER_LITERAL)
2. Значення, якщо воно є (наприклад, 2 — це NUMBER_LITERAL зі значенням 2).

Наприклад:

let -> LET_KEYWORD   
a -> IDENTIFIER "a"   
= -> EQUAL_SIGN (немає значення, тип все говорить)   
2 -> NUMBER_LITERAL 2   
...і так далі

Цей процес сканування та токенізації здійснюється Сканером (або Лексером), який перетворює сирий код на список значущих токенів. 🪄✨

Наприклад:

Код: `let a = 2;`   
Токени:   
1. { тип: LET_KEYWORD }   
2. { тип: IDENTIFIER, значення: "a" }   
3. { тип: EQUAL_SIGN }   
4. { тип: NUMBER_LITERAL, значення: 2 }

Крок 2️⃣: Парсинг тексту

Тепер, коли у нас є список токенів, треба його розпарсити. Парсинг — це процес, в якому ми намагаємось зрозуміти цей текст і перетворити його на Абстрактне Синтаксичне Дерево (AST).

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

🌲 Що таке дерево в програмуванні?

Дерево — це особливий тип структури даних, що нагадує ієрархію. Уявіть його як родовідне дерево або структуру папок на вашому комп'ютері. 🗂️

Ось як це працює:

• Найвища частина називається корінь. 🌟
• Кожен елемент (що називається вузол) може мати підвузли, що відходять від нього.
• Вузли без підвузлів називаються листи. 🍃
• Зв’язки між вузлами називаються ребра.

🛠️ Ключові особливості дерев

1. Відносини батько-дитина:
   Кожен вузол з'єднаний з його батьківським вузлом і може мати нуль або більше підвузлів. Наприклад:

Корінь  
 / \  
 Вузол1 Вузол2  
 / \  
 Лист1 Лист2

1. Правило єдиного шляху:
   Між будь-якими двома вузлами є лише один шлях, тому цикли неможливі! Якщо можна повернутися до кореня, це вже не дерево. 🔄❌

Тепер давайте подивимось, як ця логіка використовується для створення Абстрактного Синтаксичного Дерева (AST).

Швидкий тест: Яке з цих речень правильне?

let a = 2 + 3;   
let = a + 2 3;

Правильно, перше!

Це тому, що друге порушує правила граматики! Без належної граматики ми всі говорили б дурниці, і як людям, так і комп'ютерам було б складно зрозуміти сенс.

Граматика 📚

Є два основних терміни у граматиці парсингу: Термінали та Нетермінали. Якщо уявити аналогію з деревом, термінали це, по суті, листя, а нетермінали — це всі інші вузли. 🌳

Приклад 1

Давайте проілюструємо це на прикладі:

Візьмемо:

a = b + c

Це перетворюється на гілку дерева, що вигля
b c
```

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

Зрозуміло? Ми розбиваємо його на значущу структуру!

Пояснення 🧩

• Нетермінали: =, +
• Якщо вони присутні, це означає, що для граматичної правильності має бути щось зліва, справа або обидва варіанти для цього виразу.
• Термінали: a, b, c
• Це листя дерева, яке не вимагає додаткової структури.

Приклад 2

Приклад 2
Давайте розширимо цю логіку ще одним прикладом:

Розглянемо:
a = b + c * d

Це перетворюється на таку гілку дерева:

=  
 / \  
 a +  
 / \  
 b *  
 / \   
 c d

Тепер ще зрозуміліше:

• Термінали: a, b, c, d
• Нетермінали: =, +, *

Підсумок ✨
Оператори (=, +, *) — це нетермінали, оскільки вони визначають структуру виразу. Змінні (a, b, c, d) — це термінали, оскільки вони представляють кінцеві значення.

Чудово! Тепер, як ми насправді визначимо правила, з якими працюватимемо? 🤔

Синтаксис для граматики ✍️
Існує популярний формальний синтаксис для граматики під назвою BNF. Можна знайти багато цікавих відео на цей рахунок, зокрема на каналі Computerphile! Однак я розгляну набагато простіший синтаксис, схожий на regex, як це описано в книзі Crafting Interpreters.

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

Приклад "псевдоязика" 💡
Ось псевдоязик, синтаксис якого ми будемо створювати:

void name{  
a = 2 + 3;  
b = 10 + 20;  
}

Ця мова не має аргументів у функціях для спрощення, ми уникнемо складної обробки рядків на даний момент. Давайте зробимо все акуратно! 🧹

Будуємо граматику 🛠️
Розіб'ємо ієрархію компонентів в нашому коді і будемо будувати структуру поетапно.

З чого складається програма? 🤔

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

Program = Function+

• + означає 1 або більше.
• Аналогічно, * означає 0 або більше.
  Оскільки програма потребує хоча б однієї функції, ми використовуємо +.

Що таке функція?

Function = header '{' body '}'

Тут:

• header: void name
• body: Вислови всередині фігурних дужок.

Визначення заголовка та тіла

header = DataType Identifier  
body = Statement+

• header: містить DataType та Identifier в такому порядку.
• body: містить 1 або більше виразів.

Визначення DataType та Identifier

DataType = int | float | char | void  
Identifier = (alphabet | _ ) (alphanumeric | _ )*

• | означає "або".
• DataType може бути будь-яким з перерахованих типів.
• Identifier починається з літери або підкреслення, а потім може містити будь-яку кількість алфавітно-цифрових або підкреслень.

* тут означає 0 або більше символів після першого.

Діагностика виразів 🧐

Statement = identifier '=' expression;

Визначення виразу

Для простоти припустимо, що вираз складається з чисел, ідентифікаторів та операторів (+, *):

expression = terminal | (expression operator expression)   
operator = + | *  
terminal = identifier | number

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

Вирішення проблеми пріоритету операторів ⚖️

Проблема:

Розглянемо вираз:

2 + 3 * 4

Наша поточна граматика може обробити його як:

(2 + 3) * 4

Замість правильного оцінювання за BODMAS:

2 + (3 * 4)

Рішення:

Щоб виправити це, ми коригуємо граматику для обробки пріоритету, розділяючи її на рівні:

expression = term ( '+' term )*  
term = factor ( '*' factor )*  
factor = identifier | number | '(' expression ')'

Пояснення:

• term спочатку обробляє множення.
• expression обробляє додавання після того, як терміни будуть оброблені.
• factor включає дужки, щоб дозволити вручну змінювати пріоритет.

З цією граматикою вираз 2 + 3 * 4 буде правильно розібраний як:

2 + (3 * 4)

Як це працює?

term спочатку обробляє множення, оскільки воно визначене на більш низькому рівні.

• expression обробляє додавання лише після того, як терміни будуть розв'язані.
• factor включає дужки, щоб дозволити змінювати пріоритет вручну.

Використовуючи цю граматику, вираз 2 + 3 * 4 розбирається так:

expression -> term '+' term   
term -> factor '*' factor   
factor -> 3, 4

Це забезпечує правильний порядок операцій: спочатку множення (3 * 4), потім додавання (2 + 12), що дає правильний результат 14.

Дерево розбору в дії

Граматика до цього моменту:

Program = Function+   
Function = Header '{' Body '}'   
Header = DataType Identifier   
Body = Statement+   
Statement = Identifier '=' Expression   
Expression = Terminal | (Expression Operator Expression)   
Operator = '+' | '*'   
Terminal = Identifier | Number   
DataType = 'int' | 'float' | 'char' | 'void'   
Identifier = (alphabet | _ ) (alphanumeric | _ )*

Приклад коду:

void func1 {   
 a = b + c * d;   
}   
void func2 {   
 x = y + z;   
}

Дерево розбору (ASCII стиль)

Program  
├── Function (func1)  
│ ├── Header  
│ │ ├── DataType (void)  
│ │ └── Identifier (func1)  
│ ├── Body  
│ │ └── Statement  
│ │ ├── Identifier (a)  
│ │ ├── '='  
│ │ └── Expression  
│ │ ├── Identifier (b)  
│ │ ├── '+'  
│ │ └── Expression  
│ │ ├── Identifier (c)  
│ │ ├── '*'  
│ │ └── Identifier (d)  
├── Function (func2)  
│ ├── Header  
│ │ ├── DataType (void)  
│ │ └── Identifier (func2)  
│ ├── Body  
│ │ └── Statement  
│ │ ├── Identifier (x)  
│ │ ├── '='  
│ │ └── Expression  
│ │ ├── Identifier (y)  
│ │ ├── '+'  
│ │ └── Identifier (z)

Ось продовження, крок за кроком, починаючи з Дерево розбору (боковий стиль):

Дерево розбору (боковий стиль)

Для функції func1:

=  
 / \  
 a +  
 / \  
 b *  
 / \  
 c d

Для функції func2:

=  
 / \  
 x +  
 / \  
 y z

Повне дерево програми:

Program  
 ├── Function (func1)  
 │ \  
 │ =  
 │ / \
│ a +  
 │ / \  
 │ b *  
 │ / \  
 │ c d  
 └── Function (func2)  
 \  
 =  
 / \  
 x +  
 / \  
 y z

Це поділ показує, як програму можна розпарсити в дерево для зручнішого тлумачення.

Погляд на реалізацію

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

Отже, у нас є лічильник, який відслідковує поточний індекс токена. Він починається з 0 і йде до кінця списку токенів. Тепер у нас є дві функції: match і consume. match(token) перевіряє, чи є поточний токен таким самим, як той, що передано в аргументі, і повертає булеве значення.
consume(token, errorMsg) приймає тип очікуваного токена та повідомлення про помилку. Якщо токен не такий, як ми передали, код припиняється з виведенням помилки. Знову ж таки, для деталей реалізації перегляньте книгу, це справжня скарбниця знань. Я тут лише, щоб дати вам загальне уявлення.

Прогулянка і Пост-Одерна Траверсія

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

Пост-Одерна Траверсія (Лівий-Правий-Корінь)

У пост-одерній траверсії ми відвідуємо:

1. Ліве піддерево.
2. Праве піддерево.
3. Корінь.

Приклад:

Для бінарного
D E
```

Кроки:

1. Відвідайте ліве піддерево (B → D → E).
2. Відвідайте праве піддерево (C).
3. Відвідайте корінь (A).

Вихід пост-одерної траверсії:

D → E → B → C → A

Основне правило: Спочатку обробляйте дочірні елементи, а потім батьківський.

Приклад:

Розглянемо вираз, представлений таким бінарним деревом:

=  
 / \  
 a +  
 / \  
 b *  
 / \  
 c d

Де:

• b = 1
• c = 2
• d = 3

Підхід пост-одерної траверсії:

1. Починаємо з кореня: Корінь — це знак =, що означає присвоєння. Для виконання цього присвоєння спершу потрібно оцінити обидві сторони рівняння: лівий бік (LHS) і правий бік (RHS). Це вимагає, щоб ми пройшли по обох сторонах дерева, використовуючи пост-одерну траверсію.
2. Ліве піддерево (LHS): Ліва частина — це просто a, термінальний ідентифікатор. Додаткове проходження тут не потрібно, тому просто беремо a як є.
3. Праве піддерево (RHS): Правий бік — це оператор +, який є нетерміналом. Отже, нам потрібно здійснити пост-одерну траверсію правого піддерева, яке складається з:

• Лівий нащадок: b (термінал зі значенням 1).
• Правий нащадок: * (інший нетермінал).

1. Піддерево з * (право від +): Оператор множення (*) також вимагає пост-одерної траверсії. Він має два нащадки:

• c (термінал зі значенням 2).
• d (термінал зі значенням 3).

Оскільки обидва c і d є термінами, ми спочатку їх оцінюємо: c = 2 і d = 3. Множення (c * d) дає нам 2 * 3 = 6. Тепер вузол * стає:

*  
/ \  
2 3

Ми замінюємо вузол * на 6:

+  
/ \  
b 6

1. Остаточний крок: Тепер, коли ми вирішили обидва нащадки вузла + (b = 1 і результат множення * = 6), ми можемо оцінити додавання: 1 + 6 = 7. Тому вузол + замінюється на 7:

=  
/ \  
a 7

1.
Розв'язання присвоєння: Нарешті, ми можемо присвоїти значення 7 змінній a: це остаточний результат пост-одерної траверсії та процесу оцінки для цього простого виразу.

Ключові моменти:

• Пост-одерна траверсія: Цей процес спочатку відвідує ліве піддерево, потім праве піддерево і, зрештою, корінь, гарантуючи, що ми оцінюємо операнди перед операторами.
• Рекурсивна траверсія: Нетермінали (як + і *) вимагають рекурсивної траверсії для розбиття виразу на простіші компоненти, що зрештою зводить вираз до термінальних значень, які можна обчислити.
• Оцінка: Після того, як дерево повністю розібрано і зведено до термінальних значень, остаточний результат можна обчислювати крок за кроком.

Розширення цієї концепції:

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

Пропозиція для проєкту:

Чудовим проєктом для початківців буде побудова калькулятора, який може обробляти кілька арифметичних операцій:

• Наприклад, ви можете написати вираз, як:

a = 2 + 4  
b = a / 2 + 20

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

• -

Обмеження

Інтерпретатори на основі обходу дерева прості в реалізації, але страждають від поганої продуктивності через безпосереднє виконання Абстрактного Синтаксичного Дерева (AST) під час виконання, без оптимізацій, таких як пріоритети операторів або керування пам'яттю. Вони повільніші за компільовані мови, оскільки не мають оптимізацій і виконують зайву роботу під час інтерпретації. На відміну від цього, компіляція в машинний код перетворює код безпосередньо в машинну мову, що забезпечує чудову продуктивність, але без гнучкості. Компіляція у байткод перетворює код у формат, незалежний від платформи, забезпечуючи портативність і деякі оптимізації, а компіляція Just-In-Time (JIT) динамічно компілює код під час виконання, надаючи продуктивність, близьку до машинного коду, з перевагою динамічних оптимізацій, хоча й з додатковими витратами на початкову компіляцію. Я наполягаю, щоб ви ознайомилися з іншими методами компіляції і спробували удосконалити свою модель згодом.

Ви можете ознайомитись з моїм інтерпретатором, Solunox

Перекладено з: How Interpreters Work?