編譯原理復(fù)習(xí)匯總

1、復(fù)習(xí)匯總一、 第一章 概述1. 文法與自動(dòng)機(jī)的等價(jià)1) 0型文法圖靈機(jī)2) 1型文法線性有界非確定圖靈機(jī)3) 2型文法非確定下推自動(dòng)機(jī)4) 3型文法有限狀態(tài)自動(dòng)機(jī)2. 編譯技術(shù)的應(yīng)用1) 語(yǔ)法制導(dǎo)的結(jié)構(gòu)化編輯器2) 程序格式化工具3) 軟件測(cè)試工具4) 程序理解工具5) 高級(jí)語(yǔ)言的翻譯工具6) 等等3. 從面向機(jī)器的語(yǔ)言到面向人類的語(yǔ)言（結(jié)合第二章第9小點(diǎn)理解）1) 面向機(jī)器的語(yǔ)言：機(jī)器指令，匯編語(yǔ)言2) 面向人類的語(yǔ)言：通用程序設(shè)計(jì)語(yǔ)言，數(shù)據(jù)查詢語(yǔ)言，形式化描述語(yǔ)言（正規(guī)式,產(chǎn)生式）等等。4. 各語(yǔ)言的分類（結(jié)合第二章第9小點(diǎn)理解）1) 過(guò)程式語(yǔ)言，面向?qū)ο笳Z(yǔ)言：通用程序設(shè)計(jì)語(yǔ)言。2) 函數(shù)

2、語(yǔ)言：面向特點(diǎn)領(lǐng)域的，遞歸特性。例如LISP語(yǔ)言3) 說(shuō)明性，非算法式語(yǔ)言：LEX/YACC,SQL。4) 腳本式語(yǔ)言：Shell語(yǔ)言5. 語(yǔ)言之間的轉(zhuǎn)換（李靜PPT41）1) 高級(jí)語(yǔ)言之間的轉(zhuǎn)換一般稱為預(yù)處理或轉(zhuǎn)換。2) 高級(jí)語(yǔ)言翻譯成匯編語(yǔ)言或機(jī)器語(yǔ)言稱之為編譯。3) 把匯編語(yǔ)言翻譯成機(jī)器語(yǔ)言稱之為匯編。4) 將一個(gè)匯編語(yǔ)言程序匯編為可在另一臺(tái)機(jī)器上運(yùn)行的機(jī)器指令稱之為交叉匯編。5) 把機(jī)器語(yǔ)言翻譯成匯編語(yǔ)言稱之為反匯編。6) 把匯編語(yǔ)言翻譯成高級(jí)語(yǔ)言稱之為反編譯。6. 編譯器和解釋器1) 編譯器l 源程序的翻譯和翻譯后的程序的運(yùn)行是兩個(gè)不同的階段。u 編譯階段：用戶輸入源程序，經(jīng)過(guò)編譯器

3、的處理，生成目標(biāo)程序。u 目標(biāo)程序的運(yùn)行階段：根據(jù)要求輸入數(shù)據(jù)，得出結(jié)果。2) 解釋器（凡是可以采用編譯器的地方均可以采用解釋器）l 解釋器把翻譯和運(yùn)行結(jié)合到一起，編譯一段源程序，緊接著就執(zhí)行它。這種方式稱為解釋。7. 解釋器的優(yōu)點(diǎn)（對(duì)比與編譯器）1) 具有較好的動(dòng)態(tài)特性。2) 具有較好的移植特性。8. 解釋器的缺點(diǎn)（對(duì)比于編譯器）1) 相比于編譯器需花費(fèi)大量的時(shí)間。2) 占用更多的內(nèi)存空間。9. 編譯器的工作階段（結(jié)合第二章6小點(diǎn)紅色部分理解）1) 源程序->詞法分析器->語(yǔ)法分析器->語(yǔ)義分析器->中間代碼生成器->代碼優(yōu)化器->目標(biāo)代碼生成器->

