經典表達式遞歸下將法語法分析和求值 yongmou

首先，給出文法定義：

消除左遞歸後，用BNF表示
    <Expr>    -> <Term> { (+|-) <Term> }
    <Term>   -> <Factor> { (*|/) <Factor> }
    <Factor> -> (<Expr>) | num | indent

程序：

  1 /*
  2     遞歸下降法構造經典表達式的語法分析
  3     編寫遞歸下降子程序有一個協定:
  4         每一個子程序都在全局量nextToken中放入下一個輸入的token。
  5         因而，當開始一個語法分析函數時，假定nextToken具有還沒有被語法分析過程使用的輸入標記中最左面的那個標記。
  6  */
  7 #include <stdio.h>
  8 #include <ctype.h>
  9 #include <stdlib.h>
 10 
 11  enum token_type{
 12     NUMBER, OPERATOR, SEPARATOR, UNKOWN
 13 };
 14 
 15  struct Token{
 16     int type;
 17     int val;
 18 };
 19 
 20  struct Token next_token; // 下一個未處理的token
 21 // put next token into next_token
 22 void lex();
 23 
 24 // 三個非終結符
 25 double expr();
 26 double term();
 27 double factor();
 28 
 29 int main()
 30 {
 31     // input: 
 32     // 每個表達式, 以';'結尾
 33     freopen("test.in", "r", stdin);
 34     
 35     while (1){
 36         lex(); // 取得第一個token
 37         if (next_token.type == UNKOWN && next_token.val == EOF) 
 38             break;
 39         
 40         printf("%lf\n", expr());
 41         
 42         if (next_token.type != SEPARATOR || next_token.val != ';' ){
 43             fprintf(stderr, "未以\';\'結尾\n");
 44             break;
 45         }
 46     }
 47     return 0;
 48 }
 49 
 50 // <expr> -> <term> { (+ | -) <term> }
 51 double expr()
 52 {
 53     double val;
 54 
 55     // parse first term
 56     val = term();
 57     
 58     // As long as the next token is + or - , 
 59     // call lex() get next token，
 60     // and parse the next term.
 61     while(next_token.type == OPERATOR &&
 62           (next_token.val == '+' || next_token.val == '-')){
 63         int op = next_token.val;
 64         lex();
 65         
 66         if(op == '+')
 67             val += term();
 68         else if(op == '-')
 69             val -= term();
 70     }
 71     return val;
 72 }
 73 
 74 // <term> -> <factor> { (* | /) <factor> }
 75 double term()
 76 {
 77     double val;
 78 
 79     // parse first factor
 80     val = factor();
 81     
 82     // As long as the next token is * or / , 
 83     // call lex() get next token，
 84     // and parse the next factor.
 85     while(next_token.type == OPERATOR && 
 86           (next_token.val == '*'  || next_token.val == '/')){
 87         int op = next_token.val;
 88         lex();
 89         
 90         if(op == '*')
 91             val *= factor();
 92         else if(op == '-')
 93             val /= factor();
 94     }
 95     return val;
 96 }
 97 
 98 // <factor> -> (<expr>) | num
 99 double factor(){
100     double val;
101     if(next_token.type == SEPARATOR && next_token.val == '('){
102         lex();
103         val = expr();
104         if(next_token.type == SEPARATOR && next_token.val == ')'){
105             lex(); // 讀取下一個token
106         }else{
107             fprintf(stderr, "括號不匹配\n");
108             exit(1);            
109         }
110     }else if(next_token.type == NUMBER){
111         val = next_token.val;
112         lex();
113     }else{ // 既不是數字也不是'('
114         fprintf(stderr, "unkown factor: %c\n", next_token.val);
115         exit(1);
116     }
117     return val;
118 }
119 
120 void lex(){
121     int c;
122     while((c = getchar()) != EOF && isspace(c))
123         ;
124     if(isdigit(c)){
125         int val;
126         val = c - '0';
127         while(isdigit(c = getchar()))
128             val = val * 10 + c - '0';
129         ungetc(c, stdin);
130         next_token.type = NUMBER;
131         next_token.val = val;
132         return;
133     }
134     next_token.val = c;
135     switch(c){
136     case '+':
137     case '-':
138     case '*':
139     case '/':
140         next_token.type = OPERATOR;
141         break;
142     case '(':
143     case ')':
144     case ';':
145         next_token.type = SEPARATOR;
146         break;
147     default:
148         next_token.type = UNKOWN;
149     }
150 }

測試數據，以分號結尾的表達式，main()中將stdin重定向到文件test.in

12 + 2*30;
(1+2)* 5;
4+5;
8+8*7;