Главная » Программирование для UNIX » Разработка программ в системе UNIX

0
 

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

В этой главе мы изучим:

•      yacc – генератор синтаксических анализаторов, который по описа нию  грамматики языка генерирует для  него  синтаксический ана лизатор;

•      make –  программу,  предназначенную  для  управления  процессом компиляции сложных программ;

•      lex  –  программу для  создания  лексических анализаторов, аналогичную yacc.

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

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

1.           Калькулятор, выполняющий четыре арифметических действия – +,

–, *, / – над числами с плавающей точкой, с учетом скобок. Каждое

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

2.           Переменные с именами от a до z. Унарный минус и обработка неко торых ошибок.

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

exp и т. п., полезные константы, такие как π  (записывается как PI

из-за ограниченных типографских возможностей), и оператор воз-

ведения в степень.

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

5.           Операторы управления:  операторы  if–else  и  while,  объединение операторов в блоки фигурными скобками, операторы сравнения >,

<= и другие.

6.           Рекурсивные  функции  и  процедуры,  принимающие аргументы.

Операторы ввода и вывода строк и чисел.

Получившийся язык описан в главе 9, где на его примере рассмотрено программное обеспечение для подготовки документов. Справочное руководство находится в приложении 2.

Это достаточно длинная глава, так как написание нетривиальной программы требует внимания к очень  многим деталям. Предполагается, что читатель знаком с языком Си и имеет  под рукой второй том спра вочного руководства по UNIX, потому  что в этой  книге просто  не хва тит  места  для объяснения всех нюансов. Проявите упорство и будьте  готовы  перечитать главу дважды. Полный текст  окончательной версии  приведен в приложении 3 – так легче  увидеть, как скомпонована программа.

Авторы потратили немало времени, обсуждая, как назвать этот язык, но так  и не придумали ему достойного имени. Мы остановились на названии hoc (high-order calculator –  высокоорганизованный калькулятор). Соответственно, версии называются hoc1, hoc2 и т. д.

Этап  1: Калькулятор, выполняющий четыре операции

В этом разделе рассмотрена программа hoc1, выполняющая практически те же действия, что и карманный калькулятор, но уступающая ему в мобильности. Она выполняет только четыре действия: +, –, * и /, но зато обрабатывает скобки произвольной глубины вложенности, что доступно не всем карманным калькуляторам. Если  после  ввода  выражения нажата клавиша RETURN, результат вычислений появляется на следующей строке:

$ hoc1 4*3*2

24

(1+2)  * (3+4)

21

1/2 355/113

-3-4

0.5

3.1415929

hoc1:  syntax  error is on line 5   Унарный минус пока не реализован

$

Грамматика

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

list:        expr  \n

list  expr  \n expr:             NUMBER

expr  + expr expr  – expr expr  * expr expr  / expr

( expr  )

Другими словами, список (list) состоит  из последовательности выражений (expr), каждое из которых заканчивается символом новой  строки (\n).  Выражение может быть числом либо парой чисел с оператором между ними либо выражением в скобках.

Это неполное описание. Среди прочего, в нем отсутствует определение приоритетов и ассоциативности операторов, нет и разъяснения смыс ла  структурных компонентов. И  хотя  список определен в терминах выражения, а выражение – в терминах NUMBER, само NUMBER нигде не определено. Эти детали необходимо уточнить при  переходе от схематичного представления к работающей программе.

Обзор yacc

Программа yacc  – это генератор  синтаксических анализаторов1, то есть  программа,  преобразующая формальное  описание грамматики языка, подобное  приведенному выше, в программу  синтаксического

1        Имя yacc – это аббревиатура «yet another compiler-compiler» (еще один ком пилятор компиляторов), как назвал его автор, Стив Джонсон (Steve Johnson), комментируя количество аналогичных программ в тот  момент (при мерно  в 1972 году).  Но успех  имели лишь немногие компиляторы, среди  них и yacc.

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

Во-первых, надо  описать грамматику, как  это  было  сделано выше, только более  подробно.  Так определяется синтаксис языка. На  этом этапе  yacc можно использовать для  поиска ошибок и неопределенностей в грамматике.

Во-вторых,  каждое  порождающее правило  этой  грамматики  может быть  дополнено действием – описанием того,  что должно быть выполнено, когда в разбираемой программе встретится заданная грамматическая форма. Эта часть  пишется на Си с соблюдением соглашений о взаимодействии с грамматикой. Так определяется семантика языка.

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

Наконец, нужна управляющая программа,  запускающая синтаксический анализатор, построенный с помощью yacc.

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

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

Входной файл yacc имеет такой вид:

%{

необязательная секция

операторы Си, такие как #include, объявления и т. п.

%}

объявления yacc: лексические единицы, грамматические переменные, приоритеты и ассоциативность

%%

грамматические правила и действия

%%

дополнительные операторы Си (необязательно):

main()  {  …;  yyparse();  …  } yylex()  {  …  }

Этот текст обрабатывается yacc, и результат выводится в файл с именем y.tab.c, имеющий формат:

операторы Си, расположенные между %{ и %}, если имеются операторы Си, расположенные после второго  %%, если имеются: main()  { …; yyparse();  …  }

yylex() { … }

yyparse() { синтаксический анализатор, вызывающий yylex() }

То,  что  yacc создает текст на  Си,  а не скомпилированный объектный (.o) файл, типично для UNIX. Это наиболее гибкий подход – сгенерированный код переносим и может использоваться в любом другом месте.

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

Этап 1

Исходный текст hoc1 состоит  из описания грамматики и действий, лек сической  подпрограммы  yylex  и  функции main,  хранимых в  файле hoc.y.  (Имена файлов yacc традиционно заканчиваются на  .y, но сам yacc не навязывает это обозначение, в отличие от cc и c.) Первая половина  hoc.y содержит описание грамматики:

$ cat  hoc.y

%{

#define YYSTYPE  double    /*  тип данных  для стека  yacc  */

%}

%token  NUMBER

%left      ‘+’ ‘–’   /*  левоассоциативные,  одинаковый  приоритет */

%left      ‘*’ ‘/’   /*  левоассоциативные,  более высокий  приоритет */

%%

list:      /*  ничего */

| list ‘\n’

| list expr  ‘\n’        { printf("\t%.8g\n", $2);   }

;

expr:         NUMBER           { $$ = $1;  }

| expr  ‘+’ expr  { $$ = $1 + $3;  }

%%

| expr  ‘–’ expr  { $$ = $1 – $3;  }

| expr  ‘*’ expr  { $$ = $1 * $3;  }

| expr  ‘/’ expr  { $$ = $1 / $3;  }

| ‘(‘ expr  ‘)’    { $$ = $2;  }

;

/*  конец грамматики  */

В этих  нескольких строках немало новой информации. Не будем  объяснять здесь все подробности, в частности детали работы синтаксического анализатора, – это описано в руководстве по yacc.

Правила разделяются вертикальной чертой «|». С каждым грамматическим правилом может быть  связано действие, которое будет выполняться, когда на входе  будет опознано данное правило. Действие описывается последовательностью операторов Си, заключенной в фигурные  скобки { и }. Внутри действия переменные $n (т. е. $1, $2 и т. д.) ссылаются на  значения,  возвращаемые n-й  компонентой правила, а

$$ – это значение, возвращаемое правилом в целом. Так, например, в правиле

expr:      NUMBER     { $$ = $1;  }

$1 получает значение, возвращаемое при обработке лексемы NUMBER; это значение возвращается в качестве значения expr. Явное присваивание

$$ =  $1 может быть опущено, так как $$ всегда принимает значение $1, если ему явно  не присвоено что-то другое.

В следующей строке при выполнении правила

expr:      expr  ‘+’ expr      { $$ = $1 + $3;  }

значение результата равно  сумме  значений компонент expr. Обратите внимание, что знаку ‘+’ соответствует $2; пронумерованы все компоненты.

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

В yacc разрешен свободный формат входной информации; здесь  представлен рекомендуемый стандарт.

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

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

Рис. 8.1. Дерево  разбора  для выражения 2 + 3 * 4

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

#define  YYSTYPE  double

назначает стеку тип double.

Синтаксические классы, которые предстоит обрабатывать лексическому анализатору, должны быть объявлены, если только они не являются  односимвольными литералами, такими как ‘+’  и ‘–’. Объявление

%token декларирует один или несколько таких объектов. Для определения левой  или  правой ассоциативности вместо  %token следует указать

%left или  %right соответственно. (Левая ассоциативность означает, что выражение a–b–c будет  обработано как (a–b)–c, а не как a–(b–c).) При-

оритет определяется порядком описания:  лексемы, объявляемые од-

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

Оставшаяся часть  кода  состоит  из  функций  второй половины файла

hoc.y:

#include <stdio.h>

#include <ctype.h>

Продолжение hoc.y

char        *progname;    /*  для  сообщений  об ошибках  */ int lineno = 1;

main(argc,  argv)        /*  hoc1  */ char  *argv[];

{

progname = argv[0];

yyparse();

}

Функция main вызывает yyparse, выполняющую разбор. Переход от выражения к выражению полностью определяется последовательностью порождающих правил грамматики. С тем же успехом можно было  бы вызывать yyparse в цикле, определив для  list в качестве действия вывод результата и немедленный возврат.

В свою очередь, yyparse циклически вызывает функцию yylex для каждой входной лексемы. В нашем случае yylex устроена просто: она пропускает пробелы и табуляции, преобразует последовательности цифр в числовые значения, ведет  нумерацию входных строк для сообщений об  ошибках, а  все  прочие символы  возвращает без  изменений. Поскольку грамматикой определены только символы +, –, *, /, (, ) и \n, появление любого другого символа заставит yyparse сообщить об ошиб ке. Возвращаемое значение 0 сигнализирует функции yyparse о дости жении конца файла.

yylex()        /*  hoc1 */

{

Продолжение hoc.y

int c;

while  ((c=getchar()) == ‘ ‘ || c  == ‘\t’)

;

if (c  ==  EOF) return  0;

if (c  == ‘.’ ||  isdigit(c)) {      /*  число */ ungetc(c,  stdin);

scanf("%lf",  &yylval);

return NUMBER;

}

if (c  ==  ‘\n’) lineno++;

return c;

}

Переменная yylval используется для  связи  между синтаксическим и лексическим анализаторами, она определена в yyparse и имеет тот же  тип, что  и стек yacc. Функция yyparse  возвращает тип лексемы, а ее значение (если  имеется) записывает в переменную yylval. Например, число с плавающей точкой имеет тип NUMBER и значение, например 12.34. Некоторые лексемы, в частности такие знаки, как ‘+’ и ‘\n’, имеют только тип, но не значение. В таких случаях нет необходимости уста навливать значение yylval.

Объявление %token  NUMBER  преобразуется в  выходном файле y.tab.c  в директиву #define,  поэтому константу  NUMBER  можно использовать  в любом месте программы на Си. В yacc использованы значения, не пере секающиеся с таблицей символов ASCII.

При  наличии синтаксической ошибки yyparse вызывает yyerror, передавая строку с сообщением syntax   error. Ожидается, что пользователь yacc предоставит какую-нибудь функцию yyerror; наша версия просто  передает строку другой функции, warning, а она уже выводит некоторую информацию. В более новых версиях hoc сразу  используется warning.

yyerror(s)   /*  вызывается  для обработки  синтаксической ошибки  yacc  */ char  *s;

{

warning(s,  (char *)  0);

}

warning(s, t)   /*  выводит  предупреждение  */ char  *s,  *t;

{

fprintf(stderr,  "%s:  %s",  progname,  s); if  (t)

fprintf(stderr,  "  %s",  t); fprintf(stderr,  "  near  line  %d\n",  lineno);

}

На этом функции в hoc.y заканчиваются.

Компиляция программы yacc происходит в два этапа:

$ yacc  hoc.y                         Создает y.tab.c

$ cc  y.tab.c -o  hoc1         Создает исполняемую программу в  hoc1

$ hoc1 2/3

-3-4

0.66666667

