編譯分析技術(shù)與工具課件

編譯中的分析技術(shù)和工具簡(jiǎn)介編譯中的分析技術(shù)和工具簡(jiǎn)介大綱概念文法分析遞歸下降分析LL分析LR分析YACCLex選擇學(xué)習(xí)資料大綱概念概念：編譯的地位《降龍十八掌》《太公兵法》理論、形式化經(jīng)驗(yàn)、積累操作系統(tǒng)編譯器概念：編譯的地位《降龍十八掌》《太公兵法》理論、形式化經(jīng)驗(yàn)操概念：編譯編譯Compile翻譯【計(jì)】totranslateinstructions……編纂collectandputtogetherintmain(){inta,b;a=(int)&b;printf(“%x\n”,a);return0;}B801FEFF0E4BC6F8FE……C++Compiler源代碼編譯器目標(biāo)代碼概念：編譯編譯Compileintmain()B801概念：編譯基本過(guò)程#defineMAX256#defineTEXT“Hello”intmain(){inta=MAXcharx[]=TEXT……B801FEFF0E4BC6F8FE……預(yù)處理優(yōu)化代碼生成分析Pre-ProcessParseOptimizeGenerateintmain(){inta=256charx[]=“Hello”……有向無(wú)環(huán)圖DAG抽象語(yǔ)法樹(shù)AST中間代碼IntermediateCode源代碼Source目標(biāo)代碼Target概念：編譯基本過(guò)程#defineMAX256B801概念：解釋解釋InterpretInterpret：口譯#!/bin/shecho“Begin”catfile|lessmakesed…………Bash源代碼解釋器執(zhí)行動(dòng)作catmakesedless概念：解釋解釋Interpret#!/bin/shBash概念：解釋基本過(guò)程執(zhí)行分析ParseRun#!/bin/shecho“Begin”catfile|lessmakesed…………概念：解釋基本過(guò)程執(zhí)行分析ParseRun#!/bin/sh概念：分析分析Parse序列化到結(jié)構(gòu)化詞法分析、語(yǔ)法分析、語(yǔ)義分析FUNCTIONfact(x)IFx=0THENRETURN1ENDIFs=1FORi=1TOxs=s*iNEXTiENDFUNCTIONPRINTfact(10)PRINTfact(8)……概念：分析分析ParseFUNCTIONfact(x)文法文法Grammar文法的概念文法和語(yǔ)言文法的表示Chomsky文法分類文法文法Grammar文法：文法的概念（1）標(biāo)準(zhǔn)句型：（定語(yǔ)）主語(yǔ)（狀語(yǔ)）謂語(yǔ)（補(bǔ)語(yǔ)）（定語(yǔ)）賓語(yǔ)主語(yǔ)：名詞/代詞謂語(yǔ)：動(dòng)詞賓語(yǔ)：名詞/代詞定語(yǔ)：形容詞/代詞狀語(yǔ)：副詞補(bǔ)語(yǔ)：助詞名詞：蘋果、人、水、船……動(dòng)詞：揍、吃、喝、喜歡……代詞：我、它、那個(gè)形容詞：紅、壞、賤……副詞：飛快的、狠狠的、很……助詞：了、吧、嗎……我吃紅蘋果我飛快的吃蘋果我狠狠的揍了那個(gè)賤人我吃船蘋果吃了我我很喜歡壞蘋果文法：文法的概念（1）標(biāo)準(zhǔn)句型：（定語(yǔ)）主語(yǔ)（狀語(yǔ)）謂語(yǔ)（補(bǔ)文法：文法的概念（2）標(biāo)準(zhǔn)句型：（定語(yǔ)）主語(yǔ)（狀語(yǔ)）謂語(yǔ)（補(bǔ)語(yǔ)）（定語(yǔ)）賓語(yǔ)主語(yǔ)：名詞/代詞謂語(yǔ)：動(dòng)詞賓語(yǔ)：名詞/代詞……名詞：蘋果、人、水、船……動(dòng)詞：揍、吃、喝、喜歡……代詞：我、它、那個(gè)……我吃紅蘋果我飛快的吃蘋果我狠狠的揍了那個(gè)賤人開(kāi)始符號(hào)終結(jié)符Terminal非終結(jié)符Non-Terminal產(chǎn)生式Production句子推導(dǎo)、表達(dá)規(guī)約、分析文法：文法的概念（2）標(biāo)準(zhǔn)句型：（定語(yǔ)）主語(yǔ)（狀語(yǔ)）謂語(yǔ)（補(bǔ)文法：文法的概念（3）Program：ConditionStatementCommentCondition：ifExpressionStatement：printValueComment：#Text……Expression：Expression=ExpressionValue：a|b|c|d……Text：Hello|Good|How……ifa=bprintHelloifb=cprintGood……開(kāi)始符號(hào)終結(jié)符Terminal非終結(jié)符Non-Terminal產(chǎn)生式Production句子推導(dǎo)、表達(dá)規(guī)約、分析文法：文法的概念（3）Program：Condition文法：文法和語(yǔ)言文法的形式化定義文法：四元組(S,VN,VT,P)句子：文法的一個(gè)推導(dǎo)語(yǔ)言文法中所有句子的集合XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX文法：文法和語(yǔ)言文法的形式化定義XXXXXXXXXXXXXX文法：文法的表示產(chǎn)生式：α→β句子→主語(yǔ)謂語(yǔ)賓語(yǔ)A→AaA→BcB→bbAB→AcdBNF范式（Backus-NaurForm）句子::=主語(yǔ)謂語(yǔ)賓語(yǔ)<A>::=<A>a<B>::=<A>b<B>c<A>d擴(kuò)展BNF范式（EBNF范式）<A>::=<A>a|<B>c{<D>}*|ab+c|……文法：文法的表示產(chǎn)生式：α→β文法：文法的Chomsky分類(1)不同特點(diǎn)的產(chǎn)生式、不同的表達(dá)能力3型文法（正則文法）RegularGrammar產(chǎn)生式簡(jiǎn)單<A>::=a<A><A>::=a表達(dá)能力很弱a、aa、aaa、aaaa、……ac、abc、abbc、abbbc、abbbbc……沒(méi)有“記憶”能力等價(jià)于確定性有限自動(dòng)機(jī)（DFA）多用于定義單詞（token）文法：文法的Chomsky分類(1)不同特點(diǎn)的產(chǎn)生式、不同的文法：文法的Chomsky分類(2)3型文法的語(yǔ)言表達(dá)能力示例嘰嘰嘰嘰嘰嘰嘰嘰……嘰嘰嘰嘰吱吱吱吱……吱吱嘰嘰吱吱……文法：文法的Chomsky分類(2)3型文法的語(yǔ)言表達(dá)能力示文法：文法的Chomsky分類(3)3型文法的語(yǔ)言分析能力示例FUNCTIONfact(x)IFx=0THENRETURN1ENDIFs=1FORi=1TOxs=s*iNEXTiENDFUNCTIONPRINTfact(10)PRINTfact(8)……FUNCTIONfact(x)IF……PROGRAM::=TOKENSP*TOKEN::=ALPHA*ALPHA::=a|b|c|…|zALPHA::=A|B|C|…|Z文法：文法的Chomsky分類(3)3型文法的語(yǔ)言分析能力示文法：文法的Chomsky分類(4)2型文法（上下文無(wú)關(guān)文法）ContextFreeGrammarabbr.CFG產(chǎn)生式左部只有一個(gè)非終結(jié)符（|α|=1）<A>::=a<A><B><C>d<B>::=<A>x<B>yz表達(dá)能力較強(qiáng)IFa>bTHENa=bELSEb=astaticintprintk(constchar*fmt,…);有一定的“記憶”能力多用于定義簡(jiǎn)單語(yǔ)法（syntax）文法：文法的Chomsky分類(4)2型文法（上下文無(wú)關(guān)文法文法：文法的Chomsky分類(5)2型文法的語(yǔ)言表達(dá)能力示例媽媽，抱抱(我)我要(那個(gè)(娃娃))哇哇哇哇嗚嗚嗚嗚……文法：文法的Chomsky分類(5)2型文法的語(yǔ)言表達(dá)能力示文法：文法的Chomsky分類(6)2型文法的語(yǔ)言分析能力示例FUNCTIONfact(x)IFx=0THENRETURN1ENDIFs=1FORi=1TOxs=s*iNEXTiENDFUNCTIONPRINTfact(10)PRINTfact(8)……PROGRAMxsRETURN1IF……PROGRAM::=FUNCTIONFUNCTION::=FUNCSTENDST::=IFEXPRRENDIFEXPR::=EXPR=EXPR……FUNCTIONTHEN……賦值=0文法：文法的Chomsky分類(6)2型文法的語(yǔ)言分析能力示文法：文法的Chomsky分類(7)1型文法（上下文相關(guān)文法）ContextSensitiveGrammarabbr.CSG產(chǎn)生式左部長(zhǎng)度小于右部長(zhǎng)度（|α|≤|β|）<A>::=a<A><B><C>da<B>c::=<A>x<B>yz<C><B>m::=xyzu推導(dǎo)是“收斂”的表達(dá)能力更強(qiáng)能表達(dá)語(yǔ)境的概念可定義復(fù)雜語(yǔ)法和部分語(yǔ)義（semantics）文法：文法的Chomsky分類(7)1型文法（上下文相關(guān)文法文法：文法的Chomsky分類(8)1型文法的語(yǔ)言表達(dá)能力示例今王與百姓百姓同樂(lè)，則王矣王欲行王政，則勿毀之矣梁惠王齊宣王成為老大王者文法：文法的Chomsky分類(8)1型文法的語(yǔ)言表達(dá)能力示文法：文法的Chomsky分類(9)1型文法的語(yǔ)言分析能力示例intx;intmain(){intx;x=4;func();return0;}voidfunc(){x=4;}賦值ESP+[x]4賦值DS+[x]4文法：文法的Chomsky分類(9)1型文法的語(yǔ)言分析能力示文法：文法的Chomsky分類(10)0型文法（短語(yǔ)文法）產(chǎn)生式?jīng)]有限制a<A><B><C>::=ad<B>::=<A>x<B><C><B>m::=x表達(dá)能力最強(qiáng)等價(jià)于圖靈機(jī)文法：文法的Chomsky分類(10)0型文法（短語(yǔ)文法）文法：文法的Chomsky分類(11)喬姆斯基文法分類總結(jié)文法類型用處0型文法短語(yǔ)文法圖靈機(jī)1型文法上下文相關(guān)文法部分語(yǔ)義、復(fù)雜語(yǔ)法2型文法上下文無(wú)關(guān)文法語(yǔ)法3型文法正則文法單詞、簡(jiǎn)單匹配表達(dá)能力限制規(guī)則文法：文法的Chomsky分類(11)喬姆斯基文法分類總結(jié)文分析：概念(1)分析Parse序列化到結(jié)構(gòu)化理解按照指定的文法去理解給定的句子語(yǔ)義(Semantics)檢查語(yǔ)法(Syntax)分析詞法(Lexical)分析分析：概念(1)分析Parse分析：概念(2)完全分析樹(shù)結(jié)構(gòu)太復(fù)雜intx;intmain(){intx;x=4;func();return0;}voidfunc(){x=4;}賦值ESP+[x]4DS+[x]mainfunc()返回函數(shù)定義=范圍調(diào)用=賦值4范圍0變量定義x程序分析：概念(2)完全分析intx;賦值ESP+[x]4DS分析：概念(3)分工語(yǔ)法分析：主導(dǎo)詞法分析：支撐語(yǔ)義分析：指導(dǎo)、檢查語(yǔ)法樹(shù)詞法詞法詞法語(yǔ)義檢查分析：概念(3)分工語(yǔ)法樹(shù)詞法詞法詞法語(yǔ)義檢查分析：詞法分析詞法分析用正則文法去理解“字符序列”，提供“單詞序列”intx;intmain(){intx;x=4;func();return0;}voidfunc(){x=4;}intintmainmainx=x=分析：詞法分析詞法分析intx;intintmainmai分析：語(yǔ)法分析語(yǔ)法分析用2型文法去理解“單詞序列”intx;intmain(){intx;x=4;func();return0;}voidfunc(){x=4;}賦值返回函數(shù)定義調(diào)用賦值變量定義程序分析：語(yǔ)法分析語(yǔ)法分析intx;賦值返回函數(shù)定義調(diào)用賦值變分析：分析方法詞法分析直接分析構(gòu)造確定有限狀態(tài)機(jī)分析語(yǔ)法分析遞歸下降分析法LL分析法LR分析法算符優(yōu)先分析法……分析：分析方法詞法分析遞歸下降分析：下降下降逐級(jí)下降分工每一級(jí)均為函數(shù)調(diào)用1+2*3+4/5表達(dá)式因子+因子1*+因子/2345遞歸下降分析：下降下降1+2*3+4/5表達(dá)式因子+因子1*遞歸下降分析：遞歸遞歸語(yǔ)法為遞歸定義時(shí)，調(diào)用也遞歸調(diào)用嚴(yán)格定義的遞歸接口1+2*(3+4*5)表達(dá)式因子1*+因子2表達(dá)式因子3+45*遞歸下降分析：遞歸遞歸1+2*(3+4*5)表達(dá)式因子1*+遞歸下降分析遞歸下降分析結(jié)構(gòu)簡(jiǎn)單、自然編碼容易語(yǔ)言不復(fù)雜時(shí)性能極佳采用遞歸下降作為前端的著名的C編譯器：LCCGCC（>3.0）CCompilerOpenWatcomCCompilerLLVM/Clang……遞歸下降分析遞歸下降分析LL分析法(1)LL：Left-Left從左向右讀入單詞從左向右分析遞歸下降分析法即為L(zhǎng)L分析法的一種特例LL(k)：提前掃描k個(gè)單詞LL(1)：提前查看1個(gè)單詞，最常用的LL分析法1+2+3+411+1+233+3+366+6+410LL分析法(1)LL：Left-Left1+2+3+411+LL分析法(2)LL(1)分析法自頂向下分析程序直觀可用狀態(tài)轉(zhuǎn)換表實(shí)現(xiàn)可用遞歸下降實(shí)現(xiàn)易于手工實(shí)現(xiàn)LL分析法(2)LL(1)分析法LR分析法(1)LR：Left-RightbyDonaldKnuth,1965從左向右讀入單詞從右向左分析LR(k)：提前查看k個(gè)單詞LALR(1)：LR(1)加約束，最常用的LR分析法1+2+3+411+1+21+2+1+2+3+1+2+3+4101+2+71+9LR分析法(1)LR：Left-Right1+2+3+411LR分析法(2)LALR(1)分析法自底向上的分析用二維狀態(tài)轉(zhuǎn)換表實(shí)現(xiàn)轉(zhuǎn)換表構(gòu)造過(guò)程復(fù)雜，難以手工實(shí)現(xiàn)自己維護(hù)較大的棧（“記憶”的多）可表達(dá)的語(yǔ)法范圍比LL分析法廣LL和LR的兼容問(wèn)題int

