本篇內容

• 介紹Yacc的空白規則
• 範例 - 陣列讀取

介紹

我們在此之前已經介紹Yacc當中的基本規則、OR規則與遞迴規則。今天則是要來看空白規則。

空白規則主要是用來規範”不一定會出現在文本”的字串組。

舉個例子，如果我們想要讀取一個整數型別的陣列，我們可以使用 recursion 來處理：

func:
      '[' array ']'        { operation1(); }
    ;

array: 
      NUM                  { operation2(); }
    | array NUM            { operation3(); }

然而，這裡我們遇到了一個問題：如果該陣列是一個空陣列呢?

以剛剛的寫法來看，這個 array 裡面可以有一個或多個數字，但沒有數字時會匹配失敗。

所以，我們把規則改寫成這樣：

array:
      /* empty rule */
    | array NUM            { operation3(); }

這樣一樣會是兩個規則：

array: /* empty rule */  (規則1)
array: array NUM         (規則2)

以上的寫法，就算遇到空陣列，也可以匹配規則1，程式便能夠順利運行。

範例 - 陣列讀取

說明

給定一個檔案，內有一個一維陣列，用中括號包起來。請列出陣列項數與總和。

程式實作

Lex

%{
#include "main.h"
#include "yacc.tab.h"
%}

posint      ([0-9]+)
blank_chars ([ \f\r\t\v]+)

%%

{posint}        { yylval = atoi(yytext); return NUMBER; }
{blank_chars}   { ; }
"["             { return yytext[0]; }
"]"             { return yytext[0]; }
\n              { ; }

%%

int yywrap(void) {
    cout << "Finish!" << endl;
    return 1;
}

Yacc

%{
#include "main.h"

void yyerror(const char *s);
extern int yylex();
extern int yyparse();

int arraySum = 0;
int arraySize = 0;

%}

%token NUMBER

%%

func:
      '[' array ']'        { printf("Result: array size is %d; array sum is %d\n", arraySize, arraySum); }
    ;

array:
    | array NUMBER         { arraySum += $2; arraySize++; }
    ;

%%

void yyerror(const char *s) {
    cerr << s << endl;
}

執行結果

輸入內容

[ 1 2 3 ]

輸出結果

Result: array size is 3; array sum is 6

結語

空白規則在”不一定會出現”的字串組是很好用的工具，除了以上範例的遞迴外，在非遞迴的情況也可以使用。

參考資料

• Levine, John R., Tony Mason and Doug Brown [1992]. Lex & Yacc. O’Reilly & Associates, Inc. Sebastopol, California.
• Tom Niemann. Lex & Yacc