第二章形式語言理論

1、第二章第二章 形式語言概論形式語言概論n語言成分語言成分n語言和文法語言和文法n文法的分類文法的分類n語言和語法語言和語法n文法和語言的一些特性文法和語言的一些特性n分析方法簡介分析方法簡介2.1 語言成分語言成分 對程序設計語言的描述是從對程序設計語言的描述是從語法、語義和語用語法、語義和語用三個因素來考慮。三個因素來考慮。語法：語法：是對語言結構的定義。是對語言結構的定義。語義：語義：是描述了語言的含義。是描述了語言的含義。語用：語用：則是從使用的角度去描述語言。則是從使用的角度去描述語言。例例1： 寫出賦值語句寫出賦值語句 s2*3.1416*r*(r+h)的非的非形式化的描述。形式化的

2、描述。語法：賦值語句由一個變量，后隨一個賦值號語法：賦值語句由一個變量，后隨一個賦值號“”，其后面再跟一個表達式構成；，其后面再跟一個表達式構成；語義：首先計算語句右部表達式的值，然后把所得語義：首先計算語句右部表達式的值，然后把所得結果送給左部變量中；結果送給左部變量中；語用：賦值語句可用來計算和保存表達式的值。語用：賦值語句可用來計算和保存表達式的值。 用一組用一組數(shù)學符號數(shù)學符號和和規(guī)則規(guī)則來描述語言的方式稱為來描述語言的方式稱為形形式描述式描述，而把所用的數(shù)學符號和規(guī)則稱為，而把所用的數(shù)學符號和規(guī)則稱為形式語言形式語言。n 形式語言：只是從語法上研究語言。它是抽象的形式語言：只是從語法

3、上研究語言。它是抽象的數(shù)學系統(tǒng)，用于模擬程序設計語言的語法，或者是數(shù)學系統(tǒng)，用于模擬程序設計語言的語法，或者是并不很成功地模擬自然語言（如英語的語法）。并不很成功地模擬自然語言（如英語的語法）。n 形式語言理論是編譯理論的重要基礎，它主要研形式語言理論是編譯理論的重要基礎，它主要研究組成究組成符號語言的符號串的集合及它們的表示法、符號語言的符號串的集合及它們的表示法、結構與特性。結構與特性。形式語言形式語言字母表和符號字母表和符號n字母表字母表: :元素的非空有窮集合，記為元素的非空有窮集合，記為。 例如：例如：=0=01 1 1=1=a ab,cb,c n字母表中至少包含一個元素。字母表中至

4、少包含一個元素。n字母表中的元素，可以是字母、數(shù)字或其他符號。字母表中的元素，可以是字母、數(shù)字或其他符號。n不同的語言有不同的字母表。不同的語言有不同的字母表。符號符號: :字母表中的元素稱為符號或字符。字母表中的元素稱為符號或字符。 由字母表中的符號組成的任何有窮序列。由字母表中的符號組成的任何有窮序列。 例如：例如：0,00,100,00,10是字母表是字母表=0=011上的符號串上的符號串 a,ab,aacaa,ab,aaca是是1=1=a ab,cb,c 上的符號串上的符號串n符號串中的符號是有序的，順序不同符號串中的符號是有序的，順序不同, ,意義不同。意義不同。 例如例如: : a

5、bab和和baba不同不同n不含任何符號的符號串稱為不含任何符號的符號串稱為空串空串，用，用表示。表示。n符號串長度符號串長度: : 符號串中含有符號的個數(shù)。符號串中含有符號的個數(shù)。 例如例如: |: |abcabc|=3|=3| |=0 | |=0 符號串及其運算符號串及其運算1.1.符號串的連接符號串的連接 設設x x、y y是符號串是符號串, ,它們的連接是把它們的連接是把y y的符號寫的符號寫在在 x x的符號之后得到的符號串的符號之后得到的符號串xyxy。 例如：例如： x=STx=ST，y=y=abuabu ，則，則 xyxy= =STabuSTabu 顯然顯然xx = = xx=

