|
Страница 34 из 37
Синтаксический разбор Напомним, что существует целый ряд методов синтаксического
разбора и вычисления выражений. Для целей данной статьи предполо-
жим, что выражения являются рекурсивными структурными данными,
которые определяются в терминах самих себя. Если вы ограничитесь
использованием в выражениях только операторов +, -, *, / и ско-
бок, то сможете сказать, что все выражения могут быть определены
в терминах следующих правил:
выражение=>терм[+терм][-терм]
терм=>множитель[*множитель][/множитель]
множитель=>переменная, число или (выражение)
где любая часть может быть пустой. Квадратные скобки обозначают
необязательность, а => - порождение. Фактически правила являются
правилами порождения выражений. Предшествование операторов подра-
зумевается способом порождения выражений.
Выражение
10+5*В
состоит из двух термов: 10 и 5*В. Однако, включает три множителя:
10, 5 и В. Этими множителями являются два числа и одна перемен-
ная.
С другой стороны выражение
14*(7-С)
имеет два терма 10 и (7-С), один из которых является числом, а
другая дочерним выражением. Дочернее выражение распадается на од-
но число и одну переменную.
Данный процесс формирует основу для рекурсивного нисходящего
синтаксического разбора, который представляет собой набор общих
рекурсивных процедур, носящих цепочный характер. На каждом соот-
ветствующем шаге синтаксический разбор может выполнять заданные
операции в алгебраически правильной последовательности. Для при-
мера рассмотрим синтаксический разбор входного выражения 9/3-(100
+56) и выполнение операций по шагам.
Шаг 1. Взять первую лексему: 9/3
Шаг 2. Взять оба множителя и выполнить операцию деления.
В результате получается 3.
Шаг 3. Взять вторую лексему: (100+56). В данной точке вы
должны рекурсивно проанализировать второе выражение.
Шаг 4. Взять оба числа и сложить. В результате получается
156.
Шаг 5. Возвратиться из рекурсивного вызова и вычесть 156 из
3, что дает ответ - 153.
Если вы немного запутались, не беспокойтесь. Это сложная концеп-
ция. Нужно усвоить два момента о данном рекурсивном взгляде на
выражения: во-первых, предшествование операторов является неявным
при заданных правилах порождения выражений; во-вторых, данный ме-
тод синтаксического разбора и вычисления выражений очень похож на
то, как это делается вручную.
|