Глава 8
Разработка программ
Первоначально системе UNIX предназначалась роль среды для разработки программ. В настоящей главе мы обсудим некоторые применяемые с этой целью программные средства на примере солидной программы — интерпретатора языка программирования, сравнимого по мощности с Бейсиком. Мы выбрали реализацию языка, потому что возникающие здесь проблемы характерны для больших программ. Более того, многие программы полезно рассматривать как языковые процессоры, преобразующие входной поток определенной структуры в последовательность действий и выходной поток, т. е. мы хотим продемонстрировать вам программные средства разработки языков.
В частности, вашему вниманию предлагаются следующие программы:
•
yacc
— генератор синтаксических анализаторов; программа, которая по описанию грамматики языка порождает анализатор;
•
make
— программа, определяющая процесс компиляции сложных программ и управляющая им;
•
lex
— программа, аналогичная
yacc
, но создающая лексические анализаторы.
Мы покажем вам приемы разработки программ в несколько этапов — от простого к сложному. Ниже описаны шесть этапов реализации языка, каждый из которых поучителен уже сам по себе. Эти этапы отражают реальный процесс написания программы:
1. Создание калькулятора с четырьмя действиями:
+
,
-
,
*
,
/
(и со скобками). Калькулятор выполняет операции над числами с плавающей точкой, каждая строка состоит из одного выражения; полученное значение печатается сразу.
2. Добавление переменных с именами от
а
до
z
. В этой версии есть также унарный минус и некоторые средства защиты от ошибок.
3. Добавление переменных с именами произвольной длины, встроенных функций для
sin
,
exp
и т.п., полезных констант типа π (обозначается как
PI
) и операции возведения в степень.
4. Внесение внутренних изменений: оператор вычисляется не непосредственно, а порождает код, который впоследствии интерпретируется. Новые возможности не добавляются, но подготавливается переход к п. 5.
5. Добавление структур управления:
if-else
и
while
— группирование операторов с помощью и и операции отношений типа
>
,
<=
и т.п.
6. Добавление рекурсивных процедур и функций с параметрами, а также операторов для ввода-вывода строк и чисел.
Окончательная версия языка описана в гл. 9 как пример программных средств подготовки документации системы UNIX. В приложении 2 приводится справочное руководство по калькулятору.
Эта глава довольно объемная, поскольку в ней детально рассматривается, как правильно написать нетривиальную программу. Предполагается, что вы знаете язык Си и имеете под рукой экземпляр справочного руководства по системе UNIX (том 2), поскольку просто невозможно объяснить все нюансы. Будьте готовы к тому, что вам придется прочитать главу несколько раз. Окончательная версия полностью представлена в приложении 3. Заметим, кстати, что мы долго спорили из-за имени языка, но так и не придумали подходящее. Остановились на
hoc
, что означает "калькулятор высокого уровня" (high level calculator).
Его версии соответственно называются
hoc1
,
hoc2
и т.д.
8.1 Этап 1: калькулятор с четырьмя действиями
Прежде всего рассмотрим реализацию
hoc1
— программы с такими же возможностями, как и простейший карманный калькулятор, но гораздо менее удобной для переноса. Она выполняет четыре операции:
+
,
-
,
*
,
/
и, имеет скобки с произвольной глубиной вложенности, чем обладают лишь немногие калькуляторы. Если вы введете выражение и символ
RETURN, результат будет напечатан в следующей строке:
$ hoc1
4*3*2
24
(1+2)*(3+4)
21
1/2
0.5
355/113
3.1415929
-3 - 4
hoc1 : syntax error near line 4 No unary minus yet
$
Грамматика
С появлением формы Бэкуса-Наура, предложенной для Алгола, языки стали описываться с помощью формальной грамматики. Абстрактное описание грамматики
hoc1
простое и краткое:
список: выраж \n
список выраж \n
выраж: NUMBER
выраж + выраж
выраж - выраж
выраж * выраж
выраж / выраж
( выраж )
Здесь список — последовательность выражений, каждое из которых завершается символом перевода строки, а выражение — число или пара выражений, объединенных операцией, либо выражение в скобках.
Приведенное описание не полное, так как в нем не определены естественный приоритет и ассоциативность операций, а также не заданы значения конструкциям языка. Хотя список специфицируется через выраж, а оно в свою очередь через
NUMBER
, само
NUMBER
нигде не определено, Поэтому чтобы перейти от упрощенного описания к работающей программе, необходимо внести ясность в эти вопросы.
Генератор синтаксических анализаторов
yacc
[15] преобразует компилятор грамматических правил языка, подобных приведенным выше, в анализатор, который разбирает операторы языка.
Yacc
обладает возможностью приписывать значения компонентам грамматики таким образом, что в процессе разбора значение может быть "вычислено" . Используется
yacc
поэтапно,
На первом этапе записывается грамматика языка, но более точно, чем было показано ранее, т.е. определяется синтаксис. На этом этапе назначение
yacc
— предупреждение появления ошибок и двусмысленностей в грамматике.
На втором этапе каждое правило (правило вывода грамматики) сопровождается описанием действия на тот случай, когда найден экземпляр грамматической конструкции в разбираемой программе. Часть действия записывается на Си, причем должны выполняться определенные соглашения о связи между грамматикой и текстом. Здесь определяется семантика языка.
