大連理工大學(xué)編譯原理PPT

溫故知新正規(guī)式計算機實現(xiàn)狀態(tài)轉(zhuǎn)換圖不確定有限自動機確定有限自動機等價子集構(gòu)造法最簡確定有限自動機等價非形式化描述的語言狀態(tài)列舉法合并不可區(qū)別狀態(tài)手工實現(xiàn)用正規(guī)式語法結(jié)構(gòu)來指導(dǎo)構(gòu)造過程？詞法分析器的生成器Lex是LEXicalcompiler的縮寫，是Unix環(huán)境下非常著名的工具,主要功能是生成一個詞法分析器的C源碼,描述規(guī)則采用正規(guī)式。描述詞法分析器的文件*.l，經(jīng)過lex編譯后，生成一個lex.yy.c的文件，然后由C編譯器編譯生成一個詞法分析器。LEX源程序經(jīng)過LEX處理，并經(jīng)過編譯，可以生成一個詞法分析器。這個詞法分析器的作用就好像有限自動機一樣，可以用來識別和產(chǎn)生單詞符號。2.5詞法分析器的生成器2.5詞法分析器的生成器

用Lex建立詞法分析器的步驟Lex編譯器Lex源程序lex.llex.yy.cC編譯器lex.yy.ca.outa.out輸入流記號序列2.5詞法分析器的生成器LEX將用戶輸入的表達(dá)式和動作序列轉(zhuǎn)化為宿主語言的源程序，經(jīng)過編譯后的程序即是詞法分析程序，被稱為yylex。LEX不是一種完整的語言，但是它可以嵌入到其他程序設(shè)計語言的源程序中。嵌入到LEX中的程序設(shè)計語言被稱為宿主語言。宿主語言用來處理LEX的輸出代碼，同時也可以由用戶添加一些必要的代碼輔以詞法分析。目前，LEX支持的宿主語言通常是C語言。2.5詞法分析器的生成器Lex程序包括三個部分

聲明％％翻譯規(guī)則％％輔助過程Lex程序的翻譯規(guī)則

p1 {動作1}p2 {動作2}… …pn {動作n}2.5詞法分析器的生成器例---聲明部分%{/*常量LT,LE,EQ,NE,GT,GE,WHILE,DO,ID,NUMBER,RELOP的定義*/%}/*

正規(guī)定義

*/delim [\t\n]ws {delim}+letter [AZaz]digit [09]id {letter}({letter}|{digit})*number {digit}+(\.{digit}+)?(E[+\]?{digit}+)?2.5詞法分析器的生成器例---翻譯規(guī)則部分{ws} {/*

沒有動作，也不返回*/}while {return(WHILE);}do {return(DO);}{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);}2.5詞法分析器的生成器例---輔助過程部分install_id(){ /*

把詞法單元裝入符號表并返回指針。

yytext指向該詞法單元的第一個字符，

yyleng給出的它的長度 */}install_num(){ /*

類似上面的過程，但詞法單元不是標(biāo)識符而是數(shù)*/}用Lex定義常規(guī)表達(dá)式

.匹配任意字符，除了\n-指范圍[A-Za-z0-9]$行的結(jié)尾{}模式可能出現(xiàn)的次數(shù)，例如A{1,3}表示可能出現(xiàn)1次或3次^(1)行的開始；(2)否定,操作符^只能出現(xiàn)在左中括號后的第一個字符位置處[^abc]

*|?+等常用的閉包，邏輯或等操作2.5詞法分析器的生成器Lex中重要的外部變量

yytext:外部字符數(shù)組，其內(nèi)容是當(dāng)前被某個規(guī)則匹配的字符串

yyleng:當(dāng)前yytext中的字符的個數(shù)例：

[a-zA-Z]+printf(“word=%s,length=%d”,yytext,yyleng)；另外[a-zA-Z]+printf(“%s”,yytext);可以簡寫成[a-zA-Z]+ECHO;2.5詞法分析器的生成器Lex中識別規(guī)則二義性處理

能匹配最多字符的規(guī)則優(yōu)先能匹配相同數(shù)目的字符的規(guī)則，書寫順序在前的優(yōu)先eg：integerkeywordaction...;[a?z]+identifieraction...;當(dāng)輸入為integers時，匹配[a?z]+Lex中識別規(guī)則二義性處理Lex程序分割輸入流同時不搜索每個表達(dá)式的所有可能匹配。每個字符計算一次且僅一次。例如，計算she和he在輸入文本中的出現(xiàn)次數(shù)：

shes++heh++\n|/*規(guī)則同下一行*/.;在這里最后兩個規(guī)則忽略除了he和she的所有東西。然而，因為she包含he，Lex不識別包含在she中的he的情況。Lex中識別規(guī)則二義性處理假設(shè)需要計算輸入文本中she中he的個數(shù)

