本篇內容

• 介紹Yacc檔案格式
• 介紹Yacc的規則語法
• 範例 - 簡易計算機1 (2 of 3)

Yacc檔案初探 - 格式介紹

我們已經完成Lex的部分了。接著，我們要正式進入Yacc的部分囉~

Yacc檔案的副檔名為.y，格式與Lex相似，也是分成三個部分：

... Definitions ...
%%
... Rules ...
%%
... Subroutines ...

Definitions

定義的區塊主要含有以下內容

1. C語言的定義或宣告

   通常在整個檔案的最頂端，用來匯入一些資料庫或是標頭檔。

   這部分需要用%{與%}包起來。

2. 標記(token)的定義

   在lex檔案中，對於不同樣式的字詞，會對其做出相對應的標記。這些標記需要在yacc檔案中做出定義以及相關的設定，作為後續的規則匹配。在此設定標記的類型，可以做後續的進階運用。(例如，若設定該標記為integer，可以將其拿來做後續的加減乘除等運算。)

3. YYSTYPE的定義

   在進行標記時，可以用來設定yylval的屬性。

Rules

這裡主要列出yacc的規則以及相對應的操作。也就是說，在讀取檔案中，當buffer中的詞組與任一個yacc規則相符，便會執行此規則的內容。

在語法上，要注意以下幾點：

1. 定義的規則應避免互相衝突
2. 規則的內容應該要避免模糊不清的狀況

Subroutines

在完成整個檔案的讀取後，如果需要進行後續的流程，則可以在此定義。

Yacc 規則語法

接下來，我們來看看Yacc的規則是怎麼定義的。

我們用下面的輸入文本來說明

1+2

這是一個加法的算式，由兩個數字與中間的運算符號(加號)組成。

將上述的字串組合用BNF表示，可以寫成：

<加法> ::= <數字> <+> <數字> 

如果你不太清楚為什麼是這樣表示的話，可以到前天的文章複習一下。

然後，我們要將上述的BNF表示式轉成Yacc的語法。

expr: NUMBER '+' NUMBER

我們將加法的規則命名為expr，數字則是用標記的token表示。

最後，我們將規則對應到的執行程式寫在最後。

expr: NUMBER '+' NUMBER { printf("Result: %d\n", ($1+$3)); } ;

這裡我們碰到了兩個奇怪的東西 $1 跟 $3。這個東西叫做Inherited Attributes(繼承屬性)。

在Yacc語法中，我們利用編號的方式來記載規則中的每一個屬性單位。
在本例中，$1與$3表示規則中從左方算起的第一與第三個token，也就是兩個數字。

那麼，在左方的非終端符號”expr”也可以用這種方式表示嗎?

可以，使用的Inherited Attributes為$$。
以下的例子說明了不同單位所對應的屬性：

expr: NUMBER '+' NUMBER
 $$    $1    $2   $3

因此，我們可以把剛剛的執行程式改寫成這樣：

expr: NUMBER '+' NUMBER { $$ = $1 + $3; printf("Result: %d\n", $$); } ;

介紹完Yacc的基本語法後，我們可以繼續實作這個簡易計算機了。

範例 - 簡易計算機1 (2 of 3)

說明

請實作出一個簡易的計算機，計算出兩個正整數的加法，並回傳結果。

本範例分成以下三部分：

1. 完成Lex檔案的實作 (已完成)
2. 完成Yacc檔案的實作 (本日目標)
3. 完成主程式的實作

程式實作

Definitions

跟lex一樣，由於主程式是單獨寫在一個獨立的檔案中，故我們在此匯入主程式的標頭檔。

另外，我們會把yyerror yylex yyparse這三個function宣告在這裡。

我們也在此定義表示整數的token(命名為NUMBER)。

%{
#include "main.h"

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

%}

%token NUMBER

Rules

我們在此定義加法的規則，命名為”expr”。

當讀取到 ”數字 +號 數字” 的字串序列時，便將兩數相加，並印出結果。

%%

expr:
      NUMBER '+' NUMBER   { $$ = $1 + $3; printf("%d\n", $$); }
    ;

Subroutines

由於我們將主程式移到另一個檔案了，這邊就只要寫yyerror。

如果不想要作error handling，這邊就不用寫 (記得%%還是要加)，前面也不用作definition。

%%

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

到這裡，我們就完成yacc檔案的程式撰寫了。這也是整個範例中最困難的部分，恭喜！

完整程式碼

%{
#include "main.h"

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

%}

%token NUMBER

%%

expr:
      NUMBER '+' NUMBER   { $$ = $1 + $3; printf("%d\n", $$); }
    ;

%%

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

結語

介紹完Yacc語法及檔案架構後，我們成功完成了Parser中Yacc的部分。

明天我們要來看最後一部分 - 主程式，以及如何編譯與執行整份程式。

參考資料

• Undefined reference yyparse c++