編譯原理課件

1編譯原理

第一講引論課程信息編譯程序概述高級(jí)語(yǔ)言的語(yǔ)法描述3§1.課程信息一、課程名稱：編譯原理基本內(nèi)容是介紹編譯程序構(gòu)造的基本原理、方法和技術(shù)，包括詞法分析、語(yǔ)法分析、語(yǔ)義分析與中間代碼產(chǎn)生、代碼優(yōu)化及目標(biāo)代碼產(chǎn)生等。簡(jiǎn)言之，就是介紹如何將源程序翻譯成目標(biāo)代碼程序。4二、課程性質(zhì)：專業(yè)基礎(chǔ)課，必修編譯程序（器）出現(xiàn)于上世紀(jì)50年代后期（第一個(gè)高級(jí)語(yǔ)言1958年）60年代~70年代是研究高峰期60年代中期開(kāi)始在高校中開(kāi)設(shè)課程80年代開(kāi)始作為計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)的必修基礎(chǔ)課程5三、課程特點(diǎn)：充分體現(xiàn)了計(jì)算學(xué)科中抽象、理論和設(shè)計(jì)三個(gè)學(xué)科形態(tài)該課程涉及多門課程的內(nèi)容綜合運(yùn)用，涉及面廣，內(nèi)容龐雜，學(xué)習(xí)艱難程序設(shè)計(jì)語(yǔ)言、計(jì)算機(jī)體系結(jié)構(gòu)、語(yǔ)言理論及算法等離散數(shù)學(xué)、數(shù)據(jù)結(jié)構(gòu)該課程涉及的原理、方法和技術(shù)具有十分普遍的意義每一個(gè)計(jì)算機(jī)科學(xué)與技術(shù)工作者的職業(yè)生涯中反復(fù)用到，“享用一輩子”這兒接受的訓(xùn)練很難在其他地方獲得：

如：抽象與形式化方法、局部與全局優(yōu)化方法、構(gòu)造技術(shù)、證明方法等6四、學(xué)習(xí)該課程的意義編譯程序是計(jì)算機(jī)系統(tǒng)不可缺少的重要組成部分對(duì)程序設(shè)計(jì)語(yǔ)言的設(shè)計(jì)與實(shí)現(xiàn)能有更深刻的理解對(duì)程序設(shè)計(jì)語(yǔ)言有關(guān)理論有所了解從宏觀上把握程序設(shè)計(jì)語(yǔ)言——掌握了編譯原理后，就不能再說(shuō)：“某語(yǔ)言未學(xué)過(guò)，所以不會(huì)”有助于快速理解、定位和解決程序調(diào)試與運(yùn)行中出現(xiàn)的問(wèn)題7編譯方法與技術(shù)有著廣泛應(yīng)用安全技術(shù)、程序理解、軟件逆向工程、應(yīng)用軟件與軟件工具開(kāi)發(fā)、軟件測(cè)試與驗(yàn)證等編譯課程蘊(yùn)含著計(jì)算學(xué)科中解決問(wèn)題的思路、抽象和方法，這些與高等數(shù)學(xué)一樣，使你“享用一輩子”課程所涉及的內(nèi)容至今非?；钴S自然語(yǔ)言的翻譯軟件移植網(wǎng)絡(luò)安全形式化方法形式語(yǔ)義學(xué)等8

鑒于以上所述，作為計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)的學(xué)生必須學(xué)習(xí)和掌握編譯原理這門課程，當(dāng)然由于其綜合性、處理問(wèn)題的復(fù)雜性等，學(xué)習(xí)起來(lái)有一定難度，這就需要艱苦奮斗的精神和良好的學(xué)習(xí)方法9五、學(xué)習(xí)方法編譯程序的構(gòu)造是一個(gè)龐大而復(fù)雜的系統(tǒng)工程，無(wú)論是概念還是理論、方法，對(duì)初學(xué)者來(lái)說(shuō)許多都是新的，學(xué)習(xí)起來(lái)會(huì)感到困難大一些，這一點(diǎn)必須有充分認(rèn)識(shí)，為此建議學(xué)習(xí)方法上注意以下幾點(diǎn)：10課前預(yù)習(xí)，課堂認(rèn)真聽(tīng)講，課后復(fù)習(xí)加深理解，特別要經(jīng)常有意識(shí)地將前后內(nèi)容聯(lián)系起來(lái)融會(huì)貫通。因?yàn)榫幾g程序是一個(gè)龐大的程序系統(tǒng)，講解過(guò)程必須“分而治之”，這也是人們處理復(fù)雜問(wèn)題的基本方法，這就要求大家在學(xué)習(xí)過(guò)程中，始終以處理過(guò)程為主線，把前后聯(lián)系起來(lái)考慮。11理論聯(lián)系實(shí)際——親自動(dòng)手，構(gòu)造一個(gè)演示性編譯程序，至少要完成掃描器和語(yǔ)法分析器，以及語(yǔ)法制導(dǎo)翻譯產(chǎn)生中間代碼認(rèn)真完成作業(yè)，進(jìn)一步鞏固并加深理解所學(xué)知識(shí)特別要下功夫認(rèn)真學(xué)習(xí)如何從實(shí)際問(wèn)題進(jìn)行抽象并形式化，最終建立實(shí)際問(wèn)題的模型（上升為理性認(rèn)識(shí)），并借助模型進(jìn)一步設(shè)計(jì)實(shí)現(xiàn)，這將對(duì)你的能力提高大有益處12六、教材選擇：

《程序設(shè)計(jì)語(yǔ)言編譯原理》（第3版）

國(guó)防工業(yè)出版社陳火旺等內(nèi)容詳實(shí)豐富，理論與技術(shù)相結(jié)合新版充分考慮了新的研究成果——屬性文法、LR分析法、全局優(yōu)化等大多數(shù)院校一直采用，碩士入學(xué)考試參考書(shū)較為全面介紹了編譯程序構(gòu)造的基本原理、方法與技術(shù)13七、考試平時(shí)成績(jī)：30%期終考試成績(jī)：70%八、參考書(shū)目《編譯原理》陳意云張昱高教出版社《編譯原理》李建中姜守旭譯A.V.Aho,RavSethi,J.D.Ullman著

機(jī)械工業(yè)出版社《編譯原理及實(shí)踐》馮博琴馮嵐等譯KennethC.Louden著）

機(jī)械工業(yè)出版社14§2.編譯程序概述一、翻譯程序（Translator）

能夠把一種語(yǔ)言程序（稱為源語(yǔ)言程序）轉(zhuǎn)換成邏輯上等價(jià)的另一種語(yǔ)言程序（稱為目標(biāo)語(yǔ)言程序）的程序15任何非機(jī)器語(yǔ)言程序都需要翻譯程序翻譯程序的工作就是進(jìn)行等價(jià)變換（映射）兩個(gè)程序邏輯上等價(jià)是指對(duì)相同輸入得到相同的輸出翻譯程序解釋程序匯編程序編譯程序16匯編程序(Assembler)

把匯編語(yǔ)言程序轉(zhuǎn)變?yōu)闄C(jī)器語(yǔ)言程序的翻譯程序解釋程序(Interpreter)

把源程序作為輸入接收，邊解釋邊執(zhí)行的翻譯程序源程序數(shù)據(jù)解釋程序結(jié)果17編譯程序

將高級(jí)語(yǔ)言程序轉(zhuǎn)變?yōu)榈图?jí)語(yǔ)言程序的翻譯程序源程序編譯程序目標(biāo)程序18編譯程序又可根據(jù)用途和側(cè)重點(diǎn)的不同，進(jìn)一步分類為：

①診斷編譯程序(DiagnosticCompiler)

專門用于幫助程序開(kāi)發(fā)和調(diào)試的編譯程序

②優(yōu)化編譯程序(OptimizingCompiler)

著重于提高目標(biāo)代碼效率的編譯程序

③交叉編譯程序(CrossCompiler)

能夠產(chǎn)生不同于其宿主機(jī)機(jī)器代碼的編譯程序

④可變目標(biāo)編譯程序(Retargetablecomplier)

無(wú)須重寫與機(jī)器無(wú)關(guān)部分就能改變目標(biāo)機(jī)的編譯程序19二、與編譯程序相關(guān)的程序本講義只介紹編譯程序（器）構(gòu)造的基本原理、方法與技術(shù)，但在一個(gè)完整的語(yǔ)言開(kāi)發(fā)（或稱程序設(shè)計(jì)）環(huán)境中，除了編譯器這一主要工具外，還需要其他一些工具，如編輯器、連接器、裝入程序等?，F(xiàn)代計(jì)算機(jī)系統(tǒng)常將這些相互獨(dú)立的程序設(shè)計(jì)工具集成起來(lái)，構(gòu)成一個(gè)集成化的程序開(kāi)發(fā)環(huán)境，以提高程序設(shè)計(jì)效率和程序的質(zhì)量。如TurboC、VisualC++等語(yǔ)言環(huán)境都是集成化的程序設(shè)計(jì)環(huán)境。而Ada語(yǔ)言的集成環(huán)境是這方面的典型代表。20如Ada語(yǔ)言的集成環(huán)境是一個(gè)分層的程序開(kāi)發(fā)環(huán)境編譯程序MAPSE編輯程序連接程序宿主機(jī)OSAPSE工具界面用戶界面KAPSE調(diào)試程序配置管理程序命令解釋程序其他工具21

這兒要強(qiáng)調(diào)的是：盡管本課程只介紹編譯的基本理論、方法和技術(shù)，但這些基本理論、方法與技術(shù)對(duì)其他工具的構(gòu)造同樣起作用！22編輯器(Editor)

