| Главная | Новости | Статьи | Книги | Ссылки |
Приведем еще один арифметический вычислитель, использующий классический рекурсивный подход:
/* Калькулятор на основе рекурсивного грамматического разбора.
* По мотивам арифметической части программы 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 <stdio.h>
#include <ctype.h>
#include <setjmp.h>
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;
}
/* Лексический разбор ------------------------------------------*/
/* Очистить цепочку токенов */
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');
}
/* Система переменных ----------------------------------------- */
#define NEXT(v) *v = (*v)->next
#define TOKEN(v) (*v)->token
#define TYPE(v) (*v)->type
#define eq(str1, str2) (!strcmp(str1, str2))
jmp_buf breakpoint;
#define ERR(msg,val) { printf("%s\n", msg);longjmp(breakpoint, val+1);}
typedef struct {
char *name; /* Имя переменной */
int value; /* Значение переменной */
int isset; /* Получила ли значение ? */
} Var;
#define MAXV 40
Var vars[MAXV];
/* Получить значение переменной */
int getVar(char *name){ Var *ptr;
for(ptr=vars; ptr->name; ptr++)
if(eq(name, ptr->name)){
if(ptr->isset) return ptr->value;
printf("%s: ", name); ERR("variable is unbound yet", 0);
}
printf("%s: ", name); ERR("undefined variable", 0);
}
/* Создать новую переменную */
Var *internVar(char *name){ Var *ptr;
for(ptr=vars; ptr->name; ptr++)
if(eq(name, ptr->name)) return ptr;
ptr->name = strdup(name);
ptr->isset = 0; ptr->value = 0; return ptr;
}
/* Установить значение переменной */
void setVar(Var *ptr, int val){ ptr->isset = 1; ptr->value = val; }
/* Распечатать значения переменных */
void printVars(){ Var *ptr;
for(ptr=vars; ptr->name; ++ptr)
printf("\t%s %s %d\n", ptr->isset ? "BOUND ":"UNBOUND",
ptr->name, ptr->value);
}
/* Синтаксический разбор и одновременное вычисление ----------- */
/* Вычисление встроенных функций */
int apply(char *name, int args[], int nargs){
if(eq(name, "power2")){
if(nargs != 1) ERR("power2: wrong argument count", 0);
return (1 << args[0]);
} else if(eq(name, "min")){
if(nargs != 2) ERR("min: wrong argument count", 0);
return (args[0] < args[1] ? args[0] : args[1]);
} else if(eq(name, "max")){
if(nargs != 2) ERR("max: wrong argument count", 0);
return (args[0] < args[1] ? args[1] : args[0]);
} else if(eq(name, "sum")){ register i, sum;
for(i=0, sum=0; i < nargs; sum += args[i++]);
return sum;
} else if(eq(name, "rand")){
switch(nargs){
case 0: return rand();
case 1: return rand() % args[0];
case 2: return args[0] + rand() % (args[1] - args[0] + 1);
default: ERR("rand: wrong argument count", 0);
}
}
ERR("Unknown function", args[0]);
}
/* Вычислить выражение из списка лексем. */
/* Синтаксис задан праворекурсивной грамматикой */
int expr(Token *t){ int val = 0;
if(val = setjmp(breakpoint)) return val - 1;
val = expression(&t);
if(t){ printlex(NULL, t); ERR("Extra tokens", val); }
return val;
}
/* <EXPRESSION> = <EXPASS> |
<EXPASS> ";" <EXPRESSION> */
int expression(Token **v){ int arg = expass(v);
if(*v && TYPE(v) == SMC ){
NEXT(v); return expression(v);
} else return arg;
}
/* <EXPASS> = <ПЕРЕМЕННАЯ> "=" <EXPASS> |
<EXP0> */
int expass(Token **v){ int arg;
if(*v && (*v)->next && (*v)->next->type == OP &&
eq((*v)->next->token, "=")){ Var *ptr;
/* присваивание (assignment) */
if( TYPE(v) != ID ) /* слева нужна переменная */
ERR("Lvalue needed", 0);
ptr = internVar(TOKEN(v));
NEXT(v); NEXT(v); setVar(ptr, arg = expass(v)); return arg;
}
return exp0(v);
}
/* <EXP0> = <EXP1> | <EXP1> "||" <EXP0> */
int exp0(Token **v){ int arg = exp1(v);
if(*v && TYPE(v) == OP && eq(TOKEN(v), "||")){
NEXT(v); return(exp0(v) || arg );
/* помещаем arg ВТОРЫМ, чтобы второй операнд вычислялся
* ВСЕГДА (иначе не будет исчерпан список токенов и
* возникнет ошибка в expr(); Это не совсем по правилам Си.
*/
} else return arg;
}
/* <EXP1> = <EXP2> | <EXP2> "&&" <EXP1> */
int exp1(Token **v){ int arg = exp2(v);
if(*v && TYPE(v) == OP && eq(TOKEN(v), "&&")){
NEXT(v); return(exp1(v) && arg);
} else return arg;
}
/* <EXP2> = <EXP2A> | <EXP2A> "|" <EXP2> */
int exp2(Token **v){ int arg = exp2a(v);
if(*v && TYPE(v) == OP && eq(TOKEN(v), "|")){
NEXT(v); return( arg | exp2(v));
} else return arg;
}
/* <EXP2A> = <EXP2B> | <EXP2B> "^" <EXP2A> */
int exp2a(Token **v){ int arg = exp2b(v);
if(*v && TYPE(v) == OP && eq(TOKEN(v), "^")){
NEXT(v); return( arg ^ exp2a(v));
} else return arg;
}
/* <EXP2B> = <EXP2C> | <EXP2C> "&" <EXP2B> */
int exp2b(Token **v){ int arg = exp2c(v);
if(*v && TYPE(v) == OP && eq(TOKEN(v), "&")){
NEXT(v); return( arg & exp2b(v));
} else return arg;
}
/* <EXP2C> = <EXP3> | <EXP3> "==" <EXP3>
| <EXP3> "!=" <EXP3> */
int exp2c(Token **v){ int arg = exp3(v);
if(*v && TYPE(v) == OP && eq(TOKEN(v), "==")){
NEXT(v); return( arg == exp3(v));
} else if(*v && TYPE(v) == OP && eq(TOKEN(v), "!=")){
NEXT(v); return( arg != exp3(v));
} else return arg;
}
/* <EXP3> = <EXP3A> | <EXP3A> ">" <EXP3>
| <EXP3A> "<" <EXP3>
| <EXP3A> ">=" <EXP3>
| <EXP3A> "<=" <EXP3> */
int exp3(Token **v){ int arg = exp3a(v);
if(*v && TYPE(v) == OP && eq(TOKEN(v), ">")){
NEXT(v); return( arg && exp3(v));
}else if(*v && TYPE(v) == OP && eq(TOKEN(v), "<")){
NEXT(v); return( arg && exp3(v));
}else if(*v && TYPE(v) == OP && eq(TOKEN(v), ">=")){
NEXT(v); return( arg && exp3(v));
}else if(*v && TYPE(v) == OP && eq(TOKEN(v), "<=")){
NEXT(v); return( arg && exp3(v));
} else return arg;
}
/* <EXP3A> = <EXP4> | <EXP4> "<<" <EXP3A>
| <EXP4> ">>" <EXP3A> */
int exp3a(Token **v){ int arg = exp4(v);
if(*v && TYPE(v) == OP && eq(TOKEN(v), "<<")){
NEXT(v); return( arg << exp3a(v));
}else if(*v && TYPE(v) == OP && eq(TOKEN(v), ">>")){
NEXT(v); return( arg && exp3a(v));
} else return arg;
}
/* <EXP4> = <EXP5> | <EXP5> "+" <EXP4>
| <EXP5> "-" <EXP4> */
int exp4(Token **v){ int arg = exp5(v);
if(*v && TYPE(v) == OP && eq(TOKEN(v), "+")){
NEXT(v); return( arg + exp4(v));
}else if(*v && TYPE(v) == OP && eq(TOKEN(v), "-")){
NEXT(v); return( arg - exp4(v));
} else return arg;
}
/* <EXP5> = <EXP6> | <EXP6> "*" <EXP5>
| <EXP6> "/" <EXP5>
| <EXP6> "%" <EXP5> */
int exp5(Token **v){ int arg = exp6(v), arg1;
if(*v && TYPE(v) == OP && eq(TOKEN(v), "*")){
NEXT(v); return( arg * exp5(v));
}else if(*v && TYPE(v) == OP && eq(TOKEN(v), "/")){
NEXT(v); if((arg1 = exp5(v)) == 0) ERR("Zero divide", arg);
return( arg / arg1);
}else if(*v && TYPE(v) == OP && eq(TOKEN(v), "%")){
NEXT(v); if((arg1 = exp5(v)) == 0) ERR("Zero module", arg);
return( arg % arg1);
} else return arg;
}
/* <EXP6> = "!"<EXP6> | "~"<EXP6> | "-"<EXP6>
| "(" <EXPRESSION> ")"
| <ИМЯФУНКЦИИ> "(" [ <EXPRESSION> [ "," <EXPRESSION> ]... ] ")"
| <ЧИСЛО>
| <CH_ПЕРЕМЕННАЯ> */
int exp6(Token **v){ int arg;
if( !*v) ERR("Lost token", 0);
if(TYPE(v) == OP && eq(TOKEN(v), "!")){
NEXT(v); return !exp6(v);
}
if(TYPE(v) == OP && eq(TOKEN(v), "~")){
NEXT(v); return ~exp6(v);
}
if(TYPE(v) == OP && eq(TOKEN(v), "-")){
NEXT(v); return -exp6(v); /* унарный минус */
}
if(TYPE(v) == OPEN){
NEXT(v); arg = expression(v);
if( !*v || TYPE(v) != CLOSE) ERR("Lost ')'", arg);
NEXT(v); return arg;
}
if(TYPE(v) == NUM){ /* изображение числа */
arg = atoi(TOKEN(v)); NEXT(v); return arg;
}
if(TYPE(v) == ID){
char *name = (*v)->token; int args[20], nargs = 0;
NEXT(v);
if(! (*v && TYPE(v) == OPEN)){ /* Переменная */
return expvar(v, name);
}
/* Функция */
args[0] = 0;
do{ NEXT(v);
if( *v && TYPE(v) == CLOSE ) break; /* f() */
args[nargs++] = expression(v);
} while( *v && TYPE(v) == COMMA);
if(! (*v && TYPE(v) == CLOSE)) ERR("Error in '()'", args[0]);
NEXT(v);
return apply(name, args, nargs);
}
printlex(TOKEN(v), *v); ERR("Unknown token type", 0);
}
/* <CH_ПЕРЕМЕННАЯ> = <ПЕРЕМЕННАЯ> |
<ПЕРЕМЕННАЯ> "++" |
<ПЕРЕМЕННАЯ> "--"
Наши операции ++ и -- соответствуют ++x и --x из Си */
int expvar(Token **v, char *name){
int arg = getVar(name); Var *ptr = internVar(name);
if(*v && TYPE(v) == OP){
if(eq(TOKEN(v), "++")){ NEXT(v); setVar(ptr, ++arg); return arg; }
if(eq(TOKEN(v), "--")){ NEXT(v); setVar(ptr, --arg); return arg; }
}
return arg;
}
/* Головная функция ------------------------------------------- */
char input[256];
Token *head, *tail;
void main(){
do{ printf(": "); fflush(stdout);
if( !gets(input)) break;
if(!*input){ printVars(); continue; }
if(eq(input, "!!")) ; /* ничего не делать, т.е. повторить */
else{ if(head) freelex(&head); lex(&head, &tail, input); }
printf("Result: %d\n", expr(head));
} while(1); putchar('\n');
}
Напишите программу, выделяющую n-ое поле из каждой строки файла. Поля разделяются двоеточиями. Предусмотрите задание символа-разделителя из аргументов программы. Используйте эту программу для выделения поля "домашний каталог" из файла /etc/passwd. Для выделения очередного поля можно использовать следующую процедуру:
main(){
char c, *next, *strchr(); int nfield;
char *s = "11111:222222222:333333:444444";
for(nfield=0;;nfield++){
if(next = strchr(s, ':')){
c= *next; *next= '\0';
}
printf( "Поле #%d: '%s'\n", nfield, s);
/* можно сделать с полем s что-то еще */
if(next){ *next= c; s= next+1; continue; }
else { break; /* последнее поле */ }
}
}
© Copyright А. Богатырев, 1992-95
Си в UNIX
Назад | Содержание | Вперед