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

       

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


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

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

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

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

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

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

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

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

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) этот метод синтаксического анализа и вычисления выражений очень похож на тот, который вы сами используете для выполнения таких же операций.


Содержание раздела