Проект Компилятор формул

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

Первым вариантом компилятора — средства для автоматического перевода программ, является рекурсивный компилятор формул — достаточно простой, но обладающий рядом недостатков.

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

Дополнительная информация о различных подходах к реализации компиляторов может быть найдена в книге [9].

Стековый калькулятор

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

Интерфейс стекового калькулятора

interface StackCalc {
    // Добавить число в стек.
    void    push(int val);
    // Сложить.
    int     add() throws Exception;
    // Вычесть.
    int     sub() throws Exception;
    // Умножить.
    int     mul() throws Exception;
    // Разделить.
    int     div() throws Exception;
    // Показать вершину стека.
    int     top() throws Exception;
}

Методы push и top хорошо известны и комментариев не требуют, а семантика остальных четырех такова: из стека извлекаются (с помощью метода pop ) два верхних числа, над ними выполняется указанная в названии метода арифметическая операция, а результат кладется обратно в стек (с помощью метода push ). При этом в качестве первого аргумента арифметической операции берется тот из двух извлеченных элементов, который был положен в стек раньше другого. Если в момент вызова одного из этих четырех методов глубина стека меньше двух, возникает исключительная ситуация. При реализации данного интерфейса на базе ограниченного вектора выполнение метода push также может привести к исключительной ситуации, связанной с переполнением стека.

Стековый калькулятор можно использовать для вычисления значений различных арифметических выражений типа $$5(7+8)+25$$. Нужно только написать предварительно программу для вычисления значения.

С целью сокращения длины подобной программы будем записывать последовательность вызываемых методов в строку, разделяя их просто пробелом. Названия методов арифметических операций заменим на соответствующие им знаки действий ( +, -, * и / ), вместо вызова метода push с аргументом val будем записывать только его аргумент, а завершающий любую программу вызов метода top вообще включать в такую сокращенную запись программы не будем.

(рис 12.1) Выполнение программы 5 7 8 + * 25 +

С использованием этих сокращений программа для вычисления выражения $$5(7+8)+25$$ примет вид 5 7 8 + * 25 +. Рисунок 12.1 показывает последовательность состояний стека стекового калькулятора при выполнении этой программы.

В рассмотренном примере программа для стекового калькулятора была написана по исходной формуле $$5(7+8)+25$$ нами. Основной задачей этого параграфа является реализация компилятора — программы, которая сможет осуществлять преобразование формулы в программу для калькулятора автоматически.

С формальной точки зрения компилятор представляет собой программную реализацию некоторой функции $$\tau$$, действующей из множества цепочек одного языка $$L_1$$ (в рассматриваемом случае это язык арифметических формул) в множество цепочек другого $$L_2$$ (язык программ стекового калькулятора) таким образом, что $$\forall \omega \in L_1$$ семантика цепочек $$\omega$$ и $$\tau(\omega) \in L_2$$ совпадает. Говоря другими словами, компилятор (часто называемый также транслятором ) реализует перевод с одного языка на другой с сохранением смысла.

Напомним некоторые важнейшие определения, связанные с языками и грамматиками, которые были рассмотрены в лекции 3.

Пусть $$\Sigma$$ — некоторый алфавит, $$N$$ — метаалфавит, т.е. какой-то другой алфавит, не пересекающийся с $$\Sigma$$ ( $$\Sigma \cap N = \varnothing$$ ). Элементы метаалфавита $$N$$ называются метасимволами. Грамматикой $$G$$ называется набор ( $$\Sigma, N, P, S$$ ), где $$\Sigma$$ — множество символов, $$N$$ — множество метасимволов, $$P$$ — множество правил вывода вида: $$\alpha\rightarrow\beta$$, где $$\alpha\in N$$ — какой-то метасимвол, $$\beta \in (\Sigma \cup N)^*$$ — произвольная цепочка над объединением двух алфавитов, и для каждого $$\alpha\in N$$ встречается хотя бы одно правило с $$\alpha$$ в левой части (до стрелочки), а $$S \in N$$ — так называемый стартовый метасимвол.

Содержательно каждое правило грамматики имеет смысл подстановки. Например, строка $$\alpha\rightarrow\alpha\gamma\alpha$$ означает возможность замены метасимвола $$\alpha$$ на цепочку $$\alpha\gamma\alpha$$. Начав со стартового символа и пользуясь различными правилами грамматики, мы можем получать различные цепочки из символов, которые называются выводимыми цепочками.

Заметим, что если в цепочке встречается метасимвол, то ее можно преобразовать дальше, применив одно из правил грамматики с этим метасимволом в левой части. Если же метасимволов в цепочке не осталось, то процесс ее преобразования закончен и больше с цепочкой ничего сделать нельзя. По этой причине обычные символы (из алфавита $$\Sigma$$ ) часто называют терминалами, а метасимволы (из $$N$$ ) — нетерминалами.

Языком $$L(G)$$, порожденным грамматикой $$G$$, называется множество всех терминальных выводимых цепочек.

Для задания грамматики часто используют очень наглядную форму представления, называемую нормальной формой Бэкуса-Наура (НФБН). Набор правил $$P$$ задают при этом в виде совокупности правил со стрелочками, перечисляющими все возможные цепочки, на которые может быть заменен каждый из метасимволов грамматики в процессе вывода, а стартовым метасимволом считается тот, который присутствует в левой части самого первого правила.

