編譯原理教案-免費閱讀

　　

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