6、x=x2.2.符號串的方冪符號串的方冪 把符號串把符號串a(chǎn) a自身連接自身連接n n次得到的符號串次得到的符號串a(chǎn) an n = = aaaaaaaa。例如：例如： a a1 1=a a=a a2 2= =aaaa a a0 0=3.3.符號串集合的乘積符號串集合的乘積 若集合若集合A A中所有元素都是某字母表中所有元素都是某字母表 上的符號上的符號串，則稱串，則稱A A為字母表為字母表 上的符號串集合。上的符號串集合。n符號串集合符號串集合A A和和B B的乘積定義為的乘積定義為: : AB = AB = xy|xAxy|xA且且yByB ，即，即ABAB是由是由A A中的串中的串x x和和

7、B B中的串中的串y y連接而成的串連接而成的串xyxy組成的集合。組成的集合。 例如：集合例如：集合A = A = ab,cdeab,cde B = B = 0,10,1 則則 AB = AB = ab0,ab1,cde0,cde1ab0,ab1,cde0,cde1 顯然顯然 AA = = AA = A = A 注意注意:并不等于空集合并不等于空集合 4.4.符號串集合的方冪符號串集合的方冪 設設A A是符號串的集合，則稱是符號串的集合，則稱A An n為符號串集為符號串集A A的方的方冪，其中冪，其中n n是非負整數(shù)。是非負整數(shù)。A A0 0 = = A A1 1 = A = A A A2

8、 2 = A A= A AA An n = AA. = AA.A(nA(n個個) ) 例如：例如： X= abc X0 ，X1 abc ，X2 abcabc5.5.符號串集合的正閉包符號串集合的正閉包 + + = = 1 12 23 3稱為稱為的正閉包。的正閉包。 + + 表示表示 上的上的除除外的所有有窮長串的集合。外的所有有窮長串的集合。例如：例如：設A= a, b ，則： A+= a, b, aa, ab, ba, bb, aaa, aab, 6.6.符號串集合的自反閉包符號串集合的自反閉包* *=0 01 12 23 3稱為稱為的自反閉包。的自反閉包。 * *表示表示上所有有窮長的串的

9、集合。上所有有窮長的串的集合。 例如：設有字母表例如：設有字母表=0=0，11，則，則 * *=,0,1,00,01,10,11,000,=,0,1,00,01,10,11,000, n自反閉包與正閉包的關系自反閉包與正閉包的關系 * * = = 0 0+ + + + = = * * = = * *例例2：已知：字母表已知：字母表y3=yyy=acacacA2=AA=adad，adc，cad，ccB0=A+= A1A2A3.A*= A0 A1A2A3.2.2 文法和語言文法和語言1 1. .文法的定義文法的定義 是定義或描述語言的語法結構的一組形式規(guī)則。是定義或描述語言的語法結構的一組形式規(guī)則

10、。n文法文法G G（GrammarGrammar）定義為四元組）定義為四元組（V VN N，V VT T，P P，S S） V VN N(Nonternimal(Nonternimal) )：非終結符集。：非終結符集。 V VT T(Terminal(Terminal) )：終結符集。：終結符集。 P(ProductionP(Production) )：產(chǎn)生式（規(guī)則）集合。：產(chǎn)生式（規(guī)則）集合。 S S：開始符號或識別符號。：開始符號或識別符號。是出現(xiàn)在規(guī)則左部能派生出符號或符是出現(xiàn)在規(guī)則左部能派生出符號或符號串的那些符號，即每個非終結符號號串的那些符號，即每個非終結符號表示一定符號串的集合，

