編譯原理課件

編譯原理

第一章引論1.1基本概念1.2編譯過程1.3編譯程序與程式設計環(huán)境1.4高級語言程式簡介32023-11-21一、發(fā)展機器語言→組合語言→高級語言→工具語言第1代1GL2GL3GL4GL機器識別：0|1代碼 相去甚遠1.1基本概念42023-11-21源語言程式目標語言程式翻譯程式翻譯1.1基本概念二、翻譯程式把某一種語言程式(稱為源語言程式)等價地轉換成另一種語言程式(稱為目標語言程式)的程式。如：中英互譯系統(tǒng)、DBMS語言(DDL,DCL)52023-11-21高級語言程式機器語言程式結果編譯程式翻譯運行三、編譯程序(compiler)

把某一種高級語言程式等價地轉換成另一種低級語言程式(如組合語言或機器語言程式)的程式。編譯程序分類診斷編譯程序&優(yōu)化編譯程序交叉編譯程序&可變目標編譯程序1.1基本概念62023-11-21四、解釋程式把源語言寫的根源程式作為輸入，但不產生目標程式，而是邊解釋邊執(zhí)行根源程式本身。根源程式結果解釋程式解釋執(zhí)行1.1基本概念72023-11-21編譯程序vs.解釋程式編譯解釋82023-11-21五、執(zhí)行高級語言程式的步驟把高級語言程式編譯成低級語言目標程式執(zhí)行目標程式1.1基本概念92023-11-21把英文翻譯為中文識別出句子中的一個個單詞；分析句子的語法結構；根據(jù)句子的含義進行初步翻譯；對譯文進行修飾；寫出最後的譯文。1.2編譯過程102023-11-21一、程式的編譯過程（見PPT30頁）詞法分析語法分析中間代碼產生優(yōu)化目標代碼生成1.2編譯過程作用、實現(xiàn)者(並非每個編譯過程均有以上全過程)112023-11-211.詞法分析任務:輸入根源程式，對構成根源程式的字串進行掃描和分解，識別出一個個單詞符號。依循的原則：構詞規(guī)則描述工具：正規(guī)式和有限自動機FORI:=1TO100DO

保留字識別字等符整常數(shù)保留字整常數(shù)保留字122023-11-212.語法分析任務:在詞法分析的基礎上，根據(jù)語言的語法規(guī)則把單詞符號串分解成各類語法單位。依循的原則：語法規(guī)則描述工具：上下文無關文法Z:=X+0.618*Y

算術運算式，賦值語句（層次結構分析）132023-11-213.中間代碼產生任務:對各類不同語法範疇按語言的語義進行初步翻譯。依循的原則：語義規(guī)則中間代碼:三元式，四元式，樹形結構等Z:=X+0.618*Y翻譯成四元式為

(1)*0.618YT1 (2)+XT1T2 (3):=T2_Z142023-11-214.優(yōu)化任務：對於前階段產生的中間代碼進行加工變換，以期在最後階段產生更高效的目標代碼。依循的原則：程式的等價變換規(guī)則FORK:=1TO100DOBEGINX:=I+1;M:=I+10*K;N:=J+10*K;END152023-11-21中間代碼（一）序號 OPR OPN1 OPN2RESULT注釋 (1) := 1 KK:=1 (2) j< 100 K (10)if(100<K)goto(10)(3) + I 1 X X:=I+1 (4) * 10 K T1 T1:=10*K(5) + I T1 M M:=I+T1 (6) * 10 K T2 T2:=10*K(7) + J T2 N N:=J+T2 (8) + K 1 K K:=K+1 (9) j (2) goto(2)(10) 162023-11-21轉換後的等價代碼（二）序號 OPR OPN1 OPN2 RESULT 注釋 (1) + I 1 X X:=I+1 (2) := I M M:=I (3) := J N N:=J (4) := 1 K K:=1 (5) j< 100 K (10) if(100<K)goto(10)(6) + M 10 M M:=M+10 (7) + N 10 N N:=N+10 (8) + K 1 K K:=K+1 (9) j (5) goto(5) (10) 172023-11-215.目標代碼產生任務:把中間代碼變換成特定機器上的目標代碼。依賴於硬體系統(tǒng)結構和機器指令的含義目標代碼三種形式:絕對指令代碼:可直接運行可重新定位指令代碼:連接裝配，彙編指令代碼:需要進行彙編182023-11-21模組A…a模組B…b模組C…c模組A…a模組B…b模組C…c模組A…a模組D…模組C…c192023-11-215.目標代碼產生例:b=a+2 MOVa,R1 ADD#2,R1 MOVR1,b 000101

00

00000000

* 001101

10

00000010

010001

00

00000100

* L=00001111 000101

00

00001111 001101

10

00000010 010001

00

00010011

202023-11-21二、編譯程序的邏輯結構1.2編譯過程212023-11-21三、表格與表格管理常見的表格:符號名表，常數(shù)表，標號表，入口名表，過程引用表。格式:名字資訊1.2編譯過程222023-11-21例:PASCAL程式段：PROCEDUREINCWAP(M，N:INTEGER);LABELSTART;VARK:INTEGER;BEGINSTART: K:=M+1; M:=N+4; N:=K;END.232023-11-21242023-11-21252023-11-21四、出錯處理出錯處理程式：發(fā)現(xiàn)根源程式中的錯誤，把有關錯誤資訊報告給用戶語法錯誤語義錯誤1.2編譯過程262023-11-21五、遍(Pass)所謂“遍”，對根源程式或根源程式的中間結果從頭到尾掃描一次，並作有關的加工處理，生成新的中間結果或目標程式。每遍由從外存上獲得前一遍的工作結果開始，完成工作後，把結果存在外存上。每遍工作完成後所佔用的存貯空間大部分被釋放。例：IBMPascal：Pass1,Pass2Link？生成可重定位代碼。所以運行時要連接成絕對指令代碼。1.2編譯過程272023-11-21編譯前端：與源語言有關，如詞法分析，語法分析，語義分析與中間代碼產生，與機器無關的優(yōu)化編譯後端：與目標機有關，與目標機有關的優(yōu)化，目標代碼產生源語言中間語言目標語言前端後端1.2編譯過程

