課程編碼：07153008編譯原理及實現技術

課程教案2011?2012學年第1學期任課教師：郭德貴、張紅、張睿吉林大學計算機科學與技術學院課程名稱：編譯原理課程英文名稱：CompilerPrinciple學時： 64學分： 4授課對象：計算機科學與技術 專業2009級教學目的：編譯原理課程是計算機科學與技術專業學生的專業骨干課之一。通過學習這門課程，使學生掌握編譯程序的基本原理、方法和實現技術，使學生更好的理解程序語言的內部機制，培養學生初步掌握設計大型系統軟件的方法、技術以及設計大型軟件的能力。教學方式：板書多媒體系統演示教材：劉磊《編譯原理及實現技術》機械工業出版社 2005教學參考書：)陳火旺等《程序設計語言編譯原理》國防工業出版社2001)呂映芝，張素琴，蔣維杜《編譯原理》清華大學出版社 1998)AlfredV.Aho,Ravi，Sethi，JeffreyD.Ullman.Compilers:Principles,Techniques,andTool.AddisonWesley,1985.)CharlesN.Fischer,RichardJ.LeBlanc.CraftingaCompilerwithC.PearsonEducation,1991授課題目第一章編譯引論授課學時 2 授課時間教學重點、難點：本章從總體上概要介紹編譯相關的原理和技術以及典型編譯器的邏輯結構， 使學生對編譯程序有一個初步的認識。本章重點和難點為各基本概念的理解和對整個編譯程序各個階段所承擔任務的理解和掌握。教學要點： 本章需要學生掌握如下內容：.實現高級語言的編譯方式和解釋方式及其區別。編譯方式：對整個源程序進行分析，翻譯成等價的目標程序，翻譯的同時做語法檢查和語義檢查。然后再運行目標程序。解釋方式：一個語句一個語句的讀入源程序，邊翻譯邊執行，在翻譯過程中不產生目標程序。解釋方式特別適合于交互式語言；而且解釋方式允許程序執行時改變自身，比如調試程序。這種情形編譯程序不易勝任，因為它需要動態編譯，而解釋程序可以毫無困難的勝任；此外，解釋程序不依賴于目標機，因為它不生成目標代碼，可移植性優于編譯程序。但是和編譯程序相比，解釋程序開銷大，運行速度慢得多。解釋方式和編譯方式的最根本區別在于：在解釋方式下，并不生成目標代碼程序，而是直接執行源程序本身。.典型編譯器的各個組成部分以及各個部分所承擔的任務。a.詞法分析階段詞法分析的任務是掃描源程序的 ASCII碼序列，識別出一個個具有獨立意義的最小語法單位， 即單詞.b.語法分析階段語法分析的任務是根據程序設計語言的語法規則， 把詞法分析的結果分解成各種語法單位， 同時檢查程序中的語法錯誤。c.語義分析階段這一階段的任務是對語法分析所識別出的各類語法范疇，分析其含義，并進行靜態語義檢查。d.中間代碼生成在進行了上述的語法分析和語義分析階段的工作后，編譯程序將源程序變成一種內部表示形式 ^e.中間代碼優化此階段的任務是對前階段產生的中間代碼在不改變源程序語義的前提下進行加工變換， 使生成的代碼更為高效，縮短運行時間或節省存儲空間。f.目標代碼生成這一階段的任務是把中間代碼變換成特定機器上的機器指令代碼或匯編指令代碼。g.表格管理編譯程序在對源程序的分析過程中， 需要創建和管理一系列的表格，以登記源程序的各類信息和編譯各階段的進展情況。.遍具體實現上，受不同源語言、設計要求和計算機硬件條件的限制，往往將編譯程序組織成若干遍(Pass)。所謂“遍”就是對源程序或源程序的中間表示形式從頭到尾掃描一次，并作加工處理，生成新的中間結果或目標程序。既可以將編譯過程中的幾個不同階段合為一遍， 也可以把一個階段的工作分為若干遍。例如，詞法分析這一階段可以作為單獨的一遍，但更多的時候是把詞法分析程序作為語法分析程序的子程序來加以調用，將詞法分析階段和語法分析階段合并為一遍。.前端和后端概念上，我們有時把編譯程序劃分為編譯前端和編譯后端。前端主要由與源語言有關但與目標機無關的那些部分組成。編譯前端通常包括詞法分析、語法分析、語義分析、中間代碼生成，與目標機無關的中間代碼優化部分也可包含在前端 ，當然前端也包括相應部分的錯誤處理。編譯后端包括與目標機有關的中間代碼優化部分和目標代碼生成等。一般來說，這些部分與源語言無關而僅僅依賴于中間語言。很明顯編譯后端是面向目標語言的，而編譯前端則不是，它幾乎獨立于目標語言。.編譯程序的實現一般開發編譯程序有如下幾種可能途徑：a.轉換法(預處理法)：假如我們要實現L語言的編譯器，現在有L'語言的編譯器，那么可以把L語言程序轉換成L'語言的程序，再利用L'語言的編譯器實現L語言，這種方法通常用于語言的擴充。如對于C++語言，可以把C++程序轉換成C程序，再應用C語言的編譯器進行編譯，而不用重新設計和實現 C++編譯器。常見的宏定義和宏擴展都屬于這種情形。b.移植法：假設在A機器上已有L語言的編譯程序，想在B機器上開發一個L語言的編譯程序。這里有兩種實現方法：實現方法一：最直接的辦法就是將 A機的代碼直接轉換成B機代碼。實現方法二：假設A機和B機上都有高級程序設計語言W的編譯程序，并且A機上的L 語言編譯程序是用W語言寫的，我們可以修改L編譯程序的后端，即把從中間代碼生成 A機目標代碼部分改為生成B機的目標代碼。這種在A機上產生B機目標代碼的編譯程序稱為交叉編譯程序(CrossCompiler)。c.自展法：實現思想：先用目標機的匯編語言或機器語言書寫源語言的一個子集的編譯程序，然后再用這個子集作為書寫語言，實現源語言的編譯程序。通常這個過程會分成若干步，像滾雪球一樣直到生成預計源語言的編譯程序為止。我們把這樣的實現方式稱為自展技術。 使用自展技術開發編譯器要求這種高級語言必須是能夠編譯自身的。d.工具法：70年代隨著諸多種類的高級程序設計語言的出現和軟件開發自動化技術的提高，編譯程序的構造工具陸續誕生，如70年代Bell試驗室推出的LEX,YACC至今還在廣泛使用。其中LEX是詞法分析器的自動生成工具，YACC是語法分析器的自動生成工具。然而，這些工具大都是用于編譯器的前端，即與目標機有關的代碼生成和代碼優化部分由于對語義和目標機形式化描述方面還存在困難， 雖有不少生成工具被研制，但還沒有廣泛應用。e.自動生成法：如果能根據對編譯程序的描述，由計算機自動生成編譯程序，是最理想的方法，但需要對語言的語法、語義有較好的形式化描述工具，才能自動生成高質量的編譯程序。目前，語法分析的自動生成工具比較成熟，如前面提到的YACC等，但是整個編譯程序的自動生成技術還不是很成熟， 雖然有基于屬性文法的編譯程序自動生成器和基于指稱語義的編譯程序自動生成器，但產生目標程序的效率很低，離實用尚有一段距離，因此，要想真正的實現自動化，必須建立形式化描述理論。

