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