編譯原理中什麼是最右符號

A. 編譯原理習題，下圖為什麼a為句柄, 而不是最左面的b為句柄怎樣理解句柄定義中的最左簡單子樹中的簡

baSb的最右推導為：S->AB->ASb->bBSb->baSb

根據句柄定義：

所以a為baSb的句柄。

只有單層分支的子樹稱為簡單子樹。最左簡單子樹末端結點組成的符號串為句柄。

B. 規范歸約分析法是什麼

問題一：當電路中電源較少時，應優先選擇什麼分析法 算符優先分析法比LR分析（規范歸約）法的歸約速度快。在LR分析一章的語法分析器自動生成工具Yacc中，對算數表達式的歸約往往會用到算符優先關系的概念。 算符優先分析的缺點是對文法有一定的限制，在實際應用中往往只用於算數表達式的歸約。由於算符優先分析不是規范歸約，所以可能把不是文法的句子錯誤的歸約成功

問題二：編譯原理懂的進 唉，這個中文翻譯的實在差啊，這些名詞概念不需要搞清楚的，建議你看下編譯原理的英文版

問題三：編譯原理LR（1）中的R和1分別是什麼意思 優質解答
LR分析法是一種自下而上進行規范歸約的語法分析法,L指從左到右掃描輸入符號串,R是指構造最右推數前導的逆過程.LR(1)中的1是每次搜索符號需要向前參考一步,即參考下一個符號確定當前構造.
L：Left (左) R：Right (右)

問題四：使用算符優先分析法分析的語言，應具有什麼特點 算符優先分析法比LR分析（規范歸約）法的歸約速度快。在LR分析一章的語法分析器自動生成工具Yacc中，對算數表達式的歸約往往會用到算符優先關系的概念。
算符優先分析的缺點是對文法有一定的限制，在際應用中往往只用於算數表達式的歸約。由於算符優先分析不是規范歸約，所以可激信能把不是文法的句子錯誤的歸約成功

問題五：幫我看看下面 編譯原理 的題目: 謝謝! 23. D
24. D
25. A
26. D
27. C
28. B
29. D
30. A
31. A
32. B
33. A
34. 不太確定，蒙D
35. A
36. 不太確定，蒙A
37. D
38. C
39. D
40. 不知道
二、
A,B
A,D
C,D
A,C
A,B,D
A,B,C,D

問題六：編譯原理中，算符優先文法和LR文法什麼關系 算符優先分析法比LR分析（規范歸約）法的歸約速度快。在LR分析一章的語法分析器自動生成工具Yacc中，對算數表達式的歸約往往會用到算符優先關系的概念。算符優先分析的缺點是對文法有一定的限制，在實際應用中往往只用於算數表達式的歸約。由於算符優先分析不是規范歸約，所以可能把不是文法的句子錯誤的歸約成功

問題七：編譯原理 LR(0) 項目集規范族怎麼構建。 書上的實在是看不懂那些I0、I1、I2的步驟。求一個 LR分析法是一種自下而上進行規范歸約的語法分析法，L指從左到右掃描輸入符號串，R是指構造最右推導的逆過程。對大多數無二義性上下文無關文法描述的語言都可用它進行有效的分析。主要分析器有LR（0），SLR（1），LR（1），LALR（1）：
LR（0）：在分析的每一步，只需根據當前棧頂狀態而不必向前查看輸入符號就能確定應採取的分析動作。所能分析的LR（0）文法要求文法的每一個LR（0）項目集中都不含沖突項目。
示例文法：
0 S』 -> S
1 S -> A
2 S -> B
3 A -> aAb
4 A -> c
5 B -> aBb
6 B -> d

問題八：文法算符優先關系表到底怎麼看？是縱向大於行向 算符優先分析法比LR分析（規范歸約）法的歸約速度快。在LR分析一章的語法分析器自動生成工具Yacc中，對算數表達式的歸約往往會用到算符優先關系的概念。算符優先分明畢輪析的缺點是對文法有一定的限制，在實際應用中往往只用於算數表達式的歸約。由於算符優先分析不是規范歸約，所以可能把不是文法的句子錯誤的歸約成功