hoc1:  syntax  error near  line 1

$

Упражнение 8.1. Исследуйте структуру файла y.tab.c. (В hoc1 его дли на составляет около  300 строк.) ~

Вносим изменения – унарный минус

Было заявлено, что в yacc очень  легко проводить изменение языка. В качестве примера введем  в hoc1 унарный минус, чтобы выражения типа

–3–4

вычислялись, а не отбрасывались как синтаксические ошибки.

В hoc.y надо добавить ровно две строчки. В конец раздела приоритетов добавляется новая лексема  UNARYMINUS, унарный минус получает наивысший приоритет:

%left

‘+’ ‘–’

%left

‘*’ ‘/’

%left

UNARYMINUS

/*  новое */

В грамматику добавляется еще одно порождающее правило для expr:

expr:         NUMBER                       { $$ = $1;  }

| ’–’    expr    %prec UNARYMINUS  {  $$ = –$2’  } /*  новое */

Определение %prec указывает на то, что  знак унарный минус (то есть знак минус перед выражением) имеет  приоритет UNARYMINUS (высокий), а действие заключается в изменении знака. Знак минус между двумя выражениями получает приоритет по умолчанию.

Упражнение 8.2.  Добавьте в hoc1 операторы % (деление нацело или  остаток) и унарный +. Совет: обратитесь к frexp(3). ~

Экскурс в make

Вводить две команды для того,  чтобы скомпилировать новую  версию hoc1, – это невыносимо. Несложно создать командный файл, который бы выполнял эту  задачу, но есть и более  хороший способ,  который в дальнейшем можно будет  обобщить для  случая, когда исходных фай лов  в программе несколько. Программа make читает в спецификации, как компоненты программы зависят друг  от друга  и как их обрабатывать для того,  чтобы  создать новую  версию программы. Она проверяет время  изменения  различных  компонент, вычисляет  минимальный объем  рекомпиляции, необходимый для получения новой  актуальной версии, и запускает процессы. Программа make в состоянии понять замысловатые  многоступенчатые процессы типа   yacc,  поэтому  можно помещать такие задачи в  спецификацию make,  не  разбивая их  на  отдельные шаги.

Разумнее  всего  применять  make,  когда  создаваемые программы  настолько велики,  что  располагаются в нескольких исходных  файлах, но иногда она  бывает полезна и для таких небольших программ, как hoc1. Приведем спецификацию make для hoc1, предполагается, что она находится в файле под названием makefile.

$ cat  makefile

hoc1:        hoc.o

cc  hoc.o  –o hoc1

$

Здесь  написано, что hoc1 зависит от hoc.o  и что hoc.o преобразуется в hoc1 посредством запуска компилятора Си  cc и помещения выходных данных в hoc1. При  этом  make уже  знает, как преобразовать исходный файл yacc в hoc.y в объектный файл hoc.o:

$ make                                        Выполнить первое действие в makefile, hoc1 yacc    hoc.y

cc    –c y.tab.c

rm y.tab.c

mv  y.tab.o  hoc.o

cc  hoc.o  –o hoc1

$ make                                        Еще раз

