《編譯原理》教案-文庫吧

【正文】 基本字不加特殊保護，基本字和用戶自定義的標識符或標號之間沒有特殊的界符作間隔，這就使得基本字的識別甚為麻煩。這里就需要用到超前搜索。 狀態轉換圖 使用狀態轉換圖是設計詞法分析程序(掃描器)的一種好途徑。轉換圖是一張有限方向圖。在狀態轉換圖中，結點代表狀態，用圓圈表示。狀態之間用箭弧連結。箭弧上的標記（字符）代表在射出結(即箭弧始節)狀態下可能出現的輸入字符或字符類。（a）所示。在狀態1下，若輸入字符X，則讀進X，并轉換到狀態2。若輸入字符Y，則讀進Y，并轉換到狀態3。一張轉換圖只包含有限個狀態（即有限個結點），其中有一個被認為是初態，而且實際上至少要有一個終態（用雙圈表示）。（a）狀態轉換圖示例 狀態轉換圖的實現 一個狀態轉換圖可用于識別（或接受）一定的字符。大多數程序語言的單詞符號都可以用轉換圖予以識別。轉換圖非常易于用程序實現，最簡單的辦法是讓每個狀態結點對應一小段程序。下面我們將引進一組全局變量和過程，把它們作為實現轉換圖的基本成分。這些變量和過程是：1. CHAR 字符變量，存放最新讀進的源程序字符。2. TOKEN 字符數組，存放構成單詞符號的字符串。3. GETCHAR 子程序過程，把下一個輸入字符讀到CHAR中，把搜索指示器前移一字節位置。4. GETBC 子程序過程，則GETCHAR直到CHAR中進入一個非空白符。5. CONCAT 子程序過程，把CHAR中的字符連接TOKEN之后。例如，TOKEN原來的值為‘AB39。，而CHAR中存放著39。C39。，經調用CONCAT后，TOKEN的值就變為39。ABC39。6. LETTER和DIGIT布爾函數過程，它們分別CHAR中的字符是否為字母和數字，從爾給出真值TRUE或假值FALSE。 7. RESERVE 整型函數過程，對TOKEN中的字符串查找保留字表，若它是一個保留字則返回它的編碼，否則返回0值(假定0不是保留字的編碼)。8. RETRACT 子程序過程，把搜索指示器回調一個字節位置，把CHAR中的字符置為空白。 正規表達式與有限自動機 正規式與正規集 設Σ是一個有窮字母表，它的每個元素稱為一個字符。Σ上的一個字（也叫字符串）是指由Σ中的字符所構成的一個有窮序列。不包含任何字符的序列稱為空字，記為ε。用Σ* 表示Σ上的所有字的全體 ，空字ε也包括在其中。 例如，若Σ={a，b}，則Σ*={ε,a,b,aa,ab,ba,bb,aaa}下面是正規式和正規集的遞歸定義： 都是 上的正規式，它們所表示 的正規集分別為{ε} 和 Φ；∈Σ，是Σ上的一個正規式，它所表示的正規集為{α}。 上的正規式，它們所表示的正規集分別記為L（U）和L（V），那么，（U V）、（U|V）和（U）*也都是正規式，它們所表示的正規集分別為L（U）200。L（V）、L（U）.L（V）（連接積）和 （L（U））*（閉包）。僅由有限次使用上述三步驟而定義的表達式才是Σ上的正規式，僅由這些正規式所表示的字集才是Σ上的正規集。算符的優先順序為：先*，次.，最后|。例如，令Σ ={a，b} ，下面是 Σ上的正規式和相應的正規集：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)* ： Σ上的標識符的全體 (0|1)(0|1)* ： Σ上的數的全體 若兩個正規式所表示的正規集相同，則認為二者等價。兩個等價的正規式U和V記為U=V。 令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的（單值）部分映照。f（s，a）=s39。意味著：當現行狀態為s，輸入字符a時，將轉換到下一狀態s39。我們把s39。稱為s的一個后繼狀態；4. S0206。S，是唯一的一個初態；5. Z205。S，是一個終態集（可空）。 一個DFA可用一個矩陣表示，該矩陣的行表示狀態，列表示輸入字符，矩陣元素表示f（s，a）的值，這個矩陣稱為狀態轉換矩陣。 例如，有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也可以表示成一張（確定的）狀態轉換圖。對于Σ*中的任何字a，若存在一條從初態結到某一條終態結的道路，且這條路上所有弧的標記符連接成的字等于a，則稱a可為DFA M 所識別（讀出或接受）。若 M的初態結同時又是終態結， 則空字ε可為M所識別（或接受）。上例所定義的DFA M相應的狀態轉換圖如下所示：它能識別Σ上所有含有相繼兩個a或相繼兩個b的字。 狀態轉換圖 非確定有限自動機(NFA) 設一個確定的有限自動機（DFA）M是一個五元式M=(S,Σ,f,S0, Z)其中1. S是一個有限集，它的每個元素稱為一個狀態；，它的每個元素稱為一個輸入字符；3. f是一個從SΣ*到S的子集的映照，即 f：SΣ*174。 2S4. S0205。S，是非空初態集；5. Z 205。S，是一個終態集（可空）。 正規文法與有限自動機的等價性 對于正規文法G和有限自動機M，如果L（G）＝L（M），則稱G和M是等價的。關于正規文法和有限自動機的等價性，有以下結論：（1） 對每一個右線性正規文法G或左線性正規文法G，都存在一個有限自動機（FA）M，使得L（M）＝L（G）。（2） 對每一個FA M，都存在一個右線性正規文法GR或左線性正規文法GL，使得L（M）＝L（GR）＝L（GL） 正規式與有限自動機的等價性 我們可以證明：（1） 對任何FA M，都存在一個正規式r，使得L（r）＝L（M）。（2） 對任何的正規式r，都存在一個FA M，使得L（M）＝L（r）。上述結論加上前面章節所證明的結論，說明正規文法、正規式、確定有限自動機和非確定有限自動機在接收語言的能力上是互相等價的。 確定有限自動機的化簡 等價狀態；最少化。 詞法分析器的自動產生 教學目的：使用狀態轉換圖構造詞法分析程序；上機實踐LEX的實現。 語言LEX的一般描述 一個LEX源程序主要包括兩部分。一部分是正規定義式，另一個是識別規則。 產生式(也稱產生規則或簡稱規則)是定義語法范疇的一種書寫規則。一個產生式的 形式是 A174。a 其中，箭頭(有時也用：：＝)左邊的A是一個非終結符，稱為產生式的左部符號；箭頭右邊的a是由終結符號或非終結符號組成的符號串，稱為產生式的右部。我們有時也說，產生式A174。a是關于A的一條產生規則。產生式是用來定義語法范疇的。例如，令i 代表已定義的范疇“變量”，那么，產生式 算術表達式174。i 意味著把“算術表達式”這個范疇定義為“變量”。在有的書上，“174。”也用“：：＝”表示：這種表示方法也稱巴科斯范式。 超前搜索 在某些語言中，要識別一個單詞符號必須超前看若干字符。 LEX的實現 LEX的編譯程序旨在將一個LEX源程序改造為一個詞法分析器L，這個詞法分析器L將像有限自動機那樣工作。相關介紹：人們已建立了多種編制部分編譯程序或整個編譯程序的有效工具。有些能用于自動產生掃描器(如LEX)，有些可用于自動產生語法分析器(如YACC)，有些甚至可用來自動產生整個的編譯程序。這些構造編譯程序的工具稱為編譯程序——編譯程序、編譯程序產生器或翻譯程序書寫系統，它們是按對源程序和目標語言(或機器)的形式描述(作為輸入數據)而自動產生編譯程序的。授課題目（教學章、節或主題）：第三章 語法分析上下文無關文法、形式語言和文法課時安排6授課時間 第3周 第36節 第4周 第2節 教學目的、要求（分掌握、熟悉、了解三個層次）：理解和定義上下文無關文法，為學習和構造編譯程序打下良好基礎。理解語言和文法的定義掌握文法的等價變換及語法描述方法了解文法的分類教學重點和難點：文法的直觀概念、文法和語言的形式定義、文法的類型、語法樹和二義性、文法中的實用限制、句型的分析授課類型（請打√）：理論課254。 討論課□ 實驗課□ 練習課254。 其他□教學方式（請打√）：講授254。 討論□ 示教□ 指導254。 其他□教學資源（請打√）：多媒體254。 模型□ 實物□ 掛圖□ 音像□ 其他□討論、思考題、作業：P36：6，8，11教學內容 上下文無關文法 箭頭‘’讀為“定義為”，直豎‘|’讀為“或”，它們是元語言符號。在后面的討論中，根據不同情況，我們將用大寫字母A、B、C…或漢語詞組(如，算術表達式)代表非終結符號，特別是用小寫字母a、b、c…代表終結符，用α、β、γ等代表由終結符和非終結符組成的符號串。為簡便起見，當引用具體的文法例子時，僅列出產生式和指出開始符號。 例如，下面是一個上下文無關文法：Ei|EAEA+|*其中，E、A是非終結符，E是開始符號，而i、+和*是終結符。一個上下文無關文法如何定義一個語言呢?其中心思想是，從文法的開始符號出發，反復連續使用產生式，對非終結符施行替換和展開。例如，我們考慮下面的文法G: EE十E | E*E | (E) |i 其中，唯一的非終結符E可以看成是代表一類算術表達式。我們可以從E出發，進行一系列的推導，推出種種不同的算術表達式來。例如，根據規則E一(E)我們可以說：從‘E’可直接(一步地)推出‘(E)’。與前面一樣，我們用‘222?！硎尽爸苯油瞥觥?，這樣，這句話就可表示為:E222。(E)。若對‘(E)’中的E使用規則EE+E，就有(E)222。(E+E)。即，從‘(E)’可直接推出‘(E+E)’。把上述這兩步合并起來，就有E222。(E)222。(E+E)。再對‘(E+E)’中的E相繼兩次使用規則Ei之后，我們就有(E) 222。(E+E)222。(i+E)222。(i+i)。我們稱這樣的一串替換序列是從E推出(i+i)的一個推導。這個推導提供了一個證明，證明(i+i)是文法()所定義的一個算術表達式。注意，推導每前進一步總是引用一條規則(產生式),而符號‘222。’指僅推導一步的意思。我們可以用一種圖示化的方法來表示這種推導，說明He gave me a book是一個語法正確的句子。這種圖形表示稱為語法分析樹。定義 “he gave me a book”這個英文句子的規則可以說就是一個上下文無關文法。其中，He，me，book，gave，a等，稱為終結符號；句子、主語、謂語、動詞、代詞等，稱為非終結符號；這個文法最終是要定義句子的語法結構，所以句子在這里稱為開始符號；間接賓語冠詞名詞這種書寫形式稱為產生式。歸納起來，一個上下文無關文法C包括四個組成部分：一組終結符號，一組非終結符號，一個開始符號，以及一組產生式。 所謂終結符號乃是組成語言的基本符號，在程序語言中就是以前屢次提到的單詞符號，如基本字、標識符、常數、算符和界符等。從語法分析的角度來看，終結符號是一個語言的不可再分的基本符號。句子主語謂語形容詞名詞動詞賓語形容詞名詞 hegavemeabook非終結符號(也稱語法變量)用來代表語法范疇。例如，“算術表達式”、“布爾表達式”、“賦值句”、“分程序”、“過程”等，它們都是現今程序語言常見的語法范疇。我們也可以說，一個非終結符代表一個一定的語法概念。因此，一個非終結符是一個類(或集合)記號，而不是一個個體記號。例如，“算術表達式”這個非終結符乃代表一定算術式組成的類。因而，也可以說，每個非終結符號表示一定符號串的集合(由終結符號和非終結符號組成的符號串)。開始符號是一個特殊的非終結符號，它代表所定義的語言中我們最終感興趣的語法范疇，這個語法范疇通常稱為“句子”。但在程序語言中，我們最終感興趣的是“程序”這個語法范疇，而其它的語法范疇都只不過是構造“程序”的一塊塊磚石。 語法分析樹與二義性 前面我們提到過可以用一張圖表示一個句型的推導，這種表示稱為語法分析樹，或簡稱為語法樹。語法樹有助于理解一個句子語法結構的層次。語法樹通常表示成一棵倒立的樹，根在上，枝葉在下。語法樹的根結由開始符號所標記。隨著推導的展開，當某個非終結符被它的某個候選式所替換時，這個非終結符的相應結就產生出下一代新結，候選式中自左至右的每個符號對應一個新結，并用這些符號標記其相應的新結。每個新結和其父結間都有一條連線。在一棵語法樹生長過程中的任何時刻，所有那些沒有后代的端末結自左至右排列起來就是一個句型。例如，對于文法()，關于(i*i+i)的推導()。 語法樹這就是說，一棵語法樹表示了一個句型種種可能的(但未必是所有的)不同推導過程，包括最左(最右)推導。這樣的一棵語法樹是這些不同推導過程的共性抽象，是它們的代表。
如果我們堅持使用最左(最右)推導，那么，一棵語法樹就完全等價于一個最左(最右)推導，這種等價性包括樹的步步成長和推