六、編譯前端與後端282023-11-21程式設計環(huán)境編輯程式編譯程序連接程式調試工具集成化的程式設計環(huán)境1.3編譯程序與程式設計環(huán)境292023-11-21編譯程序的生成以組合語言和機器語言為工具優(yōu)點:可以針對具體的機器，充分發(fā)揮電腦的系統(tǒng)功能。生成的程式效率高。缺點:程式難讀、難寫、易出錯、難維護、生產的效率低。1.3編譯程序與程式設計環(huán)境302023-11-21高級語言書寫優(yōu)點:程式易讀、易理解、容易維護、生產的效率高。缺點:難以充分發(fā)揮電腦的系統(tǒng)功能，生成的程式效率低。1.3編譯程序與程式設計環(huán)境312023-11-21高級語言書寫利用已有的某種語言的編譯程序實現(xiàn)另一語言的編譯程序。L1語言A代碼P1:A代碼L2語言A代碼P2:L1語言L2語言A代碼P2:A代碼1.3編譯程序與程式設計環(huán)境322023-11-21

移植方法把一種機器上的編譯程序移植到另一種機器上。L語言A代碼P1:A代碼L語言B代碼P2:L語言L語言B代碼P2:A代碼L語言B代碼P2:L語言L語言B代碼P2:B代碼1.3編譯程序與程式設計環(huán)境332023-11-21L1+L2+...+Ln…L1+L2自展技術L11.3編譯程序與程式設計環(huán)境342023-11-21編譯程序自動產生編譯程序-編譯程序，編譯程序書寫系統(tǒng)LEX詞法分析程式產生器YACC語法分析程式產生器編譯程序自動產生器L語言的語法描述語義描述目標語言或機器描述L語言的編譯程序1.3編譯程序與程式設計環(huán)境352023-11-21一、參數(shù)傳遞模組之間進行參數(shù)傳遞有三種形式：1、傳地址(callbyreference)：把實在參數(shù)的地址傳遞給相應的形式參數(shù)2、傳值(callbyvalue):

調用段把實在參數(shù)的值計算出來並放在被調用段可以拿到的地方，把值帶入。3、傳名(callbyname)：過程調用的作用相當於把被調用的過程體抄到調用出現(xiàn)的地方，但把其中任一出現(xiàn)的形式參數(shù)都替換成相應的實在參數(shù)(文字替換)。1.4高級語言程式簡介362023-11-21二、存貯管理1、靜態(tài)存貯分配編譯時就安排好目標程式運行時的全部數(shù)據(jù)空間，並能確定每個資料項目目的單元地址。2、動態(tài)存貯分配如果允許遞歸、可變數(shù)據(jù)結構，則必須動態(tài)分配。①棧式：整個程式數(shù)據(jù)空間安排在一個棧中②堆式：允許自由地申請和退還空間1.4高級語言程式簡介372023-11-21

例：對於下述程式，試分析用傳名、傳值、傳地址方法傳遞參數(shù)時所得的列印結果。PROGRAMSS(input,output);VARA,B:integer;PROCEDUREP(x,y,z:integer);beginy:=y+1;z:=z+x;end;BEGINA:=2;b:=3;P(A+B,A,A);writeln(‘A=‘,A);END1.4高級語言程式簡介382023-11-21解:(1)傳名：相當於執(zhí)行A:=2;B:=3;A:=A+1;A:=A+(A+B)writeln(‘A=‘,A);所以，結果為A=9(2)傳值：把實參的值計算出來傳給形參。在調用過程P時，形參x=5;y=2;z=2出過程P時，形參x=5;y=3;z=7這並不把結果回送到主程序，所以結果為A=21.4高級語言程式簡介392023-11-21(3)傳地址：實參計算出結果，把地址送形參。設變數(shù)T=A+B(結果為5)。執(zhí)行時把T、A、A的地址(設為addr1,addr2,addr2)送給形參：x=daar1,y=addr2,z=addr2。T的地址addra即xA的地址addra即yA的地址addra即z執(zhí)行過程P即為：①y↑:=y↑+1;②z↑:=z↑+x↑所以，①為A:=A+1=3②為A:=A+T=8。因此，最後A=8.1.4高級語言程式簡介523TAB402023-11-21例：ProcedureP(x,y,z);beginy:=x+y;z:=z*z;endbeginA:=2;B:=A*2;P(B-A,A,B);printA,Bend傳地址、傳值和傳名，結果如何？1.4高級語言程式簡介第二章高級語言及其語法描述

2.1程式語言的定義2.2程式語言的語法描述422023-11-212.1程式語言的定義一個程式設計語言是一個記號系統(tǒng)，其完整的定義應包括語法和語義兩個方面語言的語法是指一組規(guī)則，用它可以形成和產生一個合適的程式上下文無關文法語法只定義什麼樣的符號序列是合法的，與這些符號的含義毫無關係PASCAL語言中：A:=B+C合乎語法規(guī)則，A:=B+不合乎語法規(guī)則闡明語法的一個工具是文法，這是形式語言理論的基本概念之一432023-11-212.2程式語言的語法描述基本概念字母表、符號、符號串、閉包等文法的定義文法的分類Chromsky對文法的分類文法和語言推導、歸約、句型、句子、語言語法分析樹和二義性442023-11-21基本概念字母表元素的非空有限集，記為。例：

={a，b，c}字母表中的元素稱為符號。例：a，b，c，字母表包含了語言中所允許出現(xiàn)的所有符號符號串符號的有窮序列。例：a,aa,ac,abc，..，無任何符號的符號串稱為空符號串，記為ε452023-11-21基本概念符號串運算符號串長度x為符號串,其長度|x|等於組成該符號串的符號個數(shù)。例：x=string，則|x|=6,|ε|=0符號串連接若x、y是定義在Σ上的符號串，則xy稱為x和y的連接，xy也是Σ上的符號串εx＝xε=x462023-11-21基本概念符號串集合的乘積令A、B為符號串集合，定義符號串集合乘積AB＝{xy|x∈A,y∈B}符號串集合的方冪符號串集合A，定義A0={ε},A1=A,A2=AA,A3=A2A,…,An＝An-1A=AAn-1，n>0符號串集合的正閉包A+=A1∪A2∪…∪An…符號串集合的自反閉包A*={ε}∪A+472023-11-21文法的直觀描述什麼是文法文法是定義或描述語法結構一組形式規(guī)則例句：Hegavemeabook.英語中的基本語法規(guī)則：<句子>

<主語><謂語><間接賓語><直接賓語><主語>

<代詞>|<名詞><謂語>

<動詞><間接賓語>

<代詞><直接賓語>

<冠詞><名詞><代詞>He|me<名詞>

book<動詞>

gave<冠詞>

a|an|the482023-11-21例句：Hegavemeabook.根據(jù)上述語法規(guī)則對例句進行分析，可推出該例句。<句子>=><主語><謂語><間接賓語><直接賓語>