4、目標(biāo)代碼2) 工作過(guò)程中的每個(gè)階段均采用了符號(hào)表管理器，出錯(cuò)處理器。10. 編譯器各階段的工作過(guò)程（結(jié)合第二章6小點(diǎn)紅色部分理解）1) 源程序通過(guò)詞法分析器翻譯成記號(hào)流，記號(hào)流通過(guò)語(yǔ)法分析產(chǎn)生語(yǔ)法樹，然后根據(jù)語(yǔ)法樹來(lái)進(jìn)行適當(dāng)?shù)恼Z(yǔ)義處理，語(yǔ)義分析產(chǎn)生符號(hào)表和中間代碼。2) 符號(hào)表的格式：標(biāo)識(shí)符，類型，分配的地址。3) 中間代碼的格式：操作符，左操作數(shù)，右操作數(shù)，結(jié)果。4) 中間代碼的優(yōu)化：傳值的代碼可以省略。5) 目標(biāo)代碼生成：生成匯編指令，格式為：操作數(shù) 源碼 目標(biāo)。l 二元運(yùn)算： OP source target target := source OP targetl 一元運(yùn)算：MOVE s

5、ource target tatget = source。11. 各階段工作歸納1) 詞法分析：根據(jù)詞法規(guī)則識(shí)別出源程序的各個(gè)記號(hào)（token），每個(gè)記號(hào)代表一類單詞（lexeme），記號(hào)的分類如下：（第二章第4小點(diǎn)）l 關(guān)鍵字：如var、begin、end 等，不做他用，稱為保留字。l 標(biāo)識(shí)符：如x、y、z、sort等，在源程序中被用作變量名，過(guò)程名，類型名和標(biāo)號(hào)等所有對(duì)象的名稱。(用記號(hào)代替)l 字面量：如60、Xidian、University等，一般用于表示常數(shù)或字符串常量。（保留原樣）l 特殊符號(hào)：=、*、+、-、;等運(yùn)算符，分隔符（保留原樣）。l 例：var x,y,z:real

6、; x:= y+z*60; var id1,id2,id3:real;id1:=id2+id3*60;2) 語(yǔ)法分析：得到語(yǔ)言結(jié)構(gòu)并以樹來(lái)表示。3) 語(yǔ)義分析：考察結(jié)構(gòu)正確的句子是否語(yǔ)義合法。4) 中間代碼生成。5) 中間代碼優(yōu)化。6) 目標(biāo)代碼生成。7) 符號(hào)表管理：合理組織符號(hào)，便于各階段查找，填寫等。8) 出錯(cuò)處理：錯(cuò)誤的種類詞法錯(cuò)，語(yǔ)法錯(cuò)，靜態(tài)語(yǔ)義錯(cuò)，動(dòng)態(tài)語(yǔ)義錯(cuò)。12. 編譯器的分析/綜合模式。（PPT53）1) 前端（分析）：語(yǔ)言結(jié)構(gòu)的分析。（語(yǔ)法和語(yǔ)義分析）2) 后端（綜合）：語(yǔ)言意義的分析與處理。（代碼的生成、優(yōu)化）3) 中間代碼：前段與后端的分解。二、 第二章 詞法分析1. 詞

7、法分析：詞法分析是編譯過(guò)程中將字符流轉(zhuǎn)換成為符號(hào)流的一個(gè)工作階段，是編譯的第一步操作，其后續(xù)工作是語(yǔ)法分析（配合第一章第11小點(diǎn)理解）。1) 詞法分析輸入源代碼。2) 詞法分析輸出記號(hào)流。3) 詞法分析需要識(shí)別此發(fā)錯(cuò)無(wú)，即非法的符號(hào)、單詞。但不識(shí)別語(yǔ)法錯(cuò)誤。2. 詞法分析器的作用1) 源程序由單詞組成，單詞是最小的語(yǔ)義單位。2) 詞法分析器的功能：l 掃描源程序字符流。l 按照源程序的語(yǔ)法規(guī)則識(shí)別出各類單詞符號(hào)。l 產(chǎn)生用于語(yǔ)法分析的記號(hào)序列。l 填寫符號(hào)表。3) 輔助功能l 跳過(guò)源程序的注釋和空白。l 把錯(cuò)誤信息和源程序聯(lián)系起來(lái)（錯(cuò)誤定位）。l 宏預(yù)處理。3. 模式（規(guī)則）（patten）：

8、將產(chǎn)生和識(shí)別單詞的規(guī)則稱為模式（規(guī)則）。4. 記號(hào)（token）：按照某個(gè)模式識(shí)別出來(lái)的元素稱為記號(hào)。（第一章和本章第11小點(diǎn)一同理解）1) 記號(hào) = 記號(hào)的類別 + 記號(hào)的屬性。（用于識(shí)別）2) 記號(hào)的類別：記號(hào)的類別可以用整形編碼來(lái)表示。3) 記號(hào)的屬性：根據(jù)記號(hào)的類別不同，記號(hào)的屬性可以用不同的表示方法，如relation(81)的屬性值為一個(gè)有限的可枚舉的集合，可以用每個(gè)屬性值在集合中的位置來(lái)表示它。（課本P16）。5. 單詞（lexeme）：被識(shí)別出元素自身的價(jià)值。（結(jié)合本章第9點(diǎn)理解）6. 詞法分析器的作用和工作方式:1) 特征：編譯器中唯一與源程序打交道的部分。2) 任務(wù)：（與第