Возьмем в качестве алфавита $$\Sigma$$ множество, состоящее из четырех знаков арифметических операций ( $$+$$, $$-$$, $$*$$ и $$/$$ ) и 26-и идентификаторов от $$a$$ до $$z$$, которыми будут обозначаться произвольные целые числа: $$\Sigma = \{ +, -, *, /, a, b, \ldots, z \}$$.

Тогда язык $$\Sigma^*$$ будет представлять из себя все возможные программы для стекового калькулятора, включая и неправильные. Например, пустая цепочка $$\varepsilon$$ означает вызов единственного метода pop, что приведет к возникновению исключительной ситуации. Принадлежащая этому языку цепочка 2 + также соответствует некорректной программе, ибо в момент вызова метода add в стеке будет содержаться только один элемент.

Для описания языка правильных программ для стекового калькулятора можно воспользоваться следующей грамматикой $$G_S$$.

$$\begin{tabular}{lrl} \ \ \ \ \ $e$ $\rightarrow$ $e\ e\ -$ \\ $\mid$ $e\ e\ +$ \\ $\mid$ $e\ e\ *$ \\ $\mid$ $e\ e\ /$ \\ $\mid$ $a$ $\mid$ $b$ $\mid$ $\ldots$ $\mid$ $z$ \\ \end{tabular}$$

Именно язык $$L(G_S)$$ мы и будем рассматривать, как язык правильных программ для стекового калькулятора.

Грамматики языка правильных арифметических формул

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

В качестве алфавита $$\Sigma$$ возьмем то же самое множество, что и раньше, состоящее из двух круглых скобок (открывающей и закрывающей), четырех знаков арифметических операций ( $$+$$, $$-$$, $$*$$ и $$/$$ ) и 26-и идентификаторов от $$a$$ до $$z$$, которыми будут обозначаться произвольные целые числа:$$\Sigma = \{ (, ), +, -, *, /, a, b, \ldots, z \}.$$

В качестве метаалфавита рассмотрим множество из трех нетерминалов:$$N=\{\alpha,\beta,\gamma\},$$ где символ $$\alpha$$ будет обозначать формулу, $$\beta$$ — имя переменной, а $$\gamma$$ — арифметическую операцию.

Множество правил $$P$$ грамматики $$G_1 = (\Sigma, N, P, S)$$ зададим так:

$$$\alpha$ $\rightarrow$ $(\alpha)$ $\mid$ $\beta$ $\mid$ $\alpha \ \gamma\ \alpha$$$ $$$\beta$ $\rightarrow$ $a$ $\mid$ $b$ $\mid$ $\ldots$ $\mid$ $z$ \\$$ $$$\gamma$ $\rightarrow$ $+$ $\mid$ $-$ $\mid$ $*$ $\mid$ $/$$$ (рис 12.2) Деревья вывода формулы x+y*z

Стартовым метасимволом этой грамматики является нетерминал $$\alpha$$, а примером вывода в ней может служить следующий вывод формулы $$x+y$$:$$\alpha \rightarrow \alpha\ \gamma\ \alpha \rightarrow x\ \gamma\ \alpha \rightarrow x +\alpha \rightarrow x+y.$$

Для формулы $$x+y*z$$ существует два существенно различных множества эквивалентных между собой цепочек вывода, каждому из которых соответствует свое дерево вывода. Эти деревья изображены на рис. 12.2 и отличаются друг от друга порядком появления в формуле операций $$+$$ и $$*$$. Хотя в результате различных выводов получается одна и та же формула, вычисления по ним дадут различные результаты. В одном случае выражение $$x+y*z$$ трактуется как $$(x+y)*z$$, а в другом — как $$x+(y*z)$$.

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

Множество нетерминалов для этой грамматики будет состоять из четырех метасимволов — $$F$$, $$T$$, $$M$$ и $$V$$, обозначающих соответственно формулу, терм, множитель и имя переменной. Множество правил $$P$$ грамматики $$G_2$$ зададим так:

$$$F$ $\rightarrow$ $T$ $\mid$ $T+F$ $\mid$ $T-F$$$ $$$T$ $\rightarrow$ $M$ $\mid$ $M*T$ $\mid$ $M/T$$$ $$$M$ $\rightarrow$ $(F)$ $\mid$ $V$$$ $$$V$ $\rightarrow$ $a$ $\mid$ $b$ $\mid$ $\ldots$ $\mid$ $z$$$

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

Грамматика $$G_0$$ отличается от только что рассмотренной $$G_2$$ порядком следования нетерминалов в правой части первых двух правил:

$$$F$ $\rightarrow$ $T$ $\mid$ $F+T$ $\mid$ $F-T$$$ $$$T$ $\rightarrow$ $M$ $\mid$ $T*M$ $\mid$ $T/M$$$ $$$M$ $\rightarrow$ $(F)$ $\mid$ $V$$$ $$$V$ $\rightarrow$ $a$ $\mid$ $b$ $\mid$ $\ldots$ $\mid$ $z$$$

Важные свойства именно этой грамматики определяют ее обозначение. Именно грамматика $$G_0$$ языка правильных арифметических формул будет использоваться в целом ряде последующих учебных курсов.

Еще один вариант грамматики (назовем ее $$G_3$$ ) таков:

$$$F$ $\rightarrow$ $T\{+T\}$ $\mid$ $T\{-T\}$$$ $$$T$ $\rightarrow$ $M\{*M\}$ $\mid$ $M\{/M\}$$$ $$$M$ $\rightarrow$ $(F)$ $\mid$ $V$$$ $$$V$ $\rightarrow$ $a$ $\mid$ $b$ $\mid$ $\ldots$ $\mid$ $z$$$

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

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

Рекурсивный компилятор формул

Как уже было отмечено в предыдущей секции, грамматика $$G_1$$ не подходит для использования ее в качестве базовой при реализации компилятора формул из-за отсутствия в ней учета приоритета операций. Поэтому поставим перед собой задачу реализовать компилятор, т.е. программу, осуществляющую автоматический перевод с сохранением семантики, с языка $$L(G_2)$$ на язык $$L(G_S)$$ программ стекового калькулятора.

Задача 12.1. Напишите программу (компилятор формул), которая для любой правильной арифметической формулы (элемента языка $$L(G_2)$$ ), данной ей на вход, выдает семантически эквивалентную ей программу стекового калькулятора (элемент языка $$L(G_S)$$ ).

Сначала даже не ясно, как подступиться к такой задаче. Однако ее разрешимость сомнения вызывать не должна — существуют же компиляторы с огромного множества языков программирования, включая язык Java!

Ключом к решению задачи является использование грамматик, задающих входной и выходной языки. Существует вполне естественное соответствие между грамматиками $$G_2$$ и $$G_S$$: в них обеих имеются ровно по одному правилу, порождающему каждую из четырех арифметических операций и правило, порождающее имя переменной (переменная является одним из способов задания числа).

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

Попробуем реализовать данную общую идею, применив рекурсию. Это определяет имя компилятора, который будет построен — рекурсивный компилятор формул.

