編譯原理

1、編譯原理,尹劍飛科技樓1406yjfbase@yahoo.com.cn13424410028,編譯原理和技術(shù)的重要性,設(shè)計和開發(fā)編譯器的原理和技術(shù)將會在一個計算機工作者的職業(yè)生涯中被多次使用。--- >編譯器的構(gòu)造綜合了計算機科學(xué)的各個方面：計算機理論、程序設(shè)計、軟件工程，是理論應(yīng)用于實踐的成功典范。-->,編譯原理和技術(shù)的重要性,自計算機科學(xué)誕生以來，語言處理器的工程化就一直在推動，隨著相關(guān)理論的開發(fā)不斷改進。--

2、 >相對其它技術(shù)而言，編譯器技術(shù)是一種內(nèi)功修煉，因為任何計算機問題都可以化為語言翻譯問題 -- some one,第一章 編譯器介紹,1.1 編譯器概貌1.2 源程序分析1.3 編譯器的階段1.4 編譯器的同胞1.5 階段的組合1.6 編譯器構(gòu)造工具,1.1 編譯器概貌,編譯器（程序）,錯誤信息,,,,,,第一個編譯器出現(xiàn)于1950年,第一個Fortran編譯器花了18人年,通過工具支持，基本的編譯器可作為學(xué)生項目，

3、在一個學(xué)期內(nèi)完成。,1.1.1 編譯器IO,分析 ( Analysis )綜合 ( Synthesis ),分析,中間表示,綜合,,,,,1.1.2 編譯過程分為兩個基本部分,1.1 編譯器概貌,1.1 編譯器概貌,1.1.3 語法樹例子,=,position,initial,rate,60,+,*,,,,,,,position = initial + rate * 60,1.1 編譯器概貌,很多軟件（不一定是編譯器）執(zhí)行類似的“

4、分析”結(jié)構(gòu)編輯器，如：HTML editor格式化（美化）打印，如：自動排版系統(tǒng)靜態(tài)檢查，如：語法檢查器解釋器，如：表達式計算器，SQL檢查解釋器，java …,1.1 編譯器概貌,D.cpp,絕對機器碼,E.asm,可重定位的機器碼,庫可重定位的機器碼,a.h,b.h, ..,C.cpp,,,,,程序的執(zhí)行是怎樣煉成的？,1.2 源程序 “分析”,分析包括三個階段詞法分析（線性分析）：字符->詞（Token）

5、語法分析（層次分析）：詞->句語義分析：句->正確（有意義）的句子,1.2 源程序 “分析”,輸入字符串：‘p’ ‘o’ ‘s’ ‘i’ ‘t’ ‘i’ ‘o’ ‘n’ ‘ ‘ ‘=‘ ‘ ‘ ‘ ‘ ‘i’ ‘n’ ‘i’ ‘t’ ‘i’ ‘a(chǎn)’ ‘l’ ‘ ‘ ‘+’ ‘r’ ‘a(chǎn)’ ‘t’ ‘e’ ‘*’ ‘6’ ‘0’，得到下述詞(Token):標識符：position, initial, rate賦值運算符：

6、=加法運算符：+乘法運算符：*數(shù)：60,1.2.1 詞法分析 （線性分析）,1.2 源程序 “分析”,賦值語句,標識符,=,表達式,+,表達式,表達式,標識符,*,表達式,表達式,,,,,,,,,,,,,position,,initial,,標識符,,rate,數(shù),,60,position = initial + rate * 60 的語法樹,標識符 | => rate,,,,,1.2.2 語法

7、分析 （層次分析）,與1.1.3不同的語法樹,1.2 源程序 “分析”,程序的層次結(jié)構(gòu)通常由遞歸規(guī)則定義：規(guī)則1：任何是規(guī)則2：任何是給定和，則下述也是表達式規(guī)則3： + 規(guī)則4： * 規(guī)則5：（ ）,1.2.2 語法分析 （層次分析）,那些是更基本的規(guī)則呢？,線性 VS 層次非遞歸定義 VS 遞歸定義三型文法 VS 二型文法 （more on later…),用自然語言表述計算機語言顯示了它的不足，需要一