9、二章第2點(diǎn)一同理解）l 濾掉源程序中的無(wú)用的部分，如注釋，空格，回車等。l 處理與具體平臺(tái)有關(guān)的輸入。l 識(shí)別記號(hào)，并交給語(yǔ)法分析器，根據(jù)模式識(shí)別記號(hào)。l 調(diào)用符號(hào)表管理器或出錯(cuò)管理器，進(jìn)行相關(guān)管理。3) 工作方式l 單獨(dú)一遍掃描。l 作為語(yǔ)法分析器的子程序。l 并行方式。4) 輸入輸出結(jié)果的分析（結(jié)合第一章9、10小點(diǎn)理解）l 源程序->詞法分析期->記號(hào)流l 源程序->詞法分析器->記號(hào)流->語(yǔ)法分析器->語(yǔ)法樹。7. 輸入緩沖區(qū)1) 設(shè)置緩沖區(qū)的必要性：l 超前搜索：為了得到某一個(gè)單詞符號(hào)的確切性質(zhì)，需要超前掃描若干個(gè)字符。l 方便實(shí)現(xiàn)讀字符和退字符操

10、作，提高詞法分析器的效率。8. 字符串：從詞法分析的角度看程序語(yǔ)言設(shè)計(jì)，他是由幾號(hào)組成的集合（第二章第4小點(diǎn)）1) 定義：語(yǔ)言L是有限字母表上有限長(zhǎng)度字符串的集合。字母表是組成字符串的所有字符的集合。即字符串中的所有字符取自字母表。2) 兩個(gè)有限：（有序集合）:因?yàn)橛?jì)算機(jī)所能表示的字符個(gè)數(shù)和字符串長(zhǎng)度是有限的。l 字母表是有限的，即字母表中的元素是有限多個(gè)。l 字符串長(zhǎng)度是有限的，即字符串中字符的個(gè)數(shù)是有限多個(gè)的。3) 字符串和集合的基本概念：（課本P19）9. 語(yǔ)言概述：（第一章第3、4小點(diǎn)理解）1) 語(yǔ)言形式化的內(nèi)容提?。菏亲趾徒M合字的規(guī)則l 語(yǔ)言：滿足一定條件的句子集合。l 句子：滿足一

11、定規(guī)則的單詞序列l(wèi) 單詞：滿足已定規(guī)則的字符。（結(jié)合本章第5點(diǎn)理解）2) 程序設(shè)計(jì)語(yǔ)言形式化的內(nèi)容提?。航M成程序的所有語(yǔ)句的集合。l 程序：滿足語(yǔ)法規(guī)則的語(yǔ)句序列。l 語(yǔ)句：滿足語(yǔ)法規(guī)則的單詞序列。l 單詞：滿足詞法規(guī)則的字符串。（結(jié)合本章第5點(diǎn)理解）3) 描述形式文法l 語(yǔ)法語(yǔ)句u 語(yǔ)句的組成規(guī)則u 描述方法：BNF范式，語(yǔ)法圖l 詞法單詞（結(jié)合本章第5點(diǎn)理解）u 單詞的組成規(guī)則。u 描述方法：BNF范式，正規(guī)式。（結(jié)合下一小點(diǎn)理解）10. 正規(guī)式和正規(guī)集1) 正規(guī)式：令是一個(gè)有限字母表，則上的正規(guī)式及其表示的集合遞歸定義為：l 是正規(guī)式，他表示集合L（）=l 若a是上的字符，則a是正規(guī)式，

