高級(jí)語(yǔ)言及其文法編譯原理三

高級(jí)語(yǔ)言及其文法編譯原理三第一頁(yè)，共七十三頁(yè)，編輯于2023年，星期二2.1語(yǔ)言概述2.2基本定義2.3文法(Grammar)的定義2.4CFG的語(yǔ)法(分析)樹(shù)(ParseTree)2.5文法的分類(lèi)2.6文法的構(gòu)造本章主要內(nèi)容第二頁(yè)，共七十三頁(yè)，編輯于2023年，星期二2.1語(yǔ)言概述什么是語(yǔ)言自然語(yǔ)言(NaturalLanguage)是人與人的通訊工具語(yǔ)義(Semantics):環(huán)境、背景知識(shí)、語(yǔ)氣、二義性——難以形式化計(jì)算機(jī)語(yǔ)言(ComputerLanguage)計(jì)算機(jī)系統(tǒng)間、人機(jī)間通訊工具嚴(yán)格的語(yǔ)法(Grammar)、語(yǔ)義(Semantics)——易于形式化：嚴(yán)格語(yǔ)言是用來(lái)交換信息的工具——功能性描述第三頁(yè)，共七十三頁(yè)，編輯于2023年，星期二2.1語(yǔ)言概述語(yǔ)言的描述方法——現(xiàn)狀自然語(yǔ)言：自然、方便-非形式化數(shù)學(xué)語(yǔ)言（符號(hào)）：嚴(yán)格、準(zhǔn)確-形式化形式化描述高度的抽象，嚴(yán)格的理論基礎(chǔ)和方便的計(jì)算機(jī)表示。第四頁(yè)，共七十三頁(yè)，編輯于2023年，星期二2.1語(yǔ)言概述語(yǔ)言——形式化的內(nèi)容提取單詞(Token)：滿(mǎn)足一定規(guī)則字符(Character)串句子(Sentence)：滿(mǎn)足一定規(guī)則單詞序列語(yǔ)言(Language)：滿(mǎn)足一定條件的句子集合語(yǔ)言是字和組合字的規(guī)則——結(jié)構(gòu)性描述例：一譯開(kāi)天第課今始編節(jié)上今天開(kāi)始上第一節(jié)編譯課第五頁(yè)，共七十三頁(yè)，編輯于2023年，星期二2.1語(yǔ)言概述程序設(shè)計(jì)語(yǔ)言——形式化的內(nèi)容提取程序設(shè)計(jì)語(yǔ)言(ProgrammingLanguage)：組成程序的所有語(yǔ)句的集合程序(Program)：滿(mǎn)足語(yǔ)法規(guī)則的語(yǔ)句序列語(yǔ)句(Sentence)：滿(mǎn)足語(yǔ)法規(guī)則的單詞序列單詞(Token)：滿(mǎn)足詞法規(guī)則的字符串例變量=表達(dá)式if條件then語(yǔ)句while條件do語(yǔ)句call過(guò)程名(參數(shù)表)第六頁(yè)，共七十三頁(yè)，編輯于2023年，星期二2.1語(yǔ)言概述描述形式——文法語(yǔ)法——語(yǔ)句語(yǔ)句的組成規(guī)則描述方法：BNF范式、語(yǔ)法(描述)圖詞法——單詞單詞的組成規(guī)則描述方法：BNF范式、正規(guī)式第七頁(yè)，共七十三頁(yè)，編輯于2023年，星期二2.2基本定義字母表（Alphabet）是一個(gè)非空有窮集合，字母表中的元素稱(chēng)為該字母表的一個(gè)字母（Letter），也叫字符（Character）。例以下是不同的字母表： ⑴{a，b，c，d} ⑵{a，b，c，……，z} ⑶{0，1}第八頁(yè)，共七十三頁(yè)，編輯于2023年，星期二2.2基本定義字母表上符號(hào)串(String)的定義

(1)ε是∑上的一個(gè)符號(hào)串，叫做空串。(2)若x是∑上的符號(hào)串，而a是∑的元素,

