《編譯原理》

(PrinciplesofCompiling)第1章引論1.1計算機語言的發展1.2翻譯系統1.3編譯系統的功能分析1.4編譯程序總體結構1.5編譯程序的生成1.6編譯技術的應用1.1計算機語言的發展機器語言(MachineLanguage)0、1代碼匯編語言(AssembleLanguage)0、1代碼與助記符：更接近于計算機硬件指令系統的工作高級語言(HighLevelLanguage)定義數據、描述算法（程序）如：C、FORTRAN、PASCAL、C++、JAVA、SQL(數據定義、數據操作)命令語言(Command)以功能封裝為特征高級語言的分類強制式語言(ImperativeLanguage)FORTRAN(段結構)、BASIC、Pascal(嵌套結構)、C……函數(應用)式語言(FunctionalLanguage)LISP、ML……邏輯式(基于規則)語言(LogicalLanguage)Prolog……面向對象語言(Object-OrientedLanguage)Smalltalk、C++、Java、Ada(程序包)……1.2翻譯系統翻譯程序(Translator)將某一種語言描述的程序(源程序——SourceProgram)翻譯成等價的另一種語言描述的程序(目標程序——ObjectProgram)的程序。翻譯程序源程序目標程序(*.C/*.PAS/*.AS)(*.OBJ/*.EXE/*.*)1.2翻譯系統解釋程序(Interpreter)口譯與筆譯（單句提交與整篇提交）源程序輸入數據計算結果解釋程序1.2翻譯系統編譯程序(Compiler)高級語言程序→匯編/機器語言程序源程序目標程序編譯程序1.2編譯系統SP Compiler

S-Source O-Object OP P-ProgramInput RS RS-RunSys. Output 編譯系統(CompilingSystem)編譯系統=編譯程序+運行系統支撐環境、運行庫等1.2翻譯系統其它：診斷編譯程序（DiagnosticCompiler)優化編譯程序（OptimizingCompiler)交叉編譯程序（CrossCompiler)可變目標編譯程序（RetargetableCompiler)并行編譯程序（ParallelizingCompiler）匯編程序(Assembler)、交叉匯編程序(CrossAssembler)、反匯編程序（Disassembler)1.2翻譯系統—匯總ML MLP Assembler DisassemblerAL ALP Compiler DataHL HLP Interpreter ResultM-MachineL-LangugeP-ProgramA-AssembleH-HighLevelTranslator1.3編譯系統的功能分析程序分析詞法、語法、語義分析綜合語句的翻譯、代碼生成例如：標識符左值與右值的綁定(binding)變量：存儲單元函數：目標代碼序列1.4編譯程序總體結構請參閱P5圖1.1

目標代碼生成器代碼優化器語義分析與中間代碼生成器語法分析器表格管理出錯處理中間代碼中間代碼目標代碼語法單位單詞符號詞法分析器源程序1.詞法分析例：res=fact*(term1+term2);結果IDN res‘=’IDNfact‘*’‘(’IDN term1‘+’IDNterm2‘)’‘;’1、詞法分析詞法分析器(LexicalAnalyzer)又叫做掃描器(Scanner)，完成詞法分析功能：詞法分析器從左到右掃描源程序（字符串），并將其轉換成單詞(記號—Token)串；同時查詞法錯誤，進行標識符登記——符號表管理。輸入：字符串 輸出：(種別碼，屬性值)——序對屬性值——token的機內表示2、語法分析語法分析器(SyntaxAnalyzer，又叫Parser)完成語法分析功能：Parser實現“組詞成句”，構造分析樹，指出語法錯誤，指導翻譯輸入：Token序列輸出：語法成分2.語法分析res=fact*(term1+term2); 字符串*；賦值語句表達式=）（fact表達式res表達式表達式表達式表達式+term1term23.語義分析功能：分析由語法分析器給出的語法單位的語義獲取標識符的屬性：類型、作用域等語義檢查：運算的合法性、取值范圍等子程序的靜態綁定：代碼的相對地址變量的靜態綁定：數據的相對地址4.中間代碼生成中間代碼(intermediateCode)例:id1+id2*id3后綴表示(逆波蘭ReversePolishNotation)id1id2id3*

+前綴表示(波蘭PolishNotation)+id1*id2id3四元組表示(三地址碼)1(*,id1,id2,T1)2(+,id3,T1,T2)

三元組表示1(*,id2,id3)2(+,id1,(1))

EE+Eid1E*Eid2id3語法樹波蘭表示問題——Lukasiewicz1929/1951年發明

中綴表示(Infixnotation):(a+①b)*(-c+②d)+③e/f波蘭表示（Polish/Prefix/Parenthesis-free/Lukasiewicznotation）——也就是前綴表示+③*+①ab+②@cd/ef運算順序從右向左逆波蘭表示(ReversePolish/Suffix/Postfixnotation)——也就是后綴表示

ab+①c@d+②*ef/+③運算順序從左向右4.中間代碼生成中間代碼的特點簡單規范機器無關易于優化與轉換三地址碼的另一種表示形式T1=id2*id3T2=id1*T1其它類型的語句舉例

printf(“hello”)x:=s （賦值）paramx （參數）callf （函數調用）s是hello的地址f是函數printf的地址對中間代碼的優化處理:對代碼進行等價變換以求提高執行效率——提高運行速度和節省存儲空間與機器無關的優化與機器有關的優化5.代碼優化與機器無關的優化局部優化常量合并：常數運算在編譯期間完成，如8+9*4公共子表達式的提取:基本塊內循環優化強度削減代碼外提與機器有關的優化寄存器的利用將常用量放入寄存器，以減少訪問內存的次數體系結構MIMD、SIMD、SPMD、向量機、流水機存儲策略根據算法訪存的要求安排：Cache、并行存儲體系——減少訪問沖突任務劃分按運行的算法即體系結構，劃分子任務(MPMD)6.目標代碼生成將中間代碼轉換成目標機上的機器指令代碼或匯編代碼7、表格管理管理各種符號表（常數、標號、變量、過程、結構……），查、填（登記、查找）源程序中出現的符號和編譯程序生成的符號，為編譯的各個階段提供信息。輔助語法檢查、語義檢查完成靜態綁定、管理編譯過程Hash表、鏈表等各種查、填表技術8、錯誤處理進行各種錯誤的檢查、報告、糾正，以及相應的續編譯處理（如：錯誤的定位與局部化）詞法：拼寫……語法：語句結構、表達式結構……語義：類型不匹配……模塊分類分析：詞法分析、語法分析、語義分析綜合：中間代碼生成、代碼優化、目標代碼生成輔助：符號表管理、出錯處理8項功能對應8個模塊編譯程序總體結構中間代碼目標代碼生成器代碼優化器語義分析與中間代碼生成器語法分析器表格管理出錯處理中間代碼目標代碼語法單位單詞符號詞法分析器源程序例一個語句的翻譯9編譯的遍（Pass）根據系統資源的狀況、運行目標的要求……等，可以將一個編譯程序設計成多遍掃描的形式，在每一遍掃描中，完成不同的任務。遍可以和階段相對應，也可無關單遍代碼不太優中間代碼目標代碼生成器代碼優化器語義分析與中間代碼生成器語法分析器中間代碼目標代碼語法單位單詞符號詞法分析器源程序10、編譯的前端與后端前端與源語言有關、與目標機無關的部分詞法分析、語法分析、語義分析與中間代碼生成、與機器無關的代碼優化后端與目標機有關的部分與機器有關的代碼優化、目標代碼生成1.5編譯程序的生成設計目標目標程序小，執行速度快編譯程序小，執行速度快診斷能力強，可靠性高可移植性，可擴充性如何實現編譯器？直接用可運行的代碼編制——太費力！Ｔ形圖表示語言翻譯的Ｔ形圖源語言表示語言目標語言功能1）交叉編譯(CrossCompiling)/移植問題一：A機上有一個C語言編譯器，是否可利用此編譯器實現B機上的C語言編譯器？條件：Ａ機有Ｃ語言的編譯程序（P1)目的：實現Ｂ機的Ｃ語言的編譯(P3)1.

(人)用Ｃ語言編制B機的Ｃ編譯程序P0(C→B)Ｃ語言Ｃ語言Ｂ機器P0Ｃ語言Ａ機器A機器P1Ｃ語言A機器Ｂ機器P22.(Ａ機的C編譯P1)編譯P0，得到在A機上可運行的P2(C→B)Ｃ語言Ｃ語言Ｂ機器P0Ｃ語言Ａ機器A機器P1Ｃ語言A機器Ｂ機器P2獲得一個工具Ｃ語言A機器Ｂ機器P2Ｃ語言Ｃ語言Ｂ機器P03.(用Ａ機的P2)編譯P0，得到在B機上可運行的P3(C→B)Ｃ語言Ｂ機器Ｂ機器P32)本機編譯器利用問題二：A機上有一個C語言編譯器，現要實現一個新語言NEW的編譯器？能利用交叉編譯技術么？Ｃ語言Ａ機器A機器P1(原有)NEW語言A機器A機器P2(生成)NEW語言Ｃ語言A機器P0(編寫)用C編寫NEW的編譯，并用C編譯器編譯它問題三：直接在一個機上實現C語言編譯器，還有別的技術么？解決：用匯編語言實現一個Ｃ子集的編譯程序(P0—人)用匯編程序處理該程序,得到P2(P2:可直接運行)用Ｃ子集編制Ｃ語言的編譯程序(P3—人)用P2編譯P3，得到P43)編譯程序的自展技術1.

用匯編語言實現一個Ｃ子集的編譯程序(P0—人)C語言子集匯編語言機器語言P02.用匯編程序(P1)處理該程序,得到P2(P2:可直接運行)匯編語言機器語言機器語言P1C語言子集機器語言機器語言P2獲得一個工具C語言子集機器語言機器語言P23.用Ｃ子集編制Ｃ語言的編譯程序(P3—人)C語言C子集機器語言P34.用P2編譯P3，得到P4C語言機器語言機器語言P44)利用編譯程序自動生成器詞法分析器的自動生成程序詞法規則說明詞法分析程序(C程序)輸入： 詞法（正規表達式） 識別動作（Ｃ程序段）輸出：

yylex()函數LEX語法分析器的自動生成程序語法規則說明語法分析程序(C程序)輸入： 語法規則（產生式） 語義動作（Ｃ程序段）輸出：

yyparse()函數ＹＡＣＣ1.6編譯技術的應用把復雜數據看作一條語句數據格式的分析利用詞法分析、語法分析方法數據處理的框架基于語法制導的語義處理框架編譯技術可以用于各種復雜數據的分析處理例1-1DOS命令date的輸出格式例：9-2-1993、09-03-1993、9-03-93語法date→month-day-year詞法month→DIGITDIGIT|DIGITday→DIGITDIGIT|DIGITyear→DIGITDIGIT|DIGIIDIGITDIGITDIGIT例1-1語義year(年)、month(月)、day(日)語義約束條件0<month.value<130<day.value<32，31，300<year.value<100002.1語言概述什么是語言自然語言(NaturalLanguage)是人與人的通訊工具語義(Semantics):環境、背景知識、語氣、二義性——難以形式化計算機語言(ComputerLanguage)計算機系統間、人機間通訊工具嚴格的語法(Grammar)、語義(Semantics)——易于形式化：嚴格語言是用來交換信息的工具——功能性描述2.1語言概述語言的描述方法——現狀自然語言：自然、方便-非形式化數學語言（符號）：嚴格、準確-形式化形式化描述高度的抽象，嚴格的理論基礎和方便的計算機表示。2.1語言概述語言——形式化的內容提取單詞(Token)：滿足一定規則字符(Character)串句子(Sentence)：滿足一定規則單詞序列語言(Language)：滿足一定條件的句子集合語言是字和組合字的規則——結構性描述例：一譯開天第課今始編節上今天開始上第一節編譯課2.1語言概述程序設計語言——形式化的內容提取程序設計語言(ProgrammingLanguage)：組成程序的所有語句的集合程序(Program)：滿足語法規則的語句序列語句(Sentence)：滿足語法規則的單詞序列單詞(Token)：滿足詞法規則的字符串例變量=表達式if條件then語句while條件do語句call過程名(參數表)2.1語言概述描述形式——文法語法——語句語句的組成規則描述方法：BNF范式、語法(描述)圖詞法——單詞單詞的組成規則描述方法：BNF范式、正規式2.2基本定義字母表（Alphabet）是一個非空有窮集合，字母表中的元素稱為該字母表的一個字母（Letter），也叫字符（Character）例以下是不同的字母表 ⑴{a，b，c，d} ⑵{a，b，c，……，z} ⑶{0，1}相當于高級語言的字符集2.2基本定義字母表上符號串(String)的定義

(1)ε是∑上的一個符號串，叫做空串。(2)若x是∑上的符號串，而a是∑的元素,

則xa是∑上的符號串。(3)y是∑上的符號串,當且僅當它由(1)和(2)導出。由字母表中的符號所組成的的任何有窮序列被稱之為該字母表上的符號串,也稱作“字”(Word)。2.2基本定義定義1設∑1、∑2是兩個字母表，∑1與∑2

的乘積(Product)∑1∑2={ab|a∈∑1，b∈∑2}例:∑1={0,1},∑2={a,b},∑1∑2={0a,0b,1a,1b}定義2設∑是一個字母表，∑的n次冪(Power)遞歸地定義為：⑴∑0={ε}⑵∑n=∑n-1∑ n≥1例：∑13={000,001,010,011,100,101,110,111}2.2基本定義定義3設∑是一個字母表，∑的正閉包(PositiveClosure)：∑+=∑∪∑2∪∑3∪∑4∪……∑的克林閉包(KleeneClosure)：∑*=∑0∪∑+=∑0∪∑∪∑2∪∑3∪……2.2基本定義例{0,1}+={0，1，00，01，11，000，001，010，011，100，……}{a，b，c，d}+={a，b，c，d，aa，ab，ac，ad，ba，bb，bc，bd，……，aaa，aab，aac，aad，aba，abb，abc……}2.2基本定義例{0,1}*={ε，0，1，00，01，11，000，001，010，011，100，…}{a，b，c，d}*={ε，a，b，c，d，aa，ab，ac，ad，ba，bb，bc，bd，…，aaa，aab，aac，aad，aba，abb，abc，…}2.2基本定義定義5設∑是一個字母表，

L

∑*，L稱為字母表∑上的一個語言（Language），

x∈L，x叫做L的一個句子。例：字母表{0，1}上的語言{0，1}{00，11}{0，1，00，11}{0，1，00，11，01，10}{00，11}*{01，10}*2.2基本定義設s是符號串：01290273前綴：移走s的尾部的零個或多于零個符號后綴：刪去s的頭部的零個或多于零個符號子串：從s中刪去一個前綴和一個后綴子序列:從s中刪去零個或多于零個符號(這些符號不要求是連續的）長度：是該符號串中的符號的數目。例如|aab|=3,|ε|=0。2.2基本定義符號串的連接和冪1.連接：設x和y是符號串，它們的連接xy是把y的符號寫在x的符號之后得到的符號串。例如，x=ba,y=nana,xy=banana.2.冪：x0=

;x1=x;x2=xx;……;xn=xn-1x;

例如,x=ba,x1=ba,x2=baba,x3=bababa,…...2.3文法的定義如何實現語言結構的形式化描述？考慮一個句子——文法要素的提取分析：Thegraywolfwilleatthegoat〈謂語〉〈主語〉〈形容詞〉〈名詞〉〈動詞〉〈直接賓語〉助動詞〈句子〉動原冠詞名詞Thegraywolfwilleatthegoat〈冠詞〉提取規則，寫在黑板上

句子

→

主語

謂語

主語

→

冠詞

形容詞

名詞

謂語

→

動詞

直接賓語

動詞

→

助動詞

動詞原形

直接賓語

→

冠詞

名詞

產生句子的規則——從產生語言的角度

冠詞

→

the

形容詞

→

gray

助動詞

→

will

動詞原形

→

eat

名詞

→

wolf

名詞

→

goat終結符號集VT={the，gray,wolf,will,eat,goat}非終結符號集VN={

句子

，

主語

，

謂語

，

冠詞

，

形容詞

，

名詞

，

動詞

，

直接賓語

，

助動詞

，

動詞原形

}語法規則集P={

句子

→

主語

謂語

，……}開始符號S=

句子

句子的語法組成

——終結符號集，非終結符號集，語法規則，開始符號文法G的形式定義文法G為一個四元組:

Ｇ=(ＶT，ＶN，Ｐ，Ｓ)ＶT：終結符(Terminal)集ＶN：非終結符(Variable)集，ＶT∩ＶN=Φ語法范疇——某個語言結構Ｓ：開始符號(StartSymbol)，S∈ＶN至少在產生式左側出現一次文法G的形式定義Ｐ：產生式(Product)集合α→β，被稱為產生式（定義式），讀作：α定義為β。其中α∈(ＶT∪ＶN)+，且α中至少有ＶN中元素的一個出現。β∈(ＶT∪ＶN)*。α稱為產生式α→β的左部(LeftPart)，β稱為產生式α→β的右部(RightPart)。

句子

主語

謂語

冠詞

形容詞

名詞

謂語

the

形容詞

名詞

謂語

thegray

名詞

謂語

thegraywolf

謂語

thegraywolf

動詞

直接賓語

thegraywolf

助動詞

動詞原形

直接賓語

thegraywolfwill

動詞原形

直接賓語

thegraywolfwilleat

直接賓語

thegraywolfwilleat

冠詞

名詞

thegraywolfwilleatthe

名詞

thegraywolfwilleatthegoat句子的派生（推導）___根據規則

句子

thegraywolfwilleatthegoatthegraywolfwilleatthewolfthegraygoatwilleatthewolfthegraygoatwilleatthegray符合語法且符合語義的句子僅是：

thegraywolfwilleatthegoat還可以“得出”其他的句子例2-1算術表達式的文法考慮簡單算術表達式組成的語言遞歸定義——中綴表示標識符(id)（常數、變量）是表達式；表達式加一個表達式是表達式；表達式減一個表達式是表達式；表達式乘一個表達式是表達式；表達式除一個表達式是表達式；表達式加上括號后是表達式。例2-1算術表達式的文法考慮用式子表示這個定義標識符(id)是表達式表達式加一個表達式是表達式E→idE→E+E表達式減一個表達式是表達式E→E-E表達式乘一個表達式是表達式E→E*E表達式除一個表達式是表達式E→E/E表達式加上括號后是表達式E→(E)例2-1算術表達式的文法P:E→E+EE→E-EE→E*EE→E/EE→(E)E→idG=（{id，+，-，*，/，(，)}，{E}，P，E）約定：只寫產生式簡寫E→E+E|E*E|E-E|E/E|(E)|id產生式的簡寫對一組有相同左部的產生式α→β1，α→β2…，α→βn簡單地記為：α→β1|β2|…|βn

讀作：α定義為或者β1，或者β2，…，或者βn。并且稱它們為α產生式。β1，β2，…，βn稱為候選式(Candidate)文法如何實現對語言的刻畫？產生式很關鍵！產生式規定的一些變換E由第1個候選式可以變成E+EE+E中的第1個E由第2個候選式可以變成E*E，從而E+E變成E*E+E根據第4個候選式，E*E+E中的E都可以變成id:E*E+E變成id*E+Eid*E+E變成id*E+idid*E+id變成id*id+id也就是說，根據第4個候選式，E*E+E經3步變換變成id*id+id1E→E+E2E→E*E3E→(E)4E→id5E→E-E6E→E/E表示依據文法進行的變換E

E+E （1）

E*E+E （2）

id*E+E （4）

id*E+id （4）

id*id+id （4）4E→id5E→E-E6E→E/EE可以變成E+EE+E中的第一個E變成E*EE*E+E變成id*E+Eid*E+E變成id*E+idid*E+id變成id*id+idE經5步變換變成id*id+id：E

5id*id+id1E→E+E2E→E*E3E→(E)實質是從E開始依據產生式對所得串中的特定部分進行變換，不斷獲得新的串，最終得到目標變換的分析實質是從E開始依據產生式對所得串中的特定部分進行變換，不斷獲得新的串，最終得到目標

E*E

依據產生式E→E+EE*E+EαAβ依據產生式A→γαγβ直接推導與歸約根據產生式對符號串進行變換的過程Ａ→γ是文法Ｇ的一個產生式，且α、β∈（ＶT∪ＶN）*，稱αＡβ的直接推導/派生(Derive)出αγβ，也稱αγβ直接歸約(Reduce)為αＡβ。記為αＡβ

αγβ例：id+E

id+E*E（多步）推導/歸約α0

α1

α2

…

αn記為α0

nαn

(恰用n步)α0

+αn

（至少一步）

α0

*αn

（若干步:零步或多步）E

5id*id+id推導/歸約回顧E

E+E （1）串中含有變量

id+E （4）串中含有變量

id+E*E （2）串中含有變量

id+id*E （4）串中含有變量

id+id*id （4）串中沒有變量到此串中已經沒有（語法）變量了，不能再推了——得到句子1E→E+E2E→E*E3E→(E)4E→id句型與句子E

E+E

E+E*EE

4id+id*E定義:如果S

*α，α∈(ＶT∪ＶN)*則稱α是G產生的一個句型(SententialForm)E

5id+id*id定義:如果S

*x，且x∈ＶT*，則稱x是G產生的一個句子(Sentence)文法G產生的語言定義： L(G)={x|S

*xandx∈VT*}文法E→E+E|E*E|(E)|id可以派生出多少個句子？文法G的作用——語言的有窮描述以有限的規則描述無限的語言現象有限:產生式集合、終結符集合、非終結符集合無限：可以導出無窮多個句子（注：L也可是有窮）id+id*id的不同推導E→E+E|E*E|(E)|idE

E+E

id+E

id+E*E

id+id*E

id+id*idE

E+E

E+E*E

E+E*id

E+id*id

id+id*idE

E*E

E+E*E

E+id*E

id+id*E

id+id*id不做限制句型

(sententialForm)（歸約）E

*

id+id*id施于最右變量右句型/規范句型 (canonical~)(最左/規范歸約)E

+

id+id*id施于最左變量左句型(left-~)（最右歸約）

E

5

id+id*id最左推導與最右推導最左推導(Left-mostDerivation)每次推導都施加在句型的最左邊的語法變量上——與最右歸約對應最右推導(Right-mostDerivation)每次推導都施加在句型的最右邊的語法變量上——與最左歸約（規范規約）對應的規范(Canonical)句型短語(Phrase)

Ｓ

*

αＡβ

+αγβ

？？就自然語言而言，γ在αγβ中什么叫什么？）如果Ｓ

*

αＡβ&A

γ則稱γ是句型αγβ的相對于變量A的直接短語最左直接短語叫做句柄(Handle)如果Ｓ

*

αＡβ&A

+γ，則稱γ是句型αγβ的相對于變量A的短語例：句型的短語與直接短語E

E+T

T+T

F+T

(E)+T

(E+T)+T

(E+T)+T

(T+T)+T

(F+T)+T

(a+T)+T

(a+T*F)+T

(a+F*F)+T

(a+b*F)+T

(a+b*c)+T

(a+b*c)+F

(a+b*c)+dE→E+T|TT→T*F|FF→(E)|id句型的句柄(Handle)——最左直接短語E→E+T|TT→T*F|FF→(E)|idE

E+T

T+T

F+T

(E)+T

(E+T)+T

(E+T)+T

(T+T)+T

(F+T)+T

(a+T)+T

(a+T*F)+T

(a+F*F)+T

(a+b*F)+T

(a+b*c)+T

(a+b*c)+F

(a+b*c)+d例2-2標識符的文法1S→L|LT T→L|N|TL|TN L→a|b|c|d letter N→0|1|2|3|4|5 digit?正整數的文法；正實數的文法2.４文法的分類(Chomsky體系)語言結構的復雜程度（形式語言）涉及文法的復雜程度、分析方法的選擇如果G滿足文法定義的要求，則Ｇ是０型文法（短語結構文法PSG:PhraseStructureGrammar）。L(G)為PSL。例2-3標識符的文法2S→L|LT T→L|N|TL|TN L→a|b|c|d N→0|1|2|3|4|5S→a|b|c|d S→aT|bT|cT|dT T→a|b|c|d|0|1|2|3|4|5 T→aT|bT|cT|dT|0T T→1T|2T|3T|4T|5T例2-4標識符的文法3S→a|b|c|dS→aT|bT|cT|dTT→a|b|c|dT→0|1|2|3|4|5T→aT|bT|cT|dT|0TT→1T|2T|3T|4T|5TS→a|b|c|dS→Ha|Hb|Hc|Hd|H0S→H1|H2|H3|H4|H5H→Ha|Hb|Hc|Hd|H0H→H1|H2|H3|H4|H5H→a|b|c|dA→aB或A→aA→Ba或A→a正規文法(RG)設A、B∈VN，a∈VT∪{

}右線性(RightLinear)文法：A→aB或A→a左線性(LeftLinear)文法：A→Ba或A→a都是３型文法(正規文法RegularGrammar-RG)L(G)為3型/正規集/正則集/正則語言（RL）例：程序設計語言的多數詞法特性左、右線性文法不可混用例非CFL的文法L={anbncn|n>0}的文法S

aBC|aSBCCB

BCaB

abbB

bbbC

bccC

cc“可以證明”不存在CFGG,使L(G)=L

在我們使用的程序語言中,有些語言結構并不是總能用上下文無關文法描述的。例L1={wcw|w∈{a,b}+}。例,aabcaab就是L1的一個句子。這個語言是檢查程序中標識符的聲明應先于引用的抽象。

例L2={anbmcndm|n,m≥0}，它是檢查過程聲明的形參個數和過程引用的參數個數是否一致問題的抽象。高級語言中的非CFL結構Chomsky體系——總結1型文法(CSG)S

aBCS

aSBCCB

BCaB

abbB

bbbC

bccC

cc

0型文法(PSG)S

aBCS

aSBCCB

BCaB

dbB

bbbC

bcC

cc2型文法(CFG)E→E+EE→E*EE→(E)E→idE→E-EE→E/E

3型文法S→a|bS→aT|bTT→a|bT→1|2T→aT|bTT→1T|2T3型文法S→a|bS→Ha|HbS→H1|H2H→Ha|HbH→H1|H2H→a|bChomsky體系——總結Ｇ=(ＶT，ＶN，Ｐ，Ｓ)是一個文法,α→β∈P* G是0型文法，L(G)是0型語言；

---其能力相當于圖靈機(TM)* |α|≤|β|:G是1型文法，L(G)是1型語言(除Ｓ→ε);

---其識別系統是線性界限自動機(LBA)* α∈ＶN:G是2型文法，L(G)是2型語言;

---其識別系統是不確定的下推自動機(PDA)* A→aB或A→a:G是右線性文法，L(G)是3型語言

A→Ba或A→ａ:G是左線性文法，L(G)是3型語言

---其識別系統是有窮自動機(FA)四種文法之間的關系是將產生式作進一步限制而定義的四種文法之間的逐級“包含”關系如下：2型文法1型文法0型文法3型文法Chomsky體系——總結ＢＮＦ范式——Backus-NaurForm

Backus-NormalFormα→β表示為α∷＝β非終結符用“<”和“>”括起來終結符：基本符號集其他β(α1|α2…|αn)≡βα1|βα2…|βαn{α1|α2…|αn}ul

{α1|α2…|αn}ml=0,u=m[α]≡α|ε……ＢＮＦ范式——BackusNormalForm例簡單算術表達式(只寫產生式)<簡單表達式>∷＝<簡單表達式>+<簡單表達式><簡單表達式>∷＝<簡單表達式>*<簡單表達式><簡單表達式>∷＝(<簡單表達式>)<簡單表達式>∷＝id即：<簡單表達式>∷＝<簡單表達式>+<簡單表達式>| <簡單表達式>*<簡單表達式>|(<簡單表達式>)|id哪些是終結符？哪些是變量？例2-5句子結構的表示

(文法E→E+E|E*E|(E)|id

）EE+EE→E+EidE→idEE*E→E*EidE→ididE→idE

E+E

id+E

id+E*E

id+id*E

id+id*id一棵樹！2.5CFG的語法樹ParseTree用樹的形式表示句型的結構樹根：開始符號中間結點：非終結符葉結點：終結符或者非終結符每個推導對應一個中間結點及其兒子——一個二級子樹-直接短語又稱為語法分析樹例2-6短語與語法(分析)樹

(文法E→E+E|E*E|(E)|id

）EE+Eid(a1)EE*id(a2)id(a3)短語——一棵子樹的葉子！短語：非單一結點的子樹的結果是相對于子樹根的短語。直接短語：僅有父子兩代的子樹的結果。句柄：一個句型的分析樹中最左那棵只有父子兩代的子樹的結果。例如，對表達式文法G[E]和句子a1+a2*a3，挑選出推導過程中產生的句型中的短語，直接短語，句柄。用子樹解釋短語，直接短語，句柄E

E+T

T+T

F+T

a1+T

a1+T*F

a1+F*F

a1+a2*FE+T

T,T+TF,F+Ta1,a1+Ta1,T*F,a1+T*Fa1,F,F*F,a1+F*F

a1,a2,a1+a2*F,a2*F

a1,a2,a3,a2*

a3

a1+a2*a3EE+TTFa1T*FFa2a3

a1+a2*a3短語a1+a2*a3

1.描述一個句子的文法不是唯一的；

2.對于一個句子的分析應是唯一的。考慮表達式下面的文法G[E],其產生式如下：

E

E+E

E*E

(E)

id

文法的二義性(歧義性/ambiquity)文法的二義性EE*EidEE+ididEE+EEEid*idid一個句子有兩棵不同的語法樹

E

E+E

a1+E

a1+E*E

a1+a2*E

a1+a2*a3

E

E*E

E+E*E

a1+E*E

a1+a2*E

a1+a2*a3EE+Ea1E*Ea2a3EE*E+EEa1a2a3兩個不同的最左推導,對應兩不同的語法樹

E

E*E

E*a3

E+E*a3

E+a2*a3

a1+a2*a3EE+Ea1E*Ea2a3EE*E+EEa1a2a3兩個不同的最右推導,對應兩不同的語法樹

E

E+E

E+E*E

E+E*a3

E+a2*a3

a1+a2*a3如果一個文法的句子存在兩棵分析樹,那么,該句子是二義性的如果一個文法包含二義性的句子,則稱這個文法是二義性的;否則，該文法是無二義性的文法的二義性1.一般來說,高級程序設計語言存在無二義性文法,但有時用二義性文法。如：表達式文法、條件語句文法S

ifexprthenS

ifexprthenSelseS

other二義性的句子:ife1thenife2thens1elses2

E→E+E|E-E|E*E|E/E|(E)|id無二義性文法較復雜E→E+T|E-T|TT→T*F|T/F|FF→(E)|id文法的二義性文法的二義性1.一般來說,高級程序設計語言存在無二義性文法,但有時用二義性文法。如：表達式文法、條件語句文法S

ifexprthenS

ifexprthenSelseS

other二義性的句子:ife1thenife2thens1elses2

文法的二義性2.對于任意一個CFG，不存在算法判定它是無二義性的；但能給出一組充分條件，滿足這組充分條件的文法是無二義性的一個文法是否為二義性的不可判定文法的二義性3.存在先天二義性語言。例如，語言

aibicj

i,j

1

aibjcj

i,j

1

存在二義性的句子akbkck一個語言是否為先天二義性的，在理論上不可判定文法的二義性4.在能駕馭的情況下，使用二義性文法——簡單E→E+E|E-E|E*E|E/E|(E)|id無二義性文法較復雜E→E+T|E-T|TT→T*F|T/F|FF→(E)|id參考書：(抽象)語法樹不同(語法)分析樹EE+idE+EEidid(抽象)語法樹+id+idid2.6文法的構造——為了更好地理解文法目的：給出語言的有窮描述途徑：刻畫語言的結構做法：給出定義的形式化描述根據經驗給出描述文法舉例{x|x是長度為偶數的0、1串} ——RLS→00S|01S|10S|11S|ε{0m1n|m,n≥1} ——RLS→0S|0A A→1A|1{0n1n|n≥1} ——CFLS→0S1|01{ww|w∈{a,b}+} ——PSLS→aCAE|bCBE Aa→aAAb→bAAE→aRE RE→DaR→RabR→RbCR→aCA|bCBBa→aBBb→bBBE→bREaR→RabR→RbCR→aCA|bCBaD→DabD→DbED→ε例2-7：{w|w為十進制數}R→N|N.DN→1|2|3|4|5|6|7|8|9N→N0|N1|N2|N3|N4|N5|N6|N7|N8|N9D→1|2|3|4|5|6|7|8|9D→0D|1D|2D|3D|4D|5D|6D|7D|8D|9DR→0|0.D|N.0|0.0無用產生式與無用符號E→T|E+T|E-TT→F|T*F|T/FF→(E)|idE→E|H+TT→FH|TQ+PF|EQFM

→(E)|id單一產生式、派生不出終極符號行(H、Q、P)、從開始符號無法派生出來(M)文法構造小結明確描述對象──語言合法的語言結構確定基本符號集VT引入非終結符各種句子結構定義句子的組成規則BNF范式或產生式值得注意的問題文法描述描述句子的組成規則，不涉及語義文法正確不能保證語義正確（例）明確目標要描述語言的結構確認基本符號集合理引入非終結符（語義明確）主要內容詞法分析器(LexicalAnalyzer,Scanner)的功能正規表達式有窮狀態自動機FA——狀態圖詞法分析器的設計與實現3.1詞法分析（掃描）器的功能功能：輸入源程序，輸出(單詞)符號(token)。即：把構成源程序的字符串轉換成單詞符號的序列單詞符號的形式按照最小的語義單位設計通常表示為二元組： （單詞符號種別，屬性值）關鍵——找出符號的分割符例如：axx=70.35+12+exp(2.7)1)單詞符號的表示常用單詞符號種別——分類（P42）各關鍵字（保留字、基本字），各種運算符，各種分界符——各用一個種別碼標識其它標識符——用一個種別碼標識常數——用一個種別碼標識屬性（值）——單詞符號的值常數的值，標識符的名字等保留字、運算符、分界符的屬性值可以省略單詞符號編碼舉例單詞符號種別編碼內部值助記符DIM1$DIMIF2$IFDO3$DOSTOP4$STOPEND5$END標識符6內部符號串$IDN整數7標準二進制$INT=8$ASG+9$PLUS*10$STAR**11$POWER，12$COMMA（13$SLP）14$SRP例3-1:單詞符號序列

while(pointer!=N){S=S++;pointer++;}

while (WHILE,_)( (SLP,_)pointer (IDN,符號表項指針)!= (NE,_)N (IDN,符號表項指針)) (SRP,_){ (LP,_)S (IDN,符號表項指針) = (EQ,_)S (IDN,符號表項指針)++ (INC,_); (SEMI,_)pointer(IDN,符號表項指針)++ (INC,_); (SEMI,_)} (RP,_)2）相關問題詞法分析器可以作為一個獨立的子程序，也可以作為一遍獨立的掃描來安排。輸入緩沖區工作區(token)單詞開始指針掃描指針正拼單詞雙緩沖區并行、捻接每次移動向前指針都需要做兩次測試2）相關問題？如何設計和實現掃描器大小問題128Byte*2|1024Byte*2|4096Byte*2forward:=forward+1;if

forward在緩沖區第一部分末尾

then重裝緩沖區第二部分elseifforward在緩沖區第二部分末尾

thenbegin

重裝緩沖區第一部分;

將forward移到緩沖區第一部分開始

endforward:=forward+1;ifforward！=eofthenif

forward在第一部分末尾

then

重裝第二部分

elseifforward在第二部分末尾

thenbegin

重裝第一部分;

將forward

移到第一部分開始

endelse終止詞法分析/*eof

在表示輸入結束*/3.2符號的描述——正規(表達)式例：標識符的文法描述約定：用d表示數字：0,1,2,…,9;

用l表示字母：A,B,…,Z,a,b,…,zG=({d,l},{S,T},P,S)S→lS→SdS→Sl左線性文法S→l|lTT→lT|lT→dT|d右線性文法表示集合：{l}{l,d}*

1)正規式：正規語言的另一種描述方法例3-2：標識符的另一種表示l(l|d)*|表示"或"*表示Kleene閉包符號的并列表示符號連接關系正規式r表示正規集,相應的正規集記為L(r)正規(表達)式(RegularExpression——RE)設∑是一個字母表，⑴Φ是∑上的RE，L(Φ)=Φ；⑵ε是∑上的RE，L(ε)={ε}；⑶對于

