編譯原理高級語言及其文法

1、第二章 高級語言(yyn)及其文法School of Computer Science & Technology Harbin Institute of Technology重點：文法的定義(dngy)與分類，CFG的語法樹及二義性、程序設(shè)計語言的定義。 難點：程序設(shè)計語言的語義定義。 共七十七頁2022/7/182第2章高級語言(yyn)及其文法2.1 語言概述2.2 基本定義2.3 文法的定義2.4 文法的分類(fn li)2.5 CFG的語法樹2.6 CFG的二義性2.7 本章小結(jié)共七十七頁2022/7/1832.1 語言(yyn)概述什么(shn me)是語言？語言是一定的群體用來進行

2、信息交流的工具。共七十七頁2022/7/1842.1 語言(yyn)概述信息交流的基礎(chǔ)是什么？按照共同約定的生成規(guī)則(guz)和理解規(guī)則(guz)去生成“句子”和理解“句子”例：“今節(jié)日上課始開譯第一編”“今日開始上第一節(jié)編譯課”共七十七頁2022/7/1852.1 語言(yyn)概述語言的特征自然語言(Natural Language)是人與人的通訊工具語義(semantics):環(huán)境、背景知識、語氣、二義性難以形式化計算機語言(Computer Language)計算機系統(tǒng)間、人機間通訊工具嚴(yán)格的語法(yf)(Grammar)、語義(semantics) 易于形式化：嚴(yán)格共七十七頁2022

3、/7/1862.1 語言(yyn)概述語言的描述方法現(xiàn)狀自然語言：自然、方便-非形式化數(shù)學(xué)語言（符號）：嚴(yán)格(yng)、準(zhǔn)確-形式化形式化描述高度的抽象，嚴(yán)格的理論基礎(chǔ)和方便的計算機表示。共七十七頁2022/7/1872.1 語言(yyn)概述語言形式化的內(nèi)容提取語言(Language)：滿足一定條件的句子集合句子(Sentence)：滿足一定規(guī)則的單詞序列單詞(Token)：滿足一定規(guī)則的字符(Character)串語言是字和組合(zh)字的規(guī)則例（自然語言：第譯始二天課今開編上節(jié)）今天開始上第二節(jié)編譯課共七十七頁2022/7/1882.1 語言(yyn)概述語言(yyn)是字及其組合規(guī)則的

4、統(tǒng)一體共七十七頁2022/7/1892.1 語言(yyn)概述程序設(shè)計語言形式化的內(nèi)容提取程序設(shè)計語言(Programming Language)：組成程序的所有語句的集合。程序(Program)：滿足(mnz)語法規(guī)則的語句序列。語句(Sentence) ：滿足語法規(guī)則的單詞序列。單詞(Token) ：滿足詞法規(guī)則的字符串。例：變量:=表達式if 條件表達式 then 語句while 條件表達式 do 語句call 過程名(參數(shù)表)共七十七頁2022/7/18102.1 語言(yyn)概述描述形式文法(wnf)語法語句語句的組成規(guī)則描述方法：BNF范式、語法(描述)圖詞法單詞單詞的組成規(guī)則描

5、述方法：BNF范式、正規(guī)式共七十七頁2022/7/1811形式語言與自動機理論(lln)的產(chǎn)生與作用語言學(xué)家Chomsky最初從產(chǎn)生語言的角度(jiod)研究語言。1956年，通過抽象，他將語言形式地定義為是由一個字母表中的字母組成的一些串的集合?？梢栽谧帜副砩习凑找欢ǖ囊?guī)則定義一個文法（Grammar），該文法所能產(chǎn)生的所有句子組成的集合就是該文法產(chǎn)生的語言。共七十七頁2022/7/1812形式語言與自動機理論(lln)的產(chǎn)生與作用克林（Kleene）在1951年到1956年間，從識別(shbi)語言的角度研究語言，給出了語言的另一種描述。克林是在研究神經(jīng)細胞中，建立了自動機，他用這種自動機