foo(){x=4;return1;}int

bar(){x=8;return1;}……if

(foo()&&bar()){printf(“x=%d\n”,x);}LR分析法(2)LALR(1)分析法intfoo(){YACC：概念(1)背景寫一個(gè)編譯器前端很困難大量編譯器前端的工作重復(fù)形式語(yǔ)言理論成熟MULTICS項(xiàng)目LALR分析法“很好很強(qiáng)大”手工構(gòu)造狀態(tài)轉(zhuǎn)換表很困難構(gòu)造狀態(tài)轉(zhuǎn)換表的方法較機(jī)械YACCYACC：概念(1)背景YACCYACC：概念(2)YetAnotherCompiler’sCompilerbyStephenC.Johnson,1975,BellLab神一般的工作人編譯器程序苦力YACC神?YACC：概念(2)YetAnotherCompilerYACC：概念(3)YACC輸入一個(gè)CFG文法輸出一個(gè)LALR分析器（C語(yǔ)言實(shí)現(xiàn)）與主程序結(jié)合，成為一個(gè)編譯器/解釋器AT&TYacc,BerkeleyYacc,GNUBison……grammar.yYACCy.tab.cCCmain.c編譯器/解釋器源程序……YACC：概念(3)YACCgrammar.yYACCy.tYACC：實(shí)踐(1)實(shí)踐任務(wù)：簡(jiǎn)單的四則混合運(yùn)算計(jì)算器calc例如：1+(2+3)*6/5-4*6從文件中讀入源程序源程序?yàn)橐粋€(gè)混合運(yùn)算式程序以#結(jié)尾運(yùn)算數(shù)為個(gè)位數(shù)運(yùn)算符為+、-、*、/和括號(hào)(、)分析完后執(zhí)行運(yùn)算，打印出結(jié)果9-8*7/(1+2+1)+4*(2+5)#calcsource.calc23YACC：實(shí)踐(1)實(shí)踐任務(wù)：簡(jiǎn)單的四則混合運(yùn)算計(jì)算器calYACC：實(shí)踐(2)分析文法，歸納語(yǔ)法1+2*(3+4*5)+6括號(hào)里和整個(gè)表達(dá)式是同構(gòu)關(guān)系乘除運(yùn)算優(yōu)先級(jí)較高加減運(yùn)算優(yōu)先級(jí)最低最直接的文法表達(dá)式::=因子+-因子+-因子+-……（一個(gè)或多個(gè)）因子::=因數(shù)*/因數(shù)*/因數(shù)*/