完成源程序輸入、編輯并產(chǎn)生標(biāo)準(zhǔn)文件（如ASCII文件）的程序。近來(lái)已與編譯器和其他程序捆綁進(jìn)一個(gè)交互開(kāi)發(fā)環(huán)境——IDE中盡管這樣的編輯器仍生成標(biāo)準(zhǔn)文件，但會(huì)轉(zhuǎn)向正被討論的程序設(shè)計(jì)語(yǔ)言的格式或結(jié)構(gòu)（稱為基于結(jié)構(gòu)的），且已包含了編譯器的某些操作；因此在程序編寫時(shí)而不是編譯時(shí)就可得知錯(cuò)誤，甚至也可調(diào)用編譯器23預(yù)處理程序(Preprocessor)

在真正翻譯開(kāi)始之前產(chǎn)生編譯程序的輸入的程序處理宏及注釋：宏是被經(jīng)常使用的較長(zhǎng)結(jié)構(gòu)的縮寫處理文件包含：把頭文件包含到程序正文中（如C的文件包含include<….h>）“理解”預(yù)處理器：把現(xiàn)代控制流和數(shù)據(jù)結(jié)構(gòu)機(jī)制添加到比較老式的語(yǔ)言中語(yǔ)言擴(kuò)充：通過(guò)大量的內(nèi)部宏定義來(lái)增強(qiáng)語(yǔ)言的能力，如Equel語(yǔ)言是一種嵌套在C語(yǔ)言中的數(shù)據(jù)庫(kù)查詢語(yǔ)言24連接程序(Linker)——又稱為連接編輯器。將分別在不同的目標(biāo)文件中編譯（或匯編）的代碼、所用標(biāo)準(zhǔn)庫(kù)函數(shù)的代碼以及操作系統(tǒng)提供的資源（如存儲(chǔ)分配程序及輸入/輸出設(shè)備）收集到一個(gè)可直接執(zhí)行的文件中的程序裝配程序(Loader)

完成程序的裝入和連接編輯兩項(xiàng)功能。裝入過(guò)程包括讀入可重定位機(jī)器代碼、修改可重定位地址、并將修改后的指令和數(shù)據(jù)放到內(nèi)存的適當(dāng)位置。

裝入程序使得可執(zhí)行代碼更加靈活25調(diào)試程序(Debugger)

可在被編譯了的程序中判定執(zhí)行錯(cuò)誤的程序它經(jīng)常與編譯程序一起放在IDE中運(yùn)行一個(gè)帶有調(diào)試程序的程序與直接執(zhí)行不同，這是因?yàn)檎{(diào)試程序保存著所有的或大多數(shù)源代碼信息，它可以在預(yù)先指定的位置（斷點(diǎn)BreakPoint）暫停執(zhí)行，并提供有關(guān)信息（已調(diào)用的函數(shù)、變量名的當(dāng)前值等）26其他有關(guān)的還有描述器(Profiler)——執(zhí)行中搜集目標(biāo)程序行為統(tǒng)計(jì)的程序項(xiàng)目管理程序(ProjectManager)——如Unix系統(tǒng)中的SCCS（源代碼控制系統(tǒng)）和RCS（修正控制系統(tǒng)）和匯編程序等綜上所述可給出一個(gè)“語(yǔ)言處理系統(tǒng)”的圖示：27我們這個(gè)課只介紹編譯程序這一部分28三、編譯過(guò)程與編譯程序結(jié)構(gòu)

1.編譯過(guò)程：

輸入輸出（高級(jí)語(yǔ)言源程序）（低級(jí)語(yǔ)言目標(biāo)程序）

編譯程序工作過(guò)程如下：識(shí)別出一個(gè)個(gè)的單詞分析句子的語(yǔ)法結(jié)構(gòu)分析句子的語(yǔ)義并進(jìn)行初步翻譯對(duì)初步翻譯進(jìn)行優(yōu)化整理出目標(biāo)程序?qū)σ陨线^(guò)程進(jìn)一步整理可得如下編譯程序結(jié)構(gòu)總框：編譯程序292.編譯程序總框：詞法分析器語(yǔ)法分析器語(yǔ)義分析與中間代碼產(chǎn)生器優(yōu)化器目標(biāo)代碼生成器單詞符號(hào)語(yǔ)法單位中間代碼中間代碼出錯(cuò)處理表格管理源程序目標(biāo)代碼303.五個(gè)階段簡(jiǎn)介第一階段：詞法分析——依據(jù)語(yǔ)言構(gòu)詞規(guī)則，識(shí)別出一個(gè)個(gè)單詞（符號(hào)）

單詞種類基本字：for，if，while等算符：＋，－，×，／等界符：，；（）等標(biāo)識(shí)符：a123，pi等常數(shù)：9，36，4.8，6E6等無(wú)窮性有窮性！31

詞法分析工作由詞法分析器（或稱掃描器）完成。

掃描器輸出為等長(zhǎng)度的單詞符號(hào)（二元式）流。

例：Position:=initial+rate*60詞法分析（掃描器）基本字表(06,‘Position’)(11,─)(06,‘initial’)(12,─)(06,‘rate’)(13,─)(07,’60的二進(jìn)制’)32第二階段：語(yǔ)法分析——依據(jù)語(yǔ)言的語(yǔ)法規(guī)則，把掃描器提供的單詞符號(hào)串分解成各種語(yǔ)法單位（范疇），如“短語(yǔ)”、“子句”、“句子”乃至“程序”。同時(shí)進(jìn)行語(yǔ)法檢查，以確定輸入串是否正確，該工作是由語(yǔ)法分析器完成的。

如：Position=initial+rate*60是一個(gè)“賦值表達(dá)式”（C語(yǔ)言中）Position=表達(dá)式表達(dá)式表達(dá)式+表達(dá)式標(biāo)示符表達(dá)式*表達(dá)式initial標(biāo)示符常數(shù)rate60標(biāo)示符33第三階段：語(yǔ)義分析與中間代碼產(chǎn)生——針對(duì)各類不同的語(yǔ)法范疇，按語(yǔ)言的語(yǔ)義規(guī)則進(jìn)行語(yǔ)義分析和初步翻譯工作，產(chǎn)生某種中間語(yǔ)言形式的中間代碼（即一種結(jié)構(gòu)簡(jiǎn)單，含義明確的記號(hào)系統(tǒng)）

該階段工作通常包括兩個(gè)方面的工作：

對(duì)每種語(yǔ)法范疇進(jìn)行靜態(tài)語(yǔ)義檢查，包括：變量是否定義過(guò)類型是否正確是否用了0作除數(shù)等34將語(yǔ)法范疇翻譯成某種形式的中間代碼，如四元式：OpARG1ARG2Result＊rate60T1＋initialT1T2:=T2Position35第四階段：優(yōu)化——對(duì)前階段產(chǎn)生的中間代碼進(jìn)行加工變換，以期在最后階段能產(chǎn)生出高效（節(jié)省時(shí)、空）的目標(biāo)代碼，這一任務(wù)是由優(yōu)化器來(lái)完成的根據(jù)優(yōu)化的范圍不同，可分為：

局部?jī)?yōu)化，循環(huán)優(yōu)化和全局優(yōu)化一個(gè)循環(huán)優(yōu)化的例子：36⑴＝1K⑴＝IM⑵J<100K⑼⑵＝JN⑶＊10KT1⑶＝1K⑷＋I(xiàn)T1M⑷J<100K⑼⑸＊10KT2⑸＋M10M⑹＋JT2N⑹＋N10N⑺＋K1K⑺＋K1K⑻Ｊ⑵⑻Ｊ⑷⑼…⑼…循環(huán)語(yǔ)句為：For(k=1;k<=100;k++){M=I+10*k;N=J+10*k;}優(yōu)化前用了兩個(gè)臨時(shí)工作單元(T1,T2),優(yōu)化后沒(méi)有用臨時(shí)單元優(yōu)化前循環(huán)體中要做300次加、200次乘，

優(yōu)化后循環(huán)體內(nèi)只做300次加37第五階段：目標(biāo)代碼生成——把中間代碼翻譯成目標(biāo)代碼顯然這階段要依賴于硬體系統(tǒng)結(jié)構(gòu)和指令系統(tǒng)涉及存貯分配、寄存器調(diào)度這一階段工作是由代碼生成器完成的說(shuō)明：以上各階段（或稱工序）并不是截然分開(kāi)的，尤其編譯程序結(jié)構(gòu)十分復(fù)雜、體積相當(dāng)龐大，所以有時(shí)人們把幾個(gè)階段的工作有機(jī)地組合在一起、穿插進(jìn)行，構(gòu)成遍。38遍（Pass）：對(duì)源程序或源程序的中間代碼從頭到尾掃描一次并做相應(yīng)處理加工分遍的好處是結(jié)構(gòu)清晰、節(jié)省內(nèi)存（每遍都從外存獲取前一遍的結(jié)果作為開(kāi)始，工作結(jié)果仍記入外存，每遍幾乎可使用全部?jī)?nèi)存）分不分遍、如何分遍要視具體情況——計(jì)算機(jī)內(nèi)存容量、源語(yǔ)言的繁簡(jiǎn)、從事編譯程序設(shè)計(jì)人員的情況等39如最早的基本BASIC語(yǔ)言采用一遍掃描的編譯程序：返回符號(hào)源程序掃描器語(yǔ)法分析器整理目標(biāo)程序停機(jī)語(yǔ)義分析器存儲(chǔ)分配器代碼生成器取字符取符號(hào)構(gòu)造返回目標(biāo)程序40又如PL/0編譯程序的結(jié)構(gòu)詞法分析程序語(yǔ)法語(yǔ)義分析程序代碼生成程序PL/0源程序目標(biāo)程序表格管理程序出錯(cuò)處理程序41再如COBOL編譯程序采用了四遍掃描的編譯程序：源程序詞法分析與名等內(nèi)碼內(nèi)碼生成器數(shù)據(jù)名長(zhǎng)度計(jì)算與過(guò)程部分分析器數(shù)據(jù)結(jié)構(gòu)特性解釋程序數(shù)據(jù)特性記錄器數(shù)據(jù)結(jié)構(gòu)記錄器目標(biāo)生成器長(zhǎng)度表數(shù)組信息表字表指源表樹(shù)表目標(biāo)程序形象字符表(Pic)基詞表外名表文字信息表配對(duì)矩陣表424.前端與后端：概念上講，編譯程序的五個(gè)階段可進(jìn)一步劃分為前端和后端：前端：主要由與源語(yǔ)言有關(guān)而與目標(biāo)機(jī)無(wú)關(guān)的部分組成，包括詞法分析、語(yǔ)法分析、語(yǔ)義分析和中間代碼產(chǎn)生。代碼優(yōu)化一般也包含在前端。后端：主要由與目標(biāo)機(jī)有關(guān)的部分組成，包括目標(biāo)代碼生成和與目標(biāo)機(jī)有關(guān)的優(yōu)化等。詳見(jiàn)下圖：43源程序詞法分析語(yǔ)法分析語(yǔ)義分析和中間代碼產(chǎn)生中間語(yǔ)言中間代碼優(yōu)化目標(biāo)代碼生成目標(biāo)代碼優(yōu)化目標(biāo)語(yǔ)言前端后端44

