Читаем без скачивания UNIX — универсальная среда программирования - Брайан Керниган
Шрифт:
Интервал:
Закладка:
• 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Генератор синтаксических анализаторов yacc[15] преобразует компилятор грамматических правил языка, подобных приведенным выше, в анализатор, который разбирает операторы языка. Yacc обладает возможностью приписывать значения компонентам грамматики таким образом, что в процессе разбора значение может быть "вычислено" . Используется yacc поэтапно,
На первом этапе записывается грамматика языка, но более точно, чем было показано ранее, т.е. определяется синтаксис. На этом этапе назначение yacc — предупреждение появления ошибок и двусмысленностей в грамматике.
На втором этапе каждое правило (правило вывода грамматики) сопровождается описанием действия на тот случай, когда найден экземпляр грамматической конструкции в разбираемой программе. Часть действия записывается на Си, причем должны выполняться определенные соглашения о связи между грамматикой и текстом. Здесь определяется семантика языка.
Третий этап — создание лексического анализатора, который должен читать разбираемый входной поток и разбивать его для анализатора на осмысленные единицы. Примером лексической единицы длиной в несколько символов может служить NUMBER; операции из одного символа, такие, как + и *, также являются лексическими единицами. По традиции лексические единицы называют лексемами.
На следующем этапе разрабатывается управляющая процедура, которая вызывает анализатор, созданный yacc.
Программа yacc преобразует грамматику и семантические процедуры в функцию разбора с именем yyparse и записывает ее в виде файла с текстом на Си. Если yacc не находит ошибок, то анализатор, лексический анализатор и управляющую процедуру можно откомпилировать, возможно, связать с другими программами на Си и выполнить.
Действие yacc сводится к многократному обращению к лексическому анализатору за лексемами, распознаванию грамматических (синтаксических) конструкций во входном потоке и выполнению семантических процедур по мере распознавания грамматических правил. Вызывать лексический анализатор нужно по имени yylex, так как именно эту функцию инициирует анализатор yyparse всякий раз, когда ему нужна следующая лексема. (Все имена, используемые yacc, начинаются с y.)
Чтобы быть более точными, укажем, что входной поток для yacc должен иметь такой вид:
%{
Операторы Си типа #include, описания и т. д.
Эта часть необязательна.
%}
yacc-описания: лексемы, грамматические переменные,
информация о приоритетах и ассоциативности
%%
грамматические правила и действия
%%
еще операторы Си (необязательно):
main() {
...; yyparse(); ...
}
yylex() {
...
}
...
Этот поток поступает на вход yacc, а результат записывается в файл y.tab.c, имеющий следующую структуру:
Операторы на Си между %{ и %}, если есть
Операторы на Си из части после второй комбинации %%, если есть:
main() {
...; yyparse(); ...
}
yylex() {
...
}
...
yyparse() {
анализатор, который вызывает yylex()
}
Такой подход типичен для системы UNIX: yacc выдает текст на Си, а не оттранслированный файл (.o), что является наиболее гибким решением, так как созданный текст, переносим и легко поддается любому другому преобразованию (если появится хорошая идея).
Генератор yacc сам по себе представляется мощным программным средством. Его изучение потребует от вас, конечно, некоторых усилий, но все ваши "затраты" многократно окупятся. Анализаторы, создаваемые yacc, — небольшие, эффективные и корректные (хотя за семантические преобразования отвечаете вы). Кроме того, многие неприятные проблемы, связанные с процессом разбора, решаются автоматически. Программы языковых распознавателей достаточно легко создавать и, что, возможно, еще более важно, изменять по мере совершенствования определения языка.
Использование программ на этапе 1Исходный текст hoc1 состоит из грамматических правил с описанием действий лексической процедуры yylex и функции main, хранимых в одном файле hoc.y. (Имена файлов, содержащих текст для yacc, традиционно оканчиваются на .y, но это соглашение в отличие от соглашения о сс и .c не поддерживает сам yacc.) Грамматика составляет первую половину файла hoc.y:
