編譯原理課件

《編譯原理》

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

目標(biāo)代碼生成器代碼優(yōu)化器語義分析與中間代碼生成器語法分析器表格管理出錯(cuò)處理中間代碼中間代碼目標(biāo)代碼語法單位單詞符號(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、語法分析語法分析器(SyntaxAnalyzer，又叫Parser)完成語法分析功能：Parser實(shí)現(xiàn)“組詞成句”，構(gòu)造分析樹，指出語法錯(cuò)誤，指導(dǎo)翻譯輸入：Token序列輸出：語法成分2.語法分析res=fact*(term1+term2); 字串*；賦值語句運(yùn)算式=）（fact運(yùn)算式res運(yùn)算式運(yùn)算式運(yùn)算式運(yùn)算式+term1term23.語義分析功能：分析由語法分析器給出的語法單位的語義獲取識(shí)別字的屬性：類型、作用域等語義檢查：運(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語法樹波蘭表示問題——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其他類型的語句舉例

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è)階段提供資訊。輔助語法檢查、語義檢查完成靜態(tài)綁定、管理編譯過程Hash表、鏈表等各種查、填表技術(shù)8、錯(cuò)誤處理進(jìn)行各種錯(cuò)誤的檢查、報(bào)告、糾正，以及相應(yīng)的續(xù)編譯處理（如：錯(cuò)誤的定位與局部化）詞法：拼寫……語法：語句結(jié)構(gòu)、運(yùn)算式結(jié)構(gòu)……語義：類型不匹配……模組分類分析：詞法分析、語法分析、語義分析綜合：中間代碼生成、代碼優(yōu)化、目標(biāo)代碼生成輔助：符號(hào)表管理、出錯(cuò)處理8項(xiàng)功能對(duì)應(yīng)8個(gè)模組編譯程序總體結(jié)構(gòu)中間代碼目標(biāo)代碼生成器代碼優(yōu)化器語義分析與中間代碼生成器語法分析器表格管理出錯(cuò)處理中間代碼目標(biāo)代碼語法單位單詞符號(hào)詞法分析器根源程式例一個(gè)語句的翻譯9編譯的遍（Pass）根據(jù)系統(tǒng)資源的狀況、運(yùn)行目標(biāo)的要求……等，可以將一個(gè)編譯程序設(shè)計(jì)成多遍掃描的形式，在每一遍掃描中，完成不同的任務(wù)。遍可以和階段相對(duì)應(yīng)，也可無關(guān)單遍代碼不太優(yōu)中間代碼目標(biāo)代碼生成器代碼優(yōu)化器語義分析與中間代碼生成器語法分析器中間代碼目標(biāo)代碼語法單位單詞符號(hào)詞法分析器根源程式10、編譯的前端與後端前端與源語言有關(guān)、與目標(biāo)機(jī)無關(guān)的部分詞法分析、語法分析、語義分析與中間代碼生成、與機(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)，可靠性高可移植性，可擴(kuò)充性如何實(shí)現(xiàn)編譯器？直接用可運(yùn)行的代碼編制——太費(fèi)力！Ｔ形圖表示語言翻譯的Ｔ形圖源語言表示語言目標(biāo)語言功能1）交叉編譯(CrossCompiling)/移植問題一：A機(jī)上有一個(gè)C語言編譯器，是否可利用此編譯器實(shí)現(xiàn)B機(jī)上的C語言編譯器？條件：Ａ機(jī)有Ｃ語言的編譯程序（P1)目的：實(shí)現(xiàn)Ｂ機(jī)的Ｃ語言的編譯(P3)1.

(人)用Ｃ語言編制B機(jī)的Ｃ編譯程序P0(C→B)Ｃ語言Ｃ語言Ｂ機(jī)器P0Ｃ語言Ａ機(jī)器A機(jī)器P1Ｃ語言A機(jī)器Ｂ機(jī)器P22.(Ａ機(jī)的C編譯P1)編譯P0，得到在A機(jī)上可運(yùn)行的P2(C→B)Ｃ語言Ｃ語言Ｂ機(jī)器P0Ｃ語言Ａ機(jī)器A機(jī)器P1Ｃ語言A機(jī)器Ｂ機(jī)器P2獲得一個(gè)工具Ｃ語言A機(jī)器Ｂ機(jī)器P2Ｃ語言Ｃ語言Ｂ機(jī)器P03.(用Ａ機(jī)的P2)編譯P0，得到在B機(jī)上可運(yùn)行的P3(C→B)Ｃ語言Ｂ機(jī)器Ｂ機(jī)器P32)本機(jī)編譯器利用問題二：A機(jī)上有一個(gè)C語言編譯器，現(xiàn)要實(shí)現(xiàn)一個(gè)新語言NEW的編譯器？能利用交叉編譯技術(shù)麼？Ｃ語言Ａ機(jī)器A機(jī)器P1(原有)NEW語言A機(jī)器A機(jī)器P2(生成)NEW語言Ｃ語言A機(jī)器P0(編寫)用C編寫NEW的編譯，並用C編譯器編譯它問題三：直接在一個(gè)機(jī)上實(shí)現(xiàn)C語言編譯器，還有別的技術(shù)麼？解決：用組合語言實(shí)現(xiàn)一個(gè)Ｃ子集的編譯程序(P0—人)用組合語言程式處理該程式,得到P2(P2:可直接運(yùn)行)用Ｃ子集編制Ｃ語言的編譯程序(P3—人)用P2編譯P3，得到P43)編譯程序的自展技術(shù)1.

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

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

