1、第2章 outline一、詞法分析概述1，詞法分析程序的功能2，詞法分析相關(guān)的一些問題二、正則表達(dá)式三、有限自動機(jī)1，確定有限自動機(jī)DFA2，非確定有限自動機(jī)NFA，NFA到DFA的轉(zhuǎn)換3，DFA的化簡4，正則表達(dá)式到NFA的轉(zhuǎn)換四、詞法分析程序構(gòu)造4、正則表達(dá)式到NFA的轉(zhuǎn)換正則表達(dá)式和有限自動機(jī)都是形式語言，都可以描述程序設(shè)計語言的單詞結(jié)構(gòu)。正則表達(dá)式便于描述和理解有限自動機(jī)便于實現(xiàn)二者的描述能力是等價的，都描述正則語言，可相互轉(zhuǎn)換。一般地，設(shè)計詞法分析程序的步驟是：先用RE定義單詞結(jié)構(gòu)，然后將RE轉(zhuǎn)化成NFA，NFA再轉(zhuǎn)化成DFA，DFA化簡并實現(xiàn)得到詞法分析程序。RE到NFA轉(zhuǎn)換-Th

2、ompson算法轉(zhuǎn)換基于語言等價原則 是RE，L()= 是RE, L()= 任何 c , c 是RE, L(c)=c( A ), L( (A) )= L(A)S0S0S0ScNFA(A)RE到NFA轉(zhuǎn)換A B， L( A B )= L(A)L(B)NFA(A)NFA(B)RE到NFA轉(zhuǎn)換A | B，L( A | B )=L(A)L(B)NFA(A)NFA(B)RE到NFA轉(zhuǎn)換A*，L( A*) = L(A)*NFA(A)特別聲明上述規(guī)則只對具有一個開始狀態(tài)和一個終止?fàn)顟B(tài)的NFA有效;任何NFA都可以經(jīng)過變換符合上述要求; NFA RE到NFA的轉(zhuǎn)換例1：將正則表達(dá)式 (a | b)* a b

3、b (a | b)轉(zhuǎn)化成等價的NFA.abbbaabRE到NFA的轉(zhuǎn)換例2：將正則表達(dá)式a(a|b)*ab*a)b 轉(zhuǎn)化成等價的NFA.01234aaababbRE到NFA的轉(zhuǎn)換例3：將正則表達(dá)式 (0 | 1)*00轉(zhuǎn)化成等價的NFA.第2章 outline一、詞法分析概述1，詞法分析程序的功能2，詞法分析相關(guān)的一些問題二、正則表達(dá)式三、有限自動機(jī)1，確定有限自動機(jī)DFA2，非確定有限自動機(jī)NFA，NFA到DFA的轉(zhuǎn)換3，DFA的化簡4，正則表達(dá)式到NFA的轉(zhuǎn)換四、詞法分析程序構(gòu)造四、詞法分析程序構(gòu)造手工構(gòu)造詞法分析程序利用自動生成工具LEX-生成詞法分析程序手工構(gòu)造詞法分析程序開發(fā)詞法分析

4、程序用正則表達(dá)式定義詞法規(guī)則NFADFA轉(zhuǎn)換轉(zhuǎn)換最簡 DFA化簡實現(xiàn)用DFA實現(xiàn)詞法分析DFADFA的輸出就是接受還拒絕，只能檢查串是否被DFA接受;詞法分析程序識別出可接受的單詞,并建立它的內(nèi)部表示ToyL詞法規(guī)則的正則定義letter = a|z|A|Z digit = 0|9NZ-digit = 1|9Keywords: Keyword = var| if | then | else| while| read| write| intIdentifiers: identifier = letter digit*Constant: integer: int = NZ-digit digit*