12、他表示集合L（a）=al 若正規(guī)式r和s分別表示集合L（r）和L（s），則u r|s是正規(guī)式，表示集合L（r）并L（s）。u rs是正規(guī)式，表示集合L（r）L（s）。u r*是正規(guī)式，表示集合L（r）*。u （r）是正規(guī)式，表示的集合仍是L（r）。（加括號(hào)改變優(yōu)先級(jí)，結(jié)合性）2) 正規(guī)集：可用于正規(guī)式描述的語(yǔ)言稱為正規(guī)語(yǔ)言或正規(guī)集。l 正規(guī)式計(jì)算的優(yōu)先級(jí)（具有左結(jié)合的性質(zhì)）u 從高到低排列：閉包運(yùn)算，連接運(yùn)算，或運(yùn)算。l 正規(guī)式中不必要的括號(hào)可以被省略。3) 正規(guī)式和正規(guī)集之間的關(guān)系是多對(duì)一的關(guān)系。4) 正規(guī)式的等價(jià)：若正規(guī)式P和Q表示了同一個(gè)正規(guī)集，則稱P和Q是等價(jià)的，即為P=Q5) 正規(guī)式

13、公理（課本P21）11. 記號(hào)的說(shuō)明（用正規(guī)式來(lái)描述）（本章第4小點(diǎn)）：正規(guī)式可以嚴(yán)格規(guī)定記號(hào)的模式，用正規(guī)式說(shuō)明記號(hào)的公式為：1) 記號(hào) = 正規(guī)式（記號(hào)是正規(guī)式）例如：id = a(a|b)可以讀作“id定義為a(a|b)”（簡(jiǎn)稱為正規(guī)式）2) 通常在不引起混淆的情況下，也把說(shuō)明記號(hào)的公式簡(jiǎn)稱為正規(guī)式，或者規(guī)則。12. 記號(hào)的識(shí)別有限自動(dòng)機(jī)1) 模式的描述正規(guī)式2) 記號(hào)的識(shí)別有限自動(dòng)機(jī)（確定，不確定）l 不確定的有限自動(dòng)機(jī)u 定義：NFA是一個(gè)五元組：M = （S，move，s0，F(xiàn)）A. S是有限個(gè)狀態(tài)的集合。B. 是有限個(gè)輸入字符（包括）的集合。C. Move是一個(gè)狀態(tài)轉(zhuǎn)移函數(shù)，mo

14、ve（si ，ch）= sj表示，當(dāng)前狀態(tài)si下若遇到輸入字符ch，則轉(zhuǎn)移到狀態(tài)sj。D. s0是唯一的初態(tài)（稱為開始狀態(tài)）E. F是終態(tài)集，他是S的子集，包含了所有的終態(tài)。u NFA的表示方式A. 狀態(tài)轉(zhuǎn)換圖：用一個(gè)有向圖直觀表示NFA。終態(tài)用一個(gè)雙圈來(lái)表示。B. 狀態(tài)轉(zhuǎn)換矩陣：用一個(gè)二維數(shù)組來(lái)直觀表示NFA。u NFA識(shí)別記號(hào)（課本P24-25 ，PPT29）A. NFA識(shí)別記號(hào)存在的問(wèn)題：1. 只有嘗試了全部可能的路徑，才能確定一個(gè)輸入序列不被接受，而這些路徑的條數(shù)隨著路徑長(zhǎng)度的增長(zhǎng)而成指數(shù)增長(zhǎng)。2. 識(shí)別過(guò)程中存在大量回溯，時(shí)間復(fù)雜度和輸入序列呈指數(shù)級(jí)增長(zhǎng)。l 確定的有限自動(dòng)狀態(tài)機(jī)（D

15、FA）u 定義：DFA是NFA的一個(gè)特例A. 沒有狀態(tài)具有狀態(tài)轉(zhuǎn)移，即狀態(tài)轉(zhuǎn)換圖中沒有標(biāo)記的邊。B. 對(duì)每一個(gè)狀態(tài)s和每一個(gè)字符a，最多有一個(gè)下一個(gè)狀態(tài)。u DFA的特征：消除了NFA的不確定性。A. 定義move（si，a）函數(shù)是一對(duì)一的。B. 轉(zhuǎn)換圖：從一個(gè)節(jié)點(diǎn)出發(fā)的邊上標(biāo)記均不相同。（沒有重復(fù)字符的狀態(tài)轉(zhuǎn)移）C. 轉(zhuǎn)換矩陣Msi，a是一個(gè)狀態(tài)。（NFA可以為狀態(tài)集）D. 字母表不包括。l 有限自動(dòng)機(jī)的等價(jià)：若有限自動(dòng)機(jī)M和M識(shí)別同意正規(guī)集，則成M和M是等價(jià)的，即為M=M。13. 簡(jiǎn)化正規(guī)式描述1) 正閉包：若r是表示L（r）的正規(guī)式，則r的正閉包是表示（L（r）的正閉包的正規(guī)式；l r+