=><代詞><謂語><間接賓語><直接賓語>=>He<謂語><間接賓語><直接賓語>=>He<動詞><間接賓語><直接賓語>=>Hegave<間接賓語><直接賓語>=>Hegave<代詞><直接賓語>=>Hegaveme<直接賓語>=>Hegaveme<冠詞><名詞>=>Hegavemea<名詞>=>Hegavemeabook492023-11-21用圖形化方式表示這種推導，形成一顆語法分析樹。<句子><主語><代詞><冠詞>Hea<謂語><間接賓語><直接賓語><動詞>gave<代詞>me<名詞>book語法成分（在形式語言中又稱“非終結符”）單詞符號（在形式語言中又稱“終結符號”)502023-11-21上述定義英文句子的規(guī)則可以說就是一個上下文無關文法歸納起來，一個上下文無關文法G包括四個組成部分：一組終結符號一組非終結符號一個開始符號一組產生式512023-11-21文法形式化定義文法定義成一個四元組G=(VN,VT,S,P)VN:非空有限的非終結符集；VT:非空有限的終結符集；S:開始符號；P:產生式集合。其中，VN

∩VT

=Φ，S∈VNP中產生式一般形式為:A

α|β，其中A∈VN

，α,β∈（VN∪VT

）*522023-11-21例1：文法G=(VN,VT,S,P)，其中VN={S}，VT={0，1}，P={S→0S1，S→01}。這裏，非終結符集中只含一個元素S；終結符集由兩個元素0和1組成；有兩條產生式；開始符號是S532023-11-21一個文法的幾種寫法

①G=({S,A}，{a,b}，P，S)

其中P：S→aAb

A→ab

A→aAb

A→ε

②G：S→aAb

A→ab

A→aAb

A→ε

③G[S]：A→abA→aAbA→εS→aAb

④G[S]：A→ab|aAb|εS→aAb

542023-11-21文法的分類對產生式施加不同的限制得到不同類型的文法0型（無限制文法）:G=(VN,VT,

S,

P)

規(guī)則形式：

;(VN

VT)+,(VN

VT)*且中至少含有一個非終結符1型（上下文有關）:

規(guī)則有1,其中=γ1Aγ2,=γ1δγ2;AVN,

δ

(VN

VT)+,γ1,γ2

(VN

VT)*.規(guī)則形式γ1Aγ2

γ1δγ2;

2型（上下文無關）:規(guī)則形式:Aδ

,

AVN

，δ

(VN

VT)+

3型（右線性和正規(guī)文法）:規(guī)則形式:

AB或A（右線性）A,BVN,(VT)*.552023-11-21左線性文法規(guī)則形式:

AB或A（左線性）A,BVN,(VT)*.正規(guī)文法規(guī)則形式:

AB或A其中A,BVN,VT，如果S

P，則S不能出現(xiàn)在任何產生式右邊正規(guī)文法中只能出現(xiàn)單個終結符，右線性文法中可能出現(xiàn)若干個終結符組成的串2型文法擴充Aδ,

AVN

，δ

(VN

VT)*允許有空產生式：A

不改變描述能力562023-11-21四個文法類的定義是逐漸增加限制的，因此每一種正規(guī)文法都是上下文無關的，每一種上下文無關文法都是上下文有關的，而每一種上下文有關文法都是0型文法。稱0型文法產生的語言為0型語言。上下文有關文法、上下文無關文法和正規(guī)文法產生的語言分別稱為上下文有關語言、上下文無關語言和正規(guī)語言現(xiàn)今大多數(shù)高級程式設計語言採用上下文無關文法來描述其語法已經足夠了572023-11-21文法舉例文法G=({S,A,B},{a,b,c,d,e},S,P),其中，P={SabcA|edB,AbeB,Bd}文法G是右線性文法改寫為正規(guī)文法正規(guī)文法產生式只能有兩種形式AB或A其中A,BVN,VT相應的正規(guī)文法為：G’=({S,A,B,A’,B’,C’,D’},{a,b,c,d,e},S,P’),P’={SaA’|eB’,A’bC’,C’cA,B’dB,AbD’,D’eB,Bd}582023-11-21592023-11-21S=>0A=>010A=>…=>0(10)*A=>0(10)*602023-11-21文法和語言上下文無關文法定義的語言從文法的開始符號出發(fā)，反復使用產生式，對非終結符進行替換和展開，直至推導出語言的各種句子來推導與歸約的概念推導、最左推導、最右推導、規(guī)範推導歸約、最左歸約、最右歸約、規(guī)範歸約句型、句子、語言的形式定義語法分析樹與二義性612023-11-21推導和歸約622023-11-21最左推導和最右推導規(guī)範推導最右直接推導又稱為規(guī)範直接推導，最右推導又稱為規(guī)範推導632023-11-21最右歸約和最左歸約的定義642023-11-21句型、句子、語言的定義定義2.6設S是文法G的識別符號，如果Su,則稱符號串u為文法G的句型定義2.7設S是文法G的識別符號，如果Su,uVT*,則稱符號串u為文法G的句子定義2.7設S是文法G的識別符號，文法G的語言L(G)={u|Su且uVT*},即文法的語言是文法所有句子的集合*

*

*

652023-11-21例2.9文法G=(VN,VT,S,P)，其中VN={S}，VT={0，1}，P={S→0S1，S→01}。這裏，非終結符集中只含一個元素S；終結符集由兩個元素0和1組成；有兩條產生式；開始符號是S662023-11-21直接推導示例對於例2.9的文法G，有如下直接推導示例

u=0S1,w=0011,直接推導：0S1=>0011，使用的規(guī)則：S→01，這裏γ=0，δ=1。

u=S,w=0S1，直接推導：S=>0S1使用的規(guī)則：S→0S1，這裏γ=ε，δ=ε

u=0S1,w=00S11,直接推導：0S1=>00S11，使用的規(guī)則：S→0S1，這裏γ=0，δ=1。

672023-11-21對例2.9的文法，存在直接推導序列v=0S1=>00S11=>000S111=>00001111=w，即0S1=>+00001111，也可記作0S1=>*00001111

S，0S1，000111都是例2.9文法G的句型，其中000111是G的句子682023-11-21考慮例2.9的文法G，有兩條產生式(規(guī)則)：(1)S→0S1和(2)S→01，通過對第一個產生式使用n-1次，然後使用第2個產生式一次，得到：

S=>0S1=>00S11=>…=>0n-1S1n-1=>

