編譯原理

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

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

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

4、分析”結(jié)構(gòu)編輯器，如：HTML editor格式化（美化）打印，如：自動(dòng)排版系統(tǒng)靜態(tài)檢查，如：語法檢查器解釋器，如：表達(dá)式計(jì)算器，SQL檢查解釋器，java …,1.1 編譯器概貌,D.cpp,絕對(duì)機(jī)器碼,E.asm,可重定位的機(jī)器碼,庫可重定位的機(jī)器碼,a.h,b.h, ..,C.cpp,,,,,程序的執(zhí)行是怎樣煉成的？,1.2 源程序 “分析”,分析包括三個(gè)階段詞法分析（線性分析）：字符->詞（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):標(biāo)識(shí)符：position, initial, rate賦值運(yùn)算符：

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

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

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

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

10、段。詞法分析：不成詞的余留串，如3int語義分析：語法結(jié)構(gòu)良好，但語義錯(cuò)誤，如加兩個(gè)標(biāo)識(shí)符，類型分別為數(shù)組和過程。,1.3.2 錯(cuò)誤處理,中間代碼可看作是一種抽象機(jī)上的程序，如GCC產(chǎn)生的中間代碼，Java Byte代碼。重要特性：容易從語義分析階段產(chǎn)生，容易翻譯到目標(biāo)代碼。中間代碼有多種形式。三地址碼，最多三個(gè)操作數(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ù)處理器宏擴(kuò)展文件包含語法糖衣匯編器裝載和聯(lián)結(jié)器OS外部引用,1.5 階段的組合,前端：主要依賴源程序，獨(dú)立于目標(biāo)機(jī)器，詞法分析、創(chuàng)建符號(hào)表、語法分析、語義分析、中間代碼生成，可能有優(yōu)化器的參與。后端：代碼優(yōu)化、代碼生成,1.6 編譯器構(gòu)造工具,解析產(chǎn)生器掃描產(chǎn)生器語義導(dǎo)向的翻譯引擎自動(dòng)代碼生成器。數(shù)據(jù)

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

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

14、stmt -> if (expr) stmt else stmt左側(cè)有且僅有一個(gè)非終止符有且僅有一個(gè)非終止符作為起始符，如非終止符S為文法G的起始符，表示為G[S],描述加減的文法G[list]，有以下4個(gè)產(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è)，所得到的符號(hào)串即稱為文法導(dǎo)出串，也稱為句型。

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

17、的文法-G[block],block -> { opt_stmts }opt_stmts -> stmt_list | εstmt_list -> stmt_list ; stmt | stmt,ε是終止符，還是非終止符,ε是終止符,給定文法G[S]，其分析樹/語法樹,根S為起始符葉節(jié)點(diǎn)為終止符（token）或ε中間節(jié)點(diǎn)為非終止符例子：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]的一個(gè)句型（這里是句子）的依據(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)過程,為判定一個(gè)串是否是一個(gè)文法的句型或句子，分析樹方法與推導(dǎo)方法效果一樣。分析樹方法直觀，但無法直接從結(jié)果分析樹中看出推導(dǎo)步驟。推導(dǎo)方法可以看出中間推導(dǎo)

21、過程。一個(gè)串是一個(gè)文法的句型或句子 iff存在一棵分析樹（語法樹） iff存在一個(gè)的最左推導(dǎo)或一個(gè)最右推導(dǎo)（規(guī)范推導(dǎo)）或即非最左也非最右推導(dǎo)。一棵分析樹對(duì)應(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因?yàn)橛?棵以上的分析樹對(duì)應(yīng)9-5+2,大家動(dòng)手畫一下,G[string]在+,-運(yùn)算符的左結(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棵以上的分析樹與之對(duì)應(yīng)

25、，所以G[S]為二義性文法。,G[S]在else與then結(jié)合性的問題上出現(xiàn)了二義性,文法二義性,給定某文法G，若存在某句子或句型w，與w對(duì)應(yīng)的分析樹（語法樹）不只一個(gè)，則稱G為二義性文法?；蛘哒f，與w對(duì)應(yīng)的最左推導(dǎo)不只一個(gè)或者說，與w對(duì)應(yīng)的最右推導(dǎo)不只一個(gè)我們?cè)谠O(shè)計(jì)文法時(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è)計(jì)也即

28、數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)合適的數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)可以方便對(duì)數(shù)據(jù)的操作語法樹操作包括對(duì)語言特征（如左結(jié)合性）的驗(yàn)證經(jīng)驗(yàn)：文法左遞歸可以體現(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)驗(yàn)：文法右遞歸可以

29、體現(xiàn)右結(jié)合性,文法設(shè)計(jì)內(nèi)功心法1-左遞歸,文法G[list]list -> list + digit | list – digit | digitdigit -> 0 | 1| 2| 3|4|5|6|7|8|9上述文法較好地體現(xiàn)了+,-運(yùn)算的左結(jié)合性，要產(chǎn)生帶有*,/運(yùn)算的表達(dá)式，可依照左遞歸范式進(jìn)行。,四運(yùn)算表達(dá)式文法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è)計(jì)內(nèi)功心法2-按優(yōu)先級(jí)引入非終止符,為處理以下3種優(yōu)先級(jí)常數(shù), () *,/+,-我們引入2個(gè)非終止符term：封裝僅含有*,/計(jì)算過的

31、表達(dá)式factor：封裝僅含有常數(shù),()計(jì)算過的表達(dá)式,文法設(shè)計(jì)內(nèi)功心法2-按優(yōu)先級(jí)引入非終止符,文法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. 得到四則運(yùn)算表達(dá)式的一個(gè)原始文法,expr -> expr + term | expr – term | termterm -> term * factor | term /

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

34、后綴表達(dá)式代碼生成,練習(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ù)個(gè)1和偶數(shù)個(gè)0所組成的符號(hào)串的集合后綴表示的算法表達(dá)式逗號(hào)分隔的左結(jié)合的標(biāo)識(shí)符列表,練習(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ǔ),以下給出若干本書用到的基本語言形式化定義的基本概念以便于讀本書時(shí)理解,字母表,字母表(符號(hào)集)由符號(hào)組成的集合，如字母表

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

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

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

39、集合連接運(yùn)算的特征,A0 = {ε},{ε}是的單位元,{ε}A,=,A{ε},A,=,,符號(hào)集合的閉包,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)生語言的能力由強(qiáng)到弱分為四類基本的文法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* 其中，對(duì)?，? 不加任何限制PSG: Phrase Structure Grammar)。由0型文法生成（或者說：定義）的語言稱為0型（遞歸可枚舉）語言。它可由圖靈（Turing）機(jī)識(shí)別。,0型文法（短語結(jié)構(gòu)文法，PSG）,文法G[S]S?ACaB

42、 Ca?aaC CB?DB CB?E aD?Da AD?AC aE?Ea AE?? 就是一個(gè)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，它可由線性限界自動(dòng)機(jī)識(shí)別。,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仍被認(rèn)為是1型文法。,CSG第二定義,1 型文法還有另一種定義形式（第二定義）： G的每個(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，它可由下推自動(dòng)機(jī)識(shí)別。非嚴(yán)格CFG允許?-產(chǎn)生式存在，即非嚴(yá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ī)）語言，它可由有限自動(dòng)機(jī)識(shí)別。正規(guī)語言可用正規(guī)表達(dá)式表示。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ù)個(gè)1和偶數(shù)個(gè)0所組成的符號(hào)串的集合后綴表示的算法表達(dá)式逗號(hào)分隔的左結(jié)合的標(biāo)識(shí)符列表,練習(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類語言識(shí)別方法,題綱,目的和基本思想規(guī)則序列規(guī)則序列應(yīng)用實(shí)例,目的和基本思想,通過特定的

54、過程（算法），以識(shí)別任意文法是4類文法（語言）中的哪一類特定的過程是通過一系列有序的判定規(guī)則定義的每一判定規(guī)則，針對(duì)某一產(chǎn)生式P，判定P是哪一類文法中的產(chǎn)生式運(yùn)用判定規(guī)則，對(duì)所有產(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 否則不影響前面對(duì)每條產(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時(shí)，應(yīng)用下述規(guī)則2. 右線性規(guī)則若P滿足下面3個(gè)條件，則P是右線性產(chǎn)生式2.1 左側(cè)只有一個(gè)非終止符（VN)2.2 右側(cè)最多只有1個(gè)VN且在最右2.3 右側(cè)至少有1個(gè)VT且在最左,規(guī)則序列：3. 左線性規(guī)則,當(dāng)產(chǎn)生式

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

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

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

59、G中存在左線性和右線性產(chǎn)生式，所以G為正規(guī)文法。即max{右線性,左線性,左/右線性} = 正規(guī)文法,規(guī)則序列應(yīng)用實(shí)例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)用實(shí)例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)用實(shí)例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)用實(shí)例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í)的理論知識(shí)3.1 設(shè)計(jì)掃描器時(shí)應(yīng)考慮的問題3

63、.1.2 單詞符號(hào)的內(nèi)部表示3.1.3 識(shí)別標(biāo)識(shí)符的若干約定和策略,關(guān)于suffix的Lexer::getNextToken,有多少人讀過Suffix源代碼？,http://192.168.150.81/sei 進(jìn)入編譯原理->第二章,關(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 },單詞識(shí)別程序的自動(dòng)生成問題,else if 風(fēng)格、回退字符回題,單詞識(shí)別的長度和優(yōu)先次序,輸入緩沖區(qū)問題,討論-else if 風(fēng)格,Switch/case/default 風(fēng)格：與else if一樣：對(duì)輸入分類、前后處理之間無關(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)格：對(duì)程序自身的狀態(tài)分類，前后有關(guān)聯(lián),,,,,,,討論-單詞識(shí)別的長度和優(yōu)先次序,為單詞識(shí)別的長度建立一個(gè)規(guī)則,,對(duì)于有共同前綴的單詞，采取最長匹配原則：最長單詞優(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,{,送語法分析,詞法分析程序的自動(dòng)生成問題,以3型文法描述單詞解析某個(gè)3型文法，以自動(dòng)生成單詞識(shí)別器,基于狀態(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,用/分開輸入和動(dòng)作，如ws/nc，表示當(dāng)輸入一個(gè)空白字符，則獲取下一字符,基于狀態(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