劃分前端和后端，就可以僅改寫后端而生成不同目標(biāo)機(jī)上的目標(biāo)程序，當(dāng)然也可考慮對(duì)不同語(yǔ)言僅稍加改變前端而產(chǎn)生相同的中間代碼，經(jīng)同一后端生成相同目標(biāo)機(jī)的目標(biāo)代碼。就目前來(lái)說(shuō)，針對(duì)相同中間代碼適應(yīng)不同目標(biāo)機(jī)的工作較多，如Ada語(yǔ)言的APSE(Ada程序設(shè)計(jì)環(huán)境)中使用的Diana中間代碼，Java語(yǔ)言定義的虛擬機(jī)代碼——Bytecode中間語(yǔ)言，都是定義良好的中間語(yǔ)言。詳見(jiàn)下圖：45Java的傳統(tǒng)環(huán)境Java源程序(.java)編譯環(huán)境Java編譯器Java字節(jié)碼(.class)Java字節(jié)碼（本地或網(wǎng)絡(luò)傳輸）運(yùn)行環(huán)境類加載程序字節(jié)碼驗(yàn)證Java類庫(kù)Java解釋器即時(shí)編譯器Java虛擬機(jī)硬件465.表格與表格管理表格記錄源程序中的各類有用信息——名字、函數(shù)、標(biāo)號(hào)、過(guò)程、數(shù)值等每個(gè)階段的工作都要與表格打交道：查、填、改等表格的結(jié)構(gòu)與處理方法：統(tǒng)一的大表與分類的小表統(tǒng)一大表名字欄為主欄（關(guān)鍵字欄），信息欄又分成若干子欄——種屬、類型等NAMEINFORMATION47分類小表：每類一張表，如：符號(hào)名表(SNT)

常數(shù)表(CT)

3.141592648…X啞元實(shí)型A數(shù)組整型

…………48DO編號(hào)(03)……L1入口地址……Swap二目子程序

入口地址……入口表(ENT)

標(biāo)號(hào)表(LBT)

基本字表

(KWT)496.出錯(cuò)處理：這是編譯程序的又一重要組成部分，因?yàn)榫幾g的各個(gè)階段都有可能發(fā)現(xiàn)源程序中的錯(cuò)誤。一旦發(fā)現(xiàn)這樣或那樣的錯(cuò)誤，就應(yīng)把錯(cuò)誤的性質(zhì)及位置報(bào)告給用戶，并且使編譯能繼續(xù)下去。50四、編譯程序的構(gòu)造過(guò)程1.需求分析，確定語(yǔ)言文本(1)確定語(yǔ)言的種類：

按語(yǔ)言范型分類，當(dāng)今大多數(shù)程序語(yǔ)言可分為四類：過(guò)程式(強(qiáng)制式語(yǔ)言)：命令驅(qū)動(dòng)，面向語(yǔ)句，如FORTRAN、PASCAL、Ada及C等函數(shù)式(應(yīng)用式)語(yǔ)言：功能驅(qū)動(dòng)，面向函數(shù)，如LISP、SNOBOL及ML等邏輯式(基于規(guī)則的)語(yǔ)言：依據(jù)條件進(jìn)行邏輯推演，如Prolog等OO語(yǔ)言：支持封裝性、繼承性、多態(tài)性及動(dòng)態(tài)聚束等，以對(duì)象為運(yùn)行單位，如Smalltalk、Java、C++等51

通過(guò)用戶提供的應(yīng)用范圍，決定采用何種語(yǔ)言。例如：偏重于科學(xué)計(jì)算的則選用Fortran；偏重于符號(hào)處理的則選用Lisp或Snobol；偏重于事務(wù)處理的則選用Cobol或數(shù)據(jù)庫(kù)管理語(yǔ)言；

……52(2)深刻理解語(yǔ)言的結(jié)構(gòu)、語(yǔ)法及語(yǔ)義這就是說(shuō)不僅僅是用程序設(shè)計(jì)語(yǔ)言編幾個(gè)程序的問(wèn)題，而是要在語(yǔ)法和語(yǔ)義方面下一些功夫。具體說(shuō)來(lái)有以下幾個(gè)方面：①程序語(yǔ)言的定義：任何程序語(yǔ)言都是某個(gè)確定的字符集上的符號(hào)按照一定規(guī)則組成的有窮序列。這里所謂的規(guī)則是從兩個(gè)方面來(lái)談的：

·語(yǔ)法規(guī)則：用于形成和產(chǎn)生一個(gè)正確的程序的一組規(guī)則。

·語(yǔ)義規(guī)則：用于定義程序意義的一組規(guī)則。53例如：從語(yǔ)法的角度看，標(biāo)識(shí)符和名字是一個(gè)東西，都是以字母開(kāi)頭的字母數(shù)字串；但從語(yǔ)義的角度看，標(biāo)識(shí)符是一個(gè)沒(méi)有任何意義的字符序列，而名字卻有確定的意義和屬性，而且具有一定的作用域和定義域，即有局部和全部之分。又如：程序從語(yǔ)法角度看，是一些語(yǔ)法范疇構(gòu)成的如下層次結(jié)構(gòu)：54程序分程序或子程序（過(guò)程、函數(shù)等）語(yǔ)句表達(dá)式數(shù)據(jù)引用算符函數(shù)調(diào)用而從語(yǔ)義的角度來(lái)說(shuō)，程序是描述一定的數(shù)據(jù)結(jié)構(gòu)及其處理過(guò)程。55②程序結(jié)構(gòu)：現(xiàn)代高級(jí)語(yǔ)言程序通常由若干子程序段（過(guò)程、函數(shù)等）構(gòu)成，許多語(yǔ)言還引入了類、程序包等更高級(jí)的結(jié)構(gòu)。例如，F(xiàn)ortran、C程序是塊結(jié)構(gòu)的；Pascal程序是過(guò)程嵌套的；Algol既有分程序嵌套，又有過(guò)程嵌套；Java與C++是面向?qū)ο蟮?，它們很重要的方面是類和繼承的概念，同時(shí)支持多態(tài)性和動(dòng)態(tài)聚束等特性；而在Ada中引入了程序包，它可以把數(shù)據(jù)和操作代碼封裝在一起，支持?jǐn)?shù)據(jù)抽象。（詳見(jiàn)教材P15-18）56③語(yǔ)言的基本成分：包括數(shù)據(jù)類型、表達(dá)式、語(yǔ)句、過(guò)程或函數(shù)等，這些在學(xué)習(xí)語(yǔ)言課時(shí)都已經(jīng)學(xué)過(guò)了，但從編譯的角度出發(fā)，應(yīng)如何了解這些基本成分呢？

·初等數(shù)據(jù)類型：牽扯到存儲(chǔ)空間的問(wèn)題；

·結(jié)構(gòu)數(shù)據(jù)類型：牽扯到下標(biāo)、維數(shù)、存放方式、分配時(shí)間----動(dòng)態(tài)與靜態(tài)等；

·表達(dá)式：牽扯到運(yùn)算分量、運(yùn)算符、形成規(guī)則、運(yùn)算順序等；

·語(yǔ)句：順序、控制、循環(huán)等；

·過(guò)程與參數(shù)傳遞：傳地址、傳值、傳名、得結(jié)果等；

·存儲(chǔ)管理：靜態(tài)存儲(chǔ)分配、動(dòng)態(tài)存儲(chǔ)分配；572.由程序設(shè)計(jì)環(huán)境確定編譯程序構(gòu)造的方式和方法最早是直接使用機(jī)器語(yǔ)言或匯編語(yǔ)言現(xiàn)在一般使用高級(jí)語(yǔ)言Pascal或C語(yǔ)言

好處：編譯方式還是解釋方式便于閱讀、理解和移植提高程序設(shè)計(jì)效率易于查錯(cuò)和修改58

任何一個(gè)編譯程序至少要涉及三種語(yǔ)言：源語(yǔ)言（S）、目標(biāo)語(yǔ)言（T）和編譯程序?qū)崿F(xiàn)語(yǔ)言（I），可用如下T型圖來(lái)表示三者之間的關(guān)系：STI59Ada語(yǔ)言A