11、用表示一定符號串的集合，用大寫字母大寫字母表示表示或用尖括號把非終結符號括起來?；蛴眉饫ㄌ柊逊墙K結符號括起來。是組成語言的基本符是組成語言的基本符號，是一個語言的不號，是一個語言的不可再分的基本符號，可再分的基本符號，通常用通常用小寫字母小寫字母表示。表示。是一個非終結符，且是一個非終結符，且至少要在一條產(chǎn)生式至少要在一條產(chǎn)生式的左部出現(xiàn)。的左部出現(xiàn)。P P中產(chǎn)生式（重寫規(guī)則）形如：中產(chǎn)生式（重寫規(guī)則）形如： A|A| 其中其中AVAVN N且至少含一個非終結符，且至少含一個非終結符，,V,V* *。nV VN N,V,VT T和和P P是非空有窮集。是非空有窮集。nV VN NVVT T=。

12、nV=VV=VN NVVT T，V V稱為文法稱為文法G G的字母表。的字母表。例如：文法例如：文法 G=(VN，VT，P，S ) VN=A VT=0，1 P: A 0 | 1 | A0 | A1 S=A2. 2. 推導和直接推導推導和直接推導 是文法是文法G G的產(chǎn)生式，若有的產(chǎn)生式，若有v v，w w滿足：滿足： v=v=,w,w= =, , 其中其中,V,V* *則稱則稱v v直接推導直接推導出出w w，或，或w w直接歸約直接歸約到到v v，記作記作v vw w。n 直接推導：直接推導：用產(chǎn)生式的右部替換產(chǎn)生式的左部的用產(chǎn)生式的右部替換產(chǎn)生式的左部的過程。過程。n 直接歸約：直接歸約：

13、用產(chǎn)生式的左部替換產(chǎn)生式的右部的用產(chǎn)生式的左部替換產(chǎn)生式的右部的過程。過程。n直接推導序列：直接推導序列： 或或 + + 若存在若存在v=uv=u0 0 u u1 1 . . u un n=w=w, (n0), (n0) 則稱則稱v v w w，v v推導推導出出w w，或，或w w歸約歸約到到v v（至少有（至少有1 1步步推導），這個直接推導序列的長度為推導），這個直接推導序列的長度為n n。n廣義推導：廣義推導： 或或 * * 若有若有v w v w 或或 v=wv=w， 則記為則記為v wv w，v v廣義推導廣義推導出出w w，w w廣義規(guī)約廣義規(guī)約到到v v（可（可以包含以包含0

14、0步推導）。步推導）。 + * + + *三種推導的比較三種推導的比較n直接推導（直接推導（）的長度為）的長度為1 1。n直接推導序列（直接推導序列（ + +）的長度）的長度n1n1。n廣義推導（廣義推導（ * *）的長度）的長度0 0。推導和規(guī)則的區(qū)別推導和規(guī)則的區(qū)別n 形式上的區(qū)別：形式上的區(qū)別：推導用推導用“”，規(guī)則用規(guī)則用“”。n 對文法對文法G G中任何規(guī)則中任何規(guī)則A A，我們有，我們有A A，即，即推導推導的依據(jù)是規(guī)則的依據(jù)是規(guī)則。2.3 文法的分類文法的分類 對文法中的規(guī)則施加不同限制，將文法和語言對文法中的規(guī)則施加不同限制，將文法和語言分為四大類：分為四大類：v0 0型文法（

15、型文法（PSGPSG）：）： 0 0型語言或短語結構語言。型語言或短語結構語言。v1 1型文法（型文法（CSGCSG）：）：1 1型語言或上下文有關語言。型語言或上下文有關語言。v2 2型文法（型文法（CFGCFG）：2 2型語言或上下文無關語言。型語言或上下文無關語言。v3 3型文法（型文法（RGRG）：3 3型語言或正則（正規(guī)）語言。型語言或正則（正規(guī)）語言。 如果對于文法如果對于文法G G，P P中每個規(guī)則具有下列形式：中每個規(guī)則具有下列形式： 其中其中VV+ + ，VV* *，則該文法，則該文法G G為為0 0型文法型文法。相應。相應的語言稱為的語言稱為0 0型語言型語言。例如：文法例

