yacc/bison 系列 (1) - 四則運算, 靠文法規則來處理優先順序

行是知之始，知是行之成。

hoc_arithmetic.y

 1 %{
 2 #include <stdio.h>
 3 #include <ctype.h>
 4 #include <stdlib.h>
 5 #include <unistd.h>
 6 #define YYSTYPE double
 7 #define YYDEBUG 1
 8 
 9 int yylex();
10 int yyerror(const char *s);
11 %}
12 
13 %token NUMBER
14 %%
15 list:    {printf("\taaempty\n");}
16      | list '\n' {printf("list \\n\n");}
17      | list expr '\n' { printf("%.8g\n", $2); }
18 
19 expr: term
20     | expr '+' term {$$ = $1 + $3;}
21     | expr '-' term {$$ = $1 - $3;}
22 
23 term: primary_expr
24     | term '*' primary_expr {$$ = $1 * $3;}
25     | term '/' primary_expr {$$ = $1 / $3;}
26 
27 primary_expr: NUMBER
28        | '(' expr ')'
29 
30 %%
31 char *progname;
32 int lineno = 1;
33 
34 
35 int yylex()
36 {
37   int c;
38   while ((c=getchar()) == ' ' || c == '\t')
39     ;
40   
41   if (c == EOF)
42     return 0;
43   if (c == '.' || isdigit(c) )
44   {
45     ungetc(c, stdin);
46     scanf("%lf", &yylval);
47     return NUMBER;
48   }
49 
50   if (c == '\n')
51     ++lineno;
52   return c;  
53 }
54 
55 int warning(const char *s, const char *t)
56 {
57   fprintf(stderr, "%s: %s", progname, s);
58   if (t)
59     fprintf(stderr, " %s", t);
60 
61   fprintf(stderr, " near line %d\n", lineno);
62 }
63 
64 int yyerror(const char *s)
65 {
66   return warning(s, 0); 
67 }
68 
69 int main(int argc, char *argv[])
70 {
71   int opt;
72   progname = argv[0];
73 
74   while ((opt = getopt(argc, argv, "d:h?")) != -1)
75   {
76     switch (opt)
77     {
78       case 'd':
79       {
80         yydebug = strtol(optarg, 0, 10);
81         if (yydebug == 1)
82           printf("enable bison debug mode\n");
83         break;
84       }
85     }
86   }
87 
88   //yydebug = 1;
89   yyparse();
90 }      

「前一篇」提到使用的四則運算是依靠 bison 的運算符定義來達成優先順序, 這篇介紹使用文法定義來處理運算符號優先權, 可以看出文法規則 hoc_arithmetic.y (L15 ~ 28) 比之前複雜不少, 雖然只是簡單的四則運算, 但這文法規則還是蠻燒腦了, 我花了一些功夫才弄懂, 不過若是要自己寫出這些規則, 我沒有這個本事。

藉助 bison 這樣的神兵利器, 只要把文法規則重新編寫之後, 再次執行 bison, 就有了一樣的四則運算功能。

本篇沒打算說明文法規則, 如果你沒有修過編譯器課程, 這些文法規則可能會難倒你 (其實也難倒我), 文法規則可以參考「自己动手写编译器」。