Будем трактовать поставленную задачу следующим образом: реализовать класс RecursCompf с методом compile, получающим в качестве аргумента исходную формулу (цепочку языка $$L(G_2)$$ ) в виде массива символов, который компилирует эту формулу и печатает получившийся результат (цепочку языка $$L(G_S)$$. Метод main, предназначенный для тестирования получившейся программы реализуем в отдельном классе RecursCompfTest. Для ввода/вывода информации будем использовать методы класса Xterm, а весь исходный текст программы разместим в одном файле, который будет иметь имя RecursCompfTest.java.

После завершения работы над программой она должна вести себя примерно так:

[roganov@msiu compf]$ java RecursCompfTest
Введите формулу -> a  
a 
Введите формулу -> a-b
a b - 
Введите формулу -> (a-b)*(a+b)
a b - a b + *

Приступим собственно к решению. Создадим отдельный метод для обработки каждого из четырех метасимволов грамматики $$G_2$$. Для компиляции формулы (метасимвола $$F$$ ) будем использовать метод compileF, терма — compileT, множителя — compileM, а имени переменной — метод compileV. Так как любая цепочка входного языка представляет из себя формулу, что соответствует метасимволу $$F$$ грамматики $$G_2$$, то ее компиляция, выполняемая методом compile, должна сводится к вызову метода compileF.

В соответствии с первым правилом грамматики $$G_2$$ формула всегда начинается с терма. Таким образом, первое действие, которое должен выполнить метод compileF, — это вызвать метод compileT. Опять таки в соответствии с грамматикой далее возможны три различных варианта: либо формула на этом заканчивается (сводится просто к терму), либо за знаками сложения или вычитания (два варианта) следует еще одна формула.

Теперь уже в соответствии с грамматикой $$G_S$$ можно сделать вывод о том, как должна происходить работа метода compileF в каждом из этих трех случаях. В первом из них делать ничего не надо, а в двух остальных следует сначала обработать формулу, следующую за знаком операции, а затем напечатать символ, ей соответствующий ( + или - ).

Обратите внимание, что при такой реализации метод compileF не пытается откомпилировать всю полученную методом compile формулу целиком — им обрабатывается только некоторая ее часть, соответствующая одному метасимволу $$F$$ в процессе ее вывода.

Для того чтобы можно было реализовать описанную идею, необходимо конкретизировать форму представления исходной формулы. Так как метод compile получает ее в виде массива символов str, вполне естественно сделать этот массив private -компонентой класса RecursCompf, доступной всем его методам и с помощью еще одной private -компоненты index отслеживать ту часть формулы, которая уже обработана. Обработка завершается, когда достигается конец формулы, длина которой равна str.length.

Этого вполне достаточно для реализации метода compileF:

private void compileF() {
        compileT();
        if (index >= str.length) return;
        if (str[index] == '+'){
            index++;
            compileF();
            Xterm.print("+ ");
            return;
        }
        if (str[index] == '-'){
            index++;
            compileF();
            Xterm.print("- ");
        }
    }

Обработка терма совершенно аналогична обработке формулы — это следует из грамматик $$G_2$$ и $$G_S$$, поэтому метод compileT пишется мгновенно:

private void compileT() {
        compileM();
        if (index >= str.length) return;
        if (str[index] == '*'){
            index++;
            compileT();
            Xterm.print("* ");
            return;
        }
        if (str[index] == '/'){
            index++;
            compileT();
            Xterm.print("/ ");
        }
    }

Множитель $$M$$ в грамматике $$G_2$$ является либо заключенной в скобки формулой, либо именем переменной. В первом случае необходимо пропустить открывающую скобку, затем вызвать метод compileF и пропустить закрывающую скобку, а во втором достаточно просто вызвать метод обработки имени переменной:

private void compileM() {
        if (str[index] == '(') {
            index++;
            compileF();
            index++;
        } else compileV();
    }

Последний из оставшихся методов является самым простым — обработка имени переменной сводится к печати этого имени (и перемещению указателя index ):

private void compileV() {
        Xterm.print("" + str[index++] + " ");
    }

Полный текст построенной программы приведен в последней секции параграфа, а мы сейчас попробуем ответить на стандартный для рекурсивных программ вопрос: почему эта программа заканчивает работу? Потенциально опасными в данном случае являются методы compileF и compileT, которые являются рекурсивными. Перед каждым таким рекурсивным вызовом, однако, обработанная часть исходной формулы увеличивается (возрастает значение переменной index ), что, в силу конечности длины исходной формулы, и гарантирует завершение работы программы в целом.

Сделаем одно небольшое чисто технологическое замечание. Хотя построенная нами реализация и является достаточно простой, программа в целом использует три различных файла ( RecursCompfTest.java, RecursCompf.java и Xterm.java ), размещенных в двух директориях (каталогах). Хорошим средством для автоматизации работы над сложными программными проектами является утилита make, которая позволяет значительно облегчить труд программиста в процессе написания и отладки большой программы (на любом языке).

В специальном управляющем файле, обычно именуемом Makefile, необходимо указать те конечные и промежуточные цели, которые должны быть достигнуты в процессе работы над проектом. В нашем случае такими целями являются запуск итоговой программы, ее компиляция и удаление class -файлов. Каждой цели в управляющем файле дается уникальное имя, после которого ставится двоеточие и перечисляются те файлы, от которых данная цель зависит, а в следующей строке после обязательного символа табуляции записывается действие, которое должно быть выполнено для достижения цели.

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

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

Makefile

# -*- mode: makefile -*-

.PHONY : run clean

# Запустить тест рекурсивного компилятора формул.
run:			RecursCompfTest.class 
	java RecursCompfTest

# Откомпилировать текст рекурсивного компилятора формул.
RecursCompfTest.class:	RecursCompfTest.java RecursCompf.java \
                        Xterm.java
	javac RecursCompfTest.java

# Удалить лишние файлы.
clean:
	rm -f *.class *.expand

Кроме описания трех целей ( run, RecursCompfTest.class и clean ) в нем содержится информация для редактора emacs о специальном режиме работы с этим файлом и указание для утилиты make, сообщающее, что цели run и clean относятся к разряду особых — они не является именами файлов, создаваемых при их построении. Символ \ в конце строки означает, что следующая строка файла должна рассматриваться, как продолжение предыдущей.

Команда make, которая в данном случае эквивалентна make run, сначала выяснит, нет ли уже построенной цели RecursCompfTest.class. Если она существует и времена модификации всех файлов, от которых зависит эта цель ( RecursCompfTest.java, RecursCompf.java и Xterm.java ) не превосходят времени создания цели RecursCompfTest.class, то будет просто выполнена команда запуска java RecursCompfTest. Если же хотя бы один из файлов с исходными текстами был модифицирован, то произойдет его перекомпиляция.

Утилита make, таким образом, позволяет не заботиться о перекомпиляции измененных исходных файлов, выполняя ее автоматически.

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

И еще одно замечание. При компиляции формулы $$a-b-c$$ получается результат a b c - -, что явно не верно!. Правильным результатом является a b - c -. Значит написанная нами программа ошибочна?

(рис 12.3) Дерево вывода формулы a-b-c

На самом деле программа написана абсолютно правильно, а причина неверной компиляции заключается в грамматике $$G_2$$. Дело в том, что эта грамматика, верно отражая приоритеты арифметических операций, неявно считает их все правоассоциативными, в то время как они являются на самом деле левоассоциативными. Это хорошо видно из рисунка 12.3, где изображено дерево вывода формулы $$a-b-c$$ в грамматике $$G_2$$.

Определенная выше грамматика $$G_0$$, задавая тот же язык, предполагает правильную ассоциативность операций. К сожалению, использовать ее для написания рекурсивного компилятора формул нельзя. При обработке формулы совершенно не ясно, с чего она начинается — с терма или с формулы. Кроме того, рекурсивная цепочка вызовов в данном случае вполне может оказаться бесконечной.

Одним из способов построения компилятора, который будет учитывать левоассоциативность всех арифметических операций, является использование грамматики $$G_3$$. Основываясь на ней, можно построить другую реализацию рекурсивного компилятора формул, в которой метод compileF после вызова метода обработки терма будет содержать цикл, обеспечивающий обработку всех следующих за ним других термов этой формулы. Аналогичное изменение необходимо сделать и в методе compileT.

Такая реализация компилятора будет уже корректно обрабатывать все правильные арифметические формулы. Ее основной недостаток — невозможность простой модификации. Внесение даже небольших изменений во входной язык требует внесения глобальных изменений и переписывания значительной части программы. Примером подобного изменения может быть повышение приоритета вычитания так, что формула $$a*b-c$$ должна будет трактоваться, как $$a*(b-c)$$.

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

Стековый компилятор формул

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

Для доказательства этого факта применим отрицание критерия индуктивности. Результатом компиляции цепочек $$w_1 = a-b$$ и $$w_2 = (a-b)$$ является одна и та же цепочка a b -. Если дописать к обеим этим цепочкам двухэлементную цепочку $$x = *c$$ (любая одноэлементная приводит к неправильной формуле), то результатом компиляции первой из них будет программа a b c * -, a второй — a b - c *, т.е. $$\tau(w_1\circ x) \ne \tau(w_2\circ x)$$.

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

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

Пусть сформулированное выше утверждение справедливо для любой формулы, число операций в которой не превосходит $$n$$. Рассмотрим произвольную формулу с $$n+1$$ операцией. Выделим ту из этих операций, которая должна выполняться последней в соответствии с действующими приоритетами и ассоциативностью. Данная операция разделяет два фрагмента исходной формулы, в каждом из которых содержится не более, чем по $$n$$ операций. По предположению индукции каждый из них может быть откомпилирован с соблюдением двух сформулированных выше условий. Запишем последовательно результат компиляции каждого из них, а затем — символ выделенной операции. Получившаяся цепочка, являющаяся переводом исходной формулы, удовлетворяет нужным требованиям, что и завершает доказательство.

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

Требуемый нам класс Compf, содержащий метод compile, можно сделать выведенным из класса Stack, являющегося непрерывной реализацией стека символов на базе вектора. Как это было объяснено выше, метод compile должен обеспечивать последовательную обработку всех символов исходной формулы, что будет осуществляться с помощью private -метода processSymbol.

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

public void compile(char[] str) { 
        processSymbol('(');
        for(int i = 0; i < str.length; i++)
            processSymbol(str[i]);
        processSymbol(')');
        Xterm.print("\n");
    }

Все возможные входные символы делятся (с помощью метода symType ) на четыре категории: две скобки ( SYM\_LEFT и SYM\_RIGHT ), знаки операций ( SYM\_OPER ) и все остальные ( SYM\_OTHER ). К последним относятся, прежде всего, имена переменных.

Реализация метода processSymbol полностью соответствует проведенному выше обсуждению компиляции с помощью стека:

private void processSymbol(char c) {
        switch (symType(c)) {
          case SYM_LEFT:
            push(c); break;
          case SYM_RIGHT:
            processSuspendedSymbols(c); pop(); break;
          case SYM_OPER:
            processSuspendedSymbols(c); push(c); break;
          case SYM_OTHER:
            nextOther(c); break;
        }
    }

Открывающая скобка всегда заносится в стек отложенных операций; закрывающая скобка приводит к вызову метода processSuspendedSymbols, обрабатывающего отложенные символы, и удалению из стека парной ей открывающей скобки; символ операции вызывает обработку отложенных символов и сам затем помещается в стек; а имя переменной просто печатается с помощью методов nextOther и nextOper.

Метод processSuspendedSymbols обеспечивает обработку всех тех отложенных операций, которые выполнимы в данный момент, что определяется приоритетом операций (метод priority ) и правилами предшествования (метод precedes ):

private void processSuspendedSymbols(char c) {
        while (precedes(top(), c))
            nextOper(pop());
    }
    private int priority(char c) {
        return c == '+' || c == '-' ? 1 : 2;
    }
    private boolean precedes(char a, char b) {
        if(symType(a) == SYM_LEFT) return false;
        if(symType(b) == SYM_RIGHT) return true;
        return priority(a) >= priority(b);
    }
    protected void nextOper(char c) {	
        Xterm.print("" + c + " ");
    }

Текст проекта целиком приведен в последней секции параграфа. Обратите внимание, насколько эта реализация компилятора сложнее рекурсивной. Однако она позволяет легко модифицировать ее при изменении входного языка. Например, изменение ассоциативности всех арифметических операций требует только удаления одного символа: в методе precedes нужно >= заменить на >. Многие значительно более сложные задачи на модификацию также сводятся к минимальным изменениям в тексте программы и не требует изменения структуры всей реализации в целом.

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

Использование в тексте программы ключевого слова protected и некоторые другие не вполне понятные моменты объясняются тем, что построенный класс Compf будет использован в качестве базового для реализации интерпретатора арифметических выражений. Подобный подход является характерной особенностью объектно-ориентированного программирования — уже написанный код может быть использован для решения родственной задачи без какой-либо его модификации.

Интерпретатор арифметических выражений

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

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

В случае программ на языках C и C++ компилятор позволяет получить файл, который содержит машинные команды и, следовательно, может быть выполнен непосредственно. Для языка Java компилятор строит так называемый байт-код, для исполнения которого необходима специальная программа (запускаемая с помощью команды java ).

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

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

Выше уже отмечалось, что наряду с десятичной системой счисления в программировании часто используют двоичную, восьмеричную и шестнадцатеричную. В целом ряде языков программирования принято соглашение, согласно которому числа, запись которых начинается с нуля, считаются восьмеричными, а те, запись которых начинается с 0x или 0X, — шестнадцатеричными. Таким образом, запись 0458 является некорректной (так как восьмеричная система счисления не содержит цифры 8), а в записи чисел, начинающихся с 0x или 0X, могут использоваться буквы от A до F, обозначающие шестнадцатеричные цифры со значениями от 10 до~15.

Запись чисел в римской системе счисления

1	2	3	4	5
I	II	III	IV	V
6	7	8	9	10
VI	VII	VIII	IX	X
11	13	18	19	22
XI	XIII	XVIII	XIX	XXII
34	39	40	60	99
XXXIV	XXXIX	XL	LX	XCIX
200	438	649	999	1207
CC	CDXXXVIII	DCXLIX	CMXCIX	MCCVII
2045	3555	3678	3900	3999
MMXLV	MMMDLV	MMMDCLXXVIII	MMMCM	MMMCMXCIX

Хорошо известным примером непозиционной системы счисления являются римская. В этой системе цифры $$I$$, $$V$$, $$X$$, $$L$$, $$C$$, $$D$$ и $$M$$ всегда обозначают 1, 5, 10, 50, 100, 500 и 1000 соответственно, вне зависимости от позиции цифры в записи числа. При записи чисел в римской системе счисления значением числа является алгебраическая сумма цифр, в него входящих. При этом цифры в записи числа следуют, как правило, в порядке убывания их значений, и не разрешается записывать рядом более трех одинаковых цифр. В том случае, когда за цифрой с большим значением следует цифра с меньшим, ее вклад в значение числа в целом является отрицательным. Таблица 12.1 содержит типичные примеры, иллюстрирующие общие правила записи чисел в римской система счисления (не превосходящих 3999).

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

Задача 12.2. Напишите программу (интерпретатор формул), которая для любой правильной арифметической формулы (элемента языка $$L(G_0)$$ ), содержащей цифры от 0 до 9, вычисляет и печатает значение этой формулы.

Для того чтобы реализовать стековый калькулятор, конечно, необходим стек целых чисел. Его непрерывная реализация будет осуществляться классом StackInt. Класс Calc, который будет осуществлять интерпретацию арифметических формул, во многом похож на класс Compf. Одним из отличий является то, что в формуле присутствуют числа, а не идентификаторы переменных. Вторым и более существенным — выполнение операций вместо их печати в виде программы для стекового компилятора.

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

Из вышесказанного следует, что класс Calc целесообразно сделать дочерним по отношению к ранее нами созданному классы Compf, включив в него private -компоненту s (стек целых чисел) и переопределив методы symOther, nextOther и nextOper:

protected int symOther(char c) {
        if (c < '0' || c > '9') {
            Xterm.println("Недопустимый символ: " + c);
            System.exit(0);
        }
        return SYM_OTHER;
    }	
    protected void nextOper(char c) {	
        int second = s.pop();
        int first  = s.pop();
        switch (c) {
          case '+':
            s.push(first + second); break;
          case '-':	  
            s.push(first - second); break;
          case '*':
            s.push(first * second); break;
          case '/':
            s.push(first / second); break;
        }
    }
    protected void nextOther(char c) {	
        s.push(char2int(c));
    }

Метод char2int позволяет преобразовать символ в соответствующее ему целое число:

private static int char2int(char c) {
        return (int)c - (int)'0';
    }

Конструктор класса Calc должен создать стек целых чисел, а метод compile после вызова одноименного метода родительского класса обязан напечатать результат вычислений, находящийся на вершине стека. Итоговый текст интерпретатора вместе с содержимом файлa Makefile, предусматривающим работу как с компилятором формул, так и с интерпретатором, приведены в последней секции параграфа.

Задачи для самостоятельного решения

Задача 12.3. Докажите, что языки, порожденные двумя указанными грамматиками, совпадают:

a) $$G_0$$ и $$G_1$$ ;