8、種更為嚴謹更易評價的表達方法來刻畫詞法和語法等語言要素。,1.2.3 詞法分析 VS 語法分析,1.2 源程序 “分析”,檢查是否存在語義錯誤，獲取類型信息。類型檢查,1.2.3 語義分析,1.2 源程序 “分析”,position,=,+,rate,*,initial,60,,,,,,,position,=,+,rate,*,initial,60,,,,,,,int2real,,1.3 編譯器的階段,源程序,詞法分析器,語法分析,

9、語義分析,中間代碼生成器,代碼優(yōu)化器,代碼生成器,目標程序,,,,,,,,,,,,,,,,,,,符號表，記錄符號與其關(guān)聯(lián)的屬性，如類型、作用域，對于過程名符號，有其參數(shù)個數(shù)和類型、傳值還是傳引用、返回類型。符號在詞法分析階段進入符號表，而與其關(guān)聯(lián)的屬性要在后繼階段補充。float position, initial, rate;,1.3.1 符號表管理,1.3 編譯器的階段,1.3 編譯器的階段,在遇到錯誤時，應(yīng)盡可能繼續(xù)執(zhí)行相應(yīng)階

10、段。詞法分析：不成詞的余留串，如3int語義分析：語法結(jié)構(gòu)良好，但語義錯誤，如加兩個標識符，類型分別為數(shù)組和過程。,1.3.2 錯誤處理,中間代碼可看作是一種抽象機上的程序，如GCC產(chǎn)生的中間代碼，Java Byte代碼。重要特性：容易從語義分析階段產(chǎn)生，容易翻譯到目標代碼。中間代碼有多種形式。三地址碼，最多三個操作數(shù)流控和過程調(diào)用 （more on later…),1.3 編譯器的階段,1.3.3 中間代碼生成,1.3 編

11、譯器的階段,1.3.4 代碼優(yōu)化1.3.5 代碼生成,（more on later…),1.4 編譯器的同胞,預(yù)處理器宏擴展文件包含語法糖衣匯編器裝載和聯(lián)結(jié)器OS外部引用,1.5 階段的組合,前端：主要依賴源程序，獨立于目標機器，詞法分析、創(chuàng)建符號表、語法分析、語義分析、中間代碼生成，可能有優(yōu)化器的參與。后端：代碼優(yōu)化、代碼生成,1.6 編譯器構(gòu)造工具,解析產(chǎn)生器掃描產(chǎn)生器語義導(dǎo)向的翻譯引擎自動代碼生成器。數(shù)據(jù)

12、流引擎,Chaper2.1 一個簡單的一遍編譯器,文法基礎(chǔ),提綱,本章為后繼章節(jié)，特別是編譯器前端（詞法分析、語法分析、中間代碼生成）提供一個實踐的鋪墊。通過設(shè)計與開發(fā)一個簡單的一遍編譯器，展示了編譯器前端構(gòu)造的基本技術(shù)。該一遍編譯器為將中綴表達式語句編譯成后綴表達式語句。該例子還不夠完善，希望同學(xué)們努力讀懂并完善之。,編譯器前端結(jié)構(gòu),字符流,詞法分析器,單詞流,語法導(dǎo)向的翻譯器,中間代碼,,,,文法Grammar,我們采用文法來

13、描述語言的句子結(jié)構(gòu)在得到某語言的文法基礎(chǔ)上，我們可判定一個句子是否屬于該語言判定一個句子是否滿足某語言的文法成為語法分析的核心問題下面的內(nèi)容圍繞如何設(shè)計上下文無關(guān)的文法以解決這個判定問題,上下文無關(guān)的文法,stmt -> if (expr) stmt else stmt上下文無關(guān)的文法，有以下幾個組成：終止符（集合），或稱為tokenif, (, ), else非終止符（集合）stmt, expr產(chǎn)生式（集合）

14、stmt -> if (expr) stmt else stmt左側(cè)有且僅有一個非終止符有且僅有一個非終止符作為起始符，如非終止符S為文法G的起始符，表示為G[S],描述加減的文法G[list]，有以下4個產(chǎn)生式組成,list -> list + digitlist -> list – digitlist -> digitdigit -> 0|1|2|3|4|5|6|7|8|9---------

15、---------------------------------左部相同的產(chǎn)生式，可以合并為： list -> list + digit | list – digit | digit終止符集合VT為：{+,-,0,1,…,9}，非終止符集合VN為：{list, digit},文法導(dǎo)出串（句型）,從起始符開始，重復(fù)替換非終止符為其所在產(chǎn)生式的右側(cè)，所得到的符號串即稱為文法導(dǎo)出串，也稱為句型。

