編譯原理課件

第1章引論1.1電腦語(yǔ)言的發(fā)展1.2翻譯系統(tǒng)1.3編譯系統(tǒng)的功能分析1.4編譯程序總體結(jié)構(gòu)1.5編譯程序的生成1.6編譯技術(shù)的應(yīng)用1.1電腦語(yǔ)言的發(fā)展機(jī)器語(yǔ)言(MachineLanguage)組合語(yǔ)言(AssembleLanguage)0、1代碼與助記符：更接近於電腦硬體指令系統(tǒng)的工作高級(jí)語(yǔ)言(HighLevelLanguage)定義數(shù)據(jù)、描述演算法（程式）如：C、FORTRAN、PASCAL、C++、JAVA、SQL(數(shù)據(jù)定義、數(shù)據(jù)操作)命令語(yǔ)言(Command)以功能封裝為特徵高級(jí)語(yǔ)言的分類強(qiáng)制式語(yǔ)言(ImperativeLanguage)FORTRAN(段結(jié)構(gòu))、BASIC、Pascal(嵌套結(jié)構(gòu))、C……函數(shù)(應(yīng)用)式語(yǔ)言(FunctionalLanguage)LISP、ML……邏輯式(基於規(guī)則)語(yǔ)言(LogicalLanguage)Prolog……面向?qū)ο笳Z(yǔ)言(Object-OrientedLanguage)Smalltalk、C++、Java、Ada(程式包)……1.2翻譯系統(tǒng)翻譯程式(Translator)將某一種語(yǔ)言描述的程式(根源程式——SourceProgram)翻譯成等價(jià)的另一種語(yǔ)言描述的程式(目標(biāo)程式——ObjectProgram)的程式。翻譯程式根源程式目標(biāo)程式(*.C/*.PAS/*.AS)(*.OBJ/*.EXE/*.*)1.2翻譯系統(tǒng)解釋程式(Interpreter)口譯與筆譯（單句提交與整篇提交）根源程式輸入數(shù)據(jù)計(jì)算結(jié)果解釋程式1.2翻譯系統(tǒng)編譯程序(Compiler)高級(jí)語(yǔ)言程式→彙編/機(jī)器語(yǔ)言程式根源程式目標(biāo)程式編譯程序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ù)等1.2翻譯系統(tǒng)其他：診斷編譯程序（DiagnosticCompiler)優(yōu)化編譯程序（OptimizingCompiler)交叉編譯程序（CrossCompiler)可變目標(biāo)編譯程序（RetargetableCompiler)並行編譯程序（ParallelizingCompiler）組合語(yǔ)言程式(Assembler)、交叉組合語(yǔ)言程式(CrossAssembler)、反組合語(yǔ)言程式（Disassembler)1.2翻譯系統(tǒng)—匯總ML MLP Assembler DisassemblerAL ALP Compiler DataHL HLP Interpreter ResultM-MachineL-LangugeP-ProgramA-AssembleH-HighLevelTranslator1.3編譯系統(tǒng)的功能分析程式分析詞法、語(yǔ)法、語(yǔ)義分析綜合語(yǔ)句的翻譯、代碼生成例如：識(shí)別字左值與右值的綁定(binding)變數(shù)：存儲(chǔ)單元函數(shù)：目標(biāo)代碼序列1.4編譯程序總體結(jié)構(gòu)請(qǐng)參閱P5圖1.1

目標(biāo)代碼生成器代碼優(yōu)化器語(yǔ)義分析與中間代碼生成器語(yǔ)法分析器表格管理出錯(cuò)處理中間代碼中間代碼目標(biāo)代碼語(yǔ)法單位單詞符號(hào)詞法分析器根源程式1.詞法分析例：res=fact*(term1+term2);結(jié)果IDN res‘=’IDNfact‘*’‘(’IDN term1‘+’IDNterm2‘)’‘;’1、詞法分析詞法分析器(LexicalAnalyzer)又叫做掃描器(Scanner)，完成詞法分析功能：詞法分析器從左到右掃描根源程式（字串），並將其轉(zhuǎn)換成單詞(記號(hào)—Token)串；同時(shí)查詞法錯(cuò)誤，進(jìn)行識(shí)別字登記——符號(hào)表管理。輸入：字串 輸出：(種別碼，屬性值)——序?qū)傩灾怠猼oken的機(jī)內(nèi)表示2、語(yǔ)法分析語(yǔ)法分析器(SyntaxAnalyzer，又叫Parser)完成語(yǔ)法分析功能：Parser實(shí)現(xiàn)“組詞成句”，構(gòu)造分析樹，指出語(yǔ)法錯(cuò)誤，指導(dǎo)翻譯輸入：Token序列輸出：語(yǔ)法成分2.語(yǔ)法分析res=fact*(term1+term2); 字串*；賦值語(yǔ)句運(yùn)算式=）（fact運(yùn)算式res運(yùn)算式運(yùn)算式運(yùn)算式運(yùn)算式+term1term23.語(yǔ)義分析功能：分析由語(yǔ)法分析器給出的語(yǔ)法單位的語(yǔ)義獲取識(shí)別字的屬性：類型、作用域等語(yǔ)義檢查：運(yùn)算的合法性、取值範(fàn)圍等副程式的靜態(tài)綁定：代碼的相對(duì)地址變數(shù)的靜態(tài)綁定：數(shù)據(jù)的相對(duì)地址4.中間代碼生成中間代碼(intermediateCode)例:id1+id2*id3尾碼表示(逆波蘭ReversePolishNotation)id1id2id3*

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

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

EE+Eid1E*Eid2id3語(yǔ)法樹波蘭表示問題——Lukasiewicz1929/1951年發(fā)明

中綴表示(Infixnotation):(a+①b)*(-c+②d)+③e/f波蘭表示（Polish/Prefix/Parenthesis-free/Lukasiewicznotation）——也就是首碼表示+③*+①ab+②@cd/ef運(yùn)算順序從右向左逆波蘭表示(ReversePolish/Suffix/Postfixnotation)——也就是尾碼表示

ab+①c@d+②*ef/+③運(yùn)算順序從左向右4.中間代碼生成中間代碼的特點(diǎn)簡(jiǎn)單規(guī)範(fàn)機(jī)器無關(guān)易於優(yōu)化與轉(zhuǎn)換三地址碼的另一種表示形式T1=id2*id3T2=id1*T1其他類型的語(yǔ)句舉例

printf(“hello”)x:=s （賦值）paramx （參數(shù)）callf （函數(shù)調(diào)用）s是hello的地址f是函數(shù)printf的地址對(duì)中間代碼的優(yōu)化處理:對(duì)代碼進(jìn)行等價(jià)變換以求提高執(zhí)行效率——提高運(yùn)行速度和節(jié)省存儲(chǔ)空間與機(jī)器無關(guān)的優(yōu)化與機(jī)器有關(guān)的優(yōu)化5.代碼優(yōu)化與機(jī)器無關(guān)的優(yōu)化局部?jī)?yōu)化常量合併：常數(shù)運(yùn)算在編譯期間完成，如8+9*4公共子運(yùn)算式的提取:基本塊內(nèi)迴圈優(yōu)化強(qiáng)度削減代碼外提與機(jī)器有關(guān)的優(yōu)化寄存器的利用將常用量放入寄存器，以減少訪問記憶體的次數(shù)體系結(jié)構(gòu)MIMD、SIMD、SPMD、向量機(jī)、流水機(jī)存儲(chǔ)策略根據(jù)演算法訪存的要求安排：Cache、並行存儲(chǔ)體系——減少訪問衝突任務(wù)劃分按運(yùn)行的演算法即體系結(jié)構(gòu)，劃分子任務(wù)(MPMD)6.目標(biāo)代碼生成將中間代碼轉(zhuǎn)換成目標(biāo)機(jī)上的機(jī)器指令代碼或彙編代碼7、表格管理管理各種符號(hào)表（常數(shù)、標(biāo)號(hào)、變數(shù)、過程、結(jié)構(gòu)……），查、填（登記、查找）根源程式中出現(xiàn)的符號(hào)和編譯程序生成的符號(hào)，為編譯的各個(gè)階段提供資訊。輔助語(yǔ)法檢查、語(yǔ)義檢查完成靜態(tài)綁定、管理編譯過程Hash表、鏈表等各種查、填表技術(shù)8、錯(cuò)誤處理進(jìn)行各種錯(cuò)誤的檢查、報(bào)告、糾正，以及相應(yīng)的續(xù)編譯處理（如：錯(cuò)誤的定位與局部化）詞法：拼寫……語(yǔ)法：語(yǔ)句結(jié)構(gòu)、運(yùn)算式結(jié)構(gòu)……語(yǔ)義：類型不匹配……模組分類分析：詞法分析、語(yǔ)法分析、語(yǔ)義分析綜合：中間代碼生成、代碼優(yōu)化、目標(biāo)代碼生成輔助：符號(hào)表管理、出錯(cuò)處理8項(xiàng)功能對(duì)應(yīng)8個(gè)模組編譯程序總體結(jié)構(gòu)中間代碼目標(biāo)代碼生成器代碼優(yōu)化器語(yǔ)義分析與中間代碼生成器語(yǔ)法分析器表格管理出錯(cuò)處理中間代碼目標(biāo)代碼語(yǔ)法單位單詞符號(hào)詞法分析器根源程式例一個(gè)語(yǔ)句的翻譯9編譯的遍（Pass）根據(jù)系統(tǒng)資源的狀況、運(yùn)行目標(biāo)的要求……等，可以將一個(gè)編譯程序設(shè)計(jì)成多遍掃描的形式，在每一遍掃描中，完成不同的任務(wù)。遍可以和階段相對(duì)應(yīng)，也可無關(guān)單遍代碼不太有效10、編譯的前端與後端前端與源語(yǔ)言有關(guān)、與目標(biāo)機(jī)無關(guān)的部分詞法分析、語(yǔ)法分析、語(yǔ)義分析與中間代碼生成、與機(jī)器無關(guān)的代碼優(yōu)化後端與目標(biāo)機(jī)有關(guān)的部分與機(jī)器有關(guān)的代碼優(yōu)化、目標(biāo)代碼生成1.5編譯程序的生成設(shè)計(jì)目標(biāo)目標(biāo)程式小，執(zhí)行速度快。編譯程序小，執(zhí)行速度快。診斷能力強(qiáng)，可靠性高?？梢浦残裕蓴U(kuò)充性。如何實(shí)現(xiàn)編譯器？直接用可運(yùn)行的代碼編制——太費(fèi)力?。孕螆D表示語(yǔ)言翻譯的Ｔ形圖源語(yǔ)言表示語(yǔ)言目標(biāo)語(yǔ)言功能1）交叉編譯(CrossCompiling)/移植問題一：A機(jī)上有一個(gè)C語(yǔ)言編譯器，是否可利用此編譯器實(shí)現(xiàn)B機(jī)上的C語(yǔ)言編譯器？條件：Ａ機(jī)有Ｃ語(yǔ)言的編譯程序目的：實(shí)現(xiàn)Ｂ機(jī)的Ｃ語(yǔ)言的編譯1.

(人)用Ｃ語(yǔ)言編制B機(jī)的Ｃ編譯程序P0(C→B)(Ａ機(jī)的C編譯P1)編譯P0，得到在A機(jī)上可運(yùn)行的P2(C→B)Ｃ語(yǔ)言Ｃ語(yǔ)言Ｂ機(jī)器Ｃ語(yǔ)言Ａ機(jī)器A機(jī)器Ｃ語(yǔ)言A機(jī)器Ｂ機(jī)器P0P1P2上次課主要內(nèi)容基本概念翻譯程式、編譯程序、解釋程式、編譯系統(tǒng)組合語(yǔ)言程式、其他編譯的掃描遍數(shù)、前端、後端編譯程序總體結(jié)構(gòu)中間代碼目標(biāo)代碼生成器代碼優(yōu)化器語(yǔ)義分析與中間代碼生成器語(yǔ)法分析器表格管理出錯(cuò)處理中間代碼目標(biāo)代碼語(yǔ)法單位單詞符號(hào)詞法分析器根源程式上次課主要內(nèi)容T形圖移植源語(yǔ)言表示語(yǔ)言目標(biāo)語(yǔ)言3.(Ａ機(jī)的P2)編譯P0，得到在B機(jī)上可運(yùn)行的P3(C→B)Ｃ語(yǔ)言Ｂ機(jī)器Ｂ機(jī)器P3Ｃ語(yǔ)言Ｃ語(yǔ)言Ｂ機(jī)器Ｃ語(yǔ)言Ａ機(jī)器A機(jī)器Ｃ語(yǔ)言A機(jī)器Ｂ機(jī)器P0P1P2P2Ｃ語(yǔ)言Ａ機(jī)器Ｂ機(jī)器Ｃ語(yǔ)言Ｃ語(yǔ)言Ｂ機(jī)器P0獲得一個(gè)工具2)本機(jī)編譯器利用問題二：A機(jī)上有一個(gè)C語(yǔ)言編譯器，現(xiàn)要實(shí)現(xiàn)一個(gè)新語(yǔ)言NEW的編譯器？能利用交叉編譯技術(shù)麼？用C編寫NEW的編譯，並用C編譯器編譯它NEW語(yǔ)言Ｃ語(yǔ)言A機(jī)器Ｃ語(yǔ)言Ａ機(jī)器A機(jī)器NEW語(yǔ)言A機(jī)器A機(jī)器P0(編寫)P1(原有)P2(生成)問題三：直接在一個(gè)機(jī)上實(shí)現(xiàn)C語(yǔ)言編譯器，還有別的技術(shù)麼？解決：用組合語(yǔ)言實(shí)現(xiàn)一個(gè)Ｃ子集的編譯程序(P0—人)用組合語(yǔ)言程式處理該程式,得到P2(P2:可直接運(yùn)行)用Ｃ子集編制Ｃ語(yǔ)言的編譯程序(P3—人)用P2編譯P3，得到P43)編譯程序的自展技術(shù)4.用P2編譯P3，得到P4Ｃ語(yǔ)言機(jī)器語(yǔ)言機(jī)器語(yǔ)言P4Ｃ子集組合語(yǔ)言機(jī)器語(yǔ)言P01.

用組合語(yǔ)言實(shí)現(xiàn)一個(gè)Ｃ子集的編譯程序(P0—人)組合語(yǔ)言機(jī)器語(yǔ)言機(jī)器語(yǔ)言Ｃ子集機(jī)器語(yǔ)言機(jī)器語(yǔ)言P1P22.用組合語(yǔ)言程式(P1)處理該程式,得到P2(P2:可直接運(yùn)行)P2Ｃ子集機(jī)器語(yǔ)言機(jī)器語(yǔ)言獲得一個(gè)工具Ｃ語(yǔ)言Ｃ子集機(jī)器語(yǔ)言P33.用Ｃ子集編制Ｃ語(yǔ)言的編譯程序(P3—人)4)利用編譯程序自動(dòng)生成器詞法分析器的自動(dòng)生成程式詞法規(guī)則說明詞法分析程式(C程式)輸入： 詞法（正規(guī)運(yùn)算式） 識(shí)別動(dòng)作（Ｃ程式段）輸出：

yylex()函數(shù)LEX語(yǔ)法分析器的自動(dòng)生成程式語(yǔ)法規(guī)則說明語(yǔ)法分析程式(C程式)輸入： 語(yǔ)法規(guī)則（產(chǎn)生式） 語(yǔ)義動(dòng)作（Ｃ程式段）輸出：

yyparse()函數(shù)ＹＡＣＣ1.6編譯技術(shù)的應(yīng)用把複雜數(shù)據(jù)看作一條語(yǔ)句數(shù)據(jù)格式的分析利用詞法分析、語(yǔ)法分析方法數(shù)據(jù)處理的框架基於語(yǔ)法制導(dǎo)的語(yǔ)義處理框架編譯技術(shù)可以用於各種複雜數(shù)據(jù)的分析處理例1-1DOS命令date的輸出格式例：9-2-1993、09-03-1993、9-03-93語(yǔ)法date→month-day-year詞法month→DIGITDIGIT|DIGITday→DIGITDIGIT|DIGITyear→DIGITDIGIT|DIGIIDIGITDIGITDIGIT例1-1（續(xù)）語(yǔ)義year(年)、month(月)、day(日)語(yǔ)義約束條件0<month.value<130<day.value<32，31，300<year.value<10000習(xí)題1.試分析一個(gè)簡(jiǎn)短的C程式，找出幾個(gè)屬於語(yǔ)法、詞法、語(yǔ)義的語(yǔ)言現(xiàn)象。2.試分析例1-1的date輸出數(shù)據(jù)的處理中，應(yīng)該做哪些詞法分析、語(yǔ)法分析、語(yǔ)義處理。3.理解交叉編譯/移植和自展技術(shù)第2章高級(jí)語(yǔ)言

及其文法2.1語(yǔ)言概述什麼是語(yǔ)言自然語(yǔ)言(NaturalLanguage)是人與人的通訊工具語(yǔ)義(Semantics):環(huán)境、背景知識(shí)、語(yǔ)氣、二義性——難以形式化電腦語(yǔ)言(ComputerLanguage)電腦系統(tǒng)間、人機(jī)間通訊工具嚴(yán)格的語(yǔ)法(Grammar)、語(yǔ)義(Semantics)——易於形式化：嚴(yán)格語(yǔ)言是用來交換資訊的工具——功能性描述2.1語(yǔ)言概述語(yǔ)言的描述方法——現(xiàn)狀自然語(yǔ)言：自然、方便-非形式化數(shù)學(xué)語(yǔ)言（符號(hào)）：嚴(yán)格、準(zhǔn)確-形式化形式化描述高度的抽象，嚴(yán)格的理論基礎(chǔ)和方便的電腦表示。2.1語(yǔ)言概述語(yǔ)言——形式化的內(nèi)容提取單詞(Token)：滿足一定規(guī)則字元(Character)串句子(Sentence)：滿足一定規(guī)則單詞序列語(yǔ)言(Language)：滿足一定條件的句子集合語(yǔ)言是字和組合字的規(guī)則——結(jié)構(gòu)性描述例：一譯開天第課今始編節(jié)上今天開始上第一節(jié)編譯課2.1語(yǔ)言概述程式設(shè)計(jì)語(yǔ)言——形式化的內(nèi)容提取程式設(shè)計(jì)語(yǔ)言(ProgrammingLanguage)：組成程式的所有語(yǔ)句的集合程式(Program)：滿足語(yǔ)法規(guī)則的語(yǔ)句序列語(yǔ)句(Sentence)：滿足語(yǔ)法規(guī)則的單詞序列單詞(Token)：滿足詞法規(guī)則的字串例變數(shù)=運(yùn)算式if條件then語(yǔ)句while條件do語(yǔ)句call過程名(參數(shù)表)2.1語(yǔ)言概述描述形式——文法語(yǔ)法——語(yǔ)句語(yǔ)句的組成規(guī)則描述方法：BNF範(fàn)式、語(yǔ)法(描述)圖詞法——單詞單詞的組成規(guī)則描述方法：BNF範(fàn)式、正規(guī)式2.2基本定義字母表（Alphabet）是一個(gè)非空有窮集合，字母表中的元素稱為該字母表的一個(gè)字母（Letter），也叫字元（Character）。例以下是不同的字母表： ⑴{a，b，c，d} ⑵{a，b，c，……，z} ⑶{0，1}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)所組成的的任何有窮序列被稱之為該字母表上的符號(hào)串,也稱作“字”(Word)。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}2.2基本定義定義3設(shè)∑是一個(gè)字母表，∑的正閉包(PositiveClosure)：∑+=∑∪∑2∪∑3∪∑4∪……∑的克林閉包(KleeneClosure)：∑*=∑0∪∑+=∑0∪∑∪∑2∪∑3∪……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……}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，…}2.2基本定義定義5設(shè)∑是一個(gè)字母表，

L

∑*，L稱為字母表∑上的一個(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}*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。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;

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

句子

→

主語(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終結(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ǔ)

，……}開始符號(hào)S=

句子

句子的語(yǔ)法組成

——終結(jié)符號(hào)集，非終結(jié)符號(hào)集，語(yǔ)法規(guī)則，開始符號(hào)文法G的形式定義文法G為一個(gè)四元組:

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

句子

主語(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ī)則

句子

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

thegraywolfwilleatthegoat還可以“得出”其他的句子例2-1算術(shù)運(yùn)算式的文法考慮簡(jiǎn)單算術(shù)運(yùn)算式組成的語(yǔ)言遞歸定義——中綴表示識(shí)別字(id)（常數(shù)、變數(shù)）是運(yùn)算式；運(yùn)算式加一個(gè)運(yùn)算式是運(yùn)算式；運(yùn)算式減一個(gè)運(yùn)算式是運(yùn)算式；運(yùn)算式乘一個(gè)運(yùn)算式是運(yùn)算式；運(yùn)算式除一個(gè)運(yùn)算式是運(yùn)算式；運(yùn)算式加上括弧後是運(yùn)算式。上次課主要內(nèi)容編譯程序?qū)崿F(xiàn)技術(shù)自展自動(dòng)生成：lex、Yacc語(yǔ)言資訊交流的工具字和組合字的規(guī)則的統(tǒng)一體字母表上的語(yǔ)言字母表∑+

、∑*、a∈∑，x∈∑*、L

∑*、x∈L首碼、尾碼、子串、串長(zhǎng)、串的連接、串的冪上次課主要內(nèi)容文法通過刻畫語(yǔ)言的結(jié)構(gòu)描述語(yǔ)言用有窮描述無窮Ｇ=(ＶT，ＶN，Ｐ，Ｓ)運(yùn)算式的遞歸定義例2-1算術(shù)運(yùn)算式的文法考慮用式子表示這個(gè)定義識(shí)別字(id)是運(yùn)算式運(yùn)算式加一個(gè)運(yùn)算式是運(yùn)算式E→idE→E+E運(yùn)算式減一個(gè)運(yùn)算式是運(yùn)算式E→E-E運(yùn)算式乘一個(gè)運(yùn)算式是運(yùn)算式E→E*E運(yùn)算式除一個(gè)運(yùn)算式是運(yùn)算式E→E/E運(yùn)算式加上括弧後是運(yùn)算式E→(E)例2-1算術(shù)運(yùn)算式的文法P:E→E+EE→E-EE→E*EE→E/EE→(E)E→idG=（{id，+，-，*，/，(，)}，{E}，P，E）約定：只寫產(chǎn)生式簡(jiǎn)寫E→E+E|E*E|(E)|id產(chǎn)生式的簡(jiǎn)寫對(duì)一組有相同左部的產(chǎn)生式α→β1，α→β2…，α→βn可以簡(jiǎn)單地記為：α→β1|β2|…|βn讀作：α定義為或者β1，或者β2，…，或者βn。並且稱它們?yōu)棣廉a(chǎn)生式。β1，β2，…，βn稱為候選式(Candidate)。產(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也就是說，根據(jù)第4個(gè)候選式，E*E+E經(jīng)3步變換變成id*id+id1E→E+E2E→E*E3E→(E)4E→id5E→E-E6E→E/E文法使用舉例E

E+E （1）

id+E （4）

id+E*E （2）

id+id*E （4）

id+id*id （4）E

5id+id*id1E→E+E2E→E*E3E→(E)4E→id5E→E-E6E→E/E直接推導(dǎo)與歸約根據(jù)產(chǎn)生式對(duì)符號(hào)串進(jìn)行變換的過程Ａ→γ是文法Ｇ的一個(gè)產(chǎn)生式，且α、β∈（ＶT∪ＶN）*，稱αＡβ的直接推導(dǎo)/派生(Derive)出αγβ，也稱αγβ直接歸約(Reduce)為αＡβ。記為αＡβ

αγβ例：id+E

id+E*E（多步）推導(dǎo)α0

α1

α2

…

αn記為α0

nαn

(恰用n步)α0

+αn

（至少一步）

α0

*αn

（若干步:零步或多步）推導(dǎo)/歸約舉例E

E+E （1）串中含有變數(shù)

id+E （4）串中含有變數(shù)

id+E*E （2）串中含有變數(shù)

id+id*E （4）串中含有變數(shù)

id+id*id （4）串中沒有變數(shù)到此串中已經(jīng)沒有（語(yǔ)法）變數(shù)了，不能再推了——得到句子1E→E+E2E→E*E3E→(E)4E→id句型與句子E

5id+id*id定義:如果S

*x，且x∈ＶT*，則稱x是G產(chǎn)生的一個(gè)句子(Sentence)E

E+E

E+E*EE

4id+id*E定義:如果S

*α，α∈(ＶT∪ＶN)*則稱α是G產(chǎn)生的一個(gè)句型(SententialForm)文法G產(chǎn)生的語(yǔ)言定義： L(G)={x|S

*xandx∈VT*}文法E→E+E|E*E|(E)|id可以派生出多少個(gè)句子？文法G的作用——語(yǔ)言的有窮描述以有限的規(guī)則描述無限的語(yǔ)言現(xiàn)象有限:產(chǎn)生式集合、終結(jié)符集合、非終結(jié)符集合無限：可以導(dǎo)出無窮多個(gè)句子（注：L也可是有窮）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施於最右變數(shù)右句型/規(guī)範(fàn)句型 (canonical~)(最左/規(guī)範(fàn)歸約)E

+

id+id*id施於最左變數(shù)左句型(left-~)（最右歸約）

E

5

id+id*id最左推導(dǎo)與最右推導(dǎo)最左推導(dǎo)(Left-mostDerivation)每次推導(dǎo)都施加在句型的最左邊的語(yǔ)法變數(shù)上?！c最右歸約對(duì)應(yīng)最右推導(dǎo)(Right-mostDerivation)每次推導(dǎo)都施加在句型的最右邊的語(yǔ)法變數(shù)上?！c最左歸約（規(guī)範(fàn)規(guī)約）對(duì)應(yīng)的規(guī)範(fàn)(Canonical)句型短語(yǔ)(Phrase)自然語(yǔ)言中什麼叫短語(yǔ)？如果Ｓ

*

αＡβ&A

+γ，則稱γ是句型αγβ的相對(duì)於變數(shù)A的短語(yǔ)如果Ｓ

*

αＡβ&A

γ，則稱γ是句型αγβ的相對(duì)於變數(shù)A的直接短語(yǔ)最左直接短語(yǔ)叫做句柄(Handle)例：(直接)短語(yǔ)E

E+T

T+T

F+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句柄(Handle)：最左直接短語(yǔ)E→E+T|TT→T*F|FF→(E)|idE

E+T

T+T

F+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例2-2識(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ù)的文法2.４文法的分類(Chomsky體系)語(yǔ)言結(jié)構(gòu)的複雜程度（形式語(yǔ)言）涉及文法的複雜程度、分析方法的選擇如果G滿足文法定義的要求，則Ｇ是０型文法（短語(yǔ)結(jié)構(gòu)文法PSG:PhraseStructureGrammar）。L(G)為PSL。上下文有關(guān)文法(CSG)若產(chǎn)生式集合中所有｜α｜≤｜β｜，除Ｓ→ε外，則Ｇ是１型文法即：上下文有關(guān)文法（CSG——ContextSensitiveGrammar）L(G)為1型/上下文有關(guān)/敏感語(yǔ)言(CSL)上下文無關(guān)文法(CFG)若α∈ＶN，β∈(ＶN∪ＶT)*，則Ｇ是２型文法即：上下文無關(guān)文法(CFG:ContextFreeGrammar)L(G)為2型/上下文無關(guān)語(yǔ)言（CFL）例：程式設(shè)計(jì)語(yǔ)言的多數(shù)語(yǔ)法特徵例2-3識(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正規(guī)文法(RG)設(shè)Ａ、Ｂ∈ＶN，ａ∈ＶT或?yàn)?/p>

右線性(RightLinear)文法：Ａ→ａＢ或Ａ→ａ左線性(LeftLinear)文法：Ａ→Ｂａ或Ａ→ａ都是３型文法(正規(guī)文法RegularGrammar-RG)L(G)為3型/正規(guī)集/正則集/正則語(yǔ)言（RL）例：程式設(shè)計(jì)語(yǔ)言的多數(shù)詞法特性左、右線性文法不可混用例非CFL的文法L={anbncn|n>0}的文法S

aBC|aSBCCB

BCaB

abbB

bbbC

bc“可以證明”不存在CFGG,使L(G)=L

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

例L2={anbmcndm|n,m≥0}，它是檢查過程聲明的形參個(gè)數(shù)和過程引用的參數(shù)個(gè)數(shù)是否一致問題的抽象。非CFL結(jié)構(gòu)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)是線性界限自動(dòng)機(jī)(LBA)* α∈ＶN:G是2型文法，L(G)是2型語(yǔ)言;

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

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

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

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

[α]≡α|ε……ＢＮＦ範(fàn)式——BackusNormalForm例簡(jiǎn)單算術(shù)運(yùn)算式(只寫產(chǎn)生式)<簡(jiǎn)單運(yùn)算式>∷＝<簡(jiǎn)單運(yùn)算式>+<簡(jiǎn)單運(yùn)算式><簡(jiǎn)單運(yùn)算式>∷＝<簡(jiǎn)單運(yùn)算式>*<簡(jiǎn)單運(yùn)算式><簡(jiǎn)單運(yùn)算式>∷＝(<簡(jiǎn)單運(yùn)算式>)<簡(jiǎn)單運(yùn)算式>∷＝id即：<簡(jiǎn)單運(yùn)算式>∷＝<簡(jiǎn)單運(yùn)算式>+<簡(jiǎn)單運(yùn)算式>| <簡(jiǎn)單運(yùn)算式>*<簡(jiǎn)單運(yùn)算式>|(<簡(jiǎn)單運(yùn)算式>)|id哪些是終結(jié)符？哪些是變數(shù)？例2-5句子結(jié)構(gòu)的表示

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

）EE+EE→E+EidE→idEE*E→E*EidE→ididE→idE

E+E

id+E

id+E*E

id+id*E

id+id*id一棵樹！上次課主要內(nèi)容產(chǎn)生式的簡(jiǎn)寫：

α→β1|β2|…|βn（候選式）文法的簡(jiǎn)寫：只寫產(chǎn)生式集、開始符約定直接派生/歸約：αＡβ

αγβＡ→γN步派生/歸約：αＡβ

NαγβＡ

Nγ句子與句型：S

*x S

*α語(yǔ)言：L(G)={x|S

*xandx∈VT*}上次課主要內(nèi)容短語(yǔ)：短語(yǔ)、直接短語(yǔ)、句柄Chomsky體系BNF範(fàn)式最左推導(dǎo)（最右歸約）最右推導(dǎo)（最左歸約）規(guī)範(fàn)推導(dǎo)/歸約，規(guī)範(fàn)句型例:(a1+a2)*a3E→E+T|E-T|TT→T*F|T/F|FF→(E)|id2.5CFG的語(yǔ)法樹ParseTree用樹的形式表示句型的結(jié)構(gòu)樹根：開始符號(hào)中間結(jié)點(diǎn)：非終結(jié)符葉結(jié)點(diǎn)：終結(jié)符或者非終結(jié)符每個(gè)推導(dǎo)對(duì)應(yīng)一個(gè)中間結(jié)點(diǎn)及其兒子——一個(gè)二級(jí)子樹-直接短語(yǔ)又稱為語(yǔ)法分析樹例短語(yǔ)與語(yǔ)法(分析)樹

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

）EE+Eid(a1)EE*id(a2)id(a3)短語(yǔ)——一棵子樹的葉子！短語(yǔ)：一棵子樹的所有葉子自左至右排列起來形成一個(gè)相對(duì)於子樹根的短語(yǔ)。直接短語(yǔ)：僅有父子兩代的一棵子樹，它的所有葉子自左至右排列起來所形成的符號(hào)串。句柄：一個(gè)句型的分析樹中最左那棵只有父子兩代的子樹的所有葉子的自左至右排列。例如，對(duì)運(yùn)算式文法G[E]和句子a1+a2*a3，挑選出推導(dǎo)過程中產(chǎn)生的句型中的短語(yǔ)，直接短語(yǔ)，句柄。用子樹解釋短語(yǔ)，直接短語(yǔ)，句柄E

E+T

T+T

F+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*FFa2a3

a1+a2*a3短語(yǔ)二義性文法與先天二義性語(yǔ)言對(duì)同一句子存在兩棵語(yǔ)法分析樹在理論上不可判定EE*EidEE+ididEE+EEEid*idid

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

2.對(duì)於一個(gè)句子的分析應(yīng)是唯一的?？紤]運(yùn)算式下麵的文法G[E],其產(chǎn)生式如下：

E

E+E

E*E

(E)

id

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

E

E+E

a1+E

a1+E*E

a1+a2*E

a1+a2*a3E

E*E

E+E*E

a1+E*E

a1+a2*E

a1+a2*a3文法的二義性

E

E+E

a1+E

a1+E*E

a1+a2*E

a1+a2*a3

E

E*E

E+E*E

a1+E*E

a1+a2*E

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

E

E*E

E*a3

E+E*a3

E+a2*a3

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

E

E+E

a1+E

a1+E*E

a1+a2*E

a1+a2*a3如果一個(gè)文法的句子存在兩棵分析樹,那麼,該句子是二義性的。如果一個(gè)文法包含二義性的句子,則稱這個(gè)文法是二義性的;否則，該文法是無二義性的。幾點(diǎn)說明：1.一般來說，程式語(yǔ)言存在無二義性文法，對(duì)於運(yùn)算式來說，文法（2.1）是無二義性的。對(duì)於條件語(yǔ)句，經(jīng)常使用二義性文法描述它：S

ifexprthenS

ifexprthenSelseS

other二義性的句子:ife1thenife2thens1elses2

二義性（歧義性,ambiquity)2.對(duì)於任意一個(gè)上下文無關(guān)文法，不存在一個(gè)演算法，判定它是無二義性的；但能給出一組充分條件，滿足這組充分條件的文法是無二義性的。3.存在先天二義性語(yǔ)言。例如，

aibicj

i,j

1

aibjcj

i,j

1

存在一個(gè)二義性的句子akbkck4.在能駕馭的情況下，使用二義性文法——簡(jiǎn)單二義性（歧義性，ambiquity)E→E+T|E-T|TT→T*F|T/F|FF→(E)|id參考書：(抽象)語(yǔ)法樹不同(語(yǔ)法)分析樹EE+idE+EEidid(抽象)語(yǔ)法樹+id+idid2.6文法的構(gòu)造——為了更好地理解文法目的：給出語(yǔ)言的有窮描述途徑：刻畫語(yǔ)言的結(jié)構(gòu)做法：給出定義的形式化描述根據(jù)經(jīng)驗(yàn)給出描述文法舉例{x|x是長(zhǎng)度為偶數(shù)的0、1串}S→00S|01S|10S|11S|ε{0m1n|m,n≥1} ——RLS→0S|0A A→1A|1{0n1n|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→ε例2-7：{w|w為十進(jìn)位數(shù)}R→N|N.DN→1|2|3|4|5|6|7|8|9N→N0|N1|N2|N3|N4|N5|N6|N7|N8|N9D→1|2|3|4|5|6|7|8|9D→0D|1D|2D|3D|4D|5D|6D|7D|8D|9DD→0|0.D|N.0|0.0無用產(chǎn)生式與無用符號(hào)E→T|E+T|E-TT→F|T*F|T/FF→(E)|idE→E|H+TT→FH|TQ+PF|EQFM

→(E)|id單一產(chǎn)生式、派生不出終極符號(hào)行(H、Q、P)、從開始符號(hào)無法派生出來(M)文法構(gòu)造小結(jié)明確描述對(duì)象──語(yǔ)言合法的語(yǔ)言結(jié)構(gòu)確定基本符號(hào)集VT引入非終結(jié)符各種句子結(jié)構(gòu)定義句子的組成規(guī)則BNF範(fàn)式或產(chǎn)生式值得注意的問題文法描述描述句子的組成規(guī)則，不涉及語(yǔ)義文法正確不能保證語(yǔ)義正確（例）明確目標(biāo)要描述語(yǔ)言的結(jié)構(gòu)確認(rèn)基本符號(hào)集合理引入非終結(jié)符（語(yǔ)義明確）本章小結(jié)：幾個(gè)基本概念文法是語(yǔ)言的一種有窮描述，它嚴(yán)格、準(zhǔn)確、簡(jiǎn)潔。文法的形式定義句型、句子、語(yǔ)言文法的分類ＣＦＧ的語(yǔ)法樹習(xí)題1)給定文法如下：E→T|E+T|E-TT→F|T*F|T/FF→(E)|id畫出運(yùn)算式id*(id+id)+id的分析樹2)判斷上題的文法屬於哪個(gè)類型的文法？為什麼？第4章

自頂向下的語(yǔ)法分析語(yǔ)法分析方法語(yǔ)法分析方法 遞歸副程式法自頂向下 預(yù)測(cè)分析法(LL(1))

算符優(yōu)先分析法自底向上

LR(0)、SLR(1)[LR(1)、LALR]

TopDownBottomUp文法產(chǎn)生語(yǔ)言自動(dòng)機(jī)識(shí)別語(yǔ)言4.1語(yǔ)法分析的功能檢查由掃描器輸出的單詞符號(hào)序列是否符合該語(yǔ)言的文法——句子，並分析出組成此句子的語(yǔ)法成分掃描器分析器語(yǔ)義處理單詞符號(hào)語(yǔ)法樹根源程式分析器的輸入：Token序列分析器的輸出語(yǔ)法樹出錯(cuò)處理:定位、續(xù)編譯4.2自頂向下分析面臨的問題與CFG的改造一、自頂向下的分析從文法的開始符號(hào)出發(fā)，尋求所給的輸入符號(hào)串的最左推導(dǎo)從樹根S開始，構(gòu)造所給輸入符號(hào)串的語(yǔ)法樹例：G為：S→xAyA→**|*，輸入串：x**yS

xAy

x**ySxAy**二、重要概念回顧推導(dǎo):αＡβ

αγβ(依據(jù)：Ａ→γ)最左(Left-most)推導(dǎo)——最左分析左句型最左推導(dǎo)對(duì)應(yīng)最右歸約最右(Right-most)推導(dǎo)——最右分析規(guī)範(fàn)推導(dǎo)、規(guī)範(fàn)句型（右句型）最右推導(dǎo)對(duì)應(yīng)最左歸約（規(guī)範(fàn)歸約）二義性(先天二義性語(yǔ)言、二義性文法)三、重要問題——虛假匹配

x*y發(fā)現(xiàn)不匹配,需要回退SxAy*SxAy**S輸入串x**yS→xAyA→**|*S

xAy

x**y匹配成功

xAy三、重要問題——回溯SSxAy*SxAy**x**yS

xAy

x**y匹配成功x**y發(fā)現(xiàn)不匹配,需要回退

xAy

x*y三、重要問題——二義性對(duì)同一句子存在兩棵語(yǔ)法分析樹，哪個(gè)是對(duì)的？影響句子分析！EE*EidEE+ididEE+EEEid*idid三、重要問題——左遞歸問題例：文法S→Say|*與它的句子*ayay*ayayS

*不對(duì)！S

Say

Sayay

Sayayay……

Sayay……ayay一個(gè)無限迴圈！三、重要問題——左遞歸問題例簡(jiǎn)單算術(shù)運(yùn)算式的文法——左遞歸E→E+T|E-T|T|-ET→T*F|T/F|FF→E↑P|PP→(E)|id|const|FUN(L)FUN→abs|sin|cos|ln|log|exp|sqrtL→E|E,LVN＝{E,T,F,P,FUN,L｝VT＝{id,const,+,-,*,/,(,),\,,abs,sin,cos,log,ln,exp,sqrt}S＝E四、消除二義性例：簡(jiǎn)單算術(shù)運(yùn)算式的文法二義性文法E→E+E|E-E|E*E|E/E|(E)|id非二義性文法E→E+T|E-T|TT→T*F|T/F|FF→(E)|id改造方法：使文法含有更多的資訊，引入語(yǔ)法變數(shù)四、消除二義性再例：If語(yǔ)句S→ifEthenSS→ifEthenSelseSS→other設(shè)執(zhí)行下列語(yǔ)句前b=0,Ifa≠0thenifa>0thenb=1elseb=-1當(dāng)a=1時(shí),b=1;當(dāng)a=-1時(shí)，b=-1Ifa≠0thenifa>0thenb=1elseb=-1當(dāng)a=1時(shí),b=1;當(dāng)a=-1時(shí)，b=0一個(gè)句子有兩棵不同的語(yǔ)法樹

S S E E S S Ifa≠0thenifa>0thenb=1elseb=-1 S S E E S S Ifa≠0thenifa>0thenb=1elseb=-1四、消除二義性1.重寫文法S→U|MU→ifEthenSU→ifEthenMelseUM→ifEthenMelseM|other2.設(shè)置一個(gè)規(guī)則——實(shí)現(xiàn)“就近”、“最長(zhǎng)”匹配原則改造1改造2S→TS|CSC→ifEthenT→CSelseC—ConditionT—Else每個(gè)else與前面最近的沒有配對(duì)的then配對(duì)，即出現(xiàn)在then和else之間的語(yǔ)句必須是配對(duì)的按照“改造1”構(gòu)造的語(yǔ)法樹

S U S M E E M MIfa≠0thenifa>0thenb=1elseb=-1M→ifEthenMelseM|other按照“改造2”構(gòu)造的語(yǔ)法樹

S S

T(最長(zhǎng)) C C E E S SIfa≠0thenifa>0thenb=1elseb=-1S→TS|CSC→ifEthenT→CSelse按照“改造2”構(gòu)造的語(yǔ)法樹

S T

S(非最長(zhǎng)) C C E E S SIfa≠0thenifa>0thenb=1elseb=-1S→TS|CSC→ifEthenT→CSelse四、消除二義性

S S S

T(最長(zhǎng)) T(最長(zhǎng)) S C C C CifEthenifEthenSelseifEthenSelseifEthenSS→TS|CSC→ifEthenT→CSelse五、消除左遞歸無法根據(jù)左遞歸文法進(jìn)行自頂向下的分析

Aa1a2……ai……an直接左遞歸A

Aα 當(dāng)前變數(shù) 輸入指針

(棧頂、最左變數(shù))間接左遞歸 A

+Aα左遞歸的消除方法將A→Aα|β替換為A→βA′和A′→αA′｜ε例：運(yùn)算式文法直接左遞歸的消除E→E+T｜TT→T*F｜FF→(E)｜idE→TE’E’→+TE’|εT→FT’T’→*FT’｜εF→(E)｜id例：間接左遞歸的消除S→Ac|c A→Bb|b B→Sa|a將B的定義代入A產(chǎn)生式得：A→Sab|ab|b將A的定義代入S產(chǎn)生式得:S→Sabc|abc|bc|c消除直接左遞歸： S→abcS’|bcS’|cS’

S’→abcS’|ε刪除“多餘的”產(chǎn)生式：A→Sab|ab|b和B→Sa|a結(jié)果： S→abcS’|bcS’|cS’

S’→abcS’|ε 消除左遞歸的一般方法用產(chǎn)生式組A

β1B|β2B

|…|βnBB

α1B|α2B

|…|αnB|ε替換產(chǎn)生式組A→Aα1|Aα2|…|Aαn|β1|β2|…|βm

其中：B為新變數(shù)，相當(dāng)於A’消除左遞歸的演算法見P70的演算法為非終結(jié)符編號(hào)，再採(cǎi)用代入法將間接左遞歸變?yōu)橹苯幼筮f歸，消除直接左遞歸上次課主要內(nèi)容自頂向下的分析推導(dǎo)（派生）：自頂向下構(gòu)造語(yǔ)法分析樹待處理的問題虛假匹配——回溯二義性文法S→TS|CSC→ifEthenT→CSelseS→U|MU→ifEthenSU→ifEthenMelseUM→ifEthenMelseM|other上次課主要內(nèi)容消除左遞歸A→Aα1|Aα2|…|Aαn|β1|β2|…|βm

的等價(jià)產(chǎn)生式組A

β1B|β2B

|…|βnBB

α1B|α2B

|…|αnB|ε其中：B為新變數(shù)，相當(dāng)於A’提取左因數(shù)六、提取左因數(shù)例：if語(yǔ)句的原始文法S→ifEthenS

|ifEthenSelseS|other遇到if時(shí)難以判斷用哪一個(gè)產(chǎn)生式進(jìn)行匹配（推導(dǎo)）存在左因數(shù)ifEthenS提取作因數(shù)：S→ifEthenSS’|otherS'→ε|elseS左因數(shù)提取方法將形如A→αβ1|αβ2|…|αβn|γ1|γ2|…|γm的規(guī)則改寫為A→αA'|γ1|γ2|…|γm和A'→β1|β2|…|βn結(jié)果：S→ifEthenSS’|otherS'→ε|elseSS→TS|CS|otherC→ifEthenT→CSelse七、CFG的使用限制沒有一種方法能夠有效地分析所有上下文無關(guān)文法存在無法處理的２型文法(CFG)每種方法能夠處理一部分上下文無關(guān)文法每種方法都有適用範(fàn)圍八、常用文法與分析方法LL文法和LR文法都是CFG的子集(無二義性)可用不同的文法來描述同一語(yǔ)言對(duì)於不同的文法，可用不同的分析方法LL文法──遞歸下降分析法、預(yù)測(cè)分析法多用於編譯的手工實(shí)現(xiàn)LR文法──LR分析法多用於編譯的自動(dòng)生成4.3自頂向下的分析方法基本思想尋找輸入符號(hào)串的最左推導(dǎo)試圖根據(jù)當(dāng)前輸入單詞確定使用哪個(gè)產(chǎn)生式基本過程從根開始，按與最左推導(dǎo)相對(duì)應(yīng)的順序，構(gòu)造輸入符號(hào)串(Token)的語(yǔ)法分析樹例符號(hào)串id+id*id的分析E→TE’E’→+TE’｜εT→FT’T’→*FT’｜εF→(E)｜idE→E+T｜TT→T*F｜FF→(E)｜id按照最左推導(dǎo)過程，構(gòu)造語(yǔ)法樹id+id*id

的最左推導(dǎo)與語(yǔ)法樹的生成對(duì)應(yīng)ＥＴＥ’ＦＴ’Ｔ＋Ｅ’idεＦＴ’idεＦ＊Ｔ’idε1、E→TE’2、T→FT'3、F→id4、T'→ε5、E'→+TE’6、T→FT’7、F→id8、T'→*FT’9、F→id10、T'→ε11、E'→εid+id*id的最左推導(dǎo)再現(xiàn)E

TE’ E→TE’

FT’E’ T→FT’

idT’E’ F→id

idE’ T’→ε

id+TE’ E’→+TE’

id+FT’E’ T→FT’

id+idT’E’ F→id

id+id*FT’E’ T’→*FT’

id+id*idT’E’ F→id

id+id*idE’ T’→ε

id+id*id E’→ε候選式的確定與回溯(Backtracking)給定文法S→cAd A→ab|e?句子ced是該文法定義語(yǔ)言的句子ec A dS候選式的確定與回溯(Backtracking)給定文法S→cAd A→ab|e?句子cad是該文法定義語(yǔ)言的句子 c A dSba候選式的確定與回溯(Backtracking)給定文法S→cAd A→ab|a?句子cad是該文法定義語(yǔ)言的句子c A dSbaac A dS候選式的確定與回溯(Backtracking)當(dāng)要進(jìn)行某個(gè)語(yǔ)法變數(shù)的推導(dǎo)時(shí)，希望能夠根據(jù)當(dāng)前符號(hào)確定候選式。如果有幾個(gè)候選式（右部）左端第一個(gè)符號(hào)相同，則分析程式無法根據(jù)當(dāng)前輸入符號(hào)選擇產(chǎn)生式，只能試探希望：尋找一類文法，我們可以方便地根據(jù)當(dāng)前輸入符合確定正確的候選式4.3.1FIRST和FOLLOW集對(duì)於

α∈(VT∪VN)*定義:α的首符號(hào)集FIRST(α)={a|α

*a…，a∈VT*}對(duì)於

A∈VN定義A的後續(xù)符號(hào)集：

FOLLOW(A)={a|S

*…Aa…，a∈VT}求FIRST(X)的演算法1)對(duì)

x∈VT，F(xiàn)IRST(x)={x}；2)對(duì)

X∈VN，取FIRST(X)的初值：

{a|X→a…∈P}； X→ε

PFIRST(X)= {a|X→a…∈P}∪{ε}； X→ε∈P3)對(duì)

X∈VN，重複如下過程，直到所有FIRST集不變?nèi)鬤→Y…∈P，且Y∈VN，則FIRST(X)=FIRST(X)∪(FIRST(Y)-{ε})；若X→Y1…Yn∈P，且Y1...Yi-1

*ε，則對(duì)k=1到i-1:FIRST(X)=FIRST(X)∪(FIRST(Yk)-{ε})；若Y1...Yn

*ε，則FIRST(X)=FIRST(X)∪{ε}例 運(yùn)算式文法的語(yǔ)法符號(hào)的FIRST集FIRST(F)={(,id}FIRST(T)=FIRST(F)={(,id}FIRST(E)=FIRST(T)={(,id}FIRST(E')={+，ε}FIRST(T')={*,ε}FIRST(+)={+},FIRST(*)={*}FIRST(()={(}FIRST())={)}FIRST(id)={id}E→TE'E'→+TE’|εT→FT'T'→*FT’|εF→(E)|id求FIRST(α)的演算法令α=X1…Xn初值FIRST(α)=FIRST(X1)-{ε};k=1;迴圈whileε∈FIRST(Xk)&k<ndoFIRST(α)=FIRST(α)∪(FIRST(Xk+1)-{ε})；K=k+1;結(jié)束處理ifk=n&ε∈FIRST(Xn)thenFIRST(α)=FIRST(α)∪{ε}求FOLLOW(A)的演算法對(duì)於所有非終結(jié)符,重複進(jìn)行以下計(jì)算1)將#加入到FOLLOW(S)#為句子的結(jié)束符2)若A→αBβ，則FOLLOW(B)=FOLLOW(B)∪FIRST(β)–{ε}3)如果A→αB或A→αBβ，且β

*ε，A≠B，則FOLLOW(B)=FOLLOW(B)∪FOLLOW(A)例運(yùn)算式文法的語(yǔ)法變數(shù)的FOLLOW集FOLLOW(E)={#,)}FOLLOW(E')=FOLLOW(E)={#,)}FOLLOW(T)=FIRST(E’)∪FOLLOW(E)∪FOLLOW(E’)={+,),#}FOLLOW(T')=FOLLOW(T)={+,),#}FOLLOW(F)=FIRST(T’)∪FOLLOW(T)∪FOLLOW(T’)={*,+,),#}E→TE'E'→+TE’|εT→FT'T'→*FT’|εF→(E)|idFIRST(F)={（,id}FIRST(T)=FIRST(F)={（,id}FIRST(E)=FIRST(T)={（,id}FIRST(E')={+，ε}FIRST(T')={*,ε}自頂向下分析希望文法滿足的條件希望：從左到右掃描輸入串，尋找它的一個(gè)最左推導(dǎo)，每次有唯一的產(chǎn)生式可用對(duì)於G的每個(gè)非終結(jié)符A的任何兩個(gè)不同的候選式A→α|β1)FIRST(α)∩FIRST(β)=φ2)如果β

*ε，則FIRST(α)∩FOLLOW(A)=φ2’)如果α

*ε，則FIRST(β)∩FOLLOW(A)=φ——文法Ｇ是LL(1)的充要條件4.3.2LL(1)文法對(duì)G的任意變數(shù)A，A→α1|α2|…|αn是所有A產(chǎn)生式，它們滿足下列條件，則稱G是LL(1)文法，F(xiàn)IRST(αi)∩FIRST(αj)=Φi≠j且當(dāng)ε∈FIRST(αj)時(shí)，F(xiàn)OLLOW(A)∩FIRST(αi)=ΦLL(1)文法是自頂向下方法能夠處理的一類文法第一個(gè)L表示從左向右掃描輸入符號(hào)串第二個(gè)L表示生成最左推導(dǎo)