詞法分析程序設(shè)計(jì)與自動(dòng)構(gòu)造

1、詞法分析程序設(shè)計(jì)與自動(dòng)構(gòu)造2011.10.121主要內(nèi)容詞法分析程序設(shè)計(jì)詞法分析程序自動(dòng)構(gòu)造21.詞法分析程序設(shè)計(jì)詞法分析總控程序見圖1。 界限符運(yùn)算符字母數(shù)字結(jié)束符“#”開始到輸入流中讀下一字符CharChar是什么？初始化標(biāo)識(shí)符和關(guān)鍵字詞法分析子程序無(wú)符號(hào)數(shù)詞法分析子程序運(yùn)算符詞法分析子程序界限符詞法分析子程序結(jié)束圖1 詞法分析總控程序3 若對(duì)自動(dòng)機(jī)的每一個(gè)狀態(tài)賦予一定的功能，并把其邊上的符號(hào)視為轉(zhuǎn)移條件，那么自動(dòng)機(jī)就成為一個(gè)程序了。以無(wú)符號(hào)數(shù)為例：給定語(yǔ)法圖2，構(gòu)造自動(dòng)機(jī)見圖3。 d.de+-d圖2 無(wú)符號(hào)數(shù)的語(yǔ)法圖4圖3 無(wú)符號(hào)數(shù)的自動(dòng)機(jī)1234560dd+-.ed.otherothe

2、rddothered7e5開始0N，P，j;1e數(shù)字d;N*10+dN是數(shù)字？Y 讀字符charNYN整型量標(biāo)記C1是嗎？ 讀字符char是e嗎？是嗎？1e 讀字符charYNYN 讀字符char是數(shù)字？Y數(shù)字d;N*10+dN；j+1j是數(shù)字？Y 讀字符charERRORNN實(shí)型量標(biāo)記C1是數(shù)字？Y數(shù)字d;P*10+dPY 讀字符charERRORNN實(shí)型量標(biāo)記C1N*10e*P-j t結(jié)束YN整數(shù)部分小數(shù)部分是嗎？是數(shù)字？指數(shù)部分N圖4 無(wú)符號(hào)數(shù)詞法分析流程圖最后可得到無(wú)符號(hào)數(shù)分析算法流圖見圖4。 62.詞法分析程序設(shè)計(jì)自動(dòng)構(gòu)造Flex簡(jiǎn)介Flex源文件分析Flex詞法分析程序設(shè)計(jì)自動(dòng)構(gòu)造

3、演示實(shí)驗(yàn)任務(wù)和要求 72.1 Flex簡(jiǎn)介FLEX通過(guò)讀取一個(gè)有規(guī)定格式的文本文件，輸出一個(gè)如下所示的C語(yǔ)言源程序。8Flex源文件格式LEX對(duì)源文件的格式要求非常嚴(yán)格，所以書寫時(shí)一定要注意。LEX的源文件由三個(gè)部份組成，每個(gè)部分之間用頂行的“%”分割，其格式如下：定義部份規(guī)則部份用戶附加C語(yǔ)言部份9 定義部分定義部份由C語(yǔ)言代碼、模式的宏定義組成。除宏定義外，定義部分的其余代碼必須用符號(hào)% 和 % 括起來(lái)。另外，flex使用的C語(yǔ)言庫(kù)文件和外部變量以及部分聲明的函數(shù)，也應(yīng)分別置于% 和 % 之內(nèi)。10例如下面是一個(gè)flex語(yǔ)言的說(shuō)明部分：% #include “stdio.h”int num

4、 = 0 %DIGIT 0-9ID A-Za-zA-Za-z0-9_*%注意：這里起標(biāo)識(shí)符作用的%和% 、%必須要頂行寫11規(guī)則部分規(guī)則部份是LEX源文件的核心部份，它包括一組模式和在生成分析器識(shí)別相應(yīng)模式后對(duì)相應(yīng)模式進(jìn)行處理的C語(yǔ)言動(dòng)作(Action)。格式如下：C語(yǔ)言代碼模式1 動(dòng)作1模式2 |模式3 動(dòng)作312用戶附加C語(yǔ)言部份支持規(guī)則動(dòng)作部分所需要的處理過(guò)程，是對(duì)規(guī)則部分中動(dòng)作的補(bǔ)充。FLEX對(duì)此部份不作任何處理，僅僅將其直接拷貝到輸出文件lex.yy.c的尾部。13Flex中模式的定義digit 0-9number (-|+)?digit+hexnumber 0 x(digit|a-

5、fA-F)+letter a-zA-Zidentifier (letter|_)(number|letter|_)* newline nwhitespace t+string *comment #*#14Flex中模式的定義-PL/0語(yǔ)言digit 0-9letter a-zA-Znumber digit+identifier letter(letter|digit)*wrongid (digit+)letter(letter|digit)*newline nwhitespace t+15Lex.yy.c中的全局變量和函數(shù)File *yyin /* 指向詞法分析器要接收的待分析程序的指 針。如