16、 如文法G[list]的句型有：list => list + digit （一個句型） => list – digit + digit （一個句型） => digit – digit + digit （一個句型） => 9 - 5 + 2 （一個句型且是句子）只包括終止符的文法導(dǎo)出串，稱為該文法的句子，句子的集合，稱為該文法定義的語言。,*,描述塊

17、的文法-G[block],block -> { opt_stmts }opt_stmts -> stmt_list | εstmt_list -> stmt_list ; stmt | stmt,ε是終止符，還是非終止符,ε是終止符,給定文法G[S]，其分析樹/語法樹,根S為起始符葉節(jié)點為終止符（token）或ε中間節(jié)點為非終止符例子：9-5+2，按下述文法的分析樹,

18、分析樹-Parse Tree語法樹-Syntax Tree,9-5+2，按文法G[list]的分析樹（語法樹）,list,,,,,,list,digit,list,digit,digit,9,,,-,5,,+,,2,,list -> list + digit | list – digit | digitdigit -> 0 | 1| 2|3|4|5|6|7|8|9,9-5+2是G[list]的一個句型（這里是句子）的依據(jù)

19、：可為9-5+2產(chǎn)生一棵分析樹,分析樹構(gòu)造過程/句型推導(dǎo)過程,list,,,,,list -> list + digit | list – digit | digitdigit -> 0 | 1| 2|3|4|5|6|7|8|9,,list,digit,list,digit,digit,9,,,-,5,,+,,2,,list => list + digit,判斷9-5+2是否是文法G[list]的句型（這里是句子）

20、的最左推導(dǎo)過程如下：,=> list – digit + digit,=> digit – digit + digit,=> 9 – digit + digit,=> 9 – 5 + digit,=> 9 – 5 + 2,小結(jié)：分析樹構(gòu)造過程/句型推導(dǎo)過程,為判定一個串是否是一個文法的句型或句子，分析樹方法與推導(dǎo)方法效果一樣。分析樹方法直觀，但無法直接從結(jié)果分析樹中看出推導(dǎo)步驟。推導(dǎo)方法可以看出中間推導(dǎo)

21、過程。一個串是一個文法的句型或句子 iff存在一棵分析樹（語法樹） iff存在一個的最左推導(dǎo)或一個最右推導(dǎo)（規(guī)范推導(dǎo)）或即非最左也非最右推導(dǎo)。一棵分析樹對應(yīng)唯一的最左推導(dǎo)和唯一的最右推導(dǎo)。,9-5+2的最左推導(dǎo)與規(guī)范推導(dǎo)（最右推導(dǎo)）比較,最左推導(dǎo),最右推導(dǎo)（規(guī)范推導(dǎo)）,list => list + digit,list => list + digit,=> list - digit + digit,=>

22、 list + 2,=> digit - digit + digit,=> 9 - digit + digit,list -> list + digit | list – digit | digitdigit -> 0 | 1| 2|3|4|5|6|7|8|9,=> 9 - 5 + digit,=> 9 - 5 + 2,,=> list – digit + 2,=> list –

23、 5 + 2,=> digit – 5 + 2,=> 9 - 5 + 2,最左歸約和最右歸約,與推導(dǎo)相反的過程稱為歸約最左歸約是最右推導(dǎo)的逆過程最右歸約是最左推導(dǎo)的逆過程關(guān)于歸約，我們將在自底向上的語法分析章節(jié)詳解。,文法二義性,文法G[string]為二義性文法string -> string + string | string - string |

24、 0|1|2|3|4|5|6|7|8|9因為有1棵以上的分析樹對應(yīng)9-5+2,大家動手畫一下,G[string]在+,-運算符的左結(jié)合性問題上出現(xiàn)了二義性,文法二義性,給定文法G[S]：S -> if E then S | if E then S else S | Nif E1 then if E2 then S1 else S2，是G[S]的合法句型，但存在不同的解釋，即有1棵以上的分析樹與之對應(yīng)

25、，所以G[S]為二義性文法。,G[S]在else與then結(jié)合性的問題上出現(xiàn)了二義性,文法二義性,給定某文法G，若存在某句子或句型w，與w對應(yīng)的分析樹（語法樹）不只一個，則稱G為二義性文法。或者說，與w對應(yīng)的最左推導(dǎo)不只一個或者說，與w對應(yīng)的最右推導(dǎo)不只一個我們在設(shè)計文法時，應(yīng)努力避免二義性。,操作符的結(jié)合性-左結(jié)合,文法G[list]list -> list + digit | list – digit

26、 | digitdigit -> 0 | 1| 2| 3|4|5|6|7|8|9------------------------------------------文法G[lst]lst -> digit + lst | digit – lst | digitdigit -> 0 | 1| 2| 3|4|5|6|7|8|9,誰體現(xiàn)左結(jié)合性？,操作符的結(jié)合性-左結(jié)合,list,,,,,,lis

27、t,digit,list,digit,digit,9,,,-,5,,+,,2,,lst,,,,,lst,digit,digit,9,+,5,,-,,2,,,lst,,digit,,list -> list + digit | list – digit | digit,lst -> digit + lst | digit – lst | digit,,,操作符的結(jié)合性-左結(jié)合,文法描述了特定的數(shù)據(jù)結(jié)構(gòu)文法設(shè)計也即

28、數(shù)據(jù)結(jié)構(gòu)設(shè)計合適的數(shù)據(jù)結(jié)構(gòu)設(shè)計可以方便對數(shù)據(jù)的操作語法樹操作包括對語言特征（如左結(jié)合性）的驗證經(jīng)驗：文法左遞歸可以體現(xiàn)左結(jié)合性但是，我們應(yīng)轉(zhuǎn)換文法中含有左遞歸的產(chǎn)生式，以去除左遞歸，從而利于自頂向下的語法分析（見后）,操作符的結(jié)合性-右結(jié)合,文法G[right]right -> letter = right | letterletter -> a |b|…|z,a=b=c的語法樹，如何畫？,經(jīng)驗：文法右遞歸可以

29、體現(xiàn)右結(jié)合性,文法設(shè)計內(nèi)功心法1-左遞歸,文法G[list]list -> list + digit | list – digit | digitdigit -> 0 | 1| 2| 3|4|5|6|7|8|9上述文法較好地體現(xiàn)了+,-運算的左結(jié)合性，要產(chǎn)生帶有*,/運算的表達式，可依照左遞歸范式進行。,四運算表達式文法G[ex]草案,文法G[ex]ex -> ex + digit |

30、ex – digit | ex * digit | ex / digit | digitdigit -> 0 | 1| 2| 3|4|5|6|7|8|9,9-5*2，是文法G[ex]的句子嗎？,文法G[ex]的ex產(chǎn)生式體現(xiàn)*, /比+,-優(yōu)先嗎？,文法設(shè)計內(nèi)功心法2-按優(yōu)先級引入非終止符,為處理以下3種優(yōu)先級常數(shù), () *,/+,-我們引入2個非終止符term：封裝僅含有*,/計算過的

31、表達式factor：封裝僅含有常數(shù),()計算過的表達式,文法設(shè)計內(nèi)功心法2-按優(yōu)先級引入非終止符,文法G[expr]expr -> expr + term | expr – term | termterm -> term * factor | term / factor | factorfactor -> digit

32、 | (expr),expr,term + term - term,factor * factor / factor,digit,(expr),,,,,,,,,里程碑1. 得到四則運算表達式的一個原始文法,expr -> expr + term | expr – term | termterm -> term * factor | term /

33、factor | factorfactor -> digit | (expr)digit -> 0|1|…|9,G[expr]的特點：,可產(chǎn)生四則運算表達式（句子）,體現(xiàn)結(jié)合性和優(yōu)先級,可處理括號,無二義性,左遞歸,,一位十進制,只能一次產(chǎn)生一個表達式,我們離一個簡單的后綴表達式編譯器還有多遠,語法制導(dǎo)的翻譯概念自頂向下（遞歸下降）的語法分析（解析）預(yù)測分析方法左遞歸消除