16、如：文法G=(VG=(VN N,V,VT T, P, S), P, S)，其中，其中V VN N=A,B,S V=A,B,S VT T=0,1=0,1 P= S0AB P= S0AB，1B01B0，BSA|01BSA|01，A1SB1A1SB1，A0A0S0B S0B 描述的描述的 0 0 型語言為型語言為 L L0 0(GS)= (GS)= 1.01.0型文法型文法2.1.1型文法型文法( (上下文有關上下文有關) ) 若文法若文法G=(VG=(VN N,V,VT T, P, S), P, S)中的每一條規(guī)則的形式為：中的每一條規(guī)則的形式為： AA 其中其中A VN N , , (VN NV

17、T T)* , (VN NVT T)+，則該文法則該文法G G為為1 1型文法型文法。相應的語言稱為。相應的語言稱為1 1型語言型語言。例如：文法例如：文法G=(VG=(VN N,V,VT T, P, S), P, S)，其中，其中V VN N=B,S V=B,S VT T=a,b,ca,b,c P=P= Sabc|aSBcSabc|aSBc , , bBbbbBbb , , cBBccBBc 描述的描述的1 1型語言為型語言為L L1 1(GS)=(GS)=a an nb bn nc cn n | n | n 113.2.2型文法型文法( (上下文無關上下文無關) ) 若文法若文法G=(VG

18、=(VN N,V,VT T, P, S), P, S)中的每一條規(guī)則的形式為：中的每一條規(guī)則的形式為： A A 其中其中A VN N , (VN NVT T)* , 則該文法則該文法G G為為2 2型文法型文法。相。相應的語言稱為應的語言稱為2 2型語言型語言。例如：文法例如：文法G=(VG=(VN N,V,VT T, P, S), P, S)，其中，其中V VN N=A,B,S V=A,B,S VT T=a,ba,b P=P=SaB|bASaB|bA, , Aa|aS|bAAAa|aS|bAA，Bb|bS|aBBBb|bS|aBB 描述的描述的2 2型語言為型語言為L L2 2(GS)=(G

19、S)=x|xx|x a,ba,b + + 且且x x中中a a和和b b的的個數(shù)相同個數(shù)相同 4.3.3型文法型文法( (右線性文法和正規(guī)文法右線性文法和正規(guī)文法) ) 若文法若文法G=(VG=(VN N,V,VT T, P, S), P, S)中的每一條規(guī)則的形式為：中的每一條規(guī)則的形式為： A Aa a或或 A AaBaB其中其中A，B VN N , a VT T* , 則該文法則該文法G G為為3 3型文法型文法。相應。相應的語言稱為的語言稱為3 3型語言型語言。例如：例如：定義標識符，定義標識符，用用I I代表標識符代表標識符; l; l代表任意一個字母代表任意一個字母; d; d代表

20、任意一個數(shù)字代表任意一個數(shù)字; ; 則定義標識符的文法為：則定義標識符的文法為： P: I l | P: I l | lIlI | | dIdI文法類別文法類別產(chǎn)生式形式產(chǎn)生式形式產(chǎn)生的語言產(chǎn)生的語言說明說明0 0型文法型文法( (短語文法短語文法) )VV+ + , ,且至少含一且至少含一個非終結符，個非終結符，VV* *0 0型語言型語言對產(chǎn)生式基對產(chǎn)生式基本無限制本無限制1 1型文法型文法( (上下文有關文法上下文有關文法) )，| | |=r=r1 1A Ar r2 2，=r=r1 1b br r2 2AVAVN N, , ,V,V* * bVbV+ + 1 1型語言（上下型語言（上下

