YACC語法：運算符優先級問題

Question

我試圖得到：（20 +（-3））* 3 /（20/3）/ 2等於4，現在，它等於17

所以基本上（20/3），然後除以2，然後除以[（20/3）/ 2]，然後乘以17.不知道如何改變我的語法/規則/優先順序讓它正確讀取。任何指導將不勝感激，謝謝。

%% 

start:    PROGRAMtoken IDtoken IStoken compoundstatement 

compoundstatement:   BEGINtoken {print_header();} statement semi ENDtoken {print_end();} 

semi:         SEMItoken statement semi 
             | 

statement:        IDtoken EQtoken exp 
             { regs[$1] = $3; } 

             | PRINTtoken exp 
             { cout << $2 << endl; } 

             | declaration 

declaration:      VARtoken IDtoken comma 

comma:        COMMAtoken IDtoken comma 
            | 

exp:         exp PLUStoken term 
             { $$ = $1 + $3; } 

             | exp MINUStoken term 
             { $$ = $1 - $3; } 

             | term 
             { $$ = $1; } 

             | MINUStoken term 
             { $$ = -$2;} 

term:         factor 
             { $$ = $1; 
             } 
             | factor TIMEStoken term 
             {$$ = $1 * $3; 
             } 
             | factor DIVIDEtoken term 
             { $$ = $1/$3; 
             } 

factor:         ICONSTtoken 
             { $$ = $1;} 
             | IDtoken 
             { $$ = regs[$1]; } 
             | LPARENtoken exp RPARENtoken 
             { $$ = $2;} 

%% 

我的標記和類型的樣子：

%token BEGINtoken 
%token COMMAtoken 

%left DIVIDEtoken 
%left TIMEStoken 

%token ENDtoken 
%token EOFtoken 
%token EQtoken 

%token <value> ICONSTtoken 
%token <value> IDtoken 

%token IStoken 
%token LPARENtoken 

%left PLUStoken MINUStoken 

%token PRINTtoken 
%token PROGRAMtoken 
%token RPARENtoken 
%token SEMItoken 

%token VARtoken 

%type <value> exp 
%type <value> term 
%type <value> factor 

Answer 1

你真的希望有人努力給你一個答案，這就是爲什麼問題一直圍繞掛了一年。請閱讀以下幫助頁面：https://stackoverflow.com/help/how-to-ask，特別是關於的部分，簡化的問題。語法文件中有很多規則不需要重現問題。我們並不需要：

%token BEGINtoken 
%token COMMAtoken 
%token ENDtoken 
%token EOFtoken 
%token EQtoken 
%token <value> IDtoken 
%token IStoken 
%token PROGRAMtoken 
%token VARtoken 
%% 
start:    PROGRAMtoken IDtoken IStoken compoundstatement 

compoundstatement:   BEGINtoken {print_header();} statement semi ENDtoken {print_end();} 

semi:         SEMItoken statement semi 
             | 
             | declaration 

declaration:      VARtoken IDtoken comma 

comma:        COMMAtoken IDtoken comma 
            | 

你可能只是刪除這些標記和規則去操作優先發布的心臟。我們不需要任何變量，聲明，分配或程序結構來說明失敗。學習簡化是心臟的主管調試，從而編程。如果你已經完成了這個簡化，更多的人會去回答。我是說這不是爲了OP，而是針對那些會遇到類似問題的人！

我想知道什麼學校設置這個任務，因爲我已經看到了SO圍繞着同樣沉悶的問題相當數量的YACC問題。我懷疑每年會有更多的人來這裏，所以回答這個問題將會對他們有所幫助。我知道在檢查語法時出現了什麼問題，但爲了測試我的解決方案，我必須編寫一個工作的詞法分析器，一些符號表例程，一個主程序和其他輔助代碼。再次，解決問題的另一個威懾力量。

讓我們找到問題的核心。你有這些令牌聲明：

%left DIVIDEtoken 
%left TIMEStoken 
%left PLUStoken MINUStoken 

這是告訴yacc，如果任何規則不明確的是，運營商聯營離去。您的這些運營商的規則是：

exp:         exp PLUStoken term 
             { $$ = $1 + $3; } 

             | exp MINUStoken term 
             { $$ = $1 - $3; } 

             | term 
             { $$ = $1; } 

             | MINUStoken term 
             { $$ = -$2;} 

term:         factor 
             { $$ = $1; 
             } 
             | factor TIMEStoken term 
             {$$ = $1 * $3; 
             } 
             | factor DIVIDEtoken term 
             { $$ = $1/$3; 
             } 

然而，這些規則不模糊，因此不需要運算符優先級的聲明。 Yacc將遵循您使用的非模糊語法。這些規則的編寫方式，告訴yacc運營商具有正確的關聯性，這與你想要的相反。現在，從你的例子中的簡單算術可以清楚地看出，操作符是以正確的關聯方式進行計算的，而你想要的是相反的。那裏真的有很大的線索嗎？

好的。如何改變關聯性？一種方法是再次使語法不明確，以便使用%left聲明，或者只是翻轉規則以反轉關聯性。這就是我所做的：

exp:         term PLUStoken exp 
             { $$ = $1 + $3; } 

             | term MINUStoken exp 
             { $$ = $1 - $3; } 

             | term 
             { $$ = $1; } 

             | MINUStoken term 
             { $$ = -$2;} 

term:         factor 
             { $$ = $1; 
             } 
             | term TIMEStoken factor 
             {$$ = $1 * $3; 
             } 
             | term DIVIDEtoken factor 
             { $$ = $1/$3; 
             } 

你看到我在那裏做了什麼？我圍繞操作員旋轉了語法規則。

現在爲更多的免責聲明。我說這是一個啞鍛鍊。動態解釋表達式對yacc工具的使用很差，而不是實際編譯器或解釋器中發生的情況。在現實的實現中，將構建一個分析樹並在樹行走期間執行值計算。這樣可以解決未聲明的變量問題（這也是本次練習中的問題）。使用regs數組來存儲值也是愚蠢的，因爲顯然有一個輔助符號表用於返回符號的唯一整數ID。在真正的編譯器/解釋器中，這些值也將存儲在該符號表中。

我希望本教程能幫助更多的學生在他們的課堂上理解這些解析問題。