2023/2/21第1章小結(jié)編譯原理課程性質(zhì)程序設(shè)計(jì)語言及其發(fā)展程序設(shè)計(jì)語言的翻譯編譯程序的總體結(jié)構(gòu)編譯程序的各個(gè)階段2023/2/22第2章

高級(jí)語言及其文法2.1語言概述2.2基本定義2.3文法的定義2.4文法的分類2.5CFG的語法樹2.6CFG的二義性2.7本章小結(jié)2023/2/232.1語言概述什么是語言？語言是一定的群體用來進(jìn)行信息交流的工具。2023/2/242.1語言概述信息交流的基礎(chǔ)是什么？按照共同約定的生成規(guī)則和理解規(guī)則去生成“句子”和理解“句子”2023/2/252.1語言概述語言的特征自然語言(NaturalLanguage)是人與人的通訊工具語義(semantics):環(huán)境、背景知識(shí)、語氣、二義性——難以形式化計(jì)算機(jī)語言(ComputerLanguage)計(jì)算機(jī)系統(tǒng)間、人機(jī)間通訊工具嚴(yán)格的語法(Grammar)、語義(semantics)——易于形式化：嚴(yán)格2023/2/262.1語言概述語言的描述方法——現(xiàn)狀自然語言：自然、方便-非形式化數(shù)學(xué)語言（符號(hào)）：嚴(yán)格、準(zhǔn)確-形式化形式化描述高度的抽象、嚴(yán)格的理論基礎(chǔ)和方便的計(jì)算機(jī)表示2023/2/272.1語言概述語言——形式化的內(nèi)容提取語言(Language)：滿足一定條件的句子集合句子(Sentence)：滿足一定規(guī)則的單詞序列單詞(Token)：滿足一定規(guī)則的字符串語言是字和組合字的規(guī)則例（自然語言：第譯始二天課今開編上節(jié)）今天開始上第二節(jié)編譯課2023/2/282.1語言概述語言是字及其組合規(guī)則的統(tǒng)一體2023/2/292.1語言概述程序設(shè)計(jì)語言——形式化的內(nèi)容提取程序設(shè)計(jì)語言(ProgrammingLanguage)：組成程序的所有語句的集合。程序(Program)：滿足語法規(guī)則的語句序列。語句(Sentence)：滿足語法規(guī)則的單詞序列。單詞(Token)：滿足詞法規(guī)則的字符串。例：變量:=表達(dá)式if條件表達(dá)式then語句while條件表達(dá)式do語句call過程名(參數(shù)表)2023/2/2102.1語言概述描述形式——文法語法——語句語句的組成規(guī)則描述方法：BNF范式、語法(描述)圖詞法——單詞單詞的組成規(guī)則描述方法：BNF范式、正規(guī)式2023/2/211形式語言與自動(dòng)機(jī)理論的產(chǎn)生與作用語言學(xué)家Chomsky最初從產(chǎn)生語言的角度研究語言。1956年，通過抽象，他將語言形式地定義為是由一個(gè)字母表中的字母組成的一些串的集合。可以在字母表上按照一定的規(guī)則定義一個(gè)文法（Grammar），該文法所能產(chǎn)生的所有句子組成的集合就是該文法產(chǎn)生的語言。2023/2/212形式語言與自動(dòng)機(jī)理論的產(chǎn)生與作用克林（Kleene）在1951年到1956年間，從識(shí)別語言的角度研究語言，給出了語言的另一種描述克林是在研究神經(jīng)細(xì)胞中，建立了自動(dòng)機(jī)對(duì)于按照一定的規(guī)則構(gòu)造的任一個(gè)自動(dòng)機(jī)，該自動(dòng)機(jī)就定義了一個(gè)語言，這個(gè)語言由該自動(dòng)機(jī)所能識(shí)別的所有句子組成2023/2/213形式語言與自動(dòng)機(jī)理論的產(chǎn)生與作用1959年，Chomsky通過深入研究，將他本人的研究成果與克林的研究成果結(jié)合了起來，不僅確定了文法和自動(dòng)機(jī)分別從生成和識(shí)別的角度去表達(dá)語言，而且證明了文法與自動(dòng)機(jī)的等價(jià)性。2023/2/214形式語言與自動(dòng)機(jī)理論的產(chǎn)生與作用20世紀(jì)50年代，人們用巴科斯范式（BackusNourForm或BackusNormalForm，簡記為BNF）成功地描述ALGOL-60促進(jìn)形式語言在20世紀(jì)60年代的大發(fā)展巴科斯范式就是上下文無關(guān)文法（ContextFreeGrammar）的一種表示形式2023/2/2152.2基本定義定義2.1

