編譯原理復(fù)習(xí)整理(每頁15張)

第二章詞法分析記號的識別-有限自動(dòng)機(jī)（FA）第二章詞法分析記號的識別-有限自動(dòng)機(jī)（FA）定義2.1:語言E是有限字母表E上有限長度字符串的集合。字母表：是組成字符串的所有字符的集合。換句話說，字符串中的所有字符取自字母表。詞法分析器是編譯器與源程序打交道的唯一階段，可以被認(rèn)為是編譯器的預(yù)處理階段。詞法的雙重含義：?規(guī)定單詞形成的規(guī)則，也被稱為構(gòu)詞規(guī)則或詞法規(guī)則。?根據(jù)構(gòu)詞規(guī)則識別輸入序列（識別出合法的單詞和指出非法的輸入序列），也被稱為詞法分析。作用濾掉源程序中的無用成分；處理與具體操作系統(tǒng)或機(jī)器有關(guān)的輸入；識別記號并交給語法分析器；調(diào)用符號表管理器和出錯(cuò)處理器進(jìn)彳亍相關(guān)處理。

模式的描述一正規(guī)式記號的識別一有限自動(dòng)機(jī)（確定、不確定）不確定的有限自動(dòng)機(jī)定義2.4NFA是一個(gè)五元組（5-tuple）：M=（S,E,move,s0,F），其中（1） S是有限個(gè)狀態(tài)（state）的集合；（2） E是有限個(gè)輸入字符（包括e）的集合；（3） move是一個(gè)狀態(tài)轉(zhuǎn)移函數(shù)，move（si,ch）=sj表示，當(dāng)前狀態(tài)si下若遇到輸入字符ch，則轉(zhuǎn)移到狀態(tài)sj；（4） sO是唯一的初態(tài)（也稱開始狀態(tài)）；（5） F是終態(tài)集（也稱接受狀態(tài)集），它是S的子集，包含了—所有的終態(tài)。考試說明考試時(shí)間：第14周考試類型：一?選擇題（20分，10題）二?填空題（10分，5空）三.判斷題（每小題1分，共10分）四?名詞解釋（20分，4題）五?簡答題（20分，4題）六?計(jì)算題（20分，3題）考試范圍：1—5章講過的內(nèi)容第二章詞法分析問題：輸入？輸出？如何由輸入得到輸出？ 源程序-〉記號流規(guī)則如何描述？ 正規(guī)式如何根據(jù)規(guī)則識別出記號？ 限自動(dòng)機(jī)二、記號的識別一有限自動(dòng)機(jī)（FA）2.不確定有限自動(dòng)機(jī)的表示一一定義表示、狀態(tài)轉(zhuǎn)換圖、狀態(tài)轉(zhuǎn)換矩陣；例2.7識別正規(guī)式（a|b）*bb所描述正規(guī)集的NFA的三種表示形式分別如下。（其中轉(zhuǎn)換矩陣表示中0為初態(tài)，3為終態(tài)）按定義：S={0,1,2,3},2={a,b}move={move(0,a)=0,move(0,a)=1,move(0,b)=0,move(1,b)=2,move(2,b)=3}狀5轉(zhuǎn)換矩陣1abPWTT{U}T—{2}T—{3}■3s0=0,F={3}狀態(tài)轉(zhuǎn)換圖課程內(nèi)容一、 引言二、 詞法分析三、 語法分析四、 語法制導(dǎo)翻譯生成中間代碼五、 運(yùn)行環(huán)境注意：明確每章的任務(wù)是什么？解決具體問題的方法有哪些？第二章詞法分析主要內(nèi)容：模式的形式化描述-正規(guī)式記號的識別-有限自動(dòng)機(jī)（NFA,DFA）詞法分析器的構(gòu)造-從正規(guī)式到DFA直到轉(zhuǎn)換圖：0a1b2b3move={move(0,a)=0,move(0,a)=1move(0,b)=0,move(1,b)=2,b二、記號的識別一有限自動(dòng)機(jī)（FA）W3.如何用NFA識別記號?方法：對字符串，從初態(tài)開始，反復(fù)試探所有路徑直到到達(dá)終態(tài)，或者到達(dá)不了終態(tài)。例如：對于字符串a(chǎn)bb,有定義：move（0,a）=1,move（1,b）=2,move（2,b）=3轉(zhuǎn)換矩陣：m[0,a]二{0,1},m[1,b]=2,m[2,b]=30丄2~3第一章引言<1>語言的翻譯不同的翻譯形式：匯編、編譯、轉(zhuǎn)換（預(yù)編譯）、逆向翻譯翻譯方法：—r-—編譯器L目標(biāo)程序輸入數(shù)據(jù)曰標(biāo)程序輸出 ?源程序輸入數(shù)據(jù)解釋器輸出一、模式的形式化描述 正規(guī)式1.正規(guī)式與正規(guī)集：P20定義2.2令藝是一個(gè)有限字母表，則藝上的正規(guī)式及其表示的集合遞歸定義如下：e是正規(guī)式，它表示集合L（e）={e}若a是遲上的字符，則a是正規(guī)式，它表示集合L（a）={a}若正規(guī)式r和s分別表示集合L（r）和L（s）,貝卩（a） r|s是正規(guī)式，表示集合L（r）UL（s）,（b） rs是正規(guī)式，表示集合L（r）L（s）,（c） r*是正規(guī)式，表示集合（L（r））*,（d） （r）是正規(guī)式，表示的集合仍然是L（r）。（加括弧改變優(yōu)先級、結(jié)合性）可用正規(guī)式描述的語言稱為正規(guī)語言或正規(guī)集。 ■問題關(guān)鍵：如何用正規(guī)式去描述語言？NFA識別記號的特點(diǎn)：是它的不確定性，即在當(dāng)前狀態(tài)下對同一字符有多于一個(gè)的下一狀態(tài)轉(zhuǎn)移。會(huì)導(dǎo)致什么問題？NFA識別記號存在的問題只有嘗試了全部可能的路徑，才能確定一個(gè)輸入序列不被接受，而這些路徑的條數(shù)隨著路徑長度的增長成指數(shù)增長。識別過程中需要進(jìn)行大量回溯，時(shí)間復(fù)雜度升高且算法趨于復(fù)雜。解決此問題的方法？——DFA目標(biāo)代碼目標(biāo)代碼一、模式的形式化描述 正規(guī)式記號的說明一一用正規(guī)式對模式進(jìn)行形式化描述：?如何用正規(guī)式描述程序設(shè)計(jì)語言中常見的記號，如標(biāo)識符、數(shù)字、運(yùn)算符和分隔符等記號=正規(guī)式?針對一種具體的程序設(shè)計(jì)語言明確語言的組成：關(guān)鍵孚、標(biāo)識符、孚面量、特殊符號等針對每一個(gè)符號類用正規(guī)式描述舉例下一個(gè)問題：如何根據(jù)規(guī)則識別出記號?

二、記號的識別一有限自動(dòng)機(jī)（FA）3.DFA定義2一5DFA是NFA的一個(gè)特例，其中：（1） 沒有狀態(tài)具有￡?duì)顟B(tài)轉(zhuǎn)移（e-transition）,即狀態(tài)轉(zhuǎn)換圖中沒有標(biāo)記￡的邊；（2） 對每個(gè)狀態(tài)s和每個(gè)字符a,最多有一個(gè)下一狀態(tài)。與NFA相比，DFA的特征（確定性），因此識別過程中就不需要回溯。二、記號的識別-有限自動(dòng)機(jī)（FA）4.模擬DFA可以將在DFA上識別輸入序列的過程形式化為算法，該算法被稱為模擬器（模擬DFA的行為）或驅(qū)動(dòng)器（用DFA的數(shù)據(jù)驅(qū)動(dòng)分析動(dòng)作）。算法（P26算法2.1）與DFA一起，即構(gòu)成識別記號的詞法分析器的核心。例題因此問題轉(zhuǎn)換為：如何為語言構(gòu)造DFA?(2)構(gòu)造N的最小DFAD；1.由子集法構(gòu)造DFA：集合閉包({0}) ={0}e一閉包(smove(A,a))={0,1}e—閉包(smove(A,b))={1}e—閉包(smove(B,a))={0,1}e一閉包(smove(B,b))={1}e_閉包(smove(C,a))={0}DFA的圖形表示(右圖)：aA（初態(tài)，終態(tài)）B（終態(tài)）CC<2>有關(guān)推導(dǎo)的基本概念CFG產(chǎn)生語言的基本方法一推導(dǎo)：從文法的開始符號開始，反復(fù)地用產(chǎn)生式的右部替換句型中的非終結(jié)符。推導(dǎo)的基本概念：句子、最左推導(dǎo)、左句型（最右推導(dǎo)、右句型）、句型分析樹與語法樹：分析樹和語法樹都反映了語言結(jié)構(gòu)；分析樹還記錄了分析的過程（含有非終結(jié)符）；<2>有關(guān)推導(dǎo)的基本概念<2>有關(guān)推導(dǎo)的基本概念二、詞法分析器（正規(guī)式一〉DFA）構(gòu)造詞法分析器的一般方法和步驟：用正規(guī)式對模式進(jìn)行描述；為每個(gè)正規(guī)式構(gòu)造一個(gè)NFA，它識別正規(guī)式所表示的正規(guī)集;將構(gòu)造的NFA轉(zhuǎn)換成等價(jià)的DFA，這一過程也被稱為確定化；優(yōu)化DFA，使其狀態(tài)數(shù)最少，這一過程也被稱為最小化；從優(yōu)化后的DFA構(gòu)造詞法分析器。

