1編譯原理

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

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

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

《程序設計語言編譯原理》（第3版）

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

機械工業出版社《編譯原理及實踐》馮博琴馮嵐等譯KennethC.Louden著）

機械工業出版社14§2.編譯程序概述一、翻譯程序（Translator）

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

把匯編語言程序轉變為機器語言程序的翻譯程序解釋程序(Interpreter)

把源程序作為輸入接收，邊解釋邊執行的翻譯程序源程序數據解釋程序結果17編譯程序

將高級語言程序轉變為低級語言程序的翻譯程序源程序編譯程序目標程序18編譯程序又可根據用途和側重點的不同，進一步分類為：

①診斷編譯程序(DiagnosticCompiler)

專門用于幫助程序開發和調試的編譯程序

②優化編譯程序(OptimizingCompiler)

著重于提高目標代碼效率的編譯程序

③交叉編譯程序(CrossCompiler)

能夠產生不同于其宿主機機器代碼的編譯程序

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

無須重寫與機器無關部分就能改變目標機的編譯程序19二、與編譯程序相關的程序本講義只介紹編譯程序（器）構造的基本原理、方法與技術，但在一個完整的語言開發（或稱程序設計）環境中，除了編譯器這一主要工具外，還需要其他一些工具，如編輯器、連接器、裝入程序等?，F代計算機系統常將這些相互獨立的程序設計工具集成起來，構成一個集成化的程序開發環境，以提高程序設計效率和程序的質量。如TurboC、VisualC++等語言環境都是集成化的程序設計環境。而Ada語言的集成環境是這方面的典型代表。20如Ada語言的集成環境是一個分層的程序開發環境編譯程序MAPSE編輯程序連接程序宿主機OSAPSE工具界面用戶界面KAPSE調試程序配置管理程序命令解釋程序其他工具21

這兒要強調的是：盡管本課程只介紹編譯的基本理論、方法和技術，但這些基本理論、方法與技術對其他工具的構造同樣起作用！22編輯器(Editor)

完成源程序輸入、編輯并產生標準文件（如ASCII文件）的程序。近來已與編譯器和其他程序捆綁進一個交互開發環境——IDE中盡管這樣的編輯器仍生成標準文件，但會轉向正被討論的程序設計語言的格式或結構（稱為基于結構的），且已包含了編譯器的某些操作；因此在程序編寫時而不是編譯時就可得知錯誤，甚至也可調用編譯器23預處理程序(Preprocessor)

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

完成程序的裝入和連接編輯兩項功能。裝入過程包括讀入可重定位機器代碼、修改可重定位地址、并將修改后的指令和數據放到內存的適當位置。

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

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

1.編譯過程：

輸入輸出（高級語言源程序）（低級語言目標程序）

編譯程序工作過程如下：識別出一個個的單詞分析句子的語法結構分析句子的語義并進行初步翻譯對初步翻譯進行優化整理出目標程序對以上過程進一步整理可得如下編譯程序結構總框：編譯程序292.編譯程序總框：詞法分析器語法分析器語義分析與中間代碼產生器優化器目標代碼生成器單詞符號語法單位中間代碼中間代碼出錯處理表格管理源程序目標代碼303.五個階段簡介第一階段：詞法分析——依據語言構詞規則，識別出一個個單詞（符號）

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

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

掃描器輸出為等長度的單詞符號（二元式）流。

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

如：Position=initial+rate*60是一個“賦值表達式”（C語言中）Position=表達式表達式表達式+表達式標示符表達式*表達式initial標示符常數rate60標示符33第三階段：語義分析與中間代碼產生——針對各類不同的語法范疇，按語言的語義規則進行語義分析和初步翻譯工作，產生某種中間語言形式的中間代碼（即一種結構簡單，含義明確的記號系統）

該階段工作通常包括兩個方面的工作：