字母表（Alphabet）∑是一個(gè)非空有窮集合，字母表中的元素稱為該字母表的一個(gè)字母（Letter），也叫字符（Character）例以下是不同的字母表： ⑴{a，b，c，d} ⑵{a，b，c，……，z} ⑶{0，1}(4)ASCII字母表2023/2/2162.2基本定義定義2.2設(shè)∑1、∑2是兩個(gè)字母表，∑1與∑2

的乘積(Product)定義為∑1∑2={ab|a∈∑1，b∈∑2}例:∑1={0,1},∑2={a,b},∑1∑2={0a,0b,1a,1b}定義2.3設(shè)∑是一個(gè)字母表，∑的n次冪(Power)遞歸地定義為：⑴∑0={ε}⑵∑n=∑n-1∑n≥1例：∑13={000,001,010,011,100,101,110,111}2023/2/2172.2基本定義定義2.4設(shè)∑是一個(gè)字母表，∑的正閉包(PositiveClosure)定義為：∑+=∑∪∑2∪∑3∪∑4∪……∑的克林閉包(KleeneClosure)為：∑*=∑0∪∑+=∑0∪∑∪∑2∪∑3∪……2023/2/2182.2基本定義

例{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……}2023/2/2192.2基本定義例{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，…}

2023/2/2202.2基本定義定義2.5設(shè)∑是一個(gè)字母表，x

∑*，x稱為字母表∑上的一個(gè)句子（sentence），ε叫做∑上的一個(gè)空句子。定義2.6設(shè)∑是一個(gè)字母表，對(duì)任意的x，y∈∑*，a∈∑，句子xay中的a叫做a在該句子中的一個(gè)出現(xiàn)(occurrence)。定義2.7設(shè)∑是一個(gè)字母表，x∈∑*，句子x中字符出現(xiàn)的總個(gè)數(shù)叫做該字符串的長度(length)，記作|x|。2023/2/2212.2基本定義定義2.8設(shè)∑是一個(gè)字母表，x，y∈∑*，x，y的并置(concatenation)是這樣一個(gè)串，該串是由串x直接連接串y所組成的。記作xy。并置又叫做連結(jié)。對(duì)于n≥0，串x的n次冪(power)定義為：⑴x0=ε；⑵xn=xn-1x。2023/2/2222.2基本定義定義2.9設(shè)∑是一個(gè)字母表，對(duì)x，y，z∈∑*，如果x=yz，則稱y是x的前綴(prefix)，如果z≠ε，則稱y是x的真前綴(properprefix)；z是x的后綴(suffix)，如果y≠ε，則稱z是x的真后綴(propersuffix)。字母表∑={a，b}上的句子abaabb的前綴、后綴、真前綴和真后綴如下：前綴：ε，a，ab，aba，abaa，abaab，abaabb真前綴：ε，a，ab，aba，abaa，abaab后綴：ε，b，bb，abb，aabb，baabb，abaabb真后綴：ε，b，bb，abb，aabb，baabb