yyparse()函數(shù)ＹＡＣＣ1.6編譯技術(shù)的應(yīng)用把複雜數(shù)據(jù)看作一條語句數(shù)據(jù)格式的分析利用詞法分析、語法分析方法數(shù)據(jù)處理的框架基於語法制導(dǎo)的語義處理框架編譯技術(shù)可以用於各種複雜數(shù)據(jù)的分析處理例1-1DOS命令date的輸出格式例：9-2-1993、09-03-1993、9-03-93語法date→month-day-year詞法month→DIGITDIGIT|DIGITday→DIGITDIGIT|DIGITyear→DIGITDIGIT|DIGIIDIGITDIGITDIGIT例1-1語義year(年)、month(月)、day(日)語義約束條件0<month.value<130<day.value<32，31，300<year.value<100002.1語言概述什麼是語言自然語言(NaturalLanguage)是人與人的通訊工具語義(Semantics):環(huán)境、背景知識(shí)、語氣、二義性——難以形式化電腦語言(ComputerLanguage)電腦系統(tǒng)間、人機(jī)間通訊工具嚴(yán)格的語法(Grammar)、語義(Semantics)——易於形式化：嚴(yán)格語言是用來交換資訊的工具——功能性描述2.1語言概述語言的描述方法——現(xiàn)狀自然語言：自然、方便-非形式化數(shù)學(xué)語言（符號(hào)）：嚴(yán)格、準(zhǔn)確-形式化形式化描述高度的抽象，嚴(yán)格的理論基礎(chǔ)和方便的電腦表示。2.1語言概述語言——形式化的內(nèi)容提取單詞(Token)：滿足一定規(guī)則字元(Character)串句子(Sentence)：滿足一定規(guī)則單詞序列語言(Language)：滿足一定條件的句子集合語言是字和組合字的規(guī)則——結(jié)構(gòu)性描述例：一譯開天第課今始編節(jié)上今天開始上第一節(jié)編譯課2.1語言概述程式設(shè)計(jì)語言——形式化的內(nèi)容提取程式設(shè)計(jì)語言(ProgrammingLanguage)：組成程式的所有語句的集合程式(Program)：滿足語法規(guī)則的語句序列語句(Sentence)：滿足語法規(guī)則的單詞序列單詞(Token)：滿足詞法規(guī)則的字串例變數(shù)=運(yùn)算式if條件then語句while條件do語句call過程名(參數(shù)表)2.1語言概述描述形式——文法語法——語句語句的組成規(guī)則描述方法：BNF範(fàn)式、語法(描述)圖詞法——單詞單詞的組成規(guī)則描述方法：BNF範(fàn)式、正規(guī)式2.2基本定義字母表（Alphabet）是一個(gè)非空有窮集合，字母表中的元素稱為該字母表的一個(gè)字母（Letter），也叫字元（Character）例以下是不同的字母表 ⑴{a，b，c，d} ⑵{a，b，c，……，z} ⑶{0，1}相當(dāng)於高級(jí)語言的字元集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è)語言（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}*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)語言結(jié)構(gòu)的形式化描述？考慮一個(gè)句子——文法要素的提取分析：Thegraywolfwilleatthegoat〈謂語〉〈主語〉〈形容詞〉〈名詞〉〈動(dòng)詞〉〈直接賓語〉助動(dòng)詞〈句子〉動(dòng)原冠詞名詞Thegraywolfwilleatthegoat〈冠詞〉提取規(guī)則，寫在黑板上

句子

→

主語

謂語

主語

→

冠詞

形容詞

名詞

謂語

→

動(dòng)詞