21、文有關語言）文有關語言）將將A A替換成替換成b b時，必須考時，必須考慮慮A A的上下的上下文文2 2型文法型文法( (上下文無關文法上下文無關文法) )AA，AVAVN N ， VV* *2 2型語言（上下型語言（上下文無關語言）文無關語言）無需考慮無需考慮A A在上下文中在上下文中的出現(xiàn)情況的出現(xiàn)情況3 3型文法型文法( (右線性文法右線性文法) )AaBAaB 或或 AaAa，A,BVA,BVN N ，aVaVT T* *3 3型語言型語言產(chǎn)生式全部產(chǎn)生式全部是規(guī)定形式是規(guī)定形式4種文法的比較種文法的比較aaV VT T，正規(guī)文法，正規(guī)文法例例3：試分析書中：試分析書中P22的例的例2

22、.6、2.7、2.8、2.9、2.10的文法。的文法。n如何判斷如何判斷4種文法種文法 1 1型文法：型文法：|1|1，規(guī)則左部至少有一個非，規(guī)則左部至少有一個非終結符；終結符； 2 2型文法：規(guī)則左部是單個非終結符；型文法：規(guī)則左部是單個非終結符； 3 3型文法：看格式。型文法：看格式。練習：練習：1.設有文法設有文法GA: AyB，BxB|x，寫出該文法，寫出該文法的完整形式及推導。的完整形式及推導。2.設有文法設有文法GA1: S A B，A a A | a，B b B | b，寫出該文法的完整形式及推導。，寫出該文法的完整形式及推導。2.4語言和語法語言和語法1.1.句型、句子和語言句

23、型、句子和語言 設有文法設有文法GSGS，若符號串，若符號串是從開始符推導出來是從開始符推導出來的的, ,即即 S S =* * ，且，且VV* *，則稱，則稱是文法是文法G G的的句型句型。若若僅由終結符組成僅由終結符組成, ,即即 S S =* * ，且，且VVT T* *，則，則稱稱是文法是文法G G的的句子句子。 所有的句子一定是句型，句型不一定是句子。所有的句子一定是句型，句型不一定是句子。例如：文法例如：文法GS： S0S1， S01 S 0S1 00S11 000S111 00001111 句型：句型：S，0S1，00S11，000S111，00001111 句子：句子：0000

24、1111語言：語言：由文法由文法G G生成的語言記為生成的語言記為L(G),L(G),它是文法它是文法G G的一的一切句子的集合切句子的集合, ,即即 L(G)=L(G)=x|Sx|S =+ + x x，且，且 xVxVT T* * 例如：文法例如：文法G G： S0S1S0S1， S01S01 S S0S1 0S1 00S11 00S11 0 03 3S1S13 3 0 0n-1n-1S1S1n-1n-1 0 0n n1 1n n L(G)=0 L(G)=0n n1 1n n|n1|n1 文法文法G G生成的每個終結符號串都在生成的每個終結符號串都在L(G)L(G)中中，L(G)L(G)中的

25、每個串確實能被中的每個串確實能被G G生成生成。文法一旦確定，語言也。文法一旦確定，語言也就唯一，語言可由不同的文法表示。就唯一，語言可由不同的文法表示。2.2.語法樹語法樹 例如：例如：They are students and They are students and teachers of the Physics teachers of the Physics Department.Department.句子句子主語主語系詞系詞表語表語代詞代詞Theyare名詞名詞連接詞連接詞名詞名詞定語定語前置詞前置詞冠詞冠詞名詞名詞名詞名詞studentsandteachersofthePhysi

26、csDepartment 它的結點由符號組成。根結點對應于開始符號。它的結點由符號組成。根結點對應于開始符號。只有非終結符號對應的結點有子結點。并且，一個只有非終結符號對應的結點有子結點。并且，一個結點和它的子結點分別對應于文法中的一個產(chǎn)生式結點和它的子結點分別對應于文法中的一個產(chǎn)生式的左部和右部。的左部和右部。 作為識別句子的輔助工具，語法樹可以表示句作為識別句子的輔助工具，語法樹可以表示句子的結構。子的結構。 直觀地描述上下文無關文法的直觀地描述上下文無關文法的句型推導過程。句型推導過程。給定文法給定文法G=(VG=(VN N,V,VT T,P,S),P,S)，對于，對于G G的任何句型都

