編譯原理語言概述

編譯原理語言概述演示文稿現(xiàn)在是1頁\一共有74頁\編輯于星期二2.1語言概述什么是語言？現(xiàn)在是2頁\一共有74頁\編輯于星期二2.1語言概述語言特征自然語言(NaturalLanguage)是人與人的通訊工具語義(semantics):環(huán)境、背景知識(shí)、語氣、二義性——難以形式化計(jì)算機(jī)語言(ComputerLanguage)計(jì)算機(jī)系統(tǒng)間、人機(jī)間通訊工具嚴(yán)格的語法(Grammar)、語義(semantics)——易于形式化：嚴(yán)格現(xiàn)在是3頁\一共有74頁\編輯于星期二2.1語言概述語言的描述方法——現(xiàn)狀自然語言：自然、方便-非形式化數(shù)學(xué)語言（符號(hào)）：嚴(yán)格、準(zhǔn)確-形式化形式化描述高度的抽象，嚴(yán)格的理論基礎(chǔ)和方便的計(jì)算機(jī)表示。現(xiàn)在是4頁\一共有74頁\編輯于星期二2.1語言概述語言——形式化的內(nèi)容提取語言(Language)：滿足一定條件的句子集合句子(Sentence)：滿足一定規(guī)則的單詞序列單詞(Token)：滿足一定規(guī)則的字符(Character)串語言是字和組合字的規(guī)則例（自然語言：第譯始一天課今開編上節(jié)）今天開始上第一節(jié)編譯課現(xiàn)在是5頁\一共有74頁\編輯于星期二2.1語言概述語言是字及其組合規(guī)則的統(tǒng)一體現(xiàn)在是6頁\一共有74頁\編輯于星期二2.1語言概述程序設(shè)計(jì)語言——形式化的內(nèi)容提取程序設(shè)計(jì)語言(ProgrammingLanguage)：組成程序的所有語句的集合。程序(Program)：滿足語法規(guī)則的語句序列。語句(Sentence)：滿足語法規(guī)則的單詞序列。單詞(Token)：滿足詞法規(guī)則的字符串。例：變量:=表達(dá)式if條件then語句while條件do語句call過程名(參數(shù)表)現(xiàn)在是7頁\一共有74頁\編輯于星期二2.1語言概述描述形式——文法語法——語句語句的組成規(guī)則描述方法：BNF范式、語法(描述)圖詞法——單詞單詞的組成規(guī)則描述方法：BNF范式、正規(guī)式現(xiàn)在是8頁\一共有74頁\編輯于星期二形式語言于自動(dòng)機(jī)理論的產(chǎn)生與作用語言學(xué)家Chomsky最初從產(chǎn)生語言的角度研究語言。1956年，通過抽象，他將語言形式地定義為是由一個(gè)字母表中的字母組成的一些串的集合?？梢栽谧帜副砩习凑找欢ǖ囊?guī)則定義一個(gè)文法（Grammar），該文法所能產(chǎn)生的所有句子組成的集合就是該文法產(chǎn)生的語言?？肆郑↘leene）在1951年到1956年間，從識(shí)別語言的角度研究語言，給出了語言的另一種描述?？肆质窃谘芯可窠?jīng)細(xì)胞中，建立了自動(dòng)機(jī)，他用這種自動(dòng)機(jī)來識(shí)別語言：對(duì)于按照一定的規(guī)則構(gòu)造的任一個(gè)自動(dòng)機(jī)，該自動(dòng)機(jī)就定義了一個(gè)語言，這個(gè)語言由該自動(dòng)機(jī)所能識(shí)別的所有句子組成?，F(xiàn)在是9頁\一共有74頁\編輯于星期二形式語言于自動(dòng)機(jī)理論的產(chǎn)生與作用1959年，Chomsky通過深入研究，將他本人的研究成果與克林的研究成果結(jié)合了起來，不僅確定了文法和自動(dòng)機(jī)分別從生成和識(shí)別的角度去表達(dá)語言，而且證明了文法與自動(dòng)機(jī)的等價(jià)性。20世紀(jì)50年代，人們用巴科斯范式（BackusNourForm或BackusNormalForm，簡記為BNF）成功地對(duì)高級(jí)語言ALGOL-60進(jìn)行了描述。實(shí)際上，巴科斯范式就是上下文無關(guān)文法（ContextFreeGrammar）的一種表示形式。這一成功，使得形式語言在20世紀(jì)60年代得到了大力的發(fā)展?，F(xiàn)在是10頁\一共有74頁\編輯于星期二形式語言于自動(dòng)機(jī)理論的產(chǎn)生與作用形式語言與自動(dòng)機(jī)理論除了在計(jì)算機(jī)科學(xué)領(lǐng)域中的直接應(yīng)用外，更在計(jì)算學(xué)科人才的計(jì)算思維的培養(yǎng)中占有極其重要的地位計(jì)算思維能力的培養(yǎng)，主要是由基礎(chǔ)理論系列課程實(shí)現(xiàn)的，該系列主要由從數(shù)學(xué)分析開始到形式語言結(jié)束的一些數(shù)學(xué)和抽象程度比較高的內(nèi)容的課程組成。它們構(gòu)成的是一個(gè)梯級(jí)訓(xùn)練系統(tǒng)。在此系統(tǒng)中，連續(xù)數(shù)學(xué)、離散數(shù)學(xué)、計(jì)算模型等三部分內(nèi)容要按階段分開，三個(gè)階段對(duì)應(yīng)與本學(xué)科的學(xué)生在大學(xué)學(xué)習(xí)期間的思維方式和能力的變化與提高過程的三個(gè)步驟?，F(xiàn)在是11頁\一共有74頁\編輯于星期二計(jì)算思維能力的培養(yǎng)過程中學(xué)數(shù)學(xué) 數(shù)學(xué)分析離散數(shù)學(xué)