直接賓語

動(dòng)詞

→

助動(dòng)詞

動(dòng)詞原形

直接賓語

→

冠詞

名詞

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

冠詞

→

the

形容詞

→

gray

助動(dòng)詞

→

will

動(dòng)詞原形

→

eat

名詞

→

wolf

名詞

→

goat終結(jié)符號(hào)集VT={the，gray,wolf,will,eat,goat}非終結(jié)符號(hào)集VN={

句子

，

主語

，

謂語

，

冠詞

，

形容詞

，

名詞

，

動(dòng)詞

，

直接賓語

，

助動(dòng)詞

，

動(dòng)詞原形

}語法規(guī)則集P={

句子

→

主語

謂語

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

句子

句子的語法組成

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

Ｇ=(ＶT，ＶN，Ｐ，Ｓ)ＶT：終結(jié)符(Terminal)集ＶN：非終結(jié)符(Variable)集，ＶT∩ＶN=Φ語法範(fàn)疇——某個(gè)語言結(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)。

句子

主語

謂語

冠詞

形容詞

名詞

謂語

the

形容詞

名詞

謂語

thegray

名詞

謂語

thegraywolf

謂語

thegraywolf

動(dòng)詞

直接賓語

thegraywolf

助動(dòng)詞

動(dòng)詞原形

直接賓語

thegraywolfwill

動(dòng)詞原形

直接賓語

thegraywolfwilleat

直接賓語

thegraywolfwilleat

冠詞

名詞

thegraywolfwilleatthe

名詞

thegraywolfwilleatthegoat句子的派生（推導(dǎo)）___根據(jù)規(guī)則

句子

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

thegraywolfwilleatthegoat還可以“得出”其他的句子例2-1算術(shù)運(yùn)算式的文法考慮簡(jiǎn)單算術(shù)運(yùn)算式組成的語言遞歸定義——中綴表示識(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)算式。例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-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)文法如何實(shí)現(xiàn)對(duì)語言的刻畫？產(chǎn)生式很關(guān)鍵！產(chǎn)生式規(guī)定的一些變換E由第1個(gè)候選式可以變成E+EE+E中的第1個(gè)E由第2個(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表示依據(jù)文法進(jìn)行的變換E

E+E （1）

E*E+E （2）

id*E+E （4）

id*E+id （4）

id*id+id （4）4E→id5E→E-E6E→E/EE可以變成E+EE+E中的第一個(gè)E變成E*EE*E+E變成id*E+Eid*E+E變成id*E+idid*E+id變成id*id+idE經(jīng)5步變換變成id*id+id：E

5id*id+id1E→E+E2E→E*E3E→(E)實(shí)質(zhì)是從E開始依據(jù)產(chǎn)生式對(duì)所得串中的特定部分進(jìn)行變換，不斷獲得新的串，最終得到目標(biāo)變換的分析實(shí)質(zhì)是從E開始依據(jù)產(chǎn)生式對(duì)所得串中的特定部分進(jìn)行變換，不斷獲得新的串，最終得到目標(biāo)

E*E

依據(jù)產(chǎn)生式E→E+EE*E+EαAβ依據(jù)產(chǎn)生式A→γαγβ直接推導(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

（若干步:零步或多步）E

5id*id+id推導(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)沒有（語法）變數(shù)了，不能再推了——得到句子1E→E+E2E→E*E3E→(E)4E→id句型與句子E

E+E

E+E*EE

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

*α，α∈(ＶT∪ＶN)*則稱α是G產(chǎn)生的一個(gè)句型(SententialForm)E

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

*x，且x∈ＶT*，則稱x是G產(chǎn)生的一個(gè)句子(Sentence)文法G產(chǎn)生的語言定義： L(G)={x|S

*xandx∈VT*}文法E→E+E|E*E|(E)|id可以派生出多少個(gè)句子？文法G的作用——語言的有窮描述以有限的規(guī)則描述無限的語言現(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)都施加在句型的最左邊的語法變數(shù)上——與最右歸約對(duì)應(yīng)最右推導(dǎo)(Right-mostDerivation)每次推導(dǎo)都施加在句型的最右邊的語法變數(shù)上——與最左歸約（規(guī)範(fàn)規(guī)約）對(duì)應(yīng)的規(guī)範(fàn)(Canonical)句型短語(Phrase)

Ｓ

*

αＡβ

+αγβ

？？就自然語言而言，γ在αγβ中什麼叫什麼？）如果Ｓ

*

αＡβ&A

γ則稱γ是句型αγβ的相對(duì)於變數(shù)A的直接短語最左直接短語叫做句柄(Handle)如果Ｓ

*

αＡβ&A

+γ，則稱γ是句型αγβ的相對(duì)於變數(shù)A的短語例：句型的短語與直接短語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)——最左直接短語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體系)語言結(jié)構(gòu)的複雜程度（形式語言）涉及文法的複雜程度、分析方法的選擇如果G滿足文法定義的要求，則Ｇ是０型文法（短語結(jié)構(gòu)文法PSG:PhraseStructureGrammar）。L(G)為PSL。例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例2-4識(shí)別字的文法3S→a|b|c|dS→aT|bT|cT|dTT→a|b|c|dT→0|1|2|3|4|5T→aT|bT|cT|dT|0TT→1T|2T|3T|4T|5TS→a|b|c|dS→Ha|Hb|Hc|Hd|H0S→H1|H2|H3|H4|H5H→Ha|Hb|Hc|Hd|H0H→H1|H2|H3|H4|H5H→a|b|c|dA→aB或A→aA→Ba或A→a正規(guī)文法(RG)設(shè)A、B∈VN，a∈VT∪{

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

aBC|aSBCCB

BCaB

abbB

bbbC

bccC

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

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

例L2={anbmcndm|n,m≥0}，它是檢查過程聲明的形參個(gè)數(shù)和過程引用的參數(shù)個(gè)數(shù)是否一致問題的抽象。高級(jí)語言中的非CFL結(jié)構(gòu)Chomsky體系——總結(jié)1型文法(CSG)S

aBCS

aSBCCB

BCaB

abbB

bbbC

bccC

cc

0型文法(PSG)S

aBCS

aSBCCB

BCaB

dbB

bbbC

bcC

cc2型文法(CFG)E→E+EE→E*EE→(E)E→idE→E-EE→E/E

3型文法S→a|bS→aT|bTT→a|bT→1|2T→aT|bTT→1T|2T3型文法S→a|bS→Ha|HbS→H1|H2H→Ha|HbH→H1|H2H→a|bChomsky體系——總結(jié)Ｇ=(ＶT，ＶN，Ｐ，Ｓ)是一個(gè)文法,α→β∈P* G是0型文法，L(G)是0型語言；

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

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

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

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

---其識(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}ul

{α1|α2…|αn}ml=0,u=m[α]≡α|ε……ＢＮＦ範(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一棵樹！2.5CFG的語法樹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í)子樹-直接短語又稱為語法分析樹例2-6短語與語法(分析)樹

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

）EE+Eid(a1)EE*id(a2)id(a3)短語——一棵子樹的葉子！短語：非單一結(jié)點(diǎn)的子樹的結(jié)果是相對(duì)於子樹根的短語。直接短語：僅有父子兩代的子樹的結(jié)果。句柄：一個(gè)句型的分析樹中最左那棵只有父子兩代的子樹的結(jié)果。例如，對(duì)運(yùn)算式文法G[E]和句子a1+a2*a3，挑選出推導(dǎo)過程中產(chǎn)生的句型中的短語，直接短語，句柄。用子樹解釋短語，直接短語，句柄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短語a1+a2*a3

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

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

E

E+E

E*E

(E)

id

文法的二義性(歧義性/ambiquity)文法的二義性EE*EidEE+ididEE+EEEid*idid一個(gè)句子有兩棵不同的語法樹

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兩個(gè)不同的最左推導(dǎo),對(duì)應(yīng)兩不同的語法樹

E

E*E

E*a3

E+E*a3

E+a2*a3

a1+a2*a3EE+Ea1E*Ea2a3EE*E+EEa1a2a3兩個(gè)不同的最右推導(dǎo),對(duì)應(yīng)兩不同的語法樹

E

E+E

E+E*E

E+E*a3

E+a2*a3

a1+a2*a3如果一個(gè)文法的句子存在兩棵分析樹,那麼,該句子是二義性的如果一個(gè)文法包含二義性的句子,則稱這個(gè)文法是二義性的;否則，該文法是無二義性的文法的二義性1.一般來說,高級(jí)程式設(shè)計(jì)語言存在無二義性文法,但有時(shí)用二義性文法。如：運(yùn)算式文法、條件語句文法S

ifexprthenS

ifexprthenSelseS

other二義性的句子:ife1thenife2thens1elses2

E→E+E|E-E|E*E|E/E|(E)|id無二義性文法較複雜E→E+T|E-T|TT→T*F|T/F|FF→(E)|id文法的二義性文法的二義性1.一般來說,高級(jí)程式設(shè)計(jì)語言存在無二義性文法,但有時(shí)用二義性文法。如：運(yùn)算式文法、條件語句文法S

ifexprthenS

ifexprthenSelseS

other二義性的句子:ife1thenife2thens1elses2

文法的二義性2.對(duì)於任意一個(gè)CFG，不存在演算法判定它是無二義性的；但能給出一組充分條件，滿足這組充分條件的文法是無二義性的一個(gè)文法是否為二義性的不可判定文法的二義性3.存在先天二義性語言。例如，語言

aibicj

i,j

1

aibjcj

i,j

1

存在二義性的句子akbkck一個(gè)語言是否為先天二義性的，在理論上不可判定文法的二義性4.在能駕馭的情況下，使用二義性文法——簡(jiǎ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參考書：(抽象)語法樹不同(語法)分析樹EE+idE+EEidid(抽象)語法樹+id+idid2.6文法的構(gòu)造——為了更好地理解文法目的：給出語言的有窮描述途徑：刻畫語言的結(jié)構(gòu)做法：給出定義的形式化描述根據(jù)經(jīng)驗(yàn)給出描述文法舉例{x|x是長(zhǎng)度為偶數(shù)的0、1串} ——RLS→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|9DR→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ì)象──語言合法的語言結(jié)構(gòu)確定基本符號(hào)集VT引入非終結(jié)符各種句子結(jié)構(gòu)定義句子的組成規(guī)則BNF範(fàn)式或產(chǎn)生式值得注意的問題文法描述描述句子的組成規(guī)則，不涉及語義文法正確不能保證語義正確（例）明確目標(biāo)要描述語言的結(jié)構(gòu)確認(rèn)基本符號(hào)集合理引入非終結(jié)符（語義明確）主要內(nèi)容詞法分析器(LexicalAnalyzer,Scanner)的功能正規(guī)運(yùn)算式有窮狀態(tài)自動(dòng)機(jī)FA——狀態(tài)圖詞法分析器的設(shè)計(jì)與實(shí)現(xiàn)3.1詞法分析（掃描）器的功能功能：輸入根源程式，輸出(單詞)符號(hào)(token)。即：把構(gòu)成根源程式的字串轉(zhuǎn)換成單詞符號(hào)的序列單詞符號(hào)的形式按照最小的語義單位設(shè)計(jì)通常表示為二元組： （單詞符號(hào)種別，屬性值）關(guān)鍵——找出符號(hào)的分割符例如：axx=70.35+12+exp(2.7)1)單詞符號(hào)的表示常用單詞符號(hào)種別——分類（P42）各關(guān)鍵字（保留字、基本字），各種運(yùn)算符，各種分界符——各用一個(gè)種別碼標(biāo)識(shí)其他識(shí)別字——用一個(gè)種別碼標(biāo)識(shí)常數(shù)——用一個(gè)種別碼標(biāo)識(shí)屬性（值）——單詞符號(hào)的值常數(shù)的值，識(shí)別字的名字等保留字、運(yùn)算符、分界符的屬性值可以省略單詞符號(hào)編碼舉例單詞符號(hào)種別編碼內(nèi)部值助記符DIM1$DIMIF2$IFDO3$DOSTOP4$STOPEND5$END識(shí)別字6內(nèi)部符號(hào)串$IDN整數(shù)7標(biāo)準(zhǔn)二進(jìn)位$INT=8$ASG+9$PLUS*10$STAR**11$POWER，12$COMMA（13$SLP）14$SRP例3-1:單詞符號(hào)序列