對每種語法范疇進行靜態語義檢查，包括：變量是否定義過類型是否正確是否用了0作除數等34將語法范疇翻譯成某種形式的中間代碼，如四元式：OpARG1ARG2Result＊rate60T1＋initialT1T2:=T2Position35第四階段：優化——對前階段產生的中間代碼進行加工變換，以期在最后階段能產生出高效（節省時、空）的目標代碼，這一任務是由優化器來完成的根據優化的范圍不同，可分為：

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

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

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

常數表(CT)

3.141592648…X啞元實型A數組整型

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

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

標號表(LBT)

基本字表

(KWT)496.出錯處理：這是編譯程序的又一重要組成部分，因為編譯的各個階段都有可能發現源程序中的錯誤。一旦發現這樣或那樣的錯誤，就應把錯誤的性質及位置報告給用戶，并且使編譯能繼續下去。50四、編譯程序的構造過程1.需求分析，確定語言文本(1)確定語言的種類：

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

通過用戶提供的應用范圍，決定采用何種語言。例如：偏重于科學計算的則選用Fortran；偏重于符號處理的則選用Lisp或Snobol；偏重于事務處理的則選用Cobol或數據庫管理語言；

……52(2)深刻理解語言的結構、語法及語義這就是說不僅僅是用程序設計語言編幾個程序的問題，而是要在語法和語義方面下一些功夫。具體說來有以下幾個方面：①程序語言的定義：任何程序語言都是某個確定的字符集上的符號按照一定規則組成的有窮序列。這里所謂的規則是從兩個方面來談的：

·語法規則：用于形成和產生一個正確的程序的一組規則。

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

·初等數據類型：牽扯到存儲空間的問題；

·結構數據類型：牽扯到下標、維數、存放方式、分配時間----動態與靜態等；

·表達式：牽扯到運算分量、運算符、形成規則、運算順序等；

·語句：順序、控制、循環等；

·過程與參數傳遞：傳地址、傳值、傳名、得結果等；

·存儲管理：靜態存儲分配、動態存儲分配；572.由程序設計環境確定編譯程序構造的方式和方法最早是直接使用機器語言或匯編語言現在一般使用高級語言Pascal或C語言

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

任何一個編譯程序至少要涉及三種語言：源語言（S）、目標語言（T）和編譯程序實現語言（I），可用如下T型圖來表示三者之間的關系：STI59Ada語言A

代碼Ada語言A

代碼CCA代碼A代碼A代碼用C語言編寫Ada編譯程序

如若A機上已經有了一個用A機器語言（稱A代碼）實現的C語言編譯程序，則可用C語言作為工具編寫Ada語言的編譯程序。這樣Ada語言的編譯程序經過C語言編譯程序編譯后就可得到A代碼的Ada語言編譯程序。可圖示如下：60現在常用構造編譯程序的方式除高級語言實現外，經常還用：自展（自編譯）：類似于滾雪球。先確定一個非常簡單的核心L0，用低級語言寫出其編譯程序C0。再把L0擴充為L1

，

，

并用L0來編寫L1的編譯程序。如此逐漸擴展下去，可得到一個系統編程語言族：

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

代碼CB

代碼CCB代碼B代碼A代碼62移植：如果一個程序能比較容易地從一臺機器上搬到另一臺機器上運行，則稱其為可移植的，移植一個程序的工作量要遠小于開發它的工作量才有意義。

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

工具就是對程序設計語言給出精確無二義的語法描述。（嚴謹、簡潔、易讀）形式化工具就是將形式語言抽象地定義為一個數學系統?！靶问健笔侵高@樣的事實：語言的所有規則是以什麼符號串能出現的方式來陳述。

§3.高級語言的語法描述66本節主要內容

預備知識

上下文無關文法及其語言的形式定義

文法的等價性

語法樹及文法二義性

文法的類型

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

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

69

〈句子〉

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

〈主語〉〈謂語〉

〈代詞〉〈謂語〉依此類推，句子“我是大學生”的全部導出過程是：

〈句子〉

〈主語〉〈謂語〉

〈代詞〉〈謂語〉

我〈謂語〉

我〈動詞〉〈直接賓語〉

我是〈直接賓語〉

我是〈名詞〉