34、后綴表達式代碼生成,練習(xí),給定上下文無關(guān)的文法G[S]S-> S S+ | S S * | aaa+a*是G[S]的句子嗎？G[S]產(chǎn)生的語言是什么？寫出下述語言的文法{an bn| n>=0}任何不是以0開始的所有偶整數(shù)所組成的集合所有由奇數(shù)個1和偶數(shù)個0所組成的符號串的集合后綴表示的算法表達式逗號分隔的左結(jié)合的標識符列表,練習(xí),下面是否存在二義性？S -> 0 S 1 | 01S ->

35、S v SS -> SS->S a | b SS -> S ( S ) S | ε給定文法G[S]:S → ABS →cA →bAA →aB →aSbB → c試分別用最左推導(dǎo)和規(guī)范推導(dǎo)導(dǎo)出bbaacb,Chapter2-2 語言的形式化定義基礎(chǔ),,語言的形式化定義基礎(chǔ),以下給出若干本書用到的基本語言形式化定義的基本概念以便于讀本書時理解,字母表,字母表(符號集)由符號組成的集合，如字母表

36、A={a,b,c}a,b,c稱為符號，一般為常量，也可以是變量，根據(jù)具體上下文確定。,符號串,符號串A={a,b,c}是一個字母表，則a,b,c,ab,ac,bc,abc,aabc等都是字母表A上的符號串。設(shè)?,?,?，x 是符號串，若x = ???,則稱?是x的子串；特別地，當(dāng)?= ? （?= ?）時，稱 ?是x的前（后）綴,若? ? x，則稱?是x的真前（后）綴,,符號串操作,符號串長|ab|=2，長度為0的符號串，記為

37、ε,符號串連接若令符號串x=abc，符號串y=123，則xy表示符號串x與y的連接，即xy=abc123ε x = x ε = x,符號串的n次方冪 若有符號串x,則 x1 = x, x2 = xx, xn = xn-1x = xxn-1 特別地有， x0= ε,strlen(“ab”),strcat(x,y),符號串連接的特征,εx,ε 是的單位元,因此我們定義x0 = ε,=,xε,x,=,符號串集合的操作,符號串集合的

38、和（并集）A + B = {w| w ? A 或 w ?B}，其中A,B為符號串的集合,符號串集合的積AB = {xy | x ? A 且 y ?B},符號串集合的方冪A1 = A, A2 = AA, An = An-1A = AAn-1 (n>0),符號集合和運算（并運算）的特征, 滿足交換律,? 是的單位元,? + A,=,A,=,A + ?,符號集合連接運算的特征,?是的零元,?A,=,?,=,A?,符號

39、集合連接運算的特征,A0 = {ε},{ε}是的單位元,{ε}A,=,A{ε},A,=,,符號集合的閉包,A的正閉包：,A的自反傳遞閉包：,文法形式定義和語言的Chomsky分類,文法形式定義G=(VN, VT, P, S)，其中VN ? VT = ?,VN ? VT = V,文法G[E]:E -> E + T| E – T | TT -> T * F | T / F | FF -> D |

40、(E)D -> 0|1|…|9,G=( {E, T, F, D}, {+,-,*,/,(,),0,1,2..,9}, {E -> …, T -> …, F -> …, D -> …}, E),四類基本的文法,Chomsky將文法按產(chǎn)生語言的能力由強到弱分為四類基本的文法0型文法（短語結(jié)構(gòu)文法，PSG）1型文法（前后文有關(guān)文法/上下文相關(guān)的文法，CSG）2型文法（前后文無

41、關(guān)的文法/上下文無關(guān)的文法，CFG）3型文法（正規(guī)文法，RG）,0型文法（短語結(jié)構(gòu)文法，PSG）,若文法G中任一產(chǎn)生式都有一般形式 ??? ??V+ ??V* 其中，對?，? 不加任何限制PSG: Phrase Structure Grammar)。由0型文法生成（或者說：定義）的語言稱為0型（遞歸可枚舉）語言。它可由圖靈（Turing）機識別。,0型文法（短語結(jié)構(gòu)文法，PSG）,文法G[S]S?ACaB