具體.靜止 變量.運(yùn)動(dòng) 離散.抽象 形式.模型

(基本運(yùn)算系統(tǒng)) (計(jì)算系統(tǒng))

實(shí)數(shù) 抽象集合

單一、具體的計(jì)算

一般、形式化的計(jì)算 （實(shí)例計(jì)算）

（模型化計(jì)算）

形式語言與自動(dòng)機(jī)理論運(yùn)算范圍特征高水平計(jì)算專業(yè)人才的計(jì)算思維能力的漸進(jìn)培養(yǎng)現(xiàn)在是12頁\一共有74頁\編輯于星期二2.2基本定義字母表（Alphabet）∑是一個(gè)非空有窮集合，字母表中的元素稱為該字母表的一個(gè)字母（Letter），也叫字符（Character）。例以下是不同的字母表： ⑴{a，b，c，d} ⑵{a，b，c，……，z} ⑶{0，1}

(4)ASCII字母表現(xiàn)在是13頁\一共有74頁\編輯于星期二2.2基本定義符號(hào)串的定義(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)所組成的任何有窮序列被稱之為該字母表上的符號(hào)串,也稱作"字"?，F(xiàn)在是14頁\一共有74頁\編輯于星期二2.2基本定義設(shè)s是符號(hào)串，則s的前綴：移走s的尾部的零個(gè)或多于零個(gè)符號(hào)后綴：刪去s的頭部的零個(gè)或多于零個(gè)符號(hào)子串:從s中刪去一個(gè)前綴和一個(gè)后綴子序列:從s中刪去零或多于零個(gè)符號(hào)(這些符號(hào)不要求連續(xù)）逆轉(zhuǎn)（用SR表示）：將S中的符號(hào)按相反次序?qū)懗龆玫降姆?hào)串長度：是該符號(hào)串中的符號(hào)的數(shù)目。例如|aab|=3,|ε|=0?，F(xiàn)在是15頁\一共有74頁\編輯于星期二2.2基本定義符號(hào)串的連接和方冪1.連接：設(shè)x和y是符號(hào)串，它們的連接xy是把y的符號(hào)寫在x的符號(hào)之后得到的符號(hào)串。例如，x=ba,y=nana,xy=banana.2.方冪：x0=;x1=x;x2=xx;……；xn=xn-1x;例如,設(shè)x=ba,則x1=ba,x2=baba,x3=bababa,……現(xiàn)在是16頁\一共有74頁\編輯于星期二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}現(xiàn)在是17頁\一共有74頁\編輯于星期二2.2基本定義定義3設(shè)∑是一個(gè)字母表，∑的正閉包(PositiveClosure)定義為：∑+=∑∪∑2∪∑3∪∑4∪……∑的克林閉包(KleeneClosure)為：∑*=∑0∪∑+=∑0∪∑∪∑2∪∑3∪……