代碼Ada語(yǔ)言A

代碼CCA代碼A代碼A代碼用C語(yǔ)言編寫Ada編譯程序

如若A機(jī)上已經(jīng)有了一個(gè)用A機(jī)器語(yǔ)言（稱A代碼）實(shí)現(xiàn)的C語(yǔ)言編譯程序，則可用C語(yǔ)言作為工具編寫Ada語(yǔ)言的編譯程序。這樣Ada語(yǔ)言的編譯程序經(jīng)過(guò)C語(yǔ)言編譯程序編譯后就可得到A代碼的Ada語(yǔ)言編譯程序?？蓤D示如下：60現(xiàn)在常用構(gòu)造編譯程序的方式除高級(jí)語(yǔ)言實(shí)現(xiàn)外，經(jīng)常還用：自展（自編譯）：類似于滾雪球。先確定一個(gè)非常簡(jiǎn)單的核心L0，用低級(jí)語(yǔ)言寫出其編譯程序C0。再把L0擴(kuò)充為L(zhǎng)1

，

，

并用L0來(lái)編寫L1的編譯程序。如此逐漸擴(kuò)展下去，可得到一個(gè)系統(tǒng)編程語(yǔ)言族：

而Lk便是我們要編譯的語(yǔ)言，其編譯程序Ck可用Lk-1編寫。這種滾雪球式的自展方法可大大減少開(kāi)發(fā)工作量。61交叉編譯：在機(jī)器A上產(chǎn)生機(jī)器B的目標(biāo)代碼，這種編譯程序稱為交叉編譯。這兒A稱宿主機(jī)，B稱為目標(biāo)機(jī)。這種情況一般是宿主機(jī)上有豐富的工具軟件，而B(niǎo)機(jī)上沒(méi)有任何高級(jí)語(yǔ)言可用。圖示為：CB

代碼CB

代碼CCB代碼B代碼A代碼62移植：如果一個(gè)程序能比較容易地從一臺(tái)機(jī)器上搬到另一臺(tái)機(jī)器上運(yùn)行，則稱其為可移植的，移植一個(gè)程序的工作量要遠(yuǎn)小于開(kāi)發(fā)它的工作量才有意義。

顯然一個(gè)編譯程序要可移植，則其前端與后端的界面要清晰、簡(jiǎn)單，這樣僅需改寫后端即可。改寫后亦可通過(guò)交叉編譯的方法得到。63編譯程序生成器：根據(jù)語(yǔ)言要求、設(shè)計(jì)實(shí)現(xiàn)的算法，能自動(dòng)產(chǎn)生編譯程序的工具軟件。可圖示為：643.確定編譯方法：本課程要介紹若干方法，但不可能全采用，只能根據(jù)語(yǔ)言特點(diǎn)采用其中一種或二種4.總體設(shè)計(jì)：分不分遍、分幾遍、前端與后端接口并畫出總框5.詳細(xì)設(shè)計(jì)：進(jìn)一步細(xì)劃總框6.實(shí)現(xiàn)及調(diào)試：采用何種方式實(shí)現(xiàn)、分調(diào)與連調(diào)等65本節(jié)目的：為語(yǔ)言的語(yǔ)法描述尋求形式化工具

工具就是對(duì)程序設(shè)計(jì)語(yǔ)言給出精確無(wú)二義的語(yǔ)法描述。（嚴(yán)謹(jǐn)、簡(jiǎn)潔、易讀）形式化工具就是將形式語(yǔ)言抽象地定義為一個(gè)數(shù)學(xué)系統(tǒng)?！靶问健笔侵高@樣的事實(shí)：語(yǔ)言的所有規(guī)則是以什麼符號(hào)串能出現(xiàn)的方式來(lái)陳述。

§3.高級(jí)語(yǔ)言的語(yǔ)法描述66本節(jié)主要內(nèi)容

預(yù)備知識(shí)

上下文無(wú)關(guān)文法及其語(yǔ)言的形式定義

文法的等價(jià)性

語(yǔ)法樹(shù)及文法二義性

文法的類型

語(yǔ)法分析的一些思考67一、預(yù)備知識(shí)1.文法的直觀概念當(dāng)我們表述一種語(yǔ)言時(shí)，無(wú)非是說(shuō)明這種語(yǔ)言的句子，如果語(yǔ)言只含有有窮多個(gè)句子，則只需列出句子的有窮集就行了，但對(duì)于含有無(wú)窮多個(gè)句子的語(yǔ)言來(lái)講，存在著如何給出它有窮表示的問(wèn)題。以自然語(yǔ)言為例，人們無(wú)法列出全部句子，但是人們可以給出一些規(guī)則，用這些規(guī)則來(lái)說(shuō)明(或者定義)句子的組成結(jié)構(gòu)，比如漢語(yǔ)句子可以是由主語(yǔ)后隨謂語(yǔ)而成，構(gòu)成謂語(yǔ)的是動(dòng)詞和直接賓語(yǔ)。例如：68“我是大學(xué)生”是漢語(yǔ)的一個(gè)句子

對(duì)該句子我們可以通過(guò)下列一組規(guī)則描述：〈句子〉∷=〈主語(yǔ)〉〈謂語(yǔ)〉〈主語(yǔ)〉∷=〈代詞〉｜〈名詞〉〈代詞〉∷=我｜你｜他〈名詞〉∷=王明｜大學(xué)生｜工人｜英語(yǔ)〈謂語(yǔ)〉∷=〈動(dòng)詞〉〈直接賓語(yǔ)〉〈動(dòng)詞〉∷=是｜學(xué)習(xí)〈直接賓語(yǔ)〉∷=〈代詞〉｜〈名詞〉有了這組規(guī)則以后，可按如下方式導(dǎo)出句子：先找∷=左端的帶有〈句子〉的規(guī)則，并將它用∷=右端的符號(hào)串代替，于是表示成：

69

〈句子〉

〈主語(yǔ)〉〈謂語(yǔ)〉然后在得到的串〈主語(yǔ)〉〈謂語(yǔ)〉中，選取〈主語(yǔ)〉或〈謂語(yǔ)〉，再用相應(yīng)規(guī)則的∷=右端代替之。比如，選取了〈主語(yǔ)〉，并采用規(guī)則〈主語(yǔ)〉∷=〈代詞〉，那么得到：

〈主語(yǔ)〉〈謂語(yǔ)〉

〈代詞〉〈謂語(yǔ)〉依此類推，句子“我是大學(xué)生”的全部導(dǎo)出過(guò)程是：

〈句子〉

〈主語(yǔ)〉〈謂語(yǔ)〉

〈代詞〉〈謂語(yǔ)〉

我〈謂語(yǔ)〉

我〈動(dòng)詞〉〈直接賓語(yǔ)〉

我是〈直接賓語(yǔ)〉

我是〈名詞〉

我是大學(xué)生70“我是大學(xué)生”的構(gòu)成符合上述規(guī)則，而“我大學(xué)生是”不符合上述規(guī)則，我們說(shuō)它不是句子。這些規(guī)則成為我們判別句子結(jié)構(gòu)合法與否的依據(jù)。換句話說(shuō)，這些規(guī)則看成是一種元語(yǔ)言，用它描述漢語(yǔ)，僅僅涉及漢語(yǔ)句子的結(jié)構(gòu)描述。這里“

”讀作“導(dǎo)出”或“派生出”。而“::=”（通常又簡(jiǎn)記為“→”）讀作“定義為”或“由…組成”，而每一條規(guī)則又稱作是產(chǎn)生式或重寫式。這樣的一種描述形式就稱作是BNF（BackusNormalForm）。71例如C語(yǔ)言中的賦值表達(dá)式可描述為：

<賦值表達(dá)式>→<左部>=<右部><左部>→<標(biāo)識(shí)符><右部>→<表達(dá)式><表達(dá)式>→<表達(dá)式><算符><表達(dá)式><表達(dá)式>→<標(biāo)識(shí)符>|<常數(shù)><標(biāo)識(shí)符>→<字母>(<字母>|<數(shù)字>)n

<字母>→A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z|a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z<數(shù)字>→0|1|2|3|4|5|6|7|8|9<算符>→+|-|*|/722.語(yǔ)言概述語(yǔ)言是由句子組成的集合。漢語(yǔ)--所有符合漢語(yǔ)語(yǔ)法的句子的全體。英語(yǔ)--所有符合英語(yǔ)語(yǔ)法的句子的全體。程序設(shè)計(jì)語(yǔ)言--所有該語(yǔ)言的程序的全體。

每個(gè)句子構(gòu)成的規(guī)則研究語(yǔ)言每個(gè)句子的含義每個(gè)句子和使用者的關(guān)系73研究程序設(shè)計(jì)語(yǔ)言每個(gè)程序構(gòu)成的規(guī)則每個(gè)程序的含義每個(gè)程序和使用者的關(guān)系語(yǔ)言研究的三個(gè)方面:

語(yǔ)法(Syntax)--表示構(gòu)成語(yǔ)言句子的各個(gè)記號(hào)之間的組合規(guī)則語(yǔ)義(Semantics)--表示各個(gè)記號(hào)的特定含義。（各個(gè)記號(hào)和記號(hào)所表示的對(duì)象之間的關(guān)系）語(yǔ)用(Pragmatics)--表示在各個(gè)記號(hào)所出現(xiàn)的行為中，它們的來(lái)源、使用和影響。74

