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

詞法分析——正則表達(dá)式授課：胡靜2023年6月9日編譯原理2目錄編譯器的結(jié)構(gòu)編譯的例子什么是詞法分析如何編寫一個(gè)詞法分析器正則表達(dá)式——用來描述tokens編寫一個(gè)詞法分析器的生成器2023年6月9日編譯原理3詞法分析器的實(shí)現(xiàn)方案詞法分析程序的設(shè)計(jì)與實(shí)現(xiàn)2023年6月9日編譯原理42023年6月9日編譯原理5詞法生成器的自動(dòng)生成工具正則表達(dá)式與有窮自動(dòng)機(jī)2023年6月9日編譯原理6正則表達(dá)式的例子2023年6月9日編譯原理7令={a，b}，正規(guī)式 正規(guī)集a {a}ab {a,b}ab {ab}(ab)(ab) {aa,ab,ba,bb}a {,a,a,……任意個(gè)a的串}(ab) {,a,b,aa,ab……所有由a和b組成的串}(ab)(aabb)(ab) {上所有含有兩個(gè)相繼的a或兩個(gè)相繼的b組成的串}正則表達(dá)式的例子={a，b}，r=a(ab)定義的正規(guī)集:{a,aa,ab,abb,……}={d，，e，+，-},則上的正規(guī)式

d(dd)(e(+-)dd)表示的是無符號(hào)數(shù)的集合。其中d為0~9的數(shù)字。若兩個(gè)正規(guī)式所表示的正規(guī)集相同，則認(rèn)為二者等價(jià)。兩個(gè)等價(jià)的正規(guī)式U和V記為U=V。例如：U=(ab)，V=ba又如：U=b(ab),V=(ba)b

再如：U=(ab),V

=(ab)正則表達(dá)式的性質(zhì)設(shè)U、V和W都是正規(guī)式，則如下關(guān)系普遍成立：U|V=V|U （交換律）U|(V|W)=(U|V)|W （結(jié)合律）U(VW)=(UV)W （結(jié)合律）、U(V|W)=UV|UW （分配律）

(V|W)U=VU|WU；εU=Uε=Urr=r r=rrr… “或”的抽取律有窮自動(dòng)機(jī)有窮自動(dòng)機(jī)（也稱有限自動(dòng)機(jī)）作為一種識(shí)別裝置，它能準(zhǔn)確地識(shí)別正規(guī)集，即識(shí)別正規(guī)文法所定義的語言與正規(guī)式所表示的集合，引入有窮自動(dòng)機(jī)這個(gè)理論，正是為詞法分析程序的自動(dòng)構(gòu)造尋找特殊的方法和工具。有窮自動(dòng)機(jī)分為兩類：確定的有窮自動(dòng)機(jī)（DFA）和不確定的有窮自動(dòng)機(jī)（NFA）。其中“不確定”的含義是：對(duì)于某個(gè)輸入符號(hào)，在同一狀態(tài)上存在不止一種轉(zhuǎn)換。確定的和不確定的有窮自動(dòng)機(jī)都能而且僅能識(shí)別正規(guī)集，即它們能夠識(shí)別正規(guī)表達(dá)式所表示的語言。確定的有窮自動(dòng)機(jī)一個(gè)確定的有窮自動(dòng)機(jī)(DFA)M是一個(gè)五元式：M=(S,∑,δ,s0,F)其中S是一個(gè)有限集，它的每個(gè)元素稱為一個(gè)狀態(tài)?！剖且粋€(gè)有窮字母表，它的每個(gè)元素稱為一個(gè)輸入字符δ是一個(gè)從S×∑至S的單值映射。δ(s,a)=s’意味著：當(dāng)現(xiàn)行狀態(tài)為s、輸入字符為a時(shí)，將轉(zhuǎn)換到下一個(gè)狀態(tài)s’。我們稱s’為s的一個(gè)后繼狀態(tài)。s0∈S，是唯一的初態(tài)。FS，是一個(gè)終態(tài)集（可空）DFA的例子2023年6月9日編譯原理12DFA的例子2023年6月9日編譯原理13詞法分析程序的自動(dòng)生成器——LEX2023年6月9日編譯原理14LEX程序結(jié)構(gòu)一個(gè)LEX程序由如下三部分組成：聲明部分%%轉(zhuǎn)換規(guī)則%%輔助過程其中聲明部分包括變量聲明、符號(hào)常量聲明和正規(guī)定義。2023年6月9日編譯原理15LEX程序結(jié)構(gòu)-聲明部分2023年6月9日編譯原理16LEX程序結(jié)構(gòu)-聲明部分2023年6月9日編譯原理172023年6月9日編譯原理18LEX程序結(jié)構(gòu)-轉(zhuǎn)換規(guī)則LEX程序的轉(zhuǎn)換規(guī)則是如下形式的語句：