則xa是∑上的符號(hào)串。(3)y是∑上的符號(hào)串,當(dāng)且僅當(dāng)它由(1)和(2)導(dǎo)出。由字母表中的符號(hào)所組成的的任何有窮序列被稱(chēng)之為該字母表上的符號(hào)串,也稱(chēng)作“字”(Word)。第九頁(yè)，共七十三頁(yè)，編輯于2023年，星期二2.2基本定義定義1設(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設(shè)∑是一個(gè)字母表，∑的n次冪(Power)遞歸地定義為：⑴∑0={ε}⑵∑n=∑n-1∑ n≥1例：∑13={000,001,010,011,100,101,110,111}第十頁(yè)，共七十三頁(yè)，編輯于2023年，星期二2.2基本定義定義3設(shè)∑是一個(gè)字母表，∑的正閉包(PositiveClosure)：∑+=∑∪∑2∪∑3∪∑4∪……∑的克林閉包(KleeneClosure)：∑*=∑0∪∑+=∑0∪∑∪∑2∪∑3∪……第十一頁(yè)，共七十三頁(yè)，編輯于2023年，星期二2.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……}第十二頁(yè)，共七十三頁(yè)，編輯于2023年，星期二2.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，…}第十三頁(yè)，共七十三頁(yè)，編輯于2023年，星期二2.2基本定義定義5設(shè)∑是一個(gè)字母表，L∑*，L稱(chēng)為字母表∑上的一個(gè)語(yǔ)言（Language），x∈L，x叫做L的一個(gè)句子。例：字母表{0，1}上的語(yǔ)言{0，1}{00，11}{0，1，00，11}{0，1，00，11，01，10}{00，11}*{01，10}*第十四頁(yè)，共七十三頁(yè)，編輯于2023年，星期二2.2基本定義設(shè)s是符號(hào)串：01290273前綴：移走s的尾部的零個(gè)或多于零個(gè)符號(hào)后綴：刪去s的頭部的零個(gè)或多于零個(gè)符號(hào)子串:從s中刪去一個(gè)前綴和一個(gè)后綴子序列:從s中刪去零個(gè)或多于零個(gè)符號(hào)(這些符號(hào)不要求是連續(xù)的）長(zhǎng)度：是該符號(hào)串中的符號(hào)的數(shù)目。例如|aab|=3,|ε|=0。第十五頁(yè)，共七十三頁(yè)，編輯于2023年，星期二2.2基本定義符號(hào)串的連接和冪1.連接：設(shè)x和y是符號(hào)串，它們的連接xy是把y的符號(hào)寫(xiě)在x的符號(hào)之后得到的符號(hào)串。例如，x=ba,y=nana,xy=banana.2.冪：x0=;x1=x;x2=xx;……;xn=xn-1x;

例如,x=ba,x1=ba,x2=baba,x3=bababa,…...第十六頁(yè)，共七十三頁(yè)，編輯于2023年，星期二2.3文法的定義如何實(shí)現(xiàn)語(yǔ)言結(jié)構(gòu)的形式化描述？第十七頁(yè)，共七十三頁(yè)，編輯于2023年，星期二考慮一個(gè)句子——文法要素的提取分析：Thegraywolfwilleatthegoat〈謂語(yǔ)〉〈主語(yǔ)〉〈形容詞〉〈名詞〉〈動(dòng)詞〉〈直接賓語(yǔ)〉助動(dòng)詞〈句子〉動(dòng)原冠詞名詞Thegraywolfwilleatthegoat〈冠詞〉第十八頁(yè)，共七十三頁(yè)，編輯于2023年，星期二句子

→

主語(yǔ)

謂語(yǔ)主語(yǔ)

→

冠詞

形容詞

名詞謂語(yǔ)

→

動(dòng)詞

直接賓語(yǔ)動(dòng)詞

→

助動(dòng)詞

動(dòng)詞原形直接賓語(yǔ)

→

冠詞

名詞產(chǎn)生句子的規(guī)則——從產(chǎn)生語(yǔ)言的角度冠詞

→

the形容詞

→

gray助動(dòng)詞

→

will動(dòng)詞原形

→

eat名詞

→

wolf名詞

→

goat第十九頁(yè)，共七十三頁(yè)，編輯于2023年，星期二終結(jié)符號(hào)集VT={the，gray,wolf,will,eat,goat}非終結(jié)符號(hào)集VN={句子，主語(yǔ)，謂語(yǔ)，冠詞，形容詞，名詞，動(dòng)詞，直接賓語(yǔ)，助動(dòng)詞，動(dòng)詞原形

}語(yǔ)法規(guī)則集P={句子→主語(yǔ)謂語(yǔ)，……}開(kāi)始符號(hào)S=句子句子的語(yǔ)法組成

——終結(jié)符號(hào)集，非終結(jié)符號(hào)集，語(yǔ)法規(guī)則，開(kāi)始符號(hào)第二十頁(yè)，共七十三頁(yè)，編輯于2023年，星期二文法G的形式定義文法G為一個(gè)四元組:

Ｇ=(ＶT，ＶN，Ｐ，Ｓ)ＶT：終結(jié)符(Terminal)集ＶN：非終結(jié)符(Variable)集，ＶT∩ＶN=Φ語(yǔ)法范疇——某個(gè)語(yǔ)言結(jié)構(gòu)Ｓ：開(kāi)始符號(hào)(StartSymbol)，S∈ＶN至少在產(chǎn)生式左側(cè)出現(xiàn)一次第二十一頁(yè)，共七十三頁(yè)，編輯于2023年，星期二文法G的形式定義Ｐ：產(chǎn)生式(Product)集合α→β，被稱(chēng)為產(chǎn)生式（定義式），讀作：α定義為β。其中α∈(ＶT∪ＶN)+，且α中至少有ＶN中元素的一個(gè)出現(xiàn)。β∈(ＶT∪ＶN)*。α稱(chēng)為產(chǎn)生式α→β的左部(LeftPart)，β稱(chēng)為產(chǎn)生式α→β的右部(RightPart)。

第二十二頁(yè)，共七十三頁(yè)，編輯于2023年，星期二句子主語(yǔ)

謂語(yǔ)

冠詞

形容詞

名詞

謂語(yǔ)

the形容詞

名詞

謂語(yǔ)

thegray名詞

謂語(yǔ)

thegraywolf謂語(yǔ)

thegraywolf

動(dòng)詞

直接賓語(yǔ)

thegraywolf助動(dòng)詞

動(dòng)詞原形

直接賓語(yǔ)

thegraywolfwill動(dòng)詞原形

直接賓語(yǔ)

thegraywolfwilleat直接賓語(yǔ)

thegraywolfwilleat

冠詞

名詞

thegraywolfwilleatthe名詞

thegraywolfwilleatthegoat句子的派生（推導(dǎo)）___根據(jù)規(guī)則第二十三頁(yè)，共七十三頁(yè)，編輯于2023年，星期二句子

thegraywolfwilleatthegoatthegraywolfwilleatthewolfthegraygoatwilleatthewolfthegraygoatwilleatthegray符合語(yǔ)法且符合語(yǔ)義的句子僅是：

thegraywolfwilleatthegoat還可以“得出”其他的句子第二十四頁(yè)，共七十三頁(yè)，編輯于2023年，星期二例2-1算術(shù)表達(dá)式的文法考慮簡(jiǎn)單算術(shù)表達(dá)式組成的語(yǔ)言遞歸定義——中綴表示標(biāo)識(shí)符(id)（常數(shù)、變量）是表達(dá)式；表達(dá)式加一個(gè)表達(dá)式是表達(dá)式；表達(dá)式減一個(gè)表達(dá)式是表達(dá)式；表達(dá)式乘一個(gè)表達(dá)式是表達(dá)式；表達(dá)式除一個(gè)表達(dá)式是表達(dá)式；表達(dá)式加上括號(hào)后是表達(dá)式。第二十五頁(yè)，共七十三頁(yè)，編輯于2023年，星期二上次課主要內(nèi)容編譯程序?qū)崿F(xiàn)技術(shù)自展自動(dòng)生成：lex、Yacc語(yǔ)言信息交流的工具字和組合字的規(guī)則的統(tǒng)一體字母表上的語(yǔ)言字母表∑+