6、來識別語言：對于按照一定的規(guī)則構(gòu)造的任一個自動機，該自動機就定義了一個語言，這個語言由該自動機所能識別的所有句子組成。共七十七頁2022/7/1813形式語言與自動機理論的產(chǎn)生(chnshng)與作用1959年，Chomsky通過深入研究，將他本人的研究成果與克林的研究成果結(jié)合了起來(q li)，不僅確定了文法和自動機分別從生成和識別的角度去表達語言，而且證明了文法與自動機的等價性。 共七十七頁2022/7/1814形式語言與自動機理論(lln)的產(chǎn)生與作用20世紀(jì)50年代，人們用巴科斯范式（Backus Nour Form 或 Backus Normal Form，簡記為BNF）成功地對高級

7、語言ALGOL-60進行了描述。實際上，巴科斯范式就是上下文無關(guān)文法（Context Free Grammar）的一種(y zhn)表示形式。這一成功，使得形式語言在20世紀(jì)60年代得到了大力的發(fā)展。 共七十七頁2022/7/1815形式語言與自動機理論的產(chǎn)生(chnshng)與作用形式語言與自動機理論除了在計算(j sun)機科學(xué)領(lǐng)域中的直接應(yīng)用外，更在計算(j sun)學(xué)科人才的計算思維的培養(yǎng)中占有極其重要的地位 計算思維能力的培養(yǎng)，主要是由基礎(chǔ)理論系列課程實現(xiàn)的，該系列主要由從數(shù)學(xué)分析開始到形式語言結(jié)束的一些數(shù)學(xué)和抽象程度比較高的內(nèi)容的課程組成。它們構(gòu)成的是一個梯級訓(xùn)練系統(tǒng)。在此系統(tǒng)中，

8、連續(xù)數(shù)學(xué)、離散數(shù)學(xué)、計算模型等三部分內(nèi)容要按階段分開，三個階段對應(yīng)與本學(xué)科的學(xué)生在大學(xué)學(xué)習(xí)期間的思維方式和能力的變化與提高過程的三個步驟。共七十七頁2022/7/18162.2 基本(jbn)定義定義2.1 字母表（Alphabet）是一個非空有窮集合，字母表中的元素稱為(chn wi)該字母表的一個字母（Letter），也叫字符（Character）例 以下是不同的字母表： a，b，c，d a，b，c，z 0，1 (4) ASCII字母表共七十七頁2022/7/18172.2 基本(jbn)定義定義2.2 設(shè)1、2是兩個(lin )字母表，1與2 的乘積(Product)定義為12=ab|a

9、1，b2 例:1=0,1, 2=a,b, 12 =0a,0b,1a,1b定義2.3 設(shè)是一個字母表，的n次冪(Power)遞歸地定義為： 0= n=n-1 n1例： 13 =000,001,010,011,100,101,110,111共七十七頁2022/7/18182.2 基本(jbn)定義定義(dngy)2.4 設(shè)是一個字母表，的正閉包(Positive Closure)定義為：+=234的克林閉包(Kleene Closure)為：*=0+ =023 共七十七頁2022/7/18192.2 基本(jbn)定義 例0,1+ = 0，1，00，01，11，000，001，010，011，10

10、0， a，b，c，d+ = a，b，c，d，aa，ab，ac，ad，ba，bb，bc，bd，aaa，aab，aac，aad，aba，abb，abc 共七十七頁2022/7/18202.2 基本(jbn)定義例0,1* = ，0，1，00，01，11，000，001，010，011，100， a，b，c，d* = ，a，b，c，d，aa，ab，ac，ad，ba，bb，bc，bd，aaa，aab，aac，aad，aba，abb，abc， 共七十七頁2022/7/18212.2 基本(jbn)定義定義2.5 設(shè)是一個字母表，x *，x稱為字母表上的一個句子（sentence），叫做上的一個空句子。定

