編譯技術(shù)：第04章01 文法語(yǔ)法VIP

1、第四章(01) (01) 文法和語(yǔ)法的定義語(yǔ)言的定義語(yǔ)言語(yǔ)言 語(yǔ)法語(yǔ)法規(guī)則規(guī)則 語(yǔ)義語(yǔ)義規(guī)則規(guī)則語(yǔ)法、語(yǔ)義都是語(yǔ)法、語(yǔ)義都是規(guī)則的集合規(guī)則的集合語(yǔ)法語(yǔ)法: : 用來(lái)用來(lái)構(gòu)造構(gòu)造程序及語(yǔ)法成分程序及語(yǔ)法成分 如表達(dá)式、語(yǔ)句如表達(dá)式、語(yǔ)句語(yǔ)義語(yǔ)義: : 用來(lái)用來(lái)規(guī)定規(guī)定語(yǔ)法單位的含義語(yǔ)法單位的含義Zhou, Erqiang2School of Information and Software Engineering基本概念：基本概念：1 1）字母表字母表: :語(yǔ)言允許使用字符的集合語(yǔ)言允許使用字符的集合2 2）詞匯詞匯: :由字符組成的有限串由字符組成的有限串( (字符串字符串) )3 3）詞法規(guī)

2、則詞法規(guī)則: : 哪些字符串合法或者不合法哪些字符串合法或者不合法 標(biāo)識(shí)符：函數(shù)名，變量名等標(biāo)識(shí)符：函數(shù)名，變量名等Zhou, Erqiang3語(yǔ)法School of Information and Software Engineering4 4）語(yǔ)法規(guī)則語(yǔ)法規(guī)則: : 句子：一個(gè)句子：一個(gè)“詞匯序列詞匯序列” 確定句子在確定句子在形式上形式上是否合法是否合法 提供句子的結(jié)構(gòu)提供句子的結(jié)構(gòu) ifif ( ( 表達(dá)式表達(dá)式 ) ) 語(yǔ)句語(yǔ)句 elseelse 語(yǔ)句語(yǔ)句Zhou, Erqiang4School of Information and Software Engineering語(yǔ)法自然語(yǔ)

3、言描述自然語(yǔ)言描述 FORTRAN FORTRAN形式化描述（形式化描述（BNFBNF） ALGOL60 ALGOL60轉(zhuǎn)換圖（語(yǔ)法圖）轉(zhuǎn)換圖（語(yǔ)法圖） PASCAL PASCALZhou, Erqiang5語(yǔ)法的表示School of Information and Software Engineering重點(diǎn)！重點(diǎn)！自然語(yǔ)言描述自然語(yǔ)言描述 FORTRAN FORTRAN形式化描述（形式化描述（BNFBNF） ALGOL60 ALGOL60轉(zhuǎn)換圖（語(yǔ)法圖）轉(zhuǎn)換圖（語(yǔ)法圖） PASCAL PASCALZhou, Erqiang6語(yǔ)法的表示School of Information and S

4、oftware Engineering構(gòu)造規(guī)則構(gòu)造規(guī)則語(yǔ)法圖的構(gòu)造語(yǔ)法圖的構(gòu)造 N 1| 2| n對(duì)應(yīng)一個(gè)語(yǔ)法圖對(duì)應(yīng)一個(gè)語(yǔ)法圖Zhou, Erqiang7轉(zhuǎn)換圖定義語(yǔ)言School of Information and Software Engineering 終結(jié)符終結(jié)符x x 非終結(jié)符非終結(jié)符N NN 1| 2| nxN2n1Zhou, Erqiang8構(gòu)造規(guī)則School of Information and Software Engineeringb1b2bm b1b2bmZhou, Erqiang9構(gòu)造規(guī)則gb b|gSchool of Information and Softwar

