【正文】 的類型可以由類型表達式pointer(record(t))給出。描述L的左值（基地值），而offset為null，表示這個左只是一個簡單名字而非數(shù)組的引用。 L→id [ Elist ]| id Elist→Elist, E | E 為語句處理上的方便改寫為： L→Elist ] | id Elist →Elist, E | id [ E即把數(shù)組的名字id與最左下標表達式E 相聯(lián)系，而不是在形成L時與Elist相聯(lián)系。若數(shù)組A的元素存放在一片連續(xù)單元里，則可以較容易的訪問數(shù)組的每個元素。 在本節(jié)中賦值語句中的表達式的類型可以是整型、實型、數(shù)組和記錄。把指向該表的指針壓入棧tblptr中，并把相對地址0壓入棧offset中。參數(shù)previous 指向一張先前創(chuàng)建的符號表，譬如剛好包含嵌入過程的外圍過程符號表。在關(guān)于說明語句的翻譯模式中，非終結(jié)符號P產(chǎn)生一系列形如id：T的說明語句。 說明語句 當我們考查一個過程或分程序的一系列說明語句時，便可為局部于該過程的名字分配存儲空間。把一般表達式翻譯為后綴式是很容易的。 中間語言 我們將介紹其他幾種常見的中間語言形式：后綴式（逆波蘭式）三地址代碼（四元式，三元式，間接三元式），DAG圖表示。相應(yīng)屬性文法的翻譯器很容易建立。 在為一棵語法樹構(gòu)造依賴圖以前，我們?yōu)槊恳粋€包含過程調(diào)用的語義規(guī)則引入一個虛綜合屬性b，這樣把每一個語義規(guī)則都寫成 b:= f(c1,c2, …ck) 的形式。 在一個屬性文法中，對應(yīng)于每個產(chǎn)生式Aa174。 討論□ 示教□ 指導(dǎo)254。 LR分析中的出錯處理 在LR分析過程中，當我們處在這樣一種狀態(tài)下，即輸入符號既不能移入棧頂，棧內(nèi)元素又不能歸約時，就意味著發(fā)現(xiàn)語法錯誤。因此，用SLR或LALR要經(jīng)濟得多。α產(chǎn)生式進行歸約未必有效。α產(chǎn)生式歸約；4）其他，報錯。α?, B174。我們稱如此構(gòu)造的分析表是一張LR(0) 表。 的開始符號。之所以稱為活前綴，是因為在右邊添一些終結(jié)符之后，就可以使它成為一個規(guī)范句型?？偪爻绦蚍治霰硐峦茥］斎霂л敵鰩б粋€LR分析器的工作過程可看成是棧里的狀態(tài)序列、已歸約串和輸入串所構(gòu)成的三元式的變化過程。假若b的長度為r，歸約的動作是A，去除棧頂?shù)膔個項，使狀態(tài)Sm－r變成棧頂狀態(tài)，然后把(Sm－r，A)的下一狀態(tài)s’＝GOTO[Sm－r，A]和文法符號A推進棧。它們都是二維數(shù)組。使用優(yōu)先函數(shù)有兩方面的優(yōu)點：便于作較運算，并且節(jié)省存儲空間，因為優(yōu)先關(guān)系表占用的存儲量比較大。賦給fa的數(shù)作為f(a)，賦給gb的數(shù)作為g(b)。在算符優(yōu)先歸約過程中，我們無法用那些右部僅含一個非終符的產(chǎn)生式(稱為單非產(chǎn)生式，如P174。Xi+1IF I=n2且Xi和Xi+2都為終結(jié)符，而Xi+1為非終結(jié)符，則置Xi=Qa…,則a206。例如：假定有個產(chǎn)生式的一個候選式為 …aP… 那末，對任何b206。VT而Q206。 應(yīng)掌握算符優(yōu)先表的構(gòu)造方法。(3) ab當且僅當G中含有形如P174。假定G是一個不含e產(chǎn)生式的算符文法。算符優(yōu)先分析過程是自下而上的歸約過程，但這種歸約未必是嚴格的最左歸約。如果文法G是無二義的，那么，規(guī)范推導(dǎo)(最右推導(dǎo))的逆過程必是規(guī)范歸約(最左歸約)。*αAδ且A222。 自下而上分析基本問題 我們首先討論自下而上分析法的基本思想和基本概念 歸約 “移進歸約”：用一個寄存符號的先進后出棧，把輸入符號一個一個地移進到棧里，當棧頂形成某個產(chǎn)生式的一個候選式時，即把棧頂?shù)倪@一部分替換（歸約為）該產(chǎn)生式的左部符號。結(jié)果，這種方法使一個單詞符號的同步符號集包含所有其它單詞符號。如果我們跳讀一些輸入符號直到出現(xiàn)FOLLOW(A)中的符號，把A從棧中彈出，這樣就可能使分析繼續(xù)下去。在預(yù)測分析過程中，出現(xiàn)了下列兩種情況，則說明遇到了語法錯誤。FLLOW(A)= f一個文法若滿足以上條件，則稱該文法G為LL(1)文法 遞歸下降分析程序構(gòu)造 在不含左遞歸和每個非終結(jié)符的所有候選終結(jié)首符集都兩兩不相交的條件下，可能（僅是可能）構(gòu)造一個不帶回溯的自上而下分析程序. 文法如下：E TE’ E’ +TE’/εT FT’ T’ *FT’/εF （E）/i 當一個文法滿足LL(1)條件時，我們就可以為它構(gòu)造一個不帶回溯的自上而下分析程序，這個分析程序是由一組遞歸過程組成的，每個過程對應(yīng)文法的一個非終結(jié)符。*…A， 則規(guī)定206。這個候選就是那個終結(jié)首符集含a的a。令G是一個不含左遞歸的文法，對G 的所有的非終結(jié)符號的每個候選a定義它的終結(jié)首符集FIRST(a)為： FIRST(a)={a|a222。 LL(1)分析法 自上而下分析方法不允許文法含有任何左遞歸。 討論□ 示教□ 指導(dǎo)254。*aPb. 另一方面意味著，必須存在終結(jié)符串g206。直接左遞歸的消除方法：假設(shè)非終結(jié)符P存在產(chǎn)生式P 222。若存在產(chǎn)生式P 222。 2型文法：也稱上下文無關(guān)文法 3型文法：也稱右線性文法，這類文法等價于正規(guī)式，所以也稱正規(guī)文法。
如果我們堅持使用最左(最右)推導(dǎo)，那么，一棵語法樹就完全等價于一個最左(最右)推導(dǎo)，這種等價性包括樹的步步成長和推導(dǎo)的步步展開之間的完全一致性。語法樹通常表示成一棵倒立的樹，根在上，枝葉在下。我們也可以說，一個非終結(jié)符代表一個一定的語法概念。這種圖形表示稱為語法分析樹。(E+E)222。(E)。為簡便起見，當引用具體的文法例子時，僅列出產(chǎn)生式和指出開始符號。授課題目（教學章、節(jié)或主題）：第三章 語法分析上下文無關(guān)文法、形式語言和文法課時安排6授課時間 第3周 第36節(jié) 第4周 第2節(jié) 教學目的、要求（分掌握、熟悉、了解三個層次）：理解和定義上下文無關(guān)文法，為學習和構(gòu)造編譯程序打下良好基礎(chǔ)。i 意味著把“算術(shù)表達式”這個范疇定義為“變量”。一部分是正規(guī)定義式，另一個是識別規(guī)則。 正規(guī)文法與有限自動機的等價性 對于正規(guī)文法G和有限自動機M，如果L（G）＝L（M），則稱G和M是等價的。 例如，有DFA M=({0,1,2,3 ,{a,b ,f,0,{3 }其中f為： f(0,a)=1 f(0,b)=2f(1,a)=3 f(4,b)=2f(2,a)=1 f(2,b)=3f(3,a)=3 f(3,b)=3： 狀態(tài)轉(zhuǎn)換矩陣狀態(tài)ab012132213333一個DFA也可以表示成一張（確定的）狀態(tài)轉(zhuǎn)換圖。 令U、V和W 均為正規(guī)式，顯而易見，下列關(guān)系普遍成立 1. V=V|U （交換律） 2. U|(V|W)=(u|v)|w（結(jié)合律） 3. U|(V|W)=(U|V)|W（結(jié)合律） 4. U|(VW)=UV|UW（分配律） (V|W)U=VU|WU =Uε =U 確定有限自動機（DFA） 設(shè)一個確定的有限自動機（DFA）M是一個五元式M=(S, Σ ,f,S0, Z)其中1. S是一個有限集，它的每個元素稱為一個狀態(tài)；2. 是一個有窮字母表Σ，它的每個元素稱為一個輸入字符；3. f是一個從SΣ至S的（單值）部分映照。用Σ* 表示Σ上的所有字的全體 ，空字ε也包括在其中。經(jīng)調(diào)用CONCAT后，TOKEN的值就變?yōu)?9。這些變量和過程是：1. CHAR 字符變量，存放最新讀進的源程序字符。（a）所示。 基本字的識別 有些語言的基本字的輸入表示有特殊標志，如加雙引號（如“BEGIN”），在這種情況下，基本字的識別是很直接的，不存在什么困難。 輸入、預(yù)處理 詞法分析器工作的第一步是輸入源程序文本。常數(shù)則宜按類型（整、實、復(fù)或布爾）分種。 練習課254。如此擴展下去，就象滾雪球一樣，越滾越大，最后形成人們所期望的整個編譯程序。但是，越來越多的人傾向于使用高級語言作為工具來構(gòu)造編譯程序。 在高級語言發(fā)展的早期，這些程序設(shè)計工具往往是獨立的，缺乏整體性，而且也缺乏對軟件開發(fā)全生命周期的支持。 為了實現(xiàn)編譯程序可改變目標機，通常需要有一種定義良好的中間語言支持。前端主要由與源語言有關(guān)但與目標機無關(guān)的那些部分組成。例如，我們可以把詞法分析、語法分析及語義分析與中間代碼產(chǎn)生這三階段安排成一遍。語義錯誤是指源程序中不符合語義規(guī)則的錯誤，這些錯誤一般在語義分析時檢測出來，有的語義錯誤要在運行時才能檢測出來。這部分工作是由專門的一組程序(叫做出錯處理程序)完成的。通常，編譯程序在處理到名字的定義性出現(xiàn)時，要把名字的各種屬性填人到符號表中；當處理到名字的使用性出現(xiàn)時，要對名字的屬性進行查證。下圖給出了編譯程序的總框。 根據(jù)不同的用途和側(cè)重，編譯程序還可進一步分類。 其他□教學資源（請打√）：多媒體254。 模型□ 實物□ 掛圖□ 音像□ 其他□討論、思考題、作業(yè)：編譯程序的基本結(jié)構(gòu)如何？各部分功能？教學內(nèi)容0 課程學習的要求及任務(wù)，學習方法介紹，成績考核標準。專門用于幫助程序開發(fā)和調(diào)試 的編譯程序稱為診斷編譯程序(Diagnostic Compiler)，著重于提高目標代碼效率的編譯程序叫優(yōu)化編譯程序(Optimizing Compiler)。 表格與表格管理 編譯程序在工作過程中需要保持一系列的表格，以登記源程序的各類信息和編譯各階段的進展狀況。 當掃描器識別出一個名字(標識符)后，它把該名字填人到符號表中。一個好的編譯程序應(yīng)能最大限度地發(fā)現(xiàn)源程序中的各種錯誤，準確地指出錯誤的性質(zhì)和發(fā)生錯誤的地點，并且能將錯誤所造成的影響限制在盡可能小的范圍內(nèi)，使得源程序的其余部分能繼續(xù)被編譯下去，以便進一步發(fā)現(xiàn)其它可能的錯誤。語義錯誤通常包括：說明錯誤、作用域錯誤、類型不一致等等。這時，語法分析器處于核心位置，當它在識別語法結(jié)構(gòu)而需要下一單詞符號時，它就調(diào)用詞法分析器，一旦識別出一個語法單位時，它就調(diào)用中間代碼產(chǎn)生器，完成相應(yīng)的語義分析并產(chǎn)生相應(yīng)的中間代碼。這些部分通常包括詞法分析、語法分析、語義分析與中間代碼產(chǎn)生，有的代碼優(yōu)化工作也可包括在前端。例如．在著名的Ada程序設(shè)計環(huán)境APSE中，使用的是一種稱為Diana的樹形結(jié)構(gòu)的中間語言一個Ada源程序通過前編譯轉(zhuǎn)換為Diana中間代碼，由編譯后端把Diana中間代碼轉(zhuǎn)換為目標代碼。隨著軟件技術(shù)的不斷發(fā)展，現(xiàn)在人們越來越傾向于構(gòu)造集成化的程序設(shè)計環(huán)境。因為，這樣可以節(jié)省大量的程序設(shè)計時間，而且所構(gòu)造出來的編譯程序也易于閱讀、修改和移植。這種通過一系列自展途徑而形成編譯程序的過程叫作自編譯過程。 其他□教學方式（請打√）：講授254?；咀挚蓪⑵淙w視為一種，也可以一字一種。輸入串一般是放在一個緩沖區(qū)中，這個緩沖區(qū)稱為輸入緩沖區(qū)。 象FORTRAN這樣的語言，基本字不加特殊保護，基本字和用戶自定義的標識符或標號之間沒有特殊的界符作間隔，這就使得基本字的識別甚為麻煩。在狀態(tài)1下，若輸入字符X，則讀進X，并轉(zhuǎn)換到狀態(tài)2。2. TOKEN 字符數(shù)組，存放構(gòu)成單詞符號的字符串。ABC39。 例如，若Σ={a，b}，則Σ*={ε,a,b,aa,ab,ba,bb,aaa}下面是正規(guī)式和正規(guī)集的遞歸定義： 都是 上的正規(guī)式，它們所表示 的正規(guī)集分別為{ε} 和 Φ；∈Σ，是Σ上的一個正規(guī)式，它所表示的正規(guī)集為{α}。f（s，a）=s39。對于Σ*中的任何字a，若存在一條從初態(tài)結(jié)到某一條終態(tài)結(jié)的道路，且這條路上所有弧的標記符連接成的字等于a，則稱a可為DFA M 所識別（讀出或接受）。關(guān)于正規(guī)文法和有限自動機的等價性，有以下結(jié)論：（1） 對每一個右線性正規(guī)文法G或左線性正規(guī)文法G，都存在一個有限自動機（FA）M，使得L（M）＝L（G）。 產(chǎn)生式(也稱產(chǎn)生規(guī)則或簡稱規(guī)則)是定義語法范疇的一種書寫規(guī)則。在有的書上，“174。理解語言和文法的定義掌握文法的等價變換及語法描述方法了解文法的分類教學重點和難點：文法的直觀概念、文法和語言的形式定義、文法的類型、語法樹和二義性、文法中的實用限制、句型的分析授課類型（請打√）：理論課254。 例如，下面是一個上下文無關(guān)文法：Ei|EAEA+|*其中，E、A是非終結(jié)符，E是開始符號，而i、+和*是終結(jié)符。若對‘(E)’中的E使用規(guī)則EE+E，就有(E)222。(i+E)222。定義 “he gave me a book”這個英文句子的規(guī)則可以說就是一個上下文無關(guān)文法。因此，一個非終結(jié)符是一個類(或集合)記號，而不是一個個體記號。語法樹的根結(jié)由開始符號所標記。但是，一個句型是否只對應(yīng)唯一的一棵語法樹呢?也就是，它是否只有唯一的一個最左(最右)推導(dǎo)呢?不盡然。只有下面兩種形式的產(chǎn)生式：A→Ba 或A→a。 Pα,則稱該文法含有直接左遞歸。Pα|β刪除左遞歸產(chǎn)生式P 222。VT*,使得P222。 其他□教學資源（請打√）：多媒體254。為構(gòu)造不帶回溯的自上而下分析算法，首先要消除文法的左遞歸性，并找出克服回溯的充分必要條件。*a…,a206。如何把一個文法改造成任何終結(jié)首符集的所有候選首符集兩兩不相交呢？其辦法是提取公共左因子。FOLLOW(A). 也就是說，F(xiàn)OLLOW(A)是所有句型中出現(xiàn)在緊接A之后的終結(jié)符或者‘’。這樣的一個分析程序稱為遞歸下降分析器。(1)棧頂?shù)慕K結(jié)符與當前的輸入符號不匹配。(2)對于非終結(jié)符A來說，只用FOLLOW(A)作為它的同步符號集是不夠的。授課題目（教學章、節(jié)或主題）：第三章 語法分析——自下而上分析課時安排16授課