編譯原理匯總第1頁(yè)/共431頁(yè)寫(xiě)在課程之前木桶原理：一個(gè)木桶由許多塊木板組成，如果組成木桶的這些木板長(zhǎng)短不一，那么這個(gè)木桶的最大容量不取決于長(zhǎng)的木板，而取決于最短的那塊木板。蝴蝶效應(yīng)：1963年12月，洛倫茲（Lorenz）在華盛頓的美國(guó)科學(xué)促進(jìn)會(huì)的一次講演中提出：一只蝴蝶在巴西扇動(dòng)翅膀，有可能會(huì)在美國(guó)的德克薩斯引起一場(chǎng)龍卷風(fēng)。他的演講和結(jié)論給人們留下了極其深刻的印象。馬太效應(yīng)：“馬太福音”第二十五章由這么幾句話：“凡有的，還要加給他叫他多余；沒(méi)有的，連他所有的也要奪過(guò)來(lái)?！?。1968年，美國(guó)科學(xué)史研究者羅伯特·莫頓（RobertK.Merton）提出這個(gè)術(shù)語(yǔ)用以概括一種社會(huì)心理現(xiàn)象：“相對(duì)于那些不知名的研究者，聲名顯赫的科學(xué)家通常得到更多的聲望即使他們的成就是相似的，同樣地，在同一個(gè)項(xiàng)目上，聲譽(yù)通常給予那些已經(jīng)出名的研究者，例如，一個(gè)獎(jiǎng)項(xiàng)幾乎總是授予最資深的研究者，即使所有工作都是一個(gè)研究生完成的?！?/p>

第2頁(yè)/共431頁(yè)學(xué)時(shí)與參考教材學(xué)時(shí)：44+16學(xué)時(shí)參考教材：1、AlfredAhoect.《編譯原理》，趙建華等譯，機(jī)械工業(yè)出版社，2009.10.2、KennethC.Louden，《編譯原理及實(shí)踐》，馮博琴等譯，機(jī)械工業(yè)出版社，2001.2.3、金成植，《編譯程序構(gòu)造原理和實(shí)現(xiàn)技術(shù)》，高等教育出版社，2000.7.4、陳火旺等，《程序設(shè)計(jì)語(yǔ)言編譯原理》，國(guó)防工業(yè)出版社，2003.8.印刷第3頁(yè)/共431頁(yè)學(xué)時(shí)與參考教材5、何炎祥等，《編譯原理》，華中理工大學(xué)出版社，2000.10.6、蔣立源，《編譯原理》，西北工業(yè)大學(xué)出版社，2000.7.7、肖軍模，《程序設(shè)計(jì)語(yǔ)言編譯方法》，大連理工大學(xué)出版社，2000.88、蔣宗禮等，《形式語(yǔ)言與自動(dòng)機(jī)理論》，清華大學(xué)出版社，2003.1.第4頁(yè)/共431頁(yè)主要內(nèi)容編譯系統(tǒng)及其設(shè)計(jì)概述（總體結(jié)構(gòu)、設(shè)計(jì)方法）語(yǔ)言與文法（文法、推導(dǎo)、歸約、分類(lèi)、分析樹(shù)）詞法分析（詞法分析、正規(guī)式與正規(guī)文法、DFA的狀態(tài)轉(zhuǎn)移圖）語(yǔ)法分析（自頂向下：LL(1)、遞歸子程序；自底向上：LR）語(yǔ)義分析（屬性文法、各種語(yǔ)句的語(yǔ)法制導(dǎo)翻譯）運(yùn)行環(huán)境（存儲(chǔ)分配、過(guò)程調(diào)用、符號(hào)表管理）代碼優(yōu)化（基本塊的優(yōu)化、循環(huán)優(yōu)化等）代碼生成（目標(biāo)機(jī)器模型、基本塊和流圖、寄存器分配、基本塊的DAG表示、從 DAG生成目標(biāo)代碼）第5頁(yè)/共431頁(yè)教學(xué)目的——《編譯原理》是一門(mén)非常好的課程AlfredV.Aho：編寫(xiě)編譯器的原理和技術(shù)具有十分普遍的意義，以至于在每個(gè)計(jì)算機(jī)科學(xué)家的研究生涯中，本書(shū)中的原理和技術(shù)都會(huì)反復(fù)用到涉及的是一個(gè)比較適當(dāng)?shù)某橄髮用嫔系臄?shù)據(jù)變換（既抽象，又實(shí)際）一些具體的表示和變換算法“自頂向下的方法”和“自底向上的方法”系統(tǒng)設(shè)計(jì)方法（思想、方法、實(shí)現(xiàn)全方位討論）一個(gè)相當(dāng)規(guī)模的系統(tǒng)的設(shè)計(jì)（含總體結(jié)構(gòu)）計(jì)算機(jī)專(zhuān)業(yè)最為恰當(dāng)、有效的知識(shí)載體之一第6頁(yè)/共431頁(yè)教學(xué)要求掌握編譯程序總體結(jié)構(gòu)在系統(tǒng)級(jí)上認(rèn)識(shí)算法、系統(tǒng)的設(shè)計(jì)具有把握系統(tǒng)的能力學(xué)習(xí)有關(guān)的原理、實(shí)現(xiàn)方法和技術(shù)，了解計(jì)算學(xué)科的基本方法、思想掌握典型方法。“在每一個(gè)計(jì)算機(jī)科技工作者的職業(yè)生涯中，這些原理和技術(shù)都被反復(fù)用到。”兼顧語(yǔ)言的描述方法、設(shè)計(jì)、應(yīng)用——形式化能形式化就能自動(dòng)化進(jìn)一步培養(yǎng)“計(jì)算機(jī)思維能力”軟件系統(tǒng)的非物理性質(zhì)第7頁(yè)/共431頁(yè)學(xué)習(xí)成果__以學(xué)生為中心理解和掌握編譯過(guò)程各個(gè)階段的工作原理理解標(biāo)準(zhǔn)編譯器各個(gè)組成部分的任務(wù)熟悉編譯過(guò)程各階段所要解決的問(wèn)題及其采用的方法和技術(shù)應(yīng)用一些標(biāo)準(zhǔn)的技術(shù)解決編譯器構(gòu)造過(guò)程中所產(chǎn)生的相關(guān)問(wèn)題理解編譯器在生成代碼時(shí)如何充分利用特定處理器的特征第8頁(yè)/共431頁(yè)第1章引論1.1計(jì)算機(jī)語(yǔ)言的發(fā)展1.2翻譯系統(tǒng)1.3編譯系統(tǒng)的功能分析1.4編譯程序總體結(jié)構(gòu)1.5

