Разбор выражений

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

выражение -> слагаемое [+ слагаемое] [- слагаемое]
слагаемое -> множитель [* множитель] [/ множитель]
множитель -> переменная, число или (выражение)

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

Давайте рассмотрим пример. Выражение 10 + 5 * B состоит из двух слагаемых: 10 и 5 * В. Второе слагаемое состоит из двух множителей: 5 и B. Эти множители представляют собой одно число и одну переменную.

С другой стороны, выражение 14 * (7 - С) содержит два множителя: 14 и (7 - С). Эти множители представляют собой одно число и одно выражение в скобках. Выражение в скобках состоит из двух слагаемых: числа и переменной.

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

9 / 3 - (100 + 56)

Если выражение разобрано корректно, разбор происходил в следующем порядке:

1. Получить первое слагаемое, 9 / 3.
2. Получить каждый множитель и выполнить деление чисел. В результате получилось число 3.
3. Получить второе слагаемое, (100 + 56). В этот момент начинается рекурсивная обработка данного подвыражения.
4. Получить оба слагаемых и выполнить сложение. В результате получилось число 156.
5. Вернуться из рекурсивного вызова и вычесть 156 из 3. Окончательным ответом является -153.

Если вас это несколько сбило с толку, не расстраивайтесь. Синтаксический разбор выражений — довольно сложное занятие, к которому нужно привыкнуть. Необходимо помнить о двух основных моментах, когда речь идет о таком рекурсивном представлении выражений. Во-первых, приоритет операций неявно закладывается в порождающие правила. Во-вторых, этот метод разбора и вычисления выражений очень похож на тот способ, которым люди вычисляют математические выражения.