`hoc1′ is up to  date.        make видит, что это не нужно

$

Этап 2: Переменные и обработка ошибок

Следующий (небольшой) шаг заключается в добавлении hoc1 «памяти» для  создания hoc2. Дополнительная память представлена 26 переменными с именами от a до z. Этот шаг не отличается особым изяществом, но он полезен в качестве промежуточного и прост  в реализации. Введем также обработку некоторых ошибок. Что касается hoc1, его подход к синтаксическим ошибкам таков: выводится соответствующее сообщение, и программа завершается, способ  обработки арифметических ошибок (деление на ноль и т. д.) также заслуживает порицания:

$ hoc1 1/0

Floating exception – core  dumped

$

Изменения, которые требуется произвести, чтобы  добавить эти новые  возможности, невелики – приблизительно 35 строчек кода. Лексический  анализатор yylex должен распознавать буквы как переменные; а в грамматику необходимо добавить порождающее правило вида

expr:         VAR

| VAR  ‘=’  expr

Выражение может содержать присваивание; так возникают множественные присваивания, например

x = y = z = 0

Простейший способ  хранения значений переменных состоит  в созда нии  массива из  26  элементов; имя переменной, состоящее из  одной  буквы, может служить индексом массива. Но если  грамматика должна  обрабатывать и имена переменных, и значения  в одном  и том  же стеке, то  надо  проинформировать yacc о том,  что  его  стек  содержит объединение элементов типов  double  и  int, а не только double.  Такая операция осуществляется при помощи объявления %union, которое помещается в начале файла. Для установки стека в базовый тип (например,  double)  подходит #define или  typedef, но для  объединения типов  необходимо использовать механизм %union, потому что yacc проверяет непротиворечивость таких выражений, как $$=$2.

Представим грамматическую часть  hoc.y для hoc2:

$ cat  hoc.y

%{

double    mem[26];        /*  память для переменных  ‘a’..’z’  */

%}

%union {               /*  тип стека  */

double    val;        /*  фактическое  значение */ int  index;   /*  индекс  в mem[]  */

}

%token  <val>     NUMBER

%token  <index> VAR

%type    <val>     expr

%right    ‘=’

%left      ‘+’ ‘–’

%left      ‘*’ ‘/’

%left      UNARYMINUS

%%

list:      /*  ничего */

| list ‘\n’

| list expr  ‘\n’        { printf("\t%.8g\n", $2);   }

| list error ‘\n’   { yyerrok; }

;

expr:         NUMBER

| VAR                   { $$ = mem[$1];  }

| VAR  ‘=’  expr    { $$ = mem[$1]  = $3;  }

| expr  ‘+’ expr  { $$ = $1 + $3;  }

| expr  ‘–’ expr  { $$ = $1 – $3;  }

| expr  ‘*’ expr  { $$ = $1 * $3;  }

| expr  ‘/’  expr  { if  ($3  ==  0.0)

execerror("division by zero", "");

$$ = $1 / $3;  }

| ‘(‘ expr  ‘)’    { $$ = $2;  }

| ‘–’ expr    %prec  UNARYMINUS     { $$ = –$2;  }

;

%%

/*  конец грамматики  */

Объявление %union  сообщает, что  элементы  стека хранят или  double (число, обычный случай), или  int, который является индексом массива  mem.  В  объявления %token добавлен  индикатор типа. Объявление

%type указывает, что expr представляет собой член  объединения <val>, то есть принадлежит к типу  double. Информация о типе  позволяет yacc генерировать ссылку на соответствующий член объединения. Обрати те внимание на то, что = является правоассоциативным, в то время как другие операторы левоассоциативны.

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

Еще  одна  проверка отлавливает сигнал об исключительной ситуации при операции с плавающей точкой, который означает, что произошло

переполнение при  выполнении операции с плавающей точкой. Обработчик сигнала устанавливается в main.

Чтобы закончить с обработкой ошибок, добавим порождающее правило для error. В грамматике yacc слово  error является зарезервированным, оно предоставляет способ упреждения синтаксических ошибок и восстановления после них. Если происходит ошибка, yacc в конце кон цов   пытается   использовать  это   порождающее  правило,   признает ошибку грамматически «правильной» и тогда  устраняет ее. Действие yyerrok устанавливает в синтаксическом анализаторе (parser) флаг, который разрешает возврат в  состояние, поддающееся интерпретации синтаксическим  анализатором.  Устранение   ошибок  не  отличается простотой в любом синтаксическом анализаторе, поэтому знайте, что сейчас были  предприняты лишь самые элементарные меры. Возможности  yacc также были  рассмотрены очень поверхностно.

Действия в грамматике hoc2 не претерпели значительных изменений. Ниже приведена  функция main,  в которую была  добавлена  функция setjmp для  сохранения «чистого» состояния, из которого производится возобновление работы после  ошибки. Функция execerror вызывает соответствующую longjmp. (См. описание setjmp и longjmp в разделе 7.5.)

#include <signal.h>

#include  <setjmp.h> jmp_buf  begin;

main(argc,  argv)        /*  hoc2  */ char  *argv[];

{

int fpecatch();

progname  =  argv[0]; setjmp(begin); signal(SIGFPE,  fpecatch); yyparse();

}

execerror(s,  t) /*  восстановление после  ошибки  времени исполнения */ char  *s,  *t;

{

warning(s,  t); longjmp(begin,  0);

}

fpecatch()   /*  перехват исключений  в операциях с  плавающей  точкой */

{

execerror("floating  point exception", (char *)  0);

}

Было решено, что для удобства отладки execerror будет вызывать abort

(см.  abort(3)), создающую дамп  оперативной памяти, который может

быть  просмотрен с помощью adb или  sdb. Когда программа станет достаточно устойчивой, вызов abort будет заменен на longjmp.

Лексический анализатор hoc2 несколько отличается от hoc1. Введена дополнительная проверка на буквы в нижнем регистре, и, так как yylval теперь имеет  тип  union,  соответствующий член  объединения должен быть определен до выхода из yylex. Вот изменившиеся фрагменты:

yylex()               /*  hoc2 */

if  (c == ‘.’ ||  isdigit(c))  {     /*  число */ ungetc(c,  stdin);

scanf("%lf",  &yylval.val);

return NUMBER;

}

if (islower(c)) {

yylval.index = c  –  ‘a'; /*  только  ASCII  */ return  VAR;

}

Еще раз обратите внимание на различие типа лексемы (например, NUM– BER) и ее значения (например, 3.1416).

Теперь  покажем на  примере, как выглядят  нововведения hoc2: пере менные и обработка ошибок:

$ hoc2

x =  355

y =  113

355

113

p =  x/z                          z не определена и поэтому равна нулю

hoc2:  division by zero  near  line 4       Обработка ошибки

x/y

3.1415929

1e30 * 1e30                          Переполнение

hoc2:  floating point  exception near  line  5

Для  того чтобы обнаружить переполнение при выполнении операции с плавающей точкой на  PDP-11, требуются дополнительные средства, но на большинстве других машин hoc2 работает в том виде, как показано выше.

Упражнение 8.3. Добавьте возможность запоминать последнее вычисленное значение, чтобы  не приходилось заново вводить его в последовательности расчетов. В качестве решения можно предложить сделать его переменной, например p (от previous – предыдущий). ~

Упражнение 8.4. Измените hoc так, чтобы точку с запятой можно было использовать как символ, завершающий выражения, эквивалентный символу новой строки. ~

Этап 3: Произвольные имена переменных; встроенные функции

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

sin

cos

atan

exp

log

log10

sqrt

int

abs

Также добавлен оператор возведения в степень ^; он обладает наивысшим  приоритетом и является правоассоциативным.

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

PI

3.14159265358979323846

π

E

2.71828182845904523536

Основание  натурального  логарифма

GAMMA

0.57721566490153286060

Константа  Эйлера–Маскерони

DEG

57.29577951308232087680

Градусов  в  радиане

PHI

1.61803398874989484820

Золотое  отношение

Получается удобный калькулятор:

$ hoc3 1.5^2.3

2.5410306 exp(2.3*log(1.5)) 2.5410306

sin(PI/2)

1

atan(1)*DEG

45

Поведение программы в целом также было несколько улучшено. В hoc2 в случае присваивания x=expr происходило не только собственно при сваивание, но и вывод значения, поскольку все выражения выводятся:

$ hoc2

x =  2 * 3.14159

6.28318         Для присваивания переменной выводится значение

В hoc3 вводится различие между присваиваниями и выражениями; теперь значения печатаются только для выражений:

$ hoc3

x =  2 * 3.14159           Присваивание: значение не выводится

x                                      Выражение:

6.28318                   значение выводится

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

hoc.y            Грамматика, main,  yylex  (как и раньше)

hoc.h            Глобальные структуры данных

symbol.c      Функции таблицы символов: lookup,  install init.c         Встроенные функции и константы; init

math.c         Интерфейсы к математическим функциям: Sqrt, Log и т. д.

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

Вернемся ненадолго к make. Сначала посмотрим на код символьной таблицы. У символа есть имя, тип  (или  VAR, или  BLTIN) и значение. Если символ принадлежит к типу  VAR, то его значение имеет  тип double; если  же символ является встроенной функцией, то его значение – это указатель на функцию, которая возвращает double. Наличие такой информации необходимо в файлах hoc.y, symbol.c и init.c. Можно было бы просто создать три копии, но при этом слишком уж просто  сделать ошибку или  забыть  обновить один  из  экземпляров при  внесении  изменений. Вместо   этого   поместим  общую  информацию  в  заголовочный  файл hoc.h, а любой  файл, нуждающейся в такой информации, будет  включать  его в себя. (Суффикс .h присутствует традиционно, но ни одна  из программ не  принуждает к  использованию именно такого обозначения.) В makefile, кроме того, добавлены записи о зависимости файлов от hoc.h  – так, чтобы они компилировались, когда он изменяется.

$ cat  hoc.h

typedef struct  Symbol { /*  элемент таблицы  символов  */ char        *name;

short    type;      /*  VAR,  BLTIN,  UNDEF  */ union  {

double    val;               /*  if VAR  */

double    (*ptr)();      /*  if  BLTIN  */

} u;

struct Symbol    *next;    /*  чтобы связать  с другим  */

} Symbol;

Symbol    *install(),  *lookup();

$

Тип UNDEF  – это VAR, которому еще не присвоено значение.

Символы связаны вместе  в список при  помощи  поля next  структуры Symbol. Сам список является локальным по отношению к symbol.c; получить к нему  доступ  можно только через  функции lookup и install. Благодаря этому изменение таблицы символов (при необходимости) не составляет труда. (Однажды это было проделано.) Функция lookup просматривает список в поиске конкретного имени  и возвращает указатель на Symbol с указанным именем, если оно найдено, и ноль в противном случае. Таблица символов использует линейный поиск, который полностью подходит для нашего интерактивного калькулятора, т. к. поиск переменных происходит только во время синтаксического раз бора, но не во время выполнения. Функция install помещает переменную с соотнесенными ей типом и значением в начало списка. Функция emalloc вызывает malloc, стандартную функцию распределения памяти (malloc(3)), и проверяет результат. Эти три фунции являются содержимым  файла symbol.c. Файл y.tab.h порождается выполнением yacc  –d; он содержит директивы #define, которые yacc сгенерировал для таких лексем, как NUMBER, VAR, BLTIN и т. д.

$ cat  symbol.c

#include "hoc.h"

#include "y.tab.h"

static Symbol  *symlist = 0;    /*  таблица  символов: связанный  список */ Symbol  *lookup(s)     /*  поиск s  в таблице символов  */

char  *s;

{

Symbol *sp;

for  (sp  = symlist;  sp  !=  (Symbol *)  0;  sp  =  sp–>next)  if  (strcmp(sp–>name,   s) ==  0)

return  sp;

return 0;      /*  0 ==> не найдено */

}

Symbol  *install(s,  t, d)    /*  внести  s  в таблицу символов */ char  *s;

int t; double  d;

{

Symbol *sp;

char  *emalloc();

sp  = (Symbol *)  emalloc(sizeof(Symbol));

sp–>name  =  emalloc(strlen(s)+1);  /*  +1 для ‘\0′  */ strcpy(sp–>name,  s);

sp–>type  = t;

sp–>u.val = d;

sp–>next  = symlist; /*  поместить в начало списка  */ symlist = sp;

return sp;

}

char  *emalloc(n)       /*  проверить  значение,  возвращенное  malloc  */ unsigned  n;

{

char  *p,  *malloc();

p =  malloc(n); if (p  ==  0)

execerror("out  of  memory",  (char  *)  0); return p;

}

$

Файл init.c  содержит определения констант  (PI  и т. д.)  и указатели для  встроенных функций; они вносятся в таблицу символов функцией init, которую вызывает main.

$ cat  init.c

#include "hoc.h"

#include "y.tab.h"

#include <math.h>

extern double      Log(),  Log10(),  Exp(),  Sqrt(),  integer(); static  struct {         /*  Константы  */

char        *name; double    cval;

} consts[] = {

"PI",        3.14159265358979323846, "E",         2.71828182845904523536,

"GAMMA",  0.57721566490153286060,   /*  постоянная  Эйлера */

"DEG",  57.29577951308232087680,    /*  градусов/радиан  */ "PHI",      1.61803398874989484820,   /*  золотое  отношение  */ 0,    0

};

static struct {         /*  Встроенные  функции  */ char        *name;

double    (*func)();

}  builtins[]  = { "sin",    sin, "cos",    cos, "atan",  atan,

"log",   Log,        /*  проверка  аргумента */ "log10",  Log10,  /*  проверка  аргумента */ "exp",   Exp,        /*  проверка  аргумента */ "sqrt", Sqrt,      /*  проверка  аргумента */ "int",    integer,

"abs",    fabs, 0,  0

};

init()  /*  вставить  константы и встроенные функции  в  таблицу */

{

8.3. Этап 3: Произвольные имена переменных; встроенные функции                           287

int i; Symbol  *s;

for  (i = 0;  consts[i].name;  i++) install(consts[i].name,  VAR,  consts[i].cval);

for  (i = 0;  builtins[i].name;  i++)  {

s  =  install(builtins[i].name,  BLTIN,  0.0); s–>u.ptr =  builtins[i].func;

}

}

Данные хранятся в таблицах, а не вносятся в код, потому что таблицы легче  читать и  изменять. Таблицы объявляются как static,  поэтому они видны только внутри файла, а не во всей программе. К математическим функциям (Log, Sqrt и т. д.) мы вскоре вернемся.

Теперь,  когда  фундамент заложен,  можно  перейти к  изменениям грамматики, которые на нем построены.

$ cat  hoc.y

%{

#include "hoc.h"

extern   double    Pow();

%}

%union {

double    val;      /*  фактическое  значение */

Symbol  *sym;     /*  указатель  на таблицу символов  */

}

%token  <val>     NUMBER

%token  <sym>      VAR  BLTIN  UNDEF

%type    <val>     expr  asgn

%right    ‘=’

%left      ‘+’ ‘–’

%left      ‘*’ ‘/’

%left      UNARYMINUS

%right    ‘^’ /*  возведение в степень */

%%

list:      /*  ничего */

| list ‘\n’

| list asgn  ‘\n’

| list expr  ‘\n’        { printf("\t%.8g\n", $2);   }

| list error ‘\n’   { yyerrok; }

;

asgn:         VAR  ‘=’ expr  { $$=$1–>u.val=$3;  $1–>type =  VAR;  }

;

expr:         NUMBER

| VAR  { if ($1–>type  == UNDEF)

execerror("undefined variable",  $1–>name);

$$ =  $1–>u.val;  }

| asgn

| BLTIN  ‘(‘ expr  ‘)’   { $$ =  (*($1–>u.ptr))($3); }

| expr  ‘+’ expr  { $$ = $1 + $3;  }

%%

| expr  ‘–’ expr  { $$ = $1 – $3;  }

| expr  ‘*’ expr  { $$ = $1 * $3;  }

| expr  ‘/’  expr  { if  ($3  ==  0.0)

execerror("division by zero", "");

$$ = $1 /  $3;  }

| expr  ‘^’ expr  { $$ = Pow($1, $3);  }

| ‘(‘ expr  ‘)’    { $$ = $2;  }

| ‘–’ expr    %prec  UNARYMINUS     { $$ = –$2;  }

;

/*  конец грамматики  */

В грамматике вдобавок к expr появилось определение asgn (для присваивания); строка ввода, содержащая только

VAR  = expr

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

Изменился описатель стека %union: вместо ссылки на переменную по ее индексу в 26-элементной таблице используется указатель на  объект типа  Symbol. Заголовочный файл hoc.h содержит определение этого типа.

Лексический анализатор распознает имена переменных, просматривает  их  в таблице  символов и  решает, являются ли  они  переменными (VAR)  или  встроенными  функциями (BLTIN).  Значение, возвращаемое yylex, принадлежит одному  из  этих  типов; а переменные, определяемые  пользователем, и  предопределенные переменные (такие как  PI) имеют тип VAR.

Одним  из свойств переменной является то, присвоено ли ей значение, поэтому использование неопределенной переменной считается ошиб кой, о чем и сообщает yyparse. Проверка на наличие у переменной зна чения должна производиться грамматическим, а не лексическим ана лизатором. Когда  тип  VAR распознается лексически, его контекст нам  еще не известен; не хотелось бы слышать жалобы на то, что переменная  x не определена в то  время,  когда она  находится в разрешенном контексте, например в левой  части присваивания, как x=1.

Вот исправленная часть  функции yylex:

yylex()               /*  hoc3 */

if  (isalpha(c))  { Symbol  *s;

char  sbuf[100], *p = sbuf;

}

do {

*p++ = c;

} while  ((c=getchar()) !=  EOF  &&   isalnum(c)); ungetc(c,  stdin);

*p = ‘\0′;

if ((s=lookup(sbuf)) == 0)

s  =  install(sbuf,  UNDEF,  0.0); yylval.sym  = s;

return s–>type  == UNDEF  ? VAR  : s–>type;

В main добавлена одна  новая строка, которая вызывает функцию ини циализации init, чтобы та вставила встроенные функции и предопределенные имена (PI и т. д.) в таблицу символов.

main(argc,  argv)        /*  hoc3  */ char  *argv[];

{

int fpecatch();

progname  =  argv[0]; init(); setjmp(begin);

signal(SIGFPE,  fpecatch);

yyparse();

}

Осталось рассказать только о файле math.c. В некоторых математических функциях необходим интерфейс для обработки ошибок, например стандартная функция sqrt, не выдавая никаких сообщений об ошиб ках,  просто  возвращает ноль, если  ее аргумент  отрицателен. В коде файла math.c  есть  проверка  на  наличие ошибки, заимствованная  из раздела 2 справочного руководства по UNIX, см. главу 7. Это решение характеризуется большей надежностью и переносимостью, чем тесты, которые можно написать  самостоятельно,  т. к. ограниченность, присущая стандартным функциям,  лучше всего  отражена в «официальном» коде. Заголовочный файл math.h содержит объявления типов  для стандартных математических  функций.  Заголовочный файл errno.h содержит имена возможных ошибок.

$ cat  math.c

#include  <math.h>

#include  <errno.h> extern    int  errno; double    errcheck();

double  Log(x) double  x;

{

return errcheck(log(x), "log");

}

double  Log10(x) double  x;

{

return errcheck(log10(x), "log10");

}

double  Sqrt(x) double  x;

{

return errcheck(sqrt(x), "sqrt");

}

double  Exp(x) double  x;

{

return errcheck(exp(x), "exp");

}

double  Pow(x,  y) double  x,  y;

{

return errcheck(pow(x,y), "exponentiation");

}

double  integer(x) double  x;

{

return (double)(long)x;

}

double  errcheck(d,  s)    /*  проверка результата  обращения  к библиотеке*/ double  d;

char  *s;

{

if  (errno  ==  EDOM)  { errno  =  0;

execerror(s, "argument  out  of  domain");

}  else  if  (errno  ==  ERANGE)  { errno  =  0;

execerror(s, "result out  of  range");

}

return d;

}

$

Если   запустить  yacc  на  новой   грамматике,  появляется  интересное (и грамматически неправильное) диагностическое сообщение:

$ yacc  hoc.y

conflicts: 1 shift/reduce

$

Сообщение «shift/reduce» (сдвиг/свертка)  означает, что  грамматика

hoc3 неоднозначна: единственная строка ввода

x = 1

может   быть    синтаксически    проанализирована    двумя   способами (рис. 8.2).

Рис. 8.2. Варианты синтаксического анализа грамматики hoc3

Синтаксический анализатор может посчитать, что asgn  должно быть  сведено  к expr, а затем к list, следуя левому дереву  грамматического разбора, а может решить, что надо сразу  же использовать следующий

\n («сдвиг») и преобразовать все в list  без промежуточных правил, как на правом дереве. Сталкиваясь с такой неоднозначной ситуацией, yacc выбирает сдвиг, потому что  в  реально  существующих грамматиках

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

сообщения,  подобные приведенному  выше,  чтобы  не  сомневаться в том,  правильный ли сделан выбор.1 Если  запустить yacc с параметром

–v, будет  выведен значительного размера файл y.output, в котором даны пояснения об источнике конфликтов.

Упражнение 8.5. В своем нынешнем виде hoc3 разрешает операции, подобные

PI  = 3

Хорошо ли это? Как  изменить hoc3 так, чтобы запретить присваивание

«константам»? ~

Упражнение 8.6.  Добавьте встроенную  функцию atan2(y,x),  которая возвращала бы угол, тангенс которого равен y/x. Добавьте встроенную функцию rand(), которая  возвращала бы  случайное число  с плавающей точкой, равномерно распределенное по интервалу (0, 1).  Как  изменить грамматику таким образом, чтобы встроенные функции могли иметь различное количество аргументов? ~

1        Сообщение yacc «reduce/reduce conflict»  (конфликт свертка/свертка)  информирует о серьезной проблеме, чаще всего  оно является симптомом наличия ошибки в грамматике, а не внутренней неоднозначности.

Упражнение 8.7.  Как  добавить возможность выполнения команд без выхода из hoc (подобно ! в других UNIX-программах)? ~

Упражнение 8.8.  Исправьте код  в файле math.c  так, чтобы  использовать таблицу вместо множества по существу идентичных функций. ~

Снова о make

Программа для  hoc3 теперь занимает не один, а пять файлов, поэтому описание в makefile   тоже будет более сложным.

$ cat  makefile

YFLAGS  = –d         # вынуждает  создание y.tab.h

OBJS  = hoc.o  init.o math.o symbol.o  # аббревиатура

hoc3:      $(OBJS)

cc  $(OBJS)  –lm  –o  hoc3 hoc.o:    hoc.h

init.o symbol.o:        hoc.h  y.tab.h

pr:

@pr  hoc.y hoc.h init.c math.c  symbol.c  makefile

clean:

rm –f  $(OBJS) y.tab.[ch]

$

Строка YFLAGS =  –d добавляет параметр –d в командную строку yacc, генерируемую  make;  он  указывает  yacc,  что  требуется вывести  файл y.tab.h с директивами #define. Строка OBJS=… вводит краткую запись для конструкции, которая неоднократно будет использоваться в даль нейшем. Синтаксис отличается от синтаксиса переменных оболочки – обязательными являются  круглые  скобки.  Флаг  -lm вызывает  просмотр математической библиотеки в поиске математических функций.

Теперь  hoc3 зависит от четырех файлов .o, при этом некоторые из них  зависят от файлов .h. После  того как эти взаимозависимости установлены, make может сделать вывод  о том,  какая рекомпиляция необходима,  после  внесения изменений в любой  из  рассматриваемых файлов. Если  хочется просто  посмотреть, что  будет  делать make,  не  запуская процессы по-настоящему, введите

$ make  -n

С другой стороны, если  надо привести время создания файлов в согла сованное состояние, то параметр –t (touch – дотронуться) обновит их, не осуществляя рекомпиляции.

Обратите внимание  на  то, что  добавлено было  не  только множество взаимозависимостей исходных файлов, также были  введены различные сервисные программы, все они аккуратно собраны в одном  месте. По умолчанию make выполняет первое, что написано в makefile, но если

указать имя  элемента, который обозначает правило зависимостей (например, symbol.o или pr), то будет выполнен этот элемент. Пустая зависимость понимается как указание на то, что элемент никогда не быва ет «новейшим», поэтому при  каждом  требовании действие будет выполняться. Например,

$ make  pr  | lpr

выводит запрошенные  данные  на  построчно  печатающий  принтер. (Начальный символ @  в @pr подавляет отображение на экране команд, которые выполняет make.) А команда

$ make  clean

удаляет выходные файлы yacc и файлы .o.

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

Экскурс в lex

Программа lex создает лексические анализаторы (lexical analyzers) подобно  тому, как yacc  создает синтаксические (parsers):  программист пишет спецификацию лексических правил языка, используя регулярные выражения и фрагменты Си, которые должны выполняться, ког да найдена соответствующая строка; lex преобразовывает ее в распознаватель (recognizer). Программы lex и yacc взаимодействуют по тому же  самому  механизму,  что  и лексические анализаторы,  которые мы уже  писали. Не будем  обсуждать тонкости lex; этот  разговор вообще  заведен в  основном для того, чтобы  заинтересовать вас  и  побудить к дальнейшему изучению. Подробная информация по работе  с lex пред ставлена в томе 2B справочного руководства по UNIX.

Для  начала представим программу lex  из  файла lex.l;  она  заменит применявшуюся до этого момента функцию yylex.

$ cat  lex.l

%{

#include "hoc.h"

#include  "y.tab.h" extern  int  lineno;

%}

%%

[ \t]   { ; }     /*  пропускать пробелы  и  табуляции */ [0–9]+\.?|[0–9]*\.[0–9]+ {

sscanf(yytext,  "%lf",  &yylval.val);  return  NUMBER;  }

[a–zA–Z][a–zA–Z0–9]*  { Symbol  *s;

if ((s=lookup(yytext))  == 0)

s  =  install(yytext,  UNDEF,  0.0); yylval.sym  =  s;

return s–>type  == UNDEF  ? VAR  : s–>type; }

\n    { lineno++; return  ‘\n';  }

.  { return  yytext[0]; }               /*  все  остальное */

$

Каждое «правило» представляет собой регулярное выражение, оно похоже на выражения egrep или awk, за исключением того, что lex распознает  управляющие символы в  стиле  Си,  такие как \t и \n. Действие заключается в фигурные скобки. Правила  проверяются одно  за  другим, а конструкции типа  * и + соответствуют строке максимально возможной длины. Если  правило соответствует следующей части ввода, то действие выполняется. Строка ввода, для которой было найдено соответствие, доступна в строке lex, которая называется yytext.

Для того чтобы использовать lex, надо изменить makefile::

$ cat  makefile

YFLAGS  = –d

OBJS  = hoc.o  lex.o  init.o  math.o  symbol.o

hoc3:      $(OBJS)

cc  $(OBJS)  –lm  –ll  –o  hoc3 hoc.o:    hoc.h

lex.o  init.o  symbol.o:    hoc.h  y.tab.h

$

Программа make знает, как перейти от файла .l к надлежащему .o; все, что ей нужно от нас – это информация о зависимостях. (Еще надо добавить  lex-библиотеку –ll к списку,  просматриваемому cc, потому что распознаватель, генерируемый lex, не является автономным.1) Вывод  полностью автоматический и выглядит впечатляюще:

$ make

yacc  –d hoc.y

conflicts:  1  shift/reduce cc    –c  y.tab.c

rm y.tab.c

mv  y.tab.o  hoc.o

1        Пользователям свободно   распространяемых  UNIX-подобных операционных  систем необходимо проверить, каким вариантом lex они на самом  деле пользуются (это можно сделать, обратившись к справочному руководству по lex). Скорее  всего, окажется, что для построения лексических анализаторов в системе предлагается вариант программы, называемый flex. В этом случае в списке библиотек для  поиска необходимо заменить –ll на –lfl. – Примеч. науч. ред.

lex    lex.l

cc    –c  lex.yy.c rm  lex.yy.c

mv  lex.yy.o  lex.o cc    –c  init.c

cc    –c math.c

cc    –c symbol.c

cc  hoc.o  lex.o init.o  math.o  symbol.o  –lm –ll  –o hoc3

$

Если  изменился один  файл, то для создания новой  версии достаточно одной команды:

$ touch  lex.l                       Изменяет время изменения  lex.l

$ make

lex    lex.l

cc    –c  lex.yy.c rm  lex.yy.c

mv  lex.yy.o  lex.o

cc  hoc.o  lex.o init.o  math.o  symbol.o  –ll –lm  –o hoc3

$

Мы долго  спорили о том, считать ли lex отступлением от основной темы  и описать этот язык кратко или  же  представить его как основной инструмент лексического анализа для сложных языков. Каждый вариант имеет  свои «за»  и «против». Основная проблема, порождаемая применением lex (не считая того, что пользователю приходится учить еще один язык), состоит  в том,  что у него есть тенденция к снижению скорости выполнения и к созданию распознавателей (recognizers), которые  больше и медленнее, чем их эквиваленты на Си. К тому же  бывает  тяжело настроить ввод  lex, если выполняется что-то  необычное, например обработка ошибок или  ввод  из файлов. В контексте hoc это не так  уж  важно. Ограниченный объем  книги не позволяет привести описание версии анализатора на  основе  lex,  поэтому (к  сожалению) для  последующего лексического анализа  вернемся  к Си.  Самостоятельная реализация версии на lex будет хорошим упражнением.

Упражнение 8.9.  Сравните размеры двух версий hoc3. Подсказка: si–  ze(1). ~

Этап 4: Строим вычислительную машину

Мы двигаемся по направлению к hoc5, интерпретатору для  языка с управляющей логикой. Промежуточным этапом на этом  пути является создание hoc4, эта программа обеспечивает те же функции, что и hoc3, но реализована она в рамках интерпретатора hoc5. На самом  деле  hoc4 написана именно так, потому что в этом случае у нас есть две программы,  которые должны вести  себя  идентично, что удобно  для отладки. По  мере  синтаксического  анализа входных данных hoc4 генерирует

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

Простой компьютер –  это  машина со стековой  организацией:  когда встречается операнд, он помещается в стек (точнее, генерируется код для проталкивания его  в стек); большинство  операторов работают с элементами,  находящимися на  вершине стека. Например,  для обработки  присваивания

x = 2 * y

порождается следующий код:

constpush            Протолкнуть константу в стек

2                    … константу 2

varpush               Протолкнуть указатель на символьную таблицу в стек

y                    … для  переменной y

eval                     Оценить: заменить указатель значением

mul                      Перемножить два верхних элемента; произведение занимает их место

varpush               Протолкнуть указатель на символьную таблицу в стек

x                    … для  переменной x

assign              Сохранить значение в переменной, вытолкнуть указатель

pop                      Очистить значение вершины стека

STOP                           Конец последовательности команд

Когда выполняется код,  выражение вычисляется и результат сохраняется в x, как указано в комментариях. Заключительный вызов pop убирает значение из стека, потому что больше оно не потребуется.

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

Код таблицы символов для  hoc4 идентичен коду для  hoc3; инициализация в init.c и математические функции в math.c также не отличаются от предыдущей версии. Грамматика такая же, как в hoc3, а вот дейст вия совершенно другие. По существу, каждое действие порождает машинные команды и все сопутствующие им аргументы. Например, три позиции порождаются для  VAR  в выражении: команда varpush, указатель на таблицу символов для переменной и команда eval, которая при  исполнении заменит указатель на  таблицу символов значением. Код для  * (умножения) состоит  из одного  слова  mul, т. к. операнды уже  находятся в стеке.

$ cat  hoc.y

%{

#include "hoc.h"

#define code2(c1,c2)       code(c1);  code(c2)

#define code3(c1,c2,c3)  code(c1);  code(c2); code(c3)

%}

%union {

Symbol  *sym;     /*  указатель  на таблицу  символов */ Inst      *inst;    /*  машинная  команда */

}

%token  <sym>      NUMBER  VAR  BLTIN  UNDEF

%right    ‘=’

%left      ‘+’ ‘–’

%left      ‘*’ ‘/’

%left      UNARYMINUS

%right    ‘^’ /*  возведение в степень */

%%

list:      /*  ничего */

| list ‘\n’

| list asgn  ‘\n’    { code2(pop,  STOP);  return 1;  }

| list expr  ‘\n’    { code2(print, STOP); return 1;  }

| list error ‘\n’ { yyerrok;  }

;

asgn:         VAR  ‘=’ expr    {  code3(varpush,(Inst)$1,assign);  }

;

expr:         NUMBER           { code2(constpush,  (Inst)$1); }

| VAR                   { code3(varpush,  (Inst)$1, eval); }

| asgn

| BLTIN  ‘(‘ expr  ‘)’ { code2(bltin,  (Inst)$1–>u.ptr); }

| ‘(‘ expr  ‘)’

| expr  ‘+’ expr  { code(add);  }

| expr  ‘–’ expr  { code(sub);  }

| expr  ‘*’ expr  { code(mul);  }

| expr  ‘/’ expr  { code(div);  }

| expr  ‘^’ expr  { code(power);  }

| ‘–’ expr    %prec  UNARYMINUS     { code(negate); }

;

%%

/*  конец грамматики  */

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

Несколько изменена функция  main.  Синтаксический анализатор теперь возвращается после  каждого оператора или выражения; порождаемый им код выполняется. В конце файла yyparse возвращает ноль.

main(argc,  argv)        /*  hoc4  */ char  *argv[];

{

int fpecatch();

progname  =  argv[0]; init(); setjmp(begin);

signal(SIGFPE,  fpecatch);

for  (initcode();  yyparse();  initcode()) execute(prog);

return 0;

}

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

yylex()               /*  hoc4 */

if  (c == ‘.’ ||  isdigit(c))  {     /*  число */ double  d;

ungetc(c,  stdin); scanf("%lf",  &d);

yylval.sym  = install("",  NUMBER,  d);

return NUMBER;

}

Каждый  элемент стека интерпретатора  является либо  значением с плавающей  точкой,  либо  указателем на  элемент таблицы  символов; тип  данных стека – это объединение типов, перечисленных выше. Сама машина представляет собой массив указателей или на функции (mul и т. д.),  выполняющие операцию, или  на данные в таблице символов. В заголовочный файл hoc.h добавлены описанные структуры данных и объявления функций, чтобы они были видны в любом месте программы (при  необходимости). (Кстати, все изменения  были  помещены в один файл, а не в два.  Для больших программ лучше распределить заголовочную информацию по нескольким файлам – так, чтобы каждый файл присоединялся только тогда, когда это действительно необходимо.)

$ cat  hoc.h

typedef struct  Symbol { /*  элемент таблицы  символов  */ char        *name;

short    type;      /*  VAR,  BLTIN,  UNDEF  */ union  {

double    val;               /*  if VAR  */

double    (*ptr)();      /*  if BLTIN  */

} u;

struct Symbol    *next;    /*  связывает с другим */

} Symbol;

Symbol    *install(),  *lookup();

typedef union  Datum  {     /*  тип  стека  интерпретатора  */ double    val;

Symbol    *sym;

} Datum;

extern   Datum  pop();

typedef int (*Inst)();  /*  машинная  команда */

#define STOP         (Inst) 0

extern   Inst  prog[];

extern   eval(),  add(), sub(), mul(),  div(), negate(),  power(); extern    assign(), bltin(),  varpush(),  constpush(), print();

$

Функции, которые выполняют машинные команды и управляют стеком, хранятся в новом  файле, code.c. Его длина составляет около 150  строк, поэтому он будет приведен по частям.

$ cat  code.c

#include "hoc.h"

#include "y.tab.h"

#define NSTACK     256

static  Datum      stack[NSTACK];  /*  стек  */

static  Datum      *stackp;      /*  следующая  свободная  ячейка стека  */

#define NPROG        2000

Inst      prog[NPROG];        /*  машина  */

Inst      *progp;          /*  следующая  свободная ячейка  для генерирования кода */ Inst      *pc;               /*  счетчик команд во время исполнения */

initcode()   /*  инициализация  для генерирования кода  */

{

}

stackp   =  stack; progp =  prog;

Стек управляется вызовами функций push и pop:

push(d)         /*  втолкнуть  d в  стек  */ Datum  d;

{

if (stackp >=  &stack[NSTACK]) execerror("stack  overflow",  (char  *)  0);

*stackp++  = d;

}

Datum  pop()  /*  вытолкнуть  верхние элементы из стека  и  вернуть */

{

if (stackp <= stack)

execerror("stack  underflow", (char *)  0); return  *––stackp;

}

Машина генерируется во время синтаксического разбора посредством обращений  к функции code,  просто  помещающей команду в следую щую свободную ячейку массива prog. Она возвращает местоположение ячейки (которое не обрабатывается в hoc4).

Inst *code(f)      /*  установить одну  машинную  команду или операнд */ Inst  f;

{

Inst *oprogp = progp;

if (progp  >= &prog[NPROG])

execerror("program  too  big", (char *)  0);

*progp++ =  f; return  oprogp;

}

Работает машина просто; настолько просто, насколько мала функция,

«запускающая» машину, когда она создана:

execute(p)    /*  запустить  машину  */ Inst  *p;

{

for  (pc  =  p;  *pc  !=  STOP;  ) (*(*pc++))();

}

Каждый цикл выполняет функцию, на которую указывает машинная команда, на которую указывает счетчик команд pc, и увеличивает pc, чтобы  тот был  готов  к следующей команде. Машинная команда с кодом STOP завершает цикл. Некоторые машинные команды, такие как constpush  и varpush, также увеличивают pc, чтобы  пропустить аргументы, следующие за командой

constpush() /*  втолкнуть константу в стек  */

{

Datum  d;

d.val =  ((Symbol  *)*pc++)–>u.val; push(d);

}

varpush()     /*  втолкнуть переменную  в стек  */

{

Datum  d;

d.sym  =  (Symbol  *)(*pc++); push(d);

}

Оставшаяся часть  машины очень  проста. Например, все арифметические  операции по существу являются одинаковыми и были созданы редактированием одного прототипа. Представим функцию add:

add()             /*  сложить два верхних элемента стека  */

{

Datum  d1, d2;

d2 = pop(); d1  = pop();

d1.val += d2.val;

push(d1);

}

Остальные функции настолько же просты.

eval()         /*  оценить переменную  в стеке  */

{

Datum  d;

d = pop();

if (d.sym–>type  == UNDEF)

execerror("undefined  variable",  d.sym–>name); d.val = d.sym–>u.val;

push(d);

}

assign()      /*  присвоить верхнее значение следующему  */

{

Datum  d1,  d2; d1 =  pop();

d2 = pop();

if (d1.sym–>type  !=  VAR  &&   d1.sym–>type !=  UNDEF) execerror("assignment  to  non–variable",

d1.sym–>name);

d1.sym–>u.val  =  d2.val; d1.sym–>type  =  VAR; push(d2);

}

print()       /*  вытолкнуть  верхнее значение из стека  и  напечатать  его  */

{

Datum  d;

d  =  pop(); printf("\t%.8g\n",  d.val);

}

bltin()       /*  оценить встроенную  функцию  на вершине  стека  */

{

Datum  d;

d = pop();

d.val =  (*(double  (*)())(*pc++))(d.val); push(d);

}

Наибольшая сложность здесь  заключается в приведении типа  к bltin, которое указывает,  что  *pc следует привести к типу   «указатель  на функцию,  возвращающую double»,   и  что  функция  выполняется, с d.val в качестве аргумента.

Если все работает правильно, диагностика в eval и assign не нужна; мы оставили ее на случай, если ошибка в какой-либо программе вызывает сбой стека. Затраты времени и пространства незначительны по сравнению    с   полученным   преимуществом –   возможностью  обнаружить

ошибку, возникшую в результате неаккуратной модификации. (Авторам не раз случалось бывать в таких ситуациях.)

Благодаря способности Си манипулировать указателями на функции код получается компактным и производительным. В качестве альтернативы можно предложить сделать операторы константами и объединить семантические функции в большой оператор switch  в execute, отнеситесь к этому как к несложному упражнению.

Третий экскурс в make

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

В makefile было  внесено два усовершенствования. Первое основано на следующем наблюдении: несмотря на то что несколько файлов зависят от констант, определенных yacc в y.tab.h, нет необходимости рекомпилировать их до тех пор,  пока константы не изменятся, так как изменения кода  (написанного на Си) в hoc.y не влияют ни на что другое. В новой версии makefile файлы .o зависят от нового файла x.tab.h, который обновляется только при  изменении содержимого y.tab.h. Второе  улуч шение  заключается  в  том,  что  правило  для   pr  (печать  исходного файла) теперь зависит от исходных файлов, так что выводятся только измененные файлы.

Первое новшество значительно ускоряет  сборку  больших программ, если  их грамматика статична, а семантика – нет (обычная ситуация). Второе же изменение экономит горы бумаги.

Вот новый вариант makefile для hoc4:

YFLAGS  = –d

OBJS  = hoc.o  code.o init.o math.o symbol.o

hoc4:      $(OBJS)

cc  $(OBJS)  –lm –o hoc4

hoc.o  code.o  init.o  symbol.o:      hoc.h code.o  init.o  symbol.o:  x.tab.h x.tab.h:  y.tab.h

–cmp  –s  x.tab.h y.tab.h || cp y.tab.h x.tab.h

pr: hoc.y  hoc.h  code.c  init.c math.c  symbol.c

@pr  $?

@touch pr

clean:

rm –f  $(OBJS) [xy].tab.[ch]

Знак «–» перед  cmp указывает, что make должна выполняться, даже если cmp закончилась неудачно; благодаря этому  процесс работает, даже если x.tab.h не существует. (Команда cmp с параметром –s не порождает вывода, а устанавливает код завершения.) Символ $? раскрывается в список элементов правила, которые устарели. К сожалению, соглашение об обозначениях, принятое в make, мало  похоже на подобное  согла шение в оболочке.

Проиллюстрируем описанное на примере; будем считать все файлы новыми. Тогда

$ touch  hoc.y                     Изменить дату hoc.y

$ make

yacc  –d hoc.y

conflicts:  1  shift/reduce cc    –c  y.tab.c

rm y.tab.c

mv  y.tab.o  hoc.o

cmp  –s  x.tab.h y.tab.h || cp y.tab.h x.tab.h

cc  hoc.o  code.o  init.o math.o  symbol.o  –lm –o hoc4

$ make  -n  pr                          Вывести изменившиеся файлы

pr  hoc.y touch  pr

$

Обратите внимание на то, что рекомпилирован был только hoc.y, т. к.

файл y.tab.h не изменился.

Упражнение 8.10.  Сделайте размеры stack и prog динамическими, чтобы hoc4 никогда не выходил за границы отведенной ему области памяти (если при обращении к malloc память может быть получена). ~

Упражнение 8.11.  Измените hoc4 так, чтобы вместо  вызова функции в execute  использовался switch для  типа  операции. Сравните количество строк исходного текста и скорость исполнения двух версий. Предположите, какую из них было бы легче  расширять и поддерживать? ~

Этап 5: Управляющая логика и операторы отношения

Эта версия, hoc5, использует преимущества нового  интерпретатора. В ней  появляются  операторы if–else и while,  подобные  операторам  Си, есть возможность группировки операторов при помощи фигурных скобок, предусмотрен оператор print. В hoc5 включен полный набор опера торов  отношения (>, >= и т. д.), а также операторы И и ИЛИ  (&& и ||). (Последние два  оператора не  гарантируют  оценку выражений слева  направо, имеющуюся в активе Си; они  оценивают оба условия, даже если в этом нет необходимости.)

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

$ cat  hoc.y

%{

#include "hoc.h"

#define code2(c1,c2)       code(c1);  code(c2)

#define code3(c1,c2,c3)  code(c1);  code(c2); code(c3)

%}

%union {

Symbol  *sym;     /*  указатель  на таблицу  символов */ Inst      *inst;    /*  машинная  команда */

}

%token  <sym>      NUMBER PRINT    VAR  BLTIN  UNDEF  WHILE  IF  ELSE

%type    <inst>    stmt  asgn  expr  stmtlist cond while  if  end

%right    ‘=’

%left      OR

%left      AND

%left      GT  GE  LT  LE  EQ  NE

%left      ‘+’ ‘–’

%left      ‘*’ ‘/’

%left      UNARYMINUS   NOT

%right    ‘^’

%%

list:      /*  ничего */

| list ‘\n’

| list asgn  ‘\n’    { code2(pop,  STOP);  return 1;  }

| list stmt  ‘\n’    { code(STOP); return 1;  }

| list expr  ‘\n’    { code2(print, STOP); return 1;  }

| list error ‘\n’ { yyerrok;  }

;

asgn:         VAR  ‘=’ expr    { $$=$3;  code3(varpush,(Inst)$1,assign);  }

;

stmt:         expr           { code(pop);  }

| PRINT  expr        { code(prexpr); $$ = $2;  }

| while  cond stmt  end {

($1)[1] = (Inst)$3; /*  тело цикла */

($1)[2] = (Inst)$4; }     /*  конец,  если  условие cond ложно  */

| if cond stmt  end {        /*  if без  части  else */ ($1)[1] =  (Inst)$3; /*  часть  then  */

($1)[3] = (Inst)$4; }     /*  конец,  если  условие cond ложно  */

| if cond stmt  end ELSE  stmt  end  {    /*  if с частью else */ ($1)[1] = (Inst)$3; /*  часть  then  */

($1)[2] = (Inst)$6; /*  часть  else */

($1)[3] = (Inst)$7; }     /*  конец,  если  условие cond ложно  */

| ‘{‘ stmtlist  ‘}’  { $$ = $2;  }

;

cond:         ‘(‘  expr  ‘)’ { code(STOP); $$ = $2;  }

;

while:      WHILE  { $$ = code3(whilecode,  STOP,  STOP);  }

;

if:   IF       { $$=code(ifcode);  code3(STOP, STOP,  STOP); }

;

end:            /*  ничего */          { code(STOP); $$ = progp;  }

;

stmtlist: /*  ничего */          { $$ = progp;  }

| stmtlist ‘\n’

| stmtlist stmt

;

expr:         NUMBER           { $$ = code2(constpush,  (Inst)$1);  }

| VAR                   { $$ = code3(varpush, (Inst)$1,  eval);  }

| asgn

| BLTIN  ‘(‘ expr  ‘)’

{ $$ = $3;  code2(bltin,(Inst)$1–>u.ptr);  }

| ‘(‘ expr  ‘)’    { $$ = $2;  }

| expr  ‘+’ expr  { code(add);  }

| expr  ‘–’ expr  { code(sub);  }

| expr  ‘*’ expr  { code(mul);  }

| expr  ‘/’ expr  { code(div);  }

| expr  ‘^’ expr  { code (power); }

| ‘–’ expr    %prec  UNARYMINUS     { $$ = $2;  code(negate);  }

| expr  GT  expr    { code(gt); }

| expr  GE  expr    { code(ge); }

| expr  LT  expr    { code(lt);  }

| expr  LE  expr    { code(le); }

| expr  EQ  expr    { code(eq); }

| expr  NE  expr    { code(ne); }

| expr  AND  expr  { code(and);  }

| expr  OR  expr    { code(or); }

| NOT  expr    { $$ = $2;  code(not); }

;

%%

В этой  грамматике пять конфликтов «сдвиг/свертка», все они  подобны упоминавшемуся в разделе, посвященном hoc3.

Обратите внимание на то, что команды STOP теперь порождаются в нескольких местах, чтобы завершить последовательность; как и раньше, progp  – это местоположение следующей машинной команды, которая будет  сгенерирована. При  выполнении эти  команды  STOP  завершают цикл в execute. Порождающее правило для  end на самом  деле является подпрограммой, вызываемой из различных мест, генерирующей STOP и возвращающей местоположение машинной команды, которая следует за ним.

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

while:   WHILE

Однако в то же время резервируются две последующие позиции в стеке  машины, они будут  заполнены позже. Затем генерируется код, пред ставляющий собой  выражение,  которое составляет  условную часть  while. Значение, возвращаемое cond, – это начало кода для условия.

После  того как распознан весь оператор while, две дополнительные позиции, которые были  зарезервированы после  команды whilecode,  заполняются адресами тела  цикла и оператора, следующего за циклом. (Затем будет генерироваться код для этого оператора.)

| while  cond stmt  end {

($1)[1] = (Inst)$3; /*  тело цикла */

($1)[2] = (Inst)$4;   } /*  конец,  если условие  cond ложно  */

$1 –  это  то  место  в  машине, где  хранится  whilecode; следовательно,

($1)[1] и ($1)[2] – это две следующие позиции.

Прояснить все помогает рис.  8.3.

Рис. 8.3. Порождение кода для while

Что касается if, все происходит аналогично, за исключением того, что резервируются три ячейки, для частей then и else и для оператора, кото рый следует за if. Вскоре мы еще поговорим о том, как все это работает.

В данной версии лексический анализатор становится более длинным, в основном для того, чтобы «вылавливать» дополнительные операторы:

yylex()               /*  hoc5 */

switch  (c) {

case  ‘>':      return  follow(‘=’,  GE,  GT); case  ‘<‘:      return  follow(‘=’,  LE,  LT);

case  ‘=':      return  follow(‘=’, EQ,  ‘=’); case  ‘!':      return  follow(‘=’, NE,  NOT); case  ‘|':      return  follow(‘|’,  OR,  ‘|’); case  ‘&':      return  follow(‘&’, AND,  ‘&’); case  ‘\n':    lineno++;  return  ‘\n'; default:        return  c;

}

}

Функция follow смотрит на один символ вперед и помещает его обрат но в поток ввода при помощи ungetc, если это не то, что ожидалось.

follow(expect,  ifyes, ifno)    /*  смотрит на  следующий  символ  в поиске >=, и  т.п.  */

{

int c = getchar();

if (c  ==  expect) return  ifyes;

ungetc(c, stdin);

return ifno;

}

В новом hoc.h содержится больше объявлений функций, например для  всех отношений, но в остальном он похож на hoc.h из hoc4. Вот его последние несколько строк:

$ cat  hoc.h

typedef int (*Inst)();  /*  машинная  команда */

#define STOP         (Inst) 0

extern   Inst  prog[],  *progp,  *code();

extern   eval(),  add(), sub(), mul(),  div(), negate(),  power(); extern    assign(), bltin(),  varpush(),  constpush(), print(); extern    prexpr();

extern   gt(), lt(), eq(),  ge(), le(),  ne(), and(),  or(), not();

extern  ifcode(),  whilecode();

$

Большая часть code.c также не отличается от версии hoc4, хотя в него и включено множество очевидных новых функций для обработки операторов  отношения. Функция le (less  than or equal to – меньше или  равно) представляет собой типичный пример:

le()

{

}

Datum  d1,  d2; d2 =  pop();

d1 = pop();

d1.val =  (double)(d1.val  <= d2.val); push(d1);

А вот  две  функции, whilecode  и  ifcode, нельзя  назвать очевидными. Для того чтобы  понять их, необходимо осознать, что execute  продвигается вдоль  последовательности команд, пока  не встретит STOP, а затем завершается возвратом. Генерирование кода  по ходу  синтаксического разбора организовано так, чтобы  каждая последовательность машинных  команд, которая должна быть  обработана одним вызовом execute, завершалась STOP. Тело while и условие, части then и else оператора if, все  они  обрабатываются рекурсивными  вызовами  execute,  которые возвращаются на родительский уровень после  того, как закончат выполнение своей  задачи. Контроль над  этими рекурсивными задачами осуществляется функциями whilecode и ifcode, которые соответствуют операторам while и if.

whilecode()

{

Datum  d;

Inst *savepc  = pc;    /*  тело цикла */

execute(savepc+2);    /*  условие  */ d  =  pop();

while  (d.val) {

execute(*((Inst  **)(savepc)));    /*  тело */ execute(savepc+2);

d = pop();

}

pc = *((Inst **)(savepc+1));    /*  следующий  оператор */

}

Ранее упоминалось, что  за  операцией whilecode  следует указатель на тело цикла, указатель на следующий оператор и затем – начало услов ной части. Когда  вызывается whilecode, счетчик команд pc уже  увеличен и указывает на указатель тела  цикла. Тогда pc+1 указывает на следующий оператор, а pc+2 – на условие.

Функция ifcode очень  похожа на whilecode; в этом  случае pc первоначально указывает на часть  then, pc+1 – на часть  else, pc+2 – на следующий  оператор, а pc+3 – на условие.

ifcode()

{

Datum  d;

Inst *savepc  = pc;    /*  часть  then  */

execute(savepc+3);    /*  условие  */ d  =  pop();

if (d.val)

execute(*((Inst  **)(savepc)));

else if (*((Inst  **)(savepc+1))) /*  часть  else? */ execute(*((Inst  **)(savepc+1)));

pc = *((Inst **)(savepc+2));         /*  следующий  оператор */

}

Код инициализации в init.c также несколько увеличился за счет таблицы ключевых слов, эти слова хранятся в таблице символов вместе  со всем остальным ее содержимым:

$ cat  init.c

static struct {         /*  Ключевые  слова */ char        *name;

int kval;

}  keywords[]  =  { "if",             IF, "else",         ELSE, "while",        WHILE, "print",        PRINT, 0,           0,

};

В init добавлен еще один цикл для размещения ключевых слов.

for  (i = 0;  keywords[i].name;  i++) install(keywords[i].name,  keywords[i].kval,  0.0);

Управление таблицей символов не изменяется; в code.c  есть функция prexpr, которая вызывается, когда выполняется оператор вида print ex5 pr.

prexpr()      /*  вывести  числовое значение */

{

Datum  d;

d  =  pop(); printf("%.8g\n",  d.val);

}

Это не функция print, которая автоматически вызывается для  печати окончательного  результата вычислений; та  выталкивает  данные из стека и добавляет в вывод  знак табуляции.

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

Упражнение 8.12.  Измените hoc5 так, чтобы выводить генерируемую им машину в пригодном для чтения виде (для  отладки). ~

Упражнение 8.13.  Добавьте операторы присваивания из Си, такие как

+=, *= и т. д.,  и операторы инкремента и декремента ++ и ––. Измените

&& и || так, чтобы  они поддерживали оценивание слева  направо и своевременное завершение (без оценки второго операнда, если  она не важна), как в Си. ~

Упражнение 8.14.  Добавьте в hoc5 оператор for,  подобный оператору Си. Добавьте break и continue. ~

Упражнение 8.15.  Как  бы вы изменили грамматику или  лексический анализатор (или оба) hoc5 для  того, чтобы  он меньше заботился о расположении  символов новой  строки? Как  добавить точку с запятой, чтобы  она стала синонимом символа новой  строки? Как  ввести согла шение об обозначениях для  комментария?  Какой следует использовать синтаксис? ~

Упражнение 8.16.  Добавьте в hoc5 обработку  прерываний так, чтобы  вышедший из-под контроля расчет можно было  остановить, не потеряв при этом уже подсчитанные значения переменных. ~

Упражнение 8.17.  Неудобно создавать программу в файле, запускать ее, а затем редактировать файл для того, чтобы внести тривиальное изменение. Измените hoc5 так, чтобы  в нем  была  команда редактирования, которая перемещала бы пользователя в редактор, в котором уже  была  бы прочитана копия его hoc-программы. Подсказка: подумайте о машинной команде text. ~

Этап 6: Функции и процедуры; ввод−вывод

Заключительным этапом эволюции hoc (по крайней мере в этой книге) является значительное расширение его функциональности – введение функций и процедур. Добавлена также возможность печати символьных строк и чисел  и чтения значений с устройства стандартного ввода. Кроме того, hoc6 принимает имена файлов в качестве аргументов, в том числе имя «–» для стандартного ввода. Вместе  эти  изменения состав ляют 235  добавочных строк кода,  которых в результате получается 810, но зато hoc из калькулятора превращается в язык программирования. Не будем  приводить все добавленные строки в этой  главе; в приложении 3  представлен весь  листинг целиком,  там  можно увидеть, как все части согласуются друг с другом.

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

$ cat  fib

proc  fib() { a = 0

b = 1

while  (b  <  $1)  { print  b

c = b

b = a+b a = c

}

print "\n"

}

$ hoc6 fib fib(1000)

1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987

Этот пример иллюстрирует использование файлов: имя «–» принадлежит стандартному вводу.

А вот функция, подсчитывающая факториал:

$ cat  fac

func  fac() {

if ($1  <= 0)  return 1 else return $1 * fac($1–1)

}

$ hoc6 fac  fac(0)

fac(7) fac(10)

1

5040

3628800

Внутри функции и процедуры (как и в  оболочке) обращение к аргу ментам выглядит  как $1,  но  разрешено и присваивать им  значения. Функции и процедуры рекурсивны, но локальными переменными являются  только  аргументы; все  остальные переменные –  глобальные, то есть они доступны в любой точке программы.

Функции и процедуры в hoc различаются, потому что это обеспечивает наличие  дополнительных проверок, которые облегчают  реализацию стека. Очень  легко забыть return или, наоборот, добавить лишнее выражение и испортить стек.

Чтобы превратить hoc5 в hoc6, в грамматику внесено  значительное количество изменений, но они локализованы. Необходимы новые  лексемы и нетерминальные символы, а в объявлении %union появляется новый член, который обрабатывает счетчик аргументов:

$ cat  hoc.y

%union {

Symbol  *sym;     /*  указатель  на таблицу  символов */ Inst      *inst;    /*  машинная  команда */

int narg;          /*  количество аргументов */

}

%token

<sym>

NUMBER STRING    PRINT  VAR  BLTIN  UNDEF  WHILE  IF  ELSE

%token

<sym>

FUNCTION  PROCEDURE  RETURN  FUNC  PROC  READ

%token

<narg>

ARG


%type

<inst>

expr  stmt  asgn  prlist  stmtlist

%type

<inst>

cond while if begin  end

%type

<sym>

procname

%type

<narg>

arglist

list:         /*  ничего  */

| list ‘\n’

| list defn  ‘\n’

| list asgn  ‘\n’    { code2(pop,  STOP);  return 1;  }

| list stmt  ‘\n’    { code(STOP); return 1;  }

| list expr  ‘\n’    { code2(print, STOP); return 1;  }

| list error ‘\n’ { yyerrok;  }

;

asgn:         VAR  ‘=’ expr  {  code3(varpush,(Inst)$1,assign); $$=$3; }

| ARG  ‘=’  expr

{ defnonly("$");  code2(argassign,(Inst)$1);  $$=$3;}

;

stmt:         expr    { code(pop); }

| RETURN  { defnonly("return"); code(procret); }

| RETURN  expr

{ defnonly("return");  $$=$2;  code(funcret); }

| PROCEDURE  begin  ‘(‘  arglist ‘)’

{ $$ = $2;  code3(call, (Inst)$1,  (Inst)$4);  }

| PRINT  prlist  { $$ = $2;  }

expr:         NUMBER   { $$ = code2(constpush, (Inst)$1);  }

| VAR           { $$ = code3(varpush, (Inst)$1, eval);  }

| ARG           { defnonly("$"); $$ = code2(arg,  (Inst)$1); }

| asgn

| FUNCTION  begin  ‘(‘ arglist  ‘)’

{ $$ = $2;  code3(call,(Inst)$1,(Inst)$4);  }

| READ  ‘(‘ VAR  ‘)’ { $$ = code2(varread,  (Inst)$3); }

begin:      /*  ничего */          { $$ = progp;  }

;

prlist:    expr                   { code(prexpr);  }

| STRING                   { $$ = code2(prstr,  (Inst)$1); }

| prlist ‘,’ expr      { code(prexpr);  }

| prlist ‘,’ STRING  { code2(prstr,  (Inst)$3); }

;

defn:         FUNC  procname { $2–>type=FUNCTION;  indef=1;  }

‘(‘ ‘)’ stmt  { code(procret); define($2);  indef=0;  }

| PROC  procname  { $2–>type=PROCEDURE;  indef=1; }

‘(‘ ‘)’ stmt  { code(procret); define($2);  indef=0;  }

; procname:  VAR

| FUNCTION

| PROCEDURE

;

arglist:  /*  ничего */          { $$ = 0;  }

| expr                   { $$ = 1;  }

%%

| arglist ‘,’ expr    { $$ = $1 + 1;  }

;

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

Правила для   defn  вводят новое  свойство yacc,  вложенное  действие. Можно вставлять  действие  в середину правила –  так, чтобы  оно  выполнялось во время распознавания этого правила. Данное свойство использовано нами для  того, чтобы  фиксировать факт нахождения в определении процедуры или  функции.  (В качестве альтернативы можно создать новый символ, аналогичный begin, который опознавался бы в нужное время.) Функция defnonly выводит предупреждение, если конструкция встречается вне  определения функции или  процедуры, где ее не должно быть. Часто возникает выбор: выявлять ли ошибки синтаксически или  семантически; мы  уже  сталкивались с такой ситуацией  при  обработке неопределенных переменных.  Функция defnonly служит хорошим примером того,  что семантическая проверка может быть легче  синтаксической.

defnonly(s) /*  предупреждает, если есть  недопустимое  определение*/ char  *s;

{

if (!indef)

execerror(s, "used  outside definition");

}

Переменная indef  объявляется  в  hoc.y  и  определяется  в  описании действия для defn.

Лексический анализатор дополнен проверкой строк в кавычках и аргументов – символом $, за которым следует число. Управляющие символы, такие как \n, интерпретируются в строках функцией backslash.

yylex()               /*  hoc6 */

if (c  ==  ‘$’)  {  /*  аргумент?  */ int  n  =  0;

while  (isdigit(c=getc(fin))) n  =  10  *  n  +  c  –  ‘0’;

ungetc(c,  fin);

if (n  == 0)

execerror("strange  $…",  (char  *)0); yylval.narg  =  n;

return ARG;

}

if (c  == ‘"’)  {  /*  строка  в  кавычках  */ char  sbuf[100],  *p,  *emalloc();

for  (p  = sbuf;  (c=getc(fin))  !=  ‘"'; p++) { if (c  == ‘\n’  || c  == EOF)

execerror("missing  quote",  ""); if  (p  >=  sbuf  +  sizeof(sbuf)  –  1)  {

*p = ‘\0′;

execerror("string  too  long", sbuf);

}

*p = backslash(c);

}

backslash(c)        /*  интерпретировать  следующий  символ с \ */ int c;

{

char  *index();    /*  `strchr()’  в некоторых  системах */ static  char  transtab[]  =  "b\bf\fn\nr\rt\t";

