Учебное пособие C#. Алгоритмы и структуры данных н. А. Тюкачев, В. Г. Хлебостроев издание третье, стереотипное 1 / 23

4.4. О
СНОВЫ РАБОТЫ ИНТЕРПРЕТАТОРА
 
Интерпретатор — это программа, которая переводит исходный текст 
в некоторое промежуточное представление, а потом выполняет соответст-
вующие действия. 
Компилятор транслирует программу, написанную на некотором языке 
высокого уровня, в объектный код. 
Процесс проектирования и создания компилятора заслуживает отдель-
ной книги. Однако можно рассмотреть основные положения работы компи-
лятора на примере построения синтаксического дерева или дерева разбора 
арифметического выражения. И построение дерева разбора, и обход его для 
вычисления выражения — еще один пример использования деревьев. 
Работа компилятора складывается из двух основных этапов [5, 36]. 
Сначала необходимо распознать структуру программы, а затем выдать экви-
валентную программу на машинном языке. Эти два этапа — анализ и синтез. 
После того, как анализатор распознает все конструкции программы, он мо-
жет установить, каким должен быть результат действия этой программы. За-
тем синтезатор вырабатывает соответствующий объектный код. 
Этап анализа составляют две фазы. Первая фаза — лексический анализ. 
Поскольку исходный текст программы представляет собой последователь-
ность символов, необходимо выделять из этой последовательности так назы-
ваемые лексемы, то есть значимые единицы языка программирования, такие 
как зарезервированные слова, идентификаторы, константы, знаки операций и 
т.п. Для выделения лексем используется сканер, задачами которого являются: 
− пропуск разделителей; 
− распознавание и обработка зарезервированных слов; 
− распознавание и обработка идентификаторов; 
− распознавание последовательности цифр в качестве чисел; 
− распознавание знаков операций, скобок и т.п. 
8 / 23

---

101 
Второй фазой является синтаксический анализ, в нашем случае это по-
строение дерева разбора. Разумеется, анализатор должен «знать» синтаксис 
языка. Синтаксис языка программирования наглядно представим в виде син-
таксических диаграмм. 
На этапе синтеза производится обход дерева и формирование объект-
ного кода. Построение компилятора невозможно без рассмотрения формаль-
ных грамматик, ограничений на язык программирования, построения табли-
цы идентификаторов и пр. Но в любом языке программирования присутст-
вуют арифметические выражения, и, не вдаваясь в подробности, на уровне 
здравого смысла рассмотрим синтаксис выражения. На рисунке 4.8 представ-
лены синтаксические диаграммы простого выражения, слагаемого и множи-
теля.
Синтаксические диаграммы отражают принятый приоритет выполне-
ния операций: сначала вычисляем множители, затем слагаемые и наконец 
выражение. Из представленных диаграмм видно, что определения рекурсив-
ны: выражение определяется через множитель, а множитель в свою оче-
редь — через выражение. Из диаграммы выражение также понятно, что до-
пускается использование унарных операций.
Простое выражение: 
Слагаемое: 
Множитель: 
Рис. 4.8. Синтаксические диаграммы арифметического выражения 
Итак, нашей целью является создание интерпретатора: сначала выра-
жение переведем в промежуточное представление — в дерево, а затем это 
дерево будем обходить, вычисляя значение выражения. Для упрощения рабо-
ты, не связанной с построением дерева разбора, в качестве операндов будем 
рассматривать только числа.
9 / 23

---

102 
Для распознавания выражения нам потребуются следующие процеду-
ры: 
− функция Peek() (сканер), выделяющая очередную лексему и 
формирующую ее значение. Если лексема — число, то сканер 
формирует и последовательность цифр, соответствующих этому 
числу. К строке-числу сканер добавляет и унарный минус; 
− функция Expression (выражение), распознающая выражение 
как арифметическую сумму слагаемых; 
− функция Term (слагаемое), распознающая слагаемое как произ-
ведение множителей; 
− функция Factor (множитель), которая обрабатывает числа, скоб-
ки и выявляет синтаксические ошибки. 
На рисунке 4.9 представлена форма, соответствующая проекту, кото-
рый создает, рисует и обходит дерево разбора, вычисляя значение выраже-
ния. 
Рис. 4.9. Дерево разбора арифметического выражения 
Вершины дерева и поддеревьев содержат операции, а в листьях нахо-
дятся операнды. При обработке дерева, т. е. при обходе с целью вычисления 
выражения, операция деления выполняется как вещественное деление с ок-
руглением. 
На форме размещены следующие элементы управления: 
− два текстовых поля для ввода исходного выражения и для вывода 
результата вычисления его значения; 
10 / 23

---

103 
− кнопка «Выполнить», при нажатии на которую обрабатывается 
выражение с одновременным построением соответствующего де-
рева разбора.
Если выражение синтаксически правильное, то дерево рисуется и затем 
производится обход дерева для вычисления выражения и вывода результата. 
Узел дерева описывается следующей структурой: