4. Стековый калькулятор и языки

4. Стековый калькулятор и языки

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

Итак, введем определение стека. Стеком называется любая структура, в которой могут накапливаться какие-то элементы и для которой выполнено следующее основное условие: элементы из стека можно доставать только в порядке, обратном порядку добавления их в стек. Это условие часто называют принципом «последним пришел – первым ушел» или LIFO (Last In – First Out).

Элемент стека, который в данный момент можно взять или посмотреть называется вершиной стека, максимальное число элементов в стеке – глубина стека. Стек, в котором нет ни одного элемента называется пустым.

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

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

Рассмотрим пример для стекового калькулятора. Пусть требуется получить значение формулы 5 - (7+8) +25. Тогда последовательность для стекового калькулятора будет такой: 5,7,8, +, •, 25, +.

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

4.1 Рекурсивная реализация компилятора правильных формул.

Будем для определенности считать, что язык правильных формул задается грамматикой:

формула?терм | терм+формула | терм-формула

терм?множитель | множитель • терм | множитель / терм

множитель?(формула) | переменная

переменная?a…z и рассмотрим реализацию компилятора в соответствии с этой грамматикой.

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

В используемой нами грамматике понятие терм определяется через понятия терм и формула. Естественно поэтому попытаться реализовать обработку формулы рекурсивно. (Напомним, что рекурсия – это ситуация или программистский прием, состоящий в том, что программа непосредственно или через другие программы обращается к себе как к подпрограмме.)

В соответствии с определением формулы при ее компиляции можно сначала найти и откомпилировать терм: либо этот терм совпадает со всей формулой, либо за ним должен следовать знак + или —. Таким образом, после компиляции терма возможны три ситуации:

• в формуле больше символов нет;

• далее идет знак +, а за ним формула;

• далее идет знак —, а за ним формула.

Соответственно в целом обработку формулы можно записать так: обрабатывается терм, затем проводится выбор: если нет непрочитанных элементов, то ничего не делать; если идет знак + или —, то пропустить его, обработать формулу и напечатать соответственно + или —.

Обратите внимание, что в методе «обработать формулу» мы обрабатываем непрочитанную часть формулы не до ее конца, а лишь до конца правильной формулы. Это связанно с тем, что далее при обработке множителя в соответствии с правилом:

множитель?(формула) переменная мы будем вызывать метод «обработать формулу» для компиляции выражения внутри скобок, а такая обработка должна заканчиваться при достижении закрывающейся скобки.

Наконец, коль скоро мы воспользовались рекурсией, мы обязаны гарантировать, что метод «обработать формулу» не будет вызывать себя бесконечно. В данном случае это действительно так, потому что перед каждым новым вызовом метода «обработать формулу» непрочитанная часть формулы уменьшается, а т.к. она конечна, то и вызовов может быть лишь конечное число. Следовательно, рано или поздно обработка формулы закончится.

Рекурсивный компилятор формул (RecursCompf.rb)

class RecursComp def compile(str)

     @str,@index = str,0

     compileF

end

private

def compileF

compileT

     return if @index >= @str.length

     cur = @str[@index].chr

     if cur == ’+’ or cur ==

          @index += 1

          compileF

          print "#{cur} "

     end

end

def compileT

     compileM

     return if @index >= @str.length

     cur = @str[@index].chr if cur == ’*’ or cur == ’/’

     @index += 1

     compileT

     print "#{cur} "

     end

end

     def compileM

if @str[@index].chr == ’(’ @index += 1

     compileF

     @index += 1

else

     compileV

     end

end

def compileV

     print "#{@str[@index].chr} "

     @index += 1

     end

end

Аналогичным способом в соответствии с грамматикой реализуются методы «обработать терм», «обработать множитель». А метод «обработать переменную» заключается лишь в выводе на экран переменной и пропуске очередного элемента.

Однако, если попытаться откомпилировать нашим компилятором формулу а – b — с, то мы увидим, что последовательность символов для стекового калькулятора соответствует формуле а – (b — с), т.е. в этой ситуации компилятор работает неверно (традиционная операция вычитания ассоциативна слева, а у нас скобки «накапливаются» справа)[12].

Обработка ввода формул (RecursComp.rb)

require "RecursCompf"

c = RecursComp.new

while true

     print " Введите формулу –> "

     c.compile(readline.chomp)

end

4.2 Реализация компилятора с помощью стека.

Грамматику, описанную в предыдущем разделе, легко преобразовать к виду, соответствующему правильному порядку выполнения арифметических действий:

формула?терм | формула + терм | формула—терм

терм?множитель | термомножитель | терм/множитель

множитель?(формула) | переменная

переменная? а | b | с |...|z

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

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

Введем новые понятия: аддитивная операция = +, —; мультипликативная операция =-,/; и зададим понятия терма и формулы в новой форме:

формула?терм{ терм }

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

Метод «обработать формулу», например, будет заключаться в следующем: сначала обрабатывается терм, затем начинается цикл, внутри которого происходит выбор: непрочитанных элементов нет ? выход из цикла;

очередной элемент + ? пропустить очередной элемент, обработать терм,

напечатать “+”; очередной элемент – ? пропустить очередной элемент, обработать терм, напечатать “—”; иначе ? выход из цикла.

Аналогичным образом модифицируется метод «обработать терм». При компиляции по новой программе формула a – b – c будет обработана правильно.

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

Прежде всего заметим, что любую правильную формулу можно скомпилировать так, что: 1) переменные в последовательности для стекового калькулятора будут идти в том же порядке, что и переменные в формуле; 2) все операции в последовательности будут расположены позже соответствующих знаков операций в формуле. (Этот факт легко доказывается индукцией по числу знаков операций в формуле.)

