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

cpp reference on regex

cpp reference on regex_search

cpp reference on enums

cpp reference on pair

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