if (c  !=  ‘\\’) return  c;

c = getc(fin);

if  (islower(c)  &&  index(transtab,  c)) return  index(transtab,  c)[1];

return c;

}

Лексический анализатор, написан ли он на Си или  же при помощи такого  генератора программ, как lex, является примером конечного ав5 томата. Наша специальная версия на  Си стала очень  сложной; для других задач lex, вероятно, подошел бы лучше, как из-за размера исходного кода, так и из-за простоты изменения.

Большая часть  других изменений относится к code.c, несколько имен  функций введено в hoc.h. Машина осталась прежней, только добавился второй стек для  отслеживания вызовов вложенных функций и процедур. (Лучше ввести второй стек, чем забивать уже существующий.) Вот начало code.c:

$ cat  code.c

#define NPROG        2000

Inst      prog[NPROG];        /*  машина  */

Inst     *progp;                 /*  следующая  свободная ячейка  для генерирования кода

*/

Inst      *pc;               /*  счетчик  команд во время исполнения */ Inst        *progbase  = prog;  /*  запуск  текущей  подпрограммы  */ int  returning;         /*  1,  если встречен  оператор return*/

typedef struct  Frame {   /*  стековый фрейм  вызова  функции/процедуры  */ Symbol  *sp;        /*  элемент таблицы  символов */

Inst      *retpc; /*  место  возобновления после возврата  */ Datum    *argn;    /*  n–й аргумент  в стеке  */

int nargs;        /*  количество аргументов */

} Frame;

