Читать «Полный справочник по С++» онлайн - страница 438

}

Эта программа получает первый операнд, оператор и второй операнд, а затем выполняет первую операцию, получает следующий оператор и его операнды и т.д. Однако, если этот подход положить в основу всей программы, то результатом выражения 10-2*3 будет число 24 (т.е. 8*3), а не 4, поскольку эта процедура игнорирует приоритет операторов. Нельзя просто перебирать операторы и операнды слева направо, поскольку в соответствии с правилами алгебры умножение имеет более высокий приоритет, чем вычитание. Начинающие программисты часто полагают, что это ограничение легко преодолеть, и иногда, правда, в очень редких случаях, им это удается. Однако, если учесть скобки, возведение в степень, переменные, унарные операторы и тому подобное, задача становится намного сложнее.

Несмотря на то что существует несколько способов создания программы, вычисляющей выражения, мы рассмотрим лишь наиболее простой и понятный. Кстати, именно поэтому он чаще всего применяется. Этот метод называется рекурсивным нисходящим анализом. По мере чтения главы читатели поймут, почему он получил такое название. (Иногда при разработке синтаксических анализаторов применяются другие методы, основанные на сложных таблицах, которые должны генерироваться другими программами. Иногда такие программы называют табличными синтаксическими анализаторами (table-driven parser).)

Синтаксический анализ выражения

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

курсивные структуры данных (recursive data structures). Если бы выражения могли состоять лишь из операций и скобок, то все выражения можно было бы оп

ределить по следующим правилам.

I выражение -> терм [+терм] [-терм] терм -> фактор [*фактор] [/фактор] фактор -> переменная, число или выражение

Квадратные скобки содержат необязательный элемент, а символ -> интерпретируется как глагол “порождает”. Правила, указанные выше, часто называют порождающими правилами (production rules), или продукциями. Следовательно, определение терма можно было бы озвучить так: “Терм порождает фактор, умноженный на фактор, или фактор, деленный на фактор”. Обратите внимание на то, что порождающие правила неявно учитывают приоритет операций.

Выражение

| 10+5*В

состоит из двух термов: 10 и 5*В. Второй терм состоит из двух факторов: 5 и В. Эти факторы состоят из одного числа и одной переменной.

С другой стороны, выражение

| 14*(7-С)

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

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