、∑*、a∈∑，x∈∑*、L∑*、x∈L前綴、后綴、子串、串長(zhǎng)、串的連接、串的冪第二十六頁(yè)，共七十三頁(yè)，編輯于2023年，星期二上次課主要內(nèi)容文法通過(guò)刻畫(huà)語(yǔ)言的結(jié)構(gòu)描述語(yǔ)言用有窮描述無(wú)窮Ｇ=(ＶT，ＶN，Ｐ，Ｓ)表達(dá)式的遞歸定義第二十七頁(yè)，共七十三頁(yè)，編輯于2023年，星期二例2-1算術(shù)表達(dá)式的文法考慮用式子表示這個(gè)定義標(biāo)識(shí)符(id)是表達(dá)式表達(dá)式加一個(gè)表達(dá)式是表達(dá)式E→idE→E+E表達(dá)式減一個(gè)表達(dá)式是表達(dá)式E→E-E表達(dá)式乘一個(gè)表達(dá)式是表達(dá)式E→E*E表達(dá)式除一個(gè)表達(dá)式是表達(dá)式E→E/E表達(dá)式加上括號(hào)后是表達(dá)式E→(E)第二十八頁(yè)，共七十三頁(yè)，編輯于2023年，星期二例2-1算術(shù)表達(dá)式的文法P:E→E+EE→E-EE→E*EE→E/EE→(E)E→idG=（{id，+，-，*，/，(，)}，{E}，P，E）約定：只寫(xiě)產(chǎn)生式簡(jiǎn)寫(xiě)E→E+E|E*E|(E)|id第二十九頁(yè)，共七十三頁(yè)，編輯于2023年，星期二產(chǎn)生式的簡(jiǎn)寫(xiě)對(duì)一組有相同左部的產(chǎn)生式α→β1，α→β2…，α→βn可以簡(jiǎn)單地記為：α→β1|β2|…|βn讀作：α定義為或者β1，或者β2，…，或者βn。并且稱(chēng)它們?yōu)棣廉a(chǎn)生式。β1，β2，…，βn稱(chēng)為候選式(Candidate)。第三十頁(yè)，共七十三頁(yè)，編輯于2023年，星期二產(chǎn)生式規(guī)定的一些變換E由第一個(gè)候選式可以變成E+EE+E中的第一個(gè)E由第二個(gè)候選式可以變成E*E，從而E+E變成E*E+E根據(jù)第4個(gè)候選式，E*E+E中的E都可以變成id:E*E+E變成id*E+Eid*E+E變成id*E+idid*E+id變成id*id+id也就是說(shuō)，根據(jù)第4個(gè)候選式，E*E+E經(jīng)3步變換變成id*id+id1E→E+E2E→E*E3E→(E)4E→id5E→E-E6E→E/E第三十一頁(yè)，共七十三頁(yè)，編輯于2023年，星期二文法使用舉例EE+E （1）

