爲什麼在某些情況下，我不能使用令牌作爲優先級標記

假設此代碼的工作：爲什麼在某些情況下，我不能使用令牌作爲優先級標記

left '*' 
left '+' 

expr: expr '+' expr 
    | expr '*' expr 
    ;

我想定義的其他優先級標記，如：

left MULTIPLY 
left PLUS 

expr: expr '+' expr %prec PLUS 
    | expr '*' expr %prec MULTIPLY 
    ;

然而，這並不實際上有效。

我想這兩種形式應該是等價的，但是，它們不是。

這不是實際問題。我只想知道這種現象的原因和原理。

謝謝。

來源

2012-06-10 Shou Ya

你說你不是在試圖解決一個特定的實際問題。從你的問題來看，我對你如何使用優先級標記有點困惑。

我想你會發現你不需要經常使用優先級標記。對讀者來說，通常會更簡單，重寫語法，以便明確說明優先順序。爲了給乘法和除法的優先級高於加減法，你可以做這樣的事情（例如改編自約翰·萊文，法& YACC 2/E，1992年）：

%token NAME NUMBER 

%% 

stmt : NAME '=' expr 
    | expr 
    ; 

expr : expr '+' term 
    | expr '-' term 
    | term 
    ; 

term : term '*' factor 
    | term '/' factor 
    | factor 
    ; 

factor : '(' expr ')' 
     | '-' factor 
     | NUMBER 
     ;

在你的榜樣，和MULTIPLY不是真正的標記;您不能與'+'和'*'交替使用它們。萊文稱它們爲僞令牌。他們在那裏將您的作品鏈接回您用%left和%nonassoc聲明定義的優先順序列表。他給出瞭如何使用%prec這個例子給一元減法即使高優先級「 - 」標記具有較低的優先級：

%token NAME NUMBER 
%left '-' '+' 
%left '*' '/' 
%nonassoc UMINUS 

%% 

stmt : NAME '=' expr 
    | expr 
    ; 

expr : expr '+' expr 
    | expr '-' expr 
    | expr '*' expr 
    | expr '/' expr 
    | '-' expr %prec UMINUS 
    | '(' expr ')' 
    | NUMBER 
    ;

綜上所述，我建議以下我的第一個代碼示例的模式，而比第二;使語法清晰。

來源

2012-06-11 23:29:18

Shift-reduce衝突是試圖減少生產與移動令牌並移動到嵌套狀態之間的衝突。當Bison解決衝突時，它不會比較兩個規則並選擇其中的一個 - 比較它想要減少的一個規則和您想要在其他規則中移動的標記。如果你有兩個規則轉移，這可能是更清楚：

expr: expr '+' expr 
    | expr '*' expr 
    | expr '*' '*' expr

的原因，所有這一切令人困惑的是野牛的方式給出了一個優先級，以「減量化」原則是將其與令牌（最後一個終端關聯在默認規則或prec聲明中的令牌中），然後使用優先級表將該令牌與您嘗試移動的令牌進行比較。基本上，預先聲明只對衝突的「減少」部分有意義，並且他們不計入換班部分。看到這個

一種方法是使用下面的語法

command: IF '(' expr ')' command    %prec NOELSE 
     : IF '(' expr ')' command ELSE command

在這個語法，你需要減少的第一條規則或移位ELSE令牌之間做出選擇。您可以通過優先考慮'）'標記和ELSE標記，或者使用prec聲明並優先考慮NOELSE而不是'）來做到這一點。如果您嘗試給第二個預先聲明，它將被忽略，Bison將繼續嘗試在優先表中查找ELSE標記的優先級。

來源

2013-09-21 14:13:50 hugomg

Yacc優先規則並不是真正關於表達式的優先級，儘管它們可以用於此。相反，它們是明確解決轉變/減少衝突（並且僅僅轉移/減少衝突）的一種方式。

瞭解它是如何工作的，需要了解移位/縮小（自下而上）解析是如何工作的。基本的想法是，您從輸入中讀取令牌符號並將這些令牌推送（「移位」）到堆棧上。當堆棧頂部的符號與語法中某條規則的右側相匹配時，您可以「減少」規則，從堆棧中彈出符號並用規則左側的單個符號替換它們。重複這個過程，移動令牌並減少規則，直到讀完整個輸入並將其縮減爲開始符號的單個實例，此時您已成功解析了整個輸入。

上述問題（以及解析器生成器的整個機制正在解決什麼問題）是知道何時可以減少規則與何時移動令牌（如果兩者都可能的話）。解析器生成器（yacc或bison）構建了一個狀態機器，用於跟蹤哪些符號已被移位，從而知道當前可能有哪些「部分匹配」規則，並且限制只能移動到那些可以匹配更多此類規則的標記。如果所討論的語法不是LALR（1），那麼這不起作用，所以在這種情況下，yacc/bsion報告會移動/減少或減少/減少衝突。

該優先規則解決轉移減少衝突的工作是通過爲語法中的某些標記和規則分配優先級。每當一個要移動的標記和一個要減少的規則之間有一個移位/減少衝突，並且BOTH具有優先級時，它將執行具有更高優先級的任何一個。如果它們具有相同的優先級，則它查看與優先級相關聯的標記%left/%nonassoc-%left意味着減少，%right意味着移位，並且%nonassoc意味着既不做也將它視爲語法錯誤。

唯一棘手的剩餘位是令牌和規則如何獲得它們的優先級。令牌從它們所在的%left/%right/%nonassoc指令中獲得它們，這也設置了排序。規則優先於%prec指令或優先於右側最右側的終端。因此，當您有：

%left '*' 
%left '+' 

expr: expr '+' expr 
    | expr '*' expr 
    ;

您設置的'*'和'+'與%left指令的優先級，並且這兩個規則得到這些令牌的優先級。

當你有：

%left MULTIPLY 
%left PLUS 

expr: expr '+' expr %prec PLUS 
    | expr '*' expr %prec MULTIPLY 
    ;

你設置的令牌MULTIPLY和的優先級，然後制定明確的規則有那些優先級。但是，您沒有爲令牌'*'和'+'設置任何優先級。因此，當兩個規則中的一個與'*'或'+'之間存在轉換/減少衝突時，由於令牌沒有優先級，因此優先級不會解決它。

來源

2013-09-21 20:27:50

爲什麼在某些情況下，我不能使用令牌作爲優先級標記

回答

相關問題