Будем для определенности считать, что язык правильных формул задается грамматикой:
формула→терм | терм+формула | терм-формула
терм→множитель | множитель • терм | множитель / терм
множитель→(формула) | переменная
переменная→a\b\…\z и рассмотрим реализацию компилятора в соответствии с этой грамматикой.
Правильная формула задается грамматикой с четырьмя метасимволами. Для каждого метасимвола пишется отдельный метод обработки. Например, метод «обработать терм» находит в начале непрочитанной части формулы терм максимальной длины, читает и печатает соответствующий фрагмент последовательности для стекового калькулятора.
В используемой нами грамматике понятие терм определяется через понятия терм и формула. Естественно поэтому попытаться реализовать обработку формулы рекурсивно. (Напомним, что рекурсия – это ситуация или программистский прием, состоящий в том, что программа непосредственно или через другие программы обращается к себе как к подпрограмме.)
В соответствии с определением формулы при ее компиляции можно сначала найти и откомпилировать терм: либо этот терм совпадает со всей формулой, либо за ним должен следовать знак + или —. Таким образом, после компиляции терма возможны три ситуации:
• в формуле больше символов нет;
• далее идет знак +, а за ним формула;
• далее идет знак —, а за ним формула.
Соответственно в целом обработку формулы можно записать так: обрабатывается терм, затем проводится выбор: если нет непрочитанных элементов, то ничего не делать; если идет знак + или —, то пропустить его, обработать формулу и напечатать соответственно + или —.
Обратите внимание, что в методе «обработать формулу» мы обрабатываем непрочитанную часть формулы не до ее конца, а лишь до конца правильной формулы. Это связанно с тем, что далее при обработке множителя в соответствии с правилом:
множитель→(формула) \ переменная мы будем вызывать метод «обработать формулу» для компиляции выражения внутри скобок, а такая обработка должна заканчиваться при достижении закрывающейся скобки.
Наконец, коль скоро мы воспользовались рекурсией, мы обязаны гарантировать, что метод «обработать формулу» не будет вызывать себя бесконечно. В данном случае это действительно так, потому что перед каждым новым вызовом метода «обработать формулу» непрочитанная часть формулы уменьшается, а т.к. она конечна, то и вызовов может быть лишь конечное число. Следовательно, рано или поздно обработка формулы закончится.
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].
require "RecursCompf"
[12]
На самом деле ошибка возникла не из-за работы компилятора, а из-за некорректно написанной грамматики, в чем легко убедиться, рассмотрев дерево вывода формул для данной грамматики.