С для профессиональных программистов



         

Порядок построения выражений


Имеется много вариантов анализа и вычисления выражений. Для использования полного синтаксического анализатора рекурсивного спуска мы должны представить выражение в виде рекурсивной структуры данных. Это означает, что выражение определяется в термах самого себя. Если выражение можно определить с использованием только символов "+" ,"-" ,"*" ,"/" и скобок, то все выражения могут быть определены с использованием следующих правил:

Выражение = > Терм [+Терм][-Терм]

Терм                 = > Фактор [*Фактор][/Фактор]

Фактор    = > Переменная, Число или (Выражение)

Очевидно, что некоторые части в выражении могут отсутствовать вообще. Квадратные скобки означают именно такие необязательные элементы выражения. Символ => имеет смысл "продуцирует".

Фактически, выше перечислены правила, которые обычно называют правилами вывода выражения. В соответствии с этими правилами терм можно определить так: "Терм является произведением или отношением факторов".

Вы вероятно заметили, что приоритет операторов безусловен в описанных выражениях, то есть вложенные элементы включают операторы с более высоким приоритетом.

В связи с этим рассмотрим ряд примеров. Выражение

10+5*B

содержит два терма: "10" и "5*B". Они, в свою очередь, состоят из

трех  факторов:  "10",  "5"  и  "B",  содержащих два числа и одну

переменную.

В другом случае выражение

14*(7-C)

содержит  два фактора "14"  и "(7-C)",  которые,  в свою очередь,

состоят из  числа и  выражения  в  скобках.  Выражение  в скобках

вычисляется как разность числа и переменной.

Можно преобразовать правила вывода выражений в множество общих рекурсивных функций, что и является зачастую основной формой синтаксического анализатора рекурсивного спуска. На каждом шаге анализатор такого типа выполняет специфические операции в соответствии с установленными алгебраическими правилами. Работу этого процесса можно рассмотреть на примере анализа выражения и выполнения арифметических операций.




Содержание  Назад  Вперед