UNIX — универсальная среда программирования

Глава 8

Разработка программ

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

В частности, вашему вниманию предлагаются следующие программы:

• 

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

• 

— программа, определяющая процесс компиляции сложных программ и управляющая им;

• 

— программа, аналогичная , но создающая лексические анализаторы.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

, и т.д.

8.1 Этап 1: калькулятор с четырьмя действиями

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

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

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

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

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

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

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

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

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

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

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

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