0n1n

可以推知L(G)中的元素僅是這樣的串(0n1n)。從而可證明L(G)={0n1n|n≥1}.692023-11-21文法等價若L(G1)=L(G2)，則稱文法G1和G2是等價的。

也就是說，如果兩個文法定義的語言一樣，則稱這兩個文法是等價的。

例如文法G[A]：

A→0R

A→01

R→A1

和例2.9的文法等價。702023-11-21證明(i*i+i)是算術運算式文法G=(VN,VT,S,P)VN={E}VT={i,+,*,(,)}S=EEi|E+E|E*E|(E)描述了算術運算式證明(i*i+i)是算術運算式如果能從文法G中推導出(i*i+i),則可證明它是算術運算式712023-11-21推導過程E=>(E)產生式：E(E)=>(E+E)產生式：EE+E=>(E*E+E)產生式：EE*E=>(i*E+E)產生式：Ei=>(i*i+E)產生式：Ei=>(i*i+i)產生式：Ei存在一個從E到(i*i+i)的推導，證明了(i*i+i)是文法G所定義的一個算術運算式722023-11-21語法分析樹我們用一張樹型結構的圖來描述一個句子的推導，這種表示稱為語法樹。語法樹的根結由文法開始符號標記。隨著推導的進行，當某個非終結符被它的候選式所替換時，此非終結符生出其下一代新結，候選式中自左至右沒有符號對應著一個新結。性質：在語法樹生長的任何時候，所有那些沒有後代的端末結自左至右的排列起來，就是一個句型。語法分析樹的生成過程：書中第31頁732023-11-21(i*i+i)的語法樹E=>(E)產生式：E(E)=>(E+E)產生式：EE+E=>(E*E+E)產生式：EE*E=>(i*E+E)產生式：Ei=>(i*i+E)產生式：Ei=>(i*i+i)產生式：EiE=>(E)產生式：E(E)=>(E*E)產生式：EE*E=>(i*E)產生式：Ei=>(i*E+E)產生式：EE+E=>(i*i+E)產生式：Ei=>(i*i+i)產生式：Ei742023-11-21文法的二義性一個文法，如果它的一個句子有兩棵或兩棵以上的語法樹，則稱此句子具有二義性。如果一個文法含有二義性的句子，則該文法具有二義性。換一個說法：如果一個文法存在某個句子對應兩棵或兩棵以上不同的語法樹，則稱該文法是二義的752023-11-21例1．注：文法的二義性是不可判定的，但可以通過約定加以改造。例2．文法G1：A→AN|NN→0|1|…|9

則L(G1)為無符號整數(shù)例3．文法G2：B→aBb|ab,求L(G2)

解：B=>aBb=>aaBbb=>aaaBbbb=>……

即，∴L(G2)={anbn|n≥1}762023-11-21例題構造文法生成下列語言(1){an|n≥1}SaA|

AaA|

或

SaS|

(2){an|n≥0}SaS|

772023-11-21(3){anb2m-1|n,m≥1}SABAaA|aBbbB|b(4){anbmck|n,m,k≥0}SABCAaA|

BbB|

CcC|

SaABAaA|

BbbB|b782023-11-21習題2.6文法G的產生式

P={NND|D,D0|1|2|3|4|5|6|7}

寫出下列符號串的最左推導和最右推導

(1)3274;(2)651733274的最左推導

N=>ND=>NND=>NNND=>DNND=>3NND=>3DND=>32ND=>32DD=>327D=>32743274的最右推導

N=>ND=>N4=>ND4=>N74=>ND74=>N274=>D274=>3274792023-11-21習題判定下列文法是否是歧義的

(1)文法的產生式如下

P={SAB,Aa|ab,Bc|bc}

解答：該文法是歧義的，因為存在一個句子abc，它對應兩棵不同的語法樹。（也可以說：存在一個句子abc，它有兩種不同形式的最左推導，即S=>AB=>aB=>abc和S=>AB=>abB=>abc）第三章詞法分析3.1詞法分析概述3.2詞法分析程式的設計3.3正規(guī)式與有限自動機3.4詞法分析程式的實現(xiàn)3.5詞法分析器的自動生成812023-11-213.1詞法分析概述一、詞法分析程式的任務二、詞法分析程式的功能三、詞法分析程式的安排四、詞法分析程式的實現(xiàn)方式五、詞法分析程式的輸出形式822023-11-21詞法分析程式詞法分析是編譯過程中的一個階段，在語法分析前進行，也可以和語法分析結合在一起作為一遍。輸入：根源程式字串輸出：等價的屬性字序列（內部表示形式）3.1詞法分析概述832023-11-21一、詞法分析程式的任務從左至右逐個字元地掃描根源程式，產生一個個單詞符號。把作為字元的根源程式改造為單詞符號串組成的中間程式，執(zhí)行詞法分析任務的程式稱為詞法分析器或稱掃描器。3.1詞法分析概述842023-11-21二、詞法分析程式的功能詞法分析程式主要執(zhí)行以下功能：讀入根源程式字串，識別開具有獨立含義的最小語法單位——單詞（符號）；把單詞變換成長度統(tǒng)一的且為定長的屬性字；其他功能：濾掉空格，跳過注釋、換行符某些預加工處理3.1詞法分析概述852023-11-21三、詞法分析程式的安排常常把詞法分析程式作為獨立的一遍或作為被語法分析程式所調用的副程式。1、作為獨立的一遍：語法分析前進行詞法分析，把單詞符號串形成中間檔存貯。3.1詞法分析概述862023-11-21三、詞法分析程式的安排2、作為被語法分析器詞用的副程式：