11、義2.6 設(shè)是一個字母表，對任意的x，y*，a，句子xay中的a叫做a在該句子中的一個出現(xiàn)(occurrence)。定義2.7 設(shè)是一個字母表，x*，句子x中字符(z f)出現(xiàn)的總個數(shù)叫做該字符(z f)串的長度(length)，記作|x|。 共七十七頁2022/7/18222.2 基本(jbn)定義定義2.8 設(shè)是一個字母表，x，y*，x，y的并置(concatenation)是這樣一個串，該串是由串x直接連接串y所組成的。記作xy。并置(bn zh)又叫做連結(jié)。對于n0，串x的n次冪(power)定義為： x0=； xn=xn-1x。共七十七頁2022/7/18232.2 基本(jbn)定

12、義定義2.9 設(shè)是一個字母表，對x，y，z*，如果x=yz，則稱y是x的前綴(prefix)，如果z，則稱y是x的真前綴(proper prefix)；z是x的后綴(suffix)，如果y，則稱z是x的真后綴(proper suffix)。字母表=a，b上的句子(j zi)abaabb的前綴、后綴、真前綴和真后綴如下：前綴：，a，ab，aba，abaa，abaab，abaabb真前綴：，a，ab，aba，abaa，abaab后綴：，b，bb，abb，aabb，baabb，abaabb真后綴：，b，bb，abb，aabb，baabb 共七十七頁2022/7/18242.2 基本(jbn)定義定義

13、2.10 設(shè)是一個字母表，對x，y，z，w，v*，如果x=yz，w=yv，則稱y是x和w的公共(gnggng)前綴(common prefix)。如果x和w的任何公共前綴都是y的前綴，則稱y是x和w的最大公共前綴(maximal common prefix)。如果x=zy，w=vy，則稱y是x和w的公共后綴(common suffix )。如果x和w的任何公共后綴都是y的后綴，則稱y是x和w的最大公共后綴(maximal common suffix )。 共七十七頁2022/7/18252.2 基本(jbn)定義定義(dngy)2.11設(shè)是一個字母表，對w，x，y，z*，如果w=xyz，則稱y

14、是w的子串(substring)。 定義2.12 設(shè)是一個字母表，對t，u，v，w，x，y，z*，如果t=uyv，w=xyz，則稱y是t和w的公共子串(common substring)。如果y1，y2，yn是t和w的公共子串，且|yj|=max|y1|，|y2|，|yn|，則稱yj是t和w的最大公共子串(maximal common substring)。 共七十七頁2022/7/18262.2 基本(jbn)定義定義2.13 設(shè)是一個(y )字母表，L *，L稱為字母表上的一個語言（Language），xL，x叫做L的一個句子。例：字母表0，1上的語言0，100，110，1，00，110，

15、1，00，11，01，1000，11*01，10*共七十七頁2022/7/18272.2 基本(jbn)定義2.14 設(shè)1，2是字母表，L11*，L22*，語言L1與L2的乘積(chngj)(product)是字母表12上的一個語言，該語言定義為： L1L2=xy|xL1，yL2共七十七頁2022/7/18282.2 基本(jbn)定義定義(dngy)2.15 設(shè)是一個字母表，L*，L的n次冪(power)是一個語言，該語言定義為： 當(dāng)n=0是，Ln=； 當(dāng)n1時，Ln= Ln-1L。L的正閉包(positive closure)L+是一個語言，該語言定義為：L+=LL2L3L4L的克林閉包(

16、Kleene closure)L*是一個語言，該語言定義為：L*= L0LL2L3L4 共七十七頁2022/7/18292.3 文法(wnf)的定義如何實現(xiàn)語言(yyn)結(jié)構(gòu)的形式化描述？考慮賦值語句的形式：左部量 = 右部表達式a = a+ab = m3+bm1 = a+m2共七十七頁2022/7/1830= ab cm1m2m3 + -問題：如何(rh)用符號來描述？即如何(rh)形式化？句子的組成規(guī)則共七十七頁2022/7/1831非終結(jié)(zhngji)符號集V = ，終結(jié)符號集T = a , b, c, m1, m2, m3, +, -語法規(guī)則集P = = ， 開始符號S = 賦值語句