每種語(yǔ)言具有兩個(gè)可識(shí)別的特性，即語(yǔ)言的形式和該形式相關(guān)聯(lián)的意義。語(yǔ)言的實(shí)例若在語(yǔ)法上是正確的，其相關(guān)聯(lián)的意義可以從兩個(gè)觀點(diǎn)來(lái)看，其一是該句子的創(chuàng)立者所想要表示的意義，另一是接收者所檢驗(yàn)到的意義。這兩個(gè)意義并非總是一樣的，前者稱為語(yǔ)言的語(yǔ)義，后者是其語(yǔ)用意義。幽默、雙關(guān)語(yǔ)和謎語(yǔ)就是利用這兩方面意義間的差異。75

如果不考慮語(yǔ)義和語(yǔ)用，即只從語(yǔ)法這一側(cè)面來(lái)看語(yǔ)言，這種意義下的語(yǔ)言稱作形式語(yǔ)言。形式語(yǔ)言抽象地定義為一個(gè)數(shù)學(xué)系統(tǒng)。該數(shù)學(xué)系統(tǒng)稱為文法?！靶问健笔侵高@樣的事實(shí)：語(yǔ)言的所有規(guī)則描述什麼符號(hào)串以什么方式出現(xiàn)。形式語(yǔ)言理論是對(duì)符號(hào)串集合的表示法、結(jié)構(gòu)及其特性的研究，是程序設(shè)計(jì)語(yǔ)言語(yǔ)法分析研究的基礎(chǔ)。763.有關(guān)定義和記號(hào)—回顧符號(hào)：可以相互區(qū)別的記號(hào)（元素）。字母表

：符號(hào)（元素）的非空有窮集合。符號(hào)串(字)：由字母表

中的符號(hào)組成的任何有窮序列稱為該字母表上的符號(hào)串。

①空字ε(沒(méi)有符號(hào)的符號(hào)串)是

上的符號(hào)串；

②若x是

上的符號(hào)串,a是

的元素,則xa是

上的符號(hào)串；

③y是

上的符號(hào)串,當(dāng)且僅當(dāng)它可以由①和②

導(dǎo)出。

例如：Σ={a,b}ε,a,b,aa,ab,aabba…都是

上的符號(hào)串77符號(hào)串s的前綴：符號(hào)串s的任何首部。如:ε、b、ba、…都是符號(hào)串banana的前綴.符號(hào)串s的后綴：符號(hào)串s的任何尾部。如:ε、a、na、…都是符號(hào)串banana的后綴.符號(hào)串s的子串：從s中刪去一個(gè)前綴和一個(gè)后綴得到的符號(hào)串.

如:ana是符號(hào)串banana的一個(gè)子串.符號(hào)串s的真前綴：x≠s且x≠ε的任何前綴x。s的真后綴，真子串可以類似地定義。78符號(hào)串的運(yùn)算：

符號(hào)串的長(zhǎng)度：符號(hào)串中符號(hào)的個(gè)數(shù).符號(hào)串s的長(zhǎng)度記為|s|。ε的長(zhǎng)度為0連接：符號(hào)串x、y的連接,是把y的符號(hào)寫在x的符號(hào)之后得到的符號(hào)串xy

如x=ab,y=cd則xy=abcd

又如εa=aε方冪：符號(hào)串自身連接n次得到的符號(hào)串

an定義為aa……aan個(gè)aa0=ε,a1=a,a2=aa…79符號(hào)串集合：若集合A中所有元素都是某字母表

上的符號(hào)串，則稱A為字母表

上的符號(hào)串集合。符號(hào)串集合A和B的乘積：

AB=xy|xA且yB若集合A=ab,cdeB=0,1則AB=ab1,ab0,cde0,cde1Σ的閉包：

上的一切符號(hào)串（包括ε）組成的集合，記為*。Σ的正閉包：

上的除ε外的所有符號(hào)串組成的集合，記為

+。80例：Σ={a,b}Σ*={ε,a,b,aa,ab,ba,bb,aaa,aab,…}Σ+={a,b,aa,ab,ba,bb,aaa,aab,…}

81語(yǔ)言：由句子構(gòu)成的集合。換言之,字母表

上的一個(gè)語(yǔ)言是

上的一些符號(hào)串的集合

(字母表

上的每個(gè)語(yǔ)言是*的一個(gè)子集)。例如：字母表Σ={a,b},Σ*={ε,a,b,aa,ab,ba,bb,aaa,aab,…}

集合{ab,aabb,aaabbb,…,anbn,…}或表示為{w|w∈Σ*且w=anbn,n≥1}為字母表

上的一個(gè)語(yǔ)言。

集合{a,aa,aaa,…}或表示為{w|w∈Σ*且w=an,n≥1}為字母表

上的一個(gè)語(yǔ)言。

ε

是一個(gè)語(yǔ)言，

即

也是一個(gè)語(yǔ)言。82二、上下文無(wú)關(guān)文法及其語(yǔ)言的形式定義1.如何來(lái)描述一種語(yǔ)言？如果語(yǔ)言是有窮的（只含有有窮多個(gè)句子），可以將句子逐一列出來(lái)表示；如果語(yǔ)言是無(wú)窮的，找出語(yǔ)言的有窮表示。語(yǔ)言的有窮表示有兩個(gè)途徑：生成方式：語(yǔ)言中的每個(gè)句子可以用嚴(yán)格定義的規(guī)則來(lái)構(gòu)造。識(shí)別方式：用一個(gè)過(guò)程，當(dāng)輸入的一任意串屬于語(yǔ)言時(shí)，該過(guò)程經(jīng)有限次計(jì)算后就會(huì)停止并回答“是”，若不屬于，要麼能停止并回答“不是”，要麼永遠(yuǎn)繼續(xù)下去。83

文法是從生成方式描述語(yǔ)言的，而自動(dòng)機(jī)則是從識(shí)別的角度來(lái)描述語(yǔ)言的。本節(jié)僅介紹有關(guān)文法的概念。前面關(guān)于“我是大學(xué)生”及“賦值表達(dá)式”的例子中，涉及到如下的概念：

?<···>所表示的是一個(gè)類概念，通常稱作語(yǔ)法范疇或語(yǔ)法變量，如果用一個(gè)符號(hào)來(lái)代替,也稱為非終極符。所有規(guī)則中的非終極符就構(gòu)成了一個(gè)非空有窮集，記為VN。上述兩例中的“句子”及“賦值表達(dá)式”顯然是最大的語(yǔ)法范疇，也是我們最感興趣的非終極符，通常稱作開(kāi)始符號(hào)，記為S。

?“大學(xué)生”、“我”、“a”、“A”、“+”等表示的是一個(gè)具體概念，用一個(gè)符號(hào)來(lái)表示，則稱為終極符號(hào)。所有這樣的符號(hào)同樣構(gòu)成了一個(gè)非空有窮集，記為VT。

?<代詞>→我、<數(shù)字>→8等稱作產(chǎn)生式。所有產(chǎn)生式的集合顯然是有窮的，記為P。這樣我們可以將文法抽象為如下的一個(gè)數(shù)學(xué)系統(tǒng)：842.上下文無(wú)關(guān)文法的形式定義一個(gè)上下文無(wú)關(guān)文法G定義為一個(gè)四元式(VN,VT,S,

P)

其中：

VN為非終結(jié)符號(hào)的非空有窮集；

VT為終結(jié)符號(hào)的非空有窮集，VN∩

VT=φ；

P為產(chǎn)生式的集合；產(chǎn)生式也稱重寫規(guī)則或生成式，形如A→α，其中：

A∈VN,α∈(VN∪

VT)*

。

A稱為產(chǎn)生式的左部，α稱作產(chǎn)生式的右部。

S稱作識(shí)別符號(hào)或開(kāi)始符號(hào)，S∈VN

且至少要在一條產(chǎn)生式中作為左部出現(xiàn)。

VN∪

VT中的符號(hào)統(tǒng)稱為文法符號(hào)。85例1文法G=（VN，VT，S，P）

VN={S},VT={0,1} P={S→0S1,S→01} S為開(kāi)始符號(hào)例2文法G=（VN，VT，S，P）

VN={<標(biāo)識(shí)符>，<字母>，<數(shù)字>} VT={a,b,c,…x,y,z,0,1,…,9} P={<標(biāo)識(shí)符>→<字母>, <標(biāo)識(shí)符>→<標(biāo)識(shí)符><字母>, <標(biāo)識(shí)符>→<標(biāo)識(shí)符><數(shù)字>,<字母>→a,…,<字母>→z,<數(shù)字>→0,…,

<數(shù)字>→9} S=<標(biāo)識(shí)符>86

文法的寫法

①.G：S→aAb

A→abA→aAb

A→ε②.G[S]：S→aSbA→abA→aAbA→ε③.G[S]：S→aSbA→ab|aAb|ε

元符號(hào)：→∷=|<>

習(xí)慣表示：大寫英文字母：終結(jié)符小寫英文字母：非終結(jié)符

873.推導(dǎo)與規(guī)約

(1)直接推導(dǎo)“”A→γ是文法G的產(chǎn)生式，若有v,w滿足：v=αAβ,w=αγβ,其中α∈V*,β∈V*

則稱v直接推導(dǎo)出w,記作

v

w；也稱w直接歸約到v，就是說(shuō)歸約是推導(dǎo)的逆過(guò)程。例：G：S→0S1，S→01

0S100S1100S11000S111000S11100001111S0S188(2)推導(dǎo)

若存在vw0w1...wn=w,(n>0)，則記為

v+w，v推導(dǎo)出w，或w歸約到v。若有v+w，或v=w，則記為v*w。例：G：S→0S1，S→01S0S10S100S1100S11000S111000S11100001111S0S100S11000S11100001111S

+00001111S

*S00S11

*00S1189(3)最左（最右）推導(dǎo)最左（最右）推導(dǎo)：在推導(dǎo)的任何一步α