3.1詞法分析概述872023-11-21相對獨立方式：把詞法分析程式作為語法分析程式的一個獨立副程式。語法分析程式需要新符號時調用這個副程式。完全獨立方式：詞法分析程式作為單獨一趟來實現(xiàn)。詞法分析程式讀入整個根源程式，它的輸出作為語法分析程式的輸入。四、詞法分析程式的實現(xiàn)方式3.1詞法分析概述882023-11-21相對獨立方式當採用遞歸下降分析等技術實現(xiàn)一趟編譯程序時常採用這種方式。根源程式詞法分析程式語法分析程式Tokengettoken….四、詞法分析程式的實現(xiàn)方式3.1詞法分析概述892023-11-21完全獨立方式採用詞法分析工作完全獨立的原因：簡化設計，降低語法分析的複雜性提高編譯效率增加編譯系統(tǒng)的可移植性根源程式詞法分析程式語法分析程式屬性字序列….四、詞法分析程式的實現(xiàn)方式3.1詞法分析概述902023-11-21單詞--是程式語言的基本語法符號。如：基本字、識別字、常數(shù)、運算符、界符等。詞法分析器中單詞的輸出形式：（單詞類別、單詞內部碼值）五、詞法分析程式的輸出形式3.1詞法分析概述912023-11-21詞法分析程式輸出的單詞符號通常用二元式表示：（單詞種別，單詞自身的值）單詞種別：表示單詞種類，常用整數(shù)編碼，它是語法分析需要的單詞自身的值：是編譯中其他階段所需要的資訊如果一個種別只含一個單詞符號，那麼該單詞符號的種別編碼就完全代表它自身的值。如果一個種別含有多個單詞符號，那麼還應給出該單詞符號的自身值：識別字自身值是識別字自身的字串；常數(shù)自身值是常數(shù)的二進位數(shù)值。五、詞法分析程式的輸出形式3.1詞法分析概述922023-11-21語言的單詞符號單詞符號是程式語言的基本語法單位，一般分為下麵5種：關鍵字（基本字）：（個數(shù)確定，可全體編為一類，也可一字一類)識別字：（個數(shù)不確定，作為一類）常數(shù)：各種類型的常數(shù)。(個數(shù)不確定，按類型分類)運算符：如+、-、*、/、<等。(個數(shù)確定，一符一類)界符：如，、；、（、）、:等。(個數(shù)確定,一符一類)注意：一種語言的單詞如何分類、怎樣編碼，主要取決於技術上的方便。五、詞法分析程式的輸出形式3.1詞法分析概述932023-11-21例：若分類表為：試分析輸入串：IFa1>0 THENb1:=c1*d1ELSEb1:=5

經詞法分析後的輸出。五、詞法分析程式的輸出形式3.1詞法分析概述942023-11-21解：輸出的單詞串為：五、詞法分析程式的輸出形式3.1詞法分析概述952023-11-21一、狀態(tài)轉換圖狀態(tài)轉換圖是一張有限方向圖。用結點代表狀態(tài)，狀態(tài)之間用箭弧連接，箭弧上的標記（字元）代表在射出結狀態(tài)下可能出現(xiàn)的輸入字元或字元類。一個狀態(tài)轉換圖只包含有限個狀態(tài)，有一個初態(tài)，終態(tài)用雙圈表示。一個狀態(tài)轉換圖可識別一定的字串。

SIE字母數(shù)字字母狀態(tài)都是非終結符號S：開始狀態(tài)E：終止狀態(tài)，用雙圈表示I：識別字狀態(tài)3.2詞法分析程式的設計例1：962023-11-21一、狀態(tài)轉換圖例2：例3：972023-11-21方法：每個結點對應一段程式，前面狀態(tài)結的程式調用其後繼結點的程式。例1：二、狀態(tài)轉換圖的實現(xiàn)PROCEDUREProc0;Getchar;casecharof‘A’…‘Z’:proc1;‘0’…‘9’:proc2;otherwiseerror;endofcase;982023-11-21為了描述方便，引入一些標準過程（函數(shù)）與變數(shù):1.全程字元變數(shù)Char：存放最新讀入的根源程式字元；2.字串TOKEN：存放構成單詞符號的字串；3.過程GETChar：讀入一個根源程式字元，放入Char中，搜索指針前移；4.過程GETNBC：反復調用GETChar，直接讀入的Char<>’’為止；5.過程CONCAT：把Char中字元連到TOKEN末尾去；6.函數(shù)Letter/digit：判別Char中是否為字母/數(shù)字；7.過程Return(c,val);8.過程Retract：搜索器指針回拔一個字元。

二、狀態(tài)轉換圖的實現(xiàn)992023-11-21例2：PROCEDUREPro0;BEGINGetchar;IFcharIN[‘A’..‘Z’]thenpro1elseerror;END;Procedurepro1;begingetchar;whilecharIN[‘A’..‘Z’,‘o’..‘9’]DObeginconcat;getchar;End;pro2;End;procedurepro2;beginretract;return(101,TOKEN);end;1002023-11-21一、基本概念二、確定有窮狀態(tài)自動機（DFA）三、非確定有窮狀態(tài)自動機（NFA）四、NFA和DFA的轉換五、正規(guī)式和有限自動機的等價性六、DFA的化簡3.3正規(guī)式與有限自動機1012023-11-21一、基本概念1.字母表Σ：元素的非空有限集合。如Σ={‘A’,‘B’,‘O’}2.字元：字母表Σ的一個元素稱為一個字元（符號）3.Σ上的字：

Σ上字元的有窮序列；例：Σ={a,b,c}4.空字ε：不含任何字元的字5.字的長度：|α|6.Σ上字的全體：Σ*7.字的連接：字α與字β的連接記為αβ3.3正規(guī)式與有限自動機1022023-11-21一、基本概念8.字的方冪：字α的n次連接稱為α的n次方冪,記為,特別地=ε9.字的集合A與B的乘積：記作,其中10.Σ*子集的方冪：

Ao={ε},A1=A,…,11.Σ*子集的正則閉包：12.Σ*子集的閉包：3.3正規(guī)式與有限自動機1032023-11-21正規(guī)式與正規(guī)集正規(guī)集是字母表Σ上的一個特殊字集，通常我們借助正規(guī)式來描述它。關於正規(guī)式與正規(guī)集的定義是遞歸的。1.ε和φ都是Σ上的正規(guī)式，它們所表示的正規(guī)集分別為{ε}和φ2.任何a∈Σ,a是Σ上的正規(guī)式，它所表示的正規(guī)式為{a}3.假定u和v是正規(guī)式，它們所代表的正規(guī)集分別是L(u)和L(v)，則u|v,uv,u*都是Σ上的正規(guī)式，它們所表示的正規(guī)集分別為L(u)∪L(v),L(u)L(v),L(u)*僅由有限次使用上述三步而定義的運算式才是Σ上的正規(guī)式，僅由這些正規(guī)式所表示的字集才是Σ上的正規(guī)集1042023-11-21正規(guī)式與正規(guī)集優(yōu)先順序遞增：

|(或)，·（連接），*,（正規(guī)式） ∪,∩,*’,（正規(guī)集）例1.Σ={0,1}，則正規(guī)式有0,1,ε,φ,1*,|0|,…，正規(guī)集有{0},{1},{ε},φ,{1}*,…若兩個正規(guī)式所表示的正規(guī)集相同，則認為二者等價1052023-11-21正規(guī)式的性質：1．交換律：U|V=V|U