17、定義句子的規(guī)則的語法(yf)組成終結(jié)符號集，非終結(jié)符號集，語法規(guī)則，開始符號共七十七頁2022/7/1832文法(wnf)G的形式定義定義2.16 文法G為一個四元組: = (，T，)：非終結(jié)符(Terminal)集語法變量（成分）代表某個語言的各種子結(jié)構(gòu)T：終結(jié)符(Variable)集語言的句子中出現(xiàn)的字符，T = ：開始符號(Start Symbol)，S代表文法所定義的語言，至少(zhsho)在產(chǎn)生式左側(cè)出現(xiàn)一次共七十七頁2022/7/1833文法G的形式(xngsh)定義：產(chǎn)生式(Product)集合，被稱為產(chǎn)生式（定義式），讀作：定義為。其中(qzhng)(T)+，且中至少有中元素的

18、一個出現(xiàn)。(T)*。稱為產(chǎn)生式的左部(Left Part)，稱為產(chǎn)生式的右部(Right Part)。產(chǎn)生式定義各個語法成分的結(jié)構(gòu)（組成規(guī)則） 共七十七頁2022/7/1834例2.9 賦值語句(yj)的文法V=， ，T=a，b，c，m1，m2，m3，+，-P=， , , a, b, c, m1, m2， m3, , , ， ， +， -S= 共七十七頁2022/7/1835例2.9 賦值語句(yj)的文法（續(xù)）符號化之后(zhhu)：G=(A，B，E，C，D，P，a，b，c，m1，m2，m3，+，-，P，A)，其中，P=AB=E，BC，BD，Ca，Cb，C c，Dm1，Dm2，Dm3，ECO

19、C，ECOD，EDOC，EDOD，O +，O - 共七十七頁2022/7/1836產(chǎn)生(chnshng)式的簡寫 對一組有相同左部的產(chǎn)生式1，2，n可以簡單地記為：1|2|n讀作：定義為或者1，或者2，或者n。并且稱它們(t men)為產(chǎn)生式。1，2，n稱為候選式(Candidate)。 對一個文法，只列出該文法的所有產(chǎn)生式，且所列的第一個產(chǎn)生式的左部是該文法的開始符號。 問題：有了定義句子的規(guī)則，如何判定某一句子是否屬于某語言？共七十七頁句子(j zi)的派生(推導(dǎo))-從產(chǎn)生語言的角度賦值語句(yj) 左部量 = 右部表達式 簡單變量 = 右部表達式 a = 右部表達式 a = 簡單變量 a

20、 = a a = a + a = a + a37共七十七頁句子(j zi)的歸約 -從識別語言的角度a = a + a a = a + a = a a = 簡單變量 a = 右部表達式 簡單變量 = 右部表達式 左部量 = 右部表達式 賦值語句 派生與識別均根據(jù)(gnj)規(guī)則38共七十七頁2022/7/1839基于產(chǎn)生式的變換(binhun)-推導(dǎo)或歸約定義2.17 設(shè)G=(V，T，P，S)是一個文法，如果P，(VT)*，則稱在G中直接推導(dǎo)出，記作： 讀作：在文法G中直接推導(dǎo)出。在不特別強調(diào)推導(dǎo)的直接性時，“直接推導(dǎo)”可以(ky)簡稱為推導(dǎo)(derivation)，有時我們也稱推導(dǎo)為派生。與之

21、相對應(yīng)，也可以稱在文法G中直接歸約成。在不特別強調(diào)歸約的直接性時，“直接歸約”可以簡稱為歸約(reduction)。由于這里實際是將中的變成了，而和都沒有變化，所以又稱將歸約成。 共七十七頁2022/7/1840(多步)推導(dǎo)(tudo)012 n記為 0 n (恰用n步) 0 n （至少一步(y b)） 0 n （若干步:零步或多步）共七十七頁2022/7/1841文法G產(chǎn)生(chnshng)的語言設(shè)G=(V，T，P，S)是一個文法，對于AV，令L(A)=x | A x & xT* 不難看出，L(A)就是語法變量A所代表的集合。定義2.19 設(shè)有文法G=(V，T，P，S)，則稱 L(G)=w