6、果不指定則默認(rèn)指向標(biāo)準(zhǔn)輸入終端（ 鍵盤）。如果我們待分析的程序是文件形式 我們可以將這個(gè)指針指向該文件的地址指針*/File *yyout /* 同上，唯一不同是該指針指向輸出的文件 。默認(rèn)指向標(biāo)準(zhǔn)輸出終端（屏幕）。我們 可通過(guò)重定向該指針改變輸出流方向。 */Char *yytext /* 指向識(shí)別的單詞的地址；用來(lái)保存掃描 一次匹配的字符串。*/Int yyleng /* 匹配的字符串中字符的個(gè)數(shù)。*/16Lex.yy.c中的全局變量和函數(shù)ECHO /* flex的默認(rèn)動(dòng)作，一般來(lái)說(shuō)是輸出字符串 */yywrap（） /* 掃描一次完后要調(diào)用的函數(shù)，返回一個(gè)值，當(dāng)這個(gè)值為1的時(shí)候分flex

7、就不再繼續(xù)掃描。*/yyrestart（） /* 重新定向flex的輸入 */17Flex源文件分析(test.l)%int wc = 0; /* word count */%a-zA-Z+ wc+; %int main(void) int n = yylex(); return n;int yywrap(void) printf(word count: %dn, wc); return 1;18Flex詞法分析產(chǎn)生器實(shí)現(xiàn)原理詞法分析器自動(dòng)生成器的核心是lex編譯器，lex編譯器的功能是將lex源程序變換為一個(gè)能識(shí)別該語(yǔ)言單詞的詞法分析器。而該詞法分析器像有窮自動(dòng)機(jī)一樣去識(shí)別處理單詞。19fl

8、ex詞法分析產(chǎn)生器實(shí)現(xiàn)原理基于lex源程序，lex編譯器的實(shí)現(xiàn)步驟大致是： 對(duì)lex源程序識(shí)別規(guī)則中的每個(gè)pi構(gòu)造一個(gè)相應(yīng)的NFA Ni。引入唯一初態(tài)S，從初態(tài)S通過(guò)弧將所有NFA Ni（i=1，n）連接成新的NFA N。、兩步實(shí)際是完成從正規(guī)式到非確定有限自動(dòng)機(jī)的構(gòu)造。 對(duì)NFA N確定化，產(chǎn)生DFA N。 DFA N 最小化。 給出控制程序。產(chǎn)生一個(gè)名為int yylex()的詞法分析函數(shù)，將之拷貝到輸出文件lex.yy.c中。20Flex詞法分析程序設(shè)計(jì)自動(dòng)構(gòu)造演示TestTest1Test221實(shí)驗(yàn)內(nèi)容和要求1、閱讀flex源文件test.l，test1.l然后生成相應(yīng)lex.yy.c

9、文件，編譯該文件生成相應(yīng)exe文件，然后運(yùn)行exe文件，觀察輸出。2、利用flex生成詞法分析程序，分別統(tǒng)計(jì)標(biāo)識(shí)符，數(shù)字和錯(cuò)誤標(biāo)識(shí)符的個(gè)數(shù)，并輸出到文件result.txt 標(biāo)識(shí)符：字母，數(shù)字和下劃線，僅以字母開始 數(shù)字：無(wú)符號(hào)數(shù)字 錯(cuò)誤標(biāo)識(shí)符：以數(shù)字開始后接字母，形如： “123a”， “62aa12a”22實(shí)驗(yàn)內(nèi)容和要求3.利用flex生成詞法分析程序，識(shí)別輸入程序中的關(guān)鍵字，標(biāo)識(shí)符，數(shù)字，運(yùn)算符、界符和錯(cuò)誤標(biāo)識(shí)符，并輸出到文件result.txt關(guān)鍵字：if then do while string int 標(biāo)識(shí)符：字母，數(shù)字和下劃線，僅以字母開始 數(shù)字：無(wú)符號(hào)數(shù)字 錯(cuò)誤標(biāo)識(shí)符：以數(shù)字開始后接字母，形如： “123a”， “62aa12a”運(yùn)算符：+ - * / = 界符: ( ) , ;23