Хрестоматия по программированию на Си в Unix
#define NUMBER (-2) /* число */
#define BOTTOM 0 /* псевдолексема "дно стека" */
#define OPENBRACKET 1 /* ( */
#define FUNC 2 /* f( */
#define CLOSEBRACKET 3 /* ) */
#define COMMA 4 /* , */
#define PLUS 5 /* + */
#define MINUS 6 /* - */
#define MULT 7 /* * */
#define DIV 8 /* / */
#define POWER 9 /* ** */
/* Приоритеты */
#define NOTDEF 333 /* не определен */
#define INFINITY 3000 /* бесконечность */
/* Стек транслятора */
typedef struct _opstack {
int cop; /* код операции */
void (*f)(); /* "отложенное" действие */
} opstack;
int osp; /* operations stack pointer */
opstack ost[MAXDEPTH];
void push(n, func) void (*func)();
{
if(osp == MAXDEPTH){ printf("Стек операций полон\n");err(5);}
ost[osp].cop = n; ost[osp++].f = func;
}
int pop(){
if( !osp ){ printf("Стек операций пуст\n"); err(6); }
return ost[--osp].cop;
}
int top(){
if( !osp ){ printf("Стек операций пуст\n"); err(7); }
return ost[osp-1].cop;
}
void (*topf())(){
return ost[osp-1].f;
}
#define drop() (void)pop()
void nop(){ printf( "???\n" ); } /* no operation */
void obr_err(){ printf( "Не хватает )\n" ); err(8); }
А. Богатырев, 1992-95 - 333 - Си в UNIX
/* Таблица приоритетов */
struct synt{
int inp_prt; /* входной приоритет */
int stk_prt; /* стековый приоритет */
void (*op)(); /* действие над стеком вычислений */
} ops[] = {
/* BOTTOM */ {NOTDEF, -1, nop },
/* OPENBRACKET */ {INFINITY, 0, obr_err},
/* FUNC */ {INFINITY, 0, obr_err},
/* CLOSEBRACKET */ {1, NOTDEF, nop }, /* NOPUSH */
/* COMMA */ {1, NOTDEF, nop }, /* NOPUSH */
/* PLUS */ {1, 1, add },
/* MINUS */ {1, 1, sub },
/* MULT */ {2, 2, mult },
/* DIV */ {2, 2, divide },
/* POWER */ {3, 3, pwr }
};
#define stkprt(i) ops[i].stk_prt
#define inpprt(i) ops[i].inp_prt
#define perform(i) (*ops[i].op)()
/* значения, заполняемые лексическим анализатором */
double value; void (*fvalue)();
int tprev; /* предыдущая лексема */
А. Богатырев, 1992-95 - 334 - Си в UNIX
/* Транслятор в польскую запись + интерпретатор */
void reset(){ sp = osp = 0; push(BOTTOM, NULL); tprev = END;}
void calc(){
int t;
do{
if( setjmp(AGAIN))
printf( "Стеки после ошибки сброшены\n" );
reset();
while((t = token()) != EOF && t != END){
if(t == NUMBER){
if(tprev == NUMBER){
printf("%g:Два числа подряд\n",value);
err(9);
}
/* любое число просто заносится в стек */
tprev = t; dpush(value); continue;
}
/* иначе - оператор */
tprev = t;
/* Выталкивание и выполнение операций со стека */
while(inpprt(t) <= stkprt( top()) )
perform( pop());
/* Сокращение или подмена скобок */
if(t == CLOSEBRACKET){
if( top() == OPENBRACKET || top() == FUNC ){
void (*ff)() = topf();
drop(); /* схлопнуть скобки */
/* обработка функции */
if(ff) (*ff)();
}else{ printf( "Не хватает (\n"); err(10); }
}
/* Занесение операций в стек (кроме NOPUSH-операций) */
if(t != CLOSEBRACKET && t != COMMA)
push(t, t == FUNC ? fvalue : NULL );
}
if( t != EOF ){
/* Довыполнить оставшиеся операции */
while( top() != BOTTOM )
perform( pop());
printstk(); /* печать стека вычислений (ответ) */
}
} while (t != EOF);
}
/* Лексический анализатор ---------------------------- */
extern void getn(), getid(), getbrack();
int token(){ /* прочесть лексему */
int c;
while((c = getchar())!= EOF && (isspace(c) || c == '\n'));
if(c == EOF) return EOF;
ungetc(c, stdin);
if(isdigit(c)){ getn(); return NUMBER; }
if(isalpha(c)){ getid(); getbrack(); return FUNC; }
return getop();
}
А. Богатырев, 1992-95 - 335 - Си в UNIX
/* Прочесть число (с точкой) */
void getn(){
int c, i; char s[80];
s[0] = getchar();
for(i=1; isdigit(c = getchar()); i++ ) s[i] = c;
if(c == '.'){ /* дробная часть */
s[i] = c;
for(i++; isdigit(c = getchar()); i++) s[i] = c;
}
s[i] = '\0'; ungetc(c, stdin); value = atof(s);
}
/* Прочесть операцию */
int getop(){
int c;
switch( c = getchar()){
case EOF: return EOF;
case '=': return END;
case '+': return PLUS;
case '-': return MINUS;
case '/': return DIV;
case '*': c = getchar();
if(c == '*') return POWER;
else{ ungetc(c, stdin); return MULT; }
case '(': return OPENBRACKET;
case ')': return CLOSEBRACKET;
case ',': return COMMA;
default: printf( "Ошибочная операция %c\n", c);
return token();
}
}
struct funcs{ /* Таблица имен функций */
char *fname; void (*fcall)();
} tbl[] = {
{ "sin", dsin }, { "cos", dcos },
{ "exp", dexp }, { "sqrt", dsqrt },
{ "sqr", dsqr }, { "pi", pi },
{ "sum", add }, { "ln", dlog },
{ "e", e }, { NULL, NULL }
};
char *lastf; /* имя найденной функции */
/* Прочесть имя функции */
void getid(){
struct funcs *ptr = tbl;
char name[80]; int c, i;
*name = getchar();
for(i=1; isalpha(c = getchar()); i++) name[i] = c;
name[i] = '\0'; ungetc(c, stdin);
/* поиск в таблице */
for( ; ptr->fname; ptr++ )
if( !strcmp(ptr->fname, name)){
fvalue = ptr->fcall;
lastf = ptr->fname; return;
}
printf( "Функция \"%s\" неизвестна\n", name ); err(11);
}
А. Богатырев, 1992-95 - 336 - Си в UNIX
/* прочесть открывающую скобку после имени функции */
void getbrack(){
int c;
while((c = getchar()) != EOF && c != '(' )
if( !isspace(c) && c != '\n' ){
printf("Между именем функции %s и ( символ %c\n", lastf, c);
ungetc(c, stdin); err(12);
}
}
void main(){ calc();}
/* Примеры:
( sin( pi() / 4 + 0.1 ) + sum(2, 4 + 1)) * (5 - 4/2) =
ответ: 23.3225
(14 + 2 ** 3 * 7 + 2 * cos(0)) / ( 7 - 4 ) =
ответ: 24
*/
7.68. Приведем еще один арифметический вычислитель, использующий классический рекур-
сивный подход:
/* Калькулятор на основе рекурсивного грамматического разбора.
* По мотивам арифметической части программы csh (СиШелл).
* csh написан Биллом Джоем (Bill Joy).
: var1 = (x = 1+3) * (y=x + x++) 36
: s = s + 1 ошибка
: y 9
: s = (1 + 1 << 2) == 1 + (1<<2) 0
: var1 + 3 + -77 -38
: a1 = 3; a2 = (a4=a3 = 2; a1++)+a4+2 8
: sum(a=2;b=3, a++, a*3-b) 12
*/
#include
#include
#include
typedef enum { NUM, ID, OP, OPEN, CLOSE, UNKNOWN, COMMA, SMC } TokenType;
char *toknames[] = { "number", "identifier", "operation",
"open_paren", "close_paren", "unknown", "comma", "semicolon" };
typedef struct _Token {
char *token; /* лексема (слово) */
struct _Token *next; /* ссылка на следующую */
TokenType type; /* тип лексемы */
} Token;
extern void *malloc(unsigned); extern char *strchr(char *, char);
char *strdup(const char *s){
char *p = (char *)malloc(strlen(s)+1);
if(p) strcpy(p,s); return p;
}
А. Богатырев, 1992-95 - 337 - Си в UNIX
/* Лексический разбор ------------------------------------------*/
/* Очистить цепочку токенов */
void freelex(Token **p){
Token *thisTok = *p;
while( thisTok ){ Token *nextTok = thisTok->next;
free((char *) thisTok->token); free((char *) thisTok);
thisTok = nextTok;
}
*p = NULL;
}
/* Добавить токен в хвост списка */
void addtoken(Token **hd, Token **tl, char s[], TokenType t){
Token *newTok = (Token *) malloc(sizeof(Token));
newTok->next = (Token *) NULL;
newTok->token = strdup(s); newTok->type = t;
if(*hd == NULL) *hd = *tl = newTok;
else{ (*tl)->next = newTok; *tl = newTok; }
}
/* Разобрать строку в список лексем (токенов) */
#define opsym(c) ((c) && strchr("+-=!~^|&*/%<>", (c)))
#define is_alpha(c) (isalpha(c) || (c) == '_')
#define is_alnum(c) (isalnum(c) || (c) == '_')
void lex(Token **hd, Token **tl, register char *s){
char *p, csave; TokenType type;
while(*s){
while( isspace(*s)) ++s; p = s;
if( !*s ) break;
if(isdigit (*s)){ type = NUM; while(isdigit (*s))s++; }
else if(is_alpha(*s)){ type = ID; while(is_alnum(*s))s++; }
else if(*s == '('){ type = OPEN; s++; }
else if(*s == ')'){ type = CLOSE; s++; }
else if(*s == ','){ type = COMMA; s++; }
else if(*s == ';'){ type = SMC; s++; }
else if(opsym(*s)){ type = OP; while(opsym(*s)) s++; }
else { type = UNKNOWN; s++; }
csave = *s; *s = '\0'; addtoken(hd, tl, p, type); *s = csave;
}
}
/* Распечатка списка лексем */
void printlex(char *msg, Token *t){
if(msg && *msg) printf("%s: ", msg);
for(; t != NULL; t = t->next)
printf("%s`%s' ", toknames[(int)t->type], t->token);
putchar('\n');
}
А. Богатырев, 1992-95 - 338 - Си в UNIX
/* Система переменных ----------------------------------------- */
#define NEXT(v) *v = (*v)->next