第二章語言和文法授課題目授課學時授課時間教學重點、難點：第二章語言和文法授課題目授課學時授課時間文法的定義和分類；短語和句柄；x的子字符串，簡稱子串。如果x的子字符串，簡稱子串。如果AB={xy|(xCA)A(yCB)},運算結果仍然表示符號串的集合。例3設A={a,bc},B={de,f},則AB={ade,af,bcde,bcf}注意有{e}A=A{}=A,A=a=，其中為空集。符號串集合的乘積一般不滿足交換律。定義9符號串集合的方哥設A是符號串集合，則稱Ai是符號串集合A的方哥，其中i是非負整數。具體定義如下:A0={}A1=AA2=AAAn=AA……A(n個A)定義10符號串集合的正閉包設A是符號串集合，則稱A+為符號串集合A的正閉包。其具體定義如下：A+=A1UA2UA3…定義11符號串集合的星閉包：設A是符號串集合，則稱A+為符號串集合A的星閉包。其具體定義如下：A*=A0UA1UA2UA3…星閉包又稱自反閉包或克林閉包。由定義顯然有A+=AA*。例4設A={ab,cd},則A+={ab,cd,abab,abcd,cdab,cdcd,ababab,ababcd,} …A*={,ab,cd,abab,abcd,cdab,cdcd,ababab,ababcd, …}定義12文法(grammar)一個文法G是一個四元組G=(Vn,Vt,S,P)其中：Vt是一個非空的有限集合，它的每個元素稱為終極符號或終極符，一般用小寫字母表示。 從語法分析的角度看，終極符號是一個語言不可再分的基本符號。Vn是一個非空的有限集合，它的每個元素稱為非終極符號或非終極符，一般用大寫字母表示。非終極符是一個語法范疇，表示一類具有某種性質的符號，它不出現在句子中。設V是文法G的符號集，則有V=VnUVt,VnAVt=，即Vn和Vt的交集為空。S是一個特殊的非終極符號，稱為文法的開始符號。 SeVn。P是產生式的有限集合。所謂的產生式，也稱為產生規則或簡稱為規則，是按照一定格式書寫的定義語法范疇的文法規則。2.文法分類一個文法的核心是產生式集合，它決定了文法所產生的語言。根據產生式所受的限制不同，喬姆斯基將文法分為四類，四類文法對應四種類型的語言，通常稱之為喬姆斯基體系。0型文法(短語型文法)如果對文法G中的任一產生式 不加任何限制，則稱G為0型文法或短語型文法。其中，、是符號串。1型文法(上下文相關文法)如果對文法G中的任一產生式均限制為形如：A其中ACVn,,C(VtUVn)*,C(VtUVn)+,則稱文法G為1型文法或上下文相關文法。c.2型文法(又稱上下文無關文法)如果對文法G中的任一產生式均限制為形如：A其中A€Vn,C(VtUVn)*則稱G為2型文法或上下文無關文法。在2型文法中，用取代非終極符A時，與A所在的上下文無關，所以稱之為上下文無關文法。例2.5文法G:SaSb|ab容易驗證，G為2型文法，G產生的語言為：L（G尸{anbn|n>1}例2.6文法G:SaPd|abcdPbPc|bc容易驗證，G為2型文法，G產生的語言為：L（G）={anbmcmdn|m,n>1}d.3型文法（又稱線性文法、正則文法、正規文法）如果對文法G中的任一產生式均限制為形如： AB或A其中A,BCVn,CVt則稱文法G為3型文法。上述形式的3型文法也稱為右線性文法， 3型文法還有另一種形式，稱為左線性文法。 如果對文法G中的任一產生式均限制為形如： AB或A其中A,BCVn,CVt這樣的3型文法稱為左線性文法。例2.8文法G:SS0|03.短語和句柄：定義13短語設G是一部文法，S是G的開始符號，是文法G的一個句型，如果有：S*A并且A+則稱是句型 的相對于非終極符A的短語。定義14直接短語（簡單短語）設G是一部文法，S是G的開始符號， 是文法G的一個句型，如果有：S*A并且A則稱是句型 的相對于非終極符A的直接短語。直接短語也稱為簡單短語。定義15句柄一個句型的最左直接短語稱為句柄。例9設有文法G:ScAdAab|a對于符號串$=cabd,顯然存在推導ScAdcabd則ab是句型cabd相對于A的短語，也是相對于A的直接短語；同時ab也是句型cabd的句柄。授課學時授課時間教學重點、難點:.授課學時授課時間教學重點、難點:.用語法樹表示推導.文法二義性授課題目第二章語法樹和文法二義性授課題目教學要點:.語法樹與文法二義性定義語法樹設G是給定的文法，稱滿足下列條件的樹為 G的一棵語法樹。a.每個節點都標有G的一個文法符號，且根節點標有初始符 S,非葉節點標有非終極符。b.如果一個非葉節點A有n個兒子節點Bi,B2,…Bn(按從左到右順序)，則AB1B2…Bn-一定是G的一■個廣生式。語法樹是推導過程的圖形表示，這種表示方式有助于理解一個句子語法結構的層次。在推導的過程中，當某個非終極符被它的某個候選式所替代時，這個非終極符的相應節點就產生出下一代的節點，候選式中每個符號依次對應地標記了新產生的節點， 每個新節點和父節點之間都有線段相連接。在一棵語法樹生長的任何時刻， 所有那些葉節點上所標記的符號按照從左到右的次序排列起來就是這個文法的一個句型，樹的生長過程就是這個句型的推導過程。例如，對于表達式文法 G:E-E+E|E*E|(E)|i，符號串i+i*i 顯然是此文法的合法句型，這個句型的最左推導過程是：EE+Ei+Ei+E*Ei+i*Ei+i*i這是句型i+i*i的最左推導序列，這個推導過程的每一步均可用語法樹表示，如圖2.1所示。