while(pointer!=N){S=S++;pointer++;}

while (WHILE,_)( (SLP,_)pointer (IDN,符號(hào)表項(xiàng)指針)!= (NE,_)N (IDN,符號(hào)表項(xiàng)指針)) (SRP,_){ (LP,_)S (IDN,符號(hào)表項(xiàng)指針) = (EQ,_)S (IDN,符號(hào)表項(xiàng)指針)++ (INC,_); (SEMI,_)pointer(IDN,符號(hào)表項(xiàng)指針)++ (INC,_); (SEMI,_)} (RP,_)2）相關(guān)問題詞法分析器可以作為一個(gè)獨(dú)立的副程式，也可以作為一遍獨(dú)立的掃描來安排。輸入緩衝區(qū)工作區(qū)(token)單詞開始指針掃描指針正拼單詞雙緩衝區(qū)並行、撚接每次移動(dòng)向前指針都需要做兩次測(cè)試2）相關(guān)問題？如何設(shè)計(jì)和實(shí)現(xiàn)掃描器大小問題128Byte*2|1024Byte*2|4096Byte*2forward:=forward+1;if

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

then重裝緩衝區(qū)第二部分elseifforward在緩衝區(qū)第二部分末尾

thenbegin

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

將forward移到緩衝區(qū)第一部分開始

