詞法分析正則表達(dá)式課件

詞法分析——正則表達(dá)式授課：胡靜10/14/20232004年12月28日1編譯原理詞法分析——正則表達(dá)式10/9/20232004年12月28目錄編譯器的結(jié)構(gòu)編譯的例子什么是詞法分析如何編寫一個(gè)詞法分析器正則表達(dá)式——用來(lái)描述tokens編寫一個(gè)詞法分析器的生成器10/14/20232編譯原理目錄編譯器的結(jié)構(gòu)10/9/20232編譯原理編譯器的應(yīng)用模型出錯(cuò)處理語(yǔ)法分析程序語(yǔ)義分析程序目標(biāo)代碼生成程序詞法分析程序中間代碼生成程序代碼優(yōu)化程序表格管理編譯的前端（FrontEnd）編譯的后端（BackEnd）10/14/20233編譯原理編譯器的應(yīng)用模型出語(yǔ)法分析程序語(yǔ)義分析程序目標(biāo)代碼生成程序詞以語(yǔ)法分析器為核心的編譯器模型語(yǔ)法分析器詞法分析器中間代碼生成器語(yǔ)義分析器一部分中間代碼輸入字符串程序入口初始化工作10/14/20234編譯原理以語(yǔ)法分析器為核心的編譯器模型語(yǔ)法分析器詞法分析器中間代碼生一個(gè)簡(jiǎn)單的編譯器結(jié)構(gòu)10/14/20235編譯原理一個(gè)簡(jiǎn)單的編譯器結(jié)構(gòu)10/9/20235編譯原理這個(gè)結(jié)構(gòu)是如何進(jìn)行工作的10/14/20236編譯原理這個(gè)結(jié)構(gòu)是如何進(jìn)行工作的10/9/20236編譯原理這個(gè)結(jié)構(gòu)是如何進(jìn)行工作的10/14/20237編譯原理這個(gè)結(jié)構(gòu)是如何進(jìn)行工作的10/9/20237編譯原理第一步：詞法分析10/14/20238編譯原理第一步：詞法分析10/9/20238編譯原理tokensIdentifiers:xy11elsen_i00Integers:21000-5005LFloatingpoint:2.00.00020.021.1e50.e-10Strings:“x”“Hesaid,\“Areyou?\””Comments:/**don’tchangethis**/Keywords:ifelsewhilebreakSymbols:+*{}++<<<[]>=10/14/20239編譯原理tokensIdentifiers:x特別的詞法分析器手寫代碼來(lái)產(chǎn)生tokens如何讀取標(biāo)識(shí)符tokens？10/14/202310編譯原理特別的詞法分析器手寫代碼來(lái)產(chǎn)生tokens10/9/2023Look-aheadCharacter一次掃描一個(gè)字符使用向前看字符(next)的方法來(lái)決定將要讀到的是什么類型的token，以及當(dāng)前這個(gè)token的結(jié)尾在何處。10/14/202311編譯原理Look-aheadCharacter一次掃描一個(gè)字符10特別的詞法分析器：高層循環(huán)10/14/202312編譯原理特別的詞法分析器：高層循環(huán)10/9/202312編譯原理問(wèn)題的提出如果只向前看一個(gè)字符，不能夠確定我們將要讀入的是哪種類型的token如果token的開頭是“i”，那么它一定是標(biāo)識(shí)符么？如果token的開頭是“2”，那么它一定是一個(gè)整型的常數(shù)么？如果我們通過(guò)上面的類似“插入”式的方法來(lái)寫識(shí)別token的程序，這樣的程序不容易寫正確，而且也不容易維護(hù)因此需要一個(gè)更加有原理性的方法：詞法分析器的生成器，可以自動(dòng)產(chǎn)生有效的詞法分析器。（例如lex，flex，Jlex）一般說(shuō)來(lái)，沒有限制的向前看是必要的10/14/202313編譯原理問(wèn)題的提出如果只向前看一個(gè)字符，不能夠確定我們將要讀入的是哪一些問(wèn)題如何明確的描述tokens2.e020.e-012.0000“”“x”“\\”“\”\’”如何將文本分割成tokensif(x==0)a=x<<1;if(x==0)a=x<1;10/14/202314編譯原理一些問(wèn)題如何明確的描述tokens10/9/202314編譯如何描述tokens我們可以使用正則表達(dá)式來(lái)描述程序設(shè)計(jì)語(yǔ)言中的tokens正則表達(dá)式(RE,RegularExpression)的定義如下：a ordinarycharacterstandsforitselfε theemptystringR|S eitherRorS(alternation),whereR,S=RERS RfollowedbyS(concatenation),whereR,S=RER* concatenationofaRERzeroormoretimes (R*=ε|R|RR|RRR|RRRR…)在實(shí)際形式中，會(huì)有優(yōu)先級(jí)的限制，因此可以加入一些括號(hào)。10/14/202315編譯原理如何描述tokens我們可以使用正則表達(dá)式來(lái)描述程序設(shè)計(jì)語(yǔ)言簡(jiǎn)單的例子正則表達(dá)式R描述的字符串的集合表示為L(zhǎng)(R)L(R)=由R定義的“語(yǔ)言”L(abc)={abc}L(hello|goodbye)={hello,goodbye}L(1(0|1)*)=所有的非零二進(jìn)制數(shù)我們可以用正則表達(dá)式來(lái)定義每種類型的token10/14/202316編譯原理簡(jiǎn)單的例子正則表達(dá)式R描述的字符串的集合表示為L(zhǎng)(R)10/一些RE的簡(jiǎn)寫R+

oneormorestringsfromL(R):R(R*)R?optionalR:(R|ε)[abce]oneofthelistedcharacters:(a|b|c|e)[a-z]onecharacterfromthisrange:(a|b|c|d|e|…|y|z)[^ab]anythingbutoneofthelistedchars[^a-z]onecharacternotfromthisrange10/14/202317編譯原理一些RE的簡(jiǎn)寫R+ 10/9/202317編譯原理簡(jiǎn)單的例子正則表達(dá)式digit=[0-9]posint=digit+int=-?posintreal=int(ε|(.posint)) =-?[0-9]+(ε|(.[0-9]+))[a-zA-Z_][a-zA-Z0-9_]*在L(R)中的字符串“0”“1”“2”“3”…“8”“412”…“-42”“1024”…“-1.56”“12”“1.0”Cidentifiers這種簡(jiǎn)寫方式不支持遞歸10/14/202318編譯原理簡(jiǎn)單的例子正則表達(dá)式在L(R)中的字符串這種簡(jiǎn)寫方式不支持遞如何切分文本只有RE是不夠的，還需要一些進(jìn)行選擇的規(guī)則大部分的語(yǔ)言，優(yōu)先選擇最長(zhǎng)的匹配當(dāng)最長(zhǎng)匹配長(zhǎng)度相同時(shí)，由優(yōu)先級(jí)決定RE’s+優(yōu)先級(jí)+最長(zhǎng)匹配規(guī)則=詞法分析器的定義10/14/202319編譯原理如何切分文本只有RE是不夠的，還需要一些進(jìn)行選擇的規(guī)則10/小結(jié)詞法分析器將文本流轉(zhuǎn)換成tokens特殊的詞法分析器不容易寫的正確，而且不易維護(hù)