1、編譯原理編譯原理(第三版第三版) 陳火旺等編著22022-3-1第二章第二章 高級語言及其語法描述高級語言及其語法描述 n常用的高級語言常用的高級語言 FORTRANFORTRAN數值計算數值計算 COBOLCOBOL事務處理事務處理 PASCALPASCAL結構程序設計結構程序設計 ADAADA大型程序、嵌入式實時系統大型程序、嵌入式實時系統 PROLOGPROLOG邏輯程序設計邏輯程序設計 ALGOLALGOL算法語言算法語言 C/C+C/C+系統程序設計系統程序設計 JavaJavaInternetInternet程序設計程序設計32022-3-1n與機器語言或匯編語言比較與機器語言或匯

2、編語言比較，高級語言高級語言的的優點優點：較接近于數學語言和工程語言較接近于數學語言和工程語言，比較直觀、比較直觀、自然和易于理解自然和易于理解; ;便于驗證其正確性便于驗證其正確性，易于改錯易于改錯; ;編寫效率高編寫效率高; ;易于移植易于移植. .42022-3-12.12.1 程序語言的定義程序語言的定義n程序語言由兩方面定義：程序語言由兩方面定義：語法語法語義語義 ( (語用語用- -語言成分的使用方法語言成分的使用方法) )52022-3-1一一. 語法語法n程序本質上是一定字符集上的字符串。程序本質上是一定字符集上的字符串。n語法語法：一組規則：一組規則，用它可以形成和產生一用它

3、可以形成和產生一個個合式合式(well-formed)的程序的程序。62022-3-1n詞法規則詞法規則：單詞符號的形成規則：單詞符號的形成規則。單詞符號是語言中具有獨立意義的最基本結構單詞符號是語言中具有獨立意義的最基本結構。一般包括：常數、標識符、基本字、算符、界符一般包括：常數、標識符、基本字、算符、界符等。等。描述工具：有限自動機描述工具：有限自動機n語法規則語法規則：語法單位的形成規則：語法單位的形成規則。語法單位通常包括：表達式、語句、分程序、過語法單位通常包括：表達式、語句、分程序、過程、函數、程序等程、函數、程序等; ;描述工具：上下文無關文法描述工具：上下文無關文法72022

4、-3-1 Ei EiEE+EEE+EEEEE* *E EE(E)E(E)n語法規則和詞法規則定義了程序的的形語法規則和詞法規則定義了程序的的形式結構。定義語法單位的意義屬于語義式結構。定義語法單位的意義屬于語義問題。問題。82022-3-1二二. . 語義語義n語義語義：一組規則：一組規則，用它可以定義一個程用它可以定義一個程序的意義序的意義。n描述方法：描述方法：自然語言描述：隱藏錯誤、二義性和不完整自然語言描述：隱藏錯誤、二義性和不完整性性形式描述：形式描述：F 操作語義操作語義(PL/1)(PL/1)F 指稱語義指稱語義(ADA)(ADA)F 代數語義代數語義(PASCAL)(PASCA

5、L)92022-3-1三程序語言的基本功能和層次結構三程序語言的基本功能和層次結構n程序語言的基本功能：描述數據和對數據程序語言的基本功能：描述數據和對數據的運算。的運算。n所謂程序，本質上說是描述一定數據的處所謂程序，本質上說是描述一定數據的處理過程。理過程。102022-3-1程序的層次結構：程序的層次結構：程序程序| |子程序或分程序、過程、函數子程序或分程序、過程、函數| |語句語句| |表達式表達式| |數據引用數據引用 算符算符 函數調用函數調用112022-3-1程序語言每個組成成分的邏輯和實現意義程序語言每個組成成分的邏輯和實現意義 n抽象的邏輯的意義抽象的邏輯的意義數學意義數