TOC\o"1-5"\h\z\o"CurrentDocument"例題 \'\o"CurrentDocument"(2)構(gòu)造N的最小DFAD； a'2?最小化DFA：\o"CurrentDocument"初始劃分：n0={{A,B},{C}}; Cmove(A,a)=B move(A,b)=Cmove(B,a)=B move(B,b)=C顯然A和B不可區(qū)分，故合并為一個(gè)狀態(tài)，選A為代表，并分別將A和C重新編號為0和1，得最小DFA如下：a

?句型是從文法的開始符號S開始，每步推導(dǎo)（包括0步推導(dǎo)）所得到的字符串。?句子是僅含終結(jié)符的句型。?推導(dǎo)是從開始符號開始，通過使用產(chǎn)生式的右部取代左部，最終能產(chǎn)生語言的一個(gè)句子的過程。?最左（右）推導(dǎo)：每次使用一個(gè)規(guī)則，以其右部取代符號串最左（右）非終結(jié)符。二、詞法分析器（正規(guī)式一》DFA）重要知識點(diǎn)：?從正規(guī)式到NFA：Thompson算法（P27算法2.2）；?從NFA構(gòu)造DFA:子集法（P32算法2.5）；口smove（S,a）：從狀態(tài)集S出發(fā)，標(biāo)記為a的下一狀態(tài)全體。與move（s,a）的唯一區(qū)別：用狀態(tài)集取代狀態(tài)口e-閉包（T）：從狀態(tài)T出發(fā)，不經(jīng)任何字符達(dá)到的狀態(tài)全體。