現(xiàn)在是18頁\一共有74頁\編輯于星期二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……}現(xiàn)在是19頁\一共有74頁\編輯于星期二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，…}

現(xiàn)在是20頁\一共有74頁\編輯于星期二2.2基本定義定義5設(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}*現(xiàn)在是21頁\一共有74頁\編輯于星期二2.3文法的定義如何實(shí)現(xiàn)語言結(jié)構(gòu)的形式化描述？現(xiàn)在是22頁\一共有74頁\編輯于星期二考慮一個(gè)句子——文法要素的提取分析：Thegreywolfwilleatthegoat〈謂語〉〈主語〉〈形容詞〉〈名詞〉〈動(dòng)詞〉〈直接賓語〉助動(dòng)詞〈句子〉動(dòng)原冠詞名詞Thegreywolfwilleatthegoat〈冠詞〉現(xiàn)在是23頁\一共有74頁\編輯于星期二句子主語謂語（1）主語冠詞形容詞名詞（2）冠詞the形容詞grey謂語

動(dòng)詞直接賓語（5）

動(dòng)詞助動(dòng)詞動(dòng)詞原形（6）助動(dòng)詞will動(dòng)詞原形eat直接賓語

冠詞名詞（9）名詞wolf名詞goat句子的組成規(guī)則問題：如何用符號(hào)來描述？即如何形式化？現(xiàn)在是24頁\一共有74頁\編輯于星期二終結(jié)符號(hào)集VT= {the，grey,wolf,will,eat,goat}非終結(jié)符號(hào)集VN= {句子，主語，謂語，冠詞，形容詞，名詞，

動(dòng)詞，直接賓語，助動(dòng)詞，動(dòng)詞原形}語法規(guī)則集P={句子

主語謂語，……}開始符號(hào)S=句子定義句子的規(guī)則的語法組成

__終結(jié)符號(hào)集，非終結(jié)符號(hào)集，語法規(guī)則，開始符號(hào)問題：有了定義句子的規(guī)則，如何判定某一句子是否屬于某語言？現(xiàn)在是25頁\一共有74頁\編輯于星期二句子主語謂語冠詞形容詞名詞謂語the形容詞名詞謂語thegrey名詞謂語thegreywolf謂語thegreywolf

動(dòng)詞直接賓語

…...thegreywolfwilleatthegoat句子的派生（推導(dǎo)）-從產(chǎn)生語言的角度

句子的歸約-從識(shí)別語言的角度-均根據(jù)規(guī)則現(xiàn)在是26頁\一共有74頁\編輯于星期二句子thegreywolfwilleatthegoat

thegreywolfwilleatthewolf

thegreygoat

willeatthewolfthegreygoat

willeatthegreywolf符合語法且符合語義的句子僅是：