6、學意義 n計算機實現的意義計算機實現的意義具體實現具體實現122022-3-12.2 2.2 高級語言的一般特性高級語言的一般特性 2.2.1 2.2.1 高級語言的分類高級語言的分類 強制式語言強制式語言(Imperative Languge)(Imperative Languge)也稱過程式語也稱過程式語言：命令驅動，面向語句言：命令驅動，面向語句nFORTRANFORTRAN、C C、PascalPascal，Ada Ada 應用式語言應用式語言（Applicative LanguageApplicative Language）：注重程）：注重程序所表示的功能，而不是一個語句接一個語句地

7、序所表示的功能，而不是一個語句接一個語句地執行執行nLISPLISP、ML ML 132022-3-1基于規則的語言基于規則的語言（Rule-based LanguageRule-based Language）：檢查）：檢查一定的條件，當它滿足值，則執行適當的動作一定的條件，當它滿足值，則執行適當的動作nProlog Prolog 面向對象語言面向對象語言（Object-Oriented LanguageObject-Oriented Language）：）：封裝性封裝性、繼承性繼承性和和多態性多態性nSmalltalkSmalltalk，C+C+，Java Java 142022-3-12.

8、2.2 2.2.2 程序結構程序結構n FORTRANFORTRAN一個程序由一個主程序段和若干輔程序段組成。一個程序由一個主程序段和若干輔程序段組成。輔程序段可以是子程序、函數段或數據塊。輔程序段可以是子程序、函數段或數據塊。每個程序段有一系列的說明語句和執行語句組成。每個程序段有一系列的說明語句和執行語句組成。各段可以獨立編譯。各段可以獨立編譯。 模塊結構，沒有嵌套和遞歸模塊結構，沒有嵌套和遞歸各程序段中的名字相互獨立各程序段中的名字相互獨立，同一個標識符在不，同一個標識符在不同的程序段中代表不同的名字同的程序段中代表不同的名字。152022-3-1主程序主程序 PROGRAM PROGR

9、AM end end輔程序輔程序1 1 SUBROUTINE SUBROUTINE end end輔程序輔程序2 2 FUNCTION FUNCTION end end162022-3-1nPASCALPASCAL程序本身可以看成是一個操作系程序本身可以看成是一個操作系統所調用的過程，過程可以嵌套和遞歸。統所調用的過程，過程可以嵌套和遞歸。一個一個PASCAL過程：過程：過程頭；過程頭；說明段（由一系列的說明語句組成）；說明段（由一系列的說明語句組成）；begin執行體（由一系列的執行語句組成）；執行體（由一系列的執行語句組成）；end172022-3-1作用域作用域：一個名字能被使用的區域范

10、圍：一個名字能被使用的區域范圍稱作這個名字的作用域。稱作這個名字的作用域。允許同一個標識符在不同的過程中代表允許同一個標識符在不同的過程中代表不同的名字。不同的名字。名字作用域規則名字作用域規則- 最近嵌套原則最近嵌套原則 n一個在子程序一個在子程序B1中說明的名字中說明的名字X只在只在B1中中有效（局部于有效（局部于B1）；）；n如果如果B2是是B1的一個內層子程序且的一個內層子程序且B2中對中對標識符標識符X沒有新的說明，則原來的名字沒有新的說明，則原來的名字X在在B2中仍然有效。如果中仍然有效。如果B2對對X重新作了說明，重新作了說明，那么，那么，B2對對X的任何引用都是指重新說明的任何

11、引用都是指重新說明過的這個過的這個X。182022-3-1program main var A, B : real; procedure P1 var B:boolean; begin end procedure P2 var A:integer; begin endbegin endA(real)B(real)B(bool)A(integer)192022-3-1PASCAL提供了豐富的數據類型和運算提供了豐富的數據類型和運算方式，它允許用戶動態地申請和退還存方式，它允許用戶動態地申請和退還存貯空間。貯空間。202022-3-1nADA程序包程序包(package)：把數據和操作代碼封裝在：

