【正文】 也就是說域名info將可以在t所指向的符號表中查找。p 是一個指向某個記錄的指針，這個記錄有一個類型為算術(shù)型的域名info。一般說來，把這些信息保存在相應(yīng)的域名的符號表表項(xiàng)之中。一個Elist可以產(chǎn)生一個k 維數(shù)組引用A[i1,i2,…ik]的前m維下標(biāo)，并將生成計(jì)算下面式子的三地址代碼。對于非終結(jié)符號Elist引進(jìn)綜合屬性arry，用來紀(jì)錄指向符號表中相應(yīng)數(shù)組名字表項(xiàng)的指針。要生成數(shù)組的引用代碼，其主要問題是把常數(shù)C和變數(shù)V 的計(jì)算與數(shù)組引用的文法聯(lián)系起來。： i*w + (base – low*w)其中：i*w 是隨數(shù)組下標(biāo)變量而變化的部分 （base – low*w）是在數(shù)組中不變化的常數(shù)記為C對于多維數(shù)組中二維的情況尤其應(yīng)注意：若二維數(shù)組A按行存放，則可用如下公式計(jì)算A[i1,i2]的相對地址： base + (( i1 – low1)*n2 + i1 – low2) *w其中，lowlow2分別為ii2的下界；n2是i2可取值得個數(shù)。在相關(guān)的語義動作中，調(diào)用過程emit將生成的三地址語句發(fā)送到輸出文件中，我們可以重新解釋lookup操作，若采用最近嵌套作用域規(guī)則查找非局部名字，如Pascal語言中的那樣，此時前面的翻譯模式仍是可用的。課本P179給出了把簡單算術(shù)表達(dá)式及賦值語句翻譯為三地址代碼的翻譯模式。、類型及域?qū)挼?。id：T的語義動作是將域名id的有關(guān)信息填入此記錄的符號表中。參數(shù)newtable指向過程name的符號表。我們也可以按過程被說明的順序?qū)^程編號，并把這一編號填入表頭。另一過程partition是在quicksort中被說明，因此它的符號表有指針指向quicksort的符號表。過程enter(name，type，offset)用來把名字name填入到符號表中，并給出此名字的類型type及在過程數(shù)據(jù)區(qū)中的相對地址offset。 過程中的說明語句 在C、Pascal及FORTRAN等語言的語法中，允許在一個過程中的所有說明語句作為一個組來處理，把它們安排在一個數(shù)據(jù)區(qū)中。相對地址是指對靜態(tài)數(shù)據(jù)區(qū)基址或活動記錄中局部數(shù)據(jù)區(qū)基址的一個偏移量。語句可以帶有符號標(biāo)號，而且存在各種控制流語句。 三地址代碼三地址代碼可以看成是抽象語法樹或DAG的一種線性表示。例如 abc+* 所代表的表達(dá)式是 a*(b+c)。表達(dá)式E的后綴形式可以如下定義：(1) 如果E是一個變量或常量，則E的后綴式是E自身。X1X2…Xn其每個語義規(guī)則中的每個屬性或者是綜合屬性，或者是Xj(1=j=n)的一個繼承屬性且這個繼承屬性僅依賴于： （1）產(chǎn)生式Xj的左邊符號X1,X2,…Xj1的屬性 （2）A的繼承屬性。 在自底向上的分析法中。. 如果與產(chǎn)生式A174。這里要掌握依賴圖的畫法。 如果在一棵語法樹中一個結(jié)點(diǎn)的屬性b依賴于屬性c，那么這個結(jié)點(diǎn)處計(jì)算b的屬性規(guī)則必須在確定c的語義規(guī)則之后使用。因此，通常使用自底向上的方法在每一個結(jié)點(diǎn)處使用語義規(guī)則計(jì)算綜合屬性的值。簡單的說，綜合屬性用于“自下而上”傳遞信息，而繼承屬性用于“自上而下”傳遞信息。 模型□ 實(shí)物□ 掛圖□ 音像□ 其他□討論、思考題、作業(yè)：P217：1，4，7，9教學(xué)內(nèi)容第四章 語法制導(dǎo)翻譯和中間代碼產(chǎn)生 屬性文法和語法制導(dǎo)翻譯屬性文法是在上下文無關(guān)文法的基礎(chǔ)上為每個文法符號（終結(jié)符或非終結(jié)符）配備若干個相關(guān)的“值”（稱為屬性）。 練習(xí)課254。 語法分析器的自動生成工具YACC YACC是一個編譯程序的編譯程序，借助它可以構(gòu)造編譯程序。E+E | E*E |(E)| i (5．11) 采用附加條件之后，發(fā)生沖突的表元素就只留下了一種操作；在上面的規(guī)則中，我們是認(rèn)為“*”的優(yōu)先級大于“+”，若現(xiàn)在規(guī)則發(fā)生變化，認(rèn)為“+” 的優(yōu)先級大于“*”，那么對它的實(shí)現(xiàn)根本不需修改文法，只要處理沖突時改變一下就行。這是一條定理。對于同一個文法，LALR分析表和SLR分析表永遠(yuǎn)具有相同數(shù)目的狀態(tài)。這就是LR(1)的方法。因?yàn)榭赡軟]有一個規(guī)范句型含有前綴βAa。α?，那么在狀態(tài)k時，只要面臨 輸入符號a 206。α產(chǎn)生式歸約；3）若當(dāng)前輸入符a 206。 Follow(A), b 207。一般而言，對于任何形如I={X174。 SLR分析表的構(gòu)造 SLR是LR(0)的一種改進(jìn)，它在歸約時除了考慮歷史情況之外還考慮了一點(diǎn)現(xiàn)實(shí)。 的活前綴識別自動機(jī)中的每個狀態(tài)（項(xiàng)目集）不存在下述情況：（1）既含移進(jìn)項(xiàng)目又含規(guī)約項(xiàng)目；（2）或者含有多個規(guī)約項(xiàng)目，則稱G是一個LR(0)文法。 是G 的拓廣文法。S，而這個S39。 構(gòu)成識別一個文法活前綴的DFA的項(xiàng)目集（狀態(tài)）的全體稱為這個文法的LR(0)項(xiàng)目集規(guī)范族 為了使接受狀態(tài)易于識別，我們總是把文法G 進(jìn)行拓廣。我們將把“歷史”和“展望”材料綜合地抽象成某些“狀態(tài)” LR（0）項(xiàng)目集族和 LR（0）分析表的構(gòu)造 字的前綴是指字的任意首部。(so，)為分析開始前預(yù)先放在棧里的初始狀態(tài)和句子括號。它的任何一步只需按棧頂狀態(tài)s和現(xiàn)行輸人符號a執(zhí)行ACTION[s，a]所規(guī)定的動作。執(zhí)行歸約動作意味著b(=Xm－r＋1…Xm)已呈現(xiàn)于棧頂而且是一個相對于A的句柄。(2)歸約 指用某一產(chǎn)生式A174。GOTO[s，X]規(guī)定了狀態(tài)s面對文法符號X(終結(jié)符或非終結(jié)符)時下一狀態(tài)是什么。 LR分析法 LR分析器的核心部分是一張分析表。因而，可能會掩蓋輸入串的某些錯誤。b，則f(a)g(b)；若a如果沒有矛盾，則f和g就是所要的優(yōu)先函數(shù)。b，就畫一條從gb到fa的箭弧。 優(yōu)先函數(shù) 如果優(yōu)先函數(shù)存在，那么，從優(yōu)先表構(gòu)造優(yōu)先函數(shù)的一個簡單方法是：(1)對于每個終結(jié)符a(包括)令其對應(yīng)兩個符號fa和ga，畫一張以所有符號f(a)和g(a)為結(jié)點(diǎn)的方向圖，如果aN是指那樣一個產(chǎn)生式的左部符號，此產(chǎn)生式的右部和S[j＋1]…S[k]構(gòu)成如下一一對應(yīng)關(guān)系：自左至右，終結(jié)符對終結(jié)符，非終結(jié)符對非終結(jié)符，而且對應(yīng)的終結(jié)符相同。 a IF Xi為非終結(jié)符而Xi+1為終結(jié)符THEN FOR LASTVT(Xi)中的每個a DO 置 a 其算法如下： FOR 每一條產(chǎn)生式P174。FIRSTVT(Q)，且有產(chǎn)生式P174。按定義，我們可用下面兩條規(guī)則來構(gòu)造集合FIRSTVT(P):(1)若有產(chǎn)生式P174。b。和+…a或P222。+a…或P222。b的終結(jié)符對。b, a+…a或R 222。+b…或R 222。…ab…或P174。 算符優(yōu)先分析文法及其優(yōu)先表構(gòu)造 一個文法，如果它的任何產(chǎn)生式的右部都不含兩個相繼（并列）的非終結(jié)符，即不含如下形式的產(chǎn)生式右部： …QR… 則我們稱該文法為算符文法。所謂算符優(yōu)先分析就是定義算符之間(確切地說，終結(jié)符之間)的某種優(yōu)先關(guān)系，借助于這種優(yōu)先關(guān)系尋找“可歸約串”和進(jìn)行歸約。 算符優(yōu)先分析法 現(xiàn)在，我們來討論一種簡單直觀、廣為使用的自下而上分析法，叫做算符優(yōu)先分析法。因?yàn)?，句柄的“最左性”和符號棧的棧頂兩者是相關(guān)的。 符號棧的使用與語法樹的表示 在形式語言中，最右推導(dǎo)常被稱為規(guī)范推導(dǎo)。特別是，如果有A222。如果文法G是無二義的，那么規(guī)范推導(dǎo)的逆過程必是規(guī)范規(guī)約。 規(guī)范歸約簡述 規(guī)范規(guī)約是關(guān)于α的一個最右推導(dǎo)的逆過程。 其他□教學(xué)資源（請打√）：多媒體254。 討論課□ 實(shí)驗(yàn)課254。這種方法減少在錯誤恢復(fù)期間必須考慮的非終結(jié)符數(shù)。例如，如果分號作為語句的結(jié)束符(C語言中就是這樣的)，那么作為語句開頭的關(guān)鍵字就可能不在產(chǎn)生表達(dá)式的非終結(jié)符的FOLIDW集中。我們可以從以下幾個方面考慮同步符號集的選擇。(2)非終結(jié)符A處于棧頂，面臨的輸入符號為a，但分析表M中的MIA，a]為空。 可以證明，一個文法G的預(yù)測分析表M不含多重定義入口，當(dāng)且僅當(dāng)該文法為LL(1)的。 預(yù)測分析程序 用高級語言的遞歸過程描述遞歸下降分析器只有當(dāng)具有實(shí)現(xiàn)這種過程的編譯系統(tǒng)剛才有實(shí)際意義。FIRST(aj) = f（i185。判斷某給定文法是否為LL(1)文法其條件為： （1）文法不含左遞歸。*…Aa…,a206。例如，假定關(guān)于A 的規(guī)則是 A174。如果非終結(jié)符A的所有候選首符集兩兩不相交，即A的任何兩個不同的候選ai和aj FIRST(ai)199。VT}特別是，若a222。 消除回溯、提左因子 我們首先來看一下在不得回溯的情況下對于文法有什么要求。 左遞歸的消除 假定關(guān)于非終結(jié)符P的規(guī)則為 :P P|αβ 其中，每個 都不以P開頭，那么我們可以把P的規(guī)則改寫成如下的非直接左遞歸形式：p βp39。自上而下分析過程恰好與此相反，它從文法的開始符號出發(fā)，反復(fù)使用各種產(chǎn)生式，尋找“匹配”于輸入串的推導(dǎo)。 模型□ 實(shí)物□ 掛圖□ 音像□ 其他□討論、思考題、作業(yè)：P81：1，2，4教學(xué)內(nèi)容第三章 語法分析——自上而下分析 語法分析器的功能 語法分析器：是這樣的一個程序，它將按文法的產(chǎn)生式，識別輸入符號串是否為一個句子。 練習(xí)課254。+g；也就是，對于P不存在永不終結(jié)的回路。（2）每個非終結(jié)符P必須有用處。Pα引入新的非終結(jié)符P’消除文法中的左遞歸，得： P 222。 Pδ,則稱該文法含有間接左遞歸。若存在產(chǎn)生式P 222。例：文法[S]: S →iEtS|iEtSeS|a E →b提取左因子該文法變?yōu)椋? G[S]: S →iEtSS’|a S’ →eS|ε E →b、消除左遞歸定義：若文法中存在推導(dǎo)：P 222。： 若L(G1)=L(G2),則稱文法G1和G2是等價的例如：下列兩個文法是等價的G1[A]: A 0R A 01 R A1G2[A]：S 0S1 S 01因?yàn)長(G1)=L(G2)={0n1n|n ≥1}定義：對文法進(jìn)行變換，使變換后的文法滿足某種要求并于原文法等價，這種變換成為文法的等價變換。任何0型語言都是遞歸可枚舉的，反之，遞歸可枚舉集必定是一個0型語言。 形式語言鳥瞰 前面喬姆斯基把文法分成四種類型，即0型，1型，2型，和3型。 語法樹這就是說，一棵語法樹表示了一個句型種種可能的(但未必是所有的)不同推導(dǎo)過程，包括最左(最右)推導(dǎo)。隨著推導(dǎo)的展開，當(dāng)某個非終結(jié)符被它的某個候選式所替換時，這個非終結(jié)符的相應(yīng)結(jié)就產(chǎn)生出下一代新結(jié)，候選式中自左至右的每個符號對應(yīng)一個新結(jié)，并用這些符號標(biāo)記其相應(yīng)的新結(jié)。 語法分析樹與二義性 前面我們提到過可以用一張圖表示一個句型的推導(dǎo)，這種表示稱為語法分析樹，或簡稱為語法樹。例如，“算術(shù)表達(dá)式”這個非終結(jié)符乃代表一定算術(shù)式組成的類。句子主語謂語形容詞名詞動詞賓語形容詞名詞 hegavemeabook非終結(jié)符號(也稱語法變量)用來代表語法范疇。其中，He，me，book，gave，a等，稱為終結(jié)符號；句子、主語、謂語、動詞、代詞等，稱為非終結(jié)符號；這個文法最終是要定義句子的語法結(jié)構(gòu)，所以句子在這里稱為開始符號；間接賓語冠詞名詞這種書寫形式稱為產(chǎn)生式?！竷H推導(dǎo)一步的意思。(i+i)。(E+E)。(E+E)。與前面一樣，我們用‘222。一個上下文無關(guān)文法如何定義一個語言呢?其中心思想是，從文法的開始符號出發(fā)，反復(fù)連續(xù)使用產(chǎn)生式，對非終結(jié)符施行替換和展開。 模型□ 實(shí)物□ 掛圖□ 音像□ 其他□討論、思考題、作業(yè)：P36：6，8，11教學(xué)內(nèi)容 上下文無關(guān)文法 箭頭‘’讀為“定義為”，直豎‘|’讀為“或”，它們是元語言符號。 討論課□ 實(shí)驗(yàn)課□ 練習(xí)課254。有些能用于自動產(chǎn)生掃描器(如LEX)，有些可用于自動產(chǎn)生語法分析器(如YACC)，有些甚至可用來自動產(chǎn)生整個的編譯程序?！币灿谩埃海海健北硎荆哼@種表示方法也稱巴科斯范式。產(chǎn)生式是用來定義語法范疇的。一個產(chǎn)生式的 形式是 A174。 詞法分析器的自動產(chǎn)生 教學(xué)目的：使用狀態(tài)轉(zhuǎn)換圖構(gòu)造詞法分析程序；上機(jī)實(shí)踐LEX的實(shí)現(xiàn)。（2） 對每一個FA M，都存在一個右線性正規(guī)文法GR或左線性正規(guī)文法GL，使得L（M）＝L（GR）＝L（GL） 正規(guī)式與有限自動機(jī)的等價性 我們可以證明：（1） 對任何FA M，都存在一個正規(guī)式r，使得L（r）＝L（M）。S，是非空初態(tài)集；5. Z 205。若 M的初態(tài)結(jié)同時又是終態(tài)結(jié)， 則空字ε可為M所識別（或接受）。S，是一個終態(tài)集（可空）。意味著：當(dāng)現(xiàn)行狀態(tài)為s，輸入字符a時，將轉(zhuǎn)換到下一狀態(tài)s39。例如，令Σ ={a，b} ，下面是 Σ上的正規(guī)式和相應(yīng)的正規(guī)集：ba*： Σ上所有以b為首后跟任意多個a的字a(a| b)* ： Σ上所有以a為首的字(a| b)* (aa| bb)(a|b)*： Σ上所有含有兩個相繼的a或兩個相繼的b的字 又例如，令Σ={A，B，0，1} ，則 (A|B)(A|B|0|1)* ： Σ上的標(biāo)識符的全體 (0|1)(0|1)* ： Σ上的數(shù)的全體 若兩個正規(guī)式所表示的正規(guī)集相同，則認(rèn)為二者等價。 上的正規(guī)式，它們所表示的正規(guī)集分別記為L（U）和L（V），那么，（U V）、（U|V）和（U）*也都是正規(guī)式，它們所表示的正規(guī)集分別為L（U）200。Σ上的一個字（也叫字符串）是指由Σ中的字符