EEEEEE句型i+i*i最左推導過程的語法樹表示對于句型i+i*I,還可以使用最右推導或既非最左又非最右的推導，同樣可以給出其推導過程并用語法樹表示。對比這些結果可以發現，如果推導方式不同，得到的推導序列就不同，語法樹的生長過程也不同。也就是說，一棵語法樹包含了一個句型的多種可能的推導過程，包括最左和最右推導，從語法樹本身看不出推導的次序。這樣的一棵語法樹是這些不同推導過程的共性抽象。那么如果使用一種確定的推導方式，比如最左推導（或最右推導） ，一個句型的最左推導是否一定唯一呢？也就是這個句型所對應的語法樹是否只有唯一的一棵呢？對于上面提到的表達式文法，它的句型 i+i*i就存在另一種完全不同的最左推導：EE*EE+E*Ei+E*Ei+i*Ei+i*i這個最左推導所對應的語法樹如圖 2.2所示。.文法二義性定義文法二義性對一個文法G,如果至少存在一個句子，有兩棵(或兩棵以上)不同的語法樹，則稱該句子是二義性的。包含有二義性句子的文法稱為二義性文法，否則，該文法是無二義性的。根據定義2.20和上面的討論，句子i+i*i存在兩個不同的最左推導，顯然它是二義性的，因此表達式文法G:E-E+E|E*E|(E)|i是二義性文法。值得指出的是，文法的二義性和語言的二義性是兩個完全不同的概念。并非由于文法的二義性，語言就有二義性?？梢杂袃蓚€文法 G和G,一個有二義性，另一個沒有二義性，但卻有L(G尸L(G'),即這兩個文法是等價的，它們所產生的語言相同。因此，我們在實際應用中，可以對文法進行等價變換，以消除文法中的二義性。例如表達式文法 G:『E+E|E*E|(E)|i,可以通過人為規定 “*”的優先級高于“+”的優先級，并且都遵從左結合，就可以構造出與之等價的無二義性文法G:授課題目 第二章文法的等價變換授課學時2授課時間教學重點、難點:.直接左遞歸和間接左遞歸的消除;.空產生式消除；教學要點：.拓廣變換 在LR類語法分析中，為了便于控制分析過程的結束，通常要求文法具有唯一的開始符并且開始符不出現于產生式的右部。如果原文法不滿足該條件，需要對原文法進行等價變換，因此，我們引入如下定理：定理2.1對任一文法Gi都可以構造文法G2,使得L(Gi)=L(G2),且G2有這樣的特點，即文法的開始符唯一并且不出現于任何產生式的右部。證明：假設S是Gi的開始符，則只要在Gi中擴充一條新產生式ZS即可，其中Z是新的開始符。另這樣擴充后的文法為 G2,則它顯然滿足定理的要求。.去空產生式：定理2.2對于任一文法Gi( L(Gi)),可構造文法G2,使得L(Gi)=L(G2),并且G2中無空產生式。證明：根據Gi,構造G2的方法如下：(i)令={A|A}，即表示文法Gi中所有右部為的產生式的左部非終極符。(2)遞歸擴充直到收斂為止，即={A|A+, +}。(3)從Gi中刪除所有空產生式。(4)從Gi中刪除只能導出空串的非終極符。(5)對于文法中任意產生式 AXiX2…Xi-iXiXi+i…Xn,Xi(i=i,2,…,n)有三種情況：若XiVt,不做動作；若XiVt-,不做動作；若Xi ，補充規則AXiX2Xi-iXi+iXn；重復這個過程，直到不出現新的產生式為止。例設有如下文法AaBcDBb|DBB|d消除該文法中的空產生式。解：={B,D},根據算法中第3步可以增加下列產生式AacDAaBcAacAB去掉文法中的空產生式 B,得到新的文法如下AaBcD|acD|aBc|acBbDBB|B|d.消除不可達產生式：定理2.3對任一文法Gi都可以構造文法G2,使得L(Gi)=L(G2),并且G2中的每個非終極符必出現在它的某個句型中。證明：根據Gi,構造文法G2的方法如下：(1)令={Z|Z是文法的開始符}。(2)遞歸擴充直到收斂為止，即={B|AxByGi,BVn,A}。(3)若一個產生式左部非終極符 A,則刪除以A為左部的所有產生式。.去公共前綴：公共前綴表示A的不同產生式的右部具有相同的前綴， 這種情形不滿足自頂向下的語法分析條件。這時可用提取左因子的方法消除產生式的公共前綴。假定關于A的規則是：A1|2|???|n|1|2|???|m(其中每個不以開頭)那么，可以把這些規則寫成AA1|2|?…仙丫A l|2| |n經過反復提取左因子，就能夠把每個非終極符所有產生式的首符集變成兩兩不相交。例2.7在Pascal語言中，語句和表達式的產生式都有公共前綴：Stmid:=ExpStmid(ExpL)ExpLExpExpLExp,ExpL其中第二個產生式表示過程調用語句。這時可通過提取左因子法消除公共前綴得到下面產生式：StmidStm'Stm':=ExpStm'(ExpL)ExpLExpExpL'ExpL',ExpExpLExpL'.消除遞歸：如果文法中的某個非終極符 A有推導A +A…，則稱A左遞歸。左遞歸情形，一定使得自頂向下的語法分析分析條件不成立。首先考慮直接的左遞歸，下面是其中一例：AAa|A3消除產生式中的直接左遞歸是比較容易的。一般情形，假定有產生式：AA1|A2|…|An|1|2|…|n其中，每個都不等于，每個都不以A開頭，那么有下面的產生式：AA(1|2|…|n)|(1|2|…|n)若令=1|2|…|n,=1|2卜1n,則可簡化成下面產生式AAa|3即有A3aa…(。至少有一個a)。顯然它可以用下面產生式定義Aa’A'A|再把和分別替換成1|2|…|n和1|2|…|n,則可得下面的產生式A(1|2|---|n)A'A'(1|2|…|n)A'|使用這個辦法，我們容易把文法中所有直接左遞歸都消除掉， 但這并不意味著已經消除整個文法的左遞歸性。例考慮下面文法：SQc|cQRb|bRSa|a雖不具有直接左遞歸，但S、Q、R都是左遞歸的，例如有SQcRbcSabc如何消除一個文法的一切左遞歸呢？消除一般左遞歸的主要思想是切斷環路。 以防止左遞歸。如果一個文法不含回路(形如P*P的推導)，也不含以為右部的產生式，那么，消除左遞歸的算法如下：(1)把文法G的所有非終極符按任意一種順序排列成 P1,P2…Pn；按此順序執行；(2)FORi:=1TOnDOBEGINFORj:=1TOi-1DO把形如PiPj的規則改寫成Pi 1|2 [???| k,其中Pj 1| 2|…| k是關于Pj的所有規則；消除關于Pi規則的直接左遞歸；END(3)化簡由(2)所得的文法。即消除那些不可到達的非終極符的產生式規則。例如，考慮例4.5的文法，令它的非終極符的排序為 R、Q、So對于R,不存在直接左遞歸。把R代入到Q的有關產生式后，我們把Q的規則變為QSab|ab|b現在的Q同樣不含直接左遞歸，把它代入到 S的有關產生式后，S變成SSabc|abc|bc|c經消除S的直接左遞歸后，我們得到整個文法為SabcS'|bcS'|cS'S'abcS'|QSab|ab|bRSa|a顯然，其中關于Q和R的規則是多余的。經化簡后所得的文法是：SabcS'|bcS'|cS'S'abcS'|注意，由于對非終極符排列順序的不同，最后所得的文法在形式上可能不一樣。但不難證明，它們都是等價的。例如，若對上面文法的非終極符排序為 S、Q、R,那么，最后所得的無左遞歸的文法是：SQc|cQRb|bRbcaR'|caR'|aR'R'bcaR'|顯然，兩個文法是等價的。授課題目 第二章有限自動機授課題目 第二章有限自動機授課學時 2 授課時間教學重點、難點：1確定有限自動機2非確定有限自動機3非確定有限自動機確定化教學要點:1.確定有限自動機(FA)一個確定有限自動機 M是一個五元組：M=(S,2,f,So,Z),其中：S:是一個有限集合，它的每個元素稱為一個狀態。2：是一個有窮字母表，它的每個元素稱為一個輸入字符。f:是狀態轉換函數，它是一個從 SXN到S的單值全映射。F(S,a)=S'意味著：當前狀態為S輸入字符為a時，自動機將轉換到下一狀態 S"我們稱S，為S的一個后繼狀態。So：So€S,是確定有限自動機唯一的初始狀態(也稱為開始狀態) 。Z:ZS,是終止狀態(也稱為接受狀態)集合。例設有DFAM=({0,1,2,3},{a,b,c},f,{0},{3})其中f定義為：f(0,a)= 1 f(0,b)=4f(1,a)= 4 f(1,b)=2f(2,a)= 3 f(2,b)=4f(3,a)= 3 f(3,b)=3f(4,a)= 4 f(4,b)=4此DFA對應的狀態轉換圖如圖所示。a,ba,bab0141422343*334442.非確定有限自動機：定義非確定有限自動機一個非確定有限自動機M是一個五元組M=(S,2f,So,Z),其中：S:是一個有限集合，它的每個元素稱為一個狀態。2：是一個有窮字母表，它的每個元素稱為一個輸入字符。f:是狀態轉換函數，它是一個從SXt到S的子集的映射，即SXt-2s.注意這里的后繼狀態不是單一的一個狀態，它是狀態集 S的子集。So:SoS,是非空初態集。Z:ZS，是終止狀態集。對于非確定有限自動機，同樣也可以用狀態轉換圖和狀態轉換矩陣來表示。例設有NFAM= ({0,1,2},{a,b},f,{0},{2})其中f定義為：f(0,a尸{0,1} f(0,b尸{0}f(1,a尸 f(1,b尸{2}f(2,a尸{2} f(2,b尸{2}此NFA對應的狀態轉換圖如圖 2.6所示。a,b圖2.6NFAM的狀態轉換圖此NFA對應的狀態轉換矩陣如圖所示。aB0{0,1}{0}1j{2}2*{2}{2}NFAM的狀態轉換矩陣3.非確定有限自動機和確定有限自動機的等價性。對任何一個NFAM,都存在一個DFAM,使得L(M'尸L(M)首先定義兩個閉包：.設I是NFAM的狀態集的子集，定義I的閉包_CLOSURE(I)為：a.若qCI，貝Uq6_CLOSURE(I)b.若qCI,那么從q出發經任意條e弧而能到達的任何狀態 q'都屬于_CLOSURE(I)。.設I是NFAM的狀態集的子集，aC匯，可以定義狀態子集IaCS,對任一sjCa,必有sCI,使得Si和sj之間存在一條由s指向sj的有向弧，弧上的標記字符恰為 a。Ia=_CLOSURE(J)其中，J是那些可從I中的某一狀態節點出發經過一條 a弧而能到達的狀態節點的全體。然后對給定的NFA按照如下的步驟進行確定化：(1)構造一張表，共有區|+1歹U,第一列為狀態子集I,然后對每個aC匯分別設一列Ia；(2)第一行第一列的狀態子集為 I為CLOSURE(s0),其中S0為初始狀態；

(3)為第一列中的I和每個kC匯求Ik,并記入相應的Ik歹U。如果它和表格第一列中的所有狀態子集均不相同，則此表生成一個新行，將它填入新行的第一列中。(4)重復步驟(3),直到對每個I和kC匯均已求得Ik,且不再生成新的狀態子集為止。此過程在有限步內一定可以終止，因為如果 |S|=n,則狀態子集最多只有2n個，上述表最多只有2n行；(5)將第一列中的每個狀態子集重命名為新的狀態，則上述表格便成為新的狀態狀換矩陣。例設有NFAM=({1,2,…9},{a,b},f,{1},{6,7,9} )其中f如圖2.8所示.NFAM的狀態轉換圖對此NFAM的狀態轉換圖對此NFA我們首先構造一張表，表的每一行含有置為s__CLOSURE(s0),這里為e__CLOSURE(1)={1然后我們開始計算表中其它單元格的值。一般而言,①|+1歹U。將表的第二行的第一列處單元格的值2}。如果某一行的第一列中的狀態子集已經確定,記為I,那么對kC匯求人,并記入這一行相應的Ik列。然后我們檢查這一行所有的狀態子集 Ik,看它們是否已經在表的第一列中出現過，如果某一個 Ik沒有出現過，則在此表的最下面生成一個新行，將它填入新行的第一列中。重復上述的過程，直至所有已生成的 Ik均已在表的第一列中出現過。這種 NFA確定化的方法稱為子按照子集法NFAM進行確定化構造出的狀態轉換矩陣表如圖所示。IIaIb{1,2}{2,4,5,6,7}{3,8}{2,4,5,6,7}{3,9,8}{3,8}{9}{3,9,8}{9}{9}對NFAM進行確定化構造出的狀態轉換矩陣表對表格的狀態子集進行重命名，分別用1、2、3、4、5來代表{1,2}、{2,4,5,6,7}、{3,8}、{3,9,8}、{9}這五個狀態子集，形成如圖 2.10所示的狀態轉換矩陣，它即是和NFAM等價的DFAM。IAb1232*4354*55*和NFAM等價的DFAM授課題目 第二章正則表達式授課學時2授課時間教學重點、難點:.正則表達式和正則集；.正則表達式和有限自動機相互轉化;教學要點：正則表達式和正則集設匯為有限字母表，在匯上的正則表達式和正則集可遞歸定義如下：(1)和是匯上的正則表達式，它們表示的正則集分別為 {&}和；(2)對任何aCE,a是匯上的正則表達式，它所表示的正則集為 {a};(3)若r,s都是正則表達式，它們表示的正則集分別為 R和S,則(r|s)、(r?s)、(r)*也是正則表達式，它們分別表示的正則集是： RUS,RS和R*。(4)有限次使用上述三條規則構成的表達式，稱為匯上的正則表達式，僅由這些正則表達式表示的集合稱為正則集。正則表達式的運算符“「讀作“或”，“？”讀作“連接”，“*”讀作“閉包”(即任意有限次的自重復連接)。在不至于引起混淆時，正則表達式中的括號可以省略不寫，連接符“? ”一般也可以省略不寫，但規定算符的優先順序為：先“ *”，次“？”，最后“|”，且規定它們的結合性為左結合。定理2.6對匯上的每一個正則表達r,存在一個匯上的非確定有限自動機 M,使得L(M)=L(r)。證明：1.對于字母表匯上的任意一個正則表達式 R,一定可以構造出一個非確定有限自動機 M,使得L(M)=L(R)。首先構造此非確定有限自動機M的初始狀態轉換圖，其中只有開始狀態 S和終止狀態Z,由S射出指向Z的有向弧上標記正則表達式R,然后按照圖2.13所示的替換規則對正則表達式R依次進行分解，分解過程中不斷加入新的狀態節點和有向弧， 直至狀態轉換圖中所有有向弧上標記的符號都是字母表匯上的元素或為止。⑴GFYD替換為 Q-HO-RKB)Ri⑵ G)-R|R**^B)替換為G) G)R2(3) 0-R1-XB)替換為Ri轉換規則1例 有正規表達式(a|b)*aa,為之構造等價的NFA。構造過程如圖所示由正則表達式構造等價NFA2.同樣，對于字母表匯上的非確定有限自動機 M,也可以在匯上構造相應的正則表達式 R,使得L(R)=L(M)。首先，對非確定有限自動機 M的狀態轉換圖進行拓廣，即令每條弧可以用一個正則表達式標記。然后在M的狀態轉換圖中加入兩個節點，一個是唯一的開始狀態節點 S,另一個是唯一的終止狀態節點 Z。從S出發用標有e的有向弧連接到M的所有初始狀態節點上，從 M的所有終止狀態節點用標有e的有向弧連接到Z節點，形成一個與M等價的M接著，對M按照圖2.15所示的替換規則進行替換，也就是不斷消去原有的節點和有向弧，當狀態轉換圖中只剩下節點 S和Z時，在S指向Z的有向弧上所標記正則表達式就是所求的結果。⑴替換為替換為。R11RF替換為。R11RFRi替換為。…rr。轉換規則2例有如圖2.16所示的NFAM,試構造與之等價的正則表達式NFAM先對NFA的狀態轉換圖進行拓廣，然后按照圖所示的轉換規則，逐步消去自動機中的節點和弧，直至狀態轉換圖中只剩下開始狀態 S和接受狀態Z為止，此時S和Z之間弧上標記的正則表達式即為所求。轉換過程如圖所示。作業安排：課后作業：4,6,8(1、3授課題目 第三章 詞法分析程序的設計授課學時 1學時 授課時間詞法分析程序的兩種接口形式；單詞分類及其內部表示形式；單詞的形式化描述；自動機的實現方法。教學要點:詞法分析介紹功能讀源程序的字符序列，逐個拼出單詞，并構造相應的內部表示TOKEN,同時檢查源程序中的詞法錯誤.單詞所謂單詞是指語言中具有獨立含義的最小的語義單位。Token單詞的內部表示。編譯程序總是用某種程序語言書寫的程序，語言的操作對象只能是該語言規定的各種數據。而編譯程序的操作對象是程序中的各種語法單位，因此，必須把它們表示成某種數據結構形式。詞法分析程序接口詞法分析程序的設計單詞分類一般常用程序設計語言的單詞可以分為以下幾類1,保留字：保留字一般是由語言系統自身定義的，通常是由字母組成的字符串。2,標識符：標識符一般是由字母開頭，字母、數字或其它符號的任意組合構成的。3,常量：用來表示各種常量。主要包括整數常數、實數常數、字符串常量等。4.特殊符號：包括運算符和界限符。運算符表示程序中算術運算、邏輯運算、字符運算、賦值運算的確定的字符或字符串。單詞內部表示單詞的內部表示TOKEN的結構一般由兩部分組成：單詞類別和語義信息。單詞類別用來區分單詞的不同種類，通?？梢杂谜麛稻幋a來表示。單詞的語義信息也取決于今后處理上的方便。對于常量和標識符還可以單獨構造常量表和標識符名字表， 此時，單詞的語義信息的值就是指向常量表或標識符名字表中相應位置的指針。單詞的形式化描述（正則表達式描述）TOC\o"1-5"\h\z描述程序設計語言中單詞的工具主要有以下三種：正則表達式、自動機和正則文法。它們的功能彼此相當。對于一個一般的程序設計語言，各類單詞的正則表達式可能如下 ：1）標識符：L（L|D）*,其中L=[a-z,A-Z],D=[0-9]2）整數： D1D*,其中D1=[1-9]3）特殊符號： +|;|：|：=|<|<=| …4）保留字： begin|end|while| …

單詞的形式化描述(有限自動機)構造識別單詞的有限自動機的方法與步驟如下：.根據構成規則對程序語言的單詞按類構造出相應的狀態轉換圖。言所有單詞的狀態轉換圖。合并方法為:一個唯一的初始狀態；.合并各類單詞的狀態轉換圖，構成一個能識別語(1)將各類單詞的狀態轉換圖的初始狀態合并為(2)化簡調整狀態沖突和對沖突狀態重新編號；的狀態轉換圖。言所有單詞的狀態轉換圖。合并方法為:一個唯一的初始狀態；自動機的實現(狀態轉換矩陣法)把自動機看作一種數據結構(狀態轉換矩陣) ，由控制程序控制字符在其上運行，從而完成詞法分析。轉換矩陣法的優點是程序短，但占存儲空間多。State:=InitState;Read(CurrentChar);whileT(State,CurrentChar)error&CurrentCharEofdobeginState:=T(State,CurrentChar);Read(CurrentChar);end;fStateFinalStatesthenAcceptelseError;自動機的實現(狀態轉換圖方法)每個狀態對應一個帶標號的 case語句；轉向邊對應goto語句。Li:caseCurrentCharofa: gotoLj;gotoLk;other:Error()endLi：caseCurrentCharofEof:Accept;a: gotoLj;b： gotoL■other:Error()end授課題目第三章詞法分析程序的實現授課題目授課學時1學時授課學時1學時授課時間教學重點、難點：詞法分析程序實現算法；詞法分析程序的自動生成。教學要點：手工實現詞法分析程序實現詞法分析程序應注意的問題保留字識別兩種方法1）設置保留字表事先構造好所謂的保留字表，在進行詞法分析時，把保留字也當作一般標識符來識別，然后查保留字表，若有，則把它作為保留字來處理；若沒有，則按一般標識符來處理。2）自動機單獨識別 在自動機中加入識別各個保留字的狀態，即把保留字和一般標識符分開來識別而不統一識別。復合單詞的識別在程序設計語言中，有一類單詞是由兩個或者兩個以上的符號組成的，這類單詞的前綴部分也可以是一個獨立的單詞。在處理這類單詞時要特別加以注意。數的轉換詞法分析程序應該把字符串轉換成數，如 “123應該轉換成123。向前看若干個字符的處理在有些語言里，為了識別出一個單詞需要向前看好幾個字符。控制字符的處理無用的空格符和制表符要刪掉；字符串內的空格不能刪；換行符不能直接刪除，用于錯誤定位。注釋的處理源程序中的注釋沒有任何語法和語義上的意義，因此在進行詞法分析時可以直接將注釋刪除， 而不必生成其TOKEN。標識符表和常量表?直接在語義信息部分存儲語義信息的長度有限制時，可直接將標識符或常量本身存儲于其 TOKEN中的語義信息部分。?設置標識符表和常量表標識符和常量沒有長度限制時，構造標識符或常量表，語義信息中為其在表中的地址（節省存貯空間）。單詞結構設計

單詞名稱類別編碼助記符輸出形式標識符1$id($id,pID)無符號整數2$int($int,pNB)+20$plus($plus,")'21$semi($semi,")':=22$assi($assi,")':23$colon($colon,")'<=24$le($le,“)’<25$lt($lt, “)’手工構造詞法分析程序確定詞法分析器的接口，即確定詞法分析器是作為語法分析的一個子程序還是作為獨立一遍。確定單詞分類和Token結構。構造每一類單詞的描述正則表達式 NFADFA。設計算法實現DFA。詞法分析器的生成器—Lex功能：依據語言的正則表達式，自動生成該語言的詞法分析程序。執行過程Lex文件輸入格式{declarations}%%{rules}%%{auxiliaryprocedures}授課題目 第四章語法分析程序介紹授課題目 第四章語法分析程序介紹授課學時 2學時 授課時間自頂向下語法分析的基本思想；First集、Follow集、Predict集的求法；教學要點：4.1語法分析程序介紹語法分析程序的功能按照文法，從源程序符號串中識別出各類語法成分，同時進行語法檢查，為語義分析和代碼生成做準備。語法錯誤類別程序的開始單詞錯，表達式的開始單詞錯，語句的開始單詞錯，表達式的后繼單詞錯，語句的后繼單詞錯等等。標識符和常量單詞錯。如域名不是標識符，在 const,type,var,function和procedure等保留字后面不是標識符，枚舉類型中的元素不是標識符等， case語句中的情形分量部分不是所允許的常量等。括號類錯誤。如begin—end不匹配，（一）不配對，［一］不配又case—end不配又if—then—end不配對等。分隔符錯。如賦值語句左部變量后面不是賦值號，標識符表或表達式表的分隔符（或后繼符）錯。語法錯誤處理緊急方式恢復短語級恢復出錯產生式全局糾正自頂向下語法分析基本思想自頂向下分析是從文法的開始符號出發， 試圖為輸入串建立一個最左推導， 或者為輸入串構造一個語法樹。這種分析是通過對當前句型的最左非終極符，反復使用它的不同規則進行替換和展開，以匹配輸入串來實現的。有如下文法G［Z］，假定要分析的句子是abacddZABAabBcd|aBd建立abacdd的一棵語法樹如右圖，說明該句子是文法G［Z］所定義的句子。顯然，對于句子abacdd可以通過如下的推導過程將其推導出來：SABabBabaBdabacddcd三個重要的集合First(3)={Vt|3*a }U(if3*then{}else)在求First(集時要對構成 3的每一文法符號 X計算First(X),因此首先給出求 First(X)的算法要八\、?1)若XVt,則First(X)={X};2)若XVn,則First(X)={a|Xa…PSet,aVt};3)若XVn,且有產生式X ，則{}First(X);4)若XVn,有產生式XYiY2-Yn,且Yi,Y2,…,YVn當Yi,Y2,…,Yi*,則First(Y1)-{},First(Y2)-{},…First(Yi-1)-{},First(Yi)都包含在First(X)中；當Yi *(i=1,2,…n)等{}并入First(X)中。若符號串3=X1X2…Xn,則下面是求First(的算法要點：1)當Xi,X2,…Xi-1 *,Xi不能*0則i1First(3)=(First(Xj)-{})First(Xi)n2)若Xi,Xi，則First(3)=1(First(Xj)Follow(A)={aVT|S +.…Aa..…}u(ifS*……Athen{#}else)求Follow(A)的算法要點：1)對所有AVn,令Follow(A)={}；對開始符S,令Follow(S)={#};2)若有產生式AxBy,?如果First(y)則Follow(B)=(First(y)—{})UFollow(A)?否則，Follow(B尸First(y)3)重復上一步，直至對所有 AVN,Follow(A)收斂為止。Predict(A3=First( B) 當 First( 3)=(First(-{)})UFollow(A),當 First( 3)授課題目 第四章遞歸下降語法分析方法授課題目 第四章遞歸下降語法分析方法授課學時 2學時 授課時間教學重點、難點：自頂向下語法分析的條件；遞歸下降分析程序原理。教學要點：自頂向下語法分析條件假設A的全部產生式為A8(i=1,2,…,n),則有下面的結論：產生式A伙被選擇的條件是當前輸入符屬于 predict(A因；至多有一個產生式被選擇的條件是：predict(A 伙)predict(A 3)=，當kj在實際的程序設計語言中，文法不滿足 LL(1)文法條件的情形主要有下面兩種情形：公共前綴：某個非終極符 A有如下的兩個產生式A,A。左遞歸：某個非終極符A有直接左遞歸產生式AA或間接左遞歸。遞歸下降法語法分析遞歸下降法語法分析原理對文法中每個非終極符 U(代表一種語法成分)都編寫一個子程序，以完成該非終極符所對應的語法成分的分析和識別任務。某個非終極符的語法分析子程序的功能是：用該非終極符的規則的右部符號串去匹配輸入串。分析過程是按文法的規則自頂向下一級一級地分配任務， 即調用有關的子程序來完成。當編譯程序根據文法和當前的輸入符號預測到下一個語法成分為 U時，即預測到待匹配的輸入符號串可以被從U出發所推導出的符號串相匹配時， 就確定U為目標，并調用分析和識別U的子程序。在分析和識別某語法成分的子程序匹配輸入串成功并正確返回時，該語法成分才算真正獲得了識別，并確定輸入串無語法錯誤。遞歸下降法語法分析程序的構造假設文法中有如下的產生式 A1|2|…|n,則應按如下方法編寫語法分析子程序procedureA()beginiftokeniftokenPredict(APredict(Athenthen0(1)else0(2)elseiftokenPredict(An)then0(n)elseerror()end其中對i=X1X2…Xn,0(i)=0'1)(X0'2);(X-；On);(X如果XiVn,0'i)XXi如果XiVt,。'i)XMatch(Xi)如果Xi=,。'(入)=SkWO)遞歸下降語法分析實例假設有如下文法：ZaBaBBbBc則相應的遞歸子程序可如下：procedureZ()beginiftoken=athenMatch(a);B;Match(a)elseerror();cedureB()beginiftoken=bthenMatch(b);B;elseiftoken=cthenMatch(c);elseerror()end;可以寫一個主程序調用文法開始符所對應的子程序進行語法分析。BeginReadToken;Zend.遞歸下降法分析遞歸下降分析法的優點是：程序結構和層次清晰明了，易于手工實現；就語義加工來說，這種方法是十分靈活的，我們可以在過程的任何地方插入有關語義加工程序，進行語義處理，而不一定要在查出短語之后再插入。該方法與那些能使用部分自動化系統的方法相比其主要缺點是需要做更多的編寫程序和調試程序工作。使用本方法時一定要把諸遞歸子程序的接口搞清楚，例如，對于上述文法處理子程序而言，進入每個分析處理子程序時第一個字符已經讀入 token中，而在退出處理子程序時，又讀出了下一個單詞到token中。因此，任何別的遞歸子程序，若要調用這個子程序，都必須遵守這一要求，否則會發生混亂，無法把語法分析進行下去。授課題目第四章LL(1)語法分析方法授課學時2學時授課時間教學重點、難點:LL(1)分析法的基本原理；LL(1)分析表的構造方法；LL(1)驅動程序的構造方法。教學要點：LL(1)分析方法LL(1)分析原理所謂的LL(1)分析方法，表示相應的語法分析將按自左至右的順序掃描輸入符號串，并在此過程中產生一個句子的最左推導；至于括號中的“ 1”，則表示在分析過程中，每進行一步推導，只要向前查看一個輸入符號，便能確定當前所應選用的產生式規則，它是 LL(k)分析法的特例。LL(1)分析條件對于任一非終極符A,其任意兩個產生式A,A,都要滿足下面條件：Predict(A川predict(A)=LL(1)分析程序邏輯結構分析表在邏輯上，一個LL(1)分析器由輸入流、LL(1)分析表、符號棧和驅動程序組成。如下圖所示。分析表a1...ai...an#輸入流LL⑴驅動程序：棧為空情形的處理XVt情形的處理符號棧XVn情的處理符號棧其中:1)輸入流即待分析的符號串，它以定界符" #"作為結尾。在各種分析技術的實現中，總是讓輸入符號串后面緊跟一個“#”標志輸入串的結束。在輸入符號串之前也有標志符號“ #"，LL(1)分析器的驅動程序將把“#”事先壓入符號棧。因此， “#”被稱為左右端標志符號，它不是文法符號，是由分析程序自動添加的。2)分析表T可用一個矩陣(或二維數組)來表示，它概括了相應文法的全部信息。矩陣的每一行對應文法的一個非終極符， 而相應的列則指出該非終極符對某個終極符 (向前看的符號)選擇哪個產生式。分析表中的元素是產生式(編號)或Error,其中Error表示當前的輸入符號不能與相應的非終極符匹配產生錯誤。即分析表元素 T(A,a),AVN,aVTU{#},或者指示了當前推導所應使用的產生式，或者指出了輸入串中含有的語法錯誤。3)符號棧中存放分析過程中的文法符號串，即文法的一個左句型。4)LL(1)分析器對每個輸入串的分析在驅動程序下進行。具體分析時是根據當前輸入符號 ai和分析棧棧頂符號Xi決定所選產生式，按分析表進行相應的操作。LL(1)分析表的構造若用T表示LL(1)分析表，則T可表示如下：T:Vn>VtPU{Error}T(A,t)=Aa,當tpredict(Aa)T(A,t)=Error,否則其中P表示所有產生式的集合。顯然，一個文法 G是LL(1)文法，當且僅當T的元素包含唯一的一個產生式或Error。LL(1)驅動程序構造LL(1)分析的動作LL(1)分析主要包括以下四個動作，其中X為符號棧棧頂元素，a為輸入流當前字符。1)替換：當XVn時選相應產生式的右部 去替換X。2)匹配：當XVt時它與a進行匹配，其結果可能成功，也可能失敗，如果成功則符號棧中將X退棧并將輸入流指針向前移動一位，否則報錯。3)成功：當格局為(空，空)時報告分析成功。4)報錯：出錯后，停止分析。LL(1)驅動程序構造LL(1)驅動程序的算法：.分析開始時，首先將標志符號#和文法開始符號S依次壓入符號棧；輸入流指針指向第一個輸入符號，即由符號棧和輸入流構成的初始格局為：(#S, a〔a2…an#)然后，反復執行第二步所列的工作。.設在分析的某一步，符號棧及剩余的輸入流處于如下的格局(#X1X2…Xm-1Xm, aiai+1...an#)其中，X1X2…Xm-1Xm為分析過程中所得的文法符號，此時，可視棧頂符號Xm的不同情況，分別作如下動作：?若XmVn,則以Xm及ai組成的符號對(Xm,ai)查分析表T。設T(Xm,ai)為一產生式，假設是XmUVW,此時將Xm從分析棧中退出，并將UVW壓入棧中，從而得到新的格局(#XiX2…Xm-1WVU,aa+1...an#)但若T(Xm,ai尸Error,則調用出錯處理程序進行處理；?若Xm=ai#，則表明棧頂符號已經與當前掃描的輸入符號得到匹配， 此時應將Xm(即ai)從棧中退出，并將輸入流指針向前移動一個位置。?若Xm=ai=#,則表明輸入串已經完全得到匹配， 此時即可宣告分析成功而結束分析。?其它情形，轉錯誤處理程序。授課題目 第四章自頂向下分析程序自動生成授課題目 第四章自頂向下分析程序自動生成授課學時 2學時 授課時間自頂向下語法程序自動生成工具 LLGen的輸入輸出;教學要點：4.4自頂向下分析程序的自動生成LLGen的輸入文件LLGen的輸入文件主要由三部分組成， 其每部分由特殊符打頭。 因為LL（1）分析的驅動程序是通用的，因此自動生成器不需要產生此部分，而只需要構造出 LL（1）分析表和文法的內部表示等。所以要構造文法的內部表示，是因為在進行分析時要做出用產生式右部替換非終極符的動作。*fmq＜選擇部分＞*define＜常數定義部分＞"terminals＜終極符定義部分＞"productions＜產生式定義部分＞*end前面和后面可有〈注釋部分〉。選擇部分由*fmq開始，其主要功能是控制輸出信息。其中可列出 LLGen所規定的幾種選擇名，其具體名和含義分別如下： bnf（輸出文法規則）；first（輸出first集）；follow（輸出follow集）；parstable（輸出分析動作表）；vocab（輸出文法符號）；text,binary（以文本或二進制形式輸出信息）。常數定義部分可有也可無。*define之后是常數定義表， 而每個常數定義由常數名和無符號整數組成，其中每個常數定義占一行。終極符定義部分由*terminals開頭，此后是終極符表，其中每個終極符占一行。終極符在表中的序號作為其序號。產生式定義部分由*productions開頭，此后是產生式表，其中每個產生式占一行。產生式的一般形式是〈左部＞:=＜右部＞，但允許不出現其中的〈左部〉和〈右部＞,具體細節不再贅述。結束部分由*end表示，其作用是使得LLGen系統完成所要做的補充工作。LLGen的輸出信息終極符個數、產生式個數等信息；產生式右部的長度；LL（1）分析表；可導出空串的符號表；文法中所有符號的內部表示；如果文法不是LL（1）文法，則報告所有沖突部分。自頂向下語法分析典型例題構造文法G[E]的LL（1）分析表，并給出句型i+i*i#的分析過程。產生式如下：ETE'(1)E'+TE'(2)I(3)TFT'(4)T'*FT'(5)作業安排：課后作業：5作業安排：課后作業：5TOC\o"1-5"\h\z| (6)F (E) ⑺|i (8)解：1)首先求各個產生式的 predict集合如下表:產生式Predict集1ETE'{(,i}2E'+TE'{+}3E'{#,)}4TFT'{i,(}5T'*FT'{*}6T'{+,),#}7F(E){(}8Fi{i}2)構造該文法的LL(1)分析表如下:i+*()#E11E，233T446566F873)句型i+i*i#的分析過程如下表分析棧輸入流矩陣兀素#Ei+i*i#T[E,i]=1#E'Ti+i*i#T[T,i]=4#E'T'Fi+i*i#T[F,i]=8#E'T'ii+i*i#Match#E'T'+i*i#T[T',+]=6#E'+i*i#T[E',+]=2#E'T++i*i#Match#E'Ti*i#T[T,i]=4#E'T'Fi*i#T[F,i]=8#E'T'ii*i#Match#E'T'*i#T[T',*]=5#E'T'F**i#Match#E'T'Fi#T[F,i]=8#E'T'ii#Match#E'T'#T[T',#]=6#E'#T[E',#]=3##成功授課題目 第五章授課題目 第五章5.3LR分析法5.3.1LR類分析法的工作過程 5.3.2LR(0)分析方法(1)作業安排：章末統一安排作業安排：章末統一安排授課題目 第五章授課題目 第五章5.1自底向上語法分析方法介紹； 5.2簡單優先分析方法作業安排：章末統一安排作業安排：章末統一安排授課學時教學重點、難點：重點：通過一個簡單文法及對該文法某句子的推導實例，使學生了解自底向上語法分析方法的分析過程，掌握該方法的基本思想（即移入-歸約），明確幾點：①規范歸約過程與最右推導過程相逆②句柄出現在棧頂③如何確定一個句型的句柄，是自底向上語法分析方法的關鍵，即：不同的識別句柄的方法決定了不同的自底向上分析法。此外，介紹最簡單的自底向上方法一一簡單優先分析法，主要講簡單優先算法和優先關系矩陣的構造。難點：理解句柄的概念及確定句柄的時機（不同時刻有不同的中間句型，也就有不同的句柄，即動態性）教學要點：1、歸約-推導實例的選擇：即選取簡單文法、文法的代表性句子，明確歸約和推導的關系。例：文法G[S]:SaAcBeAbAAbBd可選G[S]的句子：abbcde則Abbcde的最左歸約和最右推導過程：Abbcde的最左歸約過程S

aAcBe

aAcde

aAbcde

abbcdeAbbcde的最右推導過程Abbcde的最左歸約過程S

aAcBe

aAcde

aAbcde

abbcdeAbbcde的最右推導過程2、設定分析棧，明確移入-歸約過程，在分析過程中理解句柄等概念。#abbcde##ab3、簡單優先分析算法及優先關系矩陣構造授課學時 2教學重點、難點：重點：使學生理解LR(K)語法分析方法的思想、分析過程，明確LR(K)分析器的邏輯結構(4部分)和分析器的四個基本動作；掌握 LR(0)分析法的過程、基本概念與術語，即規范句型、規范前綴、規范活前綴、歸約規范活前綴等難點：理解LR(K)的K,理解用四種分析動作完成對句型分析的全過程，在移入 -歸約的過程中理解規范前綴、規范活前綴、歸約規范活前綴等概念及作用；教學要點：1、LR(K)分析器的邏輯結構:TOC\o"1-5"\h\zInputai...ai... an #?Il。什??」St Xt V二LR分析驅動程序 OOutputS0|# uStack actiongoto圖5.2LR分析器的邏輯結構圖2、四種分析動作：移入、歸約、成功、報錯的真實含義3、用格局來描述LR分析過程：查表獲得動作，執行動作完成格局轉變4、LR(0)分析法的基本概念：說明規范前綴、規范活前綴、歸約規范活前綴的定義，并通過一個簡單文法及其一個簡單句子的歸約過程理解這 3個概念的動態性，即與各個中間句型的形成密不可分。授課題目 第五章授課題目 第五章5.3.2 LR(0)分析方法(2)授課學時 2教學重點、難點：重點：派生定理及其意義；幾個定義： LR(0)項目(歸約項目、移入項目)，LR(0)項目集的投影，LR(0)項目的閉包，GO函數，LR(0)文法等；LR(0)歸約活前綴狀態機(LRSM°)的構造算法及其意義(活前綴狀態機提供的重要信息：合法檢查信息、移入 /歸約信息、移入/歸約后的轉向狀態信息)；沖突的概念，即移入-歸約沖突、歸約-歸約沖突難點：理解派生定理及其意義； LR(0)歸約活前綴狀態機(LRSM°)的構造算法及其意義，尤其是歸約后的轉向狀態的問題教學要點：1、派生定理及其意義：①派生定理的概念：開始符產生式的右部是歸約活前綴。如果A是歸約活前綴，且A是產生式，則 也是歸約活前綴。任何歸約活前綴，都可按上述方法被派生。②派生定理的意義：把歸約活前綴的定義性概念轉換為操作性概念，從而為構造活前綴狀態機來識別文法的全部歸約活前綴奠定基礎，對活前綴狀態機的應用，就是將它轉換為 LR分析表，這是分析器的核心。2、由派生定理逐漸過渡到對 LR(0)狀態機的構造，其間介紹LR(0)項目(歸約項目、移入項目)，LR(0)項目集的投影，LR(0)項目的閉包，GO函數，LR(0)文法等概念。3、構造LR(0)狀態機的算法介紹，要求：以具體實例板書求解過程。例：假設有表達式文法G[E]SE$EE+T|TTidI(E)其LR(0)狀態機：4、用格局說明歸約后的轉向狀態的確定舟舟作業安排：章末統一安排目目的活刖綴狀態機作業安排：章末統一安排授課題目 第五章授課題目 第五章5.3.4LR(1)分析方法作業安排：章末統一安排作業安排：章末統一安排授課題目 第五章授課題目 第五章5.3.2LR(0)分析方法(3) 5.3.3SLR(1)分析方法作業安排：章末統一安排作業安排：章末統一安排授課學時 2教學重點、難點：重點：由LR(0)狀態機構造出LR(0)分析表的算法及實例；LR(0)驅動程序；SLR(1)分析方法與SLR(1)文法,即SLR(1)分析表的構造及SLR(1)驅動程序；難點：LR(0)分析表的構造，SLR(1)方法的實質，即為解決LR(0)狀態機沖突而提出的一種解決方案。教學要點：1、由LR(0)狀態機構造出LR(0)分析表的算法及實例(接續上次課的 LR(0)狀態機)2、LR(0)驅動程序3、SLR(1)分析方法：SLR(1)分析表及驅動程序， 注意與LR(0)方法中的不同之處。4、SLR(1)分析方法的具體實例：例：設有文法G[S]:SE$EE+TETTTPTPPidP(E)則由其LR(0)狀態機可得SLR(1)分析表：(板書、講解)，該文法的LR(0)狀態機不板書。StateAction—LookaheadGoTo+id()$#ETP0S5S61741S3S22Acc3S5S61144R5R5R5R55R6R6R6R66S5S612747R3S8R3R38S5S699R4R4R4R410R7R7R7R711R2S8R2R212S3S10授課學時教學重點、難點：重點：SLR(1)分析遇到的問題及原因和解決辦法；四個基本概念； LR(1)-LRSM的算法與實例；從文法的LR(1)狀態機構造LR(1)分析表的方法；難點：SLR(1)分析遇到的問題及原因和解決辦法 (正是LR(1)方法的實質及出發點)；LR(1)狀態機的構造關鍵，即LR(1)項目的展望符求法和作用；授課題目 第五章授課題目 第五章5.3.6LR方法小結5.4自底向上分析程序的自動生成作業安排：課后作業：4,5作業安排：課后作業：4,5授課題目 第五章授課題目 第五章5.3.5LALR(1)分析方法作業安排：章末統一安排作業安排：章末統一安排授課學時 2教學重點、難點：重點：LALR(1)分析方法主要點：①針對LR(1)方法狀態數太多，空間時間效率不高，而提出的解決方法；②合并同心集③LALR⑴狀態機的構造方法有二：合并LR(1)狀態機中的同心狀態集，由LR(0)狀態機通過傳播方式獲得④由 LR(1)狀態機構造LALR(1)狀態機的算法⑤ LALR(1)分析表的構造算法和LR(1)分析表的構造算法一致。 LR(K)分析方法小結。難點：對LR(1)狀態機中的同心狀態集的合并，以及由此可能出現的沖突和不能出現的沖突；教學要點:1、LR(1)方法的問題：狀態數太多，空間時間效率不高，合并某些狀態的可能性以及前后的等價性；2、同心項目、同心狀態集、合并同心狀態集3、由合并同心狀態集獲得LALR狀態機的算法4、由LR(1)狀態機構造LALR(1)狀態表5、具體實例：圖5.9LALR(1)狀態機授課學時 2教學重點、難點：重點：對4種LR(K)方法從如下方面加以比較：分析能力、采用的歸約前綴狀態機的狀態數、實用性；對給定文法，判斷其屬于哪一類 LR文法的常規判斷方法(流程)；介紹幾種語法分析器的自動生成工具，如：YACC/Bison,LALRGen等。難點：對給定文法，判斷其屬于哪一類 LR文法的常規判斷方法；對自動生成方法的理解。教學要點:1、對4種LR(K)方法從如下方面加以比較：⑴分析能力(能分析的文法范圍)：LR(0)<SLR(1)<LALR(1)<LR(1)⑵識別活前綴狀態機的狀態數： LR(0)=SLR(1)=LALR(1)<LR(1)⑶實用性：LR(0)(簡單，對文法限制嚴)；LR(1)實現代價過高；SLR(1)和LALR(1)使用性較好。2、4種文法的常規判斷方法:Begin ')\End2、語法分析器的自動生成工具：如：YACC/Bison、LALRGen等。Bison是一個通用的語法分析器生成器，它讀入一個 LALR(1)上下文無關文法，生成一個用來分析該文法的語法分析器，通常生成的語法分析器是一個 C程序。只要熟練掌握Bison這個強有力的工具,很容易就可以開發出大多數語言的語法分析器。 LALRGen也由類似的功能，接受上下文無關文法的說明書，其說明書主要有三部分組成：運行選項、文法的終極符、文法的產生式規則。授課題目 第六章語義分析概述授課題目 第六章語義分析概述授課學時 2學時 授課時間語義分析的功能及重要性；標識符的內部表示；類型的內部表示；值的內部表示。教學要點:語義分析概述必要性要完成源程序到目標程序的語義等價的翻譯，首先必須保證源程序的語義正確性。因此編譯程序在對源程序進行完詞法分析、語法分析之后，還要對源程序進行語義分析。功能程序設計語言的語義可分為靜態語義和動態語義。編譯階段能確定的語義稱為靜態語義，即不需要執行程序就能確定的語義，或者說從程序文本確定的語義。動態語義是指只有在目標代碼的運行階段才能確定的語義。類型在大多數語言里都屬于靜態語義，而且它是最重要的靜態語義。描述方法靜態語義用屬性文法；動態語義通常是通過抽象機的操作或解釋模型表示。語義形式化方法：①屬性文法和操作語義②指稱語義③公理語義④代數語義內容構造標識符的符號表和進行語義錯誤檢查。實現與語法分析或代碼生成相結合標識符的內部表示構造標識符內部表示的必要性詞法分析程序將源程序分離成一個一個的單詞， 單詞是最小的語義單位。 單詞可分為幾類，其中除了標識符外，單詞的語義信息已經完全表示在相應的 TOKEN中，而標識符則在其TOKEN表示中只有名字信息，并沒有代表其含義的任何其他信息，如類型、存儲地址等。因此，對于每個標識符要構造出表示其含義的屬性記錄，并用某種結構的表(稱之為標識符的屬性表或簡稱符號表) 來記錄每個標識符的含義。有了標識符的屬性表后即可檢查類型、聲明、表達式和語句等復雜成分的語義錯誤。標識符的屬性一般常用程序設計語言的單詞可以分為以下幾類：常量名，類型名，變量名，函數名，過程名，域名TYPEidKind=(consKind,typeKind,varKind,fieldKind,procKind,funcKind)其中除過程外均涉及類型，對于過程情形可以虛設其類型標識符內部表示結構:Z常量標識符D類型標識符變量標識符⑤Z常量標識符D類型標識符變量標識符⑤域名標識符過函標識符consKindTypePtrKindForwardtypeKindTypePtrKindValueTypePtrKindAccessLevelOffvarKind|TypePtrKind OffHostTypefieldKindJypePtrKindLevelParmClasCodSizeForwardroutKind actual標識符內部表示舉例:CONST pai=3.14TYPE vector=ARRAY[1..10]OFinteger:VARx,y：real;r,s：vector設當前層數為L,偏移為0,則標識符pai,vector,x,y,r,s的屬性表示分別是:pai

vectorxyrsrealPtrconsKind3.14pai

vectorxyrsrealPtrconsKind3.14aPtrtypeKindflaserealPtrvarKinddirLevel0realPtrvarKinddirLevel1aPtrvarKinddirLevel11aPtrvarKinddirLevel21類型的內部表示類型的內部表示：?標準類型：intPtr,boolPtr,charPtr,realPtr? 非標準類型：subrange:(size,kind,HostType,Length)Enum:(size,kind,Elems,Length)Array:(size,kind,IndexType,ElementType)Set:(size,kind,BaseType)File:(size,kind,CompType)Pointer:Record:(size,kind,TypeName(size,kind,FixBody,VariantBody)FixBody(id,Type,off,Next)VariantBody(caseunit,variunits)caseunit(id,Type,off)variunits(const,FixBody,VariantBody,Next)總的類型定義：TypeIR=RECORDsize:SizeRange;CASEkind:TypeKindOFintTy :();boolTy:();charTy:();realTy:();enumTy:(Elems:TIdL);subTy :(HostType:TTypeIR;Low:Value;Up:Value);arrayTy:(IndexType:TTypeIR;ElemType:TTypeIR);recordTy:(FixBody:TFixBodyIR;VariBody:TVariBodyIR