編譯原理第2章 編譯基礎.ppt

(53頁)

'編譯原理第2章 編譯基礎.ppt'
第二章 編譯基礎1§2.0 概 述 對程序設計語言的描述是從語法、語義和語用三個因素來考慮。語法是對語言結構的定義。 語用則是從使用的角度去描述語言。語義是描述了語言的含義。2§2.0 概 述例如 賦值語句s=2*3.1416*r 的非形式化的描述為:語法:賦值語句由一個變量,后隨一個賦值號“=”,再在其后面跟一個表達式構成。語義:首先計算語句右部表達式的值,然后把所得結果送給左部變量中。語用:賦值語句可用來計算和保存表達式的值。 這種非形式化的描述,不夠清晰和準確,為了精確定義和描述程序設計語言,需采用形式化的方法。3形式化方法:是用一整套帶有嚴格規定的符號體系來描述問題的方法。 §2.1 符號表 一. 符號串與字母表 1.字母表:元素的非空有窮集合。兩含義:①字母表中至少包含一個元素。②字母表中元素可以是字母、數字或其它符號。例如:∑={ a , b , c }4 2. 符號(字符):字母表中元素。 3. 符號串:用字母表中的符號組成的任何有窮序列,也稱字。 例如:a , ab , bba , acab , …注意: ①符號串中符號的順序是很重要的。②不包含任何符號的符號串稱空串,記為ε。 |ε|=0③一個字母表上全部符號的集合是無窮的。 5 4. 符號串的前綴、后綴以及子串: 設x是一符號串,例如:x=abc符號串的前綴:從x的尾部刪除若干個(>=0)符號后所余下的部分。例如:ε,a,ab,abc符號串的后綴:從x的頭部刪除若干個(>=0)符號后所余下的部分。例如:ε,c,bc,abc子串:從x中刪除前綴和后綴之后所余下的部分。例如:ε,a,b,ab,bc,abc6 二.  符號串的運算 1.符號串的連接:設x,y是符號串,則串xy稱為它們的連接。 例如:設x=my y=computer xy=mycomputer yx=computermy 注意:對任意x Xε=εX=X 2.集合的和與乘積:設A,B是符號串的集合,則: A∪B={ω|ω∈A或ω∈B} AB={ xy|x∈A且y∈B} 例如:設 A={a,b} B={c,d} 則: A∪B={a,b,c,d} AB={ac,ad,bc,bd} 注意:Φ∪A=A∪Φ=A ΦA=AΦ=Φ {ε}A=A{ε}=A Φ={ }≠{ε} 7 3. 符號串的冪運算:若x是符號串,則 x0=ε, x1=x, x2=xx, … 例如:設 x=abc 則: x0=ε, x1=abc, x2=abcabc, … 4. 集合的冪運算:若A是符號串的集合,則 A0={ε}, A1=A, A2=AA, … 例如:設 A={a,b} 則: A0={ε}, A1={a,b}, A2={aa,ab,ba,bb}, … 5. 集合的A+(正閉包)和A*(自反傳遞閉包): 設A為任一集合,則: A+= A1∪A2∪A3∪ …∪An∪ … (A上所有符號串所組成的集合) A*=A0 ∪ A+={ε}∪ A+ 例如:設A={a,b,c} A+={a,b,c,aa,ab,ac,ba,bb,bc,…} A*={ε, a,b,c,aa,ab,ac,ba,bb,bc,… }8§2.2 文法和語言的形式定義 一.形式語言:是一字母表上按某種規則構成的所有符號串的集合。反之,任一字母表上符號串的集合均可定義為一個形式語言。  二.形式語言的描述:(三種方法) 1.當語言為有窮集合時,用枚舉法。例如:設有字母表 A={a,b,c}則:L1={a,b} L2={a,aa,ab,ac} L3={c,cc}9 2.用文法描述語言 例如:設有字母表 ∑ ={0,1} ∑+ ={0,1,00,01,11,10,000,100,… } 用A表示∑+ ,A→0 (定義為,生成,導出) 用產生式表示∑+: A→0 A→1 A→A0 A→A1  3.用自動機識別語言:構造一種裝置來識別語言,它可以判斷某符號串是否是該語言的句子。 例如: 1100→ → 是(接收) 11ab→ → 不是(不接收)  自動機10三.  文法的形式定義1. 規則(產生式):是一個符號與一個符號串的有序對(A,α),通常寫作:A→α或 A∷=α 2.非終結符與終結符: 非終結符:出現在規則左部能派生出符號或符號串的那些符號。通常用大寫字母表示。 終結符:是組成語言不可再分的基本符號,通常用小寫字母表示。 11 3.文法的形式定義:是規則的非空有窮集合,通常定義為四元組: G[S]=(Vn,Vt,P,S) 其中: Vn:規則中非終結符的集合。 Vn={A} Vt:規則中終結符的集合。 Vt={0,1} P: 文法規則式的集合。 P: A→0 A→1 A→A0 A→A1 S: 文法的開始符號(識別符號) 由它開始識別我們所定義的語言。S=A 例1 例2 例3 例4 例5 繼續12例1.設有字母表 ∑ ={a,b},請為語言 L={a2n, b2n | n>=1 } 設計一個文法。 首先分析語言中串的結構特征:L={aa,bb,aaaa,bbbb,… }(偶數個a或偶數個b組成)G[S ]=(Vn,Vt,P,S) 其中: Vn={A, B, D} Vt={a,b} P: A→aa|aaB|bb|bbD B→aa|aaB D→bb|bbD S=A易錯:A→aa|aaA|bb|bbA 會出現句子 aabb 擴大了語言范圍13問題:描述是否唯一?(回答不唯一) P1: A→B|D B→aa|aaB D→bb|bbD 等價文法: P2: A→B|D B→aa|aBa D→bb|bDb 返回14例2.已知語言 L={w|w是0和1的個數都為偶數的0,1串}。分析句子結構特征:001100 110000 0101①S→0A|1B (A,B奇數個0,1)②A→0 B→1③推出無窮串:A→0S B→1S④產生0101串:C→0B|1A A→1C B→0C 文法:G[L]=({A, B, C, S}, {0, 1} , P,S) P: S→0A|1B A→0S|1C|0 B→1S|0C|1 C→0B|1A 返回15例3. 試給出不以0開頭的正奇數文法(作業P36.7) 分析:奇數集合{1,3,5,7,9,11,…} 易錯: A→1|2*A+1 P: S→d1A|d3 A→d2A|d3 d1→1|2|3|4|5|6|7|8|9。省略部分。 ③改寫文法: E →0 | 2 | 4 | 6 | 8 N S E D 0 1NE1 042§2.4 文法的化簡和改造一.無用符號和無用產生式的刪除1.無用符號和無用產生式:我們說文法G中的一個符號x∈V是有用的,是指x必須同時滿足兩個條件:①存在α,β∈V* 有S=> αxβ (x至少出現在某句型中)②存在 t∈Vt* , 使 x=>t (從x能推出終結符號串) 否則,x是無用符號,如果一個產生式含有無用符號,則該產生式稱為無用產生式。2.刪除方法:(直觀看)①刪除P →P形式的產生式②刪除不能導出終結符號串的產生式③刪除在推導中永遠不使用的產生式*++43例如:化簡下述文法,其中S是文法的開始符號。①S →Be ②S →Ec ③A →Ae④A →e ⑤A →A ⑥B →Ce⑦B →Af ⑧C →Cf ⑨D →f⑩G →b解: 根據原則①,可消去⑤ 根據原則②,可消去② ⑥ ⑧ 根據原則③,可消去⑨ ⑩∴化簡后文法為: S →Be B →Af A →Ae A →e44二.單產生式的消除1.單產生式:右部僅含一個非終結符的產生式。 例如:A →B(文法含單產生式,增加編譯程序的時間和空間,∴要刪除)2.算法:①構造非終結符號集β,對文法G中的每個非終結符A,求: βA={ B | A=>B, B∈VN }②若有A=>B,且文法G中有B →x , 則在文法中擴充規則: A →x , 并且刪除單產生式和無用產生式 ++45例如:設有文法G1[A]: A →B | dE B →A | D |b D →B | d E →e |Ea 求:不含單產生式的文法G2 ,使得L(G1)=L(G2)。解: ∵A=>A=>dE A=>B=>b A=>D=>d ∴ βA={ A , B , D }同理:∵B=>A=>dE B=>B=>b B=>D=>d D=>A=>dE D=>B=>b D=>D=>d ∴ βB={ A , B , D } βD={ A , B , D } βE={ }擴充規則:A →b |d , B →dE | d , D →dE | b 刪除單產生式得文法G2’[A]:A →dE | b |d , B →dE |b | d , D →dE | b |d , E →e | Ea刪除無用產生式:由于B, D均不在任何句型中出現,故刪除∴文法G2[A]: A →dE | b |d E →e | Ea+++++++++46§2.5 文法和語言的分類一. 0型文法(PSG,短語文法,無限制文法): 若文法G中任一產生式具有如下形式:α→β α∈V+,β∈ V* ,則稱為0型文法。 0型文法所描述的語言稱為0型語言或遞歸可枚舉語言。0型語言可以用圖靈機TM(Turing Maching)來識別。例如:G[S]=( { S, A, B, C, D, E }, { a } , P , S )P: S →ACaB , Ca →aaC , CB →DB , CB →E aD →Da , AD →AC , aE →Ea , AE →ε 以上文法是一個0型文法,所產生的語言為:L(G)={ai | i是2的正整數次方}={aa , aaaa ,aaaaaaaa , … }特點:沒有對產生式α→β作更多的限制,僅要求α中至少含有一個非終結符。47二.1型文法(上下文有關文法) 簡寫CSG(Context Sensitive Grammar) 若文法G中任一產生式具有如下形式:αAβ→ αUβ A∈VN , U∈V+, α,β∈ V* ,則稱為1型文法。 1型文法所描述的語言稱為1型語言或上下文有關語言。1型語言可以用線性界限自動機LBA(Linear Bounded Automata)來識別。例如:G[S]=( { S, A, B, C, D }, { a, b, c } , P , S )P: S →A , A →aABD , A →abD , DB →CB CB →CD , CD →BD , bB →bb , D →c 以上文法是一個1型文法,所產生的語言為: L(G)={an bn cn | n≥1 }當n=1時:S=>A=>abD=>abc當n=2時: S =>aABD=>a2 bDBD=> a2 bCBD=> a2 bCDD => a2 bBDD=> a2 b2 DD=> a2 b2 c248三.2型文法(上下文無關文法) 簡寫CFG(Context Free Grammar) 若文法G中任一產生式具有如下形式: A→ β A∈VN , β∈ V* ,則稱為2型文法。 2型文法所描述的語言稱為2型語言,或者上下文無關語言。 2型語言可以用下推自動機PDA(Push Down Automata)來識別。例如:G[S]=( { S }, { a, b } , P , S ) P: S→aSb , S→ab 以上文法是一個2型文法,所產生的語言為: L(G)={an bn | n≥1 }通常,利用2型文法描述高級語言的句法部分,然后用PDA來識別。49四. 3型文法(正規文法) 若文法G中任一產生式具有如下形式: A→aB , A→a 右線性文法 A→Ba , A→a 左線性文法 其中: A, B∈VN , a∈ VT , 3型文法所描述的語言稱為正規語言,或者有限狀態語言。 3型語言可以用有窮自動機FA(Finite Automata) 來識別。 50 例如,用左線性正規文法和右線性正規文法定義標識符 用I代表標識符; l代表任意一個字母; d代表任意一個數字; 則定義標識符的文法為:左線性文法: P: I→ l | Il | Id右線性文法: P: I→ l | lT T→l | d | lT| dT51 例如,用左線性正規文法和右線性正規文法定義無符號整數 用N代表無符號整數; d代表任意一個數字;則定義的無符號整數文法為:左線性文法: P: N→ Nd | d右線性文法: P: N→ dN | d52 由上述四類文法的定義可知, 從0型文法到3型文法, 是逐漸增加對規則的限制條件而得到的,因此每一種正規文法都是上下文無關的文法,每一種上下文無關的文法都是上下文有關的文法,而每一種上下文有關的文法都是0型文法, 而由它們所定義的語言類是依次縮小的,有 L0 ? L1 ? L2 ? L3 。 53
關 鍵 詞:
編譯 原理 基礎
 天天文庫所有資源均是用戶自行上傳分享,僅供網友學習交流,未經上傳用戶書面授權,請勿作他用。
關于本文
本文標題:編譯原理第2章 編譯基礎.ppt
鏈接地址: http://www.476824.live/p-51497021.html
關于我們 - 網站聲明 - 網站地圖 - 資源地圖 - 友情鏈接 - 網站客服點擊這里,給天天文庫發消息,QQ:1290478887 - 聯系我們

本站為“文檔C2C交易模式”,即用戶上傳的文檔直接賣給(下載)用戶,本站只是中間服務平臺,本站所有文檔下載所得的收益歸上傳人(含作者)所有【成交的100%(原創)】。本站是網絡服務平臺方,若您的權利被侵害,侵權客服QQ:1290478887 歡迎舉報。

[email protected] 2017-2027 http://www.476824.live 網站版權所有

粵ICP備19057495號 

收起
展開
球探网即时蓝球比分 极速11选5的正规网站 七乐彩 神圣计划 丰原药业股票行情 湖北11选5走势图一定牛牛彩 幸运农场复式奖金计算 36选7走势图福建省走势图 天津时时彩开奖结果 东莞配资公司 安徽快三实用技巧 山东十一选五推荐计划