42、 Ca?aaC CB?DB CB?E aD?Da AD?AC aE?Ea AE?? 就是一個0型文法，它所產(chǎn)生的語言為,1型文法（前后文有關(guān)文法，CSG）,若一0型文法所有產(chǎn)生式具有形式（第一定義） ?1A?2? ?1??2 其中， ?1,?2?V* ??V+ A?VN| ?1A?2 |?(S

43、為起始符）且S不出現(xiàn)在任何產(chǎn)生式的右側(cè)。 CSG ( Context Sensitive Grammar) 。1型文法產(chǎn)生的語言稱為前后文有關(guān)語言CSL，它可由線性限界自動機識別。,CSG第一定義,根據(jù)定義，含有?產(chǎn)生式的文法不是1型文法。但S->? （S為起始符）可作為1型文法的特例而接受之，條件是S不出現(xiàn)在所有產(chǎn)生式的右邊。例 文法G： S?? | A A?aABC A?abC

44、 CB?BC bB?bb bC?bc cC?cc因G含有S?? ，但S不出現(xiàn)在所有產(chǎn)生式的右側(cè)，按第一定義，G仍被認為是1型文法。,CSG第二定義,1 型文法還有另一種定義形式（第二定義）： G的每個產(chǎn)生式形為???且滿足： | ? |? | ? | ?,? ?V+第二定義產(chǎn)生的語言=第一定義產(chǎn)生的語言-{?}，即S->?不可能存在于第二定義中。

45、今后，我們采用第一定義。,2型文法（前后文無關(guān)的文法，CFG）,若一1型文法G中所有產(chǎn)生式具有形式: A?? 其中，??V+， A?VNCFG(Context Free Grammar)。2型文法產(chǎn)生的語言稱為前后文無關(guān)語言CFL，它可由下推自動機識別。非嚴格CFG允許?-產(chǎn)生式存在，即非嚴格CFG產(chǎn)生式形式為 A?? 其中，??V*，A?VN,2型文法（前后文無關(guān)的文法，CFG,G[S]=

46、({S},{a,b}, {S?aSb S?ab}, S) 產(chǎn)生的語言為,3型文法（正規(guī)文法，RG）,若一2型文法G中僅含有形如 A?aB 或 A?a 的產(chǎn)生式， 其中 A,B ?VN , a ?VT 則稱G為右線性文法。類似地，若G中僅含有形如 A?Ba 或 A?a的產(chǎn)生式， 則稱G為左線性文法

47、。3型文法（正規(guī)文法）的產(chǎn)生式只有上述兩種形式。,3型文法（正規(guī)文法，RG）,RG（Regular Grammar），3型文法產(chǎn)生的語言稱為3型（正規(guī)）語言，它可由有限自動機識別。正規(guī)語言可用正規(guī)表達式表示。3型文法還可拓廣定義為 A??B A?? （ ? ?VT +）（不推薦!）,四類語言之間的關(guān)系,CSG，CFG，RG產(chǎn)生語言的特征,RG：xy*zCFG：anbnCSG：anbncn，anbncndn,…,練習(xí),給定上

48、下文無關(guān)的文法G[S]S-> S S+ | S S * | aaa+a*是G[S]的句子嗎？G[S]產(chǎn)生的語言是什么？寫出下述語言的文法{an bn| n>=0}任何不是以0開始的所有偶整數(shù)所組成的集合所有由奇數(shù)個1和偶數(shù)個0所組成的符號串的集合后綴表示的算法表達式逗號分隔的左結(jié)合的標識符列表,練習(xí),下面是否存在二義性？S -> 0 S 1 | 01S -> S v SS -> S

49、S->S a | b SS -> S ( S ) S | ε給定文法G[S]:S → ABS →cA →bAA →aB →aSbB → c試分別用最左推導(dǎo)和規(guī)范推導(dǎo)導(dǎo)出bbaacb,練習(xí),下面的文法哪些是正規(guī)文法、右線性文法、上下文無關(guān)文法或上下文有關(guān)文法？（1）S → aB (2) S → AB B → Bc A → a

50、 B → b B → bC C → c B → b C → c,,（3）S → aB (4) S → AB B → bC A → a

51、 C → c B → bC C → ε C → c C → ε,,（5）S → aAb (6) S → aA aA → aB

52、 S → ε aA → aaA A → aA B → b A → aB A → a A → a B → b,,（7）S → aCd

53、 (8) S → aA aC → B S → ε aC → aaA A → bAb B → b A → a,Chapter2-2 語言的形式化定義基礎(chǔ),4類語言識別方法,題綱,目的和基本思想規(guī)則序列規(guī)則序列應(yīng)用實例,目的和基本思想,通過特定的

54、過程（算法），以識別任意文法是4類文法（語言）中的哪一類特定的過程是通過一系列有序的判定規(guī)則定義的每一判定規(guī)則，針對某一產(chǎn)生式P，判定P是哪一類文法中的產(chǎn)生式運用判定規(guī)則，對所有產(chǎn)生式{Pi}，得到其判定集合{Pi-所屬的文法產(chǎn)生式}，其中最大者決定文法G是哪一類文法,規(guī)則序列：1. A-> ?規(guī)則,for 產(chǎn)生式P，順序應(yīng)用規(guī)則1~6：1. A-> ?規(guī)則1.1 若A為起始符且A在某產(chǎn)生式的右則，則 P是短語文

55、法的產(chǎn)生式1.2 否則不影響前面對每條產(chǎn)生式的判定結(jié)果，即如下情況不影響判定結(jié)果：1.2.1 A為起始符且A不在任何產(chǎn)生式右則1.2.2 A不為起始符,規(guī)則序列：2. 右線性規(guī)則,當(dāng)產(chǎn)生式P不滿足規(guī)則1時，應(yīng)用下述規(guī)則2. 右線性規(guī)則若P滿足下面3個條件，則P是右線性產(chǎn)生式2.1 左側(cè)只有一個非終止符（VN)2.2 右側(cè)最多只有1個VN且在最右2.3 右側(cè)至少有1個VT且在最左,規(guī)則序列：3. 左線性規(guī)則,當(dāng)產(chǎn)生式