#define NFRAME     100

Frame    frame[NFRAME];

Frame    *fp;               /*  указатель  фрейма  */

initcode() {

progp =  progbase; stackp  =  stack;

fp  =  frame; returning  =  0;

}

$

Таблица символов теперь хранит указатели на процедуры и функции, а также на строки для печати, поэтому сделано расширение типа  union в hoc.h:

$ cat  hoc.h

typedef struct  Symbol {         /*  элемент таблицы  символов */ char        *name;

short    type;

union  {

double    val;               /*  VAR  */ double    (*ptr)();      /*  BLTIN  */

int (**defn)();           /*  FUNCTION,  PROCEDURE  */ char        *str;             /*  STRING  */

} u;

struct Symbol    *next;    /*  связать  с другим */

} Symbol;

$

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

define(sp)   /*  вставить  функцию/процедуру  в таблицу  символов */ Symbol *sp;

{

sp–>u.defn  = progbase;       /*  начало кода */

progbase  = progp;      /*  следующий  код начинается  здесь  */

}

Когда  функция или  процедура вызывается во время исполнения, все аргументы уже сосчитаны и помещены в стек (первый аргумент лежит глубже всего). За кодом  машинной команды call следует указатель на таблицу  символов  и  количество аргументов.  Формируется  элемент структуры Frame,  содержащий всю  полезную информацию  о  подпрограмме – ее вхождение в таблицу символов, место, куда  она возвраща-

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