……（一個(gè)或多個(gè)）因數(shù)::=數(shù)字因數(shù)::=(表達(dá)式)YACC：實(shí)踐(2)分析文法，歸納語(yǔ)法YACC：實(shí)踐(3)化簡(jiǎn)為2型文法（CFG）BNF/EBNF表示的產(chǎn)生式（盡量用右遞歸）程序::表達(dá)式‘#’表達(dá)式::=表達(dá)式+因子表達(dá)式::=表達(dá)式-因子表達(dá)式::=因子因子::=因子*因數(shù)因子::=因子/因數(shù)因子::=因數(shù)因數(shù)::=數(shù)字因數(shù)::=‘(’表達(dá)式‘)’數(shù)字::‘0’……數(shù)字::‘9’YACC：實(shí)踐(3)化簡(jiǎn)為2型文法（CFG）YACC：實(shí)踐(4)設(shè)計(jì)動(dòng)作每分析完一條產(chǎn)生式則立即運(yùn)算例如分析……7*2……：數(shù)字::=‘7’，將“數(shù)字”的值設(shè)為7因數(shù)::=數(shù)字，將“因數(shù)”的值設(shè)為“數(shù)字”值，即7因子::=因數(shù)，將“因子”的值設(shè)為“因數(shù)”值，即7數(shù)字::=‘2’，將“數(shù)字”的值設(shè)為2因數(shù)::=數(shù)字，將“因數(shù)”的值設(shè)為“數(shù)字”值，即2因子::=因子*因數(shù)，將“因子”的值設(shè)為7*2即14……程序::=表達(dá)式#，將表達(dá)式的值XXXX打印出來(lái)YACC：實(shí)踐(4)設(shè)計(jì)動(dòng)作YACC：實(shí)踐(5)寫yacc源文件yacc源文件格式規(guī)則：類似EBNF格式動(dòng)作：C語(yǔ)言的程序段用YACC生成y.tab.c%{C語(yǔ)言的定義、聲明%}/*YACC定義*/%%/*規(guī)則定義*/規(guī)則1{動(dòng)作1};規(guī)則2{動(dòng)作2};%%其他C代碼YACCy.tab.cYACC：實(shí)踐(5)寫yacc源文件%{YACCy.tab.YACC：實(shí)踐(6)寫主控程序主控程序和y.tab.c的主要接口yylex：分析器調(diào)用yylex讀入字符（單詞）序列yyerror：當(dāng)分析錯(cuò)誤時(shí)，分析器調(diào)用該函數(shù)yyparse：開(kāi)始分析函數(shù)，由主控程序調(diào)用intmain(){……}intyylex(){……}voidyyerror(){……XXXXYYYYyyparse(){……}ZZZZy.tab.c主控程序YACC：實(shí)踐(6)寫主控程序intmain()XXXXYACC：實(shí)踐(7)聯(lián)編編譯連接cc-cy.tab.ccc-cmain.ccc-ocalcmain.o

