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 <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');
    }

7.69.

Напишите программу, выделяющую 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

Назад | Содержание | Вперед