27、能構的任何句型都能構造與之關聯(lián)的語法樹。造與之關聯(lián)的語法樹。語法樹的相關概念語法樹的相關概念n 結點：每個樹的結點對應于一個符號。結點的名結點：每個樹的結點對應于一個符號。結點的名字就是該符號。字就是該符號。n 邊：兩個結點之間的連線。邊：兩個結點之間的連線。n 根結點：沒有邊進入的結點。根結點：沒有邊進入的結點。n 分支：某個結點向下射出的邊和其結點稱為分支。分支：某個結點向下射出的邊和其結點稱為分支。n 末端結點：沒有向下射出的邊的結點成為末端結末端結點：沒有向下射出的邊的結點成為末端結點。在相對于句型的語法樹中，末端結點可能是非點。在相對于句型的語法樹中，末端結點可能是非終結符號。終結符

28、號。語法樹的特征語法樹的特征 給定文法給定文法G=(VG=(VN N,V,VT T,P,S),P,S)，對于，對于G G的任何句型都能構造的任何句型都能構造與之關聯(lián)的語法樹。這棵樹具有下列特征：與之關聯(lián)的語法樹。這棵樹具有下列特征：n 根結點的標記是根結點的標記是開始符號開始符號S S；n 每個結點的標記都是每個結點的標記都是V V中的一個符號；中的一個符號；n 若一棵子樹的根結點為若一棵子樹的根結點為A A，且其所有直接子孫的標記，且其所有直接子孫的標記從左向右的排列次序為從左向右的排列次序為A A1 1A A2 2A AR R，那么，那么 A AA A1 1A A2 2.A.AR R一一定

29、是定是P P中的一條規(guī)則；中的一條規(guī)則；n 若一標記為若一標記為A A的結點至少有一個除它以外的子孫，則的結點至少有一個除它以外的子孫，則AVAVN N。構造語法樹構造語法樹方法：方法：把開始符號做把開始符號做為根結點，對每一步為根結點，對每一步直接推導畫一個分支，直接推導畫一個分支，分支的名字是所用產(chǎn)分支的名字是所用產(chǎn)生式右部的符號（按生式右部的符號（按左右順序依次出現(xiàn)），左右順序依次出現(xiàn)），分支的個數(shù)是產(chǎn)生式分支的個數(shù)是產(chǎn)生式右部符號串的長度。右部符號串的長度。以此往下，直到再無以此往下，直到再無分支可畫結束。分支可畫結束。例如：文法例如：文法GS:GS: SAB, SAB, BcBdBc

30、Bd, , AabAab, , BcdBcd符號串符號串a(chǎn)bccddabccdd的的推導過程如下：推導過程如下：S SA AB BAcAcB Bd dA AccddccddabccddabccddSBBdbaAcdcS（1）SBA（2）SBBdAc（3）SBBdbaAcdc（5）SBBdAcdc（4）SABAcBdAccddabccdd例例4：已知：已知文法文法G G：EE+T|TEE+T|T，TTTTF|FF|F，F(xiàn)F（E E）|i|i 求句型求句型T+TT+TF F的推導過程與語法樹。的推導過程與語法樹。EET+TFTE=E+T =T+T=T+TFEET+TFTE=E+T =E+TF =T

31、+TF從語法樹中看不出句型中的符號被替代的順序。從語法樹中看不出句型中的符號被替代的順序。2.5 文法和語言的一些特性文法和語言的一些特性n 無用非終結符：無用非終結符：某個非終結符不出現(xiàn)在文法的任何一個句型中，并且不能從它推出終結符號串。含有該非終結符的規(guī)則即不可終止。n 不可達文法符號：不可達文法符號：如果一個非終結符（開始符號除外）不出現(xiàn)在該文法的任何其他的產(chǎn)生式的右部。該非終結符為不可達文法符號，含有該非終結符的規(guī)則即不可達規(guī)則。n 有害規(guī)則：有害規(guī)則：UU ，無用且引起文法的二義。n 可空非終結符：可空非終結符： 2型文法允許以下產(chǎn)生式 S，該產(chǎn)生式稱為空產(chǎn)生式，S稱為可空非終結符。