5、e Engineering生成的串是哪種形式？生成的串是哪種形式？一個(gè)一個(gè)合法的合法的終結(jié)符序列：終結(jié)符序列： 從從入口邊入口邊 通過(guò)語(yǔ)法圖通過(guò)語(yǔ)法圖 到到出口邊出口邊 通過(guò)時(shí)恰恰能識(shí)別該終結(jié)符序列通過(guò)時(shí)恰恰能識(shí)別該終結(jié)符序列語(yǔ)言：語(yǔ)言： 語(yǔ)法圖語(yǔ)法圖能識(shí)別能識(shí)別的的 所有所有終結(jié)符序列終結(jié)符序列的集合的集合Zhou, Erqiang10識(shí)別原則School of Information and Software Engineering標(biāo)識(shí)符標(biāo)識(shí)符Zhou, Erqiang11表達(dá)式語(yǔ)法圖(表達(dá)式表達(dá)式運(yùn)算符運(yùn)算符表達(dá)式表達(dá)式表達(dá)式表達(dá)式)School of Information and S

6、oftware Engineering數(shù)字?jǐn)?shù)字Zhou, Erqiang12 語(yǔ)義語(yǔ)義（規(guī)則）語(yǔ)義（規(guī)則） 定義語(yǔ)言定義語(yǔ)言合法合法句子的句子的含義含義 即句子的作用和意義的規(guī)則組合即句子的作用和意義的規(guī)則組合例：例：if(ab) then max=a else max=b if(ab) then max=a else max=b 先計(jì)算先計(jì)算ifif后的表達(dá)式后的表達(dá)式 再按照再按照所得值決定所得值決定maxmax的值的值School of Information and Software Engineering描述語(yǔ)法描述語(yǔ)法 文法和語(yǔ)法圖文法和語(yǔ)法圖描述語(yǔ)義描述語(yǔ)義 尚尚無(wú)無(wú)普遍接受的描

7、述工具普遍接受的描述工具 許多語(yǔ)言仍采用許多語(yǔ)言仍采用自然語(yǔ)言自然語(yǔ)言描述語(yǔ)義描述語(yǔ)義Zhou, Erqiang13語(yǔ)義的表示School of Information and Software Engineering自然語(yǔ)言描述自然語(yǔ)言描述 FORTRAN形式化描述（形式化描述（BNFBNF） ALGOL60轉(zhuǎn)換圖（語(yǔ)法圖）轉(zhuǎn)換圖（語(yǔ)法圖） PASCALZhou, Erqiang14語(yǔ)法的表示School of Information and Software Engineeringstmt if ( expr ) stmt else stmtif, (, ), else 都不能進(jìn)一步分解都

8、不能進(jìn)一步分解 終結(jié)符終結(jié)符，詞法單元，詞法單元stmt， expr 可以進(jìn)一步分解可以進(jìn)一步分解 非終結(jié)符非終結(jié)符，語(yǔ)言變量，語(yǔ)言變量非終結(jié)符非終結(jié)符, , 箭頭箭頭, , 終結(jié)符和非終結(jié)符序列終結(jié)符和非終結(jié)符序列 產(chǎn)生式產(chǎn)生式，productionZhou, Erqiang15形式化描述School of Information and Software Engineering指定一個(gè)非終結(jié)符為指定一個(gè)非終結(jié)符為開(kāi)始符號(hào)開(kāi)始符號(hào)定義：定義： 終結(jié)符集合：終結(jié)符集合：V VT T 非終結(jié)符集合：非終結(jié)符集合：V VN N 產(chǎn)生式集合：產(chǎn)生式集合：P P 開(kāi)始符號(hào)：開(kāi)始符號(hào)：S SG = (V

9、G = (VT T, V, VN N, S, P), S, P) G G稱(chēng)為一個(gè)稱(chēng)為一個(gè)文法文法 文法文法是對(duì)是對(duì)語(yǔ)法語(yǔ)法的形式化描述的形式化描述Zhou, Erqiang16形式化描述School of Information and Software Engineering歷史背景歷史背景 喬姆斯基喬姆斯基( (ChomskyChomsky) ) 于于19561956年建立語(yǔ)言的形式描述年建立語(yǔ)言的形式描述深遠(yuǎn)影響深遠(yuǎn)影響 語(yǔ)言學(xué)、計(jì)算機(jī)科學(xué)語(yǔ)言學(xué)、計(jì)算機(jī)科學(xué) 程序語(yǔ)言的設(shè)計(jì)程序語(yǔ)言的設(shè)計(jì)、編譯方法編譯方法、 計(jì)算復(fù)雜性計(jì)算復(fù)雜性等等Zhou, Erqiang17文法School of I