12、把數據和操作代碼封裝在一起，支持數據抽象。一起，支持數據抽象。一個程序包分為兩部分：一個程序包分為兩部分：n可見的規范說明部分，它定義了程序包外面可以訪可見的規范說明部分，它定義了程序包外面可以訪問的對象。問的對象。n程序包體，它實際定義程序包的實現細節。程序包體，它實際定義程序包的實現細節。212022-3-1package STACKS is type ELEM is private; type STACK is limited private; procedure push (S: in out STACK; E: in ELEM); procedure pop (S: in out S

13、TACK; E: out ELEM); end STACK;package body STACKS is procedure push(S: in out STACK; E: in ELEM); begin 實現細節實現細節 end push; procedure pop (S: in out STACK; E: out ELEM); begin 實現細節實現細節 end pop;end; 222022-3-1nJAVAJava是一種面向對象的高級語言是一種面向對象的高級語言n類（類（Class）n繼承繼承(Inheritance)n多態性多態性(Polymorphism)和動態綁定和動態綁定

14、(Dynamic binding)232022-3-1class Car int color_number; int door_number; int speed; push_break ( ) add_oil ( ) class Trash_Car extends car double amount; fill_trash ( ) 242022-3-12.2.3 2.2.3 數據類型與操作數據類型與操作 n一個數據類型通常包括以下三種要素：一個數據類型通常包括以下三種要素：用于區別這種類型數據對象的用于區別這種類型數據對象的屬性屬性這種類型的數據對象可以具有的這種類型的數據對象可以具有的值值

15、可以作用于這種類型的數據對象的可以作用于這種類型的數據對象的操作操作252022-3-12.2.3 2.2.3 數據類型與操作數據類型與操作 一初等數據類型一初等數據類型數值類型：整型、實型、復數、雙精度，運算：數值類型：整型、實型、復數、雙精度，運算：+ +，- -，* *，/ / 等等邏輯類型：布爾運算：邏輯類型：布爾運算：，字符類型：符號處理字符類型：符號處理指針類型指針類型262022-3-1標識符與名字標識符與名字n標識符標識符：以字母開頭的：以字母開頭的，由字母數字組成由字母數字組成的字符串的字符串。n標識符標識符與與名字名字兩者有本質區別：兩者有本質區別：標識符標識符是語法概念是

16、語法概念名字名字有確切的意義和屬性有確切的意義和屬性272022-3-1標識符與名字標識符與名字n名字：名字：值：單元中的內容值：單元中的內容屬性：類型和作用域屬性：類型和作用域n名字的性質的說明方式：名字的性質的說明方式：由說明語句來明確規定的由說明語句來明確規定的隱含說明：隱含說明：FORTRAN FORTRAN 以以I,J,K,I,J,K,N N為首的名字為首的名字代表整型，否則為實型。代表整型，否則為實型。動態動態確定：確定：“走到哪里，是什么，算什么走到哪里，是什么，算什么”（運行時才能確定）（運行時才能確定） 282022-3-1二二 數據結構數據結構1 1 數組數組n邏輯上，數組

17、是由同一類型數據所組成邏輯上，數組是由同一類型數據所組成的某種的某種n n維矩形結構，沿著每一維的距離，維矩形結構，沿著每一維的距離，稱為稱為下標下標。數組可變與不可變：編譯時能否確定其存貯數組可變與不可變：編譯時能否確定其存貯空間的大小。空間的大小。訪問：給出數組名和下標值訪問：給出數組名和下標值存放方式存放方式: : 按行存放按行存放, ,按列存放按列存放292022-3-1數組元素地址計算數組元素地址計算n數組數組A10,20A10,20的的A1A1，11為為a a，各維下標各維下標為為1 1開始，按行存放，那么開始，按行存放，那么AiAi，jj地址地址為：為： a+(i-1)a+(i-

18、1)* *20+(j-1)20+(j-1)302022-3-1內情向量內情向量n把數組的有關信息記錄在一個把數組的有關信息記錄在一個“內情向內情向量量”中，每個數組的內情向量必須包括：中，每個數組的內情向量必須包括：維數，各維的上、下限，首地址，以維數，各維的上、下限，首地址，以及數組（元素）的類型。及數組（元素）的類型。l1 u1 d1 l2 u2 d2 ln un dn n C type a 312022-3-12 2 記錄記錄n邏輯上說，記錄結構由已知類型的數據組邏輯上說，記錄結構由已知類型的數據組合在一起的一種結構。合在一起的一種結構。record char NAME20; integ