證：L(u|v)=L(u)∪L(v)=L(v)∪L(u)=L(v|u)

因此，u|v=v|u 2．結合律：(u|v)|w=u|(v|w),(uv)w=u(vw)3．分配律：u(v|w)=uv|uw,(u|v)w=uw|vw4． εu=uε=u

證：L(εu)=L(ε)L(u)=L(u)0L(u)=L(u)

1062023-11-21二、確定型有窮狀態(tài)自動機一個確定的有窮自動機（DFA）D是一個五元組：D=（K，Σ，M，S，F(xiàn)）其中

K：有窮非空的狀態(tài)集合；Σ：有窮非空的輸入符號字母表；

M：轉換函數(shù)，是在K×Σ→K上的映像，即，如M(ki,a)=kj,(ki∈K,kj∈K)就意味著，當前狀態(tài)為ki，輸入符為a時，將轉換為下一個狀態(tài)kj，我們把kj稱作ki的一個後繼狀態(tài)；

S∈K是唯一的一個初態(tài)；

F

K是非空的終態(tài)集合。1072023-11-21例1．DFAM=({0,1,2},{a,b},δ,0,{2})，其中δ(s,a)=S,δ(s,b)=2,s=0,1,2注：一個DFA可表示為一個狀態(tài)轉換矩陣，行表示狀態(tài)，列表示輸入字元，矩陣元素M[s,a]的值為δ(s,a)。例2．二、確定型有窮狀態(tài)自動機1082023-11-21一個DFAM也可用一張狀態(tài)轉換圖表示，DFA的每個狀態(tài)對於狀態(tài)轉換圖的一個接點，圖中箭弧上的標記為輸入字元，若δ(s,a)=S’，則從狀態(tài)s畫一條箭弧到S’，弧上標記為a。對Σ*中的任何字α，若存在一條從初態(tài)到某一終態(tài)的道路，且這條路上所有弧上標記連接成的字等於α，則稱α可為DFAM所識別，或稱DFAM可讀出（或接受、識別）字α。DFAM識別的字的全體記為L(M)。二、確定型有窮狀態(tài)自動機1092023-11-21如果一個DFAM的輸入字母表為∑，則我們也稱M是∑上的一個DFA?？梢宰C明：∑上的一個子集是正規(guī)的，當且僅當存在∑上的DFAM，使得V=L（M）。DFA的確定性表現(xiàn)在映射δ：S×Σ→S是一個單值函數(shù)。也就是說，對任何狀態(tài)s∈S和輸入符號a∈Σ，δ(s,a)唯一地確定了下一狀態(tài)。特別地，若DFAM的初態(tài)同時又是終態(tài)，改DFAM可識別空字ε。顯然，若DFAM中字母表Σ含n個字母，則任何一個狀態(tài)頂多只有n條發(fā)出弧。

二、確定型有窮狀態(tài)自動機1102023-11-21從狀態(tài)轉換圖構造有窮狀態(tài)自動機例如：從下麵狀態(tài)圖構造DFADFAD=（{S，Z，A，B}，{a，b}，M，S，{Z}）其中M定義為：

M（S，a）=AM（S，b）=BM（A，a）=ZM（A，b）=BM（B，a）=AM（B，b）=Z M（Z，a）=Z abSABabZbaa1112023-11-21運行DFA與識別一個字串擴充的映像M定義：

M(R,ε)=RM(R,Tt)=M(M(R,T),t)，其中t∈Σ*，

T∈Σ以上兩個式子的含義是什麼？定義：對於某DFAD=（K,Σ,M,S,F），如果M(S，t)=P,P∈F，則稱符號串t可被DFAD所接受。運行一個DFA的過程：識別一個符號串是否被接受1122023-11-21舉例如前例：DFAD=（{S，Z，A，B}，{a，b}，M，S，{Z}）

M（S，a）=AM（S，b）=BM（A，a）=ZM（A，b）=BM（B，a）=AM（B，b）=Z M（Z，a）=Z

則：M(S,ababaa)=M(M(S,a),babaa)=M(A,babaa)=M(M(A,b),abaa)=M(B,abaa)=M(A,baa)=M(B,aa)=M(A,a)=Z1132023-11-21正則集正則集：L(D)，是一個DFA接受的字串集合正則語言與正則集：L(G)=L(D)最小狀態(tài)自動機：狀態(tài)個數(shù)最少，唯一如何減少自動機的狀態(tài)數(shù)而不改變自動機所接受的語言呢？1142023-11-21如何在電腦內表示映像？映像M：含義？映像在電腦內的表示法：矩陣表示法表結構表示法1152023-11-21DFA的矩陣表示法字元狀態(tài)abSABabZbaa矩陣行代表狀態(tài)，列代表輸入字元，矩陣元素是映像得到的新狀態(tài)。1162023-11-21引入M(R,T)是K×Σ到K的單值函數(shù)，即唯一確定下一狀態(tài)如果在當前狀態(tài)下，同一個輸入字元確定的下一狀態(tài)不止一個呢？如V::=UTW::=UTUWVTTabSABabZbaaaa例如：文法G3.2:Z::=Za|Aa|BbA::=Ba|Za|aB::=Ab|Ba|b三、非確定有窮狀態(tài)自動機1172023-11-21一個非確定的有窮自動機（NFA）D是一個五元組：N=（K，Σ，M，S，F(xiàn)）其中K：有窮非空的狀態(tài)集合；Σ：有窮非空的輸入字母表；M：轉換函數(shù)，是在K×Σ到K的子集所組成集合的映像，M(R,T)={Q1,Q2,….Qn}S

K是非空的初態(tài)集合；F

K是非空的終態(tài)集合.三、非確定有窮狀態(tài)自動機1182023-11-21DFA與NFA的區(qū)別DFANFA開始狀態(tài)唯一一個或多個映像單個狀態(tài)狀態(tài)集合1192023-11-21舉例前述文法G3.2對應的自動機NFAN=({S,A,B,Z},{a,b},M,{S},{Z})其中M：M(S,a)={A}M(S,b)={B}M(A,a)={Z}M(A,b)={B}M(B,a)={A,B}M(B,b)={Z}M(Z,a)={A,Z}abSABabZbaaaa1202023-11-21擴充映像定義：

M(R,ε)={R}R為任意的狀態(tài)

M(R,Tt)=M(Q1,t)∪M(Q2,t)∪…∪M(Qn,t)

