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

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

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

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

4、oftware Engineering構(gòu)造規(guī)則構(gòu)造規(guī)則語法圖的構(gòu)造語法圖的構(gòu)造 N 1| 2| n對(duì)應(yīng)一個(gè)語法圖對(duì)應(yīng)一個(gè)語法圖Zhou, Erqiang7轉(zhuǎn)換圖定義語言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é)符序列： 從從入口邊入口邊 通過語法圖通過語法圖 到到出口邊出口邊 通過時(shí)恰恰能識(shí)別該終結(jié)符序列通過時(shí)恰恰能識(shí)別該終結(jié)符序列語言：語言： 語法圖語法圖能識(shí)別能識(shí)別的的 所有所有終結(jié)符序列終結(jié)符序列的集合的集合Zhou, Erqiang10識(shí)別原則School of Information and Software Engineering標(biāo)識(shí)符標(biāo)識(shí)符Zhou, Erqiang11表達(dá)式語法圖(表達(dá)式表達(dá)式運(yùn)算符運(yùn)算符表達(dá)式表達(dá)式表達(dá)式表達(dá)式)School of Information and S

6、oftware Engineering數(shù)字?jǐn)?shù)字Zhou, Erqiang12 語義語義（規(guī)則）語義（規(guī)則） 定義語言定義語言合法合法句子的句子的含義含義 即句子的作用和意義的規(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描述語法描述語法 文法和語法圖文法和語法圖描述語義描述語義 尚尚無無普遍接受的描

7、述工具普遍接受的描述工具 許多語言仍采用許多語言仍采用自然語言自然語言描述語義描述語義Zhou, Erqiang13語義的表示School of Information and Software Engineering自然語言描述自然語言描述 FORTRAN形式化描述（形式化描述（BNFBNF） ALGOL60轉(zhuǎn)換圖（語法圖）轉(zhuǎn)換圖（語法圖） PASCALZhou, Erqiang14語法的表示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é)符，語言變量，語言變量非終結(jié)符非終結(jié)符, , 箭頭箭頭, , 終結(jié)符和非終結(jié)符序列終結(jié)符和非終結(jié)符序列 產(chǎn)生式產(chǎn)生式，productionZhou, Erqiang15形式化描述School of Information and Software Engineering指定一個(gè)非終結(jié)符為指定一個(gè)非終結(jié)符為開始符號(hào)開始符號(hào)定義：定義： 終結(jié)符集合：終結(jié)符集合：V VT T 非終結(jié)符集合：非終結(jié)符集合：V VN N 產(chǎn)生式集合：產(chǎn)生式集合：P P 開始符號(hào)：開始符號(hào)：S SG = (V

9、G = (VT T, V, VN N, S, P), S, P) G G稱為一個(gè)稱為一個(gè)文法文法 文法文法是對(duì)是對(duì)語法語法的形式化描述的形式化描述Zhou, Erqiang16形式化描述School of Information and Software Engineering歷史背景歷史背景 喬姆斯基喬姆斯基( (ChomskyChomsky) ) 于于19561956年建立語言的形式描述年建立語言的形式描述深遠(yuǎn)影響深遠(yuǎn)影響 語言學(xué)、計(jì)算機(jī)科學(xué)語言學(xué)、計(jì)算機(jī)科學(xué) 程序語言的設(shè)計(jì)程序語言的設(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)說明幾點(diǎn)說明* 表示任意多次（表示任意多次（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 稱為稱為候選式候選式 b1 | b2 |bnZhou, Erqiang22其中其中| |表示表示“或者或者” School of Information and Software Engineering非終結(jié)符非終結(jié)符 英文英文大寫字母大寫字母表示表示開始符號(hào)開始符號(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型文法（無限制文法）型

14、文法（無限制文法） 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ī)則描述無窮無窮語言語言文法等價(jià)文法等價(jià) 兩個(gè)文法兩個(gè)文法G G和和G,G,如果有如果有L(G)=L(G) 則稱則稱G G和和GG等價(jià)等價(jià)Zhou, Erqiang42文法實(shí)例小結(jié)School of Information and Soft

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

16、gineering一棵一棵有序有序的標(biāo)記樹的標(biāo)記樹結(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)樹總結(jié)School of Information and Software Engineering推導(dǎo)樹的邊緣：推導(dǎo)樹的邊緣： 推導(dǎo)樹所有葉結(jié)點(diǎn)推導(dǎo)樹所有葉結(jié)點(diǎn)從左到右從左到右的連接。的連接。文法的二義

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

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