19、er AGE; bool MARRIED; CARD1000n訪問：復合名訪問：復合名 CARDk.NAMECARDk.NAMEn存儲：連續存放存儲：連續存放n域的地址計算：相對于記錄結構起點的相域的地址計算：相對于記錄結構起點的相對數對數OFFSETOFFSET。322022-3-13 3 字符串、表格、棧字符串、表格、棧n字符串：符號處理、公式處理字符串：符號處理、公式處理n表格：本質上是一種記錄結構表格：本質上是一種記錄結構n線性表：一組順序化的記錄結構線性表：一組順序化的記錄結構n棧：一種線性表，后進先出，棧：一種線性表，后進先出，POP, PUSHPOP, PUSH332022-3-

20、1三三 抽象數據類型抽象數據類型 n一個抽象數據類型包括：一個抽象數據類型包括：數據對象的一個集合；數據對象的一個集合；作用于這些數據對象的抽象運算的集合；作用于這些數據對象的抽象運算的集合；這種類型對象的封裝，即，除了使用類型中所定義這種類型對象的封裝，即，除了使用類型中所定義的運算外，用戶不能對這些對象進行操作。的運算外，用戶不能對這些對象進行操作。n程序設計語言對抽象數據類型的支持程序設計語言對抽象數據類型的支持Ada語言通過程序包（語言通過程序包（package）提供了數據封裝）提供了數據封裝的支持的支持Smalltalk、C+和和Java語言則通過類（語言則通過類（Class）對）對

21、抽象數據類型提供支持。抽象數據類型提供支持。 342022-3-12.2.4 2.2.4 語句與控制結構語句與控制結構一表達式一表達式表達式由運算量（也稱操作數，即數據引用或表達式由運算量（也稱操作數，即數據引用或函數調用）和算符（操作符）組成。函數調用）和算符（操作符）組成。形式：中綴、前綴、后綴形式：中綴、前綴、后綴 X X* *Y -A PY -A P352022-3-1n表達式形成規則（表達式形成規則（p23）（1 1）變量（包括下標變量）、常數是表達式；）變量（包括下標變量）、常數是表達式；（2 2）若）若E1E1、E2E2為表達式，為表達式，為二元算符，則為二元算符，則 E1 E2

22、 E1 E2 為表達式；為表達式；（3 3）若）若E E為表達式，為表達式，為一元算符，則為一元算符，則EE為表達式；為表達式；（4 4）若）若E E為表達式，則（為表達式，則（E)E)是表達式。是表達式。362022-3-1算符的優先次序算符的優先次序n一般的規定一般的規定PASCALPASCAL：左結合左結合A+B+C=(A+B)+CFORTRANFORTRAN：對于滿足左、右結合的算符可任：對于滿足左、右結合的算符可任取一種，如取一種，如A+B+CA+B+C就可以處理成就可以處理成(A+B)+C(A+B)+C，也，也可以處理成可以處理成A+(B+C)A+(B+C)。n注意兩點注意兩點：代

23、數性質能引用到什么程度視具體的語言不代數性質能引用到什么程度視具體的語言不同而不同；同而不同；在數學上成立的代數性質在計算機上未必完在數學上成立的代數性質在計算機上未必完全成立。全成立。372022-3-1二語句二語句n賦值語句：賦值語句： A := BA := B 名字特征：名字特征： ( (了解了解) )左值左值：該名字代表的那個單元（地址）稱為該：該名字代表的那個單元（地址）稱為該名字的左值。名字的左值。( (所代表的存貯單元的地址所代表的存貯單元的地址) )右值右值：一個名字的值稱為該名字的右值。：一個名字的值稱為該名字的右值。( (所所代表的存貯單元的內容代表的存貯單元的內容) )3

