編譯技術：第04章01 文法語法

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

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

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

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

5、e Engineering生成的串是哪種形式？生成的串是哪種形式？一個一個合法的合法的終結符序列：終結符序列： 從從入口邊入口邊 通過語法圖通過語法圖 到到出口邊出口邊 通過時恰恰能識別該終結符序列通過時恰恰能識別該終結符序列語言：語言： 語法圖語法圖能識別能識別的的 所有所有終結符序列終結符序列的集合的集合Zhou, Erqiang10識別原則School of Information and Software Engineering標識符標識符Zhou, Erqiang11表達式語法圖(表達式表達式運算符運算符表達式表達式表達式表達式)School of Information and S

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

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

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

9、G = (VT T, V, VN N, S, P), S, P) G G稱為一個稱為一個文法文法 文法文法是對是對語法語法的形式化描述的形式化描述Zhou, Erqiang16形式化描述School of Information and Software Engineering歷史背景歷史背景 喬姆斯基喬姆斯基( (ChomskyChomsky) ) 于于19561956年建立語言的形式描述年建立語言的形式描述深遠影響深遠影響 語言學、計算機科學語言學、計算機科學 程序語言的設計程序語言的設計、編譯方法編譯方法、 計算復雜性計算復雜性等等Zhou, Erqiang17文法School of I

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

11、( ，b b) )記為記為 := b b 或或 b bZhou, Erqiang19School of Information and Software Engineering關于關于 和和 b b 和和b b是由是由終結符終結符、非終結符非終結符組成的串組成的串 至少應含有一個至少應含有一個非終結符非終結符即即 V*VNV* b b V* 其中其中 V= VT VN Zhou, Erqiang20產(chǎn)生式School of Information and Software Engineering幾點說明幾點說明* 表示任意多次（表示任意多次（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)生式的簡化 b b1 b b2 b bn b bn 稱為稱為候選式候選式 b1 | b2 |bnZhou, Erqiang22其中其中| |表示表示“或者或者” School of Information and Software Engineering非終結符非終結符 英文英文大寫字母大寫字母表示表示開始符號開始符號

13、僅有僅有1 1個個 第一個產(chǎn)生式的第一個產(chǎn)生式的左邊左邊符號符號Zhou, Erqiang23產(chǎn)生式的約定School of Information and Software Engineering文法的表示描述文法描述文法 直接給出產(chǎn)生式集合直接給出產(chǎn)生式集合例如算術表達式文法例如算術表達式文法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型文法型文法( (上下文上下文有關有關文法文法) ) | | | = | 0Zhou, Erqiang41文法實例School of Information and Software Engineering文法的重要性文法的重要性 有限有限規(guī)則描述規(guī)則描述無窮無窮語言語言文法等價文法等價 兩個文法兩個文法G G和和G,G,如果有如果有L(G)=L(G) 則稱則稱G G和和GG等價等價Zhou, Erqiang42文法實例小結School of Information and Soft

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

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

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

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