thegreywolfwilleatthegoat句子的語義要求現(xiàn)在是27頁\一共有74頁\編輯于星期二文法G的形式定義文法G為一個(gè)四元組: Ｇ=(ＶT，ＶN，Ｐ，Ｓ)ＶT：終結(jié)符(Terminal)集ＶN：非終結(jié)符(Variable)集，ＶT∩ＶN=Φ語法成分——代表某個(gè)語言的各種子結(jié)構(gòu)Ｓ：開始符號(hào)(StartSymbol)，S∈ＶN代表文法所定義的語言，至少在產(chǎn)生式左側(cè)出現(xiàn)一次現(xiàn)在是28頁\一共有74頁\編輯于星期二文法G的形式定義Ｐ：產(chǎn)生式(Product)集合α→β，被稱為產(chǎn)生式（定義式），讀作：α定義為β。其中α∈(ＶT∪ＶN)+，且α中至少有ＶN中元素的一個(gè)出現(xiàn)。β∈(ＶT∪ＶN)*。α稱為產(chǎn)生式α→β的左部(LeftPart)，β稱為產(chǎn)生式α→β的右部(RightPart)。產(chǎn)生式定義各個(gè)語法成分的結(jié)構(gòu)（組成規(guī)則）現(xiàn)在是29頁\一共有74頁\編輯于星期二例2-1算術(shù)表達(dá)式的文法遞歸定義——中綴表示標(biāo)識(shí)符(id)（常數(shù)、變量）是表達(dá)式(E)；表達(dá)式加一個(gè)表達(dá)式是表達(dá)式；表達(dá)式減一個(gè)表達(dá)式是表達(dá)式；表達(dá)式乘一個(gè)表達(dá)式是表達(dá)式；表達(dá)式除一個(gè)表達(dá)式是表達(dá)式；表達(dá)式加上括號(hào)后是表達(dá)式；現(xiàn)在是30頁\一共有74頁\編輯于星期二例2-1算術(shù)表達(dá)式的文法考慮簡單算術(shù)表達(dá)式組成的語言G=({id，+，*，(，)}，{E}，P，E)P:E→E+EE→E*EE→(E)E→id約定：只寫產(chǎn)生式簡寫E→E+E|E*E|(E)|id（2.1）現(xiàn)在是31頁\一共有74頁\編輯于星期二產(chǎn)生式的簡寫對(duì)一組有相同左部的產(chǎn)生式α→β1，α→β2…，α→βn可以簡單地記為：α→β1|β2|…|βn讀作：α定義為或者β1，或者β2，…，或者βn。并且稱它們?yōu)棣廉a(chǎn)生式。β1，β2，…，βn稱為候選式(Candidate)?，F(xiàn)在是32頁\一共有74頁\編輯于星期二基于產(chǎn)生式的變換--推導(dǎo)或歸約E→E+E|E*E|(E)|idE由第一個(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也就是說，根據(jù)第4個(gè)候選式，E*E+E經(jīng)3步變換變成id*id+id現(xiàn)在是33頁\一共有74頁\編輯于星期二直接推導(dǎo)與歸約根據(jù)產(chǎn)生式對(duì)符號(hào)串進(jìn)行變換的過程Ａ→γ是文法Ｇ的一個(gè)產(chǎn)生式，且α、β∈（ＶT∪ＶN）*，稱αＡβ直接推導(dǎo)/派生(Derive)出αγβ，也稱αγβ直接歸約(Reduce)為αＡβ。記為αＡβαγβ例：id+Eid+E*E現(xiàn)在是34頁\一共有74頁\編輯于星期二（多步）推導(dǎo)α0α1α2…αn記為α0n

αn

(恰用n步)

α0+

αn

（至少一步）

α0*

αn

（若干步:零步或多步）現(xiàn)在是35頁\一共有74頁\編輯于星期二推導(dǎo)/歸約舉例EE+E （1）串中含有變量

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

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

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

id+id*id （4）串中沒有變量到此串中已經(jīng)沒有（語法）變量了，不能再推導(dǎo)了1、E→E+E2、E→E*E3、E→(E)4、E→id現(xiàn)在是36頁\一共有74頁\編輯于星期二句型與句子E5id+id*id句子:如果S*x，且x∈ＶT*，則稱x是G產(chǎn)生的一個(gè)句子(Sentence)EE+EE+E*EE4id+id*E句型:如果S*α，α∈(ＶT∪ＶN)*則稱α是G產(chǎn)生的一個(gè)句型(SententialForm)現(xiàn)在是37頁\一共有74頁\編輯于星期二文法G產(chǎn)生的語言 Ｌ(Ｇ)＝{x｜Ｓ*

xandx∈ＶT*}文法E→E+E|E*E|(E)|id可以派生出多少個(gè)句子？文法G的作用——語言的有窮描述以有限的規(guī)則描述無限的語言現(xiàn)象有限：產(chǎn)生式集合、終結(jié)符集合、非終結(jié)符集合無限：可以導(dǎo)出無窮多個(gè)句子（L也可是有窮）現(xiàn)在是38頁\一共有74頁\編輯于星期二id+id*id的不同推導(dǎo)E→E+E|E*E|(E)|idEE+Eid+E

id+E*Eid+id*E

id+id*idEE+E

E+E*E

E+E*idE+id*id

id+id*idEE*EE+E*EE+id*Eid+id*Eid+id*id不做限制句型(sententialForm)（歸約）E*

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

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

id+id*id現(xiàn)在是39頁\一共有74頁\編輯于星期二最左推導(dǎo)與最右推導(dǎo)最左推導(dǎo)(Left-mostDerivation)每次推導(dǎo)都施加在句型的最左邊的語法變量上?！c最右歸約對(duì)應(yīng)最右推導(dǎo)(Right-mostDerivation)每次推導(dǎo)都施加在句型的最右邊的語法變量上。——與最左歸約（規(guī)范規(guī)約）對(duì)應(yīng)的規(guī)范(Canonical)句型現(xiàn)在是40頁\一共有74頁\編輯于星期二短語(Phrase)什么叫短語？如果Ｓ*

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

αＡβandAγ，則稱γ是句型αγβ的相對(duì)于變量A的直接短語最左直接短語叫做句柄(Handle)現(xiàn)在是41頁\一共有74頁\編輯于星期二例：(直接)短語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)|id現(xiàn)在是42頁\一共有74頁\編輯于星期二句柄(Handle)：最左直接短語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(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現(xiàn)在是43頁\一共有74頁\編輯于星期二例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ù)的文法？現(xiàn)在是44頁\一共有74頁\編輯于星期二2.４文法的分類(Chomsky體系)根據(jù)語言結(jié)構(gòu)的復(fù)雜程度（形式語言）涉及文法的復(fù)雜程度、分析方法的選擇反映文法描述語言的能力如果G滿足文法定義的要求，則Ｇ是０型文法（短語結(jié)構(gòu)文法PSG:PhraseStructureGrammar）。L(G)為PSL?，F(xiàn)在是45頁\一共有74頁\編輯于星期二上下文有關(guān)文法(CSG)若產(chǎn)生式集合中所有｜α｜≤｜β｜，除Ｓ→ε外，則Ｇ是１型文法即：上下文有關(guān)文法（CSG——ContextSensitiveGrammar）L(G)為1型/上下文有關(guān)/敏感語言(CSL)現(xiàn)在是46頁\一共有74頁\編輯于星期二上下文無關(guān)文法(CFG)若α∈ＶN，β∈(ＶN∪ＶT)*，則Ｇ是２型文法即：上下文無關(guān)文法(CFG:ContextFreeGrammar)L(G)為2型/上下文無關(guān)語言（CFL）CFG能描述程序設(shè)計(jì)語言的多數(shù)語法成分現(xiàn)在是47頁\一共有74頁\編輯于星期二例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 N→1T|2T|3T|4T|5T現(xiàn)在是48頁\一共有74頁\編輯于星期二正規(guī)文法(RG)設(shè)Ａ、Ｂ∈ＶN，ａ∈ＶT或?yàn)橛揖€性(RightLinear)文法：Ａ→ａＢ或Ａ→ａ左線性(LeftLinear)文法：Ａ→Ｂａ或Ａ→ａ都是３型文法(正規(guī)文法RegularGrammar-RG)L(G)為3型/正規(guī)集/正則集/正則語言（RL）能描述程序設(shè)計(jì)語言的多數(shù)單詞左、右線性文法不可混用現(xiàn)在是49頁\一共有74頁\編輯于星期二例非CFL的文法L={anbncn|n>0}的文法SaBC|aSBCCBBCaBabbBbbbCbc“可以證明”不存在CFGG,使L(G)=L現(xiàn)在是50頁\一共有74頁\編輯于星期二

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

