工學(xué)第四章詞法分析1課件

第四章詞法分析詞法分析是編譯過程的第一步，其主要任務(wù)是對源程序進(jìn)行掃描，產(chǎn)生一個個的單詞符號，把作為字符串的源程序改造成為單詞符號串的中間程序。因此，詞法分析是編譯的基礎(chǔ)。執(zhí)行詞法分析是編譯的基礎(chǔ)。詞法分析：根據(jù)詞法規(guī)則識別及組合單詞，進(jìn)行詞法檢查。對數(shù)字常數(shù)完成數(shù)字字符串到（二進(jìn)制）數(shù)值的轉(zhuǎn)換。刪去空格字符和注解。12/22/20221第四章：詞法分析第四章詞法分析詞法分析是編譯過程的第一步，其主要任務(wù)是對4.1詞法分析程序的設(shè)計(jì)任務(wù)執(zhí)行詞法分析的程序稱為詞法分析器.詞法分析器的功能是輸入源程序,輸出單詞符號.單詞符號是一個程序語言的基本符號。12/22/20222第四章：詞法分析4.1詞法分析程序的設(shè)計(jì)任務(wù)12/16/20222第四章4.1.2詞法分析程序的輸出程序語言的單詞符號一般分為五種:關(guān)鍵字:由程序語言定義的具有固定意義的標(biāo)識符。有時稱這些標(biāo)識符為保留字或基本字。例如，Pascal中的begin，end，if,while等。標(biāo)識符:用來表示各種名字,如:變量名,數(shù)組名等.常數(shù):整型,實(shí)型,布爾型等.運(yùn)算符:+-*/等.界符:逗號,分號,括號,/*,*/等.一個程序語言的關(guān)鍵字,運(yùn)算符,界符都是確定的,一般只有幾十或上百個,而對標(biāo)識符和常數(shù)的使用都不加什么限制.12/22/20223第四章：詞法分析4.1.2詞法分析程序的輸出程序語言的單詞符號一般分為五種:單詞符號的表示單詞符號常常表示成如下二元式:(單詞種別,單詞符號的屬性值)單詞種別可用以下形式表示:單詞種別通常用整數(shù)編碼.一個語言的單詞符號如何分種，分成幾種，怎樣編碼，是一個技術(shù)性的問題。它主要取決于處理上的方便。標(biāo)識符一般統(tǒng)歸一種。常數(shù)則宜按類型分種。關(guān)鍵字可將其全體視為一種，也可以一字一種。運(yùn)算符可采用一符一種的分法，但也可以把具有一定共性的運(yùn)算符視為一種。至于界符一般用一符一種的分法。一類單詞統(tǒng)一用一個整數(shù)值代表其屬性．如1代表保留字,2代表標(biāo)識符等.每一個單詞一個類別.如1代表BEGIN,2代表END等.12/22/20224第四章：詞法分析單詞符號的表示單詞符號常常表示成如下二元式:12/16/20如果一個種別只含一個單詞符號，那么，對于這個單詞符號，種別編碼就完全代表它自身了。若一個種別含有多個單詞符號，那么，對于它的每個單詞符號，除了給出種別編碼之外，還應(yīng)給出有關(guān)單詞符號的屬性信息。屬性值:單詞符號的屬性是指單詞符號的特性或特征.屬性值則是反應(yīng)特性或特征的值.例如，對于某個標(biāo)識符，常將存放它的有關(guān)信息的符號表項(xiàng)的指針作為其屬性值；對于某個常數(shù)，則將存放它的常數(shù)表項(xiàng)的指針作為其屬性值。在本書中，假定關(guān)鍵字、運(yùn)算符和界符都是一符一種。對于它們詞法分析器只給出某種別編碼，不給出它自身的值。標(biāo)識符單列一種。常數(shù)按類型分種類。12/22/20225第四章：詞法分析如果一個種別只含一個單詞符號，那么，對于這個單詞符號，種別編1）按單詞種類分類單詞名稱標(biāo)識符無符號常數(shù)(整)無符號浮點(diǎn)數(shù)布爾常數(shù)字符串常數(shù)保留字分界符類別編碼1234567單詞值內(nèi)部字符串整數(shù)值數(shù)值0或1內(nèi)部字符串保留字或內(nèi)部編碼分界符或內(nèi)部編碼12/22/20226第四章：詞法分析1）按單詞種類分類單詞名稱類別編碼單詞值12/16/20222）保留字和分界符采用一符一類單詞名稱標(biāo)識符無符號常數(shù)(整)無符號浮點(diǎn)數(shù)布爾常數(shù)字符串常數(shù)IFTHENELSEFOR………:+*,(類別編碼123456789…….20212223…….單詞值內(nèi)部字符串整數(shù)值數(shù)值0或1內(nèi)部字符串----…..------12/22/20227第四章：詞法分析2）保留字和分界符采用一符一類單詞名稱類別編碼單詞值12/1考慮下述C++代碼段：while(i>=j)i--;經(jīng)詞法分析器處理后，它將被轉(zhuǎn)換為如下的單詞符號序列：<while,-> <(,-> <id,指向i的符號表項(xiàng)的指針> <>=,-> <id,指向j的符號表項(xiàng)的指針> <),-> <id,指向i的符號表項(xiàng)的指針> <--,-> <;,->12/22/20228第四章：詞法分析考慮下述C++代碼段：while(i>=j)i--;12詞法分析程序的實(shí)現(xiàn)方案1.詞法分析單獨(dú)作為一遍S.P.(字符串)詞法分析S.P.(符號串)語法分析第一遍第二遍單詞串優(yōu)點(diǎn):結(jié)構(gòu)清晰、各遍功能單一缺點(diǎn)：效率低2.詞法分析程序作為單獨(dú)的子程序S.P.(字符串)詞法分析程序語法分析程序取單詞單詞12/22/20229第四章：詞法分析詞法分析程序的實(shí)現(xiàn)方案1.詞法分析單獨(dú)作為一遍S.P.詞詞法分析器的設(shè)計(jì)輸入、預(yù)處理1.輸入緩沖區(qū)：詞法分析器工作的第一步是輸入源程序文本。輸入串一般是放在一個緩沖區(qū)中，這個緩沖區(qū)稱為輸入緩沖區(qū)。2.預(yù)處理：就是將程序語言中的空白符、跳格符、回車符、換行符和注解等編輯性字符剔掉。3.預(yù)處理子程序：就是用來完成編譯的預(yù)處理。4.分析器：分析器對掃描緩沖區(qū)進(jìn)行掃描時一般用兩個指示器，一個指向當(dāng)前正在識別的單詞的開始位置，另一個用于向前搜索以尋找單詞的終點(diǎn)。不論掃描緩沖區(qū)設(shè)得多大都不能保證單詞符號不會被它的邊界所打斷。因此，掃描緩沖區(qū)最好使用一個如下所示的一分為二的區(qū)域：

起點(diǎn)指示器

搜索指示器這意味著對標(biāo)識符和常數(shù)的長度實(shí)際上必須加以限制，否則，即使緩沖區(qū)再大也無濟(jì)于事。12/22/202210第四章：詞法分析詞法分析器的設(shè)計(jì)輸入、預(yù)處理12/16/202210第四章：詞法分析器的工作方式12/22/202211第四章：詞法分析詞法分析器的工作方式12/16/202211第四章：詞法分析單詞符號的識別：超前搜索在某些語言中，要識別一個單詞符號必須超前看若干字符，直到能區(qū)別開這些單詞為止，常應(yīng)用在如下幾個方面：關(guān)鍵字的識別； 標(biāo)識符的識別； 常數(shù)的識別； 算符和界符的識別；12/22/202212第四章：詞法分析單詞符號的識別：超前搜索在某些語言中，要識別一個單詞符號必須例：關(guān)鍵字的識別在FORTRAN語言中，關(guān)鍵字和用戶自定義的標(biāo)示符或標(biāo)號之間沒有特殊的界符作間隔，所以識別比較麻煩，看如下例子：1DO99K=1,102IF(5.EQ.M)I=103DO99K=1.104IF(5)=55語句1、3的區(qū)別在于等號之后的第一個界符：一個為逗點(diǎn)，另一個為句末符。所以一直搜索到這里才能區(qū)分開1句是DO語句，3語句是賦值句。語句2、4主要區(qū)別在于右括號之后的第一個字符：一個為字母，另一個為等號。所以也只能搜索到該字符才能得到語句2是IF語句，語句4是賦值句。12/22/202213第四章：詞法分析例：關(guān)鍵字的識別在FORTRAN語言中，關(guān)鍵字和用戶自定義的4.2單詞的描述工具程序設(shè)計(jì)語言中的單詞是基本語法符號。單詞符號的語法可以用有效的工具加以描述，并且基于這類描述工具，可以建立詞法分析技術(shù)，進(jìn)而可以建立詞法分析程序的自動構(gòu)造方法。多數(shù)程序設(shè)計(jì)語言的單詞的語法都能用正規(guī)文法來描述。12/22/202214第四章：詞法分析4.2單詞的描述工具程序設(shè)計(jì)語言中的單詞是基本語法符號。單詞4.2.1正規(guī)文法文法G=(ＶN，ＶT，Ｐ，Ｓ)G的任何產(chǎn)生式為A→αB或A→α，其中α∈VT*，A，B∈VN。書上P52的例子都是用正規(guī)文法表示的。在這里注意α可以為，所以右邊的表達(dá)式可能是非終結(jié)符、終結(jié)符或終結(jié)符加上非終結(jié)符。可以看例子中那些規(guī)則分別屬于那種類型。12/22/202215第四章：詞法分析4.2.1正規(guī)文法文法G=(ＶN，ＶT，Ｐ，Ｓ)G的任何產(chǎn)4.2.2正規(guī)式對于字母表Σ而言,正規(guī)式和它所代表的正規(guī)集的遞歸定義為:ε和φ是正規(guī)式,它們所表示的正規(guī)集分別為{ε}和φ;任何a∈Σ,a是Σ上的一個正規(guī)式,它所表示的正規(guī)集為{a};假定U和V都是Σ上的正規(guī)式,它們所表示的正規(guī)集分別為L(U)和L(V),那么,(U|V),(U*V),(U)*也都是正規(guī)式,它們所表示的正規(guī)集分別為L(U)∪L(V),L(U)L(V)(連接積)和(L(U))*(閉包)。僅由有限次使用上述三步驟而得到的表達(dá)式才是Σ上的正規(guī)式。由這些正規(guī)式所表示的字集才是Σ上的正規(guī)集12/22/202216第四章：詞法分析4.2.2正規(guī)式對于字母表Σ而言,正規(guī)式和它所代表的正規(guī)集的例4.2令Σ={a,b},Σ上所有正規(guī)式和相應(yīng)正規(guī)集的例子有:正規(guī)式正規(guī)集a{a}a|b{a,b}ab{ab}ba*Σ上所有以b為首后跟任意多個a的字

a(a|b)*Σ上所有以a為首的字12/22/202217第四章：詞法分析例4.2令Σ={a,b},Σ上所有正規(guī)式和相應(yīng)正規(guī)集的例子有例令Σ={A,B,0,1},則:正規(guī)式正規(guī)集(A|B)(A|B|0|1)*Σ上標(biāo)識符的全體

(0|1)(0|1)*Σ上“數(shù)”的全體正歸集是正規(guī)語言的另一種表示方法。12/22/202218第四章：詞法分析例令Σ={A,B,0,1},則:12/16/202218第正規(guī)式的等價(jià)性若兩個正規(guī)式所表示的正規(guī)集相同，則認(rèn)為二者等價(jià)。兩個等價(jià)的正規(guī)式U和V記為U=V.例如：b(ab)*=(ba)*b(a|b)*=(a*b*)*12/22/202219第四章：詞法分析正規(guī)式的等價(jià)性若兩個正規(guī)式所表示的正規(guī)集相同，則認(rèn)為二者等價(jià)注意(1)(a|b)*(2)a*b*(3)(ab)*(4)a*|b*相互不等價(jià)12aba*b*

a1b(a|b)*12ab(ab)*ax12yεεεεba*|b*12/22/202220第四章：詞法分析注意(1)(a|b)*(2)a*b*(3)(ab)*另:U,V和W均為正規(guī)式，下列關(guān)系普遍成立：(1)U|V=V|U(交換律）(2）U|（V|W）=（U|V）|W(結(jié)合律）(3）U（VW）=（UV）W(結(jié)合律）(4)U（V|W）=UV|UW(分配律）（V|W）U=VU|WU(分配律）(5)εU=Uε=Uε是連接的恒等元素(6)U|U=U“或”的抽取律正規(guī)式服從的代數(shù)規(guī)律12/22/202221第四章：詞法分析另:U,V和W均為正規(guī)式，下列關(guān)系普遍成立：正規(guī)式服從的代4.2.3正規(guī)文法和正規(guī)式的等價(jià)性一個正規(guī)語言可以由正規(guī)文法定義，也可以由正規(guī)式定義。對任何正規(guī)文法，存在定義同一語言的正規(guī)式；對任何正規(guī)式，存在生成同一語言的正規(guī)文法。12/22/202222第四章：詞法分析4.2.3正規(guī)文法和正規(guī)式的等價(jià)性一個正規(guī)語言可以由正規(guī)文法正規(guī)式轉(zhuǎn)換成正規(guī)文法將Σ上的一個正規(guī)式轉(zhuǎn)換成文法Ｇ=(ＶT,ＶN,Ｐ,Ｓ).另其中的的ＶT=Σ，確定產(chǎn)生式和ＶN的元素用如下辦法：對任何正規(guī)式r，選擇一個非終結(jié)符號S生成產(chǎn)生式S→r,并將S定為G的識別符號。若x和y都是正規(guī)式，對形如A→xy的產(chǎn)生式，重寫成A→xB,B→y兩個產(chǎn)生式,其中B是新選擇的非終結(jié)符號，即B∈ＶN12/22/202223第四章：詞法分析正規(guī)式轉(zhuǎn)換成正規(guī)文法將Σ上的一個正規(guī)式轉(zhuǎn)換成文法Ｇ=(ＶT,正規(guī)式轉(zhuǎn)換成正規(guī)文法對已轉(zhuǎn)換的文法中的形如A→x*y的產(chǎn)生式,重寫為：A→xBA→yB→xBB→y其中B為一新非終結(jié)符.對形如A→x|y的產(chǎn)生式，重寫為：A→x,A→y12/22/202224第四章：詞法分析正規(guī)式轉(zhuǎn)換成正規(guī)文法對已轉(zhuǎn)換的文法中的形如A→x*y的產(chǎn)生式例：將R=a(a|d)*轉(zhuǎn)化成相應(yīng)的正規(guī)文法，令S是文法的開始符號，首先形成S→a(a|d)*,然后形成S→aA和A→(a|d)*，再重寫第二條產(chǎn)生式形成：S→aA,A→(a|d)B,A→ε,B→(a|d)B和B→ε進(jìn)而變換為：S→aA,A→aB,A→dB,B→aB,B→dB,A→ε和B→ε12/22/202225第四章：詞法分析例：將R=a(a|d)*轉(zhuǎn)化成相應(yīng)的正規(guī)文法，令S是文法的開正規(guī)文法轉(zhuǎn)換成正規(guī)式即上述過程的逆過程,轉(zhuǎn)換規(guī)則為：文法產(chǎn)生式正規(guī)式規(guī)則1A->xB,B->yA=xy規(guī)則2A->xA|yA=x*y規(guī)則3A->x,A->yA=x|y12/22/202226第四章：詞法分析正規(guī)文法轉(zhuǎn)換成正規(guī)式即上述過程的逆過程,轉(zhuǎn)換規(guī)則為：文法產(chǎn)例：文法G[S]S→aA,S→a,A→aA,A→dA,A→a,A→d先有S=aA|aA=(aA|dA)|(a|d)再將A的正規(guī)式變換為A=(a|d)A|(a|d),據(jù)表中規(guī)則2變換為A=(a|d)*|(a|d),再將A右端代入S的正規(guī)式得：S=a(a|d)*|(a(a|d)|a再利用正規(guī)式的代數(shù)變換可以此得到S=a(a|d)*|(a|d)|εS=a(a|d)*即a(a|d)*為所求。12/22/202227第四章：詞法分析例：文法G[S]12/16/202227第四章：詞法分析補(bǔ)充：狀態(tài)轉(zhuǎn)換圖（1）狀態(tài)轉(zhuǎn)換圖狀態(tài)轉(zhuǎn)換圖是一張有限方向圖.它只包含有窮多個狀態(tài),即有窮多個結(jié)點(diǎn)，用○表示；狀態(tài)結(jié)點(diǎn)都代表文法的非終結(jié)符號,而且至少要包含一個終止?fàn)顟B(tài)，用◎表示.狀態(tài)之間用箭弧連接,箭弧上的標(biāo)記指明在射出弧的結(jié)點(diǎn)狀態(tài)下可能出現(xiàn)的輸入字符或字符類.狀態(tài)轉(zhuǎn)換圖實(shí)質(zhì)上是語法圖的一種變形。12/22/202228第四章：詞法分析補(bǔ)充：狀態(tài)轉(zhuǎn)換圖（1）狀態(tài)轉(zhuǎn)換圖12/16/202228第四(2)利用狀態(tài)圖識別(或接受)字符串的過程從初始狀態(tài)出發(fā)，按照與符號串余留部分中最左字符相匹配的原則，游歷狀態(tài)圖，直至符號串的末端為止。如果這時恰好到達(dá)終止?fàn)顟B(tài)，則符號串為該文法的句子；否則不是。大多數(shù)程序設(shè)計(jì)語言的單詞符號都可以用狀態(tài)轉(zhuǎn)換圖予以識別。可以用一張狀態(tài)轉(zhuǎn)換圖或若干張狀態(tài)轉(zhuǎn)換圖來描述一個語言的所有單詞。12/22/202229第四章：詞法分析(2)利用狀態(tài)圖識別(或接受)字符串的過程從初始狀態(tài)出發(fā)，按(3)狀態(tài)圖的畫法由右線性正規(guī)文法（產(chǎn)生式形如U->aW|a)構(gòu)造狀態(tài)轉(zhuǎn)換圖。除了原有代表非終結(jié)符號的狀態(tài)，另增加一個終止?fàn)顟B(tài)Z,對于每一條產(chǎn)生式U->a，從狀態(tài)U向Z畫一條弧，標(biāo)記為a，即12/22/202230第四章：詞法分析(3)狀態(tài)圖的畫法由右線性正規(guī)文法（產(chǎn)生式形如U->aW(3)狀態(tài)轉(zhuǎn)換圖的畫法對于每一條產(chǎn)生式U->aW，從狀態(tài)U向狀態(tài)W畫一條弧，標(biāo)記為a，即以識別符號為開始狀態(tài)。12/22/202231第四章：詞法分析(3)狀態(tài)轉(zhuǎn)換圖的畫法對于每一條產(chǎn)生式U->aW，從狀態(tài)U向(3)狀態(tài)圖的畫法由左線性正規(guī)文法（產(chǎn)生式形如U->Wa|a)構(gòu)造狀態(tài)轉(zhuǎn)換圖。除了原有代表非終結(jié)符號的狀態(tài)，另增加一個開始狀態(tài)S,對于每一條產(chǎn)生式U->a，從狀態(tài)S向U畫一條弧，標(biāo)記為a，即12/22/202232第四章：詞法分析(3)狀態(tài)圖的畫法由左線性正規(guī)文法（產(chǎn)生式形如U->Wa(3)狀態(tài)轉(zhuǎn)換圖的畫法對于每一條產(chǎn)生式U->Wa，從狀態(tài)W向狀態(tài)U畫一條弧，標(biāo)記為a，即以識別符號為終止?fàn)顟B(tài)。12/22/202233第四章：詞法分析(3)狀態(tài)轉(zhuǎn)換圖的畫法對于每一條產(chǎn)生式U->Wa，從狀態(tài)W向例1:(a)表示在狀態(tài)1下,若輸入字符為X,則讀進(jìn)X,并轉(zhuǎn)換到狀態(tài)2.若輸入字符為Y,則讀進(jìn)Y,并轉(zhuǎn)換到狀態(tài)3.(b)表示在狀態(tài)0下,若輸入字符是一個字母,則讀進(jìn)它,并轉(zhuǎn)入狀態(tài)1.在狀態(tài)1下,若下一個輸入字符為字母或數(shù)字,則讀進(jìn)它,并重現(xiàn)進(jìn)入狀態(tài)1.一直重復(fù)這個過程,直到狀態(tài)1發(fā)現(xiàn)輸入不再是字母或數(shù)字就進(jìn)入狀態(tài)2.(c)為識別整數(shù)的轉(zhuǎn)換圖.終態(tài)結(jié)上打個星號*意味著多讀進(jìn)了一個不屬于標(biāo)識符部分的字符，應(yīng)把它退還給輸入串。12/22/202234第四章：詞法分析例1:(a)表示在狀態(tài)1下,若輸入字符為X,則讀進(jìn)X,并轉(zhuǎn)換例2:Ｃ語言無符號整數(shù)的描述八進(jìn)制數(shù):(OCT，值)oct→o(0|...|7)(0|...|7)*十進(jìn)制數(shù):(DEC，值)dec→0|(1|...|9)(0|...|9)*12/22/202235第四章：詞法分析例2:Ｃ語言無符號整數(shù)的描述八進(jìn)制數(shù):(OC整數(shù)的狀態(tài)圖（1/2）3421o0-70-756101-90-9十進(jìn)制整數(shù)八進(jìn)制整數(shù)12/22/202236第四章：詞法分析整數(shù)的狀態(tài)圖（1/2）3421o0-70-756101-9識別十六進(jìn)制整數(shù)的狀態(tài)圖。將上述三個狀態(tài)轉(zhuǎn)換圖合并為一個，得到Ｃ語言無符號整數(shù)識別的狀態(tài)圖，方法步驟：（1）從開始狀態(tài)出發(fā)；（2）選擇輸入符號，構(gòu)成目標(biāo)狀態(tài)集；（3）從新狀態(tài)集出發(fā)，重復(fù)（1）、（2）

12/22/202237第四章：詞法分析識別十六進(jìn)制整數(shù)的狀態(tài)圖。將上述三個狀態(tài)轉(zhuǎn)換圖合并為一個，得例3:識別某個簡單語言的所有單詞用一些帶$的特殊符號來表示種別編碼和內(nèi)部值12/22/202238第四章：詞法分析例3:識別某個簡單語言的所有單詞用一些帶$的特殊符號來表示種為了對例3進(jìn)行更好的說明，做了如下的限制：1）所有關(guān)鍵字（如IF，WHILE等）都是“保留字”； 2）對關(guān)鍵字不需專設(shè)對應(yīng)的轉(zhuǎn)換圖，而只需要將他們預(yù)先安排在一張表格中； 3）如果關(guān)鍵字、標(biāo)識符和常數(shù)之間沒有確定的運(yùn)算符或界符作間隔，則必須至少用一個空白符作間隔。 有了上述假定后，多數(shù)單詞符號的識別就不必使用超前搜索技術(shù)。下圖是一張識別表的單詞符號的狀態(tài)轉(zhuǎn)換圖。在圖中，狀態(tài)0為初態(tài)；凡帶雙圈者均為終態(tài)；狀態(tài)13是識別不出單詞符號的出錯情形。12/22/202239第四章：詞法分析為了對例3進(jìn)行更好的說明，做了如下的限制：12/16/202例3的狀態(tài)圖：12/22/202240第四章：詞法分析例3的狀態(tài)圖：12/16/202240第四章：詞法分析狀態(tài)轉(zhuǎn)換圖的實(shí)現(xiàn)讓每個狀態(tài)結(jié)點(diǎn)對應(yīng)一段小程序，即可用程序?qū)崿F(xiàn)狀態(tài)圖。在此引進(jìn)了一組全局變量和過程，將他們作為實(shí)現(xiàn)轉(zhuǎn)換圖的基本成分。它們是：1）ch字符變量，存放最新讀進(jìn)的源程序字符。2）strToken字符數(shù)組，存放構(gòu)成單詞符號的字符串。3）GetChar子程序過程，將下一輸入字符讀到ch中，搜索指示器前移一字符位置。4）GetBC子程序過程，檢查ch中的字符是否為空白。若是，則調(diào)用GetChar直至ch中進(jìn)入一個非空白字符。5）Concat子程序過程，將ch中的字符連接到strToken之后。例如，假定strToken原來的值為“AB”，而ch中存放‘C’，經(jīng)調(diào)用concat后，strToken的值就變?yōu)椤癆BC”。6）IsLetter和IsDigit布爾函數(shù)過程，分別判斷ch中的字符是否是字母和數(shù)字7）Reserve整型函數(shù)過程，對strToken中的字符串查找保留字表，若它是一個保留字則返回它的編碼，否則返回0值。8）Retract子程序過程，將搜索指示器回調(diào)一個字符位置，將ch置為空白字符9）InsertId整型函數(shù)過程，將strToken中的標(biāo)識符插入符號表，返回符號表指針10）InsertConst整型函數(shù)過程，將strToken中的常數(shù)插入常數(shù)表，返回常數(shù)表指針12/22/202241第四章：詞法分析狀態(tài)轉(zhuǎn)換圖的實(shí)現(xiàn)讓每個狀態(tài)結(jié)點(diǎn)對應(yīng)一段小程序，即可用程序?qū)崿F(xiàn)對于不含回路的分叉結(jié)點(diǎn)來說，可讓它對應(yīng)一個switch語句或一組if…then…else語句。對應(yīng)程序如下：Getchar();If(isLetter()){狀態(tài)j的對應(yīng)程序段;}Elseif(isDigit()){狀態(tài)k的對應(yīng)程序段；}Elseif(ch=‘/’){狀態(tài)l對應(yīng)程序段；}Else{錯誤處理；}iljk字母數(shù)字/當(dāng)程序執(zhí)行到達(dá)“錯誤處理”時，意味著現(xiàn)行狀態(tài)I和當(dāng)前所面臨的輸入串不匹配。如果后面還有狀態(tài)圖，出現(xiàn)在這個地方的代碼應(yīng)為：將搜索指示器回退一個位置，并令下一個狀態(tài)圖開始工作。如果后面沒有其它狀態(tài)圖，則出現(xiàn)在上述位置的代碼應(yīng)進(jìn)行真正的出錯處理，報(bào)告源程序含有非法符號，并進(jìn)行善后處理。12/22/202242第四章：詞法分析對于不含回路的分叉結(jié)點(diǎn)來說，可讓它對應(yīng)一個switch語句或?qū)τ诤芈返臓顟B(tài)結(jié)點(diǎn)來說，可讓它對應(yīng)一個由while語句和if語句構(gòu)成的程序段，右圖所對應(yīng)的程序段可為：GetChar();While(isLetter()orisDigit()) GetChar();…狀態(tài)j的對應(yīng)程序段…ij字母或數(shù)字其它終態(tài)結(jié)點(diǎn)一般對應(yīng)一個形如return(code,value)的語句。其中，code為單詞種別編碼；value或是單詞符號的屬性值，或無定義。這個return意味著從分析器返回到調(diào)用者，一般指返回到語法分析器。凡帶*的終態(tài)結(jié)點(diǎn)意味著多讀了一個不屬于現(xiàn)行單詞符號的字符，這個字符應(yīng)予退回，也就是說，必須把搜索指示器回調(diào)一字符位置。這項(xiàng)工作有Retract過程來完成。12/22/202243第四章：詞法分析對于含回路的狀態(tài)結(jié)點(diǎn)來說，可讓它對應(yīng)一個由while語句和i轉(zhuǎn)換圖3.3的詞法分析器可構(gòu)造如下：例3的詞法分析器：intcode,value;strToken:=“”;/*置strToken為空串*/GetChar();GetBC();/*讀入一字符*/if(IsLetter())beginwhile(IsLetter()orIsDigit())beginConcat();GetChar();/*將字符進(jìn)行連接*/end12/22/202244第四章：詞法分析轉(zhuǎn)換圖3.3的詞法分析器可構(gòu)造如下：例3的詞法分析器：12/Retract();/*回調(diào)一位*/code:=Reserve();/*是保留字還是標(biāo)識符*/if(code=0)/*如是標(biāo)識符*/beginvalue:=InsertId(strToken);return($ID,value);/*返回編碼和屬性值*/endelsereturn(code,-);end12/22/202245第四章：詞法分析Retract();/*回調(diào)一位*/12/16/elseif(IsDigit())beginwhile(IsDigit())beginConcat();GetChar();endRetract();value:=InsertConst(strToken);return($INT,value);endelseif(ch==‘=’)return($ASSIGN,-);elseif(ch==‘+’)return($PLUS,-);12/22/202246第四章：詞法分析elseif(IsDigit())12/16/202246elseif(ch=‘*’)beginGetChar();if(ch=‘*’)return($POWER,-);Retract();return($SATR,-);endelseif(ch=‘;’)return($SEMICOLON,-);elseif(ch=‘(’)return($LPAR,-);elseif(ch=‘)’)return($RPAR,-);elseif(ch=‘{’)return($LBRACE,-);elseif(ch=‘}’)return($RBRACE,-);elseProcError();12/22/202247第四章：詞法分析elseif(ch=‘*’)12/16/202247第四章詞法分析詞法分析是編譯過程的第一步，其主要任務(wù)是對源程序進(jìn)行掃描，產(chǎn)生一個個的單詞符號，把作為字符串的源程序改造成為單詞符號串的中間程序。因此，詞法分析是編譯的基礎(chǔ)。執(zhí)行詞法分析是編譯的基礎(chǔ)。詞法分析：根據(jù)詞法規(guī)則識別及組合單詞，進(jìn)行詞法檢查。對數(shù)字常數(shù)完成數(shù)字字符串到（二進(jìn)制）數(shù)值的轉(zhuǎn)換。刪去空格字符和注解。12/22/202248第四章：詞法分析第四章詞法分析詞法分析是編譯過程的第一步，其主要任務(wù)是對4.1詞法分析程序的設(shè)計(jì)任務(wù)執(zhí)行詞法分析的程序稱為詞法分析器.詞法分析器的功能是輸入源程序,輸出單詞符號.單詞符號是一個程序語言的基本符號。12/22/202249第四章：詞法分析4.1詞法分析程序的設(shè)計(jì)任務(wù)12/16/20222第四章4.1.2詞法分析程序的輸出程序語言的單詞符號一般分為五種:關(guān)鍵字:由程序語言定義的具有固定意義的標(biāo)識符。有時稱這些標(biāo)識符為保留字或基本字。例如，Pascal中的begin，end，if,while等。標(biāo)識符:用來表示各種名字,如:變量名,數(shù)組名等.常數(shù):整型,實(shí)型,布爾型等.運(yùn)算符:+-*/等.界符:逗號,分號,括號,/*,*/等.一個程序語言的關(guān)鍵字,運(yùn)算符,界符都是確定的,一般只有幾十或上百個,而對標(biāo)識符和常數(shù)的使用都不加什么限制.12/22/202250第四章：詞法分析4.1.2詞法分析程序的輸出程序語言的單詞符號一般分為五種:單詞符號的表示單詞符號常常表示成如下二元式:(單詞種別,單詞符號的屬性值)單詞種別可用以下形式表示:單詞種別通常用整數(shù)編碼.一個語言的單詞符號如何分種，分成幾種，怎樣編碼，是一個技術(shù)性的問題。它主要取決于處理上的方便。標(biāo)識符一般統(tǒng)歸一種。常數(shù)則宜按類型分種。關(guān)鍵字可將其全體視為一種，也可以一字一種。運(yùn)算符可采用一符一種的分法，但也可以把具有一定共性的運(yùn)算符視為一種。至于界符一般用一符一種的分法。一類單詞統(tǒng)一用一個整數(shù)值代表其屬性．如1代表保留字,2代表標(biāo)識符等.每一個單詞一個類別.如1代表BEGIN,2代表END等.12/22/202251第四章：詞法分析單詞符號的表示單詞符號常常表示成如下二元式:12/16/20如果一個種別只含一個單詞符號，那么，對于這個單詞符號，種別編碼就完全代表它自身了。若一個種別含有多個單詞符號，那么，對于它的每個單詞符號，除了給出種別編碼之外，還應(yīng)給出有關(guān)單詞符號的屬性信息。屬性值:單詞符號的屬性是指單詞符號的特性或特征.屬性值則是反應(yīng)特性或特征的值.例如，對于某個標(biāo)識符，常將存放它的有關(guān)信息的符號表項(xiàng)的指針作為其屬性值；對于某個常數(shù)，則將存放它的常數(shù)表項(xiàng)的指針作為其屬性值。在本書中，假定關(guān)鍵字、運(yùn)算符和界符都是一符一種。對于它們詞法分析器只給出某種別編碼，不給出它自身的值。標(biāo)識符單列一種。常數(shù)按類型分種類。12/22/202252第四章：詞法分析如果一個種別只含一個單詞符號，那么，對于這個單詞符號，種別編1）按單詞種類分類單詞名稱標(biāo)識符無符號常數(shù)(整)無符號浮點(diǎn)數(shù)布爾常數(shù)字符串常數(shù)保留字分界符類別編碼1234567單詞值內(nèi)部字符串整數(shù)值數(shù)值0或1內(nèi)部字符串保留字或內(nèi)部編碼分界符或內(nèi)部編碼12/22/202253第四章：詞法分析1）按單詞種類分類單詞名稱類別編碼單詞值12/16/20222）保留字和分界符采用一符一類單詞名稱標(biāo)識符無符號常數(shù)(整)無符號浮點(diǎn)數(shù)布爾常數(shù)字符串常數(shù)IFTHENELSEFOR………:+*,(類別編碼123456789…….20212223…….單詞值內(nèi)部字符串整數(shù)值數(shù)值0或1內(nèi)部字符串----…..------12/22/202254第四章：詞法分析2）保留字和分界符采用一符一類單詞名稱類別編碼單詞值12/1考慮下述C++代碼段：while(i>=j)i--;經(jīng)詞法分析器處理后，它將被轉(zhuǎn)換為如下的單詞符號序列：<while,-> <(,-> <id,指向i的符號表項(xiàng)的指針> <>=,-> <id,指向j的符號表項(xiàng)的指針> <),-> <id,指向i的符號表項(xiàng)的指針> <--,-> <;,->12/22/202255第四章：詞法分析考慮下述C++代碼段：while(i>=j)i--;12詞法分析程序的實(shí)現(xiàn)方案1.詞法分析單獨(dú)作為一遍S.P.(字符串)詞法分析S.P.(符號串)語法分析第一遍第二遍單詞串優(yōu)點(diǎn):結(jié)構(gòu)清晰、各遍功能單一缺點(diǎn)：效率低2.詞法分析程序作為單獨(dú)的子程序S.P.(字符串)詞法分析程序語法分析程序取單詞單詞12/22/202256第四章：詞法分析詞法分析程序的實(shí)現(xiàn)方案1.詞法分析單獨(dú)作為一遍S.P.詞詞法分析器的設(shè)計(jì)輸入、預(yù)處理1.輸入緩沖區(qū)：詞法分析器工作的第一步是輸入源程序文本。輸入串一般是放在一個緩沖區(qū)中，這個緩沖區(qū)稱為輸入緩沖區(qū)。2.預(yù)處理：就是將程序語言中的空白符、跳格符、回車符、換行符和注解等編輯性字符剔掉。3.預(yù)處理子程序：就是用來完成編譯的預(yù)處理。4.分析器：分析器對掃描緩沖區(qū)進(jìn)行掃描時一般用兩個指示器，一個指向當(dāng)前正在識別的單詞的開始位置，另一個用于向前搜索以尋找單詞的終點(diǎn)。不論掃描緩沖區(qū)設(shè)得多大都不能保證單詞符號不會被它的邊界所打斷。因此，掃描緩沖區(qū)最好使用一個如下所示的一分為二的區(qū)域：

起點(diǎn)指示器

搜索指示器這意味著對標(biāo)識符和常數(shù)的長度實(shí)際上必須加以限制，否則，即使緩沖區(qū)再大也無濟(jì)于事。12/22/202257第四章：詞法分析詞法分析器的設(shè)計(jì)輸入、預(yù)處理12/16/202210第四章：詞法分析器的工作方式12/22/202258第四章：詞法分析詞法分析器的工作方式12/16/202211第四章：詞法分析單詞符號的識別：超前搜索在某些語言中，要識別一個單詞符號必須超前看若干字符，直到能區(qū)別開這些單詞為止，常應(yīng)用在如下幾個方面：關(guān)鍵字的識別； 標(biāo)識符的識別； 常數(shù)的識別； 算符和界符的識別；12/22/202259第四章：詞法分析單詞符號的識別：超前搜索在某些語言中，要識別一個單詞符號必須例：關(guān)鍵字的識別在FORTRAN語言中，關(guān)鍵字和用戶自定義的標(biāo)示符或標(biāo)號之間沒有特殊的界符作間隔，所以識別比較麻煩，看如下例子：1DO99K=1,102IF(5.EQ.M)I=103DO99K=1.104IF(5)=55語句1、3的區(qū)別在于等號之后的第一個界符：一個為逗點(diǎn)，另一個為句末符。所以一直搜索到這里才能區(qū)分開1句是DO語句，3語句是賦值句。語句2、4主要區(qū)別在于右括號之后的第一個字符：一個為字母，另一個為等號。所以也只能搜索到該字符才能得到語句2是IF語句，語句4是賦值句。12/22/202260第四章：詞法分析例：關(guān)鍵字的識別在FORTRAN語言中，關(guān)鍵字和用戶自定義的4.2單詞的描述工具程序設(shè)計(jì)語言中的單詞是基本語法符號。單詞符號的語法可以用有效的工具加以描述，并且基于這類描述工具，可以建立詞法分析技術(shù)，進(jìn)而可以建立詞法分析程序的自動構(gòu)造方法。多數(shù)程序設(shè)計(jì)語言的單詞的語法都能用正規(guī)文法來描述。12/22/202261第四章：詞法分析4.2單詞的描述工具程序設(shè)計(jì)語言中的單詞是基本語法符號。單詞4.2.1正規(guī)文法文法G=(ＶN，ＶT，Ｐ，Ｓ)G的任何產(chǎn)生式為A→αB或A→α，其中α∈VT*，A，B∈VN。書上P52的例子都是用正規(guī)文法表示的。在這里注意α可以為，所以右邊的表達(dá)式可能是非終結(jié)符、終結(jié)符或終結(jié)符加上非終結(jié)符。可以看例子中那些規(guī)則分別屬于那種類型。12/22/202262第四章：詞法分析4.2.1正規(guī)文法文法G=(ＶN，ＶT，Ｐ，Ｓ)G的任何產(chǎn)4.2.2正規(guī)式對于字母表Σ而言,正規(guī)式和它所代表的正規(guī)集的遞歸定義為:ε和φ是正規(guī)式,它們所表示的正規(guī)集分別為{ε}和φ;任何a∈Σ,a是Σ上的一個正規(guī)式,它所表示的正規(guī)集為{a};假定U和V都是Σ上的正規(guī)式,它們所表示的正規(guī)集分別為L(U)和L(V),那么,(U|V),(U*V),(U)*也都是正規(guī)式,它們所表示的正規(guī)集分別為L(U)∪L(V),L(U)L(V)(連接積)和(L(U))*(閉包)。僅由有限次使用上述三步驟而得到的表達(dá)式才是Σ上的正規(guī)式。由這些正規(guī)式所表示的字集才是Σ上的正規(guī)集12/22/202263第四章：詞法分析4.2.2正規(guī)式對于字母表Σ而言,正規(guī)式和它所代表的正規(guī)集的例4.2令Σ={a,b},Σ上所有正規(guī)式和相應(yīng)正規(guī)集的例子有:正規(guī)式正規(guī)集a{a}a|b{a,b}ab{ab}ba*Σ上所有以b為首后跟任意多個a的字

a(a|b)*Σ上所有以a為首的字12/22/202264第四章：詞法分析例4.2令Σ={a,b},Σ上所有正規(guī)式和相應(yīng)正規(guī)集的例子有例令Σ={A,B,0,1},則:正規(guī)式正規(guī)集(A|B)(A|B|0|1)*Σ上標(biāo)識符的全體

(0|1)(0|1)*Σ上“數(shù)”的全體正歸集是正規(guī)語言的另一種表示方法。12/22/202265第四章：詞法分析例令Σ={A,B,0,1},則:12/16/202218第正規(guī)式的等價(jià)性若兩個正規(guī)式所表示的正規(guī)集相同，則認(rèn)為二者等價(jià)。兩個等價(jià)的正規(guī)式U和V記為U=V.例如：b(ab)*=(ba)*b(a|b)*=(a*b*)*12/22/202266第四章：詞法分析正規(guī)式的等價(jià)性若兩個正規(guī)式所表示的正規(guī)集相同，則認(rèn)為二者等價(jià)注意(1)(a|b)*(2)a*b*(3)(ab)*(4)a*|b*相互不等價(jià)12aba*b*

a1b(a|b)*12ab(ab)*ax12yεεεεba*|b*12/22/202267第四章：詞法分析注意(1)(a|b)*(2)a*b*(3)(ab)*另:U,V和W均為正規(guī)式，下列關(guān)系普遍成立：(1)U|V=V|U(交換律）(2）U|（V|W）=（U|V）|W(結(jié)合律）(3）U（VW）=（UV）W(結(jié)合律）(4)U（V|W）=UV|UW(分配律）（V|W）U=VU|WU(分配律）(5)εU=Uε=Uε是連接的恒等元素(6)U|U=U“或”的抽取律正規(guī)式服從的代數(shù)規(guī)律12/22/202268第四章：詞法分析另:U,V和W均為正規(guī)式，下列關(guān)系普遍成立：正規(guī)式服從的代4.2.3正規(guī)文法和正規(guī)式的等價(jià)性一個正規(guī)語言可以由正規(guī)文法定義，也可以由正規(guī)式定義。對任何正規(guī)文法，存在定義同一語言的正規(guī)式；對任何正規(guī)式，存在生成同一語言的正規(guī)文法。12/22/202269第四章：詞法分析4.2.3正規(guī)文法和正規(guī)式的等價(jià)性一個正規(guī)語言可以由正規(guī)文法正規(guī)式轉(zhuǎn)換成正規(guī)文法將Σ上的一個正規(guī)式轉(zhuǎn)換成文法Ｇ=(ＶT,ＶN,Ｐ,Ｓ).另其中的的ＶT=Σ，確定產(chǎn)生式和ＶN的元素用如下辦法：對任何正規(guī)式r，選擇一個非終結(jié)符號S生成產(chǎn)生式S→r,并將S定為G的識別符號。若x和y都是正規(guī)式，對形如A→xy的產(chǎn)生式，重寫成A→xB,B→y兩個產(chǎn)生式,其中B是新選擇的非終結(jié)符號，即B∈ＶN12/22/202270第四章：詞法分析正規(guī)式轉(zhuǎn)換成正規(guī)文法將Σ上的一個正規(guī)式轉(zhuǎn)換成文法Ｇ=(ＶT,正規(guī)式轉(zhuǎn)換成正規(guī)文法對已轉(zhuǎn)換的文法中的形如A→x*y的產(chǎn)生式,重寫為：A→xBA→yB→xBB→y其中B為一新非終結(jié)符.對形如A→x|y的產(chǎn)生式，重寫為：A→x,A→y12/22/202271第四章：詞法分析正規(guī)式轉(zhuǎn)換成正規(guī)文法對已轉(zhuǎn)換的文法中的形如A→x*y的產(chǎn)生式例：將R=a(a|d)*轉(zhuǎn)化成相應(yīng)的正規(guī)文法，令S是文法的開始符號，首先形成S→a(a|d)*,然后形成S→aA和A→(a|d)*，再重寫第二條產(chǎn)生式形成：S→aA,A→(a|d)B,A→ε,B→(a|d)B和B→ε進(jìn)而變換為：S→aA,A→aB,A→dB,B→aB,B→dB,A→ε和B→ε12/22/202272第四章：詞法分析例：將R=a(a|d)*轉(zhuǎn)化成相應(yīng)的正規(guī)文法，令S是文法的開正規(guī)文法轉(zhuǎn)換成正規(guī)式即上述過程的逆過程,轉(zhuǎn)換規(guī)則為：文法產(chǎn)生式正規(guī)式規(guī)則1A->xB,B->yA=xy規(guī)則2A->xA|yA=x*y規(guī)則3A->x,A->yA=x|y12/22/202273第四章：詞法分析正規(guī)文法轉(zhuǎn)換成正規(guī)式即上述過程的逆過程,轉(zhuǎn)換規(guī)則為：文法產(chǎn)例：文法G[S]S→aA,S→a,A→aA,A→dA,A→a,A→d先有S=aA|aA=(aA|dA)|(a|d)再將A的正規(guī)式變換為A=(a|d)A|(a|d),據(jù)表中規(guī)則2變換為A=(a|d)*|(a|d),再將A右端代入S的正規(guī)式得：S=a(a|d)*|(a(a|d)|a再利用正規(guī)式的代數(shù)變換可以此得到S=a(a|d)*|(a|d)|εS=a(a|d)*即a(a|d)*為所求。12/22/202274第四章：詞法分析例：文法G[S]12/16/202227第四章：詞法分析補(bǔ)充：狀態(tài)轉(zhuǎn)換圖（1）狀態(tài)轉(zhuǎn)換圖狀態(tài)轉(zhuǎn)換圖是一張有限方向圖.它只包含有窮多個狀態(tài),即有窮多個結(jié)點(diǎn)，用○表示；狀態(tài)結(jié)點(diǎn)都代表文法的非終結(jié)符號,而且至少要包含一個終止?fàn)顟B(tài)，用◎表示.狀態(tài)之間用箭弧連接,箭弧上的標(biāo)記指明在射出弧的結(jié)點(diǎn)狀態(tài)下可能出現(xiàn)的輸入字符或字符類.狀態(tài)轉(zhuǎn)換圖實(shí)質(zhì)上是語法圖的一種變形。12/22/202275第四章：詞法分析補(bǔ)充：狀態(tài)轉(zhuǎn)換圖（1）狀態(tài)轉(zhuǎn)換圖12/16/202228第四(2)利用狀態(tài)圖識別(或接受)字符串的過程從初始狀態(tài)出發(fā)，按照與符號串余留部分中最左字符相匹配的原則，游歷狀態(tài)圖，直至符號串的末端為止。如果這時恰好到達(dá)終止?fàn)顟B(tài)，則符號串為該文法的句子；否則不是。大多數(shù)程序設(shè)計(jì)語言的單詞符號都可以用狀態(tài)轉(zhuǎn)換圖予以識別?？梢杂靡粡垹顟B(tài)轉(zhuǎn)換圖或若干張狀態(tài)轉(zhuǎn)換圖來描述一個語言的所有單詞。12/22/202276第四章：詞法分析(2)利用狀態(tài)圖識別(或接受)字符串的過程從初始狀態(tài)出發(fā)，按(3)狀態(tài)圖的畫法由右線性正規(guī)文法（產(chǎn)生式形如U->aW|a)構(gòu)造狀態(tài)轉(zhuǎn)換圖。除了原有代表非終結(jié)符號的狀態(tài)，另增加一個終止?fàn)顟B(tài)Z,對于每一條產(chǎn)生式U->a，從狀態(tài)U向Z畫一條弧，標(biāo)記為a，即12/22/202277第四章：詞法分析(3)狀態(tài)圖的畫法由右線性正規(guī)文法（產(chǎn)生式形如U->aW(3)狀態(tài)轉(zhuǎn)換圖的畫法對于每一條產(chǎn)生式U->aW，從狀態(tài)U向狀態(tài)W畫一條弧，標(biāo)記為a，即以識別符號為開始狀態(tài)。12/22/202278第四章：詞法分析(3)狀態(tài)轉(zhuǎn)換圖的畫法對于每一條產(chǎn)生式U->aW，從狀態(tài)U向(3)狀態(tài)圖的畫法由左線性正規(guī)文法（產(chǎn)生式形如U->Wa|a)構(gòu)造狀態(tài)轉(zhuǎn)換圖。除了原有代表非終結(jié)符號的狀態(tài)，另增加一個開始狀態(tài)S,對于每一條產(chǎn)生式U->a，從狀態(tài)S向U畫一條弧，標(biāo)記為a，即12/22/202279第四章：詞法分析(3)狀態(tài)圖的畫法由左線性正規(guī)文法（產(chǎn)生式形如U->Wa(3)狀態(tài)轉(zhuǎn)換圖的畫法對于每一條產(chǎn)生式U->Wa，從狀態(tài)W向狀態(tài)U畫一條弧，標(biāo)記為a，即以識別符號為終止?fàn)顟B(tài)。12/22/202280第四章：詞法分析(3)狀態(tài)轉(zhuǎn)換圖的畫法對于每一條產(chǎn)生式U->Wa，從狀態(tài)W向例1:(a)表示在狀態(tài)1下,若輸入字符為X,則讀進(jìn)X,并轉(zhuǎn)換到狀態(tài)2.若輸入字符為Y,則讀進(jìn)Y,并轉(zhuǎn)換到狀態(tài)3.(b)表示在狀態(tài)0下,若輸入字符是一個字母,則讀進(jìn)它,并轉(zhuǎn)入狀態(tài)1.在狀態(tài)1下,若下一個輸入字符為字母或數(shù)字,則讀進(jìn)它,并重現(xiàn)進(jìn)入狀態(tài)1.一直重復(fù)這個過程,直到狀態(tài)1發(fā)現(xiàn)輸入不再是字母或數(shù)字就進(jìn)入狀態(tài)2.(c)為識別整數(shù)的轉(zhuǎn)換圖.終態(tài)結(jié)上打個星號*意味著多讀進(jìn)了一個不屬于標(biāo)識符部分的字符，應(yīng)把它退還給輸入串。12/22/202281第四章：詞法分析例1:(a)表示在狀態(tài)1下,若輸入字符為X,則讀進(jìn)X,并轉(zhuǎn)換例2:Ｃ語言無符號整數(shù)的描述八進(jìn)制數(shù):(OCT，值)oct→o(0|...|7)(0|...|7)*十進(jìn)制數(shù):(DEC，值)dec→0|(1|...|9)(0|...|9)*12/22/202282第四章：詞法分析例2:Ｃ語言無符號整數(shù)的描述八進(jìn)制數(shù):(OC整數(shù)的狀態(tài)圖（1/2）3421o0-70-756101-90-9十進(jìn)制整數(shù)八進(jìn)制整數(shù)12/22/202283第四章：詞法分析整數(shù)的狀態(tài)圖（1/2）3421o0-70-756101-9識別十六進(jìn)制整數(shù)的狀態(tài)圖。將上述三個狀態(tài)轉(zhuǎn)換圖合并為一個，得到Ｃ語言無符號整數(shù)識別的狀態(tài)圖，方法步驟：（1）從開始狀態(tài)出發(fā)；（2）選擇輸入符號，構(gòu)成目標(biāo)狀態(tài)集；（3）從新狀態(tài)集出發(fā)，重復(fù)（1）、（2）

12/22/202284第四章：詞法分析識別十六進(jìn)制整數(shù)的狀態(tài)圖。將上述三個狀態(tài)轉(zhuǎn)換圖合并為一個，得例3:識別某個簡單語言的所有單詞用一些帶$的特殊符號來表示種別編碼和內(nèi)部值12/22/202285第四章：詞法分析例3:識別某個簡單語言的所有單詞用一些帶$的特殊符號來表示種為了對例3進(jìn)行更好的說明，做了如下的限制：1）所有關(guān)鍵字（如IF，WHILE等）都是“保留字”； 2）對關(guān)鍵字不需專設(shè)對應(yīng)的轉(zhuǎn)換圖，而只需要將他們預(yù)先安排在一張表格中； 3）如果關(guān)鍵字、標(biāo)識符和常數(shù)之間沒有確定的運(yùn)算符或界符作間隔，則必須至少用一個空白符作間隔。 有了上述假定后，多數(shù)單詞符號的識別就不必使用超前搜索技術(shù)。下圖是一張識別表的單詞符號的狀態(tài)轉(zhuǎn)換圖。在圖中，狀態(tài)0為初態(tài)；凡帶雙圈者均為終態(tài)；狀態(tài)13是識別不出單詞符號的出錯情形。12/22/202286第四章：詞法分析為了對例3進(jìn)行更好的說明，做了如下的限制：12/16/202例3的狀態(tài)圖：12/22/202287第四章：詞法分析例3的狀態(tài)圖：12/16/202240第四章：詞法分析狀態(tài)轉(zhuǎn)換圖的實(shí)現(xiàn)讓每個狀態(tài)結(jié)點(diǎn)對應(yīng)一段小程序，即可用程序?qū)崿F(xiàn)狀態(tài)圖。在此引進(jìn)了一組全局變量和過程，將他們作為實(shí)現(xiàn)轉(zhuǎn)換圖的基本成分。它們是：1）ch字符變量，存放最新讀進(jìn)的源程序字符。2）strToken字符數(shù)組，存放構(gòu)成單詞符號的字符串。3）GetChar子程序過程，將下一輸入字符讀到ch中，搜索指示器前移一字符位置。4）GetBC子程序過程，檢查ch中的字符是否為空白。若是，則調(diào)用GetChar直至ch中進(jìn)入一個非空白字符。5）Concat子程序過程，將ch中的字符連接到strToken之后。例如，假定strToken原來的值為“AB”，而ch中存放‘C’，經(jīng)調(diào)用concat后，strToken的值就變?yōu)椤癆BC”。6）IsLetter和IsDigit布爾函數(shù)過程，分別判斷ch中的字符是否是字母和數(shù)字7）Reserve整型函數(shù)過程，對strToken中的字符串查