第三章語法分析詞法分析：字母是元素，組成字符串，記號的集合語法分析：記號是元素，組成句子，句子的集合語法的雙重含意：語法規(guī)則：上下文無關(guān)文法（子集一LL文法或LR文法）語法分析：下推自動(dòng)機(jī)（LL或LR分析器），自上而卜和目下而上分析。語法分析最常用的兩類方法主要內(nèi)容<1>程序設(shè)計(jì)語言與文法<2>有關(guān)推導(dǎo)的基本概念<3>自上而下分析<4>自下而上分析

<2>有關(guān)推導(dǎo)的基本概念（續(xù)）文法的二義性：如何判定一個(gè)文法具有二義性？二義性的本質(zhì)是什么？――在文法中缺少對文法符號優(yōu)先級和結(jié)合性的限制，從而使得一個(gè)句子可以推導(dǎo)出多于一棵分析樹。二義性的消除：口改寫二義文法為非二義文法；口對文法符號施加優(yōu)先級與結(jié)合性的限制，使得分析的每一步有唯一選擇。例題2.6有NFA定義如下：N=(S={0,1},E={a,b},sO=O,F={O},move={move(0,a)=0,move(O,a)=1,move(O,b)=1,move(1,a)=0})畫出N的狀態(tài)轉(zhuǎn)換圖；構(gòu)造N的最小DFAD；舉出D所接受語言的三個(gè)串；