10、nformation and Software Engineering歷史回顧歷史回顧 取得了大量的成果取得了大量的成果 理論工作走在計(jì)算機(jī)發(fā)展的前面理論工作走在計(jì)算機(jī)發(fā)展的前面現(xiàn)狀展望現(xiàn)狀展望 計(jì)算機(jī)及其應(yīng)用的迅速發(fā)展計(jì)算機(jī)及其應(yīng)用的迅速發(fā)展 今天的理論遠(yuǎn)遠(yuǎn)落后今天的理論遠(yuǎn)遠(yuǎn)落后Zhou, Erqiang18School of Information and Software Engineering文法產(chǎn)生式非終結(jié)符非終結(jié)符, , 箭頭箭頭, , 終結(jié)符和非終結(jié)符序列終結(jié)符和非終結(jié)符序列stmt if ( expr ) stmt else stmt產(chǎn)生式是一個(gè)產(chǎn)生式是一個(gè)有序偶對(duì)有序偶對(duì)(

11、( ，b b) )記為記為 := b b 或或 b bZhou, Erqiang19School of Information and Software Engineering關(guān)于關(guān)于 和和 b b 和和b b是由是由終結(jié)符終結(jié)符、非終結(jié)符非終結(jié)符組成的串組成的串 至少應(yīng)含有一個(gè)至少應(yīng)含有一個(gè)非終結(jié)符非終結(jié)符即即 V*VNV* b b V* 其中其中 V= VT VN Zhou, Erqiang20產(chǎn)生式School of Information and Software Engineering幾點(diǎn)說(shuō)明幾點(diǎn)說(shuō)明* 表示任意多次（表示任意多次（0 0次或次或0 0次以上）次以上）+ 表示至少表示

12、至少1 1次次V* 表示表示 V V中的元素中的元素 可出現(xiàn)任意多次可出現(xiàn)任意多次V+ 表示表示 V V中的元素中的元素 至少出現(xiàn)至少出現(xiàn)1 1次次Zhou, Erqiang21產(chǎn)生式School of Information and Software Engineering產(chǎn)生式的簡(jiǎn)化 b b1 b b2 b bn b bn 稱(chēng)為稱(chēng)為候選式候選式 b1 | b2 |bnZhou, Erqiang22其中其中| |表示表示“或者或者” School of Information and Software Engineering非終結(jié)符非終結(jié)符 英文英文大寫(xiě)字母大寫(xiě)字母表示表示開(kāi)始符號(hào)開(kāi)始符號(hào)

13、僅有僅有1 1個(gè)個(gè) 第一個(gè)產(chǎn)生式的第一個(gè)產(chǎn)生式的左邊左邊符號(hào)符號(hào)Zhou, Erqiang23產(chǎn)生式的約定School of Information and Software Engineering文法的表示描述文法描述文法 直接給出產(chǎn)生式集合直接給出產(chǎn)生式集合例如算術(shù)表達(dá)式文法例如算術(shù)表達(dá)式文法G G0 0: : E E E+T E+T | | T T T T T T* *F F | | F F F F (E) (E) | | i iZhou, Erqiang24School of Information and Software Engineering1 1） 0 0型文法（無(wú)限制文法）型

14、文法（無(wú)限制文法） b b V V* * V VN N V V* * ， b b V V* * 2 2） 1 1型文法型文法( (上下文上下文有關(guān)有關(guān)文法文法) ) | | | = | 0Zhou, Erqiang41文法實(shí)例School of Information and Software Engineering文法的重要性文法的重要性 有限有限規(guī)則描述規(guī)則描述無(wú)窮無(wú)窮語(yǔ)言語(yǔ)言文法等價(jià)文法等價(jià) 兩個(gè)文法兩個(gè)文法G G和和G,G,如果有如果有L(G)=L(G) 則稱(chēng)則稱(chēng)G G和和GG等價(jià)等價(jià)Zhou, Erqiang42文法實(shí)例小結(jié)School of Information and Soft