2023/2/2232.2基本定義定義2.10設(shè)∑是一個(gè)字母表，對(duì)x，y，z，w，v∈∑*，如果x=yz，w=yv，則稱y是x和w的公共前綴(commonprefix)。如果x和w的任何公共前綴都是y的前綴，則稱y是x和w的最大公共前綴(maximalcommonprefix)。如果x=zy，w=vy，則稱y是x和w的公共后綴(commonsuffix)。如果x和w的任何公共后綴都是y的后綴，則稱y是x和w的最大公共后綴(maximalcommonsuffix)。2023/2/2242.2基本定義定義2.11設(shè)∑是一個(gè)字母表，對(duì)w，x，y，z∈∑*，如果w=xyz，則稱y是w的子串(substring)。定義2.12設(shè)∑是一個(gè)字母表，對(duì)t，u，v，w，x，y，z∈∑*，如果t=uyv，w=xyz，則稱y是t和w的公共子串(commonsubstring)。如果y1，y2，……，yn是t和w的公共子串，且|yj|=max{|y1|，|y2|，……，|yn|}，則稱yj是t和w的最大公共子串(maximalcommonsubstring)。2023/2/2252.2基本定義定義2.13設(shè)∑是一個(gè)字母表，L

∑*，L稱為字母表∑上的一個(gè)語言（Language），x∈L，x叫做L的一個(gè)句子。語言是指文法中一切句子的集合例：字母表{0，1}上的語言{0，1}{00，11}{0，1，00，11}{0，1，00，11，01，10}{00，11}*{01，10}*2023/2/2262.2基本定義2.14設(shè)∑1，∑2是字母表，L1∑1*，L2∑2*，語言L1與L2的乘積(product)是字母表∑1∪∑2上的一個(gè)語言，該語言定義為：L1L2={xy|x∈L1，y∈L2}2023/2/2272.2基本定義定義2.15設(shè)∑是一個(gè)字母表，L∈∑*，L的n次冪(power)是一個(gè)語言，該語言定義為：⑴當(dāng)n=0是，Ln={ε}；⑵當(dāng)n≥1時(shí)，Ln=Ln-1L。L的正閉包(positiveclosure)L+是一個(gè)語言，該語言定義為：L+=L∪L2∪L3∪L4∪……L的克林閉包(Kleeneclosure)L*是一個(gè)語言，該語言定義為：L*=L0∪L∪L2∪L3∪L4∪……2023/2/2282023/2/2292023/2/2302023/2/2312.3文法的定義如何實(shí)現(xiàn)語言結(jié)構(gòu)的形式化描述？考慮賦值語句的形式：左部量=右部表達(dá)式a=a+ab=m[3]+bm[1]=a+m[2]2023/2/232<賦值語句><左部量>=<右部表達(dá)式><左部量><簡單變量><左部量><下標(biāo)變量><簡單變量>a<簡單變量>b<簡單變量>c<下標(biāo)變量>m[1]<下標(biāo)變量>m[2]<下標(biāo)變量>m[3]<右部表達(dá)式><簡單變量><運(yùn)算符><簡單變量><右部表達(dá)式><簡單變量><運(yùn)算符><下標(biāo)變量><右部表達(dá)式><下標(biāo)變量><運(yùn)算符><簡單變量><右部表達(dá)式><下標(biāo)變量><運(yùn)算符><下標(biāo)變量><運(yùn)算符>+<運(yùn)算符>-問題：如何用符號(hào)來描述？即如何形式化？句子的組成規(guī)則2023/2/233非終結(jié)符號(hào)集V

= {<賦值語句>，<左部量>，<右部表達(dá)式>，<簡單變量>，<下標(biāo)變量>，<運(yùn)算符>}終結(jié)符號(hào)集T

= {a，b,c,m[1],m[2],m[3],+,-}語法規(guī)則集P

={<賦值語句><左部量>=<右部表達(dá)式>，……}開始符號(hào)S

=賦值語句定義句子的規(guī)則的語法組成——終結(jié)符號(hào)集，非終結(jié)符號(hào)集，語法規(guī)則，開始符號(hào)2023/2/234文法G的形式定義定義2.16文法G為一個(gè)四元組:

Ｇ=(Ｖ，T，Ｐ，Ｓ)Ｖ：非終結(jié)符(Terminal)集語法變量（成分）——代表某個(gè)語言的各種子結(jié)構(gòu)T：終結(jié)符(Variable)集語言的句子中出現(xiàn)的字符，Ｖ∩T=ΦＳ：開始符號(hào)(StartSymbol)，S∈Ｖ代表文法所定義的語言，至少在產(chǎn)生式左側(cè)出現(xiàn)一次2023/2/235文法G的形式定義Ｐ：產(chǎn)生式(Product)集合α→β，被稱為產(chǎn)生式（定義式），讀作：α定義為β。其中α∈(Ｖ∪T)+，且α中至少有Ｖ中元素的一個(gè)出現(xiàn)。β∈(Ｖ∪T)*。α稱為產(chǎn)生式α→β的左部(LeftPart)，β稱為產(chǎn)生式α→β的右部(RightPart)。產(chǎn)生式定義各個(gè)語法成分的結(jié)構(gòu)（組成規(guī)則）

2023/2/236例2.9賦值語句的文法V={<賦值語句>，<左部量>，<右部表達(dá)式>，<簡單變量>，<下標(biāo)變量>，<運(yùn)算符>}T={a，b，c，m[1]，m[2]，m[3]，+，-}P={<賦值語句><左部量>=<右部表達(dá)式>，<左部量><簡單變量>，<左部量><下標(biāo)變量>，<簡單變量>a，<簡單變量>b，<簡單變量>c，<下標(biāo)變量>m[1]，<下標(biāo)變量>m[2]，<下標(biāo)變量>m[3]，<右部表達(dá)式><簡單變量><運(yùn)算符><簡單變量>，<右部表達(dá)式><簡單變量><運(yùn)算符><下標(biāo)變量>，<右部表達(dá)式><下標(biāo)變量><運(yùn)算符><簡單變量>，<右部表達(dá)式><下標(biāo)變量><運(yùn)算符><下標(biāo)變量>，<運(yùn)算符>+，<運(yùn)算符>-}S=<賦值語句>2023/2/237例2.9賦值語句的文法（續(xù)）符號(hào)化之后：G=({A，B，E，C，D，P}，{a，b，c，m[1]，m[2]，m[3]，+，-}，P，A)，其中，P={AB=E，BC，BD，Ca，Cb，Cc，Dm[1]，Dm[2]，Dm[3]，ECOC，ECOD，EDOC，EDOD，O+，O-}2023/2/238產(chǎn)生式的簡寫

對(duì)一組有相同左部的產(chǎn)生式α→β1，α→β2…，α→βn可以簡單地記為：α→β1|β2|…|βn讀作：α定義為或者β1，或者β2，…，或者βn。并且稱它們?yōu)棣廉a(chǎn)生式。β1，β2，…，βn稱為候選式(Candidate)。對(duì)一個(gè)文法，只列出該文法的所有產(chǎn)生式，且所列的第一個(gè)產(chǎn)生式的左部是該文法的開始符號(hào)。問題：有了定義句子的規(guī)則，如何判定某一句子是否屬于某語言？2023/2/239句子的派生(推導(dǎo))-從產(chǎn)生語言的角度賦值語句

左部量=右部表達(dá)式

簡單變量

=右部表達(dá)式a=右部表達(dá)式

a=簡單變量<運(yùn)算符><簡單變量>a=a<運(yùn)算符><簡單變量>a=a+<簡單變量>

a=a+a2023/2/240句子的歸約-從識(shí)別語言的角度a=a+a

a=a+<簡單變量>

a=a<運(yùn)算符><簡單變量>

a=簡單變量<運(yùn)算符><簡單變量>

a=右部表達(dá)式

簡單變量

=右部表達(dá)式

左部量

=右部表達(dá)式

賦值語句派生與均根據(jù)規(guī)則2023/2/241基于產(chǎn)生式的變換--推導(dǎo)或歸約定義2.17設(shè)G=(V，T，P，S)是一個(gè)文法，如果αβ∈P，γ，δ∈(V∪T)*，則稱γαδ在G中直接推導(dǎo)出γβδ，記作：