其中t∈Σ*，T∈Σ，M(R,T)={Q1,Q2,….Qn}M(R,Tt)=M({Q1,Q2,…,Qn},t)=∪M(Qi,t)1212023-11-21舉例(字串被NFA所接受)對於輸入字串babbabb，運行G3.2的NFA步驟當前狀態(tài)輸入的其餘部分可能的後繼選擇1SbabbabbBB2BabbabbA,BA3AbbabbBB4BbabbZZ5ZabbA,ZA6AbbBB7BbZZ1222023-11-211．Σ上NFAM所能識別的字的全體是Σ上的一個正規(guī)集證明：設轉換圖中每條弧上可用一個正規(guī)式作標記，讓NFAM的轉換圖中加進兩節(jié)點X和Y，形成新的NFAM’，從X畫ε弧指向原NFAM的所有初態(tài)，從原NFAM的所有終態(tài)畫ε弧指向Y，顯然L(M)=L(M’)

然後，對NFAM’消結，直至只剩下X、Y兩個結點為止，符上標記為一正規(guī)式。所以，NFAM’識別的為一正規(guī)式；NFAM識別的是一正規(guī)集。

五、正規(guī)式和有限自動機的等價性X1232023-11-21消結規(guī)則為五、正規(guī)式和有限自動機的等價性1242023-11-21例1.消結點⑤五、正規(guī)式和有限自動機的等價性例2.消結點①1252023-11-212．對於Σ上的每個正規(guī)集V，存在一個Σ上的DFAM，使得V=L(M)。證明：第一步，用替代辦法構造一個NFAM’，使V=L(M’)，因為正規(guī)集V可用正規(guī)式u來描述，而u由一系列單個字元連接而成，故可用下述方法分解之：五、正規(guī)式和有限自動機的等價性SZe1e2SZe1e2SZe1|e2SZ{e}SZ

SZe1e2e1262023-11-21具體方法：構造如下轉換圖：逐步分解，便可得到一個NFAM’，有L(u)=V=L(M’)。例1．第二步，把NFAM’確定化為DFAM，得證。五、正規(guī)式和有限自動機的等價性1272023-11-21舉例例：正則運算式(A|B){A|B|0|1}的轉換系統(tǒng)的構造過程如下：SZ(A|B){A|B|0|1}SZ(A|B){A|B|0|1}SZAB

A|B|0|1SZAB

10AB1282023-11-21概念1.假設I是NFAM’的狀態(tài)集的一個子集，我們定義ε-CLOSURE(I)為（I的ε-閉包）。（1）若S∈I，則S∈ε-CLOSURE(I)（2）若S∈I，則從s出發(fā)經過任意條ε弧而達到的狀態(tài)s’，有s’∈ε-CLOSURE(I)例1.五、正規(guī)式和有限自動機的等價性若I={1,3}，則ε-CLOSURE(I)={1,3,2,8}1292023-11-21概念2.假定I是M’的狀態(tài)子集，a是Σ中的字元，定義Ia=ε-CLOSURE(J),其中J是I中任意狀態(tài)出發(fā)（跳過前面任意多條ε?。?，經過一條a弧而能達到的狀態(tài)結的全體。例2．同例1DFA，Ia={5,6,2}利用概念1和概念2，便可把NFA確定化。五、正規(guī)式和有限自動機的等價性1302023-11-21五、正規(guī)式和有限自動機的等價性令，構造一張如下的表，此表第0列為狀態(tài)子集I，第1至m列分別為狀態(tài)子集，設第一行第0列為ε-CLOSURE(X),，其中X為NFAM’的初態(tài)，求出第一個的，如果某個Iai(i=1,…,m)未曾在第0列中列出，則把Iai補入狀態(tài)子集集合I中，即列於第0列新的一行。重複上述各步，直至所有行的Iai(i=1,…,m)均在第0列I中出現(xiàn)過為止。這種迴圈必將在有限步內中止。（因為S是有限狀態(tài)集，所以S中狀態(tài)的組合數(shù)也是有限的）

1312023-11-21顯然，這張表可以看成一個狀態(tài)轉換表，也就是說可把I中每個子集看成一個狀態(tài)，而狀態(tài)轉換表唯一地刻劃了一個DFAM，其初態(tài)為該表的第1行第0列，含有原NFAM’終態(tài)的子集為新的終態(tài)。（證畢）推論：一個子集是正規(guī)的，當且僅當它可由一個DFA（或NFA）所識別。五、正規(guī)式和有限自動機的等價性1322023-11-21例：設計一個DFAM，它識別二進位偶數(shù)（不以0開頭的無符號數(shù)）解：1． 寫出正規(guī)式1（1|0）*02． 畫出NFAM’

細化為：3.確定化為DFAM五、正規(guī)式和有限自動機的等價性1332023-11-21五、正規(guī)式和有限自動機的等價性或：1342023-11-21字串W把狀態(tài)P和狀態(tài)Q區(qū)別開：等價狀態(tài)：無法區(qū)別開的兩個狀態(tài)基本思想：把狀態(tài)集劃分成互不相交的子集，使子集中的狀態(tài)是等價的化簡DFA的演算法步驟：劃分狀態(tài)集合併狀態(tài):取每組狀態(tài)中的代表狀態(tài)，刪去其他等價狀態(tài)若有死狀態(tài)或不可達狀態(tài)，則把它們刪去。死狀態(tài)：無法達到終止狀態(tài)的非終止狀態(tài)不可達狀態(tài)：不能從開始狀態(tài)達到它的那些狀態(tài)六、DFA的化簡1352023-11-21舉例劃分狀態(tài)集為{4}和{0,1,2,3}對於{0,1,2,3}和輸入字元a和b:M(0,a)={1}M(1,a)={1}M(2,a)={1}M(3,a)={1}M(0,b)={2}M(1,b)={3}M(2,b)={2}M(3,b)={4}只有狀態(tài)3在輸入為b時映像的後繼狀態(tài)不在{0,1,2,3}中，因此該狀態(tài)集劃分為{3}和{0,1,2}對於{0,1,2}:狀態(tài)1在輸入為b時的後繼狀態(tài)不在{0,1,2}中，因此劃分為{1}和{0,2}02314bbbbbaaaaa對於{0,2}:對於相同輸入字元，該子集中每一狀態(tài)映像得到的後繼狀態(tài)都相同，因此不再可劃分最後劃分為：

