【正文】 )39。,NUL)、 integer (39。,字符串 ) ?運(yùn)算符 :=(39。,NUL) ?界符： ,(39。)39。39。 ㈢ 掃描器控制程序工作原理 ?每次識(shí)別單詞，控制程序總是從初態(tài)出發(fā)，不斷讀入字符，進(jìn)入下一狀態(tài)，尋求最長(zhǎng)匹配，直到無(wú)法前進(jìn)為止，這樣始終多讀一個(gè)字符。 ?由于構(gòu)造的方法不同，在 DFA某一個(gè)終態(tài)中，有可能包含原 NFA中的二個(gè)終態(tài)或更多，即在該狀態(tài)可識(shí)別出二個(gè)詞形相似的單詞，這就存在一個(gè)優(yōu)先匹配問題。因當(dāng)前所處狀態(tài) 1為終態(tài)，故識(shí)別出一個(gè)單詞。+39。+39。+39。因當(dāng)前所處狀態(tài) 1為終態(tài)，故識(shí)別出一個(gè)單詞。由于無(wú)法再讀入字符，即查表，確認(rèn)識(shí)別出單詞為 ，返回單詞二元式編碼 (39。在查表時(shí)可將 26個(gè)字母轉(zhuǎn)換成 1個(gè)，例 39。 2. if c是數(shù)字 then c←39。:←Nul:Token[]← 2. i←i+1:c←buf[i]: 當(dāng)前狀態(tài) ← 初態(tài) 3． while DFA[當(dāng)前狀態(tài) ,c]≠0 do 4. Token←Token,c //將 Token中字符串拼接字符 c后送 Token 5. 當(dāng)前狀態(tài) ← DFA[當(dāng)前狀態(tài) ,Tra(c)] 6. i←i+1 //指向下一字符 7. if buf[i]為空 then break 8. else c←buf[i] 9. end if 10. end while 11． if not(當(dāng)前狀態(tài) ∈ 終態(tài)集 ) then output Error:exit 12. ← 根據(jù) Token[]查表的結(jié)果 13. if =??? then //?表示單詞二元式編碼表中無(wú) 14. if Token首字符是字母 then =?i? //是標(biāo)識(shí)符 15. if Token首字符是數(shù)字 then =?x? //是整常數(shù) 16. ←Token[] //此時(shí)單詞有值 17. end if 18. return t 19. end procedure ?控制程序的工作原理和手工構(gòu)造相類似，差異在于如何實(shí)現(xiàn)狀態(tài)遷移。 結(jié)論 結(jié) 束 第 3章 程序設(shè)計(jì)語(yǔ)言的語(yǔ)法描述 文法的引入 上下文無(wú)關(guān)文法 文法舉例（略） 使用文法對(duì)程序設(shè)計(jì)語(yǔ)言的結(jié)構(gòu)進(jìn)行定義和描述。 上述英文句子可用下述規(guī)則來(lái)描述： 句子 主語(yǔ) 謂語(yǔ) 冠詞 形容詞 名詞 謂語(yǔ) the 形容詞 名詞 謂語(yǔ) the big 名詞 謂語(yǔ) the big elephant 謂語(yǔ) the big elephant 動(dòng)詞 直接賓語(yǔ) the big elephant ate 直接賓語(yǔ) the big elephant ate 冠詞 名詞 the big elephant ate a 名詞 the big elephant ate a banana 上述推導(dǎo)可簡(jiǎn)單表示為： 句子 the big elephant ate a banana。 例： U→xUy ，通常用大寫字母表示非終結(jié)符，用小寫字母表示終結(jié)符。但對(duì)于程序設(shè)計(jì)語(yǔ)言來(lái)說，上下文無(wú)關(guān)文法已經(jīng)夠用了，上下文無(wú)關(guān)文法有足夠的能力描述大多數(shù)現(xiàn)今使用的程序設(shè)計(jì)語(yǔ)言的語(yǔ)法結(jié)構(gòu)。 ① 終結(jié)符是語(yǔ)言的基本符號(hào)，即程序設(shè)計(jì)語(yǔ)言的單詞。 利用遞歸文法，可以用有窮的規(guī)則來(lái)描述無(wú)窮的語(yǔ)言，這不但解決了語(yǔ)言的定義問題，而且使得對(duì)語(yǔ)言的語(yǔ)法檢查成為可能。 ①遞歸定義：定義某事物，又用到該事物本身。 1. 句子 → 主語(yǔ) 謂語(yǔ) 2. 主語(yǔ) → 冠詞 形容詞 名詞 3. 冠詞 →the|a 4. 形容詞 →big 5. 名詞 →elephant|banana 6. 謂語(yǔ) → 動(dòng)詞 直接賓語(yǔ) 7. 直接賓語(yǔ) → 冠詞 名詞 8. 動(dòng)詞 →ate ㈢ 由規(guī)則推導(dǎo)句子 可用規(guī)則來(lái)推導(dǎo)出句子。 ?用戶可使用 LEX提供的語(yǔ)言編寫源程序，源程序由描述單詞的正規(guī)式和單詞的二元式編碼構(gòu)成。 ?單詞二元式編碼表 0. procedur scanner( ) 1. ←39。 ( ) 空格 0 1 2 3 4 5 6 7 8 9 10 0 1 11 11 0 0 0 0 0 0 0 0 0 2 0 12 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 4 0 0 0 13 0 0 0 0 0 0 0 5 0 0 0 0 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 0 0 0 7 0 0 0 0 0 0 0 0 0 0 0 8 0 0 0 0 0 0 0 0 0 0 0 9 0 0 0 0 0 0 0 0 0 0 0 10 0 0 0 0 0 0 0 0 0 0 0 11 11 11 0 0 0 0 0 0 0 0 0 12 0 12 0 0 0 0 0 0 0 0 0 13 0 0 0 0 0 0 0 0 0 0 0 狀態(tài)轉(zhuǎn)換矩陣經(jīng)數(shù)字化后如右所示： ? 轉(zhuǎn)換函數(shù) 0． procedure Tra(c) 1. if c是字母 then c←39。單詞的前導(dǎo)空格在識(shí)別一個(gè)單詞前被濾去，單詞的尾部空格用作單詞的終止標(biāo)志，故在狀態(tài)轉(zhuǎn)換矩陣中，應(yīng)增加空格列，該列每個(gè)元素的值均標(biāo)記為 0。39。39。因當(dāng)前所處狀態(tài) 4為終態(tài)，故識(shí)別出一個(gè)單詞。$39。+39。+39。首字符為字母的是標(biāo)識(shí)符，首字符為數(shù)字的是無(wú)符號(hào)整常數(shù)。 狀態(tài) /字符 α β = + * , 。=39。(39。,NUL)、++(39。,字符串 ) ?無(wú)符號(hào)整常數(shù)： (39。,NUL}、 end(39。(39。=39。z39。 ① a a a a ○ 0 b a b b ② b b 詞法分析器的自動(dòng)生成 輸入正規(guī)式（構(gòu)詞規(guī)則），經(jīng)自動(dòng)生成器加工，其結(jié)果為DFA。 ?ε_(tái)CLOSURE({X})視為 DFA M39。也屬于 ε_(tái)CLOSURE(I)。使得 L(M)=L(M39。 例某一非確定有限自動(dòng)機(jī) M=（ {1， 2， 3， 4， 5， 6}， {a， b}， f， {1， 2}， {3}） 其中 f的定義為： f(1,a)={4， 5}、 f(5， ε)={6}、 f(6， ε)={2}、 f(2， ab)={3} 其余情況 f(si， α) = { }（ α∈ Σ*， si∈ S） ㈡ NFA M可用一個(gè)（非確定的）狀態(tài)轉(zhuǎn)換圖表示 ⑤ ε ⑥ a ε ① ② ab a ④ ㈢ 字 α可為 NFA M識(shí)別 ?對(duì)于 Σ*中的一個(gè)字 α，若在 NFA M中存在一條從某一初態(tài)到某一終態(tài)的路徑，且路徑上的所有標(biāo)記依序連接成的字為 α，則稱 α可為 NFA M所識(shí)別或接受。路徑上的標(biāo)記依次連接為 101，則稱 α= 101可為 M所識(shí)別或接受。 ㈢ DFA M可用一個(gè)（確定的）狀態(tài)轉(zhuǎn)換圖表示 例識(shí)別二進(jìn)制數(shù)的 DFA可用（確定的）狀態(tài)轉(zhuǎn)換圖表示如下： 狀態(tài) /字符 39。) = f(0, 39。 ?s0∈ S，是唯一的一個(gè)初態(tài)。 ?正規(guī)式運(yùn)算符優(yōu)先性依次為 :*、 若 V=U，則 UV=VV=V2 正規(guī)式與正規(guī)集 ㈠ 正規(guī)式和正規(guī)集的定義： ?ε和 Φ是 ∑上的正規(guī)式，相應(yīng)的正規(guī)集為 {ε}、 { }。 ㈡ 字（字符串） ∑上字符所構(gòu)成的有限序列。 for(int i=0。 //找到尾 token[i]=c。 //返回標(biāo)識(shí)符或基本字的二元式 } ………………………………… //其余單詞識(shí)別程序略 }//end of scanner ① 拼接函數(shù) concat(token[],ch) concat為拼接函數(shù)，它有二個(gè)參數(shù)。 buf[i]=39。 amp。 //進(jìn)入標(biāo)識(shí)符或基本字的識(shí)別 if(buf[i]=39。\039。 //拼接單詞函數(shù) char reserve(char token[])。則緩沖區(qū)指針值不變；否則緩沖區(qū)指針值加 1，指向下一字符。39。y39。+39。設(shè)源程序?yàn)?x+++y（ 39。識(shí)別出的字符串（單詞）為 134.。由于空格不是任何單詞的組成部分（除字符串常數(shù)），故在識(shí)別單詞前，應(yīng)將單詞的前導(dǎo)空格濾去。狀態(tài)之間用箭弧連接。遍數(shù)多一點(diǎn)還有一個(gè)好處，即整個(gè)編譯程序的邏輯結(jié)構(gòu)較為清晰。 這樣空格、 TAB和換行符不再是沒有意義的了，這也就是為什么在詞法分析預(yù)處理中將空格、 TAB和換行符保留下來(lái)的原因。 ?IF()GOTO55 邏輯 IF，當(dāng) M等于 5轉(zhuǎn)標(biāo)號(hào)為 55的語(yǔ)句。 and cur_c=39。 then //進(jìn)入注釋 5. i←i 1:in_ment←true 6. else 7. if old_c=39。 ?定義布爾變量 in_ment，記錄當(dāng)前處理字符是否處于注釋。 ?對(duì)于受書寫格式限制的語(yǔ)言（例 Fortran和 Cobol），還應(yīng)識(shí)別標(biāo)號(hào)區(qū)，正確給出語(yǔ)句標(biāo)號(hào)。），當(dāng)一個(gè)單詞過長(zhǎng)（例字符串常數(shù)），可分多行列出。 設(shè)源程序如下所示，其中 39。 NUL 計(jì)算園柱體表面積的源程序（輸入輸出略）如下所示： Begin/*S=2** R* R +2** R*H */ Real r,h,s。 ?val表示單詞的值，在本書中用字符串表示。每當(dāng)識(shí)別出一個(gè)單詞，就用單詞的內(nèi)部碼（單詞二元式）替換。 為一個(gè)源語(yǔ)言構(gòu)造好前端，若要在某一個(gè)特定計(jì)算機(jī)上構(gòu)造該源語(yǔ)言的編譯程序，只要構(gòu)造這個(gè)目標(biāo)機(jī)器的后端即可。 常數(shù)的二進(jìn)制值 0000000000000011（ 3） 0000000001000000（ 128） …… 常數(shù)表的結(jié)構(gòu)示意如下： ㈣ 目標(biāo)代碼生成 (Code Generation) 執(zhí)行目標(biāo)代碼生成的程序稱為目標(biāo)代碼生成器。abc表示標(biāo)識(shí)符 abc在符號(hào)表中入口（即地址）； T1和 T2是在翻譯過程中由編譯程序引入的臨時(shí)變量， amp。常用的中間代碼有三元式和四元式。B=A+B。, NUL) (39。 ② 二元式編碼 單詞 單詞種別 單詞值 + + NUL NUL * * NUL / / NUL ( ( NUL ) ) NUL … … … 標(biāo)識(shí)符 i 字符串形式符號(hào)名 整常數(shù) x 字符串形式 整常數(shù) 實(shí)常數(shù) y 字符串形式 實(shí)常數(shù) … … … 經(jīng)詞分析，算術(shù)表達(dá)式 3+abc*128的單詞內(nèi)部碼（二元式）為： (39。 編譯過程概述 典型的編譯程序工作過程是：輸入源程序，對(duì)它進(jìn)行加工處理，最后輸出目標(biāo)程序（機(jī)器語(yǔ)言或匯編語(yǔ)言形式）。除操作系統(tǒng)外，程序運(yùn)行無(wú)需其它支撐軟件。 工作方式如下圖所示： ② 編譯方式 (Compile) 將源程序全部譯為目標(biāo)程序，該目標(biāo)程序可在操作系統(tǒng)環(huán)境下直接執(zhí)行，相應(yīng)的翻譯程序稱為編譯程序 (Compiler) ，工作方式如下圖所示： 編譯程序 Compile 連接程序 Link 裝入運(yùn)行 Run 編輯程序 Edit ASCII碼 二進(jìn)制 (整體未定位 ) 二進(jìn)制 (整體定位 ) 源程序 結(jié)果 輸入數(shù)據(jù) ?編輯程序的工作結(jié)果是 ASCII碼形式的源程序。機(jī)器語(yǔ)言程序用二進(jìn)制文件存儲(chǔ)，匯編語(yǔ)言或中間語(yǔ)言程序用文本文件存儲(chǔ)。 所以，程序設(shè)計(jì)語(yǔ)言極大地提高了編程效率，大幅度地降低了編程難度。 ?和機(jī)器語(yǔ)言一樣，匯編語(yǔ)言依附于目標(biāo)計(jì)算機(jī)。機(jī)器指令即二進(jìn)制數(shù)，通常由若干字節(jié)構(gòu)成。 } 注： 10表示 16 ㈠ 機(jī)器語(yǔ)言 機(jī)器指令集合稱為機(jī)器語(yǔ)言。 ② 缺點(diǎn) ?匯編語(yǔ)句和機(jī)器指令基本上是一對(duì)一的，所以匯編語(yǔ)言的編程效率并沒有質(zhì)的提高。 ?數(shù)據(jù)類型豐富，各種功能的語(yǔ)句齊備，一條語(yǔ)句至少相當(dāng)于幾十條匯編語(yǔ)句。 ㈢ 目標(biāo)語(yǔ)言和目標(biāo)程序 (Target Language and Target Program) 目標(biāo)語(yǔ)言可以是機(jī)器語(yǔ)言 (二進(jìn)制數(shù) )，也可以是匯編語(yǔ)言 (字符 )，或者是其它中間語(yǔ)言 (字符 )，但最終結(jié)果必定是機(jī)器語(yǔ)言。 ① 解釋方式 (Interpret) 以源程序作為輸入，輸入一句解釋執(zhí)行一句，不產(chǎn)生完整的目標(biāo)程序，相應(yīng)的翻譯程序稱為解釋程序 (Interpreter) 。用戶程序執(zhí)行時(shí)，控制點(diǎn)在用戶程序自身。 ④對(duì)任何一種高級(jí)語(yǔ)言，既可采用編譯方式，也可采用解釋方式，包括匯編語(yǔ)言在內(nèi)