22、| S w & wT* 為文法G產(chǎn)生的語言(language)。wL(G)，w稱為G產(chǎn)生的一個句子(sentence)。 顯然，對于任意(rny)一個文法G，G產(chǎn)生的語言L(G)就是該文法的開始符號S所對應(yīng)的集合L(S)。 共七十七頁2022/7/1842文法(wnf)G產(chǎn)生的語言(續(xù))()x* x and xT*文法可以派生出多少個句子？文法的作用語言的有窮描述以有限的規(guī)則描述無限的語言現(xiàn)象有限：產(chǎn)生(chnshng)式集合、終結(jié)符集合、非終結(jié)符集合無限：可以導(dǎo)出無窮多個句子（L也可是有窮）共七十七頁2022/7/1843推導(dǎo)(tudo)/歸約舉例A B=E 有產(chǎn)生(chnshng)式AB=

23、E，所以可以將A換成B=E C=E 有產(chǎn)生式BC，所以可以將B=E中的B換成C a=E 有產(chǎn)生式Ca，所以可以將C=E中的C換成a a=COD 有產(chǎn)生式ECOD，所以可以將a=E中的E換成COD a=bOD 有產(chǎn)生式Cb，所以可以將a=COD中的C換成b a=b+D 有產(chǎn)生式O+，所以可以將a=bOD的O換成+ a=b+m1 有產(chǎn)生式Dm1，所以可以將a=b+D的D換成m1 AB=EBC| DCa | b | cDm1 | m2| m3ECOC | COD | DOC | DODO + | - 共七十七頁句型(j xn)與句子定義2.20 設(shè)文法G=(V，T，P，S)，對于(VT)*，如果S

24、，則稱是G產(chǎn)生的一個句型(sentential form)，簡稱(jinchng)為句型 對于任意文法G=(V，T，P，S)，G產(chǎn)生的句子和句型的區(qū)別在于句子滿足wT*，而句型滿足(VT)*44共七十七頁句型(j xn)與句子句子w是從S開始，在G中可以推導(dǎo)出來(ch li)的終結(jié)符號行，它不含語法變量；句型是從S開始，在G中可以推導(dǎo)出來的符號行，它可能含有語法變量；句子一定是句型；但句型不一定是句子 45共七十七頁2022/7/18462. 文法的分類(fn li)(Chomsky體系)根據(jù)語言結(jié)構(gòu)的復(fù)雜程度（形式語言）涉及(shj)文法的復(fù)雜程度、分析方法的選擇反映文法描述語言的能力如果G

25、滿足文法定義的要求，則是型文法（短語結(jié)構(gòu)文法PSG: Phrase Structure Grammar ）。L(G)為PSL。 共七十七頁2022/7/18471. 上下文有關(guān)(yugun)文法(CSG)如果對于P，均有|成立(chngl)(除外)，則稱為型文法即：上下文有關(guān)文法（CSGContext Sensitive Grammar） L(G)為1型/上下文有關(guān)/敏感語言(CSL)共七十七頁2022/7/18482.上下文無關(guān)(wgun)文法(CFG)如果對于P，均有|，并且V成立，則稱G為型文法即：上下文無關(guān)文法(CFG: Context Free Grammar)L(G)為2型/上下文

26、無關(guān)語言（CFL）CFG能描述(mio sh)程序設(shè)計語言的多數(shù)語法成分共七十七頁2022/7/1849例 標(biāo)識符的文法(wnf)SL|LTTL|N|TL|TN La|b|c|dN0|1|2|3|4|5Sa|b|c|dSaT|bT|cT|dTTa|b|c|d|0|1|2|3|4|5TaT|bT|cT|dT|0TN1T|2T|3T|4T|5T共七十七頁2022/7/18503. 正規(guī)(zhnggu)文法(RG)設(shè)A、BV，aT或為右線性(Right Linear)文法：AaB或Aa左線性(Left Linear)文法：ABa或Aa 都是型文法(正規(guī)文法 Regular Grammar -RG)L

