Программирование на языке Ruby

c = RecursComp.new

while true

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

     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