id+E （4）

id+E*E （2）

id+id*E （4）

id+id*id （4）E5id+id*id1E→E+E2E→E*E3E→(E)4E→id5E→E-E6E→E/E第三十二頁(yè)，共七十三頁(yè)，編輯于2023年，星期二直接推導(dǎo)與歸約根據(jù)產(chǎn)生式對(duì)符號(hào)串進(jìn)行變換的過(guò)程Ａ→γ是文法Ｇ的一個(gè)產(chǎn)生式，且α、β∈（ＶT∪ＶN）*，稱(chēng)αＡβ的直接推導(dǎo)/派生(Derive)出αγβ，也稱(chēng)αγβ直接歸約(Reduce)為αＡβ。記為αＡβαγβ例：id+Eid+E*E第三十三頁(yè)，共七十三頁(yè)，編輯于2023年，星期二（多步）推導(dǎo)α0α1α2…αn記為α0nαn

(恰用n步)α0+αn

（至少一步）

α0*αn

（若干步:零步或多步）第三十四頁(yè)，共七十三頁(yè)，編輯于2023年，星期二推導(dǎo)/歸約舉例EE+E （1）串中含有變量

id+E （4）串中含有變量

id+E*E （2）串中含有變量

id+id*E （4）串中含有變量

id+id*id （4）串中沒(méi)有變量到此串中已經(jīng)沒(méi)有（語(yǔ)法）變量了，不能再推了——得到句子1E→E+E2E→E*E3E→(E)4E→id第三十五頁(yè)，共七十三頁(yè)，編輯于2023年，星期二句型與句子E5id+id*id定義:如果S*x，且x∈ＶT*，則稱(chēng)x是G產(chǎn)生的一個(gè)句子(Sentence)EE+EE+E*EE4id+id*E定義:如果S*α，α∈(ＶT∪ＶN)*則稱(chēng)α是G產(chǎn)生的一個(gè)句型(SententialForm)第三十六頁(yè)，共七十三頁(yè)，編輯于2023年，星期二文法G產(chǎn)生的語(yǔ)言定義： L(G)={x|S*xandx∈VT*}文法E→E+E|E*E|(E)|id可以派生出多少個(gè)句子？文法G的作用——語(yǔ)言的有窮描述以有限的規(guī)則描述無(wú)限的語(yǔ)言現(xiàn)象有限:產(chǎn)生式集合、終結(jié)符集合、非終結(jié)符集合無(wú)限：可以導(dǎo)出無(wú)窮多個(gè)句子（注：L也可是有窮）第三十七頁(yè)，共七十三頁(yè)，編輯于2023年，星期二id+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*id