編譯程序的生成1.6編譯技術(shù)的應(yīng)用第9頁(yè)/共431頁(yè)1.1計(jì)算機(jī)語(yǔ)言的發(fā)展機(jī)器語(yǔ)言(MachineLanguage)與匯編語(yǔ)言(AssembleLanguage)0、1代碼與助記符：更接近于計(jì)算機(jī)硬件指令系統(tǒng)的工作高級(jí)語(yǔ)言(HighLevelLanguage)其表示方法更接近于待解問(wèn)題的表示方法定義數(shù)據(jù)、描述運(yùn)算、控制流程、傳輸數(shù)據(jù)如：C、FORTRAN、PASCAL、C++、JAVA、SQL(數(shù)據(jù)定義、數(shù)據(jù)操作)命令語(yǔ)言(CommandLanguage)控制系統(tǒng)的工作——以功能封裝為特征如UNIX上的shell第10頁(yè)/共431頁(yè)1.2翻譯系統(tǒng)翻譯程序(Translator)將某一種語(yǔ)言描述的程序(源程序——SourceProgram)翻譯成等價(jià)的另一種語(yǔ)言描述的程序(目標(biāo)程序——ObjectProgram)的程序。翻譯程序源程序目標(biāo)程序(*.C/*.PAS)(*.OBJ/*.EXE)第11頁(yè)/共431頁(yè)1.2翻譯系統(tǒng)解釋程序(Interpreter)口譯與筆譯（單句提交與整篇提交）源程序輸入數(shù)據(jù)計(jì)算結(jié)果解釋程序第12頁(yè)/共431頁(yè)1.2翻譯系統(tǒng)編譯程序(Compiler)高級(jí)語(yǔ)言程序→匯編/機(jī)器語(yǔ)言程序源程序目標(biāo)程序編譯程序第13頁(yè)/共431頁(yè)1.2編譯系統(tǒng)SP Compiler

S-Source O-Object OP P-ProgramInput RS

RS-RunSys. Output 編譯系統(tǒng)(CompilingSystem)編譯系統(tǒng)=編譯程序+運(yùn)行系統(tǒng)支撐環(huán)境、運(yùn)行庫(kù)等第14頁(yè)/共431頁(yè)1.2翻譯系統(tǒng)其它：診斷編譯程序（DiagnosticCompiler)優(yōu)化編譯程序（OptimizingCompiler)交叉編譯程序（CrossCompiler)可變目標(biāo)編譯程序（RetargetableCompiler)并行編譯程序（ParallelizingCompiler）匯編程序(Assembler)、交叉匯編程序(CrossAssembler)、反匯編程序（Disassembler)第15頁(yè)/共431頁(yè)1.2翻譯系統(tǒng)—匯總ML MLP Assembler DisassemblerAL ALP Translator Compiler DataHL HLP Interpreter ResultM-MachineL-LangugeP-ProgramA-AssembleH-HighLevel第16頁(yè)/共431頁(yè)1.3編譯系統(tǒng)的功能分析程序分析詞法、語(yǔ)法、語(yǔ)義分析綜合語(yǔ)句的翻譯、代碼生成標(biāo)識(shí)符處理：左值與右值的綁定(binding)變量：存儲(chǔ)單元函數(shù)：目標(biāo)代碼序列第17頁(yè)/共431頁(yè)1.4編譯程序總體結(jié)構(gòu)目標(biāo)代碼生成器代碼優(yōu)化器語(yǔ)義分析與中間代碼生成器語(yǔ)法分析器表格管理出錯(cuò)處理中間代碼中間代碼目標(biāo)代碼語(yǔ)法單位單詞符號(hào)詞法分析器源程序第18頁(yè)/共431頁(yè)1.詞法分析例：main(){printf(“hello”);}結(jié)果IDN main‘(’‘)’‘{’IDN printf‘(’STR hello‘)’‘;’‘}’第19頁(yè)/共431頁(yè)1、詞法分析詞法分析由詞法分析器完成(LexicalAnalyzer)，詞法分析器又叫做掃描器(Scanner)詞法分析器從左到右掃描源程序——發(fā)現(xiàn)一個(gè)字符串，則將該字符串轉(zhuǎn)換成單詞(記號(hào)—Token)串；同時(shí)要：查詞法錯(cuò)誤，進(jìn)行標(biāo)識(shí)符登記——符號(hào)表管理。輸入：字符串 輸出：(種別碼，屬性值)——序?qū)傩灾怠猼oken的機(jī)內(nèi)表示第20頁(yè)/共431頁(yè)2、語(yǔ)法分析語(yǔ)法分析由語(yǔ)法分析器(SyntaxAnalyzer)完成，語(yǔ)法分析器又叫Parser。功能：Parser實(shí)現(xiàn)“組詞成句”

將詞組成各類(lèi)語(yǔ)法成分：表達(dá)式、因子、項(xiàng)，語(yǔ)句，子程序…構(gòu)造分析樹(shù)指出語(yǔ)法錯(cuò)誤指導(dǎo)翻譯輸入：Token序列輸出：語(yǔ)法成分第21頁(yè)/共431頁(yè)2.語(yǔ)法分析res=fact*(term1+term2);*；賦值語(yǔ)句表達(dá)式=）（fact表達(dá)式res表達(dá)式表達(dá)式表達(dá)式表達(dá)式+term1term2第22頁(yè)/共431頁(yè)3.語(yǔ)義分析功能：分析由語(yǔ)法分析器識(shí)別出的語(yǔ)法單位的語(yǔ)義獲取標(biāo)識(shí)符的屬性：類(lèi)型、作用域等語(yǔ)義檢查：運(yùn)算的合法性、取值范圍等子程序的靜態(tài)綁定：代碼的相對(duì)地址變量的靜態(tài)綁定：數(shù)據(jù)的相對(duì)地址第23頁(yè)/共431頁(yè)4.中間代碼生成中間代碼(intermediateCode)例:id1+id2*id3后綴表示(逆波蘭Anti-PolishNotation)id1id2id3*

+前綴表示(波蘭PolishNotation)+id1*id2id3四元式表示(三地址碼)1(*,id1,id2,T1)2(+,id3,T1,T2)

三元式表示1(*,id2,id3)2(+,id1,(1))

EE+EidE*Eidid語(yǔ)法樹(shù)第24頁(yè)/共431頁(yè)4.中間代碼生成中間代碼的特點(diǎn)簡(jiǎn)單規(guī)范與機(jī)器無(wú)關(guān)易于優(yōu)化與轉(zhuǎn)換三地址碼的另一種表示形式T1=id2*id3T2=id1*T1其它類(lèi)型的語(yǔ)句例：printf(“hello”)x:=s （賦值）paramx （參數(shù)）callf （函數(shù)調(diào)用）注釋s是hello的地址f是函數(shù)

printf的地址第25頁(yè)/共431頁(yè)對(duì)中間代碼的優(yōu)化處理:對(duì)代碼進(jìn)行等價(jià)變換以求提高執(zhí)行效率——提高運(yùn)行速度和節(jié)省存儲(chǔ)空間與機(jī)器無(wú)關(guān)的優(yōu)化與機(jī)器有關(guān)的優(yōu)化5.代碼優(yōu)化第26頁(yè)/共431頁(yè)與機(jī)器無(wú)關(guān)的優(yōu)化局部?jī)?yōu)化常量合并：常數(shù)運(yùn)算在編譯期間完成，如8+9*4公共子表達(dá)式的提取:基本塊內(nèi)循環(huán)優(yōu)化強(qiáng)度削減用較快的操作代替較慢的操作代碼外提將循環(huán)不變計(jì)算移出循環(huán)第27頁(yè)/共431頁(yè)與機(jī)器有關(guān)的優(yōu)化寄存器的利用將常用量放入寄存器，以減少訪問(wèn)內(nèi)存的次數(shù)體系結(jié)構(gòu)MIMD、SIMD、SPMD、向量機(jī)、流水機(jī)存儲(chǔ)策略根據(jù)算法訪存的要求安排：Cache、并行存儲(chǔ)體系——減少訪問(wèn)沖突任務(wù)劃分按運(yùn)行的算法及體系結(jié)構(gòu)，劃分子任務(wù)(MPMD)第28頁(yè)/共431頁(yè)6.目標(biāo)代碼生成（CodeGenerator）將中間代碼轉(zhuǎn)換成目標(biāo)機(jī)上的機(jī)器指令代碼或匯編代碼確定源語(yǔ)言的各種語(yǔ)法成分的目標(biāo)代碼結(jié)構(gòu)（機(jī)器指令組/匯編語(yǔ)句組）制定從中間代碼到目標(biāo)代碼的翻譯策略或算法目標(biāo)代碼的形式具有絕對(duì)地址的機(jī)器指令匯編語(yǔ)言形式的目標(biāo)程序模塊結(jié)構(gòu)的機(jī)器指令（需要鏈接程序）第29頁(yè)/共431頁(yè)7、表格管理管理各種符號(hào)表（常數(shù)、標(biāo)號(hào)、變量、過(guò)程、結(jié)構(gòu)……），查、填（登記、查找）源程序中出現(xiàn)的符號(hào)和編譯程序生成的符號(hào)，為編譯的各個(gè)階段提供信息。輔助語(yǔ)法檢查、語(yǔ)義檢查完成靜態(tài)綁定、管理編譯過(guò)程Hash表、鏈表等各種查、填表技術(shù)第30頁(yè)/共431頁(yè)8、錯(cuò)誤處理進(jìn)行各種錯(cuò)誤的檢查、報(bào)告、糾正，以及相應(yīng)的續(xù)編譯處理（如：錯(cuò)誤的定位與局部化）詞法：拼寫(xiě)……語(yǔ)法：語(yǔ)句結(jié)構(gòu)、表達(dá)式結(jié)構(gòu)……語(yǔ)義：類(lèi)型不匹配……第31頁(yè)/共431頁(yè)編譯系統(tǒng)詞法分析語(yǔ)法分析語(yǔ)義分析中間代碼代碼優(yōu)化目標(biāo)代碼錯(cuò)誤處理符號(hào)表源程序目標(biāo)程序分析綜合第32頁(yè)/共431頁(yè)模塊分類(lèi)分析：詞法分析、語(yǔ)法分析、語(yǔ)義分析、中間代碼生成綜合：代碼優(yōu)化、目標(biāo)代碼生成輔助：符號(hào)表管理、出錯(cuò)處理8項(xiàng)功能對(duì)應(yīng)8個(gè)模塊第33頁(yè)/共431頁(yè)例一個(gè)語(yǔ)句的翻譯第34頁(yè)/共431頁(yè)9編譯的遍（Pass）根據(jù)系統(tǒng)資源的狀況、運(yùn)行目標(biāo)的要求……等，可以將一個(gè)編譯程序設(shè)計(jì)成多遍掃描的形式，在每一遍掃描中，完成不同的任務(wù)。如：首遍構(gòu)造語(yǔ)法樹(shù)，二遍處理中間表示，增加信息等。遍可以和階段相對(duì)應(yīng)，也可無(wú)關(guān)單遍代碼不太有效第35頁(yè)/共431頁(yè)10、編譯的前端與后端前端與源語(yǔ)言有關(guān)、與目標(biāo)機(jī)無(wú)關(guān)的部分詞法分析、語(yǔ)法分析、語(yǔ)義分析與中間代碼生成、與機(jī)器無(wú)關(guān)的代碼優(yōu)化后端與目標(biāo)機(jī)有關(guān)的部分與機(jī)器有關(guān)的代碼優(yōu)化、目標(biāo)代碼生成第36頁(yè)/共431頁(yè)1.5編譯程序的生成設(shè)計(jì)目標(biāo)目標(biāo)程序小，執(zhí)行速度快。編譯程序小，執(zhí)行速度快。診斷能力強(qiáng)，可靠性強(qiáng)?？梢浦残?，可擴(kuò)充性。如何實(shí)現(xiàn)編譯器？直接用可運(yùn)行的代碼編制——太費(fèi)力！自舉-使用語(yǔ)言提供的功能來(lái)編譯該語(yǔ)言自身?！暗谝粋€(gè)編譯器是怎樣被編譯的？”第37頁(yè)/共431頁(yè)問(wèn)題：直接在一個(gè)機(jī)上實(shí)現(xiàn)C語(yǔ)言編譯器，還有別的技術(shù)么？解決：用匯編語(yǔ)言實(shí)現(xiàn)一個(gè)Ｃ子集的編譯程序(P0—人)用匯編程序處理該程序,得到(P2:可直接運(yùn)行)用Ｃ子集編制Ｃ語(yǔ)言的編譯程序(P3—人)用P2編譯P3，得到P41)編譯程序的自展技術(shù)第38頁(yè)/共431頁(yè)2)利用編譯程序自動(dòng)生成器詞法分析器的自動(dòng)生成程序ＬＥＸ詞法規(guī)則說(shuō)明詞法分析程序(C程序)輸入： 詞法（正規(guī)表達(dá)式） 識(shí)別動(dòng)作（Ｃ程序段）輸出：

yylex()函數(shù)第39頁(yè)/共431頁(yè)語(yǔ)法分析器的自動(dòng)生成程序ＹＡＣＣ語(yǔ)法規(guī)則說(shuō)明語(yǔ)法分析程序(C程序)輸入： 語(yǔ)法規(guī)則（產(chǎn)生式） 語(yǔ)義動(dòng)作（Ｃ程序段）輸出：

yyparse()函數(shù)第40頁(yè)/共431頁(yè)1.6編譯技術(shù)的應(yīng)用把復(fù)雜數(shù)據(jù)看作一條語(yǔ)句數(shù)據(jù)格式的分析利用詞法分析、語(yǔ)法分析方法數(shù)據(jù)處理的框架基于語(yǔ)法制導(dǎo)的語(yǔ)義處理框架編譯技術(shù)可以用于各種復(fù)雜數(shù)據(jù)的分析處理第41頁(yè)/共431頁(yè)1.6編譯技術(shù)的應(yīng)用

語(yǔ)法制導(dǎo)的結(jié)構(gòu)化編輯器程序格式化工具軟件測(cè)試工具程序理解工具高級(jí)語(yǔ)言的翻譯工具

……第42頁(yè)/共431頁(yè)例1-1DOS命令date的輸出格式例：9-2-1993、09-03-1993、9-03-93語(yǔ)法date→month-day-year詞法month→DIGITDIGIT|DIGITday→DIGITDIGIT|DIGITyear→DIGITDIGIT|DIGIIDIGITDIGITDIGIT第43頁(yè)/共431頁(yè)例1-1（續(xù)）語(yǔ)義year(年)、month(月)、day(日)語(yǔ)義約束條件0<month.value<130<day.value<32，31，300<year.value<10000第44頁(yè)/共431頁(yè)小結(jié)計(jì)算機(jī)語(yǔ)言的發(fā)展翻譯系統(tǒng)及其功能編譯的總體結(jié)構(gòu)編譯的各個(gè)階段編譯的生成及應(yīng)用相關(guān)概念第45頁(yè)/共431頁(yè)習(xí)題1.試分析一個(gè)簡(jiǎn)短的C程序，找出幾個(gè)屬于語(yǔ)法、詞法、語(yǔ)義的語(yǔ)言現(xiàn)象。2.試分析例1-1的date輸出數(shù)據(jù)的處理中，應(yīng)該做哪些詞法分析、語(yǔ)法分析、語(yǔ)義處理。第46頁(yè)/共431頁(yè)高級(jí)語(yǔ)言及其文法第47頁(yè)/共431頁(yè)2.1語(yǔ)言概述2.2基本定義2.3文法(Grammar)的定義2.4CFG的分析樹(shù)（ParseTree）2.5文法的分類(lèi)2.6文法的構(gòu)造本章主要內(nèi)容第48頁(yè)/共431頁(yè)2.1語(yǔ)言概述什么是語(yǔ)言？第49頁(yè)/共431頁(yè)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)格第50頁(yè)/共431頁(yè)2.1語(yǔ)言概述語(yǔ)言的描述方法——現(xiàn)狀自然語(yǔ)言：自然、方便-非形式化數(shù)學(xué)語(yǔ)言（符號(hào)）：嚴(yán)格、準(zhǔn)確-形式化形式化描述高度的抽象，嚴(yán)格的理論基礎(chǔ)和方便的計(jì)算機(jī)表示。第51頁(yè)/共431頁(yè)2.1語(yǔ)言概述語(yǔ)言——形式化的內(nèi)容提取語(yǔ)言(Language)：滿足一定條件的句子集合句子(Sentence)：滿足一定規(guī)則的單詞序列單詞(Token)：滿足一定規(guī)則的字符(Character)串語(yǔ)言是字和組合字的規(guī)則例（自然語(yǔ)言：第譯始一天課今開(kāi)編上節(jié)）今天開(kāi)始上第一節(jié)編譯課第52頁(yè)/共431頁(yè)2.1語(yǔ)言概述程序設(shè)計(jì)語(yǔ)言——形式化的內(nèi)容提取程序設(shè)計(jì)語(yǔ)言(ProgrammingLanguage)：組成程序的所有語(yǔ)句的集合。程序(Program)：滿足語(yǔ)法規(guī)則的語(yǔ)句序列。語(yǔ)句(Sentence)：滿足語(yǔ)法規(guī)則的單詞序列。單詞(Token)：滿足詞法規(guī)則的字符串。例：變量:=表達(dá)式if條件then語(yǔ)句while條件do語(yǔ)句call過(guò)程名(參數(shù)表)第53頁(yè)/共431頁(yè)2.1語(yǔ)言概述描述形式——文法語(yǔ)法——語(yǔ)句語(yǔ)句的組成規(guī)則描述方法：BNF范式、語(yǔ)法(描述)圖詞法——單詞單詞的組成規(guī)則描述方法：BNF范式、正規(guī)式第54頁(yè)/共431頁(yè)形式語(yǔ)言于自動(dòng)機(jī)理論的產(chǎn)生與作用語(yǔ)言學(xué)家Chomsky最初從產(chǎn)生語(yǔ)言的角度研究語(yǔ)言。1956年，通過(guò)抽象，他將語(yǔ)言形式地定義為是由一個(gè)字母表中的字母組成的一些串的集合。可以在字母表上按照一定的規(guī)則定義一個(gè)文法（Grammar），該文法所能產(chǎn)生的所有句子組成的集合就是該文法產(chǎn)生的語(yǔ)言?？肆郑↘leene）在1951年到1956年間，從識(shí)別語(yǔ)言的角度研究語(yǔ)言，給出了語(yǔ)言的另一種描述?？肆质窃谘芯可窠?jīng)細(xì)胞中，建立了自動(dòng)機(jī)，他用這種自動(dòng)機(jī)來(lái)識(shí)別語(yǔ)言：對(duì)于按照一定的規(guī)則構(gòu)造的任一個(gè)自動(dòng)機(jī)，該自動(dòng)機(jī)就定義了一個(gè)語(yǔ)言，這個(gè)語(yǔ)言由該自動(dòng)機(jī)所能識(shí)別的所有句子組成。第55頁(yè)/共431頁(yè)形式語(yǔ)言于自動(dòng)機(jī)理論的產(chǎn)生與作用1959年，Chomsky通過(guò)深入研究，將他本人的研究成果與克林的研究成果結(jié)合了起來(lái)，不僅確定了文法和自動(dòng)機(jī)分別從生成和識(shí)別的角度去表達(dá)語(yǔ)言，而且證明了文法與自動(dòng)機(jī)的等價(jià)性。20世紀(jì)50年代，人們用巴科斯范式（BackusNourForm或BackusNormalForm，簡(jiǎn)記為BNF）成功地對(duì)高級(jí)語(yǔ)言ALGOL-60進(jìn)行了描述。實(shí)際上，巴科斯范式就是上下文無(wú)關(guān)文法（ContextFreeGrammar）的一種表示形式。這一成功，使得形式語(yǔ)言在20世紀(jì)60年代得到了大力的發(fā)展。第56頁(yè)/共431頁(yè)形式語(yǔ)言于自動(dòng)機(jī)理論的產(chǎn)生與作用形式語(yǔ)言與自動(dòng)機(jī)理論除了在計(jì)算機(jī)科學(xué)領(lǐng)域中的直接應(yīng)用外，更在計(jì)算學(xué)科人才的計(jì)算思維的培養(yǎng)中占有極其重要的地位計(jì)算思維能力的培養(yǎng)，主要是由基礎(chǔ)理論系列課程實(shí)現(xiàn)的，該系列主要由從數(shù)學(xué)分析開(kāi)始到形式語(yǔ)言結(jié)束的一些數(shù)學(xué)和抽象程度比較高的內(nèi)容的課程組成。它們構(gòu)成的是一個(gè)梯級(jí)訓(xùn)練系統(tǒng)。在此系統(tǒng)中，連續(xù)數(shù)學(xué)、離散數(shù)學(xué)、計(jì)算模型等三部分內(nèi)容要按階段分開(kāi)，三個(gè)階段對(duì)應(yīng)與本學(xué)科的學(xué)生在大學(xué)學(xué)習(xí)期間的思維方式和能力的變化與提高過(guò)程的三個(gè)步驟。第57頁(yè)/共431頁(yè)計(jì)算思維能力的培養(yǎng)過(guò)程中學(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ì)算）

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

(4)ASCII字母表第59頁(yè)/共431頁(yè)2.2基本定義符號(hào)串的定義由字母表中的符號(hào)所組成的任何有窮序列被稱(chēng)之為該字母表上的符號(hào)串,也稱(chēng)作"字"。(1)ε是∑上的一個(gè)符號(hào)串。(2)若x是∑上的符號(hào)串，而a是∑的元素,則xa是∑上的符號(hào)串。(3)y是∑上的符號(hào)串,當(dāng)且僅當(dāng)它由(1)和(2)導(dǎo)出。第60頁(yè)/共431頁(yè)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)：將S中的符號(hào)按相反次序?qū)懗龆玫降姆?hào)串長(zhǎng)度：是該符號(hào)串中的符號(hào)的數(shù)目。例如|aab|=3,|ε|=0。第61頁(yè)/共431頁(yè)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;例如,設(shè)x=ba,則x1=ba,x2=baba,x3=bababa,……第62頁(yè)/共431頁(yè)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}第63頁(yè)/共431頁(yè)2.2基本定義定義3設(shè)∑是一個(gè)字母表，∑的正閉包(PositiveClosure)定義為：∑+=∑∪∑2∪∑3∪∑4∪……∑的克林閉包(KleeneClosure)為：∑*=∑0∪∑+=∑0∪∑∪∑2∪∑3∪……

第64頁(yè)/共431頁(yè)2.2基本定義例{0,1}+={0，1，00，01，11，000，001，010，011，100，……}{0,1}*={ε，0，1，00，01，11，000，001，010，011，100，…}

第65頁(yè)/共431頁(yè)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}*第66頁(yè)/共431頁(yè)2.3文法的定義如何實(shí)現(xiàn)語(yǔ)言結(jié)構(gòu)的形式化描述？第67頁(yè)/共431頁(yè)考慮一個(gè)句子——文法要素的提取分析：Thegreywolfwilleatthegoat〈謂語(yǔ)〉〈主語(yǔ)〉〈形容詞〉〈名詞〉〈動(dòng)詞〉〈直接賓語(yǔ)〉助動(dòng)詞〈句子〉動(dòng)原冠詞名詞Thegreywolfwilleatthegoat〈冠詞〉第68頁(yè)/共431頁(yè)句子主語(yǔ)

謂語(yǔ)（1）主語(yǔ)冠詞形容詞名詞（2）冠詞the

（3）形容詞grey

（4）謂語(yǔ)

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

（7）動(dòng)詞原形eat

（8）直接賓語(yǔ)

冠詞名詞（9）名詞wolf

（10）

名詞goat

（11）句子的組成規(guī)則問(wèn)題：如何用符號(hào)來(lái)描述？即如何形式化？〈謂語(yǔ)〉〈主語(yǔ)〉〈形容詞〉〈名詞〉〈動(dòng)詞〉〈直接賓語(yǔ)〉助動(dòng)詞〈句子〉動(dòng)原冠詞名詞The

grey

wolf

will

eat

the

goat〈冠詞〉第69頁(yè)/共431頁(yè)終結(jié)符號(hào)集VT= {the，grey,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=句子定義句子的規(guī)則的語(yǔ)法組成

__終結(jié)符號(hào)集，非終結(jié)符號(hào)集，語(yǔ)法規(guī)則，開(kāi)始符號(hào)問(wèn)題：有了定義句子的規(guī)則，如何判定某一句子是否屬于某語(yǔ)言？第70頁(yè)/共431頁(yè)句子主語(yǔ)謂語(yǔ)冠詞形容詞名詞謂語(yǔ)the

形容詞名詞謂語(yǔ)thegrey名詞謂語(yǔ)thegreywolf

謂語(yǔ)thegreywolf

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

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

句子的歸約-從識(shí)別語(yǔ)言的角度-均根據(jù)規(guī)則第71頁(yè)/共431頁(yè)句子thegreywolfwilleatthegoat

thegreywolfwilleatthewolf

thegreygoat

willeatthewolfthegreygoat

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

thegreywolfwilleatthegoat句子的語(yǔ)義要求第72頁(yè)/共431頁(yè)文法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代表文法所定義的語(yǔ)言，至少在產(chǎn)生式左側(cè)出現(xiàn)一次第73頁(yè)/共431頁(yè)文法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)。產(chǎn)生式定義各個(gè)語(yǔ)法成分的結(jié)構(gòu)（組成規(guī)則）

第74頁(yè)/共431頁(yè)例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á)式；第75頁(yè)/共431頁(yè)例2-1算術(shù)表達(dá)式的文法考慮簡(jiǎn)單算術(shù)表達(dá)式組成的語(yǔ)言G=({id，+，*，(，)}，{E}，P，E)P:E→E+EE→E*EE→(E)E→id約定：只寫(xiě)產(chǎn)生式簡(jiǎn)寫(xiě)E→E+E|E*E|(E)|id（2.1）第76頁(yè)/共431頁(yè)產(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)。第77頁(yè)/共431頁(yè)基于產(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也就是說(shuō)，根據(jù)第4個(gè)候選式，E*E+E經(jīng)3步變換變成id*id+id第78頁(yè)/共431頁(yè)直接推導(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第79頁(yè)/共431頁(yè)（多步）推導(dǎo)α0α1α2…αn記為α0n

αn

(恰用n步)

α0+

αn

（至少一步）

α0*

αn

（若干步:零步或多步）第80頁(yè)/共431頁(yè)推導(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ǔ)法）變量了，不能再推導(dǎo)了1、E→E+E2、E→E*E3、E→(E)4、E→id第81頁(yè)/共431頁(yè)句型與句子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)第82頁(yè)/共431頁(yè)文法G產(chǎn)生的語(yǔ)言 Ｌ(Ｇ)＝{x｜Ｓ*

xandx∈ＶT*}文法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也可是有窮）第83頁(yè)/共431頁(yè)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*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*id第84頁(yè)/共431頁(yè)最左推導(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)句型第85頁(yè)/共431頁(yè)例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問(wèn)題：正整數(shù)的文法?正實(shí)數(shù)的文法？第86頁(yè)/共431頁(yè)2.４文法的分類(lèi)(Chomsky體系)根據(jù)語(yǔ)言結(jié)構(gòu)的復(fù)雜程度（形式語(yǔ)言）涉及文法的復(fù)雜程度、分析方法的選擇反映文法描述語(yǔ)言的能力如果G滿足文法定義的要求，則Ｇ是０型文法（短語(yǔ)結(jié)構(gòu)文法PSG:PhraseStructureGrammar）。L(G)為PSL。第87頁(yè)/共431頁(yè)上下文有關(guān)文法(CSG)若產(chǎn)生式集合中所有｜α｜≤｜β｜，除Ｓ→ε外，則Ｇ是１型文法即：上下文有關(guān)文法（CSG——ContextSensitiveGrammar）L(G)為1型/上下文有關(guān)/敏感語(yǔ)言(CSL)第88頁(yè)/共431頁(yè)上下文無(wú)關(guān)文法(CFG)若α∈ＶN，β∈(ＶN∪ＶT)*，則Ｇ是２型文法即：上下文無(wú)關(guān)文法(CFG:ContextFreeGrammar)L(G)為2型/上下文無(wú)關(guān)語(yǔ)言（CFL）CFG能描述程序設(shè)計(jì)語(yǔ)言的多數(shù)語(yǔ)法成分第89頁(yè)/共431頁(yè)例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 |1T|2T|3T|4T|5T第90頁(yè)/共431頁(yè)正規(guī)文法(RG)設(shè)Ａ、Ｂ∈ＶN，ａ∈ＶT或?yàn)橛揖€性(RightLinear)文法：Ａ→ａＢ或Ａ→ａ左線性(LeftLinear)文法：Ａ→Ｂａ或Ａ→ａ都是３型文法(正規(guī)文法RegularGrammar-RG)L(G)為3型/正規(guī)集/正則集/正則語(yǔ)言（RL）能描述程序設(shè)計(jì)語(yǔ)言的多數(shù)單詞左、右線性文法不可混用第91頁(yè)/共431頁(yè)例非CFL的文法L={anbncn|n>0}的文法SaBC|aSBCCBBCaBabbBbbbCbc“可以證明”不存在CFGG,使L(G)=L第92頁(yè)/共431頁(yè)

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

例2.5L2={anbmcndm|n,m≥0}，它是檢查過(guò)程聲明的形參個(gè)數(shù)和過(guò)程引用的參數(shù)個(gè)數(shù)是否一致問(wèn)題的抽象。非上下文無(wú)關(guān)的語(yǔ)言結(jié)構(gòu)第93頁(yè)/共431頁(yè)Chomsky體系——總結(jié)Ｇ=(ＶT，ＶN，Ｐ，Ｓ)是一個(gè)文法,α→β∈P* G是0型文法，L(G)是0型語(yǔ)言；

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

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

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

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

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

Backus-NormalFormα→β表示為α∷＝β非終結(jié)符用“<”和“>”括起來(lái)終結(jié)符：基本符號(hào)集其他β(α1|α2…|αn)≡βα1|βα2…|βαn[α]≡α|ε……第96頁(yè)/共431頁(yè)ＢＮＦ范式——BackusNormalForm例簡(jiǎn)單算術(shù)表達(dá)式(只寫(xiě)產(chǎn)生式)<算術(shù)表達(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即：<算術(shù)表達(dá)式>∷＝<簡(jiǎn)單表達(dá)式>+<簡(jiǎn)單表達(dá)式>|<簡(jiǎn)單表達(dá)式>*<簡(jiǎn)單表達(dá)式>|(<簡(jiǎn)單表達(dá)式>)|id哪些是終結(jié)符？哪些是變量？第97頁(yè)/共431頁(yè)例2-6句子結(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ù)！第98頁(yè)/共431頁(yè)2.5CFG的分析樹(shù)ParseTree用樹(shù)的形式表示句型的生成樹(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ù)第99頁(yè)/共431頁(yè)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短語(yǔ)第100頁(yè)/共431頁(yè)二義性文法與先天二義性語(yǔ)言對(duì)同一句子存在兩棵語(yǔ)法分析樹(shù)在理論上不可判定EE*EidEE+ididEE+EEEid*idid第101頁(yè)/共431頁(yè)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文法的二義性第102頁(yè)/共431頁(yè)

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)第103頁(yè)/共431頁(yè)

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)第104頁(yè)/共431頁(yè)如果一個(gè)文法的句子存在兩棵分析樹(shù),那么,該句子是二義性的。如果一個(gè)文法包含二義性的句子,則稱(chēng)這個(gè)文法是二義性的;否則，該文法是無(wú)二義性的。幾點(diǎn)說(shuō)明：1.一般來(lái)說(shuō)，程序語(yǔ)言存在無(wú)二義性文法，對(duì)于表達(dá)式來(lái)說(shuō)，文法（2.1）是二義性的。對(duì)于條件語(yǔ)句，經(jīng)常使用二義性文法描述它：SifexprthenSifexprthenSelseSother二義性的句子:ife1thenife2thens1elses2

二義性（歧義性，ambiquity)的定義第105頁(yè)/共431頁(yè)

下面是

Smatched_sunmatched_smatched_sifexprthenmatched_selsematched_sotherunmatched_sifexprthenSifexprthenmatched_selseunmatched_s它顯然比較復(fù)雜，因此：2.在能駕馭的情況下，使用二義性文法。描述if語(yǔ)句的無(wú)二義性文法的產(chǎn)生式第106頁(yè)/共431頁(yè)3.對(duì)于任意一個(gè)上下文無(wú)關(guān)文法，不存在一個(gè)算法，判定它是無(wú)二義性的；但能給出一組充分條件，滿足這組充分條件的文法是無(wú)二義性的。4.存在先天二義性語(yǔ)言。例如，

aibicji,j1aibjcji,j1存在一個(gè)二義性的句子akbkck。第107頁(yè)/共431頁(yè)(抽象)語(yǔ)法樹(shù)與分析樹(shù)不同(語(yǔ)法)分析樹(shù)EE+idE+EEidid(抽象)語(yǔ)法樹(shù)+id+idid第108頁(yè)/共431頁(yè)2.6文法的構(gòu)造明確描述對(duì)象──語(yǔ)言合法的語(yǔ)言結(jié)構(gòu)確定基本符號(hào)集ＶT引入非終結(jié)符各種語(yǔ)法成分的結(jié)構(gòu)定義句子的組成規(guī)則BNF范式或產(chǎn)生式第109頁(yè)/共431頁(yè)文法舉例{x|x是長(zhǎng)度為偶數(shù)的0、1串}S→00S|01S|10S|11S|ε{0m

1n

|m,n≥1} ——RLS→0S|0A A→1A|1{0n

1n

|n≥1} ——CFLS→0S1|01{ww

|w∈{a,b}+} ——PSLS→aCAE|bCBE Aa→aAAb→bAAE→aRE RE→DaR→RabR→RbCR→aCA|bCBBa→aBBb→bBBE→bREaR→RabR→RbCR→aCA|bCBaD→DabD→DbED→ε第110頁(yè)/共431頁(yè)值得注意的問(wèn)題文法描述描述句子的組成規(guī)則，不涉及語(yǔ)義文法正確不能保證語(yǔ)義正確（例）明確目標(biāo)要描述語(yǔ)言的結(jié)構(gòu)確認(rèn)基本符號(hào)集合理引入非終結(jié)符（語(yǔ)義明確）第111頁(yè)/共431頁(yè)本章小結(jié)：幾個(gè)基本概念文法是語(yǔ)言的一種有窮描述，它嚴(yán)格、準(zhǔn)確、簡(jiǎn)潔。文法的形式定義句型、句子、語(yǔ)言文法的分類(lèi)ＣＦＧ的分析樹(shù)第112頁(yè)/共431頁(yè)詞法分析第113頁(yè)/共431頁(yè)第三章詞法分析詞法分析器(Scanner)的功能正則表達(dá)式狀態(tài)轉(zhuǎn)換圖詞法分析器的設(shè)計(jì)與實(shí)現(xiàn)有窮自動(dòng)機(jī)FA第114頁(yè)/共431頁(yè)3.1詞法分析（掃描）器的功能功能：輸入源程序，輸出單詞符號(hào)(token)。即：把構(gòu)成源程序的字符串轉(zhuǎn)換成單詞符號(hào)的序列單詞符號(hào)的形式按照最小的語(yǔ)義單位設(shè)計(jì)通常表示為二元組： （單詞種別，屬性值）關(guān)鍵——找出符號(hào)的分割符第115頁(yè)/共431頁(yè)1)單詞符號(hào)的表示常用單詞種別—分類(lèi)（肖軍模P53，杜P46）各關(guān)鍵字（保留字、基本字），各種運(yùn)算符，各種分界符——各用一個(gè)種別碼標(biāo)識(shí)標(biāo)識(shí)符——用一個(gè)種別碼標(biāo)識(shí)整、實(shí)、字符常數(shù)——各用一個(gè)種別碼標(biāo)識(shí)屬性（值）——單詞的值常數(shù)的值，標(biāo)識(shí)符的名字等保留字、運(yùn)算符、分界符的屬性值可以省略第116頁(yè)/共431頁(yè)例3-1:單詞符號(hào)序列

while(*pointer!='\0'){pointer++;}

while (WHILE，_)( (SLP，_)* (FETCH，_)pointer (IDN，符號(hào)表入口指針)!= (RELOP，NE)'\0' (CONST，0)) (SRP，_){ (LP，_)pointer (IDN，符號(hào)表入口指針)++ (INC，_); (SEMI，_)} (RP，_)跟實(shí)現(xiàn)有關(guān)第117頁(yè)/共431頁(yè)2）相關(guān)問(wèn)題超前掃描雙字符運(yùn)算符（**,/*,:=,…）DO90k=1,10DO90k=1.10預(yù)處理問(wèn)題剔除源程序中的無(wú)用符號(hào)、空格、換行、注釋等掃描器的運(yùn)行方式作為獨(dú)立的遍：簡(jiǎn)單，但需增加額外的開(kāi)銷(xiāo)作為獨(dú)立的子程序：節(jié)省內(nèi)存第118頁(yè)/共431頁(yè)掃描器作為獨(dú)立的子程序第119頁(yè)/共431頁(yè)2）相關(guān)問(wèn)題符號(hào)表的查填兼顧問(wèn)題兼顧：token自身值作為符號(hào)表的入口Token串長(zhǎng)度統(tǒng)一，可放寬對(duì)標(biāo)識(shí)符的限制，但要增加額外負(fù)擔(dān)不兼顧：token自身值就是標(biāo)識(shí)符、常數(shù)本身的符號(hào)串速度快，但要限制標(biāo)識(shí)符的長(zhǎng)度第120頁(yè)/共431頁(yè)2）相關(guān)問(wèn)題錯(cuò)誤處理行、列計(jì)數(shù)發(fā)現(xiàn)并定位詞法錯(cuò)誤處理方法恐慌模式刪除剩余輸入中的一個(gè)字符向剩余輸入插入一個(gè)字符字符替換等第121頁(yè)/共431頁(yè)3）符號(hào)表的作用 符號(hào)表是一張表格，由編譯程序建立，存在于內(nèi)存或磁盤(pán)中，用于存儲(chǔ)程序編譯或運(yùn)行過(guò)程中所使用的變量（標(biāo)識(shí)符）和常量（數(shù)字常數(shù)、字符常數(shù)）等信息。詞法分析階段：建立符號(hào)表，查填符號(hào)表，將不重復(fù)的標(biāo)識(shí)符、數(shù)字常數(shù)和字符常數(shù)的性質(zhì)填入符號(hào)表中，如：名字、類(lèi)型、數(shù)值等，并且將變量（或常數(shù)）在符號(hào)表中的入口地址寫(xiě)到其自身的TOKEN字中。語(yǔ)法分析階段：主要是使用符號(hào)表。在分析過(guò)程中，需要用到某個(gè)標(biāo)識(shí)符（或常數(shù)）時(shí)，就從符號(hào)表的指定入口處查找出該符號(hào)。語(yǔ)義分析及中間代碼生成階段：主要是查填符號(hào)表。在生成四元式時(shí)，通常不使用變量的名字，而是使用它們?cè)诜?hào)表中的入口位置。另外，在翻譯說(shuō)明語(yǔ)句時(shí)，要向符號(hào)表中填入變量的類(lèi)型信息等。第122頁(yè)/共431頁(yè)符號(hào)表的作用（2）數(shù)據(jù)存儲(chǔ)分配：將變量（或常數(shù)）所使用的數(shù)據(jù)區(qū)映像地址寫(xiě)入符號(hào)表中的地址（ADDR）欄。若數(shù)據(jù)區(qū)是動(dòng)態(tài)數(shù)據(jù)，則在符號(hào)表中存儲(chǔ)過(guò)程層號(hào)和位移量等信息，待運(yùn)行時(shí)再計(jì)算具體地址。代碼優(yōu)化階段：使用符號(hào)表。一方面，遇到變量時(shí)，要到符號(hào)表中查找它的具體信息，另一方面，在優(yōu)化過(guò)程中，也有可能要使用符號(hào)表，例如在進(jìn)行合并已知量的優(yōu)化時(shí)，要檢查變量是否有常數(shù)值，這時(shí)要使用符號(hào)表的數(shù)值（VAL）欄進(jìn)行判斷。目標(biāo)代碼生成階段：在此過(guò)程中主要是查找符號(hào)表，為最終生成目標(biāo)代碼提供必要的信息，如建立DAG節(jié)點(diǎn)標(biāo)記時(shí)使用符號(hào)表暫存變量的引用活躍信息。第123頁(yè)/共431頁(yè)4）符號(hào)表的內(nèi)容符號(hào)表中包括名字（NAME）、類(lèi)型（TYPE）、種屬（KIND）、數(shù)值（VAL）和地址（ADDR）等欄，還帶有一個(gè)字符串表。其中名字欄包括兩個(gè)子欄，一個(gè)用于存放標(biāo)識(shí)符在字符串表中的起始位置，另一個(gè)存放該標(biāo)識(shí)符的長(zhǎng)度；類(lèi)型欄表示該標(biāo)識(shí)符的類(lèi)型（整、實(shí)、布爾和字符型四者之一）；種屬欄表示該標(biāo)識(shí)符屬于哪一種類(lèi)的名字（簡(jiǎn)單變量、常數(shù)名、數(shù)組名、過(guò)程名等）；數(shù)值欄存放常數(shù)標(biāo)識(shí)符的值；地址欄存放分配給該符號(hào)的地址。第124頁(yè)/共431頁(yè)5）一種符號(hào)表的數(shù)據(jù)結(jié)構(gòu)第125頁(yè)/共431頁(yè)6）輸入緩沖工作區(qū)(token)單詞開(kāi)始指針掃描指針正拼單詞第126頁(yè)/共431頁(yè)每次移動(dòng)向前指針都需要做兩次測(cè)試雙緩沖區(qū)問(wèn)題__超前掃描導(dǎo)致的效率問(wèn)題？如何設(shè)計(jì)和實(shí)現(xiàn)掃描器大小問(wèn)題128Byte*2|1024Byte*2|4096Byte*2if

forward在緩沖區(qū)第一部分末尾

thenbegin重裝緩沖區(qū)第二部分;forward:=forward+1endelseifforward在緩沖區(qū)第二部分末尾

thenbegin

重裝緩沖區(qū)第一部分;

將forward移到緩沖區(qū)第一部分開(kāi)始endelseforward:=forward+1;

forward:=forward+1;ifforward↑=eofthenbeginif

forward在第一部分末尾

thenbegin

重裝第二部分;

forward:=forward+1endelseifforward在第二部分末尾

thenbegin

重裝第一部分;

將forward

移到第一部分開(kāi)始endelse/*eof

在表示輸入結(jié)束*/

終止詞法分析end

6）輸入緩沖（1）第127頁(yè)/共431頁(yè)3.2詞法單元的識(shí)別詞法分析器要求能夠檢查輸入字符串，在前綴中找出和某個(gè)模式匹配的詞素。通過(guò)正則定義來(lái)描述各種詞法單元的模式。第128頁(yè)/共431頁(yè)1）正則表達(dá)式——RE設(shè)∑是一個(gè)字母表，⑴Φ是∑上的RE，L(Φ)=Φ；⑵ε是∑上的RE，L(ε)={ε}；⑶對(duì)于a∈∑，a是RE，L(a)={a}；⑷如果r和s是RE，L(r)=R,L(s)=S，則：

r與s的“和”(r|s)是RE，L(r|s)=R∪S； r與s的“乘積”(rs)是RE，L(rs)=RS； r的克林閉包(r*)是RE，L(r*)=R*。⑸只有滿足⑴、⑵、⑶、⑷的才是RE。第129頁(yè)/共431頁(yè)2）正則定義的例子C語(yǔ)言標(biāo)識(shí)符的正則定義letter_

A|B|…|Z|a|b|…|z|_digit0|1|…|9idletter_(letter_|digit)*id對(duì)應(yīng)的正則表達(dá)式為(A|B|…|Z|a|b|…|z|_)((A|B|…|Z|a|b|…|z|_)|(0|1|…|9))*第130頁(yè)/共431頁(yè)3）正則表達(dá)式的擴(kuò)展基本運(yùn)算符：并、連接、Kleen閉包擴(kuò)展的運(yùn)算符：一個(gè)或多個(gè)實(shí)例：?jiǎn)文亢缶Y+r+等價(jià)于rr*零個(gè)或一個(gè)實(shí)例：？r?等價(jià)于ε|r字符類(lèi)[a1a2…an]等價(jià)于a1|a2|…|an[a-e]等價(jià)于a|b|c|d|e用來(lái)使得正則表達(dá)式更加簡(jiǎn)潔，但是不會(huì)使得正則表達(dá)式能夠描述更多的語(yǔ)言。第131頁(yè)/共431頁(yè)4）運(yùn)算的優(yōu)先級(jí)運(yùn)算優(yōu)先級(jí)和結(jié)合性:*高于“連接”和|，“連接”高于||具有交換律、結(jié)合律“連接” 具有結(jié)合律、和對(duì)|的分配律()指定優(yōu)先關(guān)系意義清楚時(shí)，括號(hào)可以省略例：L(a(a|b)*(ε|((.|_)(a|b)(a|b)*))){a}{a,b}*({ε}∪{.,_}{a,b}{a,b}*)第132頁(yè)/共431頁(yè)第133頁(yè)/共431頁(yè)5）狀態(tài)轉(zhuǎn)換圖狀態(tài)轉(zhuǎn)換圖是詞法分析器的重要組件之一狀態(tài)轉(zhuǎn)換圖(transitiondiagram)狀態(tài)(state)：表示了可能在識(shí)別詞素的過(guò)程中可能出現(xiàn)的情況狀態(tài)看作是已處理部分的總結(jié)。某些狀態(tài)為接受狀態(tài)或最終狀態(tài)，表明已經(jīng)找到詞素。加上*的接受狀態(tài)表示最后讀入的符號(hào)不在詞素中。開(kāi)始狀態(tài)（初始狀態(tài)）：用start邊表示。邊(edge)：從一個(gè)狀態(tài)指向另一個(gè)狀態(tài)；邊的標(biāo)號(hào)是一個(gè)或者多個(gè)符號(hào)。如果當(dāng)前符號(hào)為s，下一個(gè)輸入符號(hào)為a，就沿著從s離開(kāi)，標(biāo)號(hào)為a的邊到達(dá)下一個(gè)狀態(tài)。第134頁(yè)/共431頁(yè)狀態(tài)轉(zhuǎn)換圖的例子第135頁(yè)/共431頁(yè)6）保留字和標(biāo)識(shí)符的識(shí)別在很多程序設(shè)計(jì)語(yǔ)言中，保留字也符合標(biāo)識(shí)符的模式，識(shí)別標(biāo)識(shí)符的狀態(tài)轉(zhuǎn)換圖也會(huì)識(shí)別保留字。解決方法在符號(hào)表中預(yù)先填寫(xiě)保留字，并指明它們不是普通標(biāo)識(shí)符。為關(guān)鍵字/保留字建立單獨(dú)的狀態(tài)轉(zhuǎn)換圖。并設(shè)定保留字的優(yōu)先級(jí)高于標(biāo)識(shí)符。第136頁(yè)/共431頁(yè)3.3詞法分析器的設(shè)計(jì)和實(shí)現(xiàn)從轉(zhuǎn)換圖構(gòu)造詞法分析器的方法變量state記錄當(dāng)前狀態(tài)一個(gè)switch根據(jù)state的值轉(zhuǎn)到相應(yīng)的代碼每個(gè)狀態(tài)對(duì)應(yīng)于一段代碼。這段代碼根據(jù)讀入的符號(hào)，確定下一個(gè)狀態(tài)如果找不到相應(yīng)的邊，則調(diào)用fail()進(jìn)行錯(cuò)誤恢復(fù)進(jìn)入某個(gè)接受狀態(tài)時(shí)，返回相應(yīng)的詞法單元。注意狀態(tài)有*標(biāo)記時(shí)，需要回退forward指針。第137頁(yè)/共431頁(yè)狀態(tài)轉(zhuǎn)換圖的例子第138頁(yè)/共431頁(yè)Relop對(duì)應(yīng)的代碼概要第139頁(yè)/共431頁(yè)處理多個(gè)模式的方法詞法分析器需要匹配多個(gè)模式解決方法順序地嘗試各個(gè)詞法單元對(duì)應(yīng)的狀態(tài)轉(zhuǎn)換圖。如果引發(fā)fail()，回退并啟動(dòng)下一個(gè)狀態(tài)圖?？梢愿鶕?jù)優(yōu)先級(jí)確定嘗試順序?！安⑿械亍边\(yùn)行各個(gè)狀態(tài)轉(zhuǎn)換圖。通過(guò)greedy策略，識(shí)別最長(zhǎng)的和某個(gè)模式匹配的輸入前綴預(yù)先把各個(gè)狀態(tài)轉(zhuǎn)換圖合成一個(gè)狀態(tài)轉(zhuǎn)換圖，然后運(yùn)行這個(gè)狀態(tài)轉(zhuǎn)換圖。第140頁(yè)/共431頁(yè)3.4有窮自動(dòng)機(jī)FA本質(zhì)上和狀態(tài)轉(zhuǎn)換圖類(lèi)似，分為兩類(lèi)：不確定的有窮自動(dòng)機(jī)（NondeterministicFiniteAutomata,NFA）邊上的標(biāo)號(hào)沒(méi)有限制，一個(gè)符號(hào)可出現(xiàn)在離開(kāi)同一個(gè)狀態(tài)的多條邊上，ε可以做標(biāo)號(hào)確定的有窮自動(dòng)機(jī)（DeterministicFiniteAutomata,DFA）對(duì)于每個(gè)狀態(tài)以及每個(gè)符號(hào)，有且只有一條邊。兩種自動(dòng)機(jī)都識(shí)別正則語(yǔ)言第141頁(yè)/共431頁(yè)1）不確定的有窮自動(dòng)機(jī)NFA由以下幾部分組成一個(gè)有窮的狀態(tài)集合S一個(gè)輸入符號(hào)集合Σ（inputalphabet）轉(zhuǎn)換函數(shù)（transitionfunction）對(duì)于每個(gè)狀態(tài)和Σ