16、 = rr* = r*r，r* = r+|。+與*具有相同的運(yùn)算結(jié)合性和優(yōu)先級(jí)2) 可缺?。簉？ = r|3) 字符組：l 枚舉：【abc】 = a|b|cl 分段4) 非字符組：l 若r是一個(gè)字符組形式的正規(guī)式，則r是表示-L（r）的正規(guī)式。5) 串：若r是字符鏈運(yùn)算的正規(guī)式，則串“r”和r等價(jià)。14. 從正規(guī)式到詞法分析器1) 構(gòu)造詞法分析器的一般方法和步驟：l 用正規(guī)式對(duì)模式進(jìn)行描述。l 為每一個(gè)正規(guī)式構(gòu)造一個(gè)NFA，他識(shí)別正規(guī)式所表示的正規(guī)集。l 將構(gòu)造出的NFA轉(zhuǎn)化為等價(jià)的DFA，這一過(guò)程也成為確定化。l 優(yōu)化DFA，使其狀態(tài)數(shù)最少，這一過(guò)程稱為最小化。l 從優(yōu)化的DFA構(gòu)造詞法分析

17、器。2) 從正規(guī)式到NFA（thompson算法）。l 對(duì)于字母表上的r，將其分解為最基本的正規(guī)式。u 對(duì)于，NFA為s0為初態(tài)，f為終態(tài)，該NFA接收。u 對(duì)于上的任意一個(gè)字符a，NFA為s0為初態(tài)，f為終態(tài)，NFA接受a。u 若正規(guī)式N（p）和N（q）是正規(guī)式p和q的NFA，則：（課本P27）。3) 從NFA到DFAl NFA標(biāo)識(shí)記號(hào)的“并行”方法。避免回溯。u 由于并行的方法在每試探一步時(shí)，考慮了所有的下一步狀態(tài)轉(zhuǎn)移，因此走的每一步都是確定的。采用并行的方法，核心思想是將不確定的下一狀態(tài)確定化。l 確定化的兩個(gè)步驟：u 消除狀態(tài)轉(zhuǎn)移；的閉包。u 消除多余一個(gè)的下一個(gè)狀態(tài)轉(zhuǎn)移。l 算法（課

18、本P30）4) DFA最小化（課本35）三、 第三章 語(yǔ)法分析1. 詞法分析：元素是字母表，組成字符串，線性結(jié)構(gòu)，單詞的集合。2. 語(yǔ)法分析：元素是終結(jié)符，組成句子，樹結(jié)構(gòu)（分析樹），句子的集合。1) 語(yǔ)法規(guī)則：上下文無(wú)關(guān)文法（子集LL文法或LR文法）2) 語(yǔ)法分析：下推自動(dòng)機(jī)（LL或LR分析器），自上而下（預(yù)測(cè)分析）和自下而上（移進(jìn)歸約）分析3. 語(yǔ)法錯(cuò)誤的處理原則1) 源程序中可能出現(xiàn)的錯(cuò)誤：l 詞法錯(cuò)誤：非法字符或拼寫錯(cuò)誤的關(guān)鍵字，標(biāo)識(shí)符等。l 語(yǔ)法錯(cuò)誤：語(yǔ)法結(jié)構(gòu)錯(cuò)誤，缺少分號(hào)等。l 靜態(tài)語(yǔ)義錯(cuò)誤：類型不一致，參數(shù)不匹配等。l 動(dòng)態(tài)語(yǔ)義錯(cuò)誤：邏輯錯(cuò)誤，無(wú)窮遞歸，變量為0做處暑等等。2)

19、語(yǔ)法錯(cuò)誤處理的目標(biāo)l 清楚而準(zhǔn)確的報(bào)告錯(cuò)誤的出現(xiàn)。l 迅速的從每個(gè)錯(cuò)誤中恢復(fù)過(guò)來(lái)。l 不應(yīng)使對(duì)語(yǔ)法正確源程序的分析速度降低太多。3) 語(yǔ)法錯(cuò)誤的基本恢復(fù)策略l 緊急方式恢復(fù)：拋棄若干輸入，直至遇到同步記號(hào)。l 短語(yǔ)級(jí)回復(fù)l 出錯(cuò)產(chǎn)生式l 全局糾正4. 上下文無(wú)關(guān)文法（CFG）1) 定義：CFG是一個(gè)四元組G = （N，T，P，S），其中：l N是非終結(jié)符的有限集合。l T是終結(jié)符的有限集合，且N交T為空集。l P是產(chǎn)生式的有限集合。u A->a，其中A屬于N（左部），a屬于（N并T）的閉包（右部），若a = ，則稱A->為空的產(chǎn)生式l S是非終結(jié)符2) 由產(chǎn)生式集表示CFGl 前提

