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