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

8.5 Этап 5: структуры управления и операции отношений

8.5 Этап 5: структуры управления и операции отношений

Версия hoc5 оправдывает все затраты, связанные с созданием интерпретатора. В нее допустимо включать операторы if-else  и while, аналогичные операторам языка Си, группировать операторы с помощью { и } и использовать оператор print. Она содержит полный набор операций отношений (>, >=, и т.д.), а также операций AND, OR, && и ||. (Две последние операции не гарантируют вычисления слева направо, хотя такой подход принят в Си; вычисляются оба условия, даже если в этом нет необходимости.)

Грамматику 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; /* symbol table pointer */
 Inst *inst; /* machine instruction */
}
%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: /* nothing */
 | 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; /* body of loop */
  ($1)[2] = (Inst)$4; } /* end, if cond fails */
 | if cond stmt end { /* else-less if */
  ($1)[1] = (Inst)$3; /* thenpart */
  ($1)[3] = (Inst)$4; } /* end, if cond fails */
 | if cond stmt end ELSE stmt end { /* if with else */
  ($1)[1] = (Inst)$3; /* thenpart */
  ($1)[2] = (Inst)$6; /* elsepart */
  ($1)[3] = (Inst)$7; } /* end, if cond fails */
 | '{' stmtlist '}' { $$ = $2; }
 ;
cond: '(' expr ')' { code(STOP); $$ = $2; }
 ;
while: WHILE { $$ = code3(whilecode, STOP, STOP); }
 ;
if: IF { $$=code(ifcode); code3(STOP, STOP, STOP); }
 ;
end: /* nothing */ { code(STOP); $$ = progp; }
 ;
stmtlist: /* nothing */ { $$ = 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); }
%%
/* end of grammar */

В грамматике есть пять случаев неоднозначности типа сдвиг/свертка, подобных упомянутой в грамматике для hoc3.

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

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

пока: WHILE

Но в то же самое время резервируются два следующих машинных слова, которые будут определены ниже. Далее создаются команды для выражения, которое образует условие в операторе while. Значение, возвращаемое правилом cond, является адресом начала команд для условия. После распознавания всего оператора while в два зарезервированных слова, вводимых за командой whilecode, заносится адрес начала тела цикла и адрес оператора, следующего за циклом. (Команда по этому адресу будет создана позднее.)

| пока усл опер все {
 ($1)[1] = (Inst) $3 /* тело цикла */
 ($1)[2] = (Inst) $4 /* все, если условие неверно */
}

Здесь $1 обозначает адрес команды whilecode, таким образом, ($1)[1] и ($1)[2] обозначают два следующих слова.

Рисунок, приведенный ниже, может прояснить ситуацию:

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

Лексический анализ теперь несколько удлиняется в основном из-за необходимости распознавания дополнительных операций:

yylex() /* hoc5 */
{
 ...
 switch (с) {
 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) /* look ahead for >=, etc. */
{
 int с = getchar();
 if (c == expect)
  return ifyes;
 ungetc(c, stdin);
  return ifno;
}

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

$ cat hoc.h
...
typedef int (*Inst)(); /* machine instruction */
#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 также не изменилась, хотя, очевидно, здесь появилось много новых процедур для обработки операций отношений. Типичным примером может служить функция le ("less than equal to" меньше или равно).

le() {
 Datum d1, d2;
 d2 = pop();
 d1 = pop();
 d1.val = (double)(d1.val <= d2.val);
 push(d1);
}

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

whilecode() {
 Datum d;
 Inst *savepc = pc; /* loop body */
 execute(savepc+2); /* condition */
 d = pop();
 while (d.val) {
  execute(*((Inst **)(savepc))); /* body */
  execute(savepc+2);
  d = pop();
 }
 pc = *((Inst **)(savepc+1)); /* next statement */
}

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

Функция ifcode аналогична предыдущей: при входе в нее pc ссылается на фрагмент посте then, pc+1 на фрагмент посте else, pc+2 на следующий оператор, а pc+3 на условие.

ifcode()
{
 Datum d;
 Inst *savepc = pc; /* then part */
 execute(savepc+3); /* condition */
 d = pop();
 if (d.val)
  execute(*((Inst **)(savepc)));
 else if (*((Inst **)(savepc+1))) /* else part? */
  execute(*((Inst **)(savepc+1)));
 pc = *((Inst**)(savepc+2)); /* next stmt */
}

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

$ cat init.с
...
static struct { /* Keywords */
 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 выраж.

prexpr() /* print numeric value */
{
 Datum d;
 d = pop();
 printf ('"%.8gn", d.val);
}

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

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

Оглавление книги