b) $$G_0$$ и $$G_2$$ ;

c) $$G_0$$ и $$G_3$$.

Задача 12.4. Задайте с помощью грамматики следующие языки:

a) язык всех целых десятичных чисел;

b) язык всех целых неотрицательных восьмеричных чисел;

c) язык всех целых неотрицательных шестнадцатеричных чисел;

d) язык всех римских чисел от 1 до 3999;

e) язык всех допустимых идентификаторов в Java;

f) язык всех констант типа double в Java;

g) язык над алфавитом $$\Sigma = \{0, 1\}$$, состоящий из всех цепочек, в которых четное количество нулей и нечетное количество единиц;

h) язык над алфавитом $$\Sigma = \{0, 1\}$$, состоящий из всех цепочек, в которых количество нулей и единиц совпадают;

i) язык над алфавитом $$\Sigma = \{0, 1\}$$, состоящий из всех цепочек, инвариантных относительно операции инвертирования;

j) язык над алфавитом $$\Sigma = \{0, 1\}$$, состоящий из всех цепочек, начинающихся с нуля и заканчивающихся нулем, в которых и количество нулей и количество единиц нечетны.

Задача 12.5. Модифицируйте текст эталонного проекта "Рекурсивный компилятор формул" так, чтобы:

a) все арифметические операции трактовались, как левоассоциативные;

