A. 計算機考研：數據結構常用演算法解析(3)
第三章
例如：Exp=a*b+(c-d/e)*f
若 Exp=a*b+(c-d/e)*f 則它的
前綴式為： +*ab*-c/def
中綴式為： a*b+c-d/e*f
後綴式為： ab*cde/-fx+
綜合比較它們之間的關系可得下列結論：
1.三式中的 「操作數之間的相對次序相同」;
(二叉樹的三種訪問次序中，葉子的相對訪問次序是相同的)
2.三式中的 「運算符之間的的相對次序不同」;
3.中綴式丟失了括弧信息，致使運算的次序不確定;
(而前綴和後綴運算只需要一個存儲操作數的棧，而中綴求值需要兩個棧，符號棧和操
作數棧)
4.前綴式的運算規則為：連續出現的兩個操作數和在它們之前且緊靠它們的運算符構成一個最小表達式;
5.後綴式的運算規則為：
·運算符在式中出現的順序恰為表達式的運算順序;
·每個運算符和在它之前出現且緊靠它的兩個操作數構成一個最小表達式;
6.中綴求值的運算規則：
如果是操作數直接入棧。
如果是運算符。這與當前棧頂比較。個如果比當前棧頂高，則入棧，如果低則說明當前棧頂是最高的必須把他先運算完了。用編譯原理的話就是說當前棧頂已經是最左素短語了)
其實中綴表達式直接求值和把中綴表達式轉化成後綴表達式在求值的過程驚人的相似，只不過是直接求值是求出來，而轉化成後綴是輸出來。
中綴表達式直接求值演算法：
OPNDType EvalueExpression()
{ //OPTR 和OPND分別為運算符棧和操作數棧
InitStack(OPTR);Push(OPTR,』#』);
InitStack(OPND);c=getchar();
While(c!=』#』|| GetTop(OPTR)!=』#』)
{
If(!IN(c,OP) ) //如果是操作數，直接入操作數棧
{ push(OPND,c);
c=getchar();
}
Else //如果是運算符，則與當前的棧頂比較
{
Switch(Precede(GetTop(OPTR),c))
{
Case 『<』: push(OPTR,c);//比當前棧頂高，這入棧
c=getchar();
break;
Case 』= 』:Pop(OPTR,x); //在我們設計的優棚肆枯先級表中，
c=getchar(); //只有』(』和』)』存在相等的情況，
break; //而在規約中間只存在『(』『)』
//所以我們直接把』(』彈出就可以了
Case 『>』: //比當前棧頂低，則要把棧頂先運算完(先規約)
pop(OPTR,theta); //把棧頂運算符彈出
Pop(OPND,b); //取出操作數，並且是前操作數雹搭
Pop(OPND,a); //在下面(棧的先進後出)
Push(OPND,Operate(a,theta,b)); //運算的結果入棧
//(他是其他運算符的操作數)
Break;
}//Switch
}//鏈洞else
}//whild
Return GetTop(OPND);//操作數棧中最後剩下的就是整個表達式的結果了。
}
考研有疑問、不知道如何總結考研考點內容、不清楚考研報名當地政策，點擊底部咨詢官網，免費領取復習資料：https://www.87dh.com/xl/
B. 編譯原理-LL1文法詳細講解
我們知道2型文法( CFG )，它的每個產生式類型都是 α→β ,其中 α ∈ VN , β ∈ (VN∪VT)*。
例如, 一個表達式的文法:
最終推導出 id + (id + id) 的句子，那麼它的推導過程就會構成一顆樹，即 CFG 分析樹：
從分析樹可以看出，我們從文法開始符號起，不斷地利用產生式的右部替換產生式左部的非終結符，最終推導出我們想要的句子。這種方式我們稱為自頂向下分析法。
從文法開始符號起，不斷用非終結符的候選式(即產生式)替換當前句型中的非終結符，最終得到相應的句子。
在每一步推導過程中，我們需要做兩個選擇:
因為一個句型中，可能存在多個非終結符，我們就不確定選擇那一個非終結符進行替換。
對於這種情況，我們就需要做強制規定，每次都選擇句型中第一個非終結符進行替換(或者每次都選擇句型中最後一個非終結符進行替換)。
自頂向下的語法分析採用最左推導方式，即總是選擇每個句型的最左非終結符進行替換。
最終的結果是要推導出一個特定句子(例如 id + (id + id) )。
我們將特定句子看成一個輸入字元串，而每一個非終結符對應一個處理方法，這個處理方法用來匹配輸入字元串的部分，演算法如下:
方法解析:
這種方式稱為遞歸下降分析( Recursive-Descent Parsing )：
當選擇的候選式不正確，就需要回溯( backtracking )，重新選擇候選式，進行下一次嘗試匹配。因為要不斷的回溯，導致分析效率比較低。
這種方式叫做預測分析( Predictive Parsing )：
要實現預測分析，我們必須保證從文法開始符號起，每一個推導過程中，當前句型最左非終結符 A 對於當前輸入字元 a ,只能得到唯一的 A 候選式。
根據上面的解決方法，我們首先想到，如果非終結符 A 的候選式只有一個以終結符 a 開頭候選式不就行了么。
進而我們可以得出，如果一個非終結符 A ，它的候選式都是以終結符開頭，並且這些終結符都各不相同，那麼本身就符合預測分析了。
這就是S_文法，滿足下面兩個條件:
例子:
這就是一個典型的S_文法，它的每一個非終結符遇到任一終結符得到候選式是確定的。如 S -> aA | bAB , 只有遇到終結符 a 和 b 的時候，才能返回 S 的候選式，遇到其他終結符時，直接報錯，匹配不成功。
雖然S_文法可以實現預測分析，但是從它的定義上看，S_文法不支持空產生式(ε產生式)，極大地限制了它的應用。
什麼是空產生式(ε產生式)？
例子
這里 A 有了空產生式，那麼 S 的產生式組 S -> aA | bAB ，就可以是 a | bB ,這樣 a , bb , bc 就變成這個文法 G 的新句子了。
根據預測分析的定義，非終結符對於任一終結符得到的產生式是確定的，要麼能獲取唯一的產生式，要麼不匹配直接報錯。
那麼空產生式何時被選擇呢？
由此可以引入非終結符 A 的後繼符號集的概念:
定義: 由文法 G 推導出來的所有句型，可以出現在非終結符 A 後邊的終結符 a 的集合，就是這個非終結符 A 的後繼符號集，記為 FOLLOW(A) 。
因此對於 A -> ε 空產生式，只要遇到非終結符 A 的後繼符號集中的字元，可以選擇這個空產生式。
那麼對於 A -> a 這樣的產生式，只要遇到終結符 a 就可以選擇了。
由此我們引入的產生式可選集概念:
定義: 在進行推導時，選用非終結符 A 一個產生式 A→β 對應的輸入符號的集合，記為 SELECT(A→β)
因為預測分析要求非終結符 A 對於輸入字元 a ,只能得到唯一的 A 候選式。
那麼對於一個文法 G 的所有產生式組，要求有相同左部的產生式，它們的可選集不相交。
在 S_文法基礎上，我們允許有空產生式，但是要做限制:
將上面例子中的文法改造:
但是q_文法的產生式不能是非終結符打頭，這就限制了其應用，因此引入LL(1)文法。
LL(1)文法允許產生式的右部首字元是非終結符，那麼怎麼得到這個產生式可選集。
我們知道對於產生式:
定義: 給定一個文法符號串 α ， α 的 串首終結符集 FIRST(α) 被定義為可以從 α 推導出的所有串首終結符構成的集合。
定義已經了解清楚了，那麼該如何求呢？
例如一個文法符號串 BCDe , 其中 B C D 都是非終結符， e 是終結符。
因此對於一個文法符號串 X1X2 … Xn ，求解 串首終結符集 FIRST(X1X2 … Xn) 演算法:
但是這里有一個關鍵點，如何求非終結符的串首終結符集？
因此對於一個非終結符 A , 求解 串首終結符集 FIRST(A) 演算法:
這里大家可能有個疑惑，怎麼能將 FIRST(Bβ) 添加到 FIRST(A) 中，如果問文法符號串 Bβ 中包含非終結符 A ，就產生了循環調用的情況，該怎麼辦?
對於 串首終結符集 ，我想大家疑惑的點就是，串首終結符集到底是針對 文法符號串 的，還是針對 非終結符 的，這個容易弄混。
其實我們應該知道， 非終結符 本身就屬於一個特殊的 文法符號串 。
而求解 文法符號串 的串首終結符集，其實就是要知道文法符號串中每個字元的串首終結符集:
上面章節我們知道了，對於非終結符 A 的 後繼符號集 :
就是由文法 G 推導出來的所有句型，可以出現在非終結符 A 後邊的終結符的集合，記為 FOLLOW(A) 。
仔細想一下，什麼樣的終結符可以出現在非終結符 A 後面，應該是在產生式中就位於 A 後面的終結符。例如 S -> Aa ，那麼終結符 a 肯定屬於 FOLLOW(A) 。
因此求非終結符 A 的 後繼符號集 演算法：
如果非終結符 A 是產生式結尾，那麼說明這個產生式左部非終結符後面能出現的終結符，也都可以出現在非終結符 A 後面。
我們可以求出 LL(1) 文法中每個產生式可選集:
根據產生式可選集，我們可以構建一個預測分析表，表中的每一行都是一個非終結符，表中的每一列都是一個終結符，包括結束符號 $ ，而表中的值就是產生式。
這樣進行語法推導的時候，非終結符遇到當前輸入字元，就可以從預測分析表中獲取對應的產生式了。
有了預測分析表，我們就可以進行預測分析了，具體流程:
可以這么理解：
我們知道要實現預測分析，要求相同左部的產生式，它們的可選集是不相交。
但是有的文法結構不符合這個要求，要進行改造。
如果相同左部的多個產生式有共同前綴，那麼它們的可選集必然相交。
例如:
那麼如何進行改造呢？
其實很簡單，進行如下轉換:
如此文法的相同左部的產生式，它們的可選集是不相交，符合現預測分析。
這種改造方法稱為 提取公因子演算法 。
當我們自頂向下的語法分析時，就需要採用最左推導方式。
而這個時候，如果產生式左部和產生式右部首字元一樣(即A→Aα)，那麼推導就可能陷入無限循環。
例如:
因此對於:
文法中不能包含這兩種形式，不然最左推導就沒辦法進行。
例如:
它能夠推導出如下:
你會驚奇的發現，它能推導出 b 和 (a)* (即由 0 個 a 或者無數個 a 生成的文法符號串)。其實就可以改造成:
因此消除 直接左遞歸 演算法的一般形式：
例如:
消除間接左遞歸的方法就是直接帶入消除，即
消除間接左遞歸演算法：
這個演算法看起來描述很多，其實理解起來很簡單：
思考 : 我們通過 Ai -> Ajβ 來判斷是不是間接左遞歸，那如果有產生式 Ai -> BAjβ 且 B -> ε ,那麼它是不是間接左遞歸呢？
間接地我們可以推出如果一個產生式 Ai -> αAjβ 且 FIRST(α) 包括空串ε，那麼這個產生式是不是間接左遞歸。
C. 編譯原理中的文法的產生式的括弧有什麼用
加上括弧，是讓編程渣談磨語侍悄言機器 最先識別。
就不用 從 E 執行到 F——EIid
先執行 括弧如斗裡面的
D. 編譯原理：真子串、前綴的問題
Let X be a set, and w∈X∗ be a word, i.e. an element of the free monoid on X. A word v∈X∗ is called prefix of w when a second word z∈X∗ exists such thatx=vz. A proper prefix of a word u is a prefix v of u not equal to u (sometimes v is required to be non-empty).
E. 編譯原理 無法提取左公因子,都有公共前綴
就是有公共前綴才可以提取左公因子啊……
bool -> expr expr'
expr' -> e
| < expr
| <= expr
| > expr
| >= expr
後面幾個比較操作符如果還算公因子的話，還可以繼續提：
用expr1 代替 < expr 和 <= expr，刪除這兩個右部，添加右部 <expr1，添加產生式expr1-> expr|= expr
用expr2 代替 > expr 和 >= expr，刪除這兩個右部，添加右部 >expr2，添加產生式expr2-> expr|= expr
F. 編譯原理lr0和slr1的區別
語法分析有自上而下和自下而上兩種分析方法其中自上而下：遞歸下降，LL(1)自下而上：LR(0),SLR(1),LR(1),LALR(1)
LR需要構造一張LR分析表，此表用於當面臨輸入字元時，將它移進，規約（即自下而上分析思想），接受還是出錯。
LR(0)找出句柄前綴，構造分析表，然後根據輸入符號進行規約。 SLR(1)使用LR(0)時若有沖突，不知道規約，移進，活移進哪一個，所以需要向前搜索，則只把有問題的地方向前搜索一次。 LR(1)1.在每個項目中增加搜索符。2.舉個列子如有A->α.Bβ，則還需將B的規則也加入。 LALR(1)就是假如兩個產生式集相同則將它們合並為一個，幾合並同心集。
G. 求助一個C語言的問題 int i=3； 則k=（i++）+（i++）+（i++）；執行過後k的
這個問題給你說了答案，以後你還會遇到很多次這樣的問題。
不如直接告訴你原理來得實在。
關於++i，i++的問題看下面看完你再不會，打死我吧！)，請認真讀完。然後再回來看你這道題。完全就是小兒科。
++是C++的自增運算符，作用是使變數自加1；——是自減運算符，作用是使變數自減1.++和——有兩種用法，一種是前綴用法，一種是後綴用法。前綴用法如：++i、——i ，後綴用法如i++、i——，前綴用法跟後綴用法的差別在於前綴時++i的值為完成i加1後的值，——i為完成i減1後的值。例如：假設i的初值為3，執行cout<<++i<<endl；輸出結果為4，而執行cout<<i++<<endl；輸出結果為3.——運算符同理。這是世人皆知的常識，我們不再討論，現在我們來討論一點有趣的東西，看如下代碼：
#include <iostream>
using namespace std;
int main()
{
int i=3;
cout<<(i++)+(i++)+(i++)<<endl;
cout<<i<<endl;
return 0;
}
問，第一次和第二次輸出的結果分別是多少？
有人說，是12和6.理由是，表達式從左至右開始計算，因為第一個括弧內++運算符是後綴用法，i的初值為3，所以，第一個括弧的值是3，計算完第一個括弧之後，i自加1，變成4，然後計算第二個括弧，第二個括弧里的++也是後綴用法，所以，值為4，執行完第二個括弧後，i再加1，變成5，接下計算第三個括弧，第三個括弧里的++也是後綴用法，所以，第三個括弧的值為5，然後計算第三個括弧相加的和，即3+4+5=12.這個理由看起來不錯，似乎應當是這樣。然而，運行結果卻讓人大跌眼鏡，竟然是9和6.這是怎麼回事呢？說起來也很簡單，和州這是因為很多編譯系統規定，在遇源渣到一條計算表達式中同時出現若干i++、i——的情況時，在當前語句中並不執行i的自增和自減，i的初值是多少，i++和i——的值就是多少，當這條表達式執行完成之後，再將i連續自加或自減若干次。
再看如下代碼：
#include <iostream>
using namespace std;
int main()
{
int i=3;
cout<<(++i)+(++i)+(++i)<<endl;
cout<<i<<endl;
return 0;
}
問，第一次和第二次輸出的結果分別是多少？
有人說，結果應該是4+5+6=15和6.理由我想大家都想明白，我就不多說了。還有人總結了上例的雹棚悄經驗，認為，輸出結果應該是9和6.我們來運行一下這個程序，看看誰說得對……
好了，運行結果出來了，不過這不是什麼好結果，可能很多人看完會抓狂，結果盡然是神鬼莫測的18和6.為什麼呢？道理跟上例差不多，那就是很編譯系統規定，連續多個前綴式++和——運算符出現在同一個運算表達式中時，先將變數連續自加或自減N次，然後判定++i的值為i+N.
為了驗證上面的說法，請看下面的代碼：
#include <iostream>
using namespace std;
int main()
{
int i=3;
cout<<(++i)+(i++)+(++i)<<endl;
cout<<i<<endl;
return 0;
}
按照我們上面的推測，第一個輸出語句應當是這樣執行的：首先，掃描整條運算表達式（++i）+（i++）+（++i），發現有兩處++的前綴式用法，於是，將i連續自加兩次，然後開始計算表達式，第一個括弧是++i，判定為5，第二個括弧是i++，判定值為5，第三個括弧是++i判定值為5，最後，計算結果5+5+5=15.因為表達式中有一個i++，所以執行計算完之後將i的值再自加1，變為6.
運行程序，驗證一下，果然，結果就是15和6.
下面在來討論一下網上很多C++論壇里討論得很多的int i=3；問++i+++i+i++的值是多少的問題。
我看到CSDN里也有人在討論這個問題，很多人在回帖，答案似乎多種多樣，有說是12的，有說是18的，更有說是9的，更有一條回帖十分搞笑——「答案是×××，這是很早以前我的一個很牛×的老師教我的解法得出的結果」。我很無語。學過編譯原理的人都知道，「++i+++i」這一段根本就無法解析，編譯系統從左至右掃描整條語句，先遇到++i，判斷出來是一個i的前綴自加運算，然後接著掃描，遇到一個+，+是一個二目運算符，它的左邊已經有一個運算數++i了，系統就向右搜索第二個運算數，又遇到一個+，++比+的運算級別要高，這時，編譯系統就將兩個+看成一個整體來處理，既然是++，編譯系統就認定，肯定它的左邊或右邊有一個變數，編譯系統先搜索左邊，發現有一個 i，是個變數，於是它就將i和其後的++組合起來，這時問題就發生了，也就是說第一個i被編譯系統綁架到它後面的++那裡去了，那麼i前面的++是個什麼東西呢？編譯系統是無法搞明白的，它會倒回去重新搜索++前面是否有左值，發現沒有，因此它就認為++是一個缺少左值的自增運算符，於是提示提示用戶：'++' needs l-value
我們寫個程序驗證一下上面的推測：
#include <iostream>
using namespace std;
int main()
{
int i=3;
cout<<++i+++i+i++<<i<<endl;
cout<<i<<endl;
return 0;
}
果然，編譯時有一個錯誤，提示error C2105： '++' needs l-value ，證實了我們的推測。這個問題的討論使我們得出一個結論：如果一個變數Ni的兩側都有++或——運算符並且Ni左邊的表達式不能分解成X+或X-的形式，那麼編譯就會出錯，X是有值變數。結論有點繞口，舉例說明吧：
程序1
#include <iostream>
using namespace std;
int main()
{
int i=3;
cout<<i+++i++<<endl;
cout<<i<<endl;
return 0;
}
程序1說明：表達式i+++i++中第二個i的左右兩側都有++，於是我們看第二個i的左側，左側是i+++，可以分解為（i++）+，其中「（i++）」是有值變數，符合X+的形式，因此i+++i++是合法表達式，可以通過編譯。
程序2
#include <iostream>
using namespace std;
int main()
{
int i=3;
cout<<++i+++i<<endl;
cout<<i<<endl;
return 0;
}
程序2說明：表達式++i+++i中第一個i的左右兩側都有++，於是我們看第一個i的左側，左側是++，不能分解成X+的形式，因此該表達式不合法。編譯時會提示：error C2105： '++' needs l-value
下面，我們再來討論一下關於i+++i的問題。曾經有人問，表達式i+++i在編譯時，編譯系統是怎麼拆分的？究竟是拆分成（i++）+i呢，還是拆分成i+（++i）。
這個問題本身的答案很簡單，是（i++）+i，不明白的自己去看編譯原理。這個問題令人感興趣之處並不在這里，不知道大家注意到i+（++i）這個表達式有什麼奇特的地方沒有？假設有如下程序：
#include <iostream>
using namespace std;
int main()
{
int i=3;
cout<<i+(++i)<<endl;
cout<<i<<endl;
return 0;
}
大家可以猜測一下程序的運行結果。
很多人可能會說是7和4，看起來的確像這樣。但是，非常遺憾，實驗再一次證明，你可能猜錯了，結果是8和4.為什麼是8和4呢？前面說過int i=3；cout<< （++i）+（++i） <<endl；的情況，編譯系統會先將i連續自加1兩次，然後將（++i）一律判定為5進行結算，輸出10.這里同理，編譯系統現將i自加1，然後再對i+（++i）做運算，（++i）的值判定為4，i的值也判定為4，因此計算結果是8.
下面我們來討論int i=3；cout<<i++<<「 and 」<<i++<<endl；的問題。首先請看如下程序，猜測輸出結果：
#include <iostream>
using namespace std;
int main()
{
int i=3;
cout<<i++<<" and "<<i++<<endl;
cout<<i<<endl;
return 0;
}
很多人認為輸出結果應該是「3 and 4」和5.我們把代碼復制到VC6.0或VC2005上編譯運行一下，看看結果……
好了，運行結束，結果是「4 and 3」和5.Oh！My God！Can you tell me why？上帝不會告訴你，我可以告訴你。這是因為很多編譯系統在處理輸出流時，是從右至左的。在上面的例子中，兩處i++處於同一個輸出序列中，編譯系統會先計算處於右側的第二個i++，這時i的值為3，因此右側i++的值為3，之後，i+1變成4，計算第一個i++的值為4，計算完之後將i的值再加1，最後才是輸出結果，所以輸出結果是4和3.
H. 將中序表達式轉化成後序表達式
首先這里涉及到了編譯原理的中間代碼結構的相關知識。
簡單的了解，如我們想要實現 A與B的相加，其有三種情況：
前綴表達式：運算符在前，則有 +AB
中綴表達式：運算符在中，則有 A+B
後綴表達式：運算符在後，則有 AB+
根據上述基本知識，後通過中綴表達式 a*b+c*(d-e)/f轉為後綴表達式的過程如下：
(1)根據算術符號的優先順序來進行操作即可，遇到括弧則先運算括弧中的式子，這與平時的運算過程其實是差不多的。
故轉換如下：
ab* + c*(de-)/f
ab* + c(de-)*/f
ab* + cde-*f/
ab* cde-*f/＋
最終後綴表達式： ab* cde-*f/＋
第二種方法：即是利用數據結構正宏源中的棧來進行解決，其的規則有如下：
遇到 」（ 「則入棧
遇到其他的絕逗操作數即abc等則加入表達式
遇到運算符（如+ - * /）則入棧，且需要注意，當處理到運算符的時候，需要將比當前處理的運算符優先順序高或同級的符號從棧中依次彈出，直到遇到比當前處理的舉態運算符優先順序低的或遇到 」( "才停止彈出。即若當前掃描到了 ＋號且棧頂存在＊號，因為乘號的運算符優先順序高於加號，則需要將＊號從棧中彈出加入表達式中，當然當加號遇到同優先順序的減號時，也要將當前處於棧頂的減號從棧頂彈出並加入表達式中。
當遇到「）」時則將已在棧中的「（」即左括弧之前的棧中符號依次彈出加入表達式中。
具體的流程可以查閱2014年計算機考研408真題的相關題型。
I. 編譯原理寫出表達式-a-(b*c/(c-d)+(-b)*a)的前綴式和後綴式。
abcde/+*+ 畫一個運算樹 先算的d/e根為"/"，子結點為d，e 然後算c+d/e，根為「+」，左右子結點為e和上面的子樹 b*(c+d/e)根為"*"，作子樹為b，右子樹為(c+d/e)的樹 最後a為右結點，"+"為根，左子樹為剛才得到的樹。 該樹後序遍歷即得。
J. 什麼叫活前綴,用通俗的話解答下,或者簡單的例子。 這個題是編譯原理的。
活前綴：右句型的前綴，而且其右端不會超過該句型的最右邊句柄的末端。
右句型：最右推導可得到的句型。
最右推導：每步推導都替代最右非終結符的推導。
推導：我們說αBγ推導出αβγ，是說存在產生式B->β。
產生式：左邊為非終結符，右邊為終結符與非終結符組合成的串。
非終結符：是字元串的集合。
終結符：組成語言的詞。如c語言中的2，a，int，if等。
句型：開始符經過若干步推導後得到的串。
前綴：如abc的前綴為a、ab、abc。
開始符：開始符是整個語言的集合。
句柄：非形式的，句柄是和某個產生式右部匹配的字元串，把句柄歸約成產生式左部的非終結符，可以得到最右推導的逆過程的一步。形式的定義為：開始符s經過若干步最右推導得到αBγ，αBγ經過一步最右推導得到αβγ，若γ為終結符的集合，則β為句柄。舉例：
E->E+E|E*E|-E|(E)|id，對於id+id*id，其中一個最右推導為E->E+E->E+E*E->E+E*id->E+id*id->id+id*id。在id+id*id歸約成E+id*id的過程中，最左邊的id是句柄。E+id*id歸約成E+E*id時，最左邊的id是句柄，把E+E*id歸約成E+E*E時，id是句柄。把E+E*E歸約成E+E時E*E是句柄。E+E歸約成E時，E+E是句柄。
歸約：可理解為把產生式右邊的串用產生式左邊的非終結符代替。
注1：再說一下活前綴，舉個例子，比如E+E*E歸約成E+E，句柄是E*E，那麼它的活前綴就是E、E+、E+E、E+E*、E+E*E。又比如id+id*id歸約成E+id*id，句柄是最左邊的id，那麼它的活前綴是id，因為不能超過句柄。
注2：至於為什麼要給出活前綴的定義和如何用歸約的方法實現語法分析，還要進一步學習。