問題九：編譯原理試題 10分 習題一、單項選擇題
1、將編譯程序分成若干個「遍」是為了 。
a．提高程序的執行效率
b．使程序的結構更加清晰
c．利用有限的機器內存並提高機器的執行效率
d．利用有限的機器內存但降低了機器的執行效率
2、構造編譯程序應掌握 。
a．源程序b．目標語言
c．編譯方法d．以上三項都是
3、變數應當 。
a．持有左值b．持有右值
c．既持有左值又持有右值d．既不持有左值也不持有右值
4、編譯程序絕大多數時間花在 上。
a．出錯處理b．詞法分析
c．目標代碼生成d．管理表格
5、 不可能是目標代碼。
a．匯編指令代碼b．可重定位指令代碼
c．絕對指令代碼d．中間代碼
6、使用 可以定義一個程序的意義。
a．語義規則b．詞法規則
c．產生規則d．詞法規則
7、詞法分析器的輸入是 。
a．單詞符號串b．源程序
c．語法單位d．目標程序
8、中間代碼生成時所遵循的是- 。
a．語法規則b．詞法規則
c．語義規則d．等價變換規則
9、編譯程序是對 。
a．匯編程序的翻譯b．高級語言程序的解釋執行
c．機器語言的執行d．高級語言的翻譯
10、語法分析應遵循 。
a．語義規則b．語法規則
c．構詞規則d．等價變換規則
解答
1、將編譯程序分成若干個「遍」是為了使編譯程序的結構更加清晰，故選b。
2、構造編譯程序應掌握源程序、目標語言及編譯方法等三方面的知識，故選d。
3、對編譯而言，變數既持有左值又持有右值，故選c。
4、編譯程序打交道最多的就是各種表格，因此選d。
5、目標代碼包括匯編指令代碼、可重定位指令代碼和絕對指令代碼3種，因此不是目標代碼的只能選d。
6、詞法分析遵循的是構詞規則，語法分析遵循的是語法規則，中間代碼生成遵循的是語義規則，並且語義規則可以定義一個程序的意義。因此選a。
7、b 8、c 9、d 10、c
二、多項選擇題
1、編譯程序各階段的工作都涉及到 。
a．語法分析b．表格管理c．出錯處理
d．語義分析e．詞法分析
2、編譯程序工作時，通常有 階段。
a．詞法分析b．語法分析c．中間代碼生成
d．語義檢查e．目標代碼生成
解答
1．b、c 2. a、b、c、e
三、填空題
1、解釋程序和編譯程序的區別在於 。
2、編譯過程通常可分為5個階段，分別是 、語法分析 、代碼優化和目標代碼生成。3、編譯程序工作過程中，第一段輸入是 ，最後階段的輸出為 程序。
4、編譯程序是指將 程序翻譯成 程序的程序。解答
是否生成目標程序 2、詞法分析 中間代碼生成 3、源程序目標代碼生成4、源程序 目標語言
一、單項選擇題
1、文法G：S→xSx|y所識別的語言是 。
a. xyxb. (xyx)*c. xnyxn(n≥0)d. x*yx*
2、文法G描述的語言L(G)是指 。
a......>>

C. 編譯原理筆記9：語法分析樹、語法樹、二義性的消除

語法分析樹和語法樹不是一種東西 。習慣上，我們把前者叫做「具體語法樹」，其能夠體現推導的過程；後者叫做「抽象語法樹」，其不體現過程，只關心最後的結果。

語法分析樹是語言推導過程的圖形化表示方法。這種表示方法反映了語言的實質以及語言的推導過程。

定義：對於 CFG G 的句型，分析樹被定義為具有下述性質的一棵樹：

推導，有最左推導和最右推導，這兩種推導方式在推導過程中的分析樹可能不同，但因最終得到的句子是相同的，所以最終的分析樹是一樣的。

分析樹能反映句型的推導過程，也能反映句型的結構。然而實際上，我們往往不關心推導的過程，而只關心推導的結果。因此，我們要對 分析樹 進行改造，得到 語法樹 。語法樹中全是終結符，沒有非終結符。而且語法樹中沒有括弧

定義：

說白了，語法樹這玩意，就一句話： 葉子全是操作數，內部全是操作符 ，樹里沒有非終結符也不能有括弧。

語法樹要表達的東西，是操作符（運算）作用於操作數（運算對象）

舉倆例子吧：

【例】： -(id+id) 的語法樹：

【例】：-id+id 的語法樹：

顯然，我們從上面這兩個語法樹中，直接就能觀察出來它們的運算順序。

【例】：句型 if C then s1 else s2

二義性問題：一個句子可能對應多於一棵語法樹。

【例】： 設文法 G： E → E+E | E*E | (E) | -E | id

則，句子 id+id*id、id+id+id 可能的分析樹有：

在該例中，雖然 id+id+id 的 「+」 的結合性無論左右都不會影響結果。但萬一，萬一「+」的含義變成了「減法」，那麼左結合和右結合就會引起很大的問題了。

我們在這里講的「二義性」的「義」並非語義——我們現在在學習的內容是「語法分析器」，尚未到需要研究語言背後含義的階段。

我們現在講的「二義性」指的是一個句子對應多種分析樹。

二義性的體現，是文法對同一句子有不止一棵分析樹。這種問題由【句子產生過程中的某些推導有多於一種選擇】引起。懸空 else 問題就可以很好地體現這種【超過一種選擇】帶來的二義性問題，示例如下。

看下面這么個例子。。

（其實，我感覺這個其實比較像是「說話大喘氣」帶來的理解歧義問題。。。）上面的產生式中並沒體現出來該咋算分一塊，所以兩種完全不同的句子結構都是合法的。

二義性問題是有救的，大概有以下這三種辦法：

這些辦法的核心，其實都是將優先順序和結合性說明白。

核心：把優先順序和結合性說明白

既然要說明白，那就不能讓一個非終結符可以直接在當次推導中能推出會帶來優先順序和結合性歧義的東西。（對分析樹的一個內部節點，不會有出現在其下面的分支是相同的非終結符的情況。如果有得選，那就有得歧義了。沒得選才能確定地一路走到黑）