56、P不滿足規(guī)則2時，應(yīng)用下述規(guī)則：3. 左線性規(guī)則若P滿足下面3個條件，則P是左線性產(chǎn)生式3.1 左側(cè)只有一個非終止符（VN)3.2 右側(cè)最多只有1個VN且在最左3.3 右側(cè)至少有1個VT且在最右,規(guī)則序列：4. CFG規(guī)則,當(dāng)產(chǎn)生式P不滿足規(guī)則3時，應(yīng)用下述規(guī)則4. CFG規(guī)則若P滿足下面3個條件，則P是CFG產(chǎn)生式4.1 左側(cè)只有一個VN4.2 右側(cè)>=1個VN4.3 若右側(cè)僅有1個VN ，則該VN 不在

57、右側(cè)的兩端，否則依據(jù)規(guī)則3/4識別,規(guī)則序列：5. CSG規(guī)則,當(dāng)產(chǎn)生式P不滿足規(guī)則4時，應(yīng)用下述規(guī)則5. CSG規(guī)則若P滿足下面2個條件，則P是CSG產(chǎn)生式5.1 左側(cè)串長>1且至少有一個VN5.2 右側(cè)串長>=左側(cè)串長注意，| ?|=0,規(guī)則序列：6. PSG規(guī)則,當(dāng)產(chǎn)生式P不滿足規(guī)則5時，應(yīng)用下述規(guī)則6. PSG規(guī)則P是短語文法（PSG）產(chǎn)生式,規(guī)則序列應(yīng)用實例,下面的文法哪些是正規(guī)文法、右線性文

58、法、上下文無關(guān)文法或上下文有關(guān)文法？（1）文法G[S]S → aB B → Bc B → b C → c解：對文法G[S]的每條產(chǎn)生式順序應(yīng)用規(guī)則1~6，有：,規(guī)則序列應(yīng)用實例1,S → aB （由規(guī)則2，得右線性） B → Bc （由規(guī)則3，得左線性）B → b （由規(guī)則2/3，得左/右線性）C → c （由規(guī)則2/3，得左/右線性）因為

59、G中存在左線性和右線性產(chǎn)生式，所以G為正規(guī)文法。即max{右線性,左線性,左/右線性} = 正規(guī)文法,規(guī)則序列應(yīng)用實例2,(2) S → AB （由規(guī)則4，得CFG） B → Bc （由規(guī)則3，得左線性）B → b （由規(guī)則2/3，得左/右線性）C → c （由規(guī)則2/3，得左/右線性） 按最大文法原則，G為CFG，即max{CFG，左線性, 左/右線性}=CF

