編譯原理回溯分析法

『壹』 回溯的在編譯原理中的運用

如左圖，在發生虛假匹配時需要進行回溯，就是退回到開始的位置

『貳』 計算機科學與技術《編譯原理》求解題

1、錯
2、對
3、錯
4、對
5、錯
6、對
7、對
8、對
9、對
10、錯

『叄』 回溯法的基本思想是什麼

回溯法又稱試探法。回溯法的基本做法是深度優先搜索，是一種組織得井井有條的、能避免不必要重復搜索的窮舉式搜索演算法。
回溯演算法的基本思想是：從一條路往前走，能進則進，不能進則退回來，換一條路再試。
當我們遇到某一類問題時，它的問題可以分解，但是又不能得出明確的動態規劃或是遞歸解法，此時可以考慮用回溯法解決此類問題。回溯法的優點在於其程序結構明確，可讀性強，易於理解，而且通過對問題的分析可以大大提高運行效率。但是，對於可以得出明顯的遞推公式迭代求解的問題，還是不要用回溯法，因為它花費的時間比較長。
對於用回溯法求解的問題，首先要將問題進行適當的轉化，得出狀態空間樹。這棵樹的每條完整路徑都代表了一種解的可能。通過深度優先搜索這棵樹，枚舉每種可能的解的情況；從而得出結果。但是，回溯法中通過構造約束函數，可以大大提升程序效率，因為在深度優先搜索的過程中，不斷的將每個解（並不一定是完整的，事實上這也就是構造約束函數的意義所在）與約束函數進行對照從而刪除一些不可能的解，這樣就不必繼續把解的剩餘部分列出從而節省部分時間。
回溯法中，首先需要明確下面三個概念：
（一）約束函數：約束函數是根據題意定出的。通過描述合法解的一般特徵用於去除不合法的解，從而避免繼續搜索出這個不合法解的剩餘部分。因此，約束函數是對於任何狀態空間樹上的節點都有效、等價的。
（二）狀態空間樹：剛剛已經提到，狀態空間樹是一個對所有解的圖形描述。樹上的每個子節點的解都只有一個部分與父節點不同。
（三）擴展節點、活結點、死結點：所謂擴展節點，就是當前正在求出它的子節點的節點，在深度優先搜索中，只允許有一個擴展節點。活結點就是通過與約束函數的對照，節點本身和其父節點均滿足約束函數要求的節點；死結點反之。由此很容易知道死結點是不必求出其子節點的（沒有意義）。
利用回溯法解題的具體步驟
首先，要通過讀題完成下面三個步驟：
(1)描述解的形式，定義一個解空間，它包含問題的所有解。
(2)構造狀態空間樹。
(3)構造約束函數（用於殺死節點）。

然後就要通過深度優先搜索思想完成回溯，完整過程如下：
(1)設置初始化的方案（給變數賦初值，讀入已知數據等）。
(2)變換方式去試探，若全部試完則轉(7)。
(3)判斷此法是否成功（通過約束函數），不成功則轉(2)。
(4)試探成功則前進一步再試探。
(5)正確方案還未找到則轉(2)。
(6)已找到一種方案則記錄並列印。
(7)退回一步（回溯），若未退到頭則轉(2)。
(8)已退到頭則結束或列印無解

『肆』 編譯原理回溯

消除回溯：提取左公因子a,（註：用e代表一補西農符號,就是反三的那個符號,在電腦上不知道怎麼打那個符號）
S→aS'|(L)
S'→S|e
消除左遞歸：
L→SL'
L'→,SL'|e (注意S前面有一個符號「,」)

『伍』 什麼是回溯演算法

