编译原理课件

《編譯原理》

(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-211564.1語法分析的任務語法分析(SyntaxAnalysis)檢查掃描器輸出的單詞序列是否符合