y.tab.o測(cè)試創(chuàng)建一個(gè)文件test.ca內(nèi)容：9-8*7/(1+2+1)+4*(2+5)#運(yùn)行：./calctest.ca結(jié)果：Result=23修改內(nèi)容：9-8*7/(1+2#運(yùn)行：./calctest.ca結(jié)果：ERROR:SyntaxerrorYACC：實(shí)踐(7)聯(lián)編YACC：實(shí)踐(8)問(wèn)題僅能識(shí)別1位數(shù)的數(shù)字（value:1|2|…99|…10000?）不能識(shí)別符號(hào)（value:A|B|…|Z|…|AB|…|ABC|?）加入這些功能使得狀態(tài)轉(zhuǎn)換表規(guī)模很大（N2）怎么辦？將數(shù)字、符號(hào)的識(shí)別功能“外包”給某個(gè)程序保持較小的狀態(tài)轉(zhuǎn)換表規(guī)模N2+M2<(N+M)2LEXYACC：實(shí)踐(8)問(wèn)題LEXLEX：概念(1)LEXLexicalParserGenerator，詞法分析器生成器目標(biāo)：配合YACCbyEricSchmidtandMichaelLesk,1975,BellLabAT&TLex,GNUFlex……LEX：概念(1)LEXLEX：概念(2)LEX輸入一個(gè)3型（正則）文法輸出一個(gè)單詞分析器與YACC結(jié)合，為YACC提供yylex()等接口grammar.yYACCy.tab.cCCmain.c編譯器/解釋器源程序……lexical.lLEXlex.yy.cy.tab.hLEX：概念(2)LEXgrammar.yYACCy.tabLEX：實(shí)踐(1)實(shí)踐任務(wù)1：簡(jiǎn)單的單詞分析器，配合YACC數(shù)字：1、10、124……常量：LONG、CHAR……從文件中讀入源程序，分析數(shù)字和符號(hào)提供yylex()，每調(diào)用一次得到一個(gè)單詞類型源程序?yàn)檩^復(fù)雜的混合運(yùn)算式120*LONG+32*(CHAR+2*LONG)#120*+32*+2*#)LONGCHAR(LONGLEX：實(shí)踐(1)實(shí)踐任務(wù)1：簡(jiǎn)單的單詞分析器，配合YACCLEX：實(shí)踐(2)實(shí)踐任務(wù)2：YACC和LEX實(shí)現(xiàn)更強(qiáng)大的計(jì)算器使YACC分析時(shí)能支持多位的整數(shù)使YACC能支持預(yù)定義的常量LONG=4CHAR=1LEX：實(shí)踐(2)實(shí)踐任務(wù)2：YACC和LEX實(shí)現(xiàn)更強(qiáng)大的計(jì)LEX：實(shí)踐(3)分析和歸納文法12345……重復(fù)且相連的數(shù)字ABCDE……重復(fù)且相連的字母+、-、*、/、(、)、#：?jiǎn)蝹€(gè)字符的運(yùn)算符“空格”……：（連續(xù)的）空白最直接的文法整數(shù)::=數(shù)字?jǐn)?shù)字?jǐn)?shù)字……（一個(gè)或多個(gè)）常量::=字母字母字母

……（一個(gè)或多個(gè)）數(shù)字::=0或1或2或……或9字母::=A或B或C或……或Z加號(hào)::=‘+’減號(hào)::=‘-’LEX：實(shí)踐(3)分析和歸納文法LEX：實(shí)踐(4)乘號(hào)::=‘*’除號(hào)::=‘/’左括號(hào)::=‘(‘右括號(hào)::=‘)’結(jié)束符號(hào)::=‘#’空白::=‘‘‘‘……（一個(gè)或多個(gè)）LEX：實(shí)踐(4)乘號(hào)::=‘*’LEX：實(shí)踐(5)化簡(jiǎn)為3型文法（正則文法）正則表達(dá)式整數(shù)::=[0-9]+常量::=[A-Z]+空白::=[]+加號(hào)::=\+減號(hào)::=\-乘號(hào)::=\*除號(hào)::=\/左括號(hào)::=\(右括號(hào)::=\)結(jié)束符號(hào)::=\#LEX：實(shí)踐(5)化簡(jiǎn)為3型文法（正則文法）LEX：實(shí)踐(6)設(shè)計(jì)動(dòng)作yylex()的返回值，不再是數(shù)值，而是枚舉NUMBER、CONSTANT、OP_ADD、OP_SUB、OP_MUL、OP_DIV、OP_LPA、OP_RPA、END這些枚舉在yacc中被看做單詞（token）對(duì)于空白，忽略。即yylex()返回的一定是非空白當(dāng)前獲取的單詞的內(nèi)容，通過(guò)yytext取得。設(shè)計(jì)接口yywrap()：返回1，分析完源程序就“撤”yyin：Lex的輸入文件。提供FILE*，它自己讀。LEX：實(shí)踐(6)設(shè)計(jì)動(dòng)作LEX：實(shí)踐(7)寫lex源文件lex源文件格式規(guī)則：正則表達(dá)式[a-z]：a|b|c|……|z[aceg]：a|c|e|ga，a+，a*，a?......動(dòng)作：C語(yǔ)言的程序段用Lex生成lex.yy.c%{C語(yǔ)言的定義、聲明%}%%/*單詞定義*/定義1{動(dòng)作1};定義2{動(dòng)作2};%%其他C代碼Lexlex.yy.cLEX：實(shí)踐(7)寫lex源文件%{Lexlex.yy.cLEX：實(shí)踐(8)改寫yacc源文件從yylex()讀到的是單詞類型從yytext讀單詞內(nèi)容用yacc-d生成y.tab.h，定義單詞類型%{C語(yǔ)言的定義、聲明%}/*YACC定義*/%%/*規(guī)則定義*/規(guī)則1{動(dòng)作1};規(guī)則2{動(dòng)作2};%%其他C代碼YACCy.tab.cy.tab.hLEX：實(shí)踐(8)改寫yacc源文件%{YACCy.tab.改寫主控程序主控程序和y.tab.c的新增接口get_constant：解析yytext的常量字符串為數(shù)值get_number：解析yytext的整數(shù)字符串為數(shù)值intyylex(){……}char*yytextLEX：實(shí)踐(9)intmain(){……}intget_constant()intget_number()voidyyerror()intyywrap()XXXXYYYYintyyparse(){……}ZZZZy.tab.clex.yy.cmain.c改寫主控程序intyylex()LEX：實(shí)踐(9)intLEX：實(shí)踐(10)聯(lián)編編譯連接cc-cy.tab.ccc-clex.yy.ccc-cmain.ccc-ocalcmain.o