endforward:=forward+1;ifforward！=eofthenif

forward在第一部分末尾

then

重裝第二部分

elseifforward在第二部分末尾

thenbegin

重裝第一部分;

將forward

移到第一部分開始

endelse終止詞法分析/*eof

在表示輸入結(jié)束*/3.2符號(hào)的描述——正規(guī)(表達(dá))式例：識(shí)別字的文法描述約定：用d表示數(shù)字：0,1,2,…,9;

用l表示字母：A,B,…,Z,a,b,…,zG=({d,l},{S,T},P,S)S→lS→SdS→Sl左線性文法S→l|lTT→lT|lT→dT|d右線性文法表示集合：{l}{l,d}*

1)正規(guī)式：正規(guī)語言的另一種描述方法例3-2：識(shí)別字的另一種表示l(l|d)*|表示"或"*表示Kleene閉包符號(hào)的並列表示符號(hào)連接關(guān)係正規(guī)式r表示正規(guī)集,相應(yīng)的正規(guī)集記為L(zhǎng)(r)正規(guī)(表達(dá))式(RegularExpression——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。運(yùn)算的優(yōu)先順序運(yùn)算優(yōu)先順序和結(jié)合性:*高於“連接”和|，“連接”高於|| 具有交換律、結(jié)合律“連接” 具有結(jié)合律、和對(duì)|的分配律()指定優(yōu)先關(guān)係意義清楚時(shí)，括弧可以省略例：L(a(a|b)*(ε|((.|_)(a|b)(a|b)*))){a}{a,b}*({ε}∪{.,_}{a,b}{a,b}*)2)正規(guī)文法與正規(guī)式正規(guī)文法與正規(guī)式等價(jià)對(duì)任何正規(guī)文法，存在定義同一語言的正規(guī)式對(duì)任何正規(guī)式，存在生成同一語言的正規(guī)文法例3-3識(shí)別字定義的轉(zhuǎn)換引入SS→l(l|d)*引入A消除閉包S→lAA→(l|d)A|ε執(zhí)行連接對(duì)|的分配律