15、ware Engineering用圖展示一個(gè)句型（句子）的推導(dǎo)過(guò)程用圖展示一個(gè)句型（句子）的推導(dǎo)過(guò)程 推導(dǎo)樹(shù)、語(yǔ)法樹(shù)推導(dǎo)樹(shù)、語(yǔ)法樹(shù)倒立的樹(shù)倒立的樹(shù) 根在上、葉在下根在上、葉在下 開(kāi)始符號(hào)為開(kāi)始符號(hào)為“樹(shù)根樹(shù)根”Zhou, Erqiang43推導(dǎo)樹(shù)（語(yǔ)法樹(shù)）School of Information and Software Engineering對(duì)于文法對(duì)于文法 E E+EE*E(E)i 句子句子 (i+i*i) 的推導(dǎo)樹(shù)的推導(dǎo)樹(shù)Zhou, Erqiang44推導(dǎo)樹(shù)實(shí)例E（E）EE*EE+iiiE（E）EE+EEiii*School of Information and Software En

16、gineering一棵一棵有序有序的標(biāo)記樹(shù)的標(biāo)記樹(shù)結(jié)點(diǎn)是文法的結(jié)點(diǎn)是文法的非終結(jié)非終結(jié)符或符或終結(jié)終結(jié)符符當(dāng)當(dāng)非終結(jié)符非終結(jié)符 被被 其其候選式候選式替代替代 該非終結(jié)符產(chǎn)生下一代枝葉該非終結(jié)符產(chǎn)生下一代枝葉結(jié)點(diǎn)結(jié)點(diǎn)A A從左到右有子結(jié)點(diǎn)從左到右有子結(jié)點(diǎn)X X1 1，X X2 2，, X, Xn n, ,則則AXAX1 1XXn n是一個(gè)產(chǎn)生式是一個(gè)產(chǎn)生式; ;Zhou, Erqiang45推導(dǎo)樹(shù)總結(jié)School of Information and Software Engineering推導(dǎo)樹(shù)的邊緣：推導(dǎo)樹(shù)的邊緣： 推導(dǎo)樹(shù)所有葉結(jié)點(diǎn)推導(dǎo)樹(shù)所有葉結(jié)點(diǎn)從左到右從左到右的連接。的連接。文法的二義

17、性：文法的二義性： 一個(gè)句子有兩棵不同的推導(dǎo)樹(shù)。一個(gè)句子有兩棵不同的推導(dǎo)樹(shù)。Zhou, Erqiang46推導(dǎo)樹(shù)總結(jié)School of Information and Software Engineering文法與語(yǔ)法圖關(guān)系文法文法和和語(yǔ)法圖語(yǔ)法圖是語(yǔ)法的是語(yǔ)法的等價(jià)表示等價(jià)表示文法文法 從從產(chǎn)生的觀點(diǎn)產(chǎn)生的觀點(diǎn)定義語(yǔ)言定義語(yǔ)言 更通用、更準(zhǔn)確地給出語(yǔ)法結(jié)構(gòu)更通用、更準(zhǔn)確地給出語(yǔ)法結(jié)構(gòu)語(yǔ)法圖語(yǔ)法圖 從從識(shí)別的觀點(diǎn)識(shí)別的觀點(diǎn)定義語(yǔ)言定義語(yǔ)言 更直觀、更清晰地給出語(yǔ)法結(jié)構(gòu)更直觀、更清晰地給出語(yǔ)法結(jié)構(gòu)Zhou, Erqiang47School of Information and Software

18、Engineering由語(yǔ)言的由語(yǔ)言的設(shè)計(jì)者確定設(shè)計(jì)者確定1)1)設(shè)計(jì)者設(shè)計(jì)者 表達(dá)意圖和設(shè)計(jì)目標(biāo)表達(dá)意圖和設(shè)計(jì)目標(biāo)2)2)使用者使用者 指導(dǎo)如何編寫(xiě)正確的程序指導(dǎo)如何編寫(xiě)正確的程序3)3)實(shí)現(xiàn)者實(shí)現(xiàn)者 指導(dǎo)如何指導(dǎo)如何編寫(xiě)語(yǔ)法檢查程序編寫(xiě)語(yǔ)法檢查程序Zhou, Erqiang48語(yǔ)法描述的用途School of Information and Software EngineeringZhou, ErqiangTHE ENDQUESTIONS49School of Information and Software Engineering考慮文法考慮文法： E T | E+T | E-T T F