20、：若文法正確，第一個(gè)產(chǎn)生式的左部是文法開始符號(hào)S，則N是出現(xiàn)在產(chǎn)生式左邊符號(hào)的集合，T是所有不出現(xiàn)在產(chǎn)生式左邊符號(hào)的集合。3) 產(chǎn)生式的一般讀法：讀作“定義為”，或者“可導(dǎo)出”。4) 終結(jié)符與非終結(jié)符在讀寫上的區(qū)別。l 大寫英文字母A、B、C表示非終結(jié)符。l 小寫字母表示終結(jié)符。l 小寫希臘字母表示任意文法符號(hào)序列。5) 產(chǎn)生式的縮寫形式（產(chǎn)生式以非終結(jié)符命名）5. CFG產(chǎn)生語(yǔ)言的基本方法（PPT9）：通過(guò)推導(dǎo)的方法產(chǎn)生語(yǔ)言 =>1) 定義3.2（PPT10）：直接推導(dǎo)。2) 強(qiáng)調(diào)的兩點(diǎn)：推導(dǎo)具有自反性，推導(dǎo)具有傳遞性。3) 定義3.3（PPT10）：由CFG G所產(chǎn)生的語(yǔ)言L(G)被

21、定義為:l L(G) = S=+> and T* ， l L(G)稱為上下文無(wú)關(guān)語(yǔ)言（Context Free Language, CFL），稱為句子。若S=*>，(NT)*，則稱為G的一個(gè)句型。 4) 定義3.4：在推導(dǎo)過(guò)程中，若每次直接推導(dǎo)均替換句型中最左邊的非終結(jié)符，則稱為最左推導(dǎo)，由最左推導(dǎo)產(chǎn)生的句型被稱為左句型。 6. 推導(dǎo)，分析樹，語(yǔ)法樹。1) 分析樹的性質(zhì)（具體語(yǔ)法樹）：l 根由開始符號(hào)所標(biāo)記。l 每個(gè)葉子都由一個(gè)終結(jié)符，非終結(jié)符，或標(biāo)記。l 每個(gè)內(nèi)部結(jié)點(diǎn)由一個(gè)非終結(jié)符標(biāo)記。l 若A是某內(nèi)部節(jié)點(diǎn)的標(biāo)記，且X1，X2，.，Xn是該節(jié)點(diǎn)從左到右所有孩子的標(biāo)記，則AX1X2

22、.Xn是一個(gè)產(chǎn)生式。若A，則標(biāo)記為A的結(jié)點(diǎn)可以僅有一個(gè)標(biāo)記為的孩子。2) 分析樹與語(yǔ)言和文法的關(guān)系：l 每一直接推導(dǎo)（每個(gè)產(chǎn)生式），對(duì)應(yīng)一顆僅有父子關(guān)系的子樹，即產(chǎn)生式左部非終結(jié)符“長(zhǎng)出”右部的孩子。l 分析樹的葉子，從左到右構(gòu)成G的一個(gè)句型。若葉子僅由終結(jié)標(biāo)記，則構(gòu)成一個(gè)句子。l 最左最右推導(dǎo)的中間過(guò)程對(duì)應(yīng)的分析樹可能不同，因?yàn)榫湫筒煌罱K的分析樹相同，因?yàn)樽罱K是同一個(gè)句子。l 分析樹既反映了產(chǎn)生句型的推導(dǎo)過(guò)程，有反映了句型的結(jié)構(gòu)。3) 語(yǔ)法樹（抽象語(yǔ)法樹）l 定義3.6：對(duì)CFG G的句型，表達(dá)式的語(yǔ)法樹被定義為具有下述性質(zhì)的一棵樹。u 根和內(nèi)部節(jié)點(diǎn)由表達(dá)式中的操作符標(biāo)記。u 葉子由表達(dá)式中的操作數(shù)標(biāo)記。u 用于改變運(yùn)算優(yōu)先級(jí)和結(jié)合性的括弧，被隱含在語(yǔ)法樹的結(jié)構(gòu)中。7. 二義性和二義性的消除1) 二義性：若G對(duì)同一句子產(chǎn)生不止一顆分析樹，則稱G為二義的。（一個(gè)句子多于一顆分析樹，與與文法和句子有關(guān)，與采