S→lA A→lA|dA|ε

例3-4正規(guī)式到正規(guī)文法的轉(zhuǎn)換a(a|b)*(ε|((.|_)(a|b)(a|b)*)) =a(a|b)* |a(a|b)*.(a(a|b)*|b(a|b)*) |a(a|b)*_(a(a|b)*|b(a|b)*) =aA|aCA→aA|bA|εC→aC|bC|.B|_BB→aA|bAS→aA|aCA→aA|bA|εC→aC|bC|.B|_BB→aA|bA正規(guī)式到正規(guī)文法的轉(zhuǎn)換按如下方法構(gòu)造正規(guī)定義式，並逐步將其轉(zhuǎn)換成正則文法引入開始符號(hào)S，從如下正規(guī)定義式開始S→r對(duì)r中的形如r1|r2|…|rn的子串用產(chǎn)生式組 A→r1|r2|…|rn表示正規(guī)式到正規(guī)文法的轉(zhuǎn)換對(duì)r中的形如r1*的子串用產(chǎn)生式組A→ε|r1A表示對(duì)r中的形如r1+的子式子，用產(chǎn)生式組A→r1|r1A表示執(zhí)行連接對(duì)|的分配律對(duì)連接運(yùn)算，要作特殊處理：按出現(xiàn)順序定義正規(guī)式到正規(guī)文法的轉(zhuǎn)換用到了正規(guī)定義式的概念例3-5：一個(gè)簡(jiǎn)單詞法的正規(guī)定義式詞法規(guī)則 單詞種別 屬性<識(shí)別字>→<字母>(<字母>|<數(shù)字>)*

IDN 符號(hào)表項(xiàng)入口<無符號(hào)整數(shù)>→<數(shù)字>(<數(shù)字>)*

NUM 數(shù)值<賦值符>→:= ASG 無<加號(hào)>→+ + 無

