Завдання синтаксичного аналізу полягає в тому, щоб по наявному рядку, що містить арифметичне вираження, і відомим значенням, що входять в неї змінних, вичислити значення вираження.
Процес обчислення арифметичних виразів можна представити у вигляді бінарного дерева. Дійсно, кожен з арифметичних операторів (+- *, /) вимагає двох операндів, які також будуть арифметичними виразами і, відповідно можуть розглядатися як піддерева. Рис. 7 показує приклад дерева, відповідного вираженню:
У такому дереві кінцевими вузлами завжди будуть змінні (тут x) або числові константи, а усі внутрішні вузли міститимуть арифметичні оператори. Щоб виконати оператор, потрібно спочатку вичислити його операнди. Таким чином, дерево на малюнку слід обходити з кінця. Відповідна послідовність вузлів називається зворотним польським записом арифметичного вираження.
При побудові синтаксичного дерева слід звернути увагу на наступну особливість. Якщо є, наприклад, вираження
і операції складання і віднімання ми прочитуватимемо зліва на право, то правильне синтаксичне дерево міститиме мінус замість плюса (рис. 8а). По суті, це дерево відповідає вираженню. Полегшити складання дерева можна, якщо аналізувати вираження (8) навпаки, справа наліво. В цьому випадку виходить дерево з рис. 8б, еквівалентне дереву 8а, але таке що не вимагає заміни знаків.
Аналогічно справа наліво треба аналізувати вирази, що містять оператори множення і ділення.
Рис. 8. Синтаксичні дерева для вираження a - b + c при читанні зліва направо (а) і справа наліво (б).
Результатом аналізу рядка має бути послідовність вузлів дерева в кінцевому порядку. Кожен вузол повинен зберігати інформацію про підвузли і про ту операцію, яка здійснюється. Наприклад, вузли можна реалізувати у вигляді записів, одне з полів якої має процедурний тип. Інший варіант - кожен вузол це об'єкт, де операція реалізована як віртуальний метод.