γαδγβδ讀作：γαδ在文法G中直接推導(dǎo)出γβδ。在不特別強(qiáng)調(diào)推導(dǎo)的直接性時(shí)，“直接推導(dǎo)”可以簡稱為推導(dǎo)(derivation)，有時(shí)我們也稱推導(dǎo)為派生。與之相對(duì)應(yīng)，也可以稱γβδ在文法G中直接歸約成γαδ。在不特別強(qiáng)調(diào)歸約的直接性時(shí)，“直接歸約”可以簡稱為歸約(reduction)。由于這里實(shí)際是將γβδ中的β變成了α，而γ和δ都沒有變化，所以又稱將β歸約成α

2023/2/242(多步)推導(dǎo)α0α1α2…αn記為α0

αn

(恰用n步)α0αn

（至少一步）

α0

αn

（若干步:零步或多步）2023/2/243文法G產(chǎn)生的語言設(shè)G=(V，T，P，S)是一個(gè)文法，對(duì)于A∈V，令

L(A)={x|Ax&x∈T*}

不難看出，L(A)就是語法變量A所代表的集合。定義2.19設(shè)有文法G=(V，T，P，S)，則稱

L(G)={w|S

w&w∈T*}

為文法G產(chǎn)生的語言(language)。w∈L(G)，w稱為G產(chǎn)生的一個(gè)句子(sentence)。顯然，對(duì)于任意一個(gè)文法G，G產(chǎn)生的語言L(G)就是該文法的開始符號(hào)S所對(duì)應(yīng)的集合L(S)。2023/2/244文法G產(chǎn)生的語言(續(xù))

Ｌ(Ｇ)＝{x｜Ｓ*

xandx∈T*}文法Ｇ可以派生出多少個(gè)句子？文法Ｇ的作用——語言的有窮描述以有限的規(guī)則描述無限的語言現(xiàn)象有限：產(chǎn)生式集合、終結(jié)符集合、非終結(jié)符集合無限：可以導(dǎo)出無窮多個(gè)句子（L也可是有窮）2023/2/245推導(dǎo)/歸約舉例AB=E

有產(chǎn)生式AB=E，所以可以將A換成B=E

C=E

有產(chǎn)生式BC，所以可以將B=E中的B換成Ca=E

有產(chǎn)生式Ca，所以可以將C=E中的C換成aa=COD

有產(chǎn)生式ECOD，所以可以將a=E中的E換成CODa=bOD

有產(chǎn)生式Cb，所以可以將a=COD中的C換成ba=b+D

有產(chǎn)生式O+，所以可以將a=bOD的O換成+a=b+m[1]有產(chǎn)生式Dm[1]，所以可以將a=b+D的D換成m[1]

AB=EBC|DCa|b|cDm[1]|m[2]|m[3]ECOC|COD|DOC|DODO+|-

2023/2/246句型與句子定義2.20設(shè)文法G=(V，T，P，S)，對(duì)于α∈(V∪T)*，如果Sα，則稱α是G產(chǎn)生的一個(gè)句型(sententialform)，簡稱為句型