y.tab.olex.yy.o測(cè)試創(chuàng)建一個(gè)文件test.ca內(nèi)容：LONG-CHAR*120/(CHAR+LONG+1)+30*(2+CHAR)#運(yùn)行：./calctest.ca結(jié)果：Result=74內(nèi)容：LONG-UNKNOWN#結(jié)果：ERROR:SyntaxerrorLEX：實(shí)踐(10)聯(lián)編選擇：比較手工vs自動(dòng)語(yǔ)法的文法類型自動(dòng)：2、3型文法，LL(1)、LALR(1)、GLR分析器手工：無(wú)絕對(duì)限制，LL(k)、LR(k)分析器語(yǔ)法復(fù)雜度自動(dòng)：無(wú)絕對(duì)限制，對(duì)復(fù)雜度不敏感手工：越復(fù)雜越困難（C++）語(yǔ)法擴(kuò)展方向編程設(shè)計(jì)水平性能要求自動(dòng)：語(yǔ)法復(fù)雜時(shí)優(yōu)勢(shì)漸顯，優(yōu)化有限手工：語(yǔ)法簡(jiǎn)單時(shí)性能佳，優(yōu)化潛力大選擇：比較手工vs自動(dòng)選擇：參考手工分析器GCC詞法、語(yǔ)法分析器LLVM/Clang詞法、語(yǔ)法分析器LCC詞法、語(yǔ)法分析器OpenWatcomCC詞法、語(yǔ)法分析器其他語(yǔ)言分析/解釋器（Python、Perl……）自動(dòng)分析器Java詞法、語(yǔ)法分析器（ANTLR）自定義格式的語(yǔ)言、配置文件解析實(shí)驗(yàn)性語(yǔ)言分析器選擇：參考手工分析器學(xué)習(xí)資料理論教材《程序設(shè)計(jì)語(yǔ)言編譯原理》，陳火旺★★★《編譯原理》，呂映芝

★★★★★《編譯原理及編譯程序構(gòu)造》，金茂忠，高仲儀★★★《CraftingACompilerWithC》，CharlesN.Fischer

