Эта глава довольно объемная, поскольку в ней детально рассматривается, как правильно написать нетривиальную программу. Предполагается, что вы знаете язык Си и имеете под рукой экземпляр справочного руководства по системе 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-описания: лексемы, грамматические переменные,

информация о приоритетах и ассоциативности

%%