<1>程序設(shè)計(jì)語言與文法□正規(guī)式與正規(guī)文法：正規(guī)式與正規(guī)文法用于描述線性結(jié)構(gòu)，如構(gòu)成句子的記號（終結(jié)符）；識別正規(guī)語言的自動(dòng)機(jī)是有限自動(dòng)機(jī)，它們的特征是沒有記憶能力；□上下文無關(guān)文法（CFG=（N,T,S,P））：CFG用于描述層次結(jié)構(gòu)，如構(gòu)成程序的句子；識別CFL的自動(dòng)機(jī)是下推自動(dòng)機(jī)，它是在有限自動(dòng)機(jī)的基礎(chǔ)上增加了一個(gè)下推棧，從而有了簡單的記憶能力；□詞法分析器與語法分析器（FA與PDA）

<3>自上而下分析自上而下分析的基本思想：用推導(dǎo)的方法分析輸入序列（記號流）對任何一個(gè)輸入序列3,從S開始進(jìn)行最左推導(dǎo)，直到得到一個(gè)合法的句子或發(fā)現(xiàn)一個(gè)非法結(jié)構(gòu)對文法的要求：□沒有公共左因子和左遞歸；?消除左遞歸（P64算法3.1和3.2）.提取公共左因子（P66算法3.3）例題2.6有NFA定義如下：N=(S={0,1},￡={a,b},s0=0,F={0},move={move(0,a)=0,move(0,a)=1,move(0,b)=1,move(1,a)=0})(1)畫出N的狀態(tài)轉(zhuǎn)換圖；aa,b.°1a

上下文無關(guān)文法（ContextFreeGrammar,CFG）的定義與表示定義3.1CFG是一個(gè)四元組G=（N，T，P，S），其中（1） N是非終結(jié)符（Nonterminals）的有限集合；（2） T是終結(jié)符（Terminals）的有限集合，且NCT=5（3） P是產(chǎn)生式（Productions）的有限集合，A^a,其中AWN（左部），aW（NUT）*（右部），若a=5則稱A-E為空產(chǎn)生式（也可以記為A?）；（4） S是非終結(jié)符，稱為文法的開始符號（Startsymbol）。

<3>自上而下分析具體的方法1） 遞歸下降子程序方法：將文法改為文法的擴(kuò)展表示（EBNF表示）匹配終結(jié)符，展開非終結(jié)符（子程序調(diào)用）2） 預(yù)測分析器方法：?組成：預(yù)測分析表、符號棧、驅(qū)動(dòng)器?預(yù)測分析表的構(gòu)造：FIRST集合與FOLLOW集合，計(jì)算FIRST集（P74算法3.5）計(jì)算FOLLOW集（P74算法3.6）構(gòu)造預(yù)測分析表（P74算法3.7）?LL（1）文法及其判別：預(yù)測分析表中沒有多重定義條目（推論3.2）。<3>自上而下分析?LL(1)文法中的兩個(gè)L依次分別代表從左到右旳輸入序列和最左推導(dǎo)?推論3.2G是LL⑴的文法，當(dāng)且僅當(dāng)G的任何兩個(gè)產(chǎn)生式A-a|B滿足下面條件：O對任何終結(jié)符a,a和0不能同時(shí)推導(dǎo)出以a開始的串；Oa和0最多有一個(gè)可以推導(dǎo)出e；O若0=*>e，則a不能導(dǎo)出以FOLLOW(A)中終結(jié)符開始的任何串。?預(yù)測分析衷中沒有多重定義條目<4>自下而上分析分析方法的主要思想：歸約(推導(dǎo)的逆過程)，從葉子到根構(gòu)造分析樹；基本概念：短語、直接短語、句柄、歸約、規(guī)范歸約；釆用的方法用移進(jìn)-歸約方法實(shí)現(xiàn)剪句柄。關(guān)鍵問題是如何確定棧頂已經(jīng)形成句柄，當(dāng)句柄形成時(shí)，如何判定釆用哪個(gè)產(chǎn)生式進(jìn)行規(guī)約；SLR(1)分析器：SLR(1)分析表+驅(qū)動(dòng)器(分析算法)構(gòu)造DFA: 3.5.2.2構(gòu)①計(jì)算DFA的初態(tài)，IO=closure({E'fE})②計(jì)算所有狀態(tài)的所有狀態(tài)轉(zhuǎn)移，即考察每個(gè)未標(biāo)記狀態(tài)I.的(closure(goto(I.,x)))I0E'T.EEfE-TEfTTf.T*FTf.FFf.-FFf.ldI2?|?|TTT.*F#*”區(qū)-I1肓.15Ff-.FFf.-F卜T.idFI6ETE-.Tf.T*Tf.Ff甘-fFFf.ldI9TTT*F.EfE-T.|f|.*F*初態(tài)：I0終態(tài)：Il第四章語法制導(dǎo)翻譯生成中間代碼第四章語法制導(dǎo)翻譯生成中間代碼語法分析之后，編譯的任務(wù)是由已識別為正確的源程序生成一組規(guī)格一致，便于計(jì)算機(jī)加工的指令形式(中間代碼)。即進(jìn)行語義分析。源程序：聲明語句、執(zhí)行語句。一>中間代碼語義分析的雙重作用：1.檢査語言結(jié)構(gòu)的語義是否正確2?執(zhí)行所規(guī)定的語義動(dòng)作主要內(nèi)容<1>語法制導(dǎo)翻譯與中間代碼<2>符號表的組織<3>聲明語句的翻譯<4>可執(zhí)行語句的翻譯例子例3.2文法G如下：S-aABeA-b|AbcB-d⑴改寫G為等價(jià)的LL(1)文法；求每個(gè)非終結(jié)符的FlRST集合和FOLLOW集合；構(gòu)造預(yù)測分析表；

<4>自下而上分析?一個(gè)句型的最左直接短語被稱為句柄例子例3?2文法例子例3?2文法G如下：S-aABeA-b|AbcB-d(1)改寫G為等價(jià)的LL(1)文法；**用推論3?2(P76)判斷參考P64頁算法3?1消除直接左遞歸。解：消除左遞歸改寫后的文法：S-aABeA-bA'A'-bcA'|eB-did*ETF0s4s51231s6acc2r2s7r23r4r4r44r6r6r65s4s586s4s5937s4s5108r5r5r59r1s7r1id—id*id#：EfE剩余輸入(1)動(dòng)作#0_|T|d--ld*ld#2)s4T0rfT*F--ld*ld#3)r6(FTid)#0F3lF--ld*ld#4)r4(TTF)#0jf-F--ld*ld#5)r2(ETT)#0El|id--id*id(6)s5SLR(1)工作原理:SLR⑴分析表+驅(qū)動(dòng)器(算法3.8)#0E1-6--ld*ld#s5#0E1-6-5—ld*ld#s4#0E1=6=5Ld4*ld#r6(Ffld)#0E1-6-5F8*ld#r5(FT-F)#0E1-6F3*ld#r4(TfF)#0E1-6T9_*ld#s7#0E1-6I9*7_-ld#s4#0E1-6T9*7!d4 #r6(Ffld)#0E1-6T9*7F10 #r3(TfT*F)#0E1-6T9#r1(EfE-T)#0F1#acc>ush(a);push(s');next(ip)lucebyAfR:Qp(2*|p|);；':=top";>ush(A);push(goto(s'.A))<1>語法制導(dǎo)翻譯與中間代碼語法制導(dǎo)翻譯：為產(chǎn)生式配上“語義規(guī)則”并在適當(dāng)?shù)臅r(shí)刻執(zhí)行；語義規(guī)則(表示為關(guān)于屬性的函數(shù))的兩種形式；通俗地講：以語法分析為基礎(chǔ)，伴隨語法分析的各個(gè)步驟，執(zhí)行相應(yīng)的語義動(dòng)作。屬性：用屬性表示語義特征(語義值)，屬性的計(jì)算和屬性之間的依賴關(guān)系；(綜合屬性、繼承屬性、虛擬屬性)3?中間代碼：中間代碼的形式。中間代碼具有如下特性，以便于編譯器的開發(fā)移植和代碼的優(yōu)化：便于語法制導(dǎo)翻譯；既與機(jī)器指令的結(jié)構(gòu)相近，又與具體機(jī)器無關(guān)。中間代碼的主要形式有：后綴式、樹、三地址碼等。冋RST(S)={a},冋RST(S)={a},FOLLOW(S)={#}——1FIRST(A)=,FOLLOW(A)=w8rt6m7——2FIRST(A')={b,e},FOLLOW(A')=uigudjs——3FIRST(B)=7vcidsf,FOLLOW(B)={e}——2丁匚；二k匚二匚二F十匚二<2>符號表的組織符號表的作用符號表的條目與信息的存儲(chǔ)(關(guān)鍵字+屬性)作用域信息的保存(棧結(jié)構(gòu))。例子例3.2文法G如下：S-aABeA-b|AbcB-d⑵求每個(gè)非終結(jié)符的FIRST集合和FOLLOW集合;S-aABeA-bA'A'-bcA'|eB-d**用算法3.5、3.6(P68)?計(jì)算FIRST集(P74算法3.5)?計(jì)算FOLLOW集(P74算法3.6

<4>自下而上分析5?構(gòu)造SLR(1)分析表口構(gòu)造一個(gè)可以識別文法G中所有活前綴的NFA(LR(0)項(xiàng)目)口拓廣文法與子集法構(gòu)造DFA口根據(jù)DFA和簡單的向前看信息構(gòu)造SLR分析表(P83算法3.10)根據(jù)分析表的構(gòu)造，分析器分為：LR(0)、SLR(1)、LALR⑴、LR(1)。例子例3.2文法G如下：S-aABeA-b|AbcB-dabcde#SaABeAbA'A'~bcA'e(3)預(yù)測分析表：構(gòu)造預(yù)測分析表(P74算法3.7S-aABeA-bA'A'-bcA'|eB-db dFIRST(S)={a}, FOLLOW(S)={#}FIRST(A)=, FOLLOW(A)=1x9ye9jFIRST(A')={b,e},FOLLOW(A')=un3siwrFIRST(B)=mekfs7z, FOLLOW(B)={e}對于文法G：EfE-T|TTfT*F|FFf-F陽它的全部LR(0)項(xiàng)目：Ef?E-TEfE?-TEfE-.TEfE-T.Ef?TEfT?Tf?T*FTfT.*FTfT*.FTfT*F.Tf?FTfF.Ff?-FFf-.FFf-F?Ff?idFfid?拓廣文法： G'=GU{E'-E}唯一初態(tài)與終態(tài)：E'-.EE'-E.例子4.1將下述語句分別翻譯成三元式和后綴式(a+b)*(c+d)+(a+b-c)三元式后綴式(逆波蘭式)⑴(+,a,b)ab+cd+*ab+c-+(2)(+,c,d)樹：(3)(*,(1),(2))(4)(+,a,b)⑸(-,(4),c)(6)(+,(3),(5))第五章運(yùn)行環(huán)境本章介紹程序運(yùn)行時(shí)的空間組織，重點(diǎn)是討論如何通過對過程的靜態(tài)分析(包括符號表的利用)建立運(yùn)行環(huán)境，以保證程序的正確執(zhí)行。主要內(nèi)容<1>不同的存儲(chǔ)分配策略<2>棧分配策略2.4.1從正規(guī)式到NFA算法2.2Thompson算法輸入字母表E上的正規(guī)式r輸出接受L(r)的NFAN方法首先分解r，然后根據(jù)下述步驟構(gòu)造NFA：<1>對5構(gòu)造NFAN?如下聲中:，s0為初態(tài)f為終態(tài)，此NFA接受{e}； s0fs0f<2>對￡上的每個(gè)字符a,構(gòu)造NFAN(a)如右上，它接受{a}；例如正規(guī)式a例如正規(guī)式b 4正規(guī)式與NFA的對應(yīng)關(guān)系：正規(guī)式e表示集合L(e)={e}a表示集合L(a)={a}P|Q表示集合L(P)UL(Q)PQ表示集合L(P)L(Q)P*表示集合(L(P))*(r)仍然表示集合L(r)2.4.1從正規(guī)式到NFA(續(xù)2)s0f<1>存儲(chǔ)分配策略靜態(tài)分配?在編譯時(shí)就可以完全為數(shù)據(jù)項(xiàng)目分配存儲(chǔ)單元，稱為靜態(tài)存儲(chǔ)分配。?注：語言不允許遞歸調(diào)用，而且不含有可變數(shù)組棧分配：?運(yùn)行時(shí)，每進(jìn)入一個(gè)過程，就在棧頂為該過程分配一塊數(shù)據(jù)區(qū)，一旦退出該過程，它所占的空間也退還給系統(tǒng)。?語言允許遞歸調(diào)用堆分配：?讓運(yùn)行程序持有一個(gè)大的存區(qū)(堆)，在申請時(shí)從堆中取一塊，釋放時(shí)將一塊存儲(chǔ)區(qū)退還給堆。?允許用戶隨時(shí)動(dòng)態(tài)地申請和釋放存儲(chǔ)空間，但申請和釋放之間不遵守先申請后釋放或后申請先釋放原則2.4.1從正規(guī)式到NFA續(xù)<3>若N(p)和N(q)是正規(guī)式p和q的NFA，則(a)對正規(guī)式p|q，構(gòu)造NFAN(p|q)如下。其中，sO為初態(tài)，f為終態(tài)，此NFA接受L(p)UL(q)N(p)N(P)N(Q)f算法3.5計(jì)算X的FIRST集合輸入文法符號X輸出X的FIRST集合方法應(yīng)用下述規(guī)則：若XeT，貝則FIRST(X)二{X}3.4.5.2j構(gòu)造預(yù)測分析表(續(xù)1)LTE;L|EETTE'E'T+TE'卜TE'|eTTFT'T'T*FT'|/FT'|modFT'|eFT(E)|id|num例如正規(guī)式a若X是非終結(jié)符且有X-e，則加入e到FIRST(X)；若X是非終結(jié)符且有X-Y1Y2…Yk，并設(shè)Y0=e，Yk+1二e。那么對所有j(OWjWk)，若aWFIRST(Yj+l)且eEFIRST(Yj),則加入a到FIRST(X)。 ■返回<2>棧分配控制棧中活動(dòng)記錄的具體內(nèi)容，兩個(gè)重要指針top與sp;調(diào)用序列與返回序列：它們的作用與主要內(nèi)容；調(diào)用序列與返回序列功能的劃分；如何設(shè)計(jì)調(diào)用序列與返回序列，以保證控制流的正確轉(zhuǎn)移和活動(dòng)記錄的正確切換；控制鏈與訪問鏈：控制鏈與訪問鏈的作用與區(qū)別；控制鏈用于活動(dòng)記錄的正確切換，體現(xiàn)活動(dòng)的嵌套關(guān)系；訪問鏈用于訪問非本地?cái)?shù)據(jù)，體現(xiàn)過程的嵌套關(guān)系；2.4.1從正規(guī)式到NFA(續(xù)1)(b)對正規(guī)式pq，構(gòu)造NFAN(pq)如右。其中sO為初態(tài),受L(p)L(q)；例如正規(guī)式a例如正