β，其中α、β是句型，都是對(duì)α中的最左（右）非終結(jié)符進(jìn)行替換最右推導(dǎo)被稱為規(guī)范推導(dǎo)。也就是說(shuō)，規(guī)范推導(dǎo)具有最右性。規(guī)范推導(dǎo)的逆過(guò)程稱為規(guī)范規(guī)約。也就是說(shuō)，規(guī)范規(guī)約具有最左性。由規(guī)范推導(dǎo)所得的句型稱為規(guī)范句型。904.句型、句子句型：有文法G，若S

*x，則稱x是文法G的句型。句子：有文法G，若S

*x，且x∈VT*，則稱x是文法G的句子。例1：G：S→0S1，S→01S0S100S11000S11100001111G的句型:S,0S1,00S11,000S111,00001111G的句子:00001111,0191例2：G[E]：E→E+T|T

T→T*F|F

F→(E)|a

EE+TT+TF+Ta+Ta+T*F

a+F*Fa+a*Fa+a*a

句子：用符號(hào)a，+，*，(和)構(gòu)成的算術(shù)表達(dá)式925.語(yǔ)言的定義

由文法G生成的語(yǔ)言記為L(zhǎng)(G),它是文法G的所有句子的集合。

L(G)={x|S

+x,S為開(kāi)始符號(hào),且x∈VT*}

例1G：S→0S1，S→01L(G)={0n1n|n≥1}

例2文法G[S]： （1）S→aSBE

（2）S→aBE

（3）EB→BE

（4）aB→ab

（5）bB→bb

（6）bE→be

（7）eE→ee

L（G）={anbnen|n≥1}為什么呢？93S

aSBE(S→aSBE)

aaBEBE(S→aBE)

aabEBE (aB→ab)

aabBEE (EB→BE)

aabbEE

（bB→bb)

aabbeE

（bE→be)

aabbee

（eE→ee)類似推導(dǎo)可以看出a,b,e在句子中出現(xiàn)的順序及個(gè)數(shù)滿足L(G)當(dāng)然要進(jìn)一步說(shuō)明：G生成的每個(gè)句子都在L(G)中L(G)中的每個(gè)句子確實(shí)能被G生成94

使用產(chǎn)生式(1)n-1次，得到推導(dǎo)序列：

S

*an-1S(BE)n-1，然后使用產(chǎn)生式(2)一次，得到：S

*

an-1S(BE)n-1

an(BE)n。然后從an(BE)n繼續(xù)推導(dǎo)，總是對(duì)EB使用產(chǎn)生式(3)的右部進(jìn)行替換，而最終在得到的串中，所有的B都先于所有的E。例如，若n=3,aaaBEBEBE

aaaBBEEBE

aaaBBEBEE

aaaBBBEEE。即有：S

*

anBnEn

再使用產(chǎn)生式(4)一次，得到S

*

anbBn-1En，然后使用產(chǎn)生式(5)n-1次得到：

S

*

anbnEn，進(jìn)而使用產(chǎn)生式(6)一次，使用產(chǎn)生式(7)n-1次，最后得到：S

*

anbnen。也能證明，對(duì)于n≥1，串a(chǎn)nbnen是唯一形式的終結(jié)符號(hào)串95

三、文法的等價(jià)性1.定義：若L(G1)=L(G2)，則稱文法G1和G2是等價(jià)的。如文法G1[A]：A→0R與G2[S]：S→0S1等價(jià)

A→01S→01R→A1因?yàn)長(zhǎng)（G1）=L（G2）={0n1n∣n≥1}。962.關(guān)于文法等價(jià)變換的幾個(gè)定理(1)對(duì)任一文法G1都可以構(gòu)造文法G2，使得L(G1)=L(G2)，但G2的開(kāi)始符號(hào)不出現(xiàn)在任何產(chǎn)生式的右部。例1：G1:E→E+E∣E*E∣(E)∣iG2:S→EE→E+E∣E*E∣(E)∣i

具體做法：加一條單個(gè)非產(chǎn)生式S→E即可。(2)對(duì)任一文法G1都可以構(gòu)造文法G2，使得L(G1)=L(G2)，但G2的每個(gè)非終結(jié)符都能導(dǎo)出一個(gè)終結(jié)符號(hào)串?？山o出如下證明：97證明：①令β={A∣A→t∈G1&A∈VT+}；②遞歸擴(kuò)充：β=β∪{W∣W→x&x∈(VT∪β)+}

由于G1的非終結(jié)符號(hào)是有窮的，上述過(guò)程一定是收斂的；③從G1的VN中刪除不包含在β中的非終結(jié)符，并從其產(chǎn)生式集中刪除其左部或右部中包含不屬于β中的符號(hào)的產(chǎn)生式，這樣得到的文法即為所要的G2。98例：G1[A]:A→Bed∣dDB→bD→Ea∣AD∣DBE→Da∣Eb①β={B}②β={B}∪{A}={A,B},到此為止；于是D,E及相關(guān)D,E的產(chǎn)生式均可刪除，得到：G2[A]:A→BedB→b

可以證明L(G1)=L(G2)。類似還可以給出如下定理：(3)對(duì)任一文法G1都可以構(gòu)造文法G2，使得L(G1)=L(G2)，但G2的每個(gè)非終結(jié)符都出現(xiàn)在某一句型中。99(4)對(duì)任一文法G1都可以構(gòu)造文法G2，使得L(G1)=L(G2)，但G2中不含單個(gè)非產(chǎn)生式。如：G1[A]:A→B∣dDG2[A]:A→dD∣b∣c

B→A∣C∣bD→d∣Da

C→B∣c

D→d∣Da(5)對(duì)任一文法G1都可以構(gòu)造文法G2，使得L(G1)=L(G2)，但G2中不含空產(chǎn)生式。形如E→ε的產(chǎn)生式稱為空產(chǎn)生式。(6)對(duì)任一文法G1都可以構(gòu)造文法G2，使得L(G1)=L(G2)，但G2中不含有左遞歸。形如E→E+T的產(chǎn)生式稱為左遞歸的。100四、語(yǔ)法樹(shù)和文法二義性

1.語(yǔ)法樹(shù)：語(yǔ)法樹(shù)是了解句子語(yǔ)法結(jié)構(gòu)的一種輔助工具。樹(shù)根即為開(kāi)始符號(hào)所標(biāo)記的結(jié)點(diǎn)。隨著推導(dǎo)的展開(kāi)，某個(gè)非終結(jié)符被它的產(chǎn)生式右部所替換時(shí)，則產(chǎn)生出下一代新結(jié)點(diǎn)。每個(gè)新結(jié)點(diǎn)和其父結(jié)點(diǎn)間都有一條連線。于是，可給出如下的定義：101設(shè)G=(VN,VT,S,P)為一cfg，若一棵樹(shù)滿足下列4個(gè)條件，則此樹(shù)稱作G的語(yǔ)法樹(shù)(推導(dǎo)樹(shù))(派生樹(shù)）：1.每個(gè)結(jié)點(diǎn)都有一個(gè)標(biāo)記，此標(biāo)記是V的一個(gè)符號(hào)2.根的標(biāo)記是S3.若一結(jié)點(diǎn)n至少有一個(gè)它自己除外的子孫，并且有標(biāo)記A，則肯定A∈VN4.如果結(jié)點(diǎn)n有標(biāo)記A,其直接子孫結(jié)點(diǎn)從左到右的次序是n1，n2，…，nk，其標(biāo)記分別為A1，A2，…，Ak，那么A→A1A2，…，Ak一定是P中的一個(gè)產(chǎn)生式語(yǔ)法樹(shù)的結(jié)果：從左到右讀出葉子的標(biāo)記而構(gòu)成的行謂之句型。102給定文法G=(VN,VT,P,S)，對(duì)于G的任何句型都能構(gòu)造與之關(guān)聯(lián)的語(yǔ)法樹(shù)(推導(dǎo)樹(shù))。定理：G為上下文無(wú)關(guān)文法， 對(duì)于α≠ε，有S

*

α，當(dāng)且僅當(dāng) 文法G有以α為結(jié)果的一棵語(yǔ)法樹(shù)(推導(dǎo)樹(shù))這里對(duì)該定理不作證明。103例如：文法G[E]:

E→E+E∣E*E∣(E)∣i

顯然(i+i)*i是該文法產(chǎn)生的一個(gè)句子，它的推導(dǎo)過(guò)程可以用右邊的語(yǔ)法樹(shù)來(lái)描述。

子樹(shù)與簡(jiǎn)單子樹(shù)

只有單層分支的子樹(shù)代次21345EE*E(E)E+Eiii104

在一棵語(yǔ)法樹(shù)生長(zhǎng)過(guò)程中的任何時(shí)刻，所有葉結(jié)點(diǎn)從左到右依次排列起來(lái)就是一個(gè)句型。這就是說(shuō)，一棵語(yǔ)法樹(shù)表示了一個(gè)句型種種可能的（但未必是所有的）不同推導(dǎo)過(guò)程，包括最左（最右）推導(dǎo)。如果我們堅(jiān)持使用最左（最右）推導(dǎo)，那么一棵語(yǔ)法樹(shù)就完全等價(jià)于一個(gè)最左（最右）推導(dǎo)。105文法G[E]:

E→i E→E+E E→E*E E→(E)EE+EE*EiiiEE*EiE+Eii句型i*i+i的兩個(gè)不同的最左推導(dǎo)：推導(dǎo)1：EE+EE*E+Ei*E+Ei*i+Ei*i+i推導(dǎo)2：EE*Ei*Ei*E+Ei*i+Ei*i+i

但是，一個(gè)句型是否只對(duì)應(yīng)唯一的一棵語(yǔ)法樹(shù)呢?一個(gè)句型是否只有唯一的一個(gè)最左(最右)推導(dǎo)呢?不盡然。試看下例：1062.文法二義性

若一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的語(yǔ)法樹(shù)，則稱這個(gè)文法是二義的；或者，若一個(gè)文法存在某個(gè)句子有兩個(gè)不同的最左（右）推導(dǎo)，則稱這個(gè)文法是二義的。顯然，上例中的文法就是一個(gè)二義文法。

1073.二義性問(wèn)題是不可判定的

不能設(shè)計(jì)一個(gè)算法，在有窮的步驟內(nèi)確切地判定一個(gè)文法是否為二義性的。因此，我們所能做的工作只能是為二義性尋找一組充分（而非必要）條件來(lái)改造二義性文法。例如對(duì)前面提到的二義性文法G(E):E→E+E∣E*E∣(E)∣i

可將其改造為如下無(wú)二義文法G′：

G′(E):E→T∣E+TT→F∣T*FF→i∣(E)優(yōu)先順序和結(jié)合律108

注意：文法的二義性和語(yǔ)言的二義性是兩個(gè)不同的概念。因?yàn)榭赡苡袃蓚€(gè)不同的文法G和G′，其中G是二義的，但是卻有L(G)=L(G′)，也就是說(shuō)，這兩個(gè)文法所產(chǎn)生的語(yǔ)言是相同的。上面的例子很好地說(shuō)明了這一點(diǎn)。如果產(chǎn)生上下文無(wú)關(guān)語(yǔ)言的每一個(gè)文法都是二義的，則說(shuō)此語(yǔ)言是先天二義的。對(duì)于一個(gè)程序設(shè)計(jì)語(yǔ)言來(lái)說(shuō)，常常希望它的文法是無(wú)二義的，因?yàn)橄Ｍ麑?duì)它的每個(gè)語(yǔ)句的分析是唯一的。109