60、G,規(guī)則序列應(yīng)用實例3,（3）G[S]S → aB （按規(guī)則2，右線性） B → bC （按規(guī)則2，右線性）C → c （按規(guī)則2/3，左/右線性） C → ε （按規(guī)則1，不影響） max{右線性, 左/右線性,不影響}=max{右線性, 右線性,不影響}=右線性，所以G為右線性注意C → c 可以判定為左線性也可以是右線性，但若判定為左線性，則max= {右線

61、性, 左線性,不影響}=正規(guī)，則將文法G所屬文法類放大了。,規(guī)則序列應(yīng)用實例4,（4）G[S]S → aAb （按規(guī)則4，CFG）aA → aB （按規(guī)則5，CSG） aA → aaA （按規(guī)則5，CSG）B → b （按規(guī)則2/3，左/右線性）A → a （按規(guī)則2/3，左/右線性）max={CFG,CSG,左/右線性}=CSG，即G為CSG,規(guī)則序列應(yīng)用實例5,(8) G[S]S → a

62、A （按規(guī)則2，右線性）aC → B （按規(guī)則6，PSG）aC → aaA （不用判斷了）B → b （不用判斷了）max{PSG,…} = PSG，即G為短語文法,Chapter3.1 詞法分析,概念,提綱,關(guān)于suffix的Lexer::getNextToken解決思路基于狀態(tài)編程的Lexer::getNextToken關(guān)于狀態(tài)的問題所需學(xué)習(xí)的理論知識3.1 設(shè)計掃描器時應(yīng)考慮的問題3

63、.1.2 單詞符號的內(nèi)部表示3.1.3 識別標識符的若干約定和策略,關(guān)于suffix的Lexer::getNextToken,有多少人讀過Suffix源代碼？,http://192.168.150.81/sei 進入編譯原理->第二章,關(guān)于suffix的Lexer::getNextToken,while (1) { cin >> c; //超前讀 if (c == ' ' || c

64、 == '\t') ; // omit white space else if (c == ‘\n’) … // number of lines else if (isdigit(c)) … // number else if (isalpha(c)) … // identifier,keywords else if (c == EOF) … else { }

65、 // *,/,+,-,err },單詞識別程序的自動生成問題,else if 風(fēng)格、回退字符回題,單詞識別的長度和優(yōu)先次序,輸入緩沖區(qū)問題,討論-else if 風(fēng)格,Switch/case/default 風(fēng)格：與else if一樣：對輸入分類、前后處理之間無關(guān)聯(lián),while (1) { c = inFile->get(); switch(c) { case EOF: …;

66、 case ' ': case '\t': case '\r': …; case '\n': …; default: …} },while (1) { switch(current_state) {case s_zero: cin >> c_char; c_state

67、 = s_ws; break; case s_ws: if (c_char==' ' || c_char== '\t') cin >> c_char; else c_state = s_n; break;case s_n: if (c_char == '\n') { ++line_no;

68、 cin >> current_char; }else current_state = s_digit; break;,狀態(tài)編程風(fēng)格：對程序自身的狀態(tài)分類，前后有關(guān)聯(lián),,,,,,,討論-單詞識別的長度和優(yōu)先次序,為單詞識別的長度建立一個規(guī)則,,對于有共同前綴的單詞，采取最長匹配原則：最長單詞優(yōu)先,<,=,b,a,,輸入流,,詞法分析,<,<,&

69、gt;,c,<,若期望的最長匹配失敗了，如已讀到，但等到是a，該怎么辦？,a,最長匹配導(dǎo)致的回退字符和性能問題,在詞法分析器中建立雙緩沖區(qū)以提高性能通過雙指針lexeme_begining, forward,f,o,o,{,_,_,,f,o,o,i n t _ x,{,送語法分析,詞法分析程序的自動生成問題,以3型文法描述單詞解析某個3型文法，以自動生成單詞識別器,基于狀態(tài)編程的Lexer::

70、getNextToken,s_zero,s_ws,,s_n,s_digit,s_number,s_alpha,s_id_keyword,s_EOF,s_unknown,nc: nextChar,用/分開輸入和動作，如ws/nc，表示當(dāng)輸入一個空白字符，則獲取下一字符,基于狀態(tài)編程的Lexer::getNextToken,while (1) { switch(current_state) {case s_zero:

71、cin >> current_char; current_state = s_ws;break;case s_ws:if (current_char == ' ' || current_char == '\t') cin >> current_char; else current_state = s_n; break;case s_n:cas