★★★★★《形式語(yǔ)言與自動(dòng)機(jī)》實(shí)踐教材《可變目標(biāo)編譯器：設(shè)計(jì)與實(shí)現(xiàn)》，ChrisW.Fraser★★★★★《Lex與Yacc》，JohnR.Levine,TonyMason★★★★★學(xué)習(xí)資料理論教材完Thanks!完Thanks!編譯中的分析技術(shù)和工具簡(jiǎn)介編譯中的分析技術(shù)和工具簡(jiǎn)介大綱概念文法分析遞歸下降分析LL分析LR分析YACCLex選擇學(xué)習(xí)資料大綱概念概念：編譯的地位《降龍十八掌》《太公兵法》理論、形式化經(jīng)驗(yàn)、積累操作系統(tǒng)編譯器概念：編譯的地位《降龍十八掌》《太公兵法》理論、形式化經(jīng)驗(yàn)操概念：編譯編譯Compile翻譯【計(jì)】totranslateinstructions……編纂collectandputtogetherintmain(){inta,b;a=(int)&b;printf(“%x\n”,a);return0;}B801FEFF0E4BC6F8FE……C++Compiler源代碼編譯器目標(biāo)代碼概念：編譯編譯Compileintmain()B801概念：編譯基本過(guò)程#defineMAX256#defineTEXT“Hello”intmain(){inta=MAXcharx[]=TEXT……B801FEFF0E4BC6F8FE……預(yù)處理優(yōu)化代碼生成分析Pre-ProcessParseOptimizeGenerateintmain(){inta=256charx[]=“Hello”……有向無(wú)環(huán)圖DAG抽象語(yǔ)法樹(shù)AST中間代碼IntermediateCode源代碼Source目標(biāo)代碼Target概念：編譯基本過(guò)程#defineMAX256B801概念：解釋解釋InterpretInterpret：口譯#!/bin/shecho“Begin”catfile|lessmakesed…………Bash源代碼解釋器執(zhí)行動(dòng)作catmakesedless概念：解釋解釋Interpret#!/bin/shBash概念：解釋基本過(guò)程執(zhí)行分析ParseRun#!/bin/shecho“Begin”catfile|lessmakesed…………概念：解釋基本過(guò)程執(zhí)行分析ParseRun#!/bin/sh概念：分析分析Parse序列化到結(jié)構(gòu)化詞法分析、語(yǔ)法分析、語(yǔ)義分析FUNCTIONfact(x)IFx=0THENRETURN1ENDIFs=1FORi=1TOxs=s*iNEXTiENDFUNCTIONPRINTfact(10)PRINTfact(8)……概念：分析分析ParseFUNCTIONfact(x)文法文法Grammar文法的概念文法和語(yǔ)言文法的表示Chomsky文法分類文法文法Grammar文法：文法的概念（1）標(biāo)準(zhǔn)句型：（定語(yǔ)）主語(yǔ)（狀語(yǔ)）謂語(yǔ)（補(bǔ)語(yǔ)）（定語(yǔ)）賓語(yǔ)主語(yǔ)：名詞/代詞謂語(yǔ)：動(dòng)詞賓語(yǔ)：名詞/代詞定語(yǔ)：形容詞/代詞狀語(yǔ)：副詞補(bǔ)語(yǔ)：助詞名詞：蘋果、人、水、船……動(dòng)詞：揍、吃、喝、喜歡……代詞：我、它、那個(gè)形容詞：紅、壞、賤……副詞：飛快的、狠狠的、很……助詞：了、吧、嗎……我吃紅蘋果我飛快的吃蘋果我狠狠的揍了那個(gè)賤人我吃船蘋果吃了我我很喜歡壞蘋果文法：文法的概念（1）標(biāo)準(zhǔn)句型：（定語(yǔ)）主語(yǔ)（狀語(yǔ)）謂語(yǔ)（補(bǔ)文法：文法的概念（2）標(biāo)準(zhǔn)句型：（定語(yǔ)）主語(yǔ)（狀語(yǔ)）謂語(yǔ)（補(bǔ)語(yǔ)）（定語(yǔ)）賓語(yǔ)主語(yǔ)：名詞/代詞謂語(yǔ)：動(dòng)詞賓語(yǔ)：名詞/代詞……名詞：蘋果、人、水、船……動(dòng)詞：揍、吃、喝、喜歡……代詞：我、它、那個(gè)……我吃紅蘋果我飛快的吃蘋果我狠狠的揍了那個(gè)賤人開(kāi)始符號(hào)終結(jié)符Terminal非終結(jié)符Non-Terminal產(chǎn)生式Production句子推導(dǎo)、表達(dá)規(guī)約、分析文法：文法的概念（2）標(biāo)準(zhǔn)句型：（定語(yǔ)）主語(yǔ)（狀語(yǔ)）謂語(yǔ)（補(bǔ)文法：文法的概念（3）Program：ConditionStatementCommentCondition：ifExpressionStatement：printValueComment：#Text……Expression：Expression=ExpressionValue：a|b|c|d……Text：Hello|Good|How……ifa=bprintHelloifb=cprintGood……開(kāi)始符號(hào)終結(jié)符Terminal非終結(jié)符Non-Terminal產(chǎn)生式Production句子推導(dǎo)、表達(dá)規(guī)約、分析文法：文法的概念（3）Program：Condition文法：文法和語(yǔ)言文法的形式化定義文法：四元組(S,VN,VT,P)句子：文法的一個(gè)推導(dǎo)語(yǔ)言文法中所有句子的集合XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX文法：文法和語(yǔ)言文法的形式化定義XXXXXXXXXXXXXX文法：文法的表示產(chǎn)生式：α→β句子→主語(yǔ)謂語(yǔ)賓語(yǔ)A→AaA→BcB→bbAB→AcdBNF范式（Backus-NaurForm）句子::=主語(yǔ)謂語(yǔ)賓語(yǔ)<A>::=<A>a<B>::=<A>b<B>c<A>d擴(kuò)展BNF范式（EBNF范式）<A>::=<A>a|<B>c{<D>}*|ab+c|……文法：文法的表示產(chǎn)生式：α→β文法：文法的Chomsky分類(1)不同特點(diǎn)的產(chǎn)生式、不同的表達(dá)能力3型文法（正則文法）RegularGrammar產(chǎn)生式簡(jiǎn)單<A>::=a<A><A>::=a表達(dá)能力很弱a、aa、aaa、aaaa、……ac、abc、abbc、abbbc、abbbbc……沒(méi)有“記憶”能力等價(jià)于確定性有限自動(dòng)機(jī)（DFA）多用于定義單詞（token）文法：文法的Chomsky分類(1)不同特點(diǎn)的產(chǎn)生式、不同的文法：文法的Chomsky分類(2)3型文法的語(yǔ)言表達(dá)能力示例嘰嘰嘰嘰嘰嘰嘰嘰……嘰嘰嘰嘰吱吱吱吱……吱吱嘰嘰吱吱……文法：文法的Chomsky分類(2)3型文法的語(yǔ)言表達(dá)能力示文法：文法的Chomsky分類(3)3型文法的語(yǔ)言分析能力示例FUNCTIONfact(x)IFx=0THENRETURN1ENDIFs=1FORi=1TOxs=s*iNEXTiENDFUNCTIONPRINTfact(10)PRINTfact(8)……FUNCTIONfact(x)IF……PROGRAM::=TOKENSP*TOKEN::=ALPHA*ALPHA::=a|b|c|…|zALPHA::=A|B|C|…|Z文法：文法的Chomsky分類(3)3型文法的語(yǔ)言分析能力示文法：文法的Chomsky分類(4)2型文法（上下文無(wú)關(guān)文法）ContextFreeGrammarabbr.CFG產(chǎn)生式左部只有一個(gè)非終結(jié)符（|α|=1）<A>::=a<A><B><C>d<B>::=<A>x<B>yz表達(dá)能力較強(qiáng)IFa>bTHENa=bELSEb=astaticintprintk(constchar*fmt,…);有一定的“記憶”能力多用于定義簡(jiǎn)單語(yǔ)法（syntax）文法：文法的Chomsky分類(4)2型文法（上下文無(wú)關(guān)文法文法：文法的Chomsky分類(5)2型文法的語(yǔ)言表達(dá)能力示例媽媽，抱抱(我)我要(那個(gè)(娃娃))哇哇哇哇嗚嗚嗚嗚……文法：文法的Chomsky分類(5)2型文法的語(yǔ)言表達(dá)能力示文法：文法的Chomsky分類(6)2型文法的語(yǔ)言分析能力示例FUNCTIONfact(x)IFx=0THENRETURN1ENDIFs=1FORi=1TOxs=s*iNEXTiENDFUNCTIONPRINTfact(10)PRINTfact(8)……PROGRAMxsRETURN1IF……PROGRAM::=FUNCTIONFUNCTION::=FUNCSTENDST::=IFEXPRRENDIFEXPR::=EXPR=EXPR……FUNCTIONTHEN……賦值=0文法：文法的Chomsky分類(6)2型文法的語(yǔ)言分析能力示文法：文法的Chomsky分類(7)1型文法（上下文相關(guān)文法）ContextSensitiveGrammarabbr.CSG產(chǎn)生式左部長(zhǎng)度小于右部長(zhǎng)度（|α|≤|β|）<A>::=a<A><B><C>da<B>c::=<A>x<B>yz<C><B>m::=xyzu推導(dǎo)是“收斂”的表達(dá)能力更強(qiáng)能表達(dá)語(yǔ)境的概念可定義復(fù)雜語(yǔ)法和部分語(yǔ)義（semantics）文法：文法的Chomsky分類(7)1型文法（上下文相關(guān)文法文法：文法的Chomsky分類(8)1型文法的語(yǔ)言表達(dá)能力示例今王與百姓百姓同樂(lè)，則王矣王欲行王政，則勿毀之矣梁惠王齊宣王成為老大王者文法：文法的Chomsky分類(8)1型文法的語(yǔ)言表達(dá)能力示文法：文法的Chomsky分類(9)1型文法的語(yǔ)言分析能力示例intx;intmain(){intx;x=4;func();return0;}voidfunc(){x=4;}賦值ESP+[x]4賦值DS+[x]4文法：文法的Chomsky分類(9)1型文法的語(yǔ)言分析能力示文法：文法的Chomsky分類(10)0型文法（短語(yǔ)文法）產(chǎn)生式?jīng)]有限制a<A><B><C>::=ad<B>::=<A>x<B><C><B>m::=x表達(dá)能力最強(qiáng)等價(jià)于圖靈機(jī)文法：文法的Chomsky分類(10)0型文法（短語(yǔ)文法）文法：文法的Chomsky分類(11)喬姆斯基文法分類總結(jié)文法類型用處0型文法短語(yǔ)文法圖靈機(jī)1型文法上下文相關(guān)文法部分語(yǔ)義、復(fù)雜語(yǔ)法2型文法上下文無(wú)關(guān)文法語(yǔ)法3型文法正則文法單詞、簡(jiǎn)單匹配表達(dá)能力限制規(guī)則文法：文法的Chomsky分類(11)喬姆斯基文法分類總結(jié)文分析：概念(1)分析Parse序列化到結(jié)構(gòu)化理解按照指定的文法去理解給定的句子語(yǔ)義(Semantics)檢查語(yǔ)法(Syntax)分析詞法(Lexical)分析分析：概念(1)分析Parse分析：概念(2)完全分析樹(shù)結(jié)構(gòu)太復(fù)雜intx;intmain(){intx;x=4;func();return0;}voidfunc(){x=4;}賦值ESP+[x]4DS+[x]mainfunc()返回函數(shù)定義=范圍調(diào)用=賦值4范圍0變量定義x程序分析：概念(2)完全分析intx;賦值ESP+[x]4DS分析：概念(3)分工語(yǔ)法分析：主導(dǎo)詞法分析：支撐語(yǔ)義分析：指導(dǎo)、檢查語(yǔ)法樹(shù)詞法詞法詞法語(yǔ)義檢查分析：概念(3)分工語(yǔ)法樹(shù)詞法詞法詞法語(yǔ)義檢查分析：詞法分析詞法分析用正則文法去理解“字符序列”，提供“單詞序列”intx;intmain(){intx;x=4;func();return0;}voidfunc(){x=4;}intintmainmainx=x=分析：詞法分析詞法分析intx;intintmainmai分析：語(yǔ)法分析語(yǔ)法分析用2型文法去理解“單詞序列”intx;intmain(){intx;x=4;func();return0;}voidfunc(){x=4;}賦值返回函數(shù)定義調(diào)用賦值變量定義程序分析：語(yǔ)法分析語(yǔ)法分析intx;賦值返回函數(shù)定義調(diào)用賦值變分析：分析方法詞法分析直接分析構(gòu)造確定有限狀態(tài)機(jī)分析語(yǔ)法分析遞歸下降分析法LL分析法LR分析法算符優(yōu)先分析法……分析：分析方法詞法分析遞歸下降分析：下降下降逐級(jí)下降分工每一級(jí)均為函數(shù)調(diào)用1+2*3+4/5表達(dá)式因子+因子1*+因子/2345遞歸下降分析：下降下降1+2*3+4/5表達(dá)式因子+因子1*遞歸下降分析：遞歸遞歸語(yǔ)法為遞歸定義時(shí)，調(diào)用也遞歸調(diào)用嚴(yán)格定義的遞歸接口1+2*(3+4*5)表達(dá)式因子1*+因子2表達(dá)式因子3+45*遞歸下降分析：遞歸遞歸1+2*(3+4*5)表達(dá)式因子1*+遞歸下降分析遞歸下降分析結(jié)構(gòu)簡(jiǎn)單、自然編碼容易語(yǔ)言不復(fù)雜時(shí)性能極佳采用遞歸下降作為前端的著名的C編譯器：LCCGCC（>3.0）CCompilerOpenWatcomCCompilerLLVM/Clang……遞歸下降分析遞歸下降分析LL分析法(1)LL：Left-Left從左向右讀入單詞從左向右分析遞歸下降分析法即為L(zhǎng)L分析法的一種特例LL(k)：提前掃描k個(gè)單詞LL(1)：提前查看1個(gè)單詞，最常用的LL分析法1+2+3+411+1+233+3+366+6+410LL分析法(1)LL：Left-Left1+2+3+411+LL分析法(2)LL(1)分析法自頂向下分析程序直觀可用狀態(tài)轉(zhuǎn)換表實(shí)現(xiàn)可用遞歸下降實(shí)現(xiàn)易于手工實(shí)現(xiàn)LL分析法(2)LL(1)分析法LR分析法(1)LR：Left-RightbyDonaldKnuth,1965從左向右讀入單詞從右向左分析LR(k)：提前查看k個(gè)單詞LALR(1)：LR(1)加約束，最常用的LR分析法1+2+3+411+1+21+2+1+2+3+1+2+3+4101+2+71+9LR分析法(1)LR：Left-Right1+2+3+411LR分析法(2)LALR(1)分析法自底向上的分析用二維狀態(tài)轉(zhuǎn)換表實(shí)現(xiàn)轉(zhuǎn)換表構(gòu)造過(guò)程復(fù)雜，難以手工實(shí)現(xiàn)自己維護(hù)較大的棧（“記憶”的多）可表達(dá)的語(yǔ)法范圍比LL分析法廣LL和LR的兼容問(wèn)題int