27、(G)為3型/正規(guī)集/正則集/正則語言（RL）能描述程序設(shè)計(chn x sh j)語言的多數(shù)單詞左、右線性文法不可混用共七十七頁2022/7/1851例 非CFL的文法(wnf)L=anbncn|n0的文法(wnf)SaBC|aSBCCBBCaBabbBbbbCbccCcc“可以證明”不存在CFG G ,使L(G)=L共七十七頁非上下文無關(guān)(wgun)的語言結(jié)構(gòu)程序設(shè)計語言的有些語言結(jié)構(gòu)不能用上下文無關(guān)文法描述 例2.9 L1=wcw|wa,b+ aabcaab就是L1的一個(y )句子 這個語言是檢查程序中標(biāo)識符的聲明應(yīng)先于引用的抽象52共七十七頁非上下文無關(guān)(wgun)的語言結(jié)構(gòu)例2.1

28、0 L2=anbmcndm|n,m0它是檢查過程聲明(shngmng)的形參個數(shù)和過程引用的參數(shù)個數(shù)是否一致問題的抽象53共七十七頁2022/7/1854Chomsky體系(tx)總結(jié)G = (V，T，P，S)是一個文法(wnf), P*G是0型文法，L(G)是0型語言； -其能力相當(dāng)于圖靈機*|:G是1型文法，L(G)是1型語言(除); -其識別系統(tǒng)是線性界限自動機* : G是2型文法，L(G)是2型語言; -其識別系統(tǒng)是不確定的下推自動機*AaB或Aa: G是右線性文法，L(G)是3型語言ABa或Aa : G是左線性文法，L(G)是3型語言 -其識別系統(tǒng)是有窮自動機共七十七頁2022/7/

29、1855文法(wnf)的類型四種(s zhn)文法之間的關(guān)系是將產(chǎn)生式作進一步限制而定義的。四種文法之間的逐級“包含”關(guān)系如下：2型文法1型文法0型文法3型文法共七十七頁2022/7/1856范式(fn sh)Backus-Naur FormBackus-Normal Form表示為非終結(jié)符用“”括起來(q li)終結(jié)符：基本符號集其他(1|2|n)1|2|n | 共七十七頁2022/7/1857范式(fn sh)Backus-Naur FormBackus-Normal Form例 簡單算術(shù)(sunsh)表達式(只寫產(chǎn)生式)+ * ()id即：+|*|()|id哪些是終結(jié)符？哪些是變量？共七