改寫為非二義文法的二義文法大概有下面這幾個特點：

改寫的關鍵步驟：

【例】改寫下面的二義文法為非二義文法。圖右側是要達成的優先順序和結合性

改寫的核心其實就兩句話：

所以能夠得到非終結符與運算的對應關系（因為不同的運算有不同的優先順序，我們想要引入多個優先順序就要引入多個新的非終結符。這樣每個非終結符就可以負責一個優先順序的運算符號，也就是說新的非終結符是與運算有關系的了。因此這里搞出來了「對應關系」四個字）如下：

優先順序由低到高分別是 +、 、-，而距離開始符號越近，優先順序越低。因此在這里的排序也可以+ -順序。每個符號對應一層的非終結符。根據所需要的結合性，則可確定是左遞歸還是右遞歸，以確定新的產生式長什麼樣子

【例】：規定優先順序和結合性，寫出改寫的非二義文法

我們已經掌握了一種叫做【改寫】的工具，能讓我們消除二義性。接下來我們就要用這個工具來嘗試搞搞懸空 else 問題！

懸空 else 問題出現的原因是 then 數量多於 else，讓 else 有多個可以結合的 then。在二義文法中，由於選哪兩個 then、else 配對都可以，故會引起出現二義的情況。在這里，我們規定 else 右結合，即與左邊最靠近的 then 結合。

為改寫此文法，可以將 S 分為完全匹配（MS）和不完全匹配（UMS）兩類。在 MS 中體現 then、else 個數相等即匹配且右結合；在UMS 中 then、else 不匹配，體現 else 右結合。

【例】：用改寫後的文法寫一個條件語句

經過檢查，無法再根據文法寫出其他分析樹，故已經消除了二義性

雖然二義文法會導致二義性，但是其並非一無是處。其有兩個顯著的優點：

在 Yacc 中，我們可以直接指定優先順序、結合性而無需自己重寫文法。

left 表示左結合，right 表示右結合。越往下的算符優先順序越高。

嗯就這么簡單。。。

我們其實可以把語言本身定義成沒有優先順序和結合性的。。然後所有的優先、結合都交由括弧進行控制，哪個先算就加括弧。把一個過程的結束用明確的標志標記出來。

比如在 Ada 中：

在 Pascal 中，給表達式加括弧：

D. 編譯原理的最左推導和最右推導。。。

(2)給出句子0127,34和568的最左推導和最右推導我是剛學編譯原理,不知道該怎麼去思考,從那入手呢? (1)帶先導0的十進制無符號整數 (2)最左推導：

E. 求最左推導和最右推導

最左推導（Leftmost Derivation）

最左推導是一種從文法的起始符號開始，總是優先替換最左邊的非終結符的推導過程。具體步驟如下：

• 從文法的起始符號開始。

• 在每一步中，找到當前字元串中的最左邊的非終結符，並用其某個產生式進行替換。

• 重復第2步，直到得到一個只包含終結符的字元串為止。

最右推導（Rightmost Derivation）

最右推導與最左推導相反，它總是優先替換最右邊的非終結符。具體步驟如下：

• 從文法的起始符號開始。

• 在每一步中，找到當前字元串中的最右邊的非終結符，並用其某個產生式進行替換。

• 重復第2步，直到得到一個只包含終結符的字元串為止。

示例

考慮以下簡單的上下文無關文法：

• S → A B

• A → a A

• A → ε

• B → b B

• B → ε

最左推導示例：

• S （起始符號）

• A B （S → A B）

• a A B （A → a A，替換最左邊的A）

• a a A B （A → a A，替換最左邊的A）

• a a b B （B → b B，替換最左邊的B）

• a a b b B （B → b B，替換最左邊的B）

• a a b b （B → ε，替換最左邊的B）

最右推導示例：

• S （起始符號）

• A B （S → A B）

• A a B （A → a A，替換最右邊的A）

• A a b B （B → b B，替換最右邊的B）

• A a b b B （B → b B，替換最右邊的B）

• A a b b （B → ε，替換最右邊的B）

• a A b b （A → a A，替換最右邊的A）

• a a A b b （A → a A，替換最右邊的A）

• a a b b b b （A → ε 和 B → ε，分別替換最右邊的A和B）

F. 句柄的編譯原理

一個句型的最左直接短語稱為該句型的句柄，句型的句柄是和某產生式右部匹配的子串，並且，把它規約成該產生式左部的非終結符，代表了最右推導過程的逆過程的一步。
如右圖，在推導過程中，S→aABe→aAde→aAbcde→abbcde，此四步的句柄分別為aABe,d,Abc,b
句柄的特徵：
1. 它是直接短語，即某規則右部。
2. 它具有最左性。
注意：短語、直接短語和句柄都是針對某一句型的，特指句型中的哪些符號子串能構成短語和直接短語，離開具體的句型來談短語、直接短語和句柄是無意義的。另外句柄的右邊僅含終結符如果文法二義，那麼句柄可能不唯一。