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

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

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

Арифметическое выражение, сокращенно (а. в.), индуктивно определяется следующим образом:

• 1. Любая переменная - это (а. в.).

2. Любая константа - это <а. в.).

3. Любая ссылка на арифметическую функцию - это (а. в.).

4. Если X - <а. в.), то (X) - тоже (а. в.).

5. Если X и Y-оба <а. в.), то (а. в.) также будут {X-Y), (X/F), (X**F).

6. Ни один объект не является арифметическим выражением, если то, что он арифметическое выражение, не следует из конечного числа применений правил 1-5.

Это определение дает набор эффективных правил, пригодных для построения любого арифметического выражения в терминах переменных, констант, ссылок на функции и операций +, -, «, / и **. Заметим, что в этом определении отсутствуют определения «переменной», «константы» и «ссылки на функцию». Мы предполагаем, .что читатель знаком с этими терминами.

Рассмотрим выражение

(((Л-В)*С)-1-(0/(£**/=-)))

Если это правильное арифметическое выражение, то должна существовать возможность построить его с помощью правил 1-5. Пример такого построения приведен на рис. 5.3.1.

Возможно иное описание этого арифметического выражения с помощью корневого двоичного дерева - рис. 5.3.2. Заметим, что все конечные вершины этого дерева соответствуют переменным или операндам, а все внутренние вершины соответствуют арифметическим операциям. Если задано это двоичное дерево, выражение легко вычисляется при известных значениях переменных. Например, предположим, что переменные имеют следующие значения: Л =4.0, В=1.0, С=5.0, D=64.0, £=2.0 и f=5.0. Значение арифметического выражения можно вычислить, проходя вверх по дереву от конечных вершин к корню, как показано на рис. 5.3.3.

Интересно заметить, что рис. 5.3.3, а и б наглядно показывают, что некоторые из промежуточных вычислений, необходимых для получения значения всего выражения, можно провести параллельно. Например, вычитание А - В можно выполнить параллельно с возведением в степень fssF. В литературе можно найти множество работ, посвященных параллельному вычислению арифметических выражений; заинтересованного читателя мы отсылаем к гл. 7 за ссылками по этому вопросу.

Логические выражения можно определить так же, как и арифметические. Для этого нам прежде всего нужно определить выражение отношения. Выражением отношения называется выражение вида (а. в.) (отн.) (а. в.), где (отн.) - одна из следующих шести операций отношения:

< < = Ф>>

Логическое выражение, сокращенно (л. в.), определяется индуктивно следующим образом:

1. Любая логическая константа есть (л. в.).

2. Любая логическая переменная есть (л. в.).

3. Любое выражение отношения есть (л. в.).

4. Если X - (л. в.), то (X) - тоже (л. в.).

5. Если X и F - оба (л. в.), то также <л. в.) будут (X AND У), (X OR У) и NOT(X).

6. Ни один объект не является (л. в.), если то, что он (л. в.), не следует из конечного числа применений правил 1-5.

Пример правильного логического выражения

((NOT А) AND В) OR (С AND (D OR Е))

Соответствующее дерево приведено на рис. 5.3.4.

Вы могли бы обратить внимание на то, что определения (а. в.) и (л. в.) содержат, видимо, лишние скобки. Можно дать определения, не требующие такого количества скобок, но такие определения неизменно приводят к двусмысленностям. Например, выражения

АЛ-В1С или NOT А AND В

Строка

яв/1яется<а.в.>- согласно правилу, использованием - строк

3 (А-В)

Б ({A-B)*d.

8 lE**F) 3 d

10 (D/(E**FO)

j:

11 «(A-B)*C) + CD/(E"F)«

5Ь 1,2 1

So 3,4 1

5е 1

5d Ба

9,8 5,10

Рис. 5.3.1. Построение арифметического выражения.

Рис. 5.3.2. Двоичное дерево для описания арифметического выражения

(((-e)*c)+(Z)/(£**f))).

©

17.0

4.0 1.0 гд е.о

а 6 в г

Рис. 5.3.3. Вычисление значения арифметического выражения.