yacc/bison 系列 (0) - 四則運算, 使用 bison 自訂運算符號的功能處理優先權

寫在前面: 文中會混用 lex/flex, yacc/bison, 指的是一樣的東西。

棄捐勿複道, 努力加餐飯

之前手工打造四則運算, 這次想挑戰 yacc/bison 來完成, 一樣嘗試很久, 卻沒有什麼進展。bison 是很古老的 parser generator, 現在有新的 parser generator, 不過我還是鍾愛它, 一直想把他學好, 看看這次能不能成功。

網路上或是編譯器書籍提到的教學, 看過之後老實說還是覺得很難, 一直都沒有能掌握 yacc/bison。我從「自制编程语言」開始學習 lex/yacc, 但還是沒從這邊掌握到學習的方法。

fig 1. 自制编程语言, 20140818 購於台南若水堂 356nt

另外還有「flex与bison (中文版)」, 但是我沒有買到這本, 手邊有的是 lex & yacc 英文版, 讀過幾次, 英文不算難懂, 但可能因為英文的關係, 也沒能從這本學好。

不好學的原因可能有幾點: 不熟文法規則, 這種文法蠻燒腦的, 如果沒有參考別人寫好的規則, 要全靠自己把四則運算的規則寫出來並不容易, 我光是看別人寫的就花了不少力氣才搞懂。另外也試著參考別人的 ebnf 寫了個 if 判斷式, 花了不少功夫才勉強可用, 不過真的可以成功分析 if 判斷式。

不同的教學文用了不同的文法, 導致學習上帶了來混亂。一般這篇教學文看不懂, 我們會找其他篇, 但由於舉例的文法規則不同, 很可能導致我們看的教學文沒有「累積」的效果, 永遠都是處在學習的最開始階段。

直到最近看了「UNIX 编程环境」第八章, Kernighan 介紹了 yacc 打造的一個語言, 讓我找到新的學習方向。

fig 2. UNIX 编程环境

Kernighan 寶刀未老, 這本書的內容很不錯, 強力推薦。原文書名是 The UNIX Programming Environment, 和另外一本大作 Advanced Programming in the UNIX Environment [W. Richard Stevens] 名字很像, 不要搞錯, 學 unix programming, 這兩本都讀一讀大有裨益。

大部分的書籍和網路文章都會把 lex, yacc 一起介紹, 2 個分開都很難學習了, 把他們兜在一起, 更是添增了學習難度。「UNIX 编程环境」8.1.3 給的例子是初學都會提到的四則運算, 但是沒有使用 lex, 只使用 yacc, 加上幾個簡單的文法, 看起來很簡單, 但我花了不少時間才搞懂其文法規則。

因為使用了 yacc 的運算符號定義能力, 所以文法才可以寫得那麼簡單。「自制编程语言」沒有運用這功能, 靠文法規則定義出運算符號的優先權, 自然文法複雜了不只一點。我個人比較喜歡用「自制编程语言」單純靠文法規定的方式, 而不是用 parser generator 的特異功能。

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

hoc.y L33 自己寫了 yylex, 如果用 lex, lex 就會產生一個 yylex(), 這是給 bison 產生的 parser (yyparser) 呼叫的。從這邊可以清楚的看到 yylex 要怎麼寫, return 什麼, 可以知道和 yyparser 的關係。

另外 L86 把 yydebug = 1 會啟動 yacc debug mode, 這時候可以看到 yyparser 是怎麼做 shift, reduce 的動作, 我就是使用這樣的方式才知道 L17 的規則是怎麼被觸發的。我加了一個 option 來開關 debug, 使用 ./hoc -d 1 可以打開 yydebug。

談 L17 的規則前先來看 L18 的規則是幹麻用的。當你一直按下 enter 時, 觸發的就是這條規則, 所以不管按下多少次 enter (\n) parser 都會正確, 不會離開。

yyparser 如果遇到不符合文法規則的輸入值, 預設行為會離開程式。

L17 是指 list 可以是空的, 這個讓我困惑很久, 因為我們打字不可能打一個空的東西進去阿, 你不管打什麼, 一定有一個對應的輸入, 怎麼會有空集合, 這邊讓我百思不解這行文法的作用。打開 debug 之後我才知道, 這個只會用到一次, yyparser 一開始就會做一次 reduce, 就會 match 這個規則。

list 1.

 1 descent@debian-vm:hoc$ ./hoc1  -d 1
 2 enable bison debug mode
 3 Starting parse
 4 Entering state 0
 5 Stack now 0
 6 Reducing stack by rule 1 (line 17):
 7       aaempty
 8 -> $$ = nterm list ()
 9 Entering state 1
10 Stack now 0 1

從 list 1 L8 可以看到, 什麼都沒輸入, 就會做 reduce 然後對應到 hoc.y L17 的規則, 所以目前處在 list 的狀態, 之後在輸入 enter (\n), 就會 match list \n 這個規則, 又被 reduce 到 list, 再次輸入 enter (\n), 又 match list \n, 再次 reduce 到 list, 這便是可以一直按下 enter 也能符合文法規則的原因。

其他 hoc.y 的四則運算規則和運算符定義就沒那麼特別了。hoc.y L14, 15 定義運算符號是左結合, 以及 */ 比 +- 優先 (寫在下面的優先權越高)。

ref:

• 上下文无关语法及分析
• The syntax of C in Backus-Naur Form