foo(){x=4;return1;}int

bar(){x=8;return1;}……if

(foo()&&bar()){printf(“x=%d\n”,x);}LR分析法(2)LALR(1)分析法intfoo(){YACC：概念(1)背景寫一個(gè)編譯器前端很困難大量編譯器前端的工作重復(fù)形式語(yǔ)言理論成熟MULTICS項(xiàng)目LALR分析法“很好很強(qiáng)大”手工構(gòu)造狀態(tài)轉(zhuǎn)換表很困難構(gòu)造狀態(tài)轉(zhuǎn)換表的方法較機(jī)械YACCYACC：概念(1)背景YACCYACC：概念(2)YetAnotherCompiler’sCompilerbyStephenC.Johnson,1975,BellLab神一般的工作人編譯器程序苦力YACC神?YACC：概念(2)YetAnotherCompilerYACC：概念(3)YACC輸入一個(gè)CFG文法輸出一個(gè)LALR分析器（C語(yǔ)言實(shí)現(xiàn)）與主程序結(jié)合，成為一個(gè)編譯器/解釋器AT&TYacc,BerkeleyYacc,GNUBison……grammar.yYACCy.tab.cCCmain.c編譯器/解釋器源程序……YACC：概念(3)YACCgrammar.yYACCy.tYACC：實(shí)踐(1)實(shí)踐任務(wù)：簡(jiǎn)單的四則混合運(yùn)算計(jì)算器calc例如：1+(2+3)*6/5-4*6從文件中讀入源程序源程序?yàn)橐粋€(gè)混合運(yùn)算式程序以#結(jié)尾運(yùn)算數(shù)為個(gè)位數(shù)運(yùn)算符為+、-、*、/和括號(hào)(、)分析完后執(zhí)行運(yùn)算，打印出結(jié)果9-8*7/(1+2+1)+4*(2+5)#calcsource.calc23YACC：實(shí)踐(1)實(shí)踐任務(wù)：簡(jiǎn)單的四則混合運(yùn)算計(jì)算器calYACC：實(shí)踐(2)分析文法，歸納語(yǔ)法1+2*(3+4*5)+6括號(hào)里和整個(gè)表達(dá)式是同構(gòu)關(guān)系乘除運(yùn)算優(yōu)先級(jí)較高加減運(yùn)算優(yōu)先級(jí)最低最直接的文法表達(dá)式::=因子+-因子+-因子+-……（一個(gè)或多個(gè)）因子::=因數(shù)*/因數(shù)*/因數(shù)*/