例2.10L2={anbmcndm|n,m≥0}，它是檢查過程聲明的形參個(gè)數(shù)和過程引用的參數(shù)個(gè)數(shù)是否一致問題的抽象。非上下文無關(guān)的語言結(jié)構(gòu)現(xiàn)在是51頁\一共有74頁\編輯于星期二Chomsky體系——總結(jié)Ｇ=(ＶT，ＶN，Ｐ，Ｓ)是一個(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ī)現(xiàn)在是52頁\一共有74頁\編輯于星期二文法的類型四種文法之間的關(guān)系是將產(chǎn)生式作進(jìn)一步限制而定義的。四種文法之間的逐級(jí)“包含”關(guān)系如下：2型文法1型文法0型文法3型文法現(xiàn)在是53頁\一共有74頁\編輯于星期二ＢＮＦ范式——Backus-NaurForm

Backus-NormalFormα→β表示為α∷＝β非終結(jié)符用“<”和“>”括起來終結(jié)符：基本符號(hào)集其他β(α1|α2…|αn)≡βα1|βα2…|βαn[α]≡α|ε……現(xiàn)在是54頁\一共有74頁\編輯于星期二ＢＮＦ范式——BackusNormalForm例簡單算術(shù)表達(dá)式(只寫產(chǎn)生式)<算術(shù)表達(dá)式>∷＝<簡單表達(dá)式>+<簡單表達(dá)式><簡單表達(dá)式>∷＝<簡單表達(dá)式>*<簡單表達(dá)式><簡單表達(dá)式>∷＝(<簡單表達(dá)式>)<簡單表達(dá)式>∷＝id即：<算術(shù)表達(dá)式>∷＝<簡單表達(dá)式>+<簡單表達(dá)式>|<簡單表達(dá)式>*<簡單表達(dá)式>|(<簡單表達(dá)式>)|id哪些是終結(jié)符？哪些是變量？現(xiàn)在是55頁\一共有74頁\編輯于星期二例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一棵樹！現(xiàn)在是56頁\一共有74頁\編輯于星期二2.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í)子樹-直接短語又稱為語法分析樹現(xiàn)在是57頁\一共有74頁\編輯于星期二短語：一棵子樹的所有葉子自左至右排列起來形成一個(gè)相對(duì)于子樹根的短語。直接短語：僅有父子兩代的一棵子樹，它的所有葉子自左至右排列起來所形成的符號(hào)串。句柄：一個(gè)句型的分析樹中最左那棵只有父子兩代的子樹的所有葉子的自左至右排列。例如，對(duì)表達(dá)式文法G[E]和句子a1+a2*a3，挑選出推導(dǎo)過程中產(chǎn)生的句型中的短語，直接短語，句柄。用子樹解釋短語，直接短語，句柄現(xiàn)在是58頁\一共有74頁\編輯于星期二EE+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短語現(xiàn)在是59頁\一共有74頁\編輯于星期二例短語與分析樹

