首先，給出文法定義：
經典表達式文法： Expr -> Expr + Term |Expr - Term |Term Term -> Term * Factor |Term / Factor |Factor Factor -> (Expr) |num
遞歸下降法，無法處理左遞歸文法
消除左遞歸後，用BNF表示
-> { (+|-) } -> { (*|/) } -> () | num | indent
程序：
1 /* 2 遞歸下降法構造經典表達式的語法分析 3 編寫遞歸下降子程序有一個協定: 4 每一個子程序都在全局量nextToken中放入下一個輸入的token。 5 因而，當開始一個語法分析函數時，假定nextToken具有還沒有被語法分析過程使用的輸入標記中最左面的那個標記。 6 */ 7 #include 8 #include 9 #include 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 // -> { (+ | -) } 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 // -> { (* | /) } 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 // -> () | 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;
延伸阅读
最新评论