24、82022-3-1n控制語句：控制語句： l無條件轉移語句無條件轉移語句 goto Ll條件語句條件語句 if B then S if B then S1 else S2l循環語句循環語句 while B do S repeat S until B for i:=E1 step E2 until E3 do Sl過程調用語句過程調用語句 call P(X1, X2, . ,Xn)l返回語句返回語句 return (E)392022-3-1n說明語句：定義各種不同數據類型的變量說明語句：定義各種不同數據類型的變量或運算，定義名字的性質。或運算，定義名字的性質。402022-3-1簡單句和復合句簡

25、單句和復合句n簡單句：不包含其他語句成分的基本句簡單句：不包含其他語句成分的基本句n復合句：句中有句的語句復合句：句中有句的語句412022-3-1復習：程序語言的定義復習：程序語言的定義n程序語言由兩方面定義：程序語言由兩方面定義：語法語法：一組規則：一組規則，用它可以形成和產生一個合用它可以形成和產生一個合式式(well-formed)的程序的程序n詞法規則詞法規則：單詞符號的形成規則：單詞符號的形成規則。常數、標識符、基本字、算符、界符等。常數、標識符、基本字、算符、界符等。有限自動機有限自動機n語法規則語法規則：語法單位的形成規則：語法單位的形成規則。表達式、語句、分程序、過程、函數、

26、程序等表達式、語句、分程序、過程、函數、程序等; ;上下文無關文法上下文無關文法語義語義: :一組規則一組規則，用它可以定義一個程序的意義用它可以定義一個程序的意義422022-3-1復習：程序語言的基本功能和層次結構復習：程序語言的基本功能和層次結構n程序語言的基本功能：描述數據和對數據的運算。程序語言的基本功能：描述數據和對數據的運算。n所謂程序，本質上說是描述一定數據的處理過程。所謂程序，本質上說是描述一定數據的處理過程。程序程序| |子程序或分程序、過程、函數子程序或分程序、過程、函數| |語句語句| |表達式表達式| |數據引用數據引用 算符算符 函數調用函數調用432022-3-1

27、復習：復習：高級語言的一般特性高級語言的一般特性 n高級語言的分類高級語言的分類 n程序結構程序結構n數據類型與操作數據類型與操作初等數據類型初等數據類型數據結構數據結構抽象數據類型抽象數據類型n語句與控制結構語句與控制結構442022-3-12.3 2.3 程序語言的語法描述程序語言的語法描述 n幾個概念幾個概念: :考慮一個考慮一個有窮有窮 字母表字母表 字符集字符集其中每一個元素稱為一個其中每一個元素稱為一個字符字符上的上的字字( (也叫也叫字符串字符串) )是指由是指由中的字符所中的字符所構成的一個有窮序列構成的一個有窮序列不包含任何字符的序列稱為不包含任何字符的序列稱為空字空字，記為

28、，記為用用* *表示表示上的所有字的全體上的所有字的全體, ,包含空字包含空字例如例如: : 設設 =a=a，bb，則，則 * *=,a,b,aa,ab,ba,bb,aaa,.=,a,b,aa,ab,ba,bb,aaa,.452022-3-1n*的子集的子集U和和V的的連接連接（積積）定義為）定義為UV | U & V n設：設：U a, aa V b, bb 那么：那么：UV = ab, abb, aab, aabb VU = ？462022-3-1n*的子集的子集U和和V的的連接連接（積積）定義為）定義為UV | U & V nV自身的自身的 n次次積積記為記為Vn = V

29、VVn規定規定V0 = ，令，令 V* = V0 V1 V2 V3 稱稱V*是是V的的閉包閉包;n記記 VVV* ，稱，稱V+是是V的正規閉包。的正規閉包。472022-3-1n設：設：U a, aa n那么：那么： U* = , a, aa, aaa, aaaa, U = a, aa, aaa, aaaa, n注意：注意：空集空集 、 、 、| |482022-3-12.3.1 2.3.1 上下文無關文法上下文無關文法n文法文法： 描述語言的語法結構的形式規則描述語言的語法結構的形式規則nHe gave me a book. He He me me book book a a gave ga