(文法E→E+E|E*E|(E)|id）EE+EidEE*idid一棵子樹的葉子！現(xiàn)在是60頁\一共有74頁\編輯于星期二二義性文法與先天二義性語言對(duì)同一句子存在兩棵語法分析樹在理論上不可判定EE*EidEE+ididEE+EEEid*idid現(xiàn)在是61頁\一共有74頁\編輯于星期二1.描述一個(gè)句子的文法不是唯一的；2.對(duì)于一個(gè)句子的分析應(yīng)是唯一的?？紤]表達(dá)式下面的文法G[E],其產(chǎn)生式如下：

EE+EE*E(E)a

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

EE+Ea+Ea+E*Ea+a*Ea+a*a

EE*EE+E*Ea+E*Ea+a*Ea+a*a文法的二義性現(xiàn)在是62頁\一共有74頁\編輯于星期二

EE+Ea+Ea+E*Ea+a*Ea+a*a

EE*EE+E*Ea+E*Ea+a*Ea+a*aEE+EE*EaaaEE*E+EEaaa最左推導(dǎo)現(xiàn)在是63頁\一共有74頁\編輯于星期二

EE+EE+E*EE+E*aE+a*aa+a*a

EE*EE*aE+E*aE+a*aa+a*aEE+EE*EaaaEE*E+EEaaa最右推導(dǎo)現(xiàn)在是64頁\一共有74頁\編輯于星期二如果一個(gè)文法的句子存在兩棵分析樹,那么,該句子是二義性的。如果一個(gè)文法包含二義性的句子,則稱這個(gè)文法是二義性的;否則，該文法是無二義性的。幾點(diǎn)說明：1.一般來說，程序語言存在無二義性文法，對(duì)于表達(dá)式來說，文法（2.1）是二義性的。對(duì)于條件語句，經(jīng)常使用二義性文法描述它：SifexprthenSifexprthenSelseSother二義性的句子:ife1thenife2thens1elses2

二義性（歧義性，ambiquity)的定義現(xiàn)在是65頁\一共有74頁\編輯于星期二

下面是

Smatched_sunmatched_smatched_sifexprthenmatched_s