語(yǔ)法樹(shù)是了解句子語(yǔ)法結(jié)構(gòu)的一種輔助工具，也是語(yǔ)法分析的輔助工具，因此又稱為語(yǔ)法分析樹(shù)。這樣一來(lái)，就存在著自上而下和自下而上兩種分析方法。

■在自上而下的分析方法中如何選擇使用哪個(gè)產(chǎn)生式進(jìn)行推導(dǎo)？ 假定要被代換的最左非終結(jié)符號(hào)是B，且有n條規(guī)則：B→A1|A2|…|An，那么如何確定用哪個(gè)右部去替代B？

■在自下而上的分析方法中如何識(shí)別可歸約的串？ 在分析程序工作的每一步，都是從當(dāng)前串中選擇一個(gè)子串，將它歸約到某個(gè)非終結(jié)符號(hào)，該子串稱為“可歸約串”。110五、文法的分類----形式語(yǔ)言鳥(niǎo)瞰(1)通過(guò)對(duì)產(chǎn)生式施加不同的限制，Chomsky將文法分為四種類型：即0型、1型、2型、3型。

①0型文法：若文法G=(VN,VT,S,P)

的每個(gè)產(chǎn)生式α→β滿足：

α∈(VN∪VT)+且至少含有一個(gè)非終結(jié)符，

β∈(VN∪VT)*，則該文法稱為0型文法。

②若0型文法G的任何產(chǎn)生式α→β，都有|β|≥|α|，但S→ε除外，這時(shí)S不得出現(xiàn)在任何產(chǎn)生式的右部；則該文法稱為1型文法。

③若文法G的任何產(chǎn)生式α→β，都有α∈VN，β∈(VN∪VT)*，則該文法稱為2型文法。

④若文法G的任何產(chǎn)生式的形式都為A→αB或A→α，其中A∈VN

，B∈VN

，α∈VT*，則該文法稱為3型文法。111例11型文法文法G[S]： S→CD Ab→bA C→aCA Ba→aB C→bCB Bb→bB AD→aD C→ε BD→bD D→ε Aa→bD例22型文法

文法G[S]： S→AB A→BS|0 B→SA|1112例33型文法G[S]：

S→0A|1B|0 A→0A|1B|0S B→1B|1|0G[I]： I→lT I→l T→lT

T→dT

T→l

T→d

試問(wèn)：它們產(chǎn)生的語(yǔ)言是什么？113

(2)四種文法之間的逐級(jí)“包含”關(guān)系隨著對(duì)產(chǎn)生式限制條件的增多，四種文法的能力逐級(jí)減弱。2型文法1型文法0型文法3型文法114(3)四種文法及其分別對(duì)應(yīng)的語(yǔ)言和識(shí)別系統(tǒng)

0型文法（又稱為短語(yǔ)文法）的能力相當(dāng)于圖靈機(jī)，可以表征任何遞歸可枚舉集。0型文法產(chǎn)生的語(yǔ)言稱為0型語(yǔ)言。而且任何0型語(yǔ)言都是遞歸可枚舉的，或者說(shuō)都可以被一個(gè)圖靈機(jī)所接收；反之，遞歸可枚舉集也必定是一個(gè)0型語(yǔ)言。

1型文法又稱為上下文有關(guān)文法。這種文法意味著：對(duì)非終結(jié)符進(jìn)行替換時(shí)必須考慮上下文，例如產(chǎn)生式的形式為α1Aα2→α1βα2，則只有當(dāng)A出現(xiàn)在α1和α2這樣的上下文環(huán)境時(shí)，才允許用β替換A。

1型文法產(chǎn)生的語(yǔ)言稱為1型語(yǔ)言或上下文有關(guān)語(yǔ)言（CSL）。其識(shí)別系統(tǒng)是線性界限自動(dòng)機(jī)(LBA)。115

帶a0a1a2a3a4a5a6a7a8…an-1an

有限控制器磁頭任何能用圖靈機(jī)描述的計(jì)算都能機(jī)械實(shí)現(xiàn)，任何能在現(xiàn)代計(jì)算機(jī)上實(shí)現(xiàn)的計(jì)算都能用圖靈機(jī)描述116

2型文法：產(chǎn)生式的形式為A→β，β取代A時(shí)與A的上下文無(wú)關(guān)，因此又稱為上下文無(wú)關(guān)文法（CFG

）

。它產(chǎn)生的語(yǔ)言稱為2型語(yǔ)言或上下文無(wú)關(guān)語(yǔ)言（CFL），其識(shí)別系統(tǒng)是下推自動(dòng)機(jī)(PDA)。

CFG有足夠的能力描述現(xiàn)今大多數(shù)程序設(shè)計(jì)語(yǔ)言的語(yǔ)法結(jié)構(gòu)，也就是說(shuō)現(xiàn)今大多數(shù)程序設(shè)計(jì)語(yǔ)言都是CFL。

3型文法：產(chǎn)生式形式為A→αB或A→α的3型文法稱為右線性文法，產(chǎn)生式形式為A→Bα或A→α的則稱為左線性文法。由于3型文法等價(jià)于正規(guī)式（將在第三章介紹），所以也稱為正規(guī)文法。相對(duì)應(yīng)地，它所產(chǎn)生的語(yǔ)言稱為3型語(yǔ)言或正規(guī)（則）語(yǔ)言，可以為有窮自動(dòng)機(jī)（FA）所接收。117小結(jié)1.本節(jié)出現(xiàn)的概念較多,應(yīng)重點(diǎn)理解文法,推導(dǎo),句型,句子及語(yǔ)言的定義等概念.語(yǔ)法分析有關(guān)內(nèi)容在后面章節(jié)會(huì)詳細(xì)討論.2.文法作為程序語(yǔ)言的語(yǔ)法的描述工具,它用規(guī)則只能陳述的是:語(yǔ)言的所有句子以什麼樣的符號(hào)串能出現(xiàn).請(qǐng)記住文法和語(yǔ)言的形式定義中的“形式”的含義—只涉及語(yǔ)言的語(yǔ)法不涉及語(yǔ)言的語(yǔ)義.3.本節(jié)內(nèi)容是形式語(yǔ)言理論的一部分.形式語(yǔ)言理論是對(duì)符號(hào)串集合的表示法、結(jié)構(gòu)及其特性的研究。是程序設(shè)計(jì)語(yǔ)言語(yǔ)法分析研究的基礎(chǔ)。118§1.詞法分析器的構(gòu)造