she{s++;REJECT;}he{h++;}\n|/*規(guī)則同下一行*/.;因為she包括he，Lex通常不識別she中的he，因為一旦它處理過she，這些字符就過去了。有時候，用戶希望阻止這種選擇。動作REJECT表示“進(jìn)行下一次選擇”。它使得當(dāng)當(dāng)前規(guī)則被執(zhí)行后，其他的規(guī)則可以第二次被選擇。因此輸入指針的位置會被調(diào)整。2.5詞法分析器的生成器簡單的例子刪除輸入中每行結(jié)尾處所有空白符%%

[\t]+$;如果要將字符串中的空格或者制表符轉(zhuǎn)換為單個空格，需要增加一條規(guī)則：%%

[\t]+$;[\t]+printf(“”);2.5詞法分析器的生成器intnum_lines=0,num_chars=0;%%\n++num_lines;++num_chars;.++num_chars;%%main(){ yylex(); printf("#oflines=%d,#ofchars=%d\n",num_lines,num_chars);}上機實驗例子example.l2.5詞法分析器的生成器helloworldwoaitiananmenhelloworldilove上機實驗例子example.llex.yy.exe#oflines=3,#ofchars=49上機作業(yè)1、下載“軟件學(xué)院編譯原理實踐.zip”，閱讀教程中有關(guān)PL/0詞法分析器的源代碼。2、下載“Lex_一個詞法分析器的生成器(全文).doc”，閱讀有關(guān)Lex的內(nèi)容。3、下載“Lex和Yacc簡明教程.pdf”，閱讀教程中有關(guān)Lex和Yacc的內(nèi)容。4、下載“l(fā)ex_實驗.zip”，按照“flex說明.txt”要求完成如下上機題：1、編寫一個詞法分析器，它針對輸入文件，實現(xiàn)以下功能：

1）每遇到你的學(xué)號，就輸出你的名字，對于其他的串原樣輸出。

2）統(tǒng)計輸入文件中字母的數(shù)目。例如：（以肖永躍的上機題為例）：輸入文件如下所示：200213001helloworldwoaitiananmenhelloworldilove200213001輸出應(yīng)該如下所示：肖永欽helloworldwoaitiananmenhelloworldilove肖永欽#ofids=11,#ofchars=66下載“第二次上機作業(yè)_詞法分析”文檔上機作業(yè)本章要點源程序字符流順序組合詞法單元詞法記號模式非形式化描述形式化描述正規(guī)式字母組合串語言集合集合字母表名字連接指數(shù)和LUM連接LM閉包L*正閉包L+計算機實現(xiàn)狀態(tài)轉(zhuǎn)換圖不確定有限自動機確定有限自動機等價子集構(gòu)造法最簡確定有限自動機狀態(tài)列舉法合并不可區(qū)別狀態(tài)手工實現(xiàn)正規(guī)式語法結(jié)構(gòu)Lex作業(yè)答案習(xí)題2.3首尾均為0的二進(jìn)制串0，1組成的二進(jìn)制串，包括空串倒數(shù)第3位為0的二進(jìn)制串包含且僅包含3個1的二進(jìn)制串1的個數(shù)和0的個數(shù)均為偶數(shù)的二進(jìn)制串1、DFA，接受

0和1的個數(shù)都是偶數(shù)的字符串312011110000開始偶0偶1奇0奇1奇0偶1偶0奇1鞏固與提高2、敘述正規(guī)式(00|11)((01|10)(00|11)(01|10)(00|11))描述的語言。

答案：所有由偶數(shù)個0和偶數(shù)個1構(gòu)成的串。分析：該正規(guī)式的一個重要特點是，它是兩個字符一組來考慮的。正規(guī)式(00|11)表示的串的長度是偶數(shù)，每兩個字符一組的話，不是00就是11。再看正規(guī)式(01|10)(00|11)(01|10)，它表示的串由01或10開始，中間有若干組00或11，最后出現(xiàn)01或10。這樣的串仍然由偶數(shù)個0和偶數(shù)個1構(gòu)成，只不過第一組是01或10的話，那么一定還要有一組01或10才能保證它們的偶數(shù)性。顯然，正規(guī)式(01|10)(00|11)(01|10)(00|11)表示的串也仍然是由偶數(shù)個0和偶數(shù)個1構(gòu)成。這樣，可以判斷題目所給的正規(guī)式表示的語言的每個句子都是由偶數(shù)個0和偶數(shù)個1構(gòu)成。