b) приоритеты операций сложения и вычитания были выше, чем у операций умножения и деления;

c) в качестве имен переменных допускались произвольные идентификаторы языка Java;

d) для группировки в формулах можно было использовать не только круглые, но также квадратные и фигурные скобки;

e) компилировались формулы, содержащие операцию % (остаток от деления) с приоритетом, равным приоритету операций умножения и деления; в язык стекового компилятора при этом также добавляется операция % ;

f) компилировались формулы, содержащие пробелы и комментарии двух видов: /* */ и // ;

g) компилировались формулы, запись которых состоит из нескольких строк;

h) компилировались формулы, содержащие унарные арифметические операции + и - ; в язык стекового компилятора при этом также добавляются операции + и - ;

i) компилировались формулы, содержащие бинарные битовые операции | и ; в язык стекового компилятора при этом также добавляются операции | и ;

j) компилировались формулы, содержащие унарную битовую операцию ^ ; в язык стекового компилятора при этом также добавляется операция ^.

Задача 12.6. Модифицируйте текст эталонного проекта "Рекурсивный компилятор формул" так, чтобы:

a) формулы, содержащие только десятичные числа (до 3999), компилировались в программы для стекового калькулятора, содержащие восьмеричные числа;

b) формулы, содержащие только десятичные числа (до 3999), компилировались в программы для стекового калькулятора, содержащие шестнадцатеричные числа;

