我們從昨天的規則衝突中可以發現,部分衝突的發生原因,在於當字串組合可以被兩種以上的規則匹配時,系統不知道要匹配哪一項規則。因此,我們可以定義規則的階級差異,在發生衝突時,優先匹配位階較高的規則,便可以避免衝突發生。規則的階級定義有很多種方式,今天先來看看其中一種: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 '*' '/'
若是有多個符號要被定義優先級,則後定義的符號具有較高的優先級。在上面的寫法中,”乘法與除法”比”加法與減法”具有較高的優先級。
到此,我們就定義好四則運算的兩大規則:
請實作出一個簡易的計算機,能夠對多個正整數做四則運算(加減乘除),符合運算優先順序為小括號→乘除法→加減法,並回傳結果。
%{
#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;
}
%{
#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,可以規範位階相同或不同時的規則匹配順位。