call()        /*  вызвать  функцию  */

{

Symbol *sp  = (Symbol *)pc[0];  /*  элемент таблицы           */

/*  символов для  функции  */

if (fp++  >= &frame[NFRAME–1])

execerror(sp–>name,  "call  nested  too  deeply"); fp–>sp  = sp;

fp–>nargs  =  (int)pc[1]; fp–>retpc  =  pc  +  2;

fp–>argn  = stackp  – 1;               /*  последний  аргумент */

execute(sp–>u.defn); returning  =  0;

}

Эта структура проиллюстрирована на рис.  8.4.

Рис. 8.4. Структуры данных для  вызова процедуры

Со временем вызванная подпрограмма возвратится, при  выполнении

procret или funcret:

funcret()    /*  возврат  из функции  */

{

Datum  d;

if (fp–>sp–>type  ==  PROCEDURE) execerror(fp–>sp–>name,  "(proc) returns  value");

d = pop();  /*  сохранить возвращенное функцией  значение*/

ret(); push(d);

}

procret()    /*  возврат  из процедуры  */

{

if  (fp–>sp–>type  ==  FUNCTION) execerror(fp–>sp–>name,

"(func) returns no value");

ret();

}

Функция ret выталкивает аргументы из стека, восстанавливает указатель фрейма fp и устанавливает счетчик команд.