a∈∑，a是RE，L(a)={a}；⑷如果r和s是RE，L(r)=R,L(s)=S，則：

r與s的“和”(r|s)是RE，L(r|s)=R∪S；

r與s的“乘積”(rs)是RE，L(rs)=RS；

r的克林閉包(r*)是RE，L(r*)=R*。⑸只有滿足⑴、⑵、⑶、⑷的才是RE。運算的優先級運算優先級和結合性:*高于“連接”和|，“連接”高于|| 具有交換律、結合律“連接” 具有結合律、和對|的分配律()指定優先關系意義清楚時，括號可以省略例：L(a(a|b)*(ε|((.|_)(a|b)(a|b)*))){a}{a,b}*({ε}∪{.,_}{a,b}{a,b}*)2)正規文法與正規式正規文法與正規式等價對任何正規文法，存在定義同一語言的正規式對任何正規式，存在生成同一語言的正規文法例3-3標識符定義的轉換引入SS→l(l|d)*引入A消除閉包S→lAA→(l|d)A|ε執行連接對|的分配律

S→lA A→lA|dA|ε

例3-4正規式到正規文法的轉換a(a|b)*(ε|((.|_)(a|b)(a|b)*)) =a(a|b)* |a(a|b)*.(a(a|b)*|b(a|b)*) |a(a|b)*_(a(a|b)*|b(a|b)*) =aA|aCA→aA|bA|εC→aC|bC|.B|_BB→aA|bAS→aA|aCA→aA|bA|εC→aC|bC|.B|_BB→aA|bA正規式到正規文法的轉換按如下方法構造正規定義式，并逐步將其轉換成正則文法引入開始符號S，從如下正規定義式開始S→r對r中的形如r1|r2|…|rn的子串用產生式組 A→r1|r2|…|rn表示正規式到正規文法的轉換對r中的形如r1*的子串用產生式組A→ε|r1A表示對r中的形如r1+的子式子，用產生式組A→r1|r1A表示執行連接對|的分配律對連接運算，要作特殊處理：按出現順序定義正規式到正規文法的轉換用到了正規定義式的概念例3-5：一個簡單詞法的正規定義式詞法規則 單詞種別 屬性<標識符>→<字母>(<字母>|<數字>)*