{4}{3}{1}{0,2}六、DFA的化簡1362023-11-21舉例（續(xù)1）對於劃分結果{4},{3},{1},{0,2}，把{0,2}合併為一個狀態(tài)，其狀態(tài)轉換圖如圖：0213aaaabbb02314bbbbbaaaaab六、DFA的化簡1372023-11-21根源程式的輸入在內存開闢緩衝區(qū)，將程式文本放進該緩衝區(qū)預處理：刪除無用字元等詞法分析程式對緩衝區(qū)掃描時，設置兩個指示器，一個指向當前正在識別的單詞的開始位置，稱為起始指針；另一個用於向前搜索，以尋找單詞的終點，稱為掃描指針。起始指針搜索指針3.4詞法分析程式的實現(xiàn)1382023-11-21超前搜索詞法分析程式在讀取單詞時，為了判斷是否已讀入整個單詞的全部字元，常採取向前多讀取字元並通過讀取的字元來判別，即所謂超前搜索技術。3.4詞法分析程式的實現(xiàn)1392023-11-21關鍵字的識別與查表演算法對於關鍵字，先把它們當成識別字，然後去查關鍵字表。若在表中查到，則為關鍵字，獲取相應的類別碼；否則，認為是識別字。查找演算法：線性查找折半查找Hash函數(shù)3.4詞法分析程式的實現(xiàn)1402023-11-21使用狀態(tài)圖設計詞法分析程式多數(shù)語言的詞法規(guī)則可用正則文法和正則運算式來描述。正則文法或正則運算式定義的語言都可以被狀態(tài)圖識別。使用狀態(tài)圖設計詞法分析程式的步驟如下：對程式設計語言的單詞按類構造相應的狀態(tài)圖。（這裏把關鍵字與識別字作為一類）合併各類單詞的狀態(tài)圖，增加一個出錯處理終態(tài)，構成一個識別該語言所有單詞的狀態(tài)轉換圖對狀態(tài)圖的每一個終點編一段相應的副程式。3.4詞法分析程式的實現(xiàn)1412023-11-21201字母字母|數(shù)字其他3456數(shù)字數(shù)字其他+-78*/9101113<=>:;1617其他13=舉例1422023-11-21本節(jié)討論：用正規(guī)式描述單詞符號，並研究如何從正規(guī)產生識別這些單詞符號的詞法分析程式。3.5詞法分析器的自動生成1432023-11-21一、LEX語言一個LEX語言程式經過編譯後得到的結果程式，其作用相當於一個DFA，可用來識別和產生單詞也就是說其功能即為一個詞法分析器。1442023-11-21一個LEX根源程式包括兩部分：輔助定義式和識別規(guī)則1、輔助定義式

D1→R1

Dn→Rn

其中Ri為正規(guī)式，只允許出現(xiàn)∑上字元D1,…,Di-1；Di為這個正規(guī)式Ri的簡名例1．Letter→A|B|…|ZDigit→0|1|…|9Id→Letter(Letter|Digit)*...1452023-11-212.識別規(guī)則

P1{A1}...Pm{Am}其中，Pi稱為詞形，為正規(guī)式(∑∪{D1,…,Dm})Ai稱為詞形Pi的動作（程式）顯然：一個LEX根源程式產生的詞法分析器只能識別形如Pi的單詞。1462023-11-21二、LEX的實現(xiàn)LEX編譯程序的目的是把一個LEX程式改造為一個詞法分析器L，這個詞法分析器L將象自動機一樣工作。1．詞法分析器L的工作方法

L逐個地掃描輸入串的每個字元，尋找一個最大的子串匹配某個Pi（即：當輸入串已匹配某個詞形時，並不立即返回，而是沿著此道路繼續(xù)前進，直至不能前進為止，逐個字元地逆向搜索，找到第一個逆向搜索到的匹配詞形），把這個子串放入TOKEN中，然後L調用動作副程式Ai（如果有二義，前面位置的詞形優(yōu)先），當Ai工作完後，L就把所得的單詞符號（種別，內部碼值）返回語法分析程式。下次調用L，接著往下分析。1472023-11-212.LEX程式的編譯過程（1）對每條識別規(guī)則Pi構造一個NFAMi;

（2）引入一個新的初態(tài)X，從X畫ε弧到每一個NFAMi的初態(tài)，構造出一個NFAM;

（3）把NFAM改造為DFAM’，這個DFAM’就是能識別所有形如Pi詞形的詞法分析器。這樣我們就可用程式實現(xiàn)之，即編制出詞法分析程式L。

1482023-11-21實例1編寫程式，實現(xiàn)下述LEX根源程式的功能輔助定義：(1)digit→0|1|...|9(2)letter→A|B|...|Z

識別規(guī)則:(1)digit(digit)*{Return(4,val)}(2)letter(letter|digit)*

{Return(5，Token)}(3)*{Return(6,_)}(4)**{Return(7,_)}1492023-11-21解：1、各識別規(guī)則的NFA為：1502023-11-212、加入新初態(tài)X，構成NFAM整體1512023-11-213、確定化為DFAM’1522023-11-214、寫出實現(xiàn)其功能的程式PROGRAMLEX(input,output)BEGINTOKEN:=’’;getchar;CASEcharOF‘0’..’9’:[whilecharIN[‘0’..’9’]DOBEGINTOKEN:=TOKEN+char;getcharEND;retract;IFVAL(token,value)THENreturn(4,value)];‘A’..’Z’:[whilecharIN[‘A’..’Z’,’0’..’9’]DOBEGINTOKEN:=TOKEN+char;getcharEND;retract;Return(5,token)];‘*’:[getchar;IFchar=’*’THENReturn(7,-)ELSE[retract;Return(6,-)]ELSE:ERROR;END{ofcase};END;1532023-11-21實例2∑={a,b},LEX程式為a{written(‘word=1’)}abb{written(‘word=2’)}a*bb*{written(‘word=3’)}

寫出其功能的類pascal程式。1542023-11-21解：1、構造上述三條識別規(guī)則的NFA，並連成整體1552023-11-212、確定化步驟IIaIb0{x,1,2,3}{R1，21,3}{R3}1{R1，21,3}{3}{22,R3}2{R3}{R3}3{3}{3}{R3}4{22,R3}{R2,R3}5{R2,R3}{R3}1562023-11-21注意：1.最長匹配2.前者優(yōu)先PROCEDUREproc0;getchar;IFchar=‘a’thenproc1;IFchar=‘b’thenproc2;

其他出錯PROCEDUREproc1;IFeof（）thenreturn(1,-)IFchar=‘a’thenproc3;IFchar=‘b’thenproc4;

其他出錯1572023-11-21PROCEDUREproc3;whilechar=‘a’Dogetchar;IFchar