《詞法分析正則表達(dá)式課件》由會員分享，可在線閱讀，更多相關(guān)《詞法分析正則表達(dá)式課件（21頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。
1、,啊,啊,*,編譯原理,*,詞法分析正則表達(dá)式,授課：胡靜,12/15/2024,2004年12月28日,1,編譯原理,詞法分析正則表達(dá)式10/9/20232004年12月28,目錄,編譯器的結(jié)構(gòu),編譯的例子,什么是詞法分析,如何編寫一個(gè)詞法分析器,正則表達(dá)式用來描述tokens,編寫一個(gè)詞法分析器的生成器,12/15/2024,2,編譯原理,目錄編譯器的結(jié)構(gòu)10/9/20232編譯原理,編譯器的應(yīng)用模型,出,錯(cuò),處,理,語法分析程序,語義分析程序,目標(biāo)代碼生成程序,詞法分析程序,中間代碼生成程序,代碼優(yōu)化程序,表,格,管,理,編譯的前端,（Front End）,編譯的后端,（Back End
2、）,12/15/2024,3,編譯原理,編譯器的應(yīng)用模型出語法分析程序語義分析程序目標(biāo)代碼生成程序詞,以語法分析器為核心的編譯器模型,語法分析器,詞法分析器,中間代碼生成器,語義分析器,一部分中間代碼,輸入字符串,程序入口,初始化工作,12/15/2024,4,編譯原理,以語法分析器為核心的編譯器模型語法分析器詞法分析器中間代碼生,一個(gè)簡單的編譯器結(jié)構(gòu),12/15/2024,5,編譯原理,一個(gè)簡單的編譯器結(jié)構(gòu)10/9/20235編譯原理,這個(gè)結(jié)構(gòu)是如何進(jìn)行工作的,12/15/2024,6,編譯原理,這個(gè)結(jié)構(gòu)是如何進(jìn)行工作的10/9/20236編譯原理,這個(gè)結(jié)構(gòu)是如何進(jìn)行工作的,12/15/20
3、24,7,編譯原理,這個(gè)結(jié)構(gòu)是如何進(jìn)行工作的10/9/20237編譯原理,第一步：詞法分析,12/15/2024,8,編譯原理,第一步：詞法分析10/9/20238編譯原理,tokens,Identifiers:x y11 elsen _i00,Integers:2 1000 -500 5L,Floating point:2.0 0.00020 .02 1.1e5 0.e-10,Strings:“x”“He said,“Are you?”,Comments:/*dont change this*/,Keywords:if else while break,Symbols:+*+=,12/15/
4、2024,9,編譯原理,tokensIdentifiers:x,特別的詞法分析器,手寫代碼來產(chǎn)生tokens,如何讀取標(biāo)識符tokens？,12/15/2024,10,編譯原理,特別的詞法分析器手寫代碼來產(chǎn)生tokens10/9/2023,Look-ahead Character,一次掃描一個(gè)字符,使用向前看字符(next)的方法來決定將要讀到的是什么類型的token，以及當(dāng)前這個(gè)token的結(jié)尾在何處。,12/15/2024,11,編譯原理,Look-ahead Character一次掃描一個(gè)字符10,特別的詞法分析器：高層循環(huán),12/15/2024,12,編譯原理,特別的詞法分析器：高層循
5、環(huán)10/9/202312編譯原理,問題的提出,如果只向前看一個(gè)字符，不能夠確定我們將要讀入的是哪種類型的token,如果token的開頭是“i”，那么它一定是標(biāo)識符么？,如果token的開頭是“2”，那么它一定是一個(gè)整型的常數(shù)么？,如果我們通過上面的類似“插入”式的方法來寫識別token的程序，這樣的程序不容易寫正確，而且也不容易維護(hù),因此需要一個(gè)更加有原理性的方法：詞法分析器的生成器，可以自動產(chǎn)生有效的詞法分析器。（例如lex，flex，Jlex）,一般說來，沒有限制的向前看是必要的,12/15/2024,13,編譯原理,問題的提出如果只向前看一個(gè)字符，不能夠確定我們將要讀入的是哪,一些問題
6、,如何明確的描述tokens,2.e0 20.e-01 2.0000,“”“x”“”“”,如何將文本分割成tokens,if(x=0)a=x1;,if(x=0)a=x1;,12/15/2024,14,編譯原理,一些問題如何明確的描述tokens10/9/202314編譯,如何描述tokens,我們可以使用,正則表達(dá)式,來描述程序設(shè)計(jì)語言中的tokens,正則表達(dá)式(RE,Regular Expression)的定義如下：,a ordinary character stands for itself,the empty string,R|S either R or S(alternation),
7、where R,S=RE,RS R followed by S(concatenation),where R,S=RE,R*concatenation of a RE R zero or more times,(R*=|R|RR|RRR|RRRR),在實(shí)際形式中，會有優(yōu)先級的限制，因此可以加入一些括號。,12/15/2024,15,編譯原理,如何描述tokens我們可以使用正則表達(dá)式來描述程序設(shè)計(jì)語言,簡單的例子,正則表達(dá)式R描述的字符串的集合表示為L(R),L(R)=由R定義的“語言”,L(abc)=abc,L(hello|goodbye)=hello,goodbye,L(1(0|1)*)=
8、所有的非零二進(jìn)制數(shù),我們可以用正則表達(dá)式來定義每種類型的token,12/15/2024,16,編譯原理,簡單的例子正則表達(dá)式R描述的字符串的集合表示為L(R)10/,一些RE的簡寫,R,+,one or more strings from L(R):R(R*),R?,optional R:(R|),abce,one of the listed characters:(a|b|c|e),a-z,one character from this range:(a|b|c|d|e|y|z),ab,anything but one of the listed chars,a-z,one charact
9、er not from this range,12/15/2024,17,編譯原理,一些RE的簡寫R+10/9/202317編譯原理,簡單的例子,正則表達(dá)式,digit=0-9,posint=digit+,int=-?posint,real=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”,C identifiers,這種簡寫方式不支持遞歸,12/15/2024,18,編譯原理,簡單的例子正則表達(dá)式在L(R)中的字符串這
10、種簡寫方式不支持遞,如何切分文本,只有RE是不夠的，還需要一些進(jìn)行選擇的規(guī)則,大部分的語言，優(yōu)先選擇最長的匹配,當(dāng)最長匹配長度相同時(shí)，由優(yōu)先級決定,REs+優(yōu)先級+最長匹配規(guī)則=詞法分析器的定義,12/15/2024,19,編譯原理,如何切分文本只有RE是不夠的，還需要一些進(jìn)行選擇的規(guī)則10/,小結(jié),詞法分析器將文本流轉(zhuǎn)換成tokens,特殊的詞法分析器不容易寫的正確，而且不易維護(hù),對大部分語言來說，合法的tokens都可以由正則表達(dá)式方便的精確的定義。,12/15/2024,20,編譯原理,小結(jié)詞法分析器將文本流轉(zhuǎn)換成tokens10/9/20232,Thanks for your time!,Questions&Answers,12/15/2024,21,編譯原理,10/9/202321編譯原理,
詞法分析正則表達(dá)式課件
