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