編譯程序首先在單詞級(jí)別上來(lái)分析和翻譯源程序。詞法分析的任務(wù)是：從左至右逐個(gè)字符地對(duì)源程序進(jìn)行掃描，產(chǎn)生一個(gè)個(gè)單詞符號(hào)，即把作為字符串的源程序改造成為單詞符號(hào)串的中間程序。因此，詞法分析是編譯的基礎(chǔ)。執(zhí)行詞法分析的程序稱為詞法分析器(通常又稱為掃描器,scanner）。119一、一般考慮：

1.詞法分析程序的主要任務(wù)：讀入字符串形式的源程序—輸入剔除非單詞符號(hào)—空格符、換行符，跳過(guò)注釋拼單詞符號(hào)—**、:=、FOR、BEGIN等捻接語(yǔ)句行并產(chǎn)生語(yǔ)句結(jié)束標(biāo)志源程序的列表輸出宏展開(kāi)，……120

2.詞法分析器的輸入和輸出形式輸入—字符串形式的源程序輸出—單詞符號(hào)串。程序語(yǔ)言的單詞符號(hào)一般分為五種：

關(guān)鍵字、運(yùn)算符、界符、標(biāo)識(shí)符、常數(shù)詞法分析器輸出的單詞符號(hào)常常表示為二元式：

（單詞種別，單詞符號(hào)的屬性值）121

★單詞種別通常用整數(shù)編碼

單詞種別是對(duì)單詞符號(hào)的一種分類。一個(gè)語(yǔ)言的單詞符號(hào)如何分種，分成幾種，怎樣編碼是一個(gè)技術(shù)性問(wèn)題。它取決于處理上的方便。標(biāo)識(shí)符一般統(tǒng)歸為一種。常數(shù)則宜按類型（整、實(shí)、布爾等）分種。關(guān)鍵字可視其全體為一種，也可以一字一種。采用一字一種的分法實(shí)際處理起來(lái)較為方便。運(yùn)算符可采用一符一種的分法，但也可以把具有一定共性的運(yùn)算符視為一種。至于界符一般用一符一種的分法。

122★單詞符號(hào)屬性信息記錄單詞符號(hào)的特征或特性

如果一個(gè)種別只含有一個(gè)單詞符號(hào)，那么對(duì)于這個(gè)單詞符號(hào)，種別編碼就完全代表它自身了，因此屬性值就沒(méi)有意義了。若同一個(gè)種別含有多個(gè)單詞符號(hào)，那麼，對(duì)于它的每個(gè)單詞符號(hào)，除了給出種別編碼之外，還應(yīng)給出各有關(guān)單詞符號(hào)的屬性信息。

屬性值是反映特性或特征的值。例如，對(duì)于某個(gè)標(biāo)識(shí)符，常將存放它有關(guān)信息的符號(hào)表項(xiàng)的指針作為其屬性值；對(duì)于某個(gè)常數(shù)，則將存放該常數(shù)二進(jìn)制表項(xiàng)的指針作為其屬性值。123

作為例子考慮下述C++語(yǔ)句：

while(i>=j)i--;

若while種別為01,(種別為11,標(biāo)識(shí)符種別為20,>=種別為12,)種別為13,－－種別為14,;種別為30,則經(jīng)詞法分析器處理后，它將被轉(zhuǎn)換為如下的單詞符號(hào)序列：

(01,—)(11,—)(20,指向i的符號(hào)表項(xiàng)的指針)(12,—)(20,指向j的符號(hào)表項(xiàng)的指針)(13,—)(20,指向i的符號(hào)表項(xiàng)的指針)(14,—)(30,—)1243.詞法分析器與語(yǔ)法分析器的銜接

通常把詞法分析器安排成一個(gè)獨(dú)立子程序，而不是單獨(dú)的一遍。這樣一來(lái)，就無(wú)須在外存中保留整個(gè)源程序的內(nèi)碼形式，而是每當(dāng)語(yǔ)法分析器需要單詞符號(hào)時(shí)就調(diào)用這個(gè)子程序。每一次調(diào)用，詞法分析器就從源程序字符串中識(shí)別出一個(gè)單詞符號(hào)，把它交給語(yǔ)法分析器。這樣做的好處是：壓縮編譯時(shí)掃描字符的時(shí)間：編譯時(shí)大量時(shí)間花費(fèi)在字符的掃描上；詞法規(guī)則描述簡(jiǎn)單，便于建立掃描器的自動(dòng)方法，便于獨(dú)立研究；使得語(yǔ)法分析獲得更多信息；便于處理同一語(yǔ)言的幾種不同表示形式；

125由以上考慮，可以初步設(shè)計(jì)為：源程序掃描器語(yǔ)法分析器取符號(hào)送符號(hào)126二、進(jìn)一步考慮：

1.輸入、預(yù)處理

詞法分析器工作的第一步是輸入源程序文本。輸入串一般放在一個(gè)緩沖區(qū)中，這個(gè)緩沖區(qū)稱源程序輸入緩沖區(qū)。詞法分析器的工作可以直接在這個(gè)緩沖區(qū)中進(jìn)行。但在許多情況下，把輸入串預(yù)處理一下，對(duì)單詞符號(hào)的識(shí)別工作將是比較方便的。預(yù)處理工作包括對(duì)空白符、跳格符、回車符和換行符等編輯性字符的處理，及刪除注解等。于是可以設(shè)想構(gòu)造一個(gè)預(yù)處理子程序，它完成上面的工作。每當(dāng)詞法分析器調(diào)用它時(shí)就處理出一串確定長(zhǎng)度的輸入字符，并將其裝入詞法分析器所指定的緩沖區(qū)中（稱為掃描緩沖區(qū)）。這樣分析器就可以在此緩沖區(qū)中直接而方便地進(jìn)行單詞符號(hào)的識(shí)別工作。1272.對(duì)半互補(bǔ)緩沖區(qū)

分析器對(duì)掃描緩沖區(qū)進(jìn)行掃描時(shí)一般使用兩個(gè)指示器，一個(gè)指向當(dāng)前正在識(shí)別單詞的開(kāi)始位置（指向新單詞的首字符），另一個(gè)用于向前搜索以尋找單詞的終點(diǎn)。但是不論掃描緩沖區(qū)設(shè)得多大都不能保證單詞符號(hào)不會(huì)被緩沖區(qū)的邊界所打斷。因此，掃描緩沖區(qū)最好使用一分為二的區(qū)域，并使兩區(qū)首尾相接，形成一個(gè)對(duì)半互補(bǔ)緩沖區(qū)。例如：每半個(gè)區(qū)可容64個(gè)字符，而這兩個(gè)半?yún)^(qū)又是互補(bǔ)的。如果搜索指示器從單詞起點(diǎn)出發(fā)搜索到半?yún)^(qū)的邊緣但尚未達(dá)到單詞的終點(diǎn)，那么就調(diào)用預(yù)處理子程序，令其把后續(xù)的64個(gè)字符裝入另半?yún)^(qū)。可以認(rèn)定在另半?yún)^(qū)一定可以達(dá)到單詞的終點(diǎn)。這意味著標(biāo)示符和常數(shù)的長(zhǎng)度實(shí)際上必須加以限制，否則即使緩沖區(qū)再大也無(wú)濟(jì)于事。128于是對(duì)半互補(bǔ)緩沖區(qū)可圖示如下：

。。。。。。While。。。。。。起點(diǎn)指針?biāo)阉髦羔?/p>

綜上所述，預(yù)處理子程序、掃描器和語(yǔ)法分析器相互之間的關(guān)系及工作情況可圖示如下：

129單詞符號(hào)掃描器預(yù)處理子程序輸入緩沖區(qū)源程序掃描緩沖區(qū)列表語(yǔ)法分析器取單詞1303.單詞符號(hào)識(shí)別－超前搜索技術(shù)問(wèn)題發(fā)生在對(duì)基本字不加任何保護(hù)的語(yǔ)言中，基本字及用戶自定義的標(biāo)識(shí)符或標(biāo)號(hào)之間無(wú)特殊分界符，這使得關(guān)鍵字的識(shí)別甚為麻煩。

請(qǐng)看下面的例子：

1DO99K=1,102IF(5.EQ.M)I=103DO99K=1.104IF(5)=55

這四個(gè)語(yǔ)句都是正確的FORTRAN語(yǔ)句。語(yǔ)句1和2分別是DO和IF語(yǔ)句，它們都是以某基本字開(kāi)頭的。語(yǔ)句3和4是賦值語(yǔ)句，它們都是以用戶自定義的標(biāo)識(shí)符開(kāi)頭的。131

為了從1、2中識(shí)別出關(guān)鍵字DO和IF，我們必須要能夠區(qū)別1、3和區(qū)別2、4。語(yǔ)句1、3的區(qū)別在于等號(hào)之后的第一個(gè)界符：一個(gè)為逗號(hào)，另一個(gè)為小數(shù)點(diǎn)，語(yǔ)句2、4的主要區(qū)別在于右括號(hào)后的第一個(gè)字符：一個(gè)為字母，另一個(gè)為等號(hào)。這就是說(shuō)，為了識(shí)別1、2句中的關(guān)鍵字，我們必須超前掃描許多個(gè)字符，超前到能夠肯定詞性的地方為止。對(duì)于1、3來(lái)說(shuō)，盡管都以‘D’和‘O’兩個(gè)字母開(kāi)頭，但不能一見(jiàn)‘DO’就認(rèn)定是DO語(yǔ)句。而必須超前搜索，跳過(guò)所有的字母和數(shù)字，看看是否有等號(hào)。如果有，再向前搜索。若下一個(gè)界符是逗號(hào)，則可以肯定DO應(yīng)為關(guān)鍵字。否則，DO不構(gòu)成關(guān)鍵字，它只是用戶標(biāo)識(shí)符的頭兩個(gè)字母。132

所以為了區(qū)別1和3，必須超前掃描若干字符直到等號(hào)后的第一個(gè)界符處。對(duì)于2和4來(lái)說(shuō)，同樣需超前掃描到與IF后的左括號(hào)相對(duì)應(yīng)的那個(gè)右括號(hào)之后的第一個(gè)字符為止。若此字符是字母，則得邏輯IF。若此字符為數(shù)字，則得算術(shù)IF。否則，應(yīng)認(rèn)為是用戶自定義標(biāo)識(shí)符IF。這種向前掃描若干字符直到找到能區(qū)分單詞的字符為止的技術(shù)就叫超前搜索。

133

標(biāo)識(shí)符的識(shí)別：標(biāo)識(shí)符是字母開(kāi)頭的一個(gè)字母數(shù)字串，一般有運(yùn)算符和界符分開(kāi)，與基本字的區(qū)別前已談及，所以容易識(shí)別。常數(shù)的識(shí)別：算術(shù)常數(shù)大多相似，只是轉(zhuǎn)換二進(jìn)制的問(wèn)題，但像3.E5、3.EQ.5顯然也要用到超前搜索技術(shù)。另有3HABC一類的常數(shù)需要特殊處理。算符