我是大學生70“我是大學生”的構成符合上述規則，而“我大學生是”不符合上述規則，我們說它不是句子。這些規則成為我們判別句子結構合法與否的依據。換句話說，這些規則看成是一種元語言，用它描述漢語，僅僅涉及漢語句子的結構描述。這里“

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

<賦值表達式>→<左部>=<右部><左部>→<標識符><右部>→<表達式><表達式>→<表達式><算符><表達式><表達式>→<標識符>|<常數><標識符>→<字母>(<字母>|<數字>)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<數字>→0|1|2|3|4|5|6|7|8|9<算符>→+|-|*|/722.語言概述語言是由句子組成的集合。漢語--所有符合漢語語法的句子的全體。英語--所有符合英語語法的句子的全體。程序設計語言--所有該語言的程序的全體。

每個句子構成的規則研究語言每個句子的含義每個句子和使用者的關系73研究程序設計語言每個程序構成的規則每個程序的含義每個程序和使用者的關系語言研究的三個方面:

語法(Syntax)--表示構成語言句子的各個記號之間的組合規則語義(Semantics)--表示各個記號的特定含義。（各個記號和記號所表示的對象之間的關系）語用(Pragmatics)--表示在各個記號所出現的行為中，它們的來源、使用和影響。74

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

如果不考慮語義和語用，即只從語法這一側面來看語言，這種意義下的語言稱作形式語言。形式語言抽象地定義為一個數學系統。該數學系統稱為文法?！靶问健笔侵高@樣的事實：語言的所有規則描述什麼符號串以什么方式出現。形式語言理論是對符號串集合的表示法、結構及其特性的研究，是程序設計語言語法分析研究的基礎。763.有關定義和記號—回顧符號：可以相互區別的記號（元素）。字母表

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

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

①空字ε(沒有符號的符號串)是

上的符號串；

②若x是

上的符號串,a是

的元素,則xa是

上的符號串；

③y是

上的符號串,當且僅當它可以由①和②

導出。

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

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

如:ana是符號串banana的一個子串.符號串s的真前綴：x≠s且x≠ε的任何前綴x。s的真后綴，真子串可以類似地定義。78符號串的運算：

符號串的長度：符號串中符號的個數.符號串s的長度記為|s|。ε的長度為0連接：符號串x、y的連接,是把y的符號寫在x的符號之后得到的符號串xy

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

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

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

上的符號串，則稱A為字母表

上的符號串集合。符號串集合A和B的乘積：

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

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

上的除ε外的所有符號串組成的集合，記為

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

81語言：由句子構成的集合。換言之,字母表

上的一個語言是

上的一些符號串的集合