ret()         /*  общий  возврат  из процедуры  или функции  */

{

int i;

for  (i = 0;  i < fp–>nargs; i++)

pop();        /*  вытолкнуть  аргументы  */ pc  = (Inst  *)fp–>retpc;

––fp;

returning  = 1;

}

В нескольких подпрограммах интерпретатора необходимо произвести незначительные   изменения  для  обработки ситуации,  когда   return встречается во вложенном операторе. Это решается (не очень  красиво, но вполне адекватно) при помощи флага, названного returning, принимающего  значение  «истина»,   если   был   встречен  оператор  return. Функции  ifcode, whilecode  и execute  завершаются раньше, если  уста новлен returning; call переустанавливает его в 0.

ifcode()

{

Datum  d;

Inst *savepc  = pc;    /*  часть  then  */

execute(savepc+3);    /*  условие  */ d  =  pop();

if (d.val)

execute(*((Inst **)(savepc)));

else if (*((Inst  **)(savepc+1))) /*  часть  else? */ execute(*((Inst  **)(savepc+1)));

if (!returning)

pc = *((Inst  **)(savepc+2)); /*  следующий  оператор */

}

whilecode()

{

Datum  d;

Inst *savepc  = pc;

execute(savepc+2);    /*  условие  */ d  =  pop();

while  (d.val) {

execute(*((Inst  **)(savepc)));    /*  body */ if  (returning)

break;

execute(savepc+2);    /*  условие  */ d  =  pop();

}

if (!returning)

pc = *((Inst  **)(savepc+1)); /*  следующий  оператор */

}