E+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*id第三十八頁(yè)，共七十三頁(yè)，編輯于2023年，星期二最左推導(dǎo)與最右推導(dǎo)最左推導(dǎo)(Left-mostDerivation)每次推導(dǎo)都施加在句型的最左邊的語(yǔ)法變量上?！c最右歸約對(duì)應(yīng)最右推導(dǎo)(Right-mostDerivation)每次推導(dǎo)都施加在句型的最右邊的語(yǔ)法變量上?！c最左歸約（規(guī)范規(guī)約）對(duì)應(yīng)的規(guī)范(Canonical)句型第三十九頁(yè)，共七十三頁(yè)，編輯于2023年，星期二短語(yǔ)(Phrase)自然語(yǔ)言中什么叫短語(yǔ)？如果Ｓ*

αＡβ&A+γ，則稱(chēng)γ是句型αγβ的相對(duì)于變量A的短語(yǔ)如果Ｓ*

αＡβ&Aγ，則稱(chēng)γ是句型αγβ的相對(duì)于變量A的直接短語(yǔ)最左直接短語(yǔ)叫做句柄(Handle)第四十頁(yè)，共七十三頁(yè)，編輯于2023年，星期二例：(直接)短語(yǔ)EE+TT+TF+T(E)+T(E+T)+T(E+T)+T(T+T)+T(F+T)+T(a+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)|id第四十一頁(yè)，共七十三頁(yè)，編輯于2023年，星期二句柄(Handle)：最左直接短語(yǔ)E→E+T|TT→T*F|FF→(E)|idEE+TT+TF+T(E)+T(E+T)+T(E+T)+T(T+T)+T(F+T)+T(a+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第四十二頁(yè)，共七十三頁(yè)，編輯于2023年，星期二例2-2標(biāo)識(shí)符的文法1S→L|LT T→L|N|TL|TN L→a|b|c|d letter N→0|1|2|3|4|5 digit?正整數(shù)的文法；正實(shí)數(shù)的文法第四十三頁(yè)，共七十三頁(yè)，編輯于2023年，星期二2.４文法的分類(lèi)(Chomsky體系)語(yǔ)言結(jié)構(gòu)的復(fù)雜程度（形式語(yǔ)言）涉及文法的復(fù)雜程度、分析方法的選擇如果G滿(mǎn)足文法定義的要求，則Ｇ是０型文法（短語(yǔ)結(jié)構(gòu)文法PSG:PhraseStructureGrammar）。L(G)為PSL。第四十四頁(yè)，共七十三頁(yè)，編輯于2023年，星期二上下文有關(guān)文法(CSG)若產(chǎn)生式集合中所有｜α｜≤｜β｜，除Ｓ→ε外，則Ｇ是１型文法即：上下文有關(guān)文法（CSG——ContextSensitiveGrammar）L(G)為1型/上下文有關(guān)/敏感語(yǔ)言(CSL)第四十五頁(yè)，共七十三頁(yè)，編輯于2023年，星期二上下文無(wú)關(guān)文法(CFG)若α∈ＶN，β∈(ＶN∪ＶT)*，則Ｇ是２型文法即：上下文無(wú)關(guān)文法(CFG:ContextFreeGrammar)L(G)為2型/上下文無(wú)關(guān)語(yǔ)言（CFL）例：程序設(shè)計(jì)語(yǔ)言的多數(shù)語(yǔ)法特征第四十六頁(yè)，共七十三頁(yè)，編輯于2023年，星期二例2-3標(biāo)識(shí)符的文法2S→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 T→1T|2T|3T|4T|5T第四十七頁(yè)，共七十三頁(yè)，編輯于2023年，星期二正規(guī)文法(RG)設(shè)Ａ、Ｂ∈ＶN，ａ∈ＶT或?yàn)橛揖€(xiàn)性(RightLinear)文法：Ａ→ａＢ或Ａ→ａ左線(xiàn)性(LeftLinear)文法：Ａ→Ｂａ或Ａ→ａ都是３型文法(正規(guī)文法RegularGrammar-RG)L(G)為3型/正規(guī)集/正則集/正則語(yǔ)言（RL）例：程序設(shè)計(jì)語(yǔ)言的多數(shù)詞法特性左、右線(xiàn)性文法不可混用第四十八頁(yè)，共七十三頁(yè)，編輯于2023年，星期二例非CFL的文法L={anbncn|n>0}的文法SaBC|aSBCCBBCaBabbBbbbCbc“可以證明”不存在CFGG,使L(G)=L第四十九頁(yè)，共七十三頁(yè)，編輯于2023年，星期二