對(duì)于任意文法G=(V，T，P，S)，G產(chǎn)生的句子和句型的區(qū)別在于句子滿足w∈T*，而句型滿足α∈(V∪T)*2023/2/247句型與句子句子w是從S開始，在G中可以推導(dǎo)出來的終結(jié)符號(hào)行，它不含語法變量；句型α是從S開始，在G中可以推導(dǎo)出來的符號(hào)行，它可能含有語法變量；句子一定是句型；但句型不一定是句子2023/2/2482.４文法的分類(Chomsky體系)根據(jù)語言結(jié)構(gòu)的復(fù)雜程度（形式語言）涉及文法的復(fù)雜程度、分析方法的選擇反映文法描述語言的能力如果G滿足文法定義的要求，則Ｇ是０型文法（短語結(jié)構(gòu)文法PSG:PhraseStructureGrammar）。L(G)為PSL。2023/2/2491.上下文有關(guān)文法(CSG)如果對(duì)于αβ∈P，均有|β|≥|α|成立(Ｓ→ε除外)，則稱Ｇ為１型文法即：上下文有關(guān)文法（CSG——ContextSensitiveGrammar）L(G)為1型/上下文有關(guān)/敏感語言(CSL)2023/2/2502.上下文無關(guān)文法(CFG)如果對(duì)于αβ∈P，均有|β|≥|α|，并且α∈V成立，則稱G為２型文法即：上下文無關(guān)文法(CFG:ContextFreeGrammar)L(G)為2型/上下文無關(guān)語言（CFL）CFG能描述程序設(shè)計(jì)語言的多數(shù)語法成分2023/2/251例標(biāo)識(shí)符的文法S→L|LT T→L|N|TL|TN L→a|b|c|d N→0|1|2|3|4|5S→a|b|c|d S→aT|bT|cT|dT T→a|b|c|d|0|1|2|3|4|5 T→aT|bT|cT|dT|0T N→1T|2T|3T|4T|5T2023/2/2522023/2/2532023/2/2543.正規(guī)文法(RG)設(shè)Ａ、Ｂ∈Ｖ，ａ∈T或?yàn)橛揖€性(RightLinear)文法：Ａ→ａＢ或Ａ→ａ左線性(LeftLinear)文法：Ａ→Ｂａ或Ａ→ａ都是３型文法(正規(guī)文法RegularGrammar-RG)L(G)為3型/正規(guī)集/正則集/正則語言（RL）能描述程序設(shè)計(jì)語言的多數(shù)單詞左、右線性文法不可混用2023/2/255例非CFL的文法L={anbncn|n>0}的文法SaBC|aSBCCBBCaBabbBbbbCbccCcc“可以證明”不存在CFGG,使L(G)=L2023/2/256非上下文無關(guān)的語言結(jié)構(gòu)程序設(shè)計(jì)語言的有些語言結(jié)構(gòu)不能用上下文無關(guān)文法描述例2.9L1={wcw|w∈{a,b}+}aabcaab就是L1的一個(gè)句子這個(gè)語言是檢查程序中標(biāo)識(shí)符的聲明應(yīng)先于引用的抽象2023/2/257非上下文無關(guān)的語言結(jié)構(gòu)

例2.10L2={anbmcndm|n,m≥0}它是檢查過程聲明的形參個(gè)數(shù)和過程引用的參數(shù)個(gè)數(shù)是否一致問題的抽象2023/2/258Chomsky體系——總結(jié)Ｇ=(Ｖ，T，Ｐ，Ｓ)是一個(gè)文法,α→β∈P* G是0型文法，L(G)是0型語言；

---其能力相當(dāng)于圖靈機(jī)* |α|≤|β|:G是1型文法，L(G)是1型語言(除Ｓ→ε);

---其識(shí)別系統(tǒng)是線性界限自動(dòng)機(jī)* α∈ＶN:G是2型文法，L(G)是2型語言;

---其識(shí)別系統(tǒng)是不確定的下推自動(dòng)機(jī)* A→aB或A→a:G是右線性文法，L(G)是3型語言

A→Ba或A→ａ:G是左線性文法，L(G)是3型語言

---其識(shí)別系統(tǒng)是有窮自動(dòng)機(jī)2023/2/259文法的類型四種文法之間的關(guān)系是將產(chǎn)生式作進(jìn)一步限制而定義的。四種文法之間的逐級(jí)“包含”關(guān)系如下：2型文法1型文法0型文法3型文法2023/2/260ＢＮＦ范式——Backus-NaurForm

Backus-NormalFormα→β表示為α∷＝β非終結(jié)符用“<”和“>”括起來終結(jié)符：基本符號(hào)集其他β(α1|α2…|αn)≡βα1|βα2…|βαn[α]≡α|ε……2023/2/261ＢＮＦ范式——Backus-NaurForm

