Video about what the parser is and its types
Wiki article about lexical analysis
Wiki about parser in general and parsing process
Wiki on recursive descent parsers
video explaining CFG and PEG in detail
cpp reference on function wrappers
a series of articles on parsing topic
Написати програму-інтерпретатор математичних виразів, що підтримує змінні та (в більш складному варіанті) оператори розгалуження. Можете взяти за основу вашу або чиюсь попередню лабораторну роботу із Shunting Yard.
В цій роботі замість того, щоб одразу обчислювати значення кожної операції, необхідно спочатку побудувати абстрактне синтаксичне дерево виразу. Далі обчислення виразу зводиться до обходу дерева в глибину і обчислення значення вузлів дерева або прийняття рішення про зміну порядку обходу дерева. Як приклад, можна навести умовний оператор: обчислюється лише одна з гілок вершини цього оператора, а інша пропускається.
Значення змінних під час обходу дерева найкраще зберігати в хеш-таблиці. Ніякі типи даних, крім чисел із плаваючою комою, впроваджувати не обов'язково.
AST використовують щоразу при компіляції програм написаних практично всіма мовами програмування. Наприклад, наступному фрагментові коду (приклад з вікіпедії)
while b ≠ 0
if a > b
a := a − b
else
b := b − a
return a
може відповідати таке дерево:
На вхід програмі подається текстовий файл з кодом, наприклад:
abc = 1;
q = 3;
2+abc*q;
Програма має вивести результат обчислення останнього виразу на екран:
result = 5.0