30、ve492022-3-1 He me book a gave He He He gave He gave He gave me He gave me He gave me a He gave me a book502022-3-1n上下文無關文法的定義上下文無關文法的定義： 一個上下文無關文法一個上下文無關文法G G是一個四元式是一個四元式 G=(VG=(VT T，V VN N，S S，P)P)，其中，其中V VT T：終結符集合：終結符集合( (非空非空) )V VN N：非終結符集合：非終結符集合( (非空非空) )，且，且V VT T V VN N= =S S：文法的開始符號，：文法的開

31、始符號，S S V VN NP P：產生式集合：產生式集合( (有限有限) )，每個產生式形式為，每個產生式形式為P P， P P V VN N， ( (V VT T V VN N) )* *開始符開始符S S至少必須在某個產生式的左部出現至少必須在某個產生式的左部出現一次。一次。組成語言的不可再分基本符號能派生出符號或符號串的那些符號512022-3-1n例，定義只含例，定義只含+，*的算術表達式的文法的算術表達式的文法 G = ， 其中，其中，P由下列產生式組成：由下列產生式組成：E iE E+EE E*EE (E)522022-3-1n幾點規定：幾點規定：“ ”也可以用也可以用“:=表示

32、，表示， 這種表示稱為巴這種表示稱為巴科斯范式科斯范式(BNF) P 1 P 2 可縮寫為可縮寫為 P 1| 2| n P n 其中，其中，“|”讀成讀成“或或”，稱為，稱為P的一個候選式。的一個候選式。表示一個文法時，通常只給出開始符號和產生式，表示一個文法時，通常只給出開始符號和產生式，如上例，可表示為：如上例，可表示為：G(E)： E i | E+E | E*E | (E)532022-3-1n幾點規定：幾點規定：“ ”也可以用也可以用“:=表示，表示， 這種表示稱為巴這種表示稱為巴科斯范式科斯范式(BNF) P 1 P 2 可縮寫為可縮寫為 P 1| 2| n P n 其中，其中，“|

33、”讀成讀成“或或”，稱為，稱為P的一個候選式。的一個候選式。表示一個文法時，通常只給出開始符號和產生式，表示一個文法時，通常只給出開始符號和產生式，如上例，可表示為：如上例，可表示為：G(E)： E i | E+E | E*E | (E)n例，定義只含例，定義只含+，*的算術表達式的文法的算術表達式的文法 G=， 其中，其中，P由下列產生式組成：由下列產生式組成：E iE E+EE E*EE (E)542022-3-1n定義：稱定義：稱 A 直接推出直接推出，即，即 A 僅當僅當A 是一個產生式，是一個產生式， 且且 ， (VT VN)* 。n如果如果 1 2 n，則我們稱這個序，則我們稱這個

34、序列是從列是從 1到到 n的一個的一個推導推導。若存在一個從。若存在一個從 1到到 n的推導，則稱的推導，則稱 1可以可以推導推導出出 n 。n對文法對文法G(E)： E i | E+E | E*E | (E)E (E) (E+E) (i+E) (i+i)552022-3-1n通常，用通常，用 表示：從表示：從 1 1出發，經過出發，經過一步或若干步，可以推出一步或若干步，可以推出 n n。（。（推導推導）n*1 用用 表示：從表示：從 1 1出發，經過出發，經過0 0步或步或若干步，可以推出若干步，可以推出 n n。（。（廣義推導廣義推導）* 所以所以 ： 即即 或或n1562022-3-1