Таким образом, формулу можно компилировать так: встретив имя переменной, немедленно его напечатать, а встретив знак операции или скобку, печатать те из предыдущих, но еще невыполненных операций (будем их называть отложенными), которые выполнимы в данный момент, после чего «откладывать» и новый знак. Поскольку среди оставшихся отложенных операций нет таких, которые выполнимы до пришедшего знака, то для хранения можно воспользоваться стеком (назовем его стеком операций). Этот стек и есть та информация, которая необходима для индуктивной компиляции формулы.

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

class Stack

     def initialize

           @array = Array.new

     end

     def push(c)

           @array.push(c)

     end

     def pop

           @array.pop

     end

     def top

           @array.last

     end

end

Класс Compf

Давайте теперь разберем класс Compf – компилятор формул, использующий стек операций. Класс Compf является подклассом класса Stack и имеет методы всех трёх типов доступа: public, protected и private. Компилятор допускает только однобуквенные имена переменных.

require ’Stack’ class Compf < Stack def compile(str)

     "(#{str})".each_byte { |c| processSymbol(c.chr) }

end

     private def symType(c) case c

when ’(’

     SYM_LEFT when ’)’

     SYM_RIGHT when ’+’, ’-’, ’*’, ’/’

     SYM_OPER

     else

           symOther(c)

     end

end

def processSymbol(c)

case symType(c)

when SYM_LEFT

     push(c)

when SYM_RIGHT

     processSuspendedSymbol(c)

     pop

when SYM_OPER

     processSuspendedSymbol(c)

     push(c)

when SYM_OTHER

     nextOther(c)

     end

end

def processSuspendedSymbol(c)

while precedes(top, c)

     nextOper(pop)

     end

end

Работа начинается с вызова метода compile, в котором все символы строки str последовательно передаются методу processSymbol.

def priority(c)

     (c == ’+’ or c == ’-’) ? 1 : 2 end

def precedes(a, b)

     return false if symType(a) == SYM_LEFT

return true

if symType(b) == SYM_RIGHT

     priority(a) >= priority(b) end

     protected

     SYM_LEFT = 0; SYM_RIGHT = 1; SYM_OPER = 2; SYM_OTHER = 3

def symOther(c)

# Сравнение символа с образцом (регулярным выражением).

raise "Недопустимый символ #{c}" if c !~ /[a-z]/

     SYM_OTHER

end

def nextOper(c)

     print "#{c} "

end

def nextOther(c)

     nextOper(c)

     end

end

Квалификатор доступа protected и метод nextOther нужны для создания на базе класса Compf нового класса Calc, реализующего калькулятор формул[13].

Класс Calc (калькулятор числовых формул) выведен из класса Compf, переопределяет некоторые методы последнего, и имеет дополнительный стек для размещения в нём чисел. Калькулятор работает только с цифрами (числами от 0 до 9).

Несколько комментариев к методу nextOper(c) класса Calc. Множественное присваивание в первой строке метода корректно, т.к. в языке Ruby при выполнении множественного (параллельного) присваивания сначала последовательно вычисляются все выражения в правой части оператора присваивания.

require ’Compf’

class Calc < Compf def initialize

# Вызов метода initialize базового класса Compf. super

# Создание стека результатов операций.

@s = Stack.new

end

def compile(str) super

return @s.top end

protected

def symOther(c)

raise "Недопустимый символ #{c}" if c !~ /[0-9]/ SYM_OTHER end

def nextOper(c)

second, first = @s.pop, @s.pop @s.push(first.method(c).call(second)) end

def nextOther(c)

@s.push(c.to_i)

end

end

Конструкция first.method(c).call(second) во второй строке метода может быть объяснена таким примером: выражение 3.metod(’-’).call(2), эквивалентно выражению 3. – (2) или просто 3-2.

Задача 1. Добавьте операции sin, cos и унарный минус.

Задача 2. Добавьте правоассоциативную операцию ~ возведения в степень.

Задача 3. Добавьте квадратные и фигурные скобки.

Задача 4. Измените программу так, чтобы допускались в качестве имен переменных произвольные идентификаторы языка Ruby.

Задача 5. Добавьте левоассоциативную операцию % с приоритетом, равным приоритету операции /.

Задача 6. Добавьте возможность записи формулы с пробелами и комментариями двух типов (/* */ и //).

Задача 7. Измените программу так, чтобы ввод, содержащий в качестве аргументов только восьмеричные числа (начинающиеся с нуля, например 056), компилировался в программу, содержащую десятичные числа.

Задача 8. Измените программу так, чтобы ввод, содержащий в качестве аргументов только шестнадцатеричные числа (начинающиеся с 0x, например 0x56), компилировался в программу, содержащую восьмеричные числа.

Задача 9. Измените программу так, чтобы ввод, содержащий в качестве аргументов только римские числа, не превосходящие 5000, компилировался в программу, содержащую десятичные числа.

Задача 10. Измените программу так, чтобы для коммутативной операции аргументы выдавались в алфавитном порядке.

Задача 11. Добавьте фигурные скобки, означающие возведение в квадрат. Используйте операцию DUP стекового калькулятора.

Задача 12. Считая, что a = 0, оптимизируйте формулу (уберите лишние сложения).

Задача 13. Считая, что b = 1, оптимизируйте формулу (уберите лишние умножения).

Задача 14. Добавьте возможность ввода формулы на нескольких строках.