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

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

)

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

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

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

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

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

Ссылка на основную публикацию
Adblock detector