35、q定義：假定定義：假定G G是一個文法，是一個文法，S S 是它的開始符號。是它的開始符號。如果如果 ，則稱，則稱 是一個是一個句型句型。僅含終結。僅含終結符號的句型是一個符號的句型是一個句子句子。文法。文法G G所產生的句子的所產生的句子的全體是一個全體是一個語言語言，將它記為，將它記為 L(G)L(G)。*S ,|)(*TV SGL572022-3-1n例：例： (i*i+i)是文法是文法 G(E)： E i | E+E | E*E | (E) 的一個句子。的一個句子。 證明：證明： E (E) (E+E) (E*E+E) (i*E+E) (i*i+E) (i*i+i) E，(E)，(E*

36、E+E)，(i*i+i)是句型。是句型。582022-3-1q例：文法例：文法G1(A)：A c|AbG1(A)的語言的語言?L(G1)=c，cb，cbb，以以c開頭，后繼若干個開頭，后繼若干個b592022-3-1n例：文法例：文法G2(S)：S ABA aA|aB bB|bG2(S)的語言的語言?L(G2)=ambn|m，n0602022-3-1q例：給出產生語言為例：給出產生語言為anbn|n 1的文法。的文法。 G3(S)： S aSb S ab612022-3-1q例：給出產生語言為例：給出產生語言為ambn|1 n m 2n的的文法。文法。 G4(S)： S aSb | aaSb

37、S ab | aab 622022-3-1n從一個句型到另一個句型的推導往往不唯從一個句型到另一個句型的推導往往不唯一。一。 E+Ei+Ei+i E+EE+ii+in最左推導最左推導：任何一步：任何一步 都是對都是對 中的最中的最左非終結符進行替換。左非終結符進行替換。 最右推導最右推導：任何一步：任何一步 都是對都是對 中的最中的最右非終結符進行替換。右非終結符進行替換。632022-3-12.3.2 2.3.2 語法樹與二義性語法樹與二義性n用一張圖表示一個句型的推導用一張圖表示一個句型的推導, ,稱為語法樹。稱為語法樹。n(i(i* *i+i)i+i)的語法樹的語法樹Ei+*()EiiE

38、EEEE (E)(E+E)(E*E+E)(i*E+E)(i*i+E)(i*i+i)E (E)(E+E)(E+i)(E*E+i)(E*i+i)(i*i+i) 一棵語法樹是不同推導過程的共性抽象。一棵語法樹是不同推導過程的共性抽象。G(E)： E i | E+E | E*E | (E)(i*i+i)642022-3-1n如果使用最左如果使用最左( (右右) )推導，則一個最左推導，則一個最左( (右右) )推導與語法樹一一對應。推導與語法樹一一對應。n一個句型是否只對應唯一一棵語法樹？一個句型是否只對應唯一一棵語法樹？Ei+*()EiiEEEEE+*()EiEEiiEE652022-3-1n定義定

39、義：如果一個文法存在某個句子對應兩如果一個文法存在某個句子對應兩顆不同的語法樹顆不同的語法樹，則說這個則說這個文法是二義的文法是二義的。G(E)： E i|E+E|E*E|(E) 是二義文法。是二義文法。n語言語言的二義性：一個的二義性：一個語言是二義性的語言是二義性的，如，如果對它不存在無二義性的果對它不存在無二義性的文法文法。可能存在可能存在G和和G，一個為二義的，一個為無二，一個為二義的，一個為無二義的。但義的。但L(G)=L(G)n二義性問題是不可判定問題，即不存在一二義性問題是不可判定問題，即不存在一個算法，它能在有限步驟內，確切地判定個算法，它能在有限步驟內，確切地判定一個文法是否是二義的。一個文法是否是二義的。n可以找到一組無二義文法的充分條件。可以找到一組無二義文法的充分條件。662022-3-1二義文法：二義文法：G(E)： E i|E+E|E*E|(E)表達式表達式 項項|表達式表達式+項項項項 因子因子 | 項項*因子因子因子因子 (表達式表達式) | i無二義文法：無二義文法： G(E)：E T | E+T T F | T*F F (E) | i672022-3-1)EEEFFTTTTi+*(EFi