30、十七頁2022/7/18582.5 CFG的語法(yf)樹Parse Tree用樹的形式表示句型的生成樹根： 開始符號中間結(jié)點： 非終結(jié)符葉結(jié)點： 終結(jié)符或者非終結(jié)符每個推導(dǎo)對應(yīng)一個(y )中間結(jié)點及其兒子一個二級子樹-直接短語又稱為分析樹(parse tree)、推導(dǎo)樹(derivation tree)、派生樹(derivation tree) 共七十七頁2022/7/1859例 句子(j zi)結(jié)構(gòu)的表示 (文法EE+E|E*E|(E)|id ）EE+EEE+EidEidEE*EE*EidEididEidEE+Eid+Eid+E*Eid+id*Eid+id*id一棵樹！共七十七頁2022/

31、7/1860短語(duny)(Phrase)定義2.27 設(shè)有CFG G=(V，T，P，S)，(VT)*，S A，A ，則稱是句型的相對于變量A的短語(phrase)；如果(rgu)此時有A，則稱是句型的相對于變量A的直接短語(immediate phrase)在無意義沖突時，簡稱為句型的直接短語。直接短語也叫做簡單短語(simple phrase)。定義2.28 設(shè)有CFG G=(V，T，P，S)，G的句型的最左直接短語叫做句柄(handle)。 共七十七頁2022/7/1861 例：(直接(zhji)短語EE+T T+TF+T(E)+T(E+T)+T(E+T)+T(T+T)+T(F+T)+

32、T(id+T)+T(a+T*F)+T(a+F*F)+T(a+b*F)+T(a+b*c)+T(a+b*c)+F(a+b*c)+dEE+T|T TT*F|F F(E)|id共七十七頁2022/7/1862句柄(Handle)：最左直接(zhji)短語TT* F|F EE+T|T F( E )| idEE+T T+TF+T(E)+T(E+T)+T(E+T)+T(T+T)+T(F+T)+T(id+T)+T(a+T*F)+T(a+F*F)+T(a+b*F)+T(a+b*c)+T(a+b*c)+F(a+b*c)+d共七十七頁2022/7/1863用子樹解釋短語(duny)，直接短語(duny)，句柄短語：

33、一棵子樹的所有葉子自左至右排列(pili)起來形成一個相對于子樹根的短語。直接短語：僅有父子兩代的一棵子樹，它的所有葉子自左至右排列起來所形成的符號串。句柄：一個句型的分析樹中最左那棵只有父子兩代的子樹的所有葉子的自左至右排列。例如，對表達式文法GE和句子a1+a2*a3，挑選出推導(dǎo)過程中產(chǎn)生的句型中的短語，直接短語，句柄共七十七頁2022/7/1864EE+TT+TF+T a1+T a1+T*F a1+F * F a1+a2 *FE+T T,T+T F,F+T a1, a1+T a1, T*F, a1+T*Fa1, F,F*F, a1+F*F a1, a2,a1+ a2 *F, a2 *F

34、a1, a2, a3, a2 * a3 a1+ a2 *a3EE+TTFa1T*FFa2a3a1+a2 *a3短語(duny) 共七十七頁2022/7/1865例 短語(duny)與分析樹 (文法EE+E|E*E|(E)|id ）EE+EidEE*idid一棵子樹的葉子(y zi)！共七十七頁2022/7/1866id+id*id的不同(b tn)推導(dǎo)EE+E|E*E|(E)|idE E+E id+E id+E*E id+id*E id+id*idE E+E E+E*E E+E*id E+id*id id+id*idE E*E E+E*E E+id*E id+id*E id+id*id不做限制

35、(xinzh)句型 (sentential Form)（歸約）E * id+id*id施于最右變量右句型/規(guī)范句型 (canonical ) (最左/規(guī)范歸約)E + id+id*id施于最左變量左句型(left-) （最右歸約） E5 id+id*id共七十七頁2022/7/1867最左推導(dǎo)(tudo)與最右推導(dǎo)(tudo)最左推導(dǎo)(Left-most Derivation)每次推導(dǎo)都施加在句型的最左邊的語法變量上。與最右歸約對應(yīng)最右推導(dǎo)(Right-most Derivation)每次推導(dǎo)都施加在句型的最右邊(yu bian)的語法變量上。與最左歸約（規(guī)范規(guī)約）對應(yīng)的規(guī)范(Canonica

36、l)句型共七十七頁2022/7/18682.6 CFG的二義性對同一句子存在(cnzi)兩棵語法分析樹在理論上不可判定EE*EidEE+ididEE+EEEid*idid共七十七頁2022/7/1869 1. 描述一個(y )句子的文法不是唯一的； 2. 對于一個句子的分析應(yīng)是唯一的?？紤]表達式下面的文法 GE,其產(chǎn)生式如下： EE+EE*E (E) a 對于句子a+a*a, 有如下兩個最左推導(dǎo)： EE+E a+E a+E*E a+a*E a+a*a E E*E E+E*E a+E*E a+a*E a+a*a文法(wnf)的二義性共七十七頁2022/7/1870 EE+E a+E a+E*E a+a*E a+a*a E E*EE+E*E a+E*Ea+a*E a+a*aEE+EE*EaaaEE*E+EEaaa最左推導(dǎo)(tudo)共七