<減號(hào)>→- MINUS 無<星號(hào)>→* STAR 無變換為正規(guī)文法<識(shí)別字>→letter<識(shí)別字尾><識(shí)別字尾>→ε|letter<識(shí)別字尾>|digit<識(shí)別字尾><整數(shù)>→digit<整數(shù)尾><整數(shù)尾>→ε|digit<整數(shù)尾> <賦值號(hào)>→:=<加號(hào)>→+<等號(hào)>→=…(其他：實(shí)數(shù)、算術(shù)運(yùn)算符、關(guān)係運(yùn)算符、分號(hào)、括弧等）正規(guī)文法到正規(guī)定義式的轉(zhuǎn)換代入：對(duì)於A→xB,B→y，構(gòu)造A→xy遞歸：對(duì)於A→xA|y，構(gòu)造A→x*y多候選式：對(duì)於A→x，A→y，構(gòu)造A→x|yS→0AA→1BB→2B|2C C→3C|3S→01BS→012*2CS→012*23*3S→012+3+

一個(gè)語言的文法描述不是唯一的（等價(jià)文法）3.3符號(hào)的識(shí)別──狀態(tài)轉(zhuǎn)換圖1狀態(tài)轉(zhuǎn)換圖（有窮自動(dòng)機(jī)FAM=(Q，∑，δ，q0，F(xiàn))）

用來描述詞法分析器識(shí)別記號(hào)的分析過程結(jié)點(diǎn)：狀態(tài)用○表示；終態(tài)用◎表示有向弧──箭頭弧標(biāo)記──輸入字元識(shí)別字的狀態(tài)圖<識(shí)別字>→letter(letter|digit)*

123letterletter,digit其他開始終態(tài)初態(tài)例3-5的狀態(tài)圖詞法規(guī)則 單詞種別 屬性<識(shí)別字>→letter(letter|digit)*

IDN 符號(hào)表項(xiàng)入口<無符號(hào)整數(shù)>→digit(digit)*

NUM 數(shù)值<賦值符>→:= ASG 無<加號(hào)>→+ + 無

<減號(hào)>→- MINUS 無<星號(hào)>→* STAR 無例3-5的狀態(tài)圖letter,digitletter（IDN，入口）digitdigit

(其他)

(其他)（NUM，值）（ASG，_）=：+（ADD，_）s+（INC，_）其他IDN→letter(letter|digit)*NUM→digit(digit)*ASG→:=INC→++ADD→+利用狀態(tài)轉(zhuǎn)換圖識(shí)別單詞符號(hào)1.從初態(tài)出發(fā)2.讀入一字元3.按當(dāng)前字元轉(zhuǎn)入下一狀態(tài)4.重複2,3直到無法繼續(xù)轉(zhuǎn)移在遇到讀入的字元是Token的分割符時(shí)，若當(dāng)前狀態(tài)是終止?fàn)顟B(tài)，說明讀入的字元組成一單詞；否則，說明輸入不符合詞法規(guī)則。2、從正規(guī)文法出發(fā)，構(gòu)造狀態(tài)圖1.以每個(gè)非終結(jié)符為狀態(tài)結(jié)點(diǎn)，開始符號(hào)對(duì)應(yīng)初態(tài)S2.增設(shè)一個(gè)終態(tài)TABaAa3.對(duì)於規(guī)則A→aB，畫從狀態(tài)A到B的弧，標(biāo)為a4.對(duì)於規(guī)則A→a，畫從狀態(tài)A到終態(tài)T的弧，標(biāo)為a*.對(duì)於規(guī)則A→rB,B→

sB，畫從狀態(tài)A到狀態(tài)N的弧，標(biāo)為r和狀態(tài)N到N的標(biāo)記為s的弧AsrB例3-6 Ｃ語言無符號(hào)整數(shù)的識(shí)別

1、正規(guī)定義式描述八進(jìn)制數(shù):(OCT，值)oct→0(0|1|2|3|4|5|6|7)(0|1|2|3|4|5|6|7)*十進(jìn)位數(shù):(DEC，值)dec→(1|...|9)(0|...|9)*|0十六進(jìn)制數(shù):(HEX，值)hex→0x(0|1|...|9|a|...|f|A|…|F)(0|...|9|a|...|f|A|…|F)*Asr2、識(shí)別不同進(jìn)制數(shù)的狀態(tài)圖342100-70-7

(其他)56101-90-9

(其他)十進(jìn)位整數(shù)八進(jìn)制整數(shù)oct→0(0|1|2|3|4|5|6|7)(0|1|2|3|4|5|6|7)*dec→(1|...|9)(0|...|9)*|02、識(shí)別不同進(jìn)制數(shù)的狀態(tài)圖910810