c) формулы, содержащие только десятичные числа (до 3999), компилировались в программы для стекового калькулятора, содержащие римские числа;

d) формулы, содержащие только восьмеричные числа (до 3999), компилировались в программы для стекового калькулятора, содержащие десятичные числа;

e) формулы, содержащие только восьмеричные числа (до 3999), компилировались в программы для стекового калькулятора, содержащие римские числа;

f) формулы, содержащие только шестнадцатеричные числа (до 3999), компилировались в программы для стекового калькулятора, содержащие десятичные числа;

g) формулы, содержащие только шестнадцатеричные числа (до 3999), компилировались в программы для стекового калькулятора, содержащие римские числа;

h) формулы, содержащие только римские числа (до 3999), компилировались в программы для стекового калькулятора, содержащие десятичные числа;

i) формулы, содержащие только римские числа (до 3999), компилировались в программы для стекового калькулятора, содержащие восьмеричные числа;

j) формулы, содержащие только римские числа (до 3999), компилировались в программы для стекового калькулятора, содержащие шестнадцатеричные числа.

Задача 12.7. Напишите программу (компилятор формул), которая для любой правильной арифметической формулы (элемента языка $$L(G_3)$$ ), данной ей на вход, выдает семантически эквивалентную ей программу стекового калькулятора (элемент языка $$L(G_S)$$ ).

Задача 12.8. Модифицируйте текст эталонного проекта "Стековый компилятор формул" так, чтобы:

a) деление трактовалось, как левоассоциативная операция;

b) приоритеты операций сложения и вычитания были выше, чем у операций умножения и деления;

c) в качестве имен переменных допускались произвольные идентификаторы языка Java;

d) для группировки в формулах можно было использовать не только круглые, но также квадратные и фигурные скобки;

e) компилировались формулы, содержащие операцию % (остаток от деления) с приоритетом, равным приоритету операций умножения и деления; в язык стекового компилятора при этом также добавляется операция % ;

f) компилировались формулы, содержащие пробелы и комментарии двух видов: /* */ и // ;

g) компилировались формулы, запись которых состоит из нескольких строк;

h) компилировались формулы, содержащие унарные арифметические операции + и - ; в язык стекового компилятора при этом также добавляются операции + и - ;

i) компилировались формулы, содержащие бинарные битовые операции | и ; в язык стекового компилятора при этом также добавляются операции | и ;

j) компилировались формулы, содержащие унарную битовую операцию ^ ; в язык стекового компилятора при этом также добавляется операция ^.

Задача 12.9. Модифицируйте текст эталонного проекта "Стековый компилятор формул" так, чтобы:

a) формулы, содержащие только десятичные числа (до 3999), компилировались в программы для стекового калькулятора, содержащие восьмеричные числа;

b) формулы, содержащие только десятичные числа (до 3999), компилировались в программы для стекового калькулятора, содержащие шестнадцатеричные числа;

c) формулы, содержащие только десятичные числа (до 3999), компилировались в программы для стекового калькулятора, содержащие римские числа;

d) формулы, содержащие только восьмеричные числа (до 3999), компилировались в программы для стекового калькулятора, содержащие десятичные числа;

e) формулы, содержащие только восьмеричные числа (до 3999), компилировались в программы для стекового калькулятора, содержащие римские числа;

f) формулы, содержащие только шестнадцатеричные числа (до 3999), компилировались в программы для стекового калькулятора, содержащие десятичные числа;

g) формулы, содержащие только шестнадцатеричные числа (до 3999), компилировались в программы для стекового калькулятора, содержащие римские числа;

h) формулы, содержащие только римские числа (до 3999), компилировались в программы для стекового калькулятора, содержащие десятичные числа;

i) формулы, содержащие только римские числа (до 3999), компилировались в программы для стекового калькулятора, содержащие восьмеричные числа;

j) формулы, содержащие только римские числа (до 3999), компилировались в программы для стекового калькулятора, содержащие шестнадцатеричные числа.

# -*- mode: makefile -*-

.PHONY : run clean

# Запустить тест рекурсивного компилятора формул.
run:			RecursCompfTest.class 
	java RecursCompfTest

# Откомпилировать текст рекурсивного компилятора формул.
RecursCompfTest.class:	RecursCompfTest.java RecursCompf.java \
                        Xterm.java
	javac RecursCompfTest.java

# Удалить лишние файлы.
clean:
	rm -f *.class *.expand

// Рекурсивный компилятор формул.
public class RecursCompf {
    private static final int DEFSIZE = 255;
    private char[] str;
    private int    index;
    private void compileF() {
        compileT();
        if (index >= str.length) return;
        if (str[index] == '+'){
            index++;
            compileF();
            Xterm.print("+ ");
            return;
        }
        if (str[index] == '-'){
            index++;
            compileF();
            Xterm.print("- ");
        }
    }
    private void compileT() {
        compileM();
        if (index >= str.length) return;
        if (str[index] == '*'){
            index++;
            compileT();
            Xterm.print("* ");
            return;
        }
        if (str[index] == '/'){
            index++;
            compileT();
            Xterm.print("/ ");
        }
    }
    private void compileM() {
        if (str[index] == '(') {
            index++;
            compileF();
            index++;
        } else
	    compileV();
    }
    private void compileV() {
        Xterm.print("" + str[index++] + " ");
    }