IDN 符號表項入口<無符號整數>→<數字>(<數字>)*

NUM 數值<賦值符>→:= ASG 無<加號>→+ + 無

<減號>→- MINUS 無<星號>→* STAR 無變換為正規文法<標識符>→letter<標識符尾><標識符尾>→ε|letter<標識符尾>|digit<標識符尾><整數>→digit<整數尾><整數尾>→ε|digit<整數尾> <賦值號>→:=<加號>→+<等號>→=…(其它：實數、算術運算符、關系運算符、分號、括號等）正規文法到正規定義式的轉換代入：對于A→xB,B→y，構造A→xy遞歸：對于A→xA|y，構造A→x*y多候選式：對于A→x，A→y，構造A→x|yS→0AA→1BB→2B|2C C→3C|3S→01BS→012*2CS→012*23*3S→012+3+

一個語言的文法描述不是唯一的（等價文法）3.3符號的識別──狀態轉換圖1狀態轉換圖（有窮自動機FAM=(Q，∑，δ，q0，F)）

用來描述詞法分析器識別記號的分析過程結點：狀態用○表示；終態用◎表示有向弧──箭頭弧標記──輸入字符標識符的狀態圖<標識符>→letter(letter|digit)*

123letterletter,digit其它開始終態初態例3-5的狀態圖詞法規則 單詞種別 屬性<標識符>→letter(letter|digit)*

IDN 符號表項入口<無符號整數>→digit(digit)*

NUM 數值<賦值符>→:= ASG 無<加號>→+ + 無

<減號>→- MINUS 無<星號>→* STAR 無例3-5的狀態圖letter,digitletter（IDN，入口）digitdigit

(其它)

(其它)（NUM，值）（ASG，_）=：+（ADD，_）s+（INC，_）其它IDN→letter(letter|digit)*NUM→digit(digit)*ASG→:=INC→++ADD→+利用狀態轉換圖識別單詞符號1.從初態出發2.讀入一字符3.按當前字符轉入下一狀態4.重復2,3直到無法繼續轉移在遇到讀入的字符是Token的分割符時，若當前狀態是終止狀態，說明讀入的字符組成一單詞；否則，說明輸入不符合詞法規則。2、從正規文法出發，構造狀態圖1.以每個非終結符為狀態結點，開始符號對應初態S2.增設一個終態TABaAa3.對于規則A→aB，畫從狀態A到B的弧，標為a4.對于規則A→a，畫從狀態A到終態T的弧，標為a*.對于規則A→rB,B→

sB，畫從狀態A到狀態N的弧，標為r和狀態N到N的標記為s的弧AsrB例3-6 Ｃ語言無符號整數的識別

1、正規定義式描述八進制數:(OCT，值)oct→0(0|1|2|3|4|5|6|7)(0|1|2|3|4|5|6|7)*十進制數:(DEC，值)dec→(1|...|9)(0|...|9)*|0十六進制數:(HEX，值)hex→0x(0|1|...|9|a|...|f|A|…|F)(0|...|9|a|...|f|A|…|F)*Asr2、識別不同進制數的狀態圖342100-70-7

(其它)56101-90-9

(其它)十進制整數八進制整數oct→0(0|1|2|3|4|5|6|7)(0|1|2|3|4|5|6|7)*dec→(1|...|9)(0|...|9)*|02、識別不同進制數的狀態圖910810

(其它)十六進制整數7x0-9,a-f0-9,a-f狀態圖合并1、從開始狀態出發；2、選擇輸入符號，構成目標狀態集3、從新狀態集出發，重復1、2hex→0x(0|1|...|9|a|...|f|A|…|F)(0|...|9|a|...|f|A|…|F)*（HEX，值）（OCT，值）3、Ｃ語言無符號整數識別的狀態圖9810其它2,6,7x0-9,a-f0-9,a-f30-70-7其它51-90-9其它（DEC，值）其它4106另一種做法開始12061-93x0-9,a-f40-9,a-f其它0-9其它50-70-7其它（DEC，值）（HEX，值）（OCT，值）其它3.4詞法分析程序的設計與實現狀態轉移圖——教材P43狀態轉移圖的實現——教材P44-46另一種實現：子程序scan()輸入：字符流輸出：Symbol(Code):單詞種別Attr(value):屬性（全局變量）數據結構與子例程數據結構ch當前輸入字符token輸入緩沖區(字符數組)symbol單詞種別（子程序的返回值）attr屬性（全局變量）子程序Lookup(token):將token存入符號表，返回入口指針isKeyword(token):判別token是關鍵字？返回關鍵字種別或-1getchar():從輸入緩沖區中讀入一個字符放入chisdigit()isalpha()例3-3的狀態圖的實現算法1.getchar()2.WHILEch是空格 //跳過空格2.1DOgetchar();3.CASEchOF4.isdigit(ch):4.1ch→token;getchar();4.2WHILEisdigit(ch)DO{ch→token;getchar();}4.3輸入指針回退一個字符；4.4將token中的字符串變成數值→attr4.5返回NUM5.isalpha(ch):5.1ch→token;getchar();5.2WHILEisalpha(ch)ORisdigit(ch)DO{ch→token;getchar()};5.3 輸入指針回退一個字符;5.4key=isKeyword(token);5.5IFkey≥0THEN返回key5.6Lookup(token)→attr;5.7返回IDN6':':getchar();6.1IFch等于'='THEN返回ASG6.2出錯處理7'+':返回ADD8'-':返回SUB9'*':返回MUL10'/':返回DIV11'=':返回EQ12'>':返回GT13'<':返回LT14'(':返回LP15')':返回RP16';':返回SEMI17其它:出錯處理18ENDOFCASE需要說明的問題緩沖區預處理，超前搜索關鍵字的處理，符號表的實現Lookup：查找效率，算法的優化實現詞法錯誤處理由于高級語言的詞組成的集合為3型語言，所以，這里討論的詞法分析技術可以用于處理所有的3型語言，也就是所有的可以用3型文法描述的語言。如：信息檢索系統的查詢語言、命令語言等LEX簡介：實現過程Lex源程序Lex.yy.cLex編譯器詞法分析器LLex.yy.cC編譯器Token序列詞法分析器L輸入流LEX簡介：Lex程序結構聲明部分(正規定義式)%%轉換規則(識別規則)%%輔助過程%{常量定義%}正規定義掃描器的自動生成：LEX簡介1、正規定義式letter→A|B|C|…|Z|a|b|c|…|zdigit→0|1|2|…|9identifier→letter(letter|digit)*integer→digit(digit)*

2、識別規則正規式 動作描述token1 {action1}token2 {action2}……tokenn {actionn}本章總結詞法分析器從組成源程序的字符行中尋找出單詞，并給出它們的種別和屬性——輸出二元組序列高級語言的單詞組成一個3型語言3型語言可以用RE、RG、FA描述FA的狀態轉移圖，可以被用來指導相應的詞法分析器的實現2023/11/241564.1語法分析的任務語法分析(SyntaxAnalysis)檢查掃描器輸出的單詞序列是否符合該語言的文法(句子)，并分析組成此