第二章語言的基本知識(參考版)
2024-10-02 14:03本頁面
【正文】 作業(yè) 。文法 () 中的表達(dá)式文法， a是終結(jié)符號。 把描述詞法的正規(guī)文法從描述語法的上 下文無關(guān)文法中分離出來。 上下文無關(guān)文法。 定義 如果一個上下文無關(guān)文法 G中存在具有下列特征的非終結(jié)符 A: A αAβ 其中 α,β∈ {VT∪ VN}+,則稱 A為自嵌套的 , +? 上下文無關(guān)語言和正則語言的區(qū)別 48 包含自嵌套非終結(jié)符號的文法是 語言 {anbn|n?0}是上下文無關(guān)語言，原因是找不到一個非自嵌套的上下文無關(guān)文法描述它； 語言 {anbm|n， m ? 0}是正則語言 ,原因是存在一個正規(guī)文法描述它。 例 L2={anbmdm|n,m≥0}，它是檢查過程聲明的形參個數(shù)和過程引用的參數(shù)個數(shù)一致問題的抽象。 例如 ,aabcaab就是 L1的一個句子。即， S αAβ 且 A γ， γ∈ VT* *? +? 定義之 3,4 44 形式語言概觀 ?. 1 文法分類 ?. 2 非上下文無關(guān)文法的語言結(jié)構(gòu) ?. 3 上下文無關(guān)語言和正規(guī)語言的區(qū)別 45 逐漸對產(chǎn)生式施加限制 四種類型： 0型， 1型， 2型， 3型 0型： G=(VT,VN,S,P) 規(guī) 則形式 ： ??? ?,?? (VT?VN)*, ??? 推 導(dǎo)： ??????? 1型（上下文有關(guān)） ： ??????? 規(guī) 則形式 ： ?A?? ??? A ?VN, ?,?,.? ? (VT?VN)*, ??? 2型（上下文無關(guān)）： 規(guī) 則形式 ： A?? A ?VN， ? ? (VT?VN)* 3型（右線性）： A? aB A ? a （ 左 線性） A? Ba A ? a a ?VT?{?} 文法分類 46 在我們使用的程序語言中 ,有些語言結(jié)構(gòu)并不是總能用上下文無關(guān)文法描述的。例如， ?aibicj?i,j?1?? ?aibjcj?i,j?1? 存在一個二義性的句子 akbkck。 描述 if語句的無二義性文法的產(chǎn)生式 : 43 3. 對于任意一個上下文無關(guān)文法，不存在 一個算法，判定它是無二義性的；但能給出一組充分條件，滿足這組充分條件的文法是無二義性的。幾點說明： 1 . 一般來說，程序語言存在無二義性文法， 對于表達(dá)式來說，文法（ 2 .1）是無二義性的。如果一個文法包含二義性的句子 ,則稱這個文法是二義性的 。 用子樹解釋短語，直接短語，句柄 : 36 E ?E+T ?T+T ?F+T ? a1+T ? a1+T*F ? a1+F * F ? a1+a2 *F E+T T,T+T F,F+T a1, a1+T a1, T*F, a1+T*F a1, F,F*F, a1+F*F a1, a2,a1+ a2 *F, a2 *F a1, a2, a3, a2 * a3 a1+ a2 *a3 E E + T T F a1 T * F F a2 a3 ?a1+a2 *a3 短語 例 (a) 37 E ?E+T ?E+T*F ?E+T*a3 ?E+F* a3 ?E+a2 * a3 ?T+a2 * a3 ?F+a2 * a3 E E + T T F a1 T * F F a2 a3 ?a1+a2 *a3 例 (b) 38 1. 描述一個句子的文法不是唯一的； 2. 2. 對于一個句子的分析應(yīng)是唯一的。 句柄：一個句型的分析樹中最左那棵只有父子兩代的子樹的所有葉子的自左至右排列。例如： S A b S a S b a A a a 三 . 子樹 35 短語：一棵子樹的所有葉子自左至右排列起來形成一個相對于子樹根的短語。 分析樹是推導(dǎo)的圖形表示。分析樹并未描述推導(dǎo)過程。 一 .分析樹的定義 30 G=(VT,VN,S,P), 其中 P: S?aAS?a A ?SbA ?SS ?ba 3 1 2 4 6 5 7 8 9 10 11 S a A S S b A a a b a 例 31 根據(jù)推導(dǎo)序列，對每步推導(dǎo)畫相應(yīng)分枝 A S a S b S A a a b a ?aSbAS ?aabAS ?aabbaS ?aabbaa ?aAS S 二 . 如何畫出分析樹 (） 32 根據(jù)歸約序列，對每步歸約畫相應(yīng)分枝 A S a S b S A a a b a ?aAa ?aSbAa ?aSbba
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1