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

На самом деле синтаксический анализ выражений — весьма простая процедура. Во многих отношениях она гораздо проще других задач, возникающих перед программистами. Ее простота является следствием строгих правил алгебры. В этой главе мы рассмотрим программу рекурсивного нисходящего анализа (recursive-descent parser) и все вспомогательные процедуры, позволяющие вычислять арифметические выражения. Мы разработаем три версии программы синтаксического анализа выражений. Первые две версии являются обычными, а третья — обобщенной. Ее можно применять к любым числовым типам. Однако перед тем как приступить к разработке синтаксического анализатора, необходимо сделать краткий обзор выражений и правил их грамматического разбора.

□

Выражения

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

• Числа

• Операции +, -, /, *, ^А, % и =

• Скобки

• Переменные

В нашем синтаксическом анализаторе символ ^А будет означать возведение в степень (а не логическую операцию исключающего “ИЛИ”, как обычно). Символ = обозначает оператор присваивания. Перечисленные выше компоненты объединяются в выражения в соответствии с правилами алгебры. Приведем некоторые примеры.

10-8

(100—5)*14/6

а+Ь-с

10*5

а=10-Ь

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

+ - (унврные)

высший

* / %

+ -

НИЗШИЙ

Операторы, имеющие одинаковый приоритет, вычисляются слева направо.

В примерах, рассмотренных по ходу изложения, все переменные обозначаются одной буквой (иначе говоря, допускается использование лишь 26 переменных* соответствующих буквам от а до z). Строчные и прописные буквы не различаются (буквы а и а считаются одинаковыми). В первой версии анализатора все числовые переменные приводятся к типу double, хотя читатели легко смогут модифицировать эту программу, настроив ее на обработку любого другого числового типа. Кроме того, для упрощения логики программы в нес включены минимальиые средства проверки ошибок.

Ш Синтаксический анализ выражений: постановка задачи

На первый взгляд, синтаксический анализ выражений кажется довольно простой задачей. Однако, чтобы лучше понять ее, попробуйте-ка вычислить выражение

| 10-2*3

Как известно, результат этого выражения равен 4. Несмотря на то что создать программу, вычисляющую это арифметическое выражение, довольно легко, возникает вопрос, как создать программу, вычисляющую правильный результат произвольного выражения. В качестве первого варианта можно написать следующую программу.

а = первый операнд whi!e(ecTb операнды) ор = оператор b = второй операнд а = a op b