在我們使用的程序語(yǔ)言中,有些語(yǔ)言結(jié)構(gòu)并不是總能用上下文無(wú)關(guān)文法描述的。例L1={wcw|w∈{a,b}+}。例,aabcaab就是L1的一個(gè)句子。這個(gè)語(yǔ)言是檢查程序中標(biāo)識(shí)符的聲明應(yīng)先于引用的抽象。

例L2={anbmcndm|n,m≥0}，它是檢查過(guò)程聲明的形參個(gè)數(shù)和過(guò)程引用的參數(shù)個(gè)數(shù)是否一致問(wèn)題的抽象。非CFL結(jié)構(gòu)第五十頁(yè)，共七十三頁(yè)，編輯于2023年，星期二Chomsky體系——總結(jié)Ｇ=(ＶT，ＶN，Ｐ，Ｓ)是一個(gè)文法,α→β∈P* G是0型文法，L(G)是0型語(yǔ)言；

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

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

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

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

---其識(shí)別系統(tǒng)是有窮自動(dòng)機(jī)(FA)第五十一頁(yè)，共七十三頁(yè)，編輯于2023年，星期二四種文法之間的關(guān)系是將產(chǎn)生式作進(jìn)一步限制而定義的。四種文法之間的逐級(jí)“包含”關(guān)系如下：2型文法1型文法0型文法3型文法Chomsky體系——總結(jié)第五十二頁(yè)，共七十三頁(yè)，編輯于2023年，星期二ＢＮＦ范式——Backus-NaurForm

Backus-NormalFormα→β表示為α∷＝β非終結(jié)符用“<”和“>”括起來(lái)終結(jié)符：基本符號(hào)集其他β(α1|α2…|αn)≡βα1|βα2…|βαn{α1|α2…|αn}nm