32、在消除左遞歸方法中用到空產(chǎn)生式。 例如：文法例如：文法GS： （1）SBe （2） BAf （3） AAe （4） Ae （5） CCf （6） Df 多余規(guī)則為：（多余規(guī)則為：（5）不可終止）不可終止 （6）不可到達）不可到達最左推導、最右推導和規(guī)范推導最左推導、最右推導和規(guī)范推導是指對于一個推導序列中的每一步直接是指對于一個推導序列中的每一步直接推導推導 =，都對，都對 中的中的最左最左非終結符進行替換。非終結符進行替換。是指對于一個推導序列中的每一步直接是指對于一個推導序列中的每一步直接推導推導 =，都對，都對 中的中的最右最右非終結符進行替換。非終結符進行替換。n 最右推導也稱為最右推

33、導也稱為規(guī)范推導規(guī)范推導，用規(guī)范推導推導出的句，用規(guī)范推導推導出的句型稱為型稱為規(guī)范句型規(guī)范句型。例例5：已知：已知文法文法GSGS：SABSAB，AA0|1BAA0|1B，B0|S1B0|S1 求求句子句子101001的最右、最左推導。的最右、最左推導。S右右=A =AS1=AAB1=AA01 =A1B01=A1001=1B1001=101001S左左=AB=1BB=10B=10S1=10AB1 =101BB1=1010B1=101001例如：文法例如：文法G G：EE+E|EEE+E|EE|E|（E E）|i|i 句子句子 i ii+ii+i 對應的語法樹對應的語法樹最左推導最左推導1 1

34、：E EE E+E+EE EE E+E+Ei iE E+E+Ei ii i+ +E Ei ii+i+i i最左推導最左推導2 2：E EE EE Ei iE Ei iE E+E+Ei ii i+ +E Ei ii+i+i iiEE+EEEiiEEEiEE+ii文法的二義性文法的二義性(Ambiguity)(Ambiguity) 如果一個文法存在某個句子對應兩棵或者兩棵如果一個文法存在某個句子對應兩棵或者兩棵以上不同的語法樹，則說這個文法是以上不同的語法樹，則說這個文法是二義的二義的。二義二義性文法存在某個句子性文法存在某個句子, ,它它有兩個不同的最左（右）有兩個不同的最左（右）推導。推導。

35、二義性的文法將給編譯程序的執(zhí)行帶來問題。二義性的文法將給編譯程序的執(zhí)行帶來問題。當編譯程序?qū)Χx性文法生成的句子結構進行語法當編譯程序?qū)Χx性文法生成的句子結構進行語法分析時，就會產(chǎn)生兩種甚至更多種不同的理解。語分析時，就會產(chǎn)生兩種甚至更多種不同的理解。語法結構上的不確定性，必將導致語義處理上的不確法結構上的不確定性，必將導致語義處理上的不確定性。因此，希望描述語言的文法是無二義性的。定性。因此，希望描述語言的文法是無二義性的。消除文法的二義性消除文法的二義性n 方法一：方法一：不改變文法中原有的語法規(guī)則，僅加不改變文法中原有的語法規(guī)則，僅加進一些語法的非形式規(guī)定。進一些語法的非形式規(guī)定。n 方法二：方法二：構造一個等價的無二義性的文法，即構造一個等價的無二義性的文法，即把排除二義性的規(guī)則合并到原有文法中，改寫原把排除二義性的規(guī)則合并到原有文法中，改寫原有的文法。有的文法。2.6 分析方法簡介分析方法簡介