回溯演算法也叫試探法，它是一種系統地搜索問題的解的方法。回溯演算法的基本思想是：從一條路往前走，能進則進，不能進則退回來，換一條路再試。用回溯演算法解決問題的一般步驟為： 1、定義一個解空間，它包含問題的解。 2、利用適於搜索的方法組織解空間。 3、利用深度優先法搜索解空間。 4、利用限界函數避免移動到不可能產生解的子空間。 問題的解空間通常是在搜索問題的解的過程中動態產生的，這是回溯演算法的一個重要特性。 1.跳棋問題： 33個方格頂點擺放著32枚棋子，僅中央的頂點空著未擺放棋子。下棋的規則是任一棋子可以沿水平或成垂直方向跳過與其相鄰的棋子，進入空著的頂點並吃掉被跳過的棋子。試設計一個演算法找出一種下棋方法，使得最終棋盤上只剩下一個棋子在棋盤中央。 演算法實現提示 利用回溯演算法，每次找到一個可以走的棋子走動，並吃掉。若走到無子可走還是剩餘多顆，則回溯，走下一顆可以走動的棋子。當吃掉31顆時說明只剩一顆，程序結束。 2.中國象棋馬行線問題： 中國象棋半張棋盤如圖1(a)所示。馬自左下角往右上角跳。今規定只許往右跳，不許往左跳。比如 圖4（a）中所示為一種跳行路線，並將所經路線列印出來。列印格式為： 0，0->2,1->3,3->1,4->3,5->2,7->4,8… 演算法分析： 如圖1(b),馬最多有四個方向，若原來的橫坐標為j、縱坐標為i,則四個方向的移動可表示為： 1: （i,j）→（i+2,j+1）； (i<3,j<8) 2: （i,j）→（i+1,j+2）； (i<4,j<7) 3: （i,j）→（i-1,j+2）； (i>0,j<7) 4: （i,j）→（i-2,j+1）； (i>1,j<8) 搜索策略： S1:Ａ[１]:=(0,0); S2:從Ａ[1]出發，按移動規則依次選定某個方向，如果達到的是（4,8）則轉向S3,否則繼續搜索下 一個到達的頂點； S3:列印路徑。 演算法設計： procere try(i:integer); {搜索} var j:integer; begin for j:=1 to 4 do {試遍4個方向} if 新坐標滿足條件 then begin 記錄新坐標; if 到達目的地 then print {統計方案，輸出結果} else try(i+1); {試探下一步} 退回到上一個坐標，即回溯; end; end;

『陸』 編譯原理問題

第一個問題：編譯時是否有影響無關緊要只是你的源文件變大了，但是執行起來是沒有影響的。
第二個：採用靜態全局變數是為了在連接多個文件時防止重名問題出現，因為程序員在編程時不會一個人完成一個較大程序，必需要分工，每個人都用自己的文件來寫程序，這樣在多個文件中可能會把名字起重了，比如在本文件中用static 類型 a定義後，a就只能是B文件的全局變數，這時A文件也可以用static 類型 a來定義，但是它僅限於A文件，當然如果你不把A文件和B文件合在一起就沒啥意義了，可以說如果B文件的執行結束了，這個靜態全局變數就被釋放了。
第三個：只要應用程序結束，變數就釋放了
第四個：開辟的空間放在內存中，也就是ram(隨機存取存儲器)，你理解的對

『柒』 LL（1）分析法是什麼

LL(1)分析使用顯式棧而不是遞歸調用來完成分析。以標准方式表示這個棧非常有用，這樣LL(1)分析程序的動作就可以快捷地顯現出來。在這個介紹性的討論中，我們使用了生成成對括弧的串的簡單文法：
S →(S) S |
且將額外的棧項推向右邊。輸入符號由左列向右。美元符號標出了輸入的結束（它與由掃描程序生成的 EOF 記號相對應）。給出了由分析程序執行的動作的簡短描述，它將改變棧和（有可能）輸入。
LL(1)分析中的重復和選擇也存在著與在遞歸下降程序分析中遇到的類似問題，而且正是由於這個原因，還不能夠為的簡單演算法表達式文法給出一個LL(1)分析表