U{ε}中的符號(hào)，給出相應(yīng)的后繼狀態(tài)集合一個(gè)狀態(tài)s0被指定為開(kāi)始狀態(tài)/初始狀態(tài)（有些定義中可以有多個(gè)開(kāi)始狀態(tài)）S的一個(gè)子集被指定為接受狀態(tài)第142頁(yè)/共431頁(yè)2）NFA的例子狀態(tài)集合S={0,1,2,3}開(kāi)始狀態(tài)0接受狀態(tài)集合{3}轉(zhuǎn)換函數(shù)：(0,a){0,1}(0,b){0}(1,b)2(2,b)3相應(yīng)的圖形表示第143頁(yè)/共431頁(yè)3）輸入字符串的接受一個(gè)NFA接受輸入字符串x，當(dāng)且僅當(dāng)對(duì)應(yīng)的轉(zhuǎn)換圖中存在一條從開(kāi)始狀態(tài)到某個(gè)接受狀態(tài)的路徑，該路徑中各條邊上的標(biāo)號(hào)組成x（ε標(biāo)號(hào)不考慮）。前面的NFA接受aabb，因?yàn)椋篘FA接受的語(yǔ)言：從開(kāi)始狀態(tài)到達(dá)接受狀態(tài)的所有路徑上的標(biāo)號(hào)串的集合。就是它接受的所有符號(hào)串的集合第144頁(yè)/共431頁(yè)4）確定有窮自動(dòng)機(jī)一個(gè)NFA被稱(chēng)為DFA，如果沒(méi)有ε之上的轉(zhuǎn)換動(dòng)作對(duì)于每個(gè)狀態(tài)s和每個(gè)輸入符號(hào)，有且僅有一條標(biāo)號(hào)為a的離開(kāi)s的邊可以高效判斷一個(gè)串能否被一個(gè)DFA接受。每個(gè)NFA都有一個(gè)等價(jià)的DFA。即它們接受同樣的語(yǔ)言。第145頁(yè)/共431頁(yè)5）從正則表達(dá)式到自動(dòng)機(jī)的轉(zhuǎn)換正則表達(dá)式可以簡(jiǎn)潔、精確地描述詞法單元的模式但是在進(jìn)行模式匹配時(shí)需要模擬DFA的執(zhí)行。因此，需要將正則表達(dá)式轉(zhuǎn)換為DFA步驟：正則表達(dá)式到NFANFA到DFA第146頁(yè)/共431頁(yè)6）正則表達(dá)式到NFA基本思想根據(jù)正則表達(dá)式的遞歸定義，按照正則表達(dá)式的結(jié)構(gòu)遞歸地構(gòu)造出相應(yīng)的NFA。算法分成兩個(gè)部分：基本規(guī)則處理ε和單符號(hào)的情況對(duì)于每個(gè)正則表達(dá)式的運(yùn)算，建立組合組合相應(yīng)NFA的方法。第147頁(yè)/共431頁(yè)轉(zhuǎn)換算法（1）基本規(guī)則部分表達(dá)式ε表達(dá)式a第148頁(yè)/共431頁(yè)歸納部分s|rsr轉(zhuǎn)換算法（2）第149頁(yè)/共431頁(yè)歸納部分s*轉(zhuǎn)換算法（3）第150頁(yè)/共431頁(yè)7）轉(zhuǎn)換得到的NFA的特性狀態(tài)數(shù)量最多為r中的運(yùn)算符和運(yùn)算符分量總數(shù)的兩倍因?yàn)槊總€(gè)步驟只引入兩個(gè)狀態(tài)有且只有一個(gè)開(kāi)始狀態(tài)和有關(guān)接受狀態(tài)除接受狀態(tài)之外，每個(gè)狀態(tài)要么由一條標(biāo)號(hào)不等于ε的出邊，要么有兩條標(biāo)號(hào)為ε的出邊。第151頁(yè)/共431頁(yè)正則表達(dá)式到NFA的例子（1）正則表達(dá)式(a|b)*abb第一個(gè)a對(duì)應(yīng)的NFA第一個(gè)b對(duì)應(yīng)的NFA第152頁(yè)/共431頁(yè)(a|b)的NFA第二個(gè)a的NFA正則表達(dá)式到NFA的例子（2）第153頁(yè)/共431頁(yè)(a|b)*的NFA正則表達(dá)式到NFA的例子（3）第154頁(yè)/共431頁(yè)8）NFA合并的方法合并方法：引入新的開(kāi)始狀態(tài)，并引入從這個(gè)開(kāi)始狀態(tài)到各個(gè)原開(kāi)始狀態(tài)的ε轉(zhuǎn)換。第155頁(yè)/共431頁(yè)詞法分析程序的設(shè)計(jì)與實(shí)現(xiàn)狀態(tài)轉(zhuǎn)移圖——教材P