(字母表

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

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

上的一個語言。

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

上的一個語言。

ε

是一個語言，

即

也是一個語言。82二、上下文無關文法及其語言的形式定義1.如何來描述一種語言？如果語言是有窮的（只含有有窮多個句子），可以將句子逐一列出來表示；如果語言是無窮的，找出語言的有窮表示。語言的有窮表示有兩個途徑：生成方式：語言中的每個句子可以用嚴格定義的規則來構造。識別方式：用一個過程，當輸入的一任意串屬于語言時，該過程經有限次計算后就會停止并回答“是”，若不屬于，要麼能停止并回答“不是”，要麼永遠繼續下去。83

文法是從生成方式描述語言的，而自動機則是從識別的角度來描述語言的。本節僅介紹有關文法的概念。前面關于“我是大學生”及“賦值表達式”的例子中，涉及到如下的概念：

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

?“大學生”、“我”、“a”、“A”、“+”等表示的是一個具體概念，用一個符號來表示，則稱為終極符號。所有這樣的符號同樣構成了一個非空有窮集，記為VT。

?<代詞>→我、<數字>→8等稱作產生式。所有產生式的集合顯然是有窮的，記為P。這樣我們可以將文法抽象為如下的一個數學系統：842.上下文無關文法的形式定義一個上下文無關文法G定義為一個四元式(VN,VT,S,

P)

其中：

VN為非終結符號的非空有窮集；

VT為終結符號的非空有窮集，VN∩

VT=φ；

P為產生式的集合；產生式也稱重寫規則或生成式，形如A→α，其中：

A∈VN,α∈(VN∪

VT)*

。

A稱為產生式的左部，α稱作產生式的右部。

S稱作識別符號或開始符號，S∈VN

且至少要在一條產生式中作為左部出現。

VN∪

VT中的符號統稱為文法符號。85例1文法G=（VN，VT，S，P）

VN={S},VT={0,1} P={S→0S1,S→01} S為開始符號例2文法G=（VN，VT，S，P）

VN={<標識符>，<字母>，<數字>} VT={a,b,c,…x,y,z,0,1,…,9} P={<標識符>→<字母>, <標識符>→<標識符><字母>, <標識符>→<標識符><數字>,<字母>→a,…,<字母>→z,<數字>→0,…,

<數字>→9} S=<標識符>86

文法的寫法

①.G：S→aAb

A→abA→aAb

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

元符號：→∷=|<>

習慣表示：大寫英文字母：終結符小寫英文字母：非終結符

873.推導與規約

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

則稱v直接推導出w,記作

v

w；也稱w直接歸約到v，就是說歸約是推導的逆過程。例：G：S→0S1，S→01

0S100S1100S11000S111000S11100001111S0S188(2)推導

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

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

+00001111S

*S00S11

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

β，其中α、β是句型，都是對α中的最左（右）非終結符進行替換最右推導被稱為規范推導。也就是說，規范推導具有最右性。規范推導的逆過程稱為規范規約。也就是說，規范規約具有最左性。由規范推導所得的句型稱為規范句型。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

句子：用符號a，+，*，(和)構成的算術表達式925.語言的定義

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

L(G)={x|S

+x,S為開始符號,且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)類似推導可以看出a,b,e在句子中出現的順序及個數滿足L(G)當然要進一步說明：G生成的每個句子都在L(G)中L(G)中的每個句子確實能被G生成94

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

S

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

*

an-1S(BE)n-1

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

aaaBBEEBE

aaaBBEBEE

aaaBBBEEE。即有：S

*

anBnEn

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

*

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

S

*

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

*

anbnen。也能證明，對于n≥1，串anbnen是唯一形式的終結符號串95

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

A→01S→01R→A1因為L（G1）=L（G2）={0n1n∣n≥1}。962.關于文法等價變換的幾個定理(1)對任一文法G1都可以構造文法G2，使得L(G1)=L(G2)，但G2的開始符號不出現在任何產生式的右部。例1：G1:E→E+E∣E*E∣(E)∣iG2:S→EE→E+E∣E*E∣(E)∣i

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

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

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

B→A∣C∣bD→d∣Da

C→B∣c

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

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

*

α，當且僅當 文法G有以α為結果的一棵語法樹(推導樹)這里對該定理不作證明。103例如：文法G[E]:

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

顯然(i+i)*i是該文法產生的一個句子，它的推導過程可以用右邊的語法樹來描述。

子樹與簡單子樹

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

在一棵語法樹生長過程中的任何時刻，所有葉結點從左到右依次排列起來就是一個句型。這就是說，一棵語法樹表示了一個句型種種可能的（但未必是所有的）不同推導過程，包括最左（最右）推導。如果我們堅持使用最左（最右）推導，那么一棵語法樹就完全等價于一個最左（最右）推導。105文法G[E]:

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

但是，一個句型是否只對應唯一的一棵語法樹呢?一個句型是否只有唯一的一個最左(最右)推導呢?不盡然。試看下例：1062.文法二義性

若一個文法存在某個句子對應兩棵不同的語法樹，則稱這個文法是二義的；或者，若一個文法存在某個句子有兩個不同的最左（右）推導，則稱這個文法是二義的。顯然，上例中的文法就是一個二義文法。

1073.二義性問題是不可判定的

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

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

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

注意：文法的二義性和語言的二義性是兩個不同的概念。因為可能有兩個不同的文法G和G′，其中G是二義的，但是卻有L(G)=L(G′)，也就是說，這兩個文法所產生的語言是相同的。上面的例子很好地說明了這一點。如果產生上下文無關語言的每一個文法都是二義的，則說此語言是先天二義的。對于一個程序設計語言來說，常常希望它的文法是無二義的，因為希望對它的每個語句的分析是唯一的。109

語法樹是了解句子語法結構的一種輔助工具，也是語法分析的輔助工具，因此又稱為語法分析樹。這樣一來，就存在著自上而下和自下而上兩種分析方法。

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

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

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

的每個產生式α→β滿足：

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

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

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

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

④若文法G的任何產生式的形式都為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

試問：它們產生的語言是什么？113

(2)四種文法之間的逐級“包含”關系隨著對產生式限制條件的增多，四種文法的能力逐級減弱。2型文法1型文法0型文法3型文法114(3)四種文法及其分別對應的語言和識別系統

0型文法（又稱為短語文法）的能力相當于圖靈機，可以表征任何遞歸可枚舉集。0型文法產生的語言稱為0型語言。而且任何0型語言都是遞歸可枚舉的，或者說都可以被一個圖靈機所接收；反之，遞歸可枚舉集也必定是一個0型語言。

1型文法又稱為上下文有關文法。這種文法意味著：對非終結符進行替換時必須考慮上下文，例如產生式的形式為α1Aα2→α1βα2，則只有當A出現在α1和α2這樣的上下文環境時，才允許用β替換A。

1型文法產生的語言稱為1型語言或上下文有關語言（CSL）。其識別系統是線性界限自動機(LBA)。115

帶a0a1a2a3a4a5a6a7a8…an-1an

有限控制器磁頭任何能用圖靈機描述的計算都能機械實現，任何能在現代計算機上實現的計算都能用圖靈機描述116

2型文法：產生式的形式為A→β，β取代A時與A的上下文無關，因此又稱為上下文無關文法（CFG

）

。它產生的語言稱為2型語言或上下文無關語言（CFL），其識別系統是下推自動機(PDA)。

CFG有足夠的能力描述現今大多數程序設計語言的語法結構，也就是說現今大多數程序設計語言都是CFL。

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

編譯程序首先在單詞級別上來分析和翻譯源程序。詞法分析的任務是：從左至右逐個字符地對源程序進行掃描，產生一個個單詞符號，即把作為字符串的源程序改造成為單詞符號串的中間程序。因此，詞法分析是編譯的基礎。執行詞法分析的程序稱為詞法分析器(通常又稱為掃描器,scanner）。119一、一般考慮：

1.詞法分析程序的主要任務：讀入字符串形式的源程序—輸入剔除非單詞符號—空格符、換行符，跳過注釋拼單詞符號—**、:=、FOR、BEGIN等捻接語句行并產生語句結束標志源程序的列表輸出宏展開，……120

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

關鍵字、運算符、界符、標識符、常數詞法分析器輸出的單詞符號常常表示為二元式：

（單詞種別，單詞符號的屬性值）121

★單詞種別通常用整數編碼

單詞種別是對單詞符號的一種分類。一個語言的單詞符號如何分種，分成幾種，怎樣編碼是一個技術性問題。它取決于處理上的方便。標識符一般統歸為一種。常數則宜按類型（整、實、布爾等）分種。關鍵字可視其全體為一種，也可以一字一種。采用一字一種的分法實際處理起來較為方便。運算符可采用一符一種的分法，但也可以把具有一定共性的運算符視為一種。至于界符一般用一符一種的分法。

122★單詞符號屬性信息記錄單詞符號的特征或特性

如果一個種別只含有一個單詞符號，那么對于這個單詞符號，種別編碼就完全代表它自身了，因此屬性值就沒有意義了。若同一個種別含有多個單詞符號，那麼，對于它的每個單詞符號，除了給出種別編碼之外，還應給出各有關單詞符號的屬性信息。

屬性值是反映特性或特征的值。例如，對于某個標識符，常將存放它有關信息的符號表項的指針作為其屬性值；對于某個常數，則將存放該常數二進制表項的指針作為其屬性值。123

作為例子考慮下述C++語句：

while(i>=j)i--;

若while種別為01,(種別為11,標識符種別為20,>=種別為12,)種別為13,－－種別為14,;種別為30,則經詞法分析器處理后，它將被轉換為如下的單詞符號序列：

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

通常把詞法分析器安排成一個獨立子程序，而不是單獨的一遍。這樣一來，就無須在外存中保留整個源程序的內碼形式，而是每當語法分析器需要單詞符號時就調用這個子程序。每一次調用，詞法分析器就從源程序字符串中識別出一個單詞符號，把它交給語法分析器。這樣做的好處是：壓縮編譯時掃描字符的時間：編譯時大量時間花費在字符的掃描上；詞法規則描述簡單，便于建立掃描器的自動方法，便于獨立研究；使得語法分析獲得更多信息；便于處理同一語言的幾種不同表示形式；

125由以上考慮，可以初步設計為：源程序掃描器語法分析器取符號送符號126二、進一步考慮：

1.輸入、預處理

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

分析器對掃描緩沖區進行掃描時一般使用兩個指示器，一個指向當前正在識別單詞的開始位置（指向新單詞的首字符），另一個用于向前搜索以尋找單詞的終點。但是不論掃描緩沖區設得多大都不能保證單詞符號不會被緩沖區的邊界所打斷。因此，掃描緩沖區最好使用一分為二的區域，并使兩區首尾相接，形成一個對半互補緩沖區。例如：每半個區可容64個字符，而這兩個半區又是互補的。如果搜索指示器從單詞起點出發搜索到半區的邊緣但尚未達到單詞的終點，那么就調用預處理子程序，令其把后續的64個字符裝入另半區?？梢哉J定在另半區一定可以達到單詞的終點。這意味著標示符和常數的長度實際上必須加以限制，否則即使緩沖區再大也無濟于事。128于是對半互補緩沖區可圖示如下：

。。。。。。While。。。。。。起點指針搜索指針

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

129單詞符號掃描器預處理子程序輸入緩沖區源程序掃描緩沖區列表語法分析器取單詞1303.單詞符號識別－超前搜索技術問題發生在對基本字不加任何保護的語言中，基本字及用戶自定義的標識符或標號之間無特殊分界符，這使得關鍵字的識別甚為麻煩。

請看下面的例子：

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

這四個語句都是正確的FORTRAN語句。語句1和2分別是DO和IF語句，它們都是以某基本字開頭的。語句3和4是賦值語句，它們都是以用戶自定義的標識符開頭的。131

為了從1、2中識別出關鍵字DO和IF，我們必須要能夠區別1、3和區別2、4。語句1、3的區別在于等號之后的第一個界符：一個為逗號，另一個為小數點，語句2、4的主要區別在于右括號后的第一個字符：一個為字母，另一個為等號。這就是說，為了識別1、2句中的關鍵字，我們必須超前掃描許多個字符，超前到能夠肯定詞性的地方為止。對于1、3來說，盡管都以‘D’和‘O’兩個字母開頭，但不能一見‘DO’就認定是DO語句。而必須超前搜索，跳過所有的字母和數字，看看是否有等號。如果有，再向前搜索。若下一個界符是逗號，則可以肯定DO應為關鍵字。否則，DO不構成關鍵字，它只是用戶標識符的頭兩個字母。132

所以為了區別1和3，必須超前掃描若干字符直到等號后的第一個界符處。對于2和4來說，同樣需超前掃描到與IF后的左括號相對應的那個右括號之后的第一個字符為止。若此字符是字母，則得邏輯IF。若此字符為數字，則得算術IF。否則，應認為是用戶自定義標識符IF。這種向前掃描若干字符直到找到能區分單詞的字符為止的技術就叫超前搜索。

133

標識符的識別：標識符是字母開頭的一個字母數字串，一般有運算符和界符分開，與基本字的區別前已談及，所以容易識別。常數的識別：算術常數大多相似，只是轉換二進制的問題，但像3.E5、3.EQ.5顯然也要用到超前搜索技術。另有3HABC一類的常數需要特殊處理。算符