p1 {action1} p2 {action2} … pn {actionn}其中每一個(gè)pi是一個(gè)正則表達(dá)式，也稱為詞形。每一個(gè)actioni表示當(dāng)模式pi匹配上一個(gè)詞形后詞法分析器所要執(zhí)行的程序段，其基本動(dòng)作是返回單詞的類別編碼和單詞值。2023年6月9日編譯原理19LEX程序結(jié)構(gòu)LEX程序的第三部分包含action所需要的輔助過程。這些過程可以單獨(dú)編譯，并與詞法分析器一起裝載。由LEX創(chuàng)建的詞法分析器與語法分析器協(xié)同工作的方式如下：詞法分析器被語法分析器調(diào)用后，從尚未掃描的輸入字符串中讀字符，每次讀入一個(gè)字符，直到發(fā)現(xiàn)能與某個(gè)正規(guī)表達(dá)式pi匹配的最長(zhǎng)前綴。詞法分析器執(zhí)行actioni。通常actioni會(huì)將控制返回給語法分析器。然后如果不將控制交給語法分析器，詞法分析可以繼續(xù)發(fā)現(xiàn)更多的詞素，直到某個(gè)操作將控制返回給語法分析器。詞法分析器這種不斷查找詞素，直到以顯示的return調(diào)用結(jié)束工作的方式，使其可以方便的處理空白符和注釋。詞法分析器只返回記號(hào)給語法分析器，帶有與詞素相關(guān)信息的屬性值是通過全局變量yylval傳遞的。2023年6月9日編譯原理20LEX舉例正規(guī)表達(dá)式記號(hào)屬性值ws--ifif-thenthen-elseelse-idid指向符號(hào)表表項(xiàng)的指針numnum指向符號(hào)表表項(xiàng)的指針<relopLT<=relopLE=relopEQ<>relopNE>relopGT>=relopGE2023年6月9日編譯原理21LEX舉例%{ /*符號(hào)常數(shù)定義LT,LE,EQ,NE,GT,GE,IF,THEN,ELSE,ID,NUMBER,RELOP*/%} /*正規(guī)定義*/dilim [\t\n]ws {delim}+letter [A-Za-z]digit [0-9]id {letter}({letter}|{digit})*number {digit}+(\.{digit}+)?(E[+\-])?{digit}+)?%%2023年6月9日編譯原理22LEX舉例%%{ws} {/*沒有動(dòng)作和返回值*/}if {return(IF);}then {return(THEN);}else {return(ELSE);}{id} {yylval=install_id();return(ID);}{number} {yylval=install_num();return(NUMBER);}“<” {yylval=LT;return(RELOP);}“<=” {yylval=LE;return(RELOP);}“=” {yylval=EQ;return(RELOP);}“<>” {yylval=NE;return(RELOP);}“>” {yylval=GT;return(RELOP);}“>=” {yylval=GE;return(RELOP);}%%2023年6月9日編譯原理23LEX舉例%%install_id(){/*往符號(hào)表填入詞素的過程，yytext指向詞素的第一個(gè)字符，yyleng表示詞素的長(zhǎng)度。將詞素填入符號(hào)表，返回指向該詞素所在表項(xiàng)的指針*/}install_num(){/*與填寫詞素的過程類似，只不過詞素是一個(gè)數(shù)。*/}LEX的實(shí)現(xiàn)LEX的功能是根據(jù)LEX源程序構(gòu)造一個(gè)詞法分析程序，該詞法分析程序?qū)嵸|(zhì)上是一個(gè)有窮自動(dòng)機(jī)。LEX生成的詞法分析程序有上述兩部分構(gòu)成。LEX的功能是根據(jù)LEX源程序生成狀態(tài)轉(zhuǎn)換矩陣和控制程序202