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

詞法分析——正則表達(dá)式授課：胡靜10/14/20232004年12月28日1編譯原理詞法分析——正則表達(dá)式10/9/20232004年12月28目錄編譯器的結(jié)構(gòu)編譯的例子什么是詞法分析如何編寫一個(gè)詞法分析器正則表達(dá)式——用來描述tokens編寫一個(gè)詞法分析器的生成器10/14/20232編譯原理目錄編譯器的結(jié)構(gòu)10/9/20232編譯原理編譯器的應(yīng)用模型出錯(cuò)處理語法分析程序語義分析程序目標(biāo)代碼生成程序詞法分析程序中間代碼生成程序代碼優(yōu)化程序表格管理編譯的前端（FrontEnd）編譯的后端（BackEnd）10/14/20233編譯原理編譯器的應(yīng)用模型出語法分析程序語義分析程序目標(biāo)代碼生成程序詞以語法分析器為核心的編譯器模型語法分析器詞法分析器中間代碼生成器語義分析器一部分中間代碼輸入字符串程序入口初始化工作10/14/20234編譯原理以語法分析器為核心的編譯器模型語法分析器詞法分析器中間代碼生一個(gè)簡單的編譯器結(jié)構(gòu)10/14/20235編譯原理一個(gè)簡單的編譯器結(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特別的詞法分析器手寫代碼來產(chǎn)生tokens如何讀取標(biāo)識(shí)符tokens？10/14/202310編譯原理特別的詞法分析器手寫代碼來產(chǎn)生tokens10/9/2023Look-aheadCharacter一次掃描一個(gè)字符使用向前看字符(next)的方法來決定將要讀到的是什么類型的token，以及當(dāng)前這個(gè)token的結(jié)尾在何處。10/14/202311編譯原理Look-aheadCharacter一次掃描一個(gè)字符10特別的詞法分析器：高層循環(huán)10/14/202312編譯原理特別的詞法分析器：高層循環(huán)10/9/202312編譯原理問題的提出如果只向前看一個(gè)字符，不能夠確定我們將要讀入的是哪種類型的token如果token的開頭是“i”，那么它一定是標(biāo)識(shí)符么？如果token的開頭是“2”，那么它一定是一個(gè)整型的常數(shù)么？如果我們通過上面的類似“插入”式的方法來寫識(shí)別token的程序，這樣的程序不容易寫正確，而且也不容易維護(hù)因此需要一個(gè)更加有原理性的方法：詞法分析器的生成器，可以自動(dòng)產(chǎn)生有效的詞法分析器。（例如lex，flex，Jlex）一般說來，沒有限制的向前看是必要的10/14/202313編譯原理問題的提出如果只向前看一個(gè)字符，不能夠確定我們將要讀入的是哪一些問題如何明確的描述tokens2.e020.e-012.0000“”“x”“\\”“\”\’”如何將文本分割成tokensif(x==0)a=x<<1;if(x==0)a=x<1;10/14/202314編譯原理一些問題如何明確的描述tokens10/9/202314編譯如何描述tokens我們可以使用正則表達(dá)式來描述程序設(shè)計(jì)語言中的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á)式來描述程序設(shè)計(jì)語言簡單的例子正則表達(dá)式R描述的字符串的集合表示為L(R)L(R)=由R定義的“語言”L(abc)={abc}L(hello|goodbye)={hello,goodbye}L(1(0|1)*)=所有的非零二進(jìn)制數(shù)我們可以用正則表達(dá)式來定義每種類型的token10/14/202316編譯原理簡單的例子正則表達(dá)式R描述的字符串的集合表示為L(R)10/一些RE的簡寫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的簡寫R+ 10/9/202317編譯原理簡單的例子正則表達(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這種簡寫方式不支持遞歸10/14/202318編譯原理簡單的例子正則表達(dá)式在L(R)中的字符串這種簡寫方式不支持遞如何切分文本只有RE是不夠的，還需要一些進(jìn)行選擇的規(guī)則大部分的語言，優(yōu)先選擇最長的匹配當(dāng)最長匹配長度相同時(shí)，由優(yōu)先級(jí)決定RE’s+優(yōu)先級(jí)+最長匹配規(guī)則=詞法分析器的定義10/14/202319編譯原理如何切分文本只有RE是不夠的，還需要一些進(jìn)行選擇的規(guī)則10/小結(jié)詞法分析器將文本流轉(zhuǎn)換成tokens特殊的詞法分析器不容易寫的正確，而且不易維護(hù)