КАЛЬКУЛЯТОР, ПОЛИЗ И ГРАММАТИКА

Часто в жизни, когда возникает необходимость что-то подсчитать, мы пользуемся калькуляторами. Задумывались ли Вы когда-нибудь, как действует калькулятор, по какому алгоритму проводятся вычисления? В любом случае, попытаемся построить свой программный калькулятор. Начнем это на первый взгляд непростое дело с решения такой задачи.
Польский калькулятор. Вместо обычной скобочной записи арифметических выражений польский математик Ян Лукасевич предложил использовать бесскобочную (обратную польскую или ПОЛИЗ), в которой операнды записываются в том же порядке, что и в исходном выражении, а каждый знак операции следует непосредственно за операндами, над которыми эта операция проводится. Вычисление выражения производится слева направо с учетом приоритета операций. Например, выражение ‘(2+5*2)/3-1′ преобразуется в ‘2 5 2 * + 3 / 1 -‘. Сначала выполняется операция ‘*’ над предшествующими двумя операндами 5 и 2, результат 10 помещается на место чисел 5 и 2. Затем выполняется операция ‘+’ над предшествующими двумя операндами 2 и 10, результат 12 помещается на место 2 и 10, и так далее, до тех пор, пока не будет выполнена последняя операция над последней парой операндов(операция ‘-‘ над числами 4 и 1). Приведем еще примеры выражений в обычной записи и в ПОЛИЗ:
обычная запись 3*11-1 ((2+2)-555)*(9/99)
ПОЛИЗ 3 11 * 1 — 2 2 + 555 — 9 99 / *
Сформулируем следующую задачу. Вводится арифметическое выражение в обратной польской записи. Разделителем операндов во введенном выражении служат пробелы. Разработать алгоритм, вычисляющий значение такого бесскобочного выражения. Операнды — целые положительные числа. Допустимыми операциями являются ‘+’, ‘-‘, ‘*’, ‘/’. Исходное выражение вводится в виде строки.
Для решения этой задачи нам понадобится структура данных, известная как «Стек». Напомним, что это такое. Стеком будем называть последовательность элементов, упорядоченных по времени их поступления. Эта последовательность доступна только с одного конца (вершины стека). Для работы со стеком необходим указатель вершины стека. Основные операции над стеком следующие: «запомнить в стеке» и «извлечь из стека» (причем извлекается последний из занесенных в стек элементов — то есть элемент с вершины стека). Поэтому говорят, что стек — это структура типа LIFO — «Last In — First Out» — «последним зашел — первым вышел». Для представления стека в программе обычно используется одномерный массив (назовем его Stack), нумерация элементов которого начинается с нуля. В этом нулевом элементе массива хранится индекс первого свободного места в массиве (т.е. увеличенный на 1 индекс вершины стека). Если массив пуст, то указатель равен 1 (Stack[0]=1). Добавление элемента X в стек реализуется очень просто — на первое свободное место (индекс которого хранится в Stack[0]) помещается X, после чего индекс первого свободного места увеличивается на 1. Если необходимо извлечь элемент x из стека, то берется последний из занесенных элементов (естественно, только в том случае, если стек непуст), и указатель на первое свободное место уменьшается на 1.
Занести в стек Извлечь из стека
Stack[Stack[0]]:=x; if Stack[0]<>1 { Если стек не пуст }
Stack[0]:=Stack[0]+1; then begin x:=Stack[Stack[0]-1];
Stack[0]:=Stack[0]-1;
end;
Перед вычислением выражения стек пуст. Будем просматривать входную строку слева направо и выполнять следующие действия: если очередной элемент строки — операнд (число), то поместим его в стек; если очередной элемент строки — операция, то она относится к предыдущим двум операндам, которые уже находятся в стеке (в позициях Stack[Stack[0]-1] и Stack[Stack[0]-2] — т.е. в вершине стека). Извлекаем эти операнды из стека, выполняем над ними требуемую операцию, и результат снова заносим в стек. Когда входная строка закончится (обычно говорится «будет полностью разобрана»), то искомое значение выражения будет находиться в Stack[1].
Рассмотрим теперь алгоритм перевода выражения в ПОЛИЗ.
Пусть вводится скобочное арифметическое выражение. В выражении могут встречаться открывающая и закрывающая круглые скобки ‘(‘ и ‘)’, знаки операций и цифры от 0 до 9.
Найдем значение этого скобочного выражения.
Припишем числовой приоритет каждой арифметической операции, открывающей скобке, а также ситуации, когда стек пуст, следующим образом: символу ‘(‘ припишем приоритет 0, ‘+’ и ‘-‘ ѕ 1; ‘*’ и ‘/’ ѕ 2; пустому стеку ѕ 0.
Алгоритм перевода выражения в ПОЛИЗ.
Шаг 1. Если входная строка пустая, то перейти к шагу 6; иначе прочитать следующий элемент (скобку, операцию или операнд) и обозначить его через x.
Шаг 2. Если x — операнд, то перенести его в выходную строку, поместить вслед за ним разделитель и вернуться к шагу 1.
Шаг 3. Если x — открывающая скобка, то поместить ее в стек и вернуться к шагу 1. Если x — закрывающая скобка, то перейти к шагу 4; во всех остальных случаях перейти к шагу 5.
Шаг 4. Если элемент, находящийся на вершине стека, не является открывающей скобкой, то перенести его из стека в выходную строку, поместить за ним разделитель, а затем повторить шаг 4. Если на вершине стека находится открывающая скобка, удалить ее из стека и вернуться к шагу 1.
Шаг 5. Если приоритет элемента на вершине стека не меньше приоритета x, то перенести этот элемент из стека в выходную строку, поместить за ним разделитель, а затем повторить шаг 5. Иначе поместить x на вершину стека и вернуться к шагу 1.
Шаг 6. Освободить стек, удаляя каждый раз по одному элементу и помещая его в выходную строку с последующим разделителем. Закончить работу.
Проверьте, что этот алгоритм переводит выражение ‘(2+5*2)/3-1′ в ‘2 5 2 * + 3 / 1 -‘. Если в ходе построения обратной польской записи не переносить знак операции в выходную строку (где он стоял бы непосредственно за теми операндами, над которыми должна выполняться эта операция), а взять из выходной строки два последних операнда, выполнить над ними операцию, и результат поместить снова в выходную строку, то у нас после шага 6 в выходной строке окажется искомый результат.
Давайте рассмотрим еще один способ вычисления арифметического выражения. В отличие от вышеописанного, новый способ, во-первых, не требует таблицы приоритетов, во-вторых, позволяет легко обнаруживать ошибки во входной строке, в-третьих, дает универсальный способ анализа и вычисления не только любого выражения (как арифметического, так и логического), но и произвольного оператора языка программирования.
В основе рассматриваемого метода лежит способ описания языков программирования с помощью специальных правил, похожих на правила описания любого языка (в том числе и естественного). Для описания структуры любого языка можно использовать:
основные элементы языка (т.е. набор слов, который обычно называют алфавит);
вспомогательные элементы (т.е. условные элементы, являющиеся обобщенными названиями каких-либо конструкций языка, например, подлежащее, сказуемое, глагол и т.п.);
правила, устанавливающие связь между основными и вспомогательными элементами.
Чтобы отличать основные элементы от вспомогательных, договоримся, что вспомогательные элементы заключаются в угловые скобки ‘<' и '>‘. Знак ‘::=’ означает, что элемент слева от него заменяется на цепочку элементов справа (заметим, что слева может находиться только вспомогательный элемент, а справа любая, возможно пустая, цепочка из основных и вспомогательных элементов). Начальным элементом при анализе всегда является вспомогательный.
Для каждого вспомогательного элемента найдем правило с совпадающей левой частью и заменим этот элемент на правую часть найденного правила. Договоримся, что замену вспомогательных элементов будем осуществлять слева направо, и всегда применять правила к самому левому вспомогательному элементу. Процесс будет продолжаться до тех пор, пока не будет получена цепочка, состоящая только из основных элементов. Этот процесс иначе называется выводом. Вывод считается построенным правильно после того, как все вспомогательные элементы будут заменены на основные элементы. Такие обозначения были использованы впервые для описания языка программирования ALGOL-60 и получили название Нормальная Форма Бэкуса (НФБ).
Попробуем с помощью НФБ составить правила для упрощенного арифметического выражения. Предположим, что наше арифметическое выражение состоит из следующих основных элементов: арифметических операций (например, ‘+’ и ‘*’); операндов-переменных (например, единичных букв латинского алфавита); операндов-констант (например, целых беззнаковых); круглых скобок. Введем знак ‘|’, который означает ‘или’, и построим правила для описания операндов арифметического выражения. Символ ( будет означать пустую цепочку, то есть конец правила.
1. <Переменная> ::= а | b | c | … | z
2. <Цифра> ::= 0 | 1 | 2 |…| 9
3. <Беззнаковая целая константа ѕ БЦК> ::= <Цифра> < Продолжение беззнаковой целой константы ѕ ПБЦК>
4.<ПБЦК> ::= <Цифра> <ПБЦК> | (
Договоримся, что если мы применяем правило <Цифра> ::= 0, то будем говорить, что используется правило 2а, если <Цифра> ::= 1, то используется правило 2б и т.п. Здесь, по смыслу, ( означает, что если следующий символ в цепочке не цифра, то выполняется правило 4б.
Построим дерево (иначе оно называется деревом вывода), которое покажет, каким образом можно с помощью правил 2, 3 и 4 получить константу ’12’ (рис. 1). Аналогичным образом можно построить константу любой длины. Итак, мы описали операнды арифметического выражения.
Рассмотрим, какие элементы могут перемножаться в арифметическом выражении ѕ это операнды-переменные и операнды-константы, а также любое арифметическое выражение, заключенное в круглые скобки. То есть имеем правила:
5.<Множитель> ::= <Переменная>| <Беззнаковая целая константа>| (<Арифметическое выражение>)
6.<Терм> ::= <Множитель> * <Терм>| <Множитель>
Правило 6 предусматривает два варианта для вспомогательного символа <Терм>: правило 6а используется для порождения сомножителей, а 6б — для остановки порождения. Полученные таким образом <Термы> могут складываться в различных комбинациях, следовательно, можно записать новое правило:
7.<Арифметическое выражение> ::= <Терм> + <Арифметическое выражение>| <Терм>
Заметим, что начальным элементом является вспомогательный символ <Арифметическое выражение> (иначе этот начальный элемент называют аксиомой), и таким образом определяется формальная грамматика для описания синтаксической конструкции <Арифметическое выражение>. Используя эти правила, мы можем написать программу анализа конкретного арифметического выражения на правильность записи (иначе, на синтаксическую правильность). При этом главная процедура будет осуществлять ввод конкретного арифметического выражения в виде, например, строки символов S, и вызывать процедуру <Арифметическое выражение> (всего, кроме главной процедуры, мы будем использовать столько процедур, сколько в наших правилах вспомогательных элементов, т.е. процедуры: <Арифметическое выражение>, <Терм>, <Множитель>, <Переменная>, <Беззнаковая целая константа>, <Продолжение беззнаковой целой константы>, <Цифра>).
Пример. Рассмотрим схему реализации двух из вышеперечисленных процедур, а именно, <Продолжение беззнаковой целой константы> и <Цифра>, остальные процедуры записываются по той же схеме (здесь i — номер анализируемого символа во входной строке с выражением):
процедура <Продолжение беззнаковой целой константы>;
Вызвать процедуру <Цифра>;
Если признак=’цифра’,
вызвать процедуру <Продолжение беззнаковой целой константы>;
конец процедуры <Продолжение беззнаковой целой константы>;

процедура <Цифра>;
Если i-ый символ входной строки — не цифра,
то сформировать признак ‘не цифра’,
иначе i:=i+1;
сформировать признак ‘цифра’,
конец процедуры <Цифра>;
Как уже упоминалось ранее, правила 1-7, описывают только синтаксис выражения. Например, с помощью таких правил нельзя определить, принадлежит ли данная константа заданному числовому диапазону, вычислить значение выражения и т.п. Для реализации этого можно дополнить наши правила так называемыми действиями (иначе называемыми семантическими процедурами), которые будут выполняться параллельно с анализом арифметического выражения. Договоримся, что действия будут выполняться над последним проанализированным основным элементом; если рядом с этим элементом не стоит действие, то ничего не выполняется.
Сформулируем действия, с помощью которых можно перевести арифметическое выражение из входной строки в ПОЛИЗ.
Действие Д1: переслать элемент (то есть операнд-переменную или операнд-константу), стоящую перед данным действием в выходную строку.
Действие Д2: переслать знак операции сложения, стоящий перед данным действием, в выходную строку.
Действие Д3: переслать знак операции умножения, стоящий перед данным действием, в выходную строку.
Тогда правила 5, 6 и 7, дополненные действиями, примут вид:
5′.<Множитель> ::= <Переменная> {Д1}| <Беззнаковая целая константа> {Д1}| (<Арифметическое выражение>)
6′.<Терм> ::= <Множитель> * <Терм> {Д3}| <Множитель>
7′.<Арифметическое выражение> ::= <Терм> + <Арифметическое выражение> {Д2}| <Терм>
При разработке программы синтаксического анализа необходимо вставить в текст программы:
в процедуру <Множитель> после вызова процедуры <Переменная> вызов процедуры, выполняющей действие {Д1};
в процедуру <Терм> после вызова процедуры <Терм> вызов процедуры, выполняющей действие {Д3};
в процедуру <Арифметическое выражение> после вызова процедуры <Арифметическое выражение> вызов процедуры, выполняющей действие {Д2}.
При выполнении синтаксического анализа строки (a+b*c( будет построен вывод (a {Д1} + b {Д1} * c {Д1} {Д3Ht} {Д2 }(.
Это означает следующее:
так как в выводе справа от переменной (а( стоит действие, то проанализировав перемнную (а(, анализатор начинает выполнять {Д1}, то есть пересылает эту переменную в выходную строку;
так как в выводе справа от знака операции (+( не стоит действие, то проанализировав символ (+(, анализатор переходит к анализу следующего символа и не выполняет никаких дейчтвий;
так как в выводе справа от переменной (b( стоит действие, то проанализировав перемнную (b(, анализатор начинает выполнять {Д1}, то есть пересылает эту переменную в выходную строку;
так как в выводе справа от знака операции (*( не стоит действие, то проанализировав символ (*(, анализатор переходит к анализу следующего символа и не выполняет никаких дейчтвий;
так как в выводе справа от переменной (с( стоит действие, то проанализировав перемнную (с(, анализатор начинает выполнять {Д1}, то есть пересылает эту переменную в выходную строку;
так как следом за действием {Д1} в строке вывода указано действие {Д3}, то выполняется процедура, посылающая в выходную строку символ (*(;
так как следом за действием {Д3} в строке вывода указано действие {Д2}, то выполняется процедура, посылающая в выходную строку символ (+(.
Результатом выполнения анализатора являются синтаксические ошибки, если они обнаружены, а если арифметическое выражение записано синтаксически правильно, то в выходной строке сформируется его представление в ПОЛИЗ, то есть (a b c * +(.
Рассмотрим, какие действия можно применить для вычисления данного арифметического выражения ‘а+123*с’.
Во-первых, мы должны включить в действие {Д1} правила для выделения и определения значений операндов-переменных, операндов-констант, то есть:
Действие Д1: Взять значение элемента (переменной, константы), стоящей слева от действия, и поместить его в вершину стека.
Во-вторых, мы должны включить в действия {Д2}, {Д2} правила выполнения операции непосредственного сложения или, соответственно, умножения над двумя последними значениями (операндами), хранящимися в стеке, то есть:
Действия Д2 и Д3 :
Прочитать из стека значения двух последних записанных туда элементов (переменной, константы). Чтение, как Вы помните, идет из вершины стека, причем прочитанное значение из стека выталкивается.
Выполнить операцию, соответственно, сложения или умножения над ними.
Проверить, принадлежит ли полученное значение заданному числовому диапазону и, если нет, то сформировать об этом соответствующее сообщение.
Результат выполнения операции занести в вершину стека.
Тогда после работы анализатора в вершине стека будет находиться только одно значение – результат выполнения проанализированного арифметического выражения.
Упражнение 1. Как будет выглядеть таблица приоритетов и как изменится алгоритм, если разрешить операции ‘-‘ и ‘^’ — унарный минус (знак, обозначающий отрицательность числа) и возведение в степень соответственно?
Упражнение 2. Дано арифметическое выражение, состоящее из букв, цифр, знаков арифметических операций и скобок, записанное в общепринятой форме. Составить программу, удаляющую из выражения лишние пары скобок, не влияющие на порядок выполнения операций, например: ‘((6/2)*А+(8-5))/(E)’ должно быть преобразовано в ‘(6/2*A+8-5)/E’.
Упражнение 3. Переведите в ПОЛИЗ и постройте самостоятельно дерево вывода для арифметического выражения ‘(32+127)*14-2′.
Упражнение 4. По заданным нами правилам 1—7 напишите программу, реализующую анализ арифметического выражения на синтаксическую правильность, проверку данных на корректность (то есть принадлежат ли данные некоторому числовому диапазону), и вычисление результата данного арифметического выражения.
Упражнение 5. Расширить описание элемента <Арифметическое выражение>, добавив операции ‘-‘, ‘/’,’^’ и разрешив вычисления над числами со знаком и идентификаторами (переменными с именами, длина которых не меньше одного символа). Напишите программу, реализующую вычисление такого расширенного арифметического выражения.
Упражнение 6. Составьте правила для описания любого логического выражения.
Используйте в качестве операций: ‘or’ (или), ‘and’ (и), ‘not’ (не), а также ‘<' (меньше), '>‘ (больше), ‘=’ (равно); в качестве операндов: логические константы (true, false), переменные, арифметические выражения. Результатом вычисления логического выражения должно быть либо ‘истина’ либо ‘ложь’).

И. Волков, Л. Певзнер

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Можно использовать следующие HTML-теги и атрибуты: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>