(其他)十六進(jìn)制整數(shù)7x0-9,a-f0-9,a-f狀態(tài)圖合併1、從開始狀態(tài)出發(fā)；2、選擇輸入符號(hào)，構(gòu)成目標(biāo)狀態(tài)集3、從新狀態(tài)集出發(fā)，重複1、2hex→0x(0|1|...|9|a|...|f|A|…|F)(0|...|9|a|...|f|A|…|F)*（HEX，值）（OCT，值）3、Ｃ語言無符號(hào)整數(shù)識(shí)別的狀態(tài)圖9810其他2,6,7x0-9,a-f0-9,a-f30-70-7其他51-90-9其他（DEC，值）其他4106另一種做法開始12061-93x0-9,a-f40-9,a-f其他0-9其他50-70-7其他（DEC，值）（HEX，值）（OCT，值）其他3.4詞法分析程式的設(shè)計(jì)與實(shí)現(xiàn)狀態(tài)轉(zhuǎn)移圖——教材P43狀態(tài)轉(zhuǎn)移圖的實(shí)現(xiàn)——教材P44-46另一種實(shí)現(xiàn)：副程式scan()輸入：字元流輸出：Symbol(Code):單詞種別Attr(value):屬性（全局變數(shù)）數(shù)據(jù)結(jié)構(gòu)與子例程數(shù)據(jù)結(jié)構(gòu)ch當(dāng)前輸入字元token輸入緩衝區(qū)(字元數(shù)組)symbol單詞種別（副程式的返回值）attr屬性（全局變數(shù)）副程式Lookup(token):將token存入符號(hào)表，返回入口指針isKeyword(token):判別token是關(guān)鍵字？返回關(guān)鍵字種別或-1getchar():從輸入緩衝區(qū)中讀入一個(gè)字元放入chisdigit()isalpha()例3-3的狀態(tài)圖的實(shí)現(xiàn)演算法1.getchar()2.WHILEch是空格 //跳過空格2.1DOgetchar();3.CASEchOF4.isdigit(ch):4.1ch→token;getchar();4.2WHILEisdigit(ch)DO{ch→token;getchar();}4.3輸入指針回退一個(gè)字元；4.4將token中的字串變成數(shù)值→attr4.5返回NUM5.isalpha(ch):5.1ch→token;getchar();5.2WHILEisalpha(ch)ORisdigit(ch)DO{ch→token;getchar()};5.3 輸入指針回退一個(gè)字元;5.4key=isKeyword(token);5.5IFkey≥0THEN返回key5.6Lookup(token)→attr;5.7返回IDN6':':getchar();6.1IFch等於'='THEN返回ASG6.2出錯(cuò)處理7'+':返回ADD8'-':返回SUB9'*':返回MUL10'/':返回DIV11'=':返回EQ12'>':返回GT13'<':返回LT14'(':返回LP15')':返回RP16';':返回SEMI17其他:出錯(cuò)處理18ENDOFCASE需要說明的問題緩衝區(qū)預(yù)處理，超前搜索關(guān)鍵字的處理，符號(hào)表的實(shí)現(xiàn)Lookup：查找效率，演算法的優(yōu)化實(shí)現(xiàn)詞法錯(cuò)誤處理由於高級(jí)語言的片語成的集合為3型語言，所以，這裏討論的詞法分析技術(shù)可以用於處理所有的3型語言，也就是所有的可以用3型文法描述的語言。如：資訊檢索系統(tǒng)的查詢語言、命令語言等LEX簡(jiǎn)介：實(shí)現(xiàn)過程Lex根源程式Lex.yy.cLex編譯器詞法分析器LLex.yy.cC編譯器Token序列詞法分析器L輸入流LEX簡(jiǎn)介：Lex程式結(jié)構(gòu)聲明部分(正規(guī)定義式)%%轉(zhuǎn)換規(guī)則(識(shí)別規(guī)則)%%輔助過程%{常量定義%}正規(guī)定義掃描器的自動(dòng)生成：LEX簡(jiǎn)介1、正規(guī)定義式letter→A|B|C|…|Z|a|b|c|…|zdigit→0|1|2|…|9identifier→letter(letter|digit)*integer→digit(digit)*

2、識(shí)別規(guī)則正規(guī)式 動(dòng)作描述token1 {action1}token2 {action2}……tokenn {actionn}本章總結(jié)詞法分析器從組成根源程式的字元行中尋找出單詞，並給出它們的種別和屬性——輸出二元組序列高級(jí)語言的單詞組成一個(gè)3型語言3型語言可以用RE、RG、FA描述FA的狀態(tài)轉(zhuǎn)移圖，可以被用來指導(dǎo)相應(yīng)的詞法分析器的實(shí)現(xiàn)2023-11-211564.1語法分析的任務(wù)語法分析(SyntaxAnalysis)檢查掃描器輸出的單詞序列是否符合