第二章語言的基本知識-資料下載頁
2025-09-19 14:03本頁面
【導讀】學習本章的目的。文法和語言的定義。構造編譯程序的算法是從研究源程序及。語言分語法，語義和語用。字母表是符號的非空有窮集合。序寫出而得到的符號串。真前綴，真后綴，真子串:x≠s?：L0={ε}，L1＝L，L*＝∪Li=L0∪L1∪L2∪L3∪…四.最左推導和最右推導。短語，直接短語，句柄。VT是一個非空有窮終結符號集合；開始符號S至必須。在某個產生式的左部出現(xiàn)一次。
【正文】 ed_s else mathed_s ?other unmathed_s ?if expr then S ? if expr then mathed_s else unmathed_s 它顯然比較復雜，因此： 2. 在能駕馭的情況下，使用 二義性文法。 描述 if語句的無二義性文法的產生式 : 43 3. 對于任意一個上下文無關文法，不存在 一個算法，判定它是無二義性的；但能給出一組充分條件，滿足這組充分條件的文法是無二義性的。 4. 存在先天二義性語言。例如， ?aibicj?i,j?1?? ?aibjcj?i,j?1? 存在一個二義性的句子 akbkck。 壓縮過的文法（化簡了的文法）： 1．形式的產生式： A→ A ?P ； 2. 每個非終結符號 A必須都有用處。即， S αAβ 且 A γ， γ∈ VT* *? +? 定義之 3,4 44 形式語言概觀 ?. 1 文法分類 ?. 2 非上下文無關文法的語言結構 ?. 3 上下文無關語言和正規(guī)語言的區(qū)別 45 逐漸對產生式施加限制 四種類型： 0型， 1型， 2型， 3型 0型： G=(VT,VN,S,P) 規(guī) 則形式 ： ??? ?,?? (VT?VN)*, ??? 推 導： ??????? 1型（上下文有關） ： ??????? 規(guī) 則形式 ： ?A?? ??? A ?VN, ?,?,.? ? (VT?VN)*, ??? 2型（上下文無關）： 規(guī) 則形式 ： A?? A ?VN， ? ? (VT?VN)* 3型（右線性）： A? aB A ? a （ 左 線性） A? Ba A ? a a ?VT?{?} 文法分類 46 在我們使用的程序語言中 ,有些語言結構并不是總能用上下文無關文法描述的。 例 L1={wcw|w∈ {a,b}+}。 例如 ,aabcaab就是 L1的一個句子。這個語言是檢查程序中標識符的聲明應先于引用的抽象 。 例 L2={anbmdm|n,m≥0}，它是檢查過程聲明的形參個數(shù)和過程引用的參數(shù)個數(shù)一致問題的抽象。 47 語言中過程定義和引用的語法并不涉及到參數(shù)個數(shù)，例如， Pascal的過程語句可描述為 scall→ id(rlist) rlist→ rlist, r |r 實參和形參個數(shù)的一致性檢查也是放在語義分析階段完成的。 定義 如果一個上下文無關文法 G中存在具有下列特征的非終結符 A: A αAβ 其中 α,β∈ {VT∪ VN}+,則稱 A為自嵌套的 , +? 上下文無關語言和正則語言的區(qū)別 48 包含自嵌套非終結符號的文法是 語言 {anbn|n?0}是上下文無關語言，原因是找不到一個非自嵌套的上下文無關文法描述它； 語言 {anbm|n， m ? 0}是正則語言 ,原因是存在一個正規(guī)文法描述它。 在程序語言中，與詞法有關的規(guī)則屬于正規(guī)文法；與局部語法有關的規(guī)則屬于上 下文無關文法；而與全局語法和語義有關的部分往往要用上下文有關文法來描述。 上下文無關文法。 49 用上下文有關文法描述程序語言不僅相當困難，將使語法定義變得煩雜，難懂，而且一般不能構造有效的分析程序，因此，通常用上下文無關文法描述，而把與上下文有關的限制包含在非形式描述的全局語法與語義中。 把描述詞法的正規(guī)文法從描述語法的上 下文無關文法中分離出來。在分離出正則文法后的上下文無關文法中，這些單詞符號是屬于終結符號 VT中的符號。文法 () 中的表達式文法， a是終結符號。 為什么不用上下文有關文法描述程序語言？ 50 ： G[S]: ( b ) , ( c ), ( d ), ( e ) G[S]: ( a ), ( b ) , ( c ), ( d ) G[bexpr]: ( b ) 1. 寫出下面語言的三型文法： （ a) ?an?n?0? (b) ?anbm?n,m?1? (c) ?anbmck?n,m?1? (d)Pascal的標識符 (e) Pascal的整數(shù) 2. 已知文法 G[S]， 其產生式如下： S?(S)?? (a)L(G[S])是什磨？ (b)對于 (a)的 結果，試給出證明。 作業(yè)
教學課件相關推薦
鄂ICP備17016276號-1