Чтение онлайн

1. Создание калькулятора с четырьмя действиями:

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

2. Добавление переменных с именами от

до . В этой версии есть также унарный минус и некоторые средства защиты от ошибок.

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

, и т.п., полезных констант типа (обозначается как ) и операции возведения в степень.

4. Внесение внутренних изменений: оператор вычисляется не непосредственно, а порождает код, который впоследствии интерпретируется. Новые возможности не добавляются, но подготавливается переход к п. 5.

5. Добавление структур управления:

и — группирование операторов с помощью и и операции отношений типа , и т.п.

6. Добавление рекурсивных процедур и функций с параметрами, а также операторов для ввода-вывода строк и чисел.

Окончательная версия языка описана в гл. 9 как пример программных средств подготовки документации системы UNIX. В приложении 2 приводится справочное руководство по калькулятору.

Эта глава довольно объемная, поскольку в ней детально рассматривается, как правильно написать нетривиальную программу. Предполагается, что вы знаете язык Си и имеете под рукой экземпляр справочного руководства по системе UNIX (том 2), поскольку просто невозможно объяснить все нюансы. Будьте готовы к тому, что вам придется прочитать главу несколько раз. Окончательная версия полностью представлена в приложении 3. Заметим, кстати, что мы долго спорили из-за имени языка, но так и не придумали подходящее. Остановились на

, что означает "калькулятор высокого уровня" (high level calculator).

Его версии соответственно называются

, и т.д.

Прежде всего рассмотрим реализацию

— программы с такими же возможностями, как и простейший карманный калькулятор, но гораздо менее удобной для переноса. Она выполняет четыре операции: , , , и, имеет скобки с произвольной глубиной вложенности, чем обладают лишь немногие калькуляторы. Если вы введете выражение и символ RETURN, результат будет напечатан в следующей строке:

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

простое и краткое:

Здесь список — последовательность выражений, каждое из которых завершается символом перевода строки, а выражение — число или пара выражений, объединенных операцией, либо выражение в скобках.

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

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

Генератор синтаксических анализаторов

[15] преобразует компилятор грамматических правил языка, подобных приведенным выше, в анализатор, который разбирает операторы языка. обладает возможностью приписывать значения компонентам грамматики таким образом, что в процессе разбора значение может быть "вычислено" . Используется поэтапно,

На первом этапе записывается грамматика языка, но более точно, чем было показано ранее, т.е. определяется синтаксис. На этом этапе назначение

— предупреждение появления ошибок и двусмысленностей в грамматике.

На втором этапе каждое правило (правило вывода грамматики) сопровождается описанием действия на тот случай, когда найден экземпляр грамматической конструкции в разбираемой программе. Часть действия записывается на Си, причем должны выполняться определенные соглашения о связи между грамматикой и текстом. Здесь определяется семантика языка.

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

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

На следующем этапе разрабатывается управляющая процедура, которая вызывает анализатор, созданный

.

Программа

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

Действие

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