本篇內容

• 介紹 Yacc語法中的優先級: left & right
• 範例 - 簡易計算機4

優先級

我們從昨天的規則衝突中可以發現，部分衝突的發生原因，在於當字串組合可以被兩種以上的規則匹配時，系統不知道要匹配哪一項規則。因此，我們可以定義規則的階級差異，在發生衝突時，優先匹配位階較高的規則，便可以避免衝突發生。規則的階級定義有很多種方式，今天先來看看其中一種：left & right。

優先級(1) left & right

從昨天的例子，我們發現shift/reduce conflict主要發生在字串組同時匹配到shift跟reduce操作的時候。在做數值運算時，先做前面的運算或是先做後面的運算，運算結果有可能會有很大的不同。

在做連續加減法的運算時，在沒有括號的情況下，主要的運算方式為由左至右逐步計算。
因此，我們只要在符合運算的序列出現時，就優先做計算，便可以解決衝突的問題。

在Lex中，我們可以利用”left”(左相關)跟”right”(右相關)這兩個語法。來看下面這個例子：

1 + 2 + 3

在上面的式子中，兩個+號有相同的優先級。那哪個部分會先被運算呢?

如果是定義左相關，那就會由左向右運算。

%left '+'
// operation: (1 + 2) + 3

同理，若是定義右相關，那就會由右方先計算。

%right '+'
// operation: 1 + (2 + 3)

如此一來，衝突的問題就解決了。

接著，我們要讓計算機可以進行四則運算。四則運算有個重要的規則：先乘除後加減。然而若是按照下面這個寫法，加減乘除的規則位階相同，無法達成”先計算乘除法”的要求，且會造成規則衝突。

expr:
      NUMBER                { $$ = $1; }
    | expr '+' expr         { $$ = $1 + $3; }
    | expr '-' expr         { $$ = $1 - $3; }
    | expr '*' expr         { $$ = $1 * $3; }
    | expr '/' expr         { $$ = $1 / $3; }

因此，我們除了定義加減法之外，也要定義乘除法，並且比加減法具有更高的優先級。寫法如下：

%left '+' '-'
%left '*' '/'

若是有多個符號要被定義優先級，則後定義的符號具有較高的優先級。在上面的寫法中，”乘法與除法”比”加法與減法”具有較高的優先級。

到此，我們就定義好四則運算的兩大規則：

1. 先乘除後加減
2. 位階相同時，由左而右計算

範例 - 簡易計算機4

說明

請實作出一個簡易的計算機，能夠對多個正整數做四則運算(加減乘除)，符合運算優先順序為小括號→乘除法→加減法，並回傳結果。

程式實作

Lex

• 本次目標是實作四則運算，故有四種運算符號
• 本次運算包含小括號，需要回傳其token

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

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

%%

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

%%

int yywrap(void) {
    return 1;
}

Yacc

• 在Definition區塊新增優先級
• 新增乘法與除法的Rules
• 新增小括號的Rule

%{
#include "main.h"

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

%}

%token NUMBER
%left '+' '-'
%left '*' '/'

%%

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

expr:
      NUMBER                { $$ = $1; }
    | expr '+' expr         { $$ = $1 + $3; }
    | expr '-' expr         { $$ = $1 - $3; }
    | expr '*' expr         { $$ = $1 * $3; }
    | expr '/' expr         { $$ = $1 / $3; }
    | '(' expr ')'          { $$ = $2; }
    ;

%%

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

執行結果

輸入內容

4 * 7 + 88 / 4 =

輸出結果

Result: 50

結語

今天我們介紹了優先級left & right，可以規範位階相同或不同時的規則匹配順位。

參考資料

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