[α]≡α|ε……第五十三頁(yè)，共七十三頁(yè)，編輯于2023年，星期二ＢＮＦ范式——BackusNormalForm例簡(jiǎn)單算術(shù)表達(dá)式(只寫(xiě)產(chǎn)生式)<簡(jiǎn)單表達(dá)式>∷＝<簡(jiǎn)單表達(dá)式>+<簡(jiǎn)單表達(dá)式><簡(jiǎn)單表達(dá)式>∷＝<簡(jiǎn)單表達(dá)式>*<簡(jiǎn)單表達(dá)式><簡(jiǎn)單表達(dá)式>∷＝(<簡(jiǎn)單表達(dá)式>)<簡(jiǎn)單表達(dá)式>∷＝id即：<簡(jiǎn)單表達(dá)式>∷＝<簡(jiǎn)單表達(dá)式>+<簡(jiǎn)單表達(dá)式>| <簡(jiǎn)單表達(dá)式>*<簡(jiǎn)單表達(dá)式>|(<簡(jiǎn)單表達(dá)式>)|id哪些是終結(jié)符？哪些是變量？第五十四頁(yè)，共七十三頁(yè)，編輯于2023年，星期二例2-5句子結(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一棵樹(shù)！第五十五頁(yè)，共七十三頁(yè)，編輯于2023年，星期二上次課主要內(nèi)容產(chǎn)生式的簡(jiǎn)寫(xiě)：

α→β1|β2|…|βn（候選式）文法的簡(jiǎn)寫(xiě)：只寫(xiě)產(chǎn)生式集、開(kāi)始符約定直接派生/歸約：αＡβαγβＡ→γN步派生/歸約：αＡβNαγβＡNγ句子與句型：S*x S*α語(yǔ)言：L(G)={x|S*xandx∈VT*}第五十六頁(yè)，共七十三頁(yè)，編輯于2023年，星期二上次課主要內(nèi)容短語(yǔ)：短語(yǔ)、直接短語(yǔ)、句柄Chomsky體系BNF范式最左推導(dǎo)（最右歸約）最右推導(dǎo)（最左歸約）規(guī)范推導(dǎo)/歸約，規(guī)范句型例:(a1+a2)*a3E→E+T|E-T|TT→T*F|T/F|FF→(E)|id第五十七頁(yè)，共七十三頁(yè)，編輯于2023年，星期二2.5CFG的語(yǔ)法樹(shù)ParseTree用樹(shù)的形式表示句型的結(jié)構(gòu)樹(shù)根：開(kāi)始符號(hào)中間結(jié)點(diǎn)：非終結(jié)符葉結(jié)點(diǎn)：終結(jié)符或者非終結(jié)符每個(gè)推導(dǎo)對(duì)應(yīng)一個(gè)中間結(jié)點(diǎn)及其兒子——一個(gè)二級(jí)子樹(shù)-直接短語(yǔ)又稱(chēng)為語(yǔ)法分析樹(shù)第五十八頁(yè)，共七十三頁(yè)，編輯于2023年，星期二例短語(yǔ)與語(yǔ)法(分析)樹(shù)

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

）EE+Eid(a1)EE*id(a2)id(a3)短語(yǔ)——一棵子樹(shù)的葉子！第五十九頁(yè)，共七十三頁(yè)，編輯于2023年，星期二短語(yǔ)：一棵子樹(shù)的所有葉子自左至右排列起來(lái)形成一個(gè)相對(duì)于子樹(shù)根的短語(yǔ)。直接短語(yǔ)：僅有父子兩代的一棵子樹(shù)，它的所有葉子自左至右排列起來(lái)所形成的符號(hào)串。句柄：一個(gè)句型的分析樹(shù)中最左那棵只有父子兩代的子樹(shù)的所有葉子的自左至右排列。例如，對(duì)表達(dá)式文法G[E]和句子a1+a2*a3，挑選出推導(dǎo)過(guò)程中產(chǎn)生的句型中的短語(yǔ)，直接短語(yǔ)，句柄。用子樹(shù)解釋短語(yǔ)，直接短語(yǔ)，句柄第六十頁(yè)，共七十三頁(yè)，編輯于2023年，星期二EE+TT+TF+T

a1+T

a1+T*F

a1+F*F

a1+a2*FE+T

T,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短語(yǔ)第六十一頁(yè)，共七十三頁(yè)，編輯于2023年，星期二二義性文法與先天二義性語(yǔ)言對(duì)同一句子存在兩棵語(yǔ)法分析樹(shù)在理論上不可判定EE*EidEE+ididEE+EEEid*idid第六十二頁(yè)，共七十三頁(yè)，編輯于2023年，星期二

1.描述一個(gè)句子的文法不是唯一的；

2.對(duì)于一個(gè)句子的分析應(yīng)是唯一的。考慮表達(dá)式下面的文法G[E],其產(chǎn)生式如下：

EE+EE*E(E)id

對(duì)于句子a1+a2*a3,有如下兩個(gè)最左推導(dǎo)：

EE+Ea1+Ea1+E*Ea1+a2*Ea1+a2*a3EE*EE+E*Ea1+E*Ea1+a2*Ea1+a2*a3文法的二義性第六十三頁(yè)，共七十三頁(yè)，編輯于2023年，星期二

EE+Ea1+Ea1+E*Ea1+a2*Ea1+a2*a3

EE*EE+E*Ea1+E*Ea1+a2*Ea1+a2*a3EE+Ea1E*Ea2a3EE*E+EEa1a2a3最左推導(dǎo)第六十四頁(yè)，共七十三頁(yè)，編輯于2023年，星期二

EE*EE*a3

E+E*a3E+a2*a3

a1+a2*a3EE+Ea1E*Ea2a3EE*E+EEa1a2a3最右推導(dǎo)

EE+Ea1+Ea1+E*Ea1+a2*Ea1+a2*a3第六十五頁(yè)，共七十三頁(yè)，編輯于2023年，星期二如果一個(gè)文法的句子存在兩棵分析樹(shù),那么,該句子是二義性的。如果一個(gè)文法包含二義性的句子,則稱(chēng)這個(gè)文法是二義性的;否則，該文法是無(wú)二義性的。幾點(diǎn)說(shuō)明：1.一般來(lái)說(shuō)，程序語(yǔ)言存在無(wú)