11000011010011000011100110反過來還需要考慮，任何由偶數(shù)個0和偶數(shù)個1構(gòu)成的串是否都在這個語言中。這實際上是問，每個這樣的串，其結(jié)構(gòu)是否都符合正規(guī)式(00|11)((01|10)(00|11)(01|10)(00|11))所做的刻劃。我們可以這樣敘述由偶數(shù)個0和偶數(shù)個1構(gòu)成的串，從左向右，每兩個字符一組地考察它

1.由若干個（強調(diào)一下，可以是零個）00或11開始（這由正規(guī)式(00|11)描述）；

2．一旦出現(xiàn)一個01或10，那么經(jīng)過若干個00或11后，一定會出現(xiàn)一個01或10。這第二個01或10的后面可能還有若干個00或11，一直到串的結(jié)束，或者到再次出現(xiàn)01或10為止。如果串沒有結(jié)束的話，就是重復(fù)出現(xiàn)這里所描述的結(jié)構(gòu)（所以這由((01|10)(00|11)(01|10)(00|11))描述）。 因此正規(guī)式(00|11)((01|10)(00|11)(01|10)(00|11))描述的是偶數(shù)個0和偶數(shù)個1構(gòu)成的串。110000110100110000111001103、寫出語言“所有相鄰數(shù)字都不相同的非空數(shù)字串”的正規(guī)定義。答案：no_0-8 9no_0-7 (8|no_0-88)(no_0-88)(no_0-8|

)|no_0-8no_0-6 (7|no_0-77)(no_0-77)(no_0-7|

)|no_0-7no_0-5 (6|no_0-66)(no_0-66)(no_0-6|

)|no_0-6no_0-4 (5|no_0-55)(no_0-55)(no_0-5|

)|no_0-5no_0-3 (4|no_0-44)(no_0-44)(no_0-4|

)|no_0-4no_0-2 (3|no_0-33)(no_0-33)(no_0-3|

)|no_0-3no_0-1 (2|no_0-22)(no_0-22)(no_0-2|

)|no_0-2no_0 (1|no_0-11)(no_0-11)(no_0-1|

)|no_0-1answer (0|no_00)(no_00)(no_0|

)|no_04、將下圖的DFA極小化。aastart0123abbbbb4DFA0123aabbabbbstart45aaa,b加入死狀態(tài)后的DFA1、加入死狀態(tài)2、合并不可區(qū)分狀態(tài)先把狀態(tài)集分成非接受狀態(tài)集{0,1,2,3,5}和接受狀態(tài)集{4}這兩個子集。1．集合{4}不能再分解，我們看集合{0,1,2,3,5}。move({0,1,2,3,5},a)={1,2,5}

move({0,1,2,3,5},b)={3,4,5}由于b

轉(zhuǎn)換的結(jié)果{3,4,5}不是最初劃分的某個集合的子集，因此{(lán)0,1,2,3,5}需要再分，由于狀態(tài)1和狀態(tài)2的b轉(zhuǎn)換都到狀態(tài)4。因此狀態(tài)集合的進(jìn)一步劃分是：{1,2}，{0,3,5}和{4}2．由于move({1,2},a)={2,5}

move({1,2},b)={4}

move({0,3,5},a)={1,5}move({0,3,5},b)={3,5}顯然{1,2}和{0,3,5}需要再分，分別分成：{1}和{2}以及{0,3}和{5}3．由于 move({0,3},a)={1}

move({0,3},b)={3}因此不需要再分。這樣狀態(tài)0和狀態(tài)3合并成一個狀態(tài)，我們?nèi)?為代表，再刪去死狀態(tài)5，就得到該題的結(jié)果。正確做法！012bbbb4aastart最簡DFA最初的劃分是{0,1,2,3}和{4}。1．狀態(tài)集合的進(jìn)一步劃分是：{1,2}，{0,3}和{4}

2．忽略了死狀態(tài)的影響，會認(rèn)為它們都不需要再分錯誤做法！1、直接合并不可區(qū)分狀態(tài)01bbaastarta4一個不正確的結(jié)果aastart0123abbbbb4DFA5、為正規(guī)式(a|b)*a(a|b)構(gòu)造最簡DFA(課后習(xí)題(2.12(a))解：三種方法：方法一：

(1)根據(jù)算法2.4構(gòu)造NFA(2)根據(jù)算法2.2將NFADFA(3)根據(jù)算法2.3將DFA簡化方法二：

(1)直接構(gòu)造NFA

(2)根據(jù)算法2.2將NFADFA

A={0}

B={0,1}

C={0,1,2}

D={0,2}

(3)根據(jù)算法2.3將DFA簡化劃分狀態(tài)集{A,B}，{C,D};{A,B}面臨字母a時轉(zhuǎn)到{B,C}，由于B,C分屬于不同的狀態(tài)集，故此狀態(tài)集{A,B}需要進(jìn)一步劃分成{A}{B};考慮{C,D},它面臨字母a時