    public void RecursCompf() {	
        str = new char[DEFSIZE];
    }
    public void compile(char[] str) {
        this.str = str;
        index    = 0;
        compileF();
        Xterm.print("\n");
    }
}

// Тест для рекурсивного компилятора формул.
public class RecursCompfTest {
    public static void main(String[] args) throws Exception {
        RecursCompf c = new RecursCompf();
        while (true)	       
            c.compile(Xterm.inputChars("Введите формулу -> "));	    
    }
}

# -*- mode: makefile -*-

.PHONY : compf calc clean

# Запустить тест стекового компилятора формул.
compf:			CompfTest.class
	java CompfTest

# Откомпилировать текст стекового компилятора формул.
CompfTest.class:	CompfTest.java Compf.java Xterm.java
	javac CompfTest.java

# Запустить тест калькулятора формул.
calc:			CalcTest.class
	java CalcTest

# Откомпилировать текст калькулятора формул.
CalcTest.class:		CalcTest.java Calc.java Compf.java Xterm.java
	javac CalcTest.java

# Удалить лишние файлы.
clean:
	rm -f *.class *.expand

// Непрерывная реализация стека символов.
class Stack {
    private static final int DEFSIZE = 16;
    private char[] array;
    private int    head;

    public Stack() {
        array = new char[DEFSIZE];
        head = 0; 
    }
    public final void push(char c) {
        array[head++] = c;
    }
    public final char pop() {
        return array[--head];
    }
    public final char top() {
        return array[head-1];
    }
} 
// Стековый компилятор формул.
public class Compf extends Stack {
    // Типы символов (скобки, знаки операции, иное).
    protected final static int SYM_LEFT  = 0,
                               SYM_RIGHT = 1,
                               SYM_OPER  = 2,
                               SYM_OTHER = 3;
    private int symType(char c) {
        switch (c) {
          case '(':
            return SYM_LEFT;
          case ')':
            return SYM_RIGHT;
          case '+': case '-': case '*': case '/':
            return SYM_OPER;
          default:
            return symOther(c);
        }
    }
    private void processSymbol(char c) {
        switch (symType(c)) {
          case SYM_LEFT:
            push(c); break;
          case SYM_RIGHT:
            processSuspendedSymbols(c); pop(); break;
          case SYM_OPER:
            processSuspendedSymbols(c); push(c); break;
          case SYM_OTHER:
            nextOther(c); break;
        }
    }
    private void processSuspendedSymbols(char c) {
        while (precedes(top(), c))
            nextOper(pop());
    }
    private int priority(char c) {
        return c == '+' || c == '-' ? 1 : 2;
    }
    private boolean precedes(char a, char b) {
        if(symType(a) == SYM_LEFT) return false;
        if(symType(b) == SYM_RIGHT) return true;
        return priority(a) >= priority(b);
    }
    protected int symOther(char c) {
        if (c < 'a' || c > 'z') {
            Xterm.println("Недопустимый символ: " + c);
            System.exit(0);
        }
        return SYM_OTHER;
    }	
    protected void nextOper(char c) {	
        Xterm.print("" + c + " ");
    }
    protected void nextOther(char c) {	
        nextOper(c);
    }

    public void compile(char[] str) { 
        processSymbol('(');
        for(int i = 0; i < str.length; i++)
            processSymbol(str[i]);
        processSymbol(')');
        Xterm.print("\n");
    }
}

// Тест для компилятора формул.
public class CompfTest {
    public static void main(String[] args) throws Exception {
        Compf c = new Compf();
        while (true)	       
            c.compile(Xterm.inputChars("Введите формулу -> "));	    
    }
}

// Непрерывная реализация стека целых чисел.
class StackInt {
    private static final int DEFSIZE = 16;
    private int[] array;
    private int   head;

    public StackInt() {
        array = new int[DEFSIZE];
        head = 0;
    }
    public final void push(int val) {
        array[head++] = val;
    }
    public final int pop() {
        return array[--head];
    }
    public final int top() {
        return array[head-1];
    }
}
// Калькулятор арифметических формул.
public class Calc extends Compf {
    private StackInt s;
    private static int char2int(char c) {
        return (int)c - (int)'0';
    }
    protected int symOther(char c) {
        if (c < '0' || c > '9') {
            Xterm.println("Недопустимый символ: " + c);
            System.exit(0);
        }
        return SYM_OTHER;
    }	
    protected void nextOper(char c) {	
        int second = s.pop();
        int first  = s.pop();
        switch (c) {
          case '+':
            s.push(first + second); break;
          case '-':	  
            s.push(first - second); break;
          case '*':
            s.push(first * second); break;
          case '/':
            s.push(first / second); break;
        }
    }
    protected void nextOther(char c) {	
        s.push(char2int(c));
    }

    public Calc() {
        s = new StackInt();
    }
    public final void compile(char[] str) { 
        super.compile(str);
        Xterm.println("" + s.top());
    }
}

// Тест для калькулятора формул.
public class CalcTest {
    public static void main(String[] args) throws Exception {
        Calc c = new Calc();
        while (true)	       
            c.compile(Xterm.inputChars("Введите формулу -> "));	    
    }
}