execute(p) Inst *p;

{

for  (pc  = p;  *pc  !=  STOP   &&  !returning;  ) (*((++pc)[–1]))();

}

Аргументы для  использования или присваивания выбираются из  памяти при  помощи функции getarg,  которая осуществляет  арифметические операции над стеком:

double  *getarg()      /*  возвращает указатель  на  аргумент */

{

int  nargs  =  (int)  *pc++; if  (nargs  >  fp–>nargs)

execerror(fp–>sp–>name,  "not  enough arguments"); return &fp–>argn[nargs  –  fp–>nargs].val;

}

arg()    /*  протолкнуть аргумент в стек  */

{

Datum  d;

d.val  =  *getarg(); push(d);

}

argassign()        /*  сохранить вершину  стека  в  аргументе */

{

Datum  d;

d = pop();

push(d);        /*  оставить  значение в стеке  */

*getarg() = d.val;

}

Печать строк и чисел  осуществляется функциями prstr и prexpr.

prstr()       /*  вывести  строковое значение */

{

printf("%s", (char *)  *pc++);

}

prexpr()      /*  вывести  числовое значение */

{

Datum  d;

d = pop();

printf("%.8g ", d.val);

}

Переменные считывает функция varread. Она возвращает 0 при  дости жении конца файла; в остальных случаях она возвращает 1 и устанавливает указанные переменные.

varread()    /*  читать  в переменную  */

{

Datum  d;

extern FILE *fin;

Symbol  *var  =  (Symbol  *)  *pc++; Again:

switch  (fscanf(fin,  "%lf",  &var–>u.val)) { case  EOF:

if (moreinput())

goto  Again;

d.val  =  var–>u.val  =  0.0; break;

case  0:

execerror("non–number  read  into",  var–>name); break;

default:

d.val = 1.0; break;

}

var–>type  =  VAR; push(d);

}

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

Мы подходим к завершению разработки hoc. Для сравнения приведем количество непустых строк в каждой версии:

hoc1

59

hoc2

94

hoc3

248

(версия с lex  229)

hoc4

396

hoc5

574

hoc6

809

Естественно, подсчеты были произведены программами:

$ sed  ‘/^$/d’  `pick *.[chyl]` | wc -l

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

Упражнение 8.18.  Измените hoc6 так, чтобы разрешить использовать формальные параметры, имеющие имена, в подпрограммах как аль тернативу $1 и т. д. ~

Упражнение 8.19.  Сейчас  все переменные, кроме параметров, являются глобальными. Большая часть  механизма добавления локальных переменных, сохраняемых в стеке, уже  готова. Можно предложить создать объявление auto, которое готовит на стеке  место для перечисленных  переменных; переменные,  которые не  объявлены таким способом, будут считаться глобальными. Надо  будет расширить и таблицу символов, сделав так, чтобы  сначала производился поиск локальных переменных, а уже  затем – глобальных. Как  это будет взаимодействовать с аргументами, имеющими имена? ~

Упражнение 8.20.  Как  бы вы добавили в hoc массивы? Как  передавать их функциям и процедурам? Как  возвращать их? ~

Упражнение 8.21.  Обобщите хранение  строк  так, чтобы  переменные могли хранить строки  вместо  чисел. Какие потребуются операторы? Самым сложным в этой  задаче является  управление памятью: надо убедиться, что строки хранятся так, что когда они не нужны, они освобождаются, чтобы  не возникало утечек памяти. В качестве промежуточного шага добавьте улучшенные возможности форматирования выходных данных, например доступ  к какой-либо форме  функции printf из Си. ~

Оценка производительности

Для  того чтобы получить представление о том, насколько хорошо работает hoc, было проведено его сравнение с некоторыми другими программами UNIX, реализующими калькуляторы. Таблицу, представленную в данном разделе, следует воспринимать с некоторой долей скептицизма,  но, тем не менее, она показывает, что наша реализация вполне разумна. Все времена приведены в секундах пользовательского времени на PDP-11/70. Решались две задачи. Первым был расчет функции Аккермана  ack(3,3).  Это   хорошая   проверка  для   механизма  вызова функций, т. к. для данного расчета необходимо 2432  вызова различной глубины вложенности.

func  ack() {

if ($1  == 0)  return $2+1

if  ($2  == 0)  return  ack($1–1,  1) return  ack($1–1,  ack($1,  $2–1))

}

ack(3,3)

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

proc  fib() {

a = 0 b = 1

while (b  <  $1)  { c  =  b

b = a+b a  = c

}

}

i = 1

while  (i  <  100)  { fib(1000) i  =  i  +  1

}

Сравнивались четыре языка: hoc, bc(1), bas (древний диалект Бейсика, который работает только на PDP-11) и Си (с использованием типа double для всех переменных).

Таблица 8.1. Секунды затраченного времени (PDP511/70)

программа

ack(3,3)

100×fib(1000)

hoc bas bc

c

5,5

1,3 39,7

<0,1

5,0

0,7

14,9

<0,1

Числа в табл. 8.1  представляют собой суммы пользовательского и системного времени работы процессора, измеренные time. Можно также оснастить программу на Си инструментальными средствами, позволяющими определить, сколько времени использует каждая из функций. Программу надо  перекомпилировать с параметром –p,  включающим режим профилирования. Если изменить makefile

hoc6:        $(OBJS)

cc  $(CFLAGS)  $(OBJS)  –lm –o  hoc6

(команда cc использует переменную CFLAGS), а затем сказать

$ make  clean; make CFLAGS=-p

то  в  получившейся  программе будет  содержаться профилирующий код.  Когда программа выполняется, она  оставляет после себя  файл с данными mon.out, который интерпретируется программой prof.

Чтобы вкратце пояснить эти понятия, представим испытание hoc6 программой Фибоначчи, описанной выше.

$ hoc6 <fibtest                          Запустить тест

$ prof  hoc6 | sed  15q                  Проанализировать


322

Глава 8. Разработка программ

name

%time

cumsecs   #call

ms/call

_pop

15.6

0.85  32182

0.03

_push

14.3

1.63  32182

0.02

mcount

11.3

2.25

csv

10.1

2.80

cret

8.8

3.28

_assign

8.2

3.73    5050

0.09

_eval

8.2

4.18    8218

0.05

_execute

6.0

4.51    3567

0.09

_varpush

5.9

4.83  13268

0.02

_lt

2.7

4.98    1783

0.08

_constpu

2.0

5.09      497

0.22

_add

1.7

5.18    1683

0.05

_getarg

1.5

5.26    1683

0.05

_yyparse

0.6

5.30          3

11.11

$

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

Затраты окажутся еще больше, если добавить время для функций свя зывания подпрограммы Си, csv и cret (mcount является частью профилирующего кода, компилируемого посредством cc  –p.) Если  заменить вызовы функций макросами, разница должна быть значительной.

Чтобы проверить это предположение, изменим code.c, заменив вызовы

push и pop макросами управления стеком:

#define push(d)  *stackp++  = (d)

#define popm()   *––stackp              /*  функция  все  еще  нужна  */

(Функция pop все  еще  необходима в качестве  кода машинной опера ции, поэтому просто заменить все pop нельзя.) Новая версия работает на 35% быстрее, значения времени из табл. 8.1 сокращаются с 5,5  до 3,7 секунд и с 5,0 до 3,1.

Упражнение 8.22.  В макросах push и popm проверка ошибок не выполняется. Прокомментируйте разумность такой архитектуры. Можно ли совместить проверку  ошибок, предоставляемую функциями,  со скоростью  выполнения макросов? ~

Оглянемся назад

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

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

Второй, более философский момент заключается в том,  чтобы  воспринимать  имеющееся задание как разработку языка, а  не  «написание программы». Организация  программы в  качестве процессора языка способствует регулярности синтаксиса (то есть пользовательского интерфейса) и  структурирует реализацию. Это также  гарантирует, что новые  возможности будут согласованы с уже  существующими. Конеч но же, понятие «язык» не ограничивается стандартными языками программирования,  только в  этой  книге уже  были  представлены  такие специализированные языки, как eqn и pic, а также сами yacc, lex и make.

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

Заголовочные файлы представляют собой хорошее средство для  орга низации объявлений данных, которые должны быть видимыми в нескольких файлах. Централизуя информацию, они исключают появление ошибок, обусловленных использованием несовместимых версий, особенно  в паре  с make. Кроме того,  важно разместить данные и функции  в файлах так, чтобы  они не были видимыми тогда, когда этого не требуется.

Есть несколько тем,  которым не было уделено особого внимания из-за недостатка места. Например, не рассказывалось о том,  в какой степе ни применялись все остальные средства UNIX  во время разработки семейства hoc. Каждая версия программы находится в отдельном каталоге, идентичные файлы связаны ссылками; ls и du многократно используются для  того,  чтобы  следить за тем,  что где находится. Ответы  на многие другие вопросы дают программы. Например, где объявлена данная переменная? Обратитесь к grep. Что изменилось в этой версии? Поможет  diff. Как  интегрировать изменения в данную  версию? Используйте idiff.  Каков размер этого файла? Спросите у wc. Пора  сделать резервную копию? Примените утилиту cp. Как копировать толь ко те файлы, которые изменились после  последнего резервного копирования? Используйте make. Такой общий подход типичен для  повседневной разработки программ в системе UNIX: совокупность небольших инструментальных средств, использованных по отдельности или  (при  необходимости) объединенных  вместе,  помогает  автоматизировать работу, которую иначе пришлось бы выполнять вручную.

История и библиография

Программа  yacc  была   создана  Стивом  Джонсоном (Steve Johnson). Формально класс языков, для  которых yacc может генерировать синтаксические анализаторы, называется LALR(1): синтаксический раз бор происходит слева  направо, при  этом  просмотр ввода происходит с опережением максимум на одну лексему. Понятие отдельного описа ния для того,  чтобы  разрешить проблему приоритетов и неоднозначности  в грамматике, появилось только в yacc. См. «Deterministic par sing  of  ambiguous grammars» А. В. Ахо  (A. V.  Aho), С. С.  Джонсона (S. C. Johnson) и Д. Д. Ульмана (J. D. Ullman) (издано CACM в августе 1975  года). Использованы некоторые передовые алгоритмы и структуры данных для создания и хранения таблиц синтаксического анализа.

Хорошее описание базовой теории, лежащей в основе  yacc и других генераторов синтаксических анализаторов, приведено в книге А. В. Ахо и Д. Д. Ульмана «Principles of Compiler Design» (Принципы проектирования компиляторов), Addison-Wesley, 1977. Сам yacc описан в томе 2В справочного  руководства  по  UNIX.  В  том  же   разделе  представлен калькулятор, сопоставимый с hoc2; полезно произвести их сравнение.

Программа lex была  изначально создана Майком Леском (Mike Lesk). Теоретические основы  представлены в уже  упомянутом труде Ахо  и Ульмана, а сам  язык lex  документирован  в справочном руководстве по UNIX.

Многие  языковые процессоры, включая переносимый компилятор Си, Паскаль, ФОРТРАН 77,  Ratfor, awk, bc, eqn и pic, были реализованы с использованием yacc и (в меньшей степени) lex.

Программа  make  была   написана Сту  Фелдманом  (Stu   Feldman).  См.

«MAKE – a program for  maintaining computer programs» (MAKE – прорамма для  поддержки компьютерных программ), изданную Software – Practice & Experience в апреле 1979  года.

В книге «Writing Efficient Programs» (Написание эффективных программ) Джона Бентли (Jon Bentley) (Prentice-Hall, 1982) описаны техники, позволяющие увеличить скорость выполнения программы. Особое внимание обращается на то, что сначала следует выбрать правильный алгоритм, а затем уже – в случае необходимости – усовершенствовать код.

Источник: Керниган Б., Пайк Р., UNIX. Программное окружение. – Пер. с англ. – СПб: Символ-Плюс, 2003. – 416 с., ил.

По теме:

  • Комментарии