5、 | 0 Other symbols: syms = +|-| *|/ | | , ”,”(”,: tk.type =PLUS; ReadNext(); goto Done; “t”,”n”,” ”: goto WS; other: error(); /出現(xiàn)字母表以外的字符根據(jù) DFA構(gòu)造詞法分析程序Num: ReadNext(); case CurrentChar of “0.9”: strlen+ = CurrentChar; goto Num ; other: tk.type = NUM； /other1:數(shù)字以外的字符 strcpy(tk.val, str); if CurrentCh

6、ar EOF goto Done; /已經(jīng)讀入下一字符 else exit(1);根據(jù) DFA構(gòu)造詞法分析程序ID: ReadNext(); case CurrentChar of “0.9”, “a.z”,“A.Z”：strlen+ = CurrentChar; goto ID; other: if IsKeyword(str) tk.type = IsKeyword(str) else tk.type = IDE, strcpy(tk.val, str) ; if CurrentChar EOF goto Done; else exit(1); 根據(jù) DFA構(gòu)造詞法分析程序Done: To

7、kenListtotal = tk; / 向token表中添加新的token total +; /token總數(shù)增加一個 len = 0; /準(zhǔn)備存儲新的token串 strcpy(str, “”); / token屬性值重置 if (CurrentChar = EOF) exit(1); goto start; /開始掃描新的token開發(fā)詞法分析程序應(yīng)注意的一些問題去掉注釋、空格、制表符等格式控制符號x = 0; /*變量初始化*/x = y * z ; /計算x進(jìn)行宏替換#define LEN 100包含文件的拷貝#include “stdio.h”括號匹配的問題，本屬于語法分析部分，但

8、放在詞法分析部分處理，可以大大減輕語法分析程序的負(fù)擔(dān)！、（）、 開發(fā)詞法分析程序應(yīng)注意的一些問題保留字的問題保留字(關(guān)鍵字)的結(jié)構(gòu)和標(biāo)識符的結(jié)構(gòu)相同識別方法：保留字表：首先建立保留字表，保留字表是保留字名字到相應(yīng)Token表示的映射表；將標(biāo)識符和保留字統(tǒng)一識別，然后每當(dāng)識別出一個標(biāo)識符，就查保留字表，在表中，說明是保留字，返回Token表示；不在表中說明是標(biāo)識符，繼續(xù)構(gòu)造屬性信息。直接識別：每個保留字作為一類單詞，效率低。開發(fā)詞法分析程序應(yīng)注意的一些問題詞法分析程序的結(jié)束兩種方案當(dāng)讀到程序結(jié)束符時,認(rèn)為詞法分析結(jié)束例如: Pascal語言規(guī)定“.”是程序結(jié)束符,當(dāng)掃描到“.”時便認(rèn)為詞法分析結(jié)

9、束.當(dāng)讀到文件結(jié)束符EOF時,認(rèn)為詞法分析結(jié)束.開發(fā)詞法分析程序應(yīng)注意的一些問題詞法分析程序的類型 附 屬詞法分析器語法分析callToken字符序列 獨 立詞法分析器語法分析TokenList字符序列四、詞法分析程序構(gòu)造手工構(gòu)造詞法分析程序利用自動生成工具LEX-生成詞法分析程序詞法分析程序的生成器 LexLEX（Lexical Analyzer Generator）即詞法分析器的生成器，是由貝爾實驗室的M.E.Lesk和E.Schmidt于1972年在UNIX操作系統(tǒng)上首次開發(fā)的。最新版本是FLEX(Fast Lexical Analyzer Genrator)工作原理：LEX通過對Lex

10、源文件(.l文件)的掃描，經(jīng)過宏替換將規(guī)則部分的正則表達(dá)式轉(zhuǎn)換成與之等價的DFA，并產(chǎn)生DFA的狀態(tài)轉(zhuǎn)換矩陣（稀疏矩陣）；利用該矩陣和Lex源文件中的C代碼一起產(chǎn)生一個名為yylex()的詞法分析函數(shù)，并將yylex()函數(shù)拷貝到輸出文件lex.yy.c中。flex.lRE-like definitionlex.yy.c( yylex() )詞法分析程序的生成器 LexflexLex源程序*.llex.yy.cC編譯器lex.yy.ca.outa.out輸入流Token序列用Lex創(chuàng)建一個詞法分析器的過程Lex源文件的結(jié)構(gòu)定義部分% 常量%規(guī)則部分%輔助函數(shù)部分% ID,NUM,IF,ADD%

11、正則定義 letter A-Za-zdigit 0-9id letter(letter|digit)*num digit+if return (IF);+ return(ADD);id yylval = strcpy(yytext, yylength); return(ID)；num yylval = Change(); return(NUM);int Change() /*將字符串形式的常數(shù)轉(zhuǎn)換成整數(shù)形式*/Lex的例子int num_chars=0,num_lines=0; /*定義兩個全局變量，一個記字符數(shù)，一個記行數(shù).注意：該語句不能頂行*/%n +num_chars+; +num_l

12、ines;. +num_chars;%int main() yylex(); printf(“%d,%d”, num_chars,num_lines);int yywrap()/*文件結(jié)束處理函數(shù)，當(dāng)yylex()讀到文件結(jié)束標(biāo)記EOF時，會調(diào)用該函數(shù)。所以用戶必須提供該函數(shù)，否則會提示編譯出錯 */ return 1;/返回1表示文件掃描結(jié)束，不必再掃描別的文件Lex中的沖突解決%program printf(“%sn”,yytext);/*模式1*/procedure printf(“%sn”,yytext);/*模式2*/a-za-z0-9* printf(“%sn”,yytext);/

13、*模式3*/當(dāng)輸入串為“programming”時，模式1（匹配“program”）和模式3（“programming”）都匹配，但會選擇匹配串長的模式3。當(dāng)輸入串為“program”時，因為模式1和模式3匹配的串長度相等故會選擇模式1.當(dāng)輸入與長度不同的多個模式匹配時，Lex選擇長模式進(jìn)行匹配當(dāng)輸入與長度相同的多個模式匹配時，Lex選擇列于前面的模式進(jìn)行匹配第二章 總結(jié)關(guān)于 有限自動機(jī)DFA的定義(, 開始狀態(tài), 狀態(tài)集, 終止?fàn)顟B(tài)集, 轉(zhuǎn)換函數(shù)f)NFA的定義(, 開始狀態(tài)集, 狀態(tài)集,終止?fàn)顟B(tài)集, 轉(zhuǎn)換函數(shù)f)NFA 與 DFA的區(qū)別開始狀態(tài)數(shù)NFA允許從一個狀態(tài)和一個符號引出多條邊第二章 總結(jié)關(guān)于 有限自動機(jī)NFA 到 DFA的轉(zhuǎn)換主要思想解決的問題DFA 的化簡主要思想解決的問題DFA 的實現(xiàn)第二章 總結(jié)關(guān)于正則表達(dá)式正則表達(dá)式的定義正則定義正則表達(dá)式 到 NFA的轉(zhuǎn)換主要思想解決的問題用正則表達(dá)式定義詞法結(jié)構(gòu)第二章 總結(jié)關(guān)于詞法分析器用正則表達(dá)式定義詞法結(jié)構(gòu)將正則表達(dá)式 轉(zhuǎn)換成 NFA將NFA 轉(zhuǎn)換成 DFAD