……（一個(gè)或多個(gè)）因數(shù)::=數(shù)字因數(shù)::=(表達(dá)式)YACC：實(shí)踐(2)分析文法，歸納語(yǔ)法YACC：實(shí)踐(3)化簡(jiǎn)為2型文法（CFG）BNF/EBNF表示的產(chǎn)生式（盡量用右遞歸）程序::表達(dá)式‘#’表達(dá)式::=表達(dá)式+因子表達(dá)式::=表達(dá)式-因子表達(dá)式::=因子因子::=因子*因數(shù)因子::=因子/因數(shù)因子::=因數(shù)因數(shù)::=數(shù)字因數(shù)::=‘(’表達(dá)式‘)’數(shù)字::‘0’……數(shù)字::‘9’YACC：實(shí)踐(3)化簡(jiǎn)為2型文法（CFG）YACC：實(shí)踐(4)設(shè)計(jì)動(dòng)作每分析完一條產(chǎn)生式則立即運(yùn)算例如分析……7*2……：數(shù)字::=‘7’，將“數(shù)字”的值設(shè)為7因數(shù)::=數(shù)字，將“因數(shù)”的值設(shè)為“數(shù)字”值，即7因子::=因數(shù)，將“因子”的值設(shè)為“因數(shù)”值，即7數(shù)字::=‘2’，將“數(shù)字”的值設(shè)為2因數(shù)::=數(shù)字，將“因數(shù)”的值設(shè)為“數(shù)字”值，即2因子::=因子*因數(shù)，將“因子”的值設(shè)為7*2即14……程序::=表達(dá)式#，將表達(dá)式的值XXXX打印出來(lái)YACC：實(shí)踐(4)設(shè)計(jì)動(dòng)作YACC：實(shí)踐(5)寫yacc源文件yacc源文件格式規(guī)則：類似EBNF格式動(dòng)作：C語(yǔ)言的程序段用YACC生成y.tab.c%{C語(yǔ)言的定義、聲明%}/*YACC定義*/%%/*規(guī)則定義*/規(guī)則1{動(dòng)作1};規(guī)則2{動(dòng)作2};%%其他C代碼YACCy.tab.cYACC：實(shí)踐(5)寫yacc源文件%{YACCy.tab.YACC：實(shí)踐(6)寫主控程序主控程序和y.tab.c的主要接口yylex：分析器調(diào)用yylex讀入字符（單詞）序列yyerror：當(dāng)分析錯(cuò)誤時(shí)，分析器調(diào)用該函數(shù)yyparse：開(kāi)始分析函數(shù)，由主控程序調(diào)用intmain(){……}intyylex(){……}voidyyerror(){……XXXXYYYYyyparse(){……}ZZZZy.tab.c主控程序YACC：實(shí)踐(6)寫主控程序intmain()XXXXYACC：實(shí)踐(7)聯(lián)編編譯連接cc-cy.tab.ccc-cmain.ccc-ocalcmain.o

y.tab.o測(cè)試創(chuàng)建一個(gè)文件test.ca內(nèi)容：9-8*7/(1+2+1)+4*(2+5)#運(yùn)行：./calctest.ca結(jié)果：Result=23修改內(nèi)容：9-8*7/(1+2#運(yùn)行：./calctest.ca結(jié)果：ERROR:SyntaxerrorYACC：實(shí)踐(7)聯(lián)編YACC：實(shí)踐(8)問(wèn)題僅能識(shí)別1位數(shù)的數(shù)字（value:1|2|…99|…10000?）不能識(shí)別符號(hào)（value:A|B|…|Z|…|AB|…|ABC|?）加入這些功能使得狀態(tài)轉(zhuǎn)換表規(guī)模很大（N2）怎么辦？將數(shù)字、符號(hào)的識(shí)別功能“外包”給某個(gè)程序保持較小的狀態(tài)轉(zhuǎn)換表規(guī)模N2+M2<(N+M)2LEXYACC：實(shí)踐(8)問(wèn)題LEXLEX：概念(1)LEXLexicalParserGenerator，詞法分析器生成器目標(biāo)：配合YACCbyEricSchmidtandMichaelLesk,1975,BellLabAT&TLex,GNUFlex……LEX：概念(1)LEXLEX：概念(2)LEX輸入一個(gè)3型（正則）文法輸出一個(gè)單詞分析器與YACC結(jié)合，為YACC提供yylex()等接口grammar.yYACCy.tab.cCCmain.c編譯器/解釋器源程序……lexical.lLEXlex.yy.cy.tab.hLEX：概念(2)LEXgrammar.yYACCy.tabLEX：實(shí)踐(1)實(shí)踐任務(wù)1：簡(jiǎn)單的單詞分析器，配合YACC數(shù)字：1、10、124……常量：LONG、CHAR……從文件中讀入源程序，分析數(shù)字和符號(hào)提供yylex()，每調(diào)用一次得到一個(gè)單詞類型源程序?yàn)檩^復(fù)雜的混合運(yùn)算式120*LONG+32*(CHAR+2*LONG)#120*+32*+2*#)LONGCHAR(LONGLEX：實(shí)踐(1)實(shí)踐任務(wù)1：簡(jiǎn)單的單詞分析器，配合YACCLEX：實(shí)踐(2)實(shí)踐任務(wù)2：YACC和LEX實(shí)現(xiàn)更強(qiáng)大的計(jì)算器使YACC分析時(shí)能支持多位的整數(shù)使YACC能支持預(yù)定義的常量LONG=4CHAR=1LEX：實(shí)踐(2)實(shí)踐任務(wù)2：YACC和LEX實(shí)現(xiàn)更強(qiáng)大的計(jì)LEX：實(shí)踐(3)分析和歸納文法12345……重復(fù)且相連的數(shù)字ABCDE……重復(fù)且相連的字母+、-、*、/、(、