Backus-NormalForm例簡單算術(shù)表達(dá)式(只寫產(chǎn)生式)<算術(shù)表達(dá)式>∷＝<簡單表達(dá)式>+<簡單表達(dá)式><簡單表達(dá)式>∷＝<簡單表達(dá)式>*<簡單表達(dá)式><簡單表達(dá)式>∷＝(<簡單表達(dá)式>)<簡單表達(dá)式>∷＝id即：<算術(shù)表達(dá)式>∷＝<簡單表達(dá)式>+<簡單表達(dá)式>|<簡單表達(dá)式>*<簡單表達(dá)式>|(<簡單表達(dá)式>)|id哪些是終結(jié)符？哪些是變量？2023/2/2622.5CFG的語法樹ParseTree用樹的形式表示句型的生成樹根：開始符號(hào)中間結(jié)點(diǎn)：非終結(jié)符葉結(jié)點(diǎn)：終結(jié)符或者非終結(jié)符每個(gè)推導(dǎo)對(duì)應(yīng)一個(gè)中間結(jié)點(diǎn)及其兒子——一個(gè)二級(jí)子樹-直接短語又稱為分析樹(parsetree)、推導(dǎo)樹(derivationtree)、派生樹(derivationtree)

2023/2/263例句子結(jié)構(gòu)的表示

(文法E→E+E|E*E|(E)|id

）EE+EE→E+EidE→idEE*E→E*EidE→ididE→idEE+Eid+Eid+E*Eid+id*Eid+id*id一棵樹！2023/2/264短語(Phrase)定義2.27設(shè)有CFGG=(V，T，P，S)，α，γ，β∈(V∪T)*，SγAβ，Aα，則稱α是句型γαβ的相對(duì)于變量A的短語(phrase)；如果此時(shí)有Aα，則稱α是句型γαβ的相對(duì)于變量A的直接短語(immediatephrase)在無意義沖突時(shí)，簡稱為句型γαβ的直接短語。直接短語也叫做簡單短語(simplephrase)。定義2.28設(shè)有CFGG=(V，T，P，S)，G的句型的最左直接短語叫做句柄(handle)。2023/2/265

例：(直接)短語EE+TT+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)+dE→E+T|TT→T*F|FF→(E)|id2023/2/266句柄(Handle)：最左直接短語T→T*F|FE→E+T|TF→(E)|idEE+TT+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)+d2023/2/267用子樹解釋短語，直接短語，句柄短語：一棵子樹的所有葉子自左至右排列起來形成一個(gè)相對(duì)于子樹根的短語。直接短語：僅有父子兩代的一棵子樹，它的所有葉子自左至右排列起來所形成的符號(hào)串。句柄：一個(gè)句型的分析樹中最左那棵只有父子兩代的子樹的所有葉子的自左至右排列。例如，對(duì)表達(dá)式文法G[E]和句子a1+a2*a3，挑選出推導(dǎo)過程中產(chǎn)生的句型中的短語，直接短語，句柄2023/2/268EE+TT+TF+T

a1+T

a1+T*F

a1+F*F

a1+a2*FE+TT,T+TF,F+Ta1,a1+Ta1,T*F,a1+T*Fa1,F,F*F,a1+F*F

a1,a2,a1+a2*F,a2*F

a1,a2,a3,a2*

a3

a1+a2*a3EE+TTFa1T*FFa2a3a1+a2*a3短語2023/2/269例短語與分析樹

(文法E→E+E|E*E|(E)|id

）EE+EidEE*idid一棵子樹的葉子！2023/2/270id+id*id的不同推導(dǎo)E→E+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*idE+id*id

id+id*idE

E*E

E+E*E

E+id*E

id+id*E

id+id*id不做限制句型

(sententialForm)（歸約）E*

id+id*id施于最右變量右句型/規(guī)范句型 (canonical~)(最左/規(guī)范歸約)E+

id+id*id施于最左變量左句型(left-~)（最右歸約）

E5

id+id*id2023/2/271最左推導(dǎo)與最右推導(dǎo)最左推導(dǎo)(Left-mostDerivation)每次推導(dǎo)都施加在句型的最左邊的語法變量上。——與最右歸約對(duì)應(yīng)最右推導(dǎo)(Right-mostDerivation)每次推導(dǎo)都施加在句型的最右邊的語法變量上?！c最左歸約（規(guī)范規(guī)約）對(duì)應(yīng)的規(guī)范(Canonical)句型2023/2/2722.6CFG的二義性對(duì)同一句子存在兩棵語法分析樹在理論上不可判定EE*EidEE+ididE