• /  113
  • 下載費用: 29.9積分  

編譯原理課件 第三章.ppt

'編譯原理課件 第三章.ppt'
復習:程序語言的語法描述 幾個概念:考慮一個有窮 字母表∑ 字符集其中每一個元素稱為一個字符∑上的字(也叫字符串) 是指由∑中的字符所構成的一個有窮序列不包含任何字符的序列稱為空字,記為ε用∑*表示∑上的所有字的全體,包含空字ε復習:程序語言的語法描述 ∑*的子集U和V的連接(積)定義為UV={ ?? | ??U & ??V } V自身的 n次積記為 Vn=VV…V規定V0={?},令 V*=V0∪V1∪V2∪V3∪… 稱V*是V的閉包;記 V+=VV* ,稱V+是V的正規閉包。復習:程序語言的語法描述 上下文無關文法的定義: 一個上下文無關文法G是一個四元式 G=(VT,VN,S,P),其中VT:終結符集合(非空)VN:非終結符集合(非空),且VT ? VN=?S:文法的開始符號,S?VNP:產生式集合(有限),每個產生式形式為P??, P?VN, ? ? (VT ? VN)*開始符S至少必須在某個產生式的左部出現一次。復習:程序語言的語法描述 定義:稱?A?直接推出???,即?A????? 僅當A ? ?是一個產生式, 且?, ?? (VT ? VN)* 。如果?1 ? ?2 ? ? ??n,則我們稱這個序列是從?1到?n的一個推導。若存在一個從?1到?n的推導,則稱?1可以推導出?n 。通常,用 表示:從?1出發,經過一步或若干步,可以推出?n。 用 表示:從?1出發,經過0步或若干步,可以推出?n。 所以 : 即 或定義:假定G是一個文法,S 是它的開始符號。如果 ,則?稱是一個句型。僅含終結符號的句型是一個句子。文法G所產生的句子的全體是一個語言,將它記為 L(G)。復習:程序語言的語法描述 最左推導:任何一步? ? ?都是對?中的最左非終結符進行替換。 最右推導:任何一步? ? ?都是對?中的最右非終結符進行替換。復習:程序語言的語法描述 用一張圖表示一個句型的推導,稱為語法樹。E ?(E)?(E+E)?(E*E+E)?(i*E+E)?(i*i+E)?(i*i+i)E ?(E)?(E+E)?(E+i)?(E*E+i)?(E*i+i)?(i*i+i)復習:程序語言的語法描述 定義:如果一個文法存在某個句子對應兩顆不同的語法樹,則說這個文法是二義的。語言的二義性:一個語言是二義性的,如果對它不存在無二義性的文法。復習:程序語言的語法描述 形式語言鳥瞰0型(短語文法,圖靈機): 產生式形如: ? ? ? 其中:?? (VT ? VN)*且至少含有一個非終結符;?? (VT ? VN)*1型(上下文有關文法,線性界限自動機): 產生式形如: ? ? ? 其中:|?| ? |?|,僅 S?? 例外。復習:程序語言的語法描述 形式語言鳥瞰2型(上下文無關文法,非確定下推自動機): 產生式形如: A ? ? 其中:A? VN;?? (VT ? VN)*。3型(正規文法,有限自動機): 產生式形如: A ? ?B 或 A ? ? 其中: ?? VT*;A,B?VN 產生式形如: A ? B? 或 A ? ? 其中: ?? VT*;A,B?VN第三章 詞法分析詞法分析的任務:從左至右逐個字符地對源程序進行掃描,產生一個個單詞符號。詞法分析器(Lexical Analyzer) 又稱掃描器(Scanner):執行詞法分析的程序3.1 對于詞法分析器的要求一、詞法分析器的功能和輸出形式功能:輸入源程序、輸出單詞符號單詞符號的種類:基本字:如 begin,repeat,?標識符——表示各種名字:如變量名、數組名和過程名常數:各種類型的常數運算符:+,-,*,/,?界符:逗號、分號、括號和空白輸出的單詞符號的表示形式:(單詞種別,單詞自身的值)單詞種別通常用整數編碼表示。若一個種別只有一個單詞符號,則種別編碼就代表該單詞符號。假定基本字、運算符和界符都是一符一種。若一個種別有多個單詞符號,則對于每個單詞符號,給出種別編碼和自身的值。標識符單列一種;標識符自身的值表示成按機器字節劃分的內部碼。常數按類型分種;常數的值則表示成標準的二進制形式。例 C程序 while (i>=j) i--;輸出單詞符號:=, - >例 FORTRAN程序IF (5.EQ.M) GOTO 100輸出單詞符號:邏輯IF (34,-)左括號 (2,-)整常數 (20, ‘5’的二進制)等號 (6,-)標識符 (26, ‘M’)右括號 (16,-)GOTO (30,-)標號 (19, ‘100’的二進制)二、詞法分析器作為一個獨立子程序詞法分析是作為一個獨立的階段,是否應當將其處理為一遍呢?作為獨立階段的優點:結構簡潔、清晰和條理化,有利于集中考慮詞法分析一些枝節問題。不作為一遍:將其處理為一個子程序。詞法分析器詞法分析器語法分析器符號表源程序單詞符號取下一單詞...詞法分析器的結構預處理子程序掃描器輸入緩沖區掃描緩沖區單詞符號輸入列表3.2 詞法分析器的設計輸入串放在輸入緩沖區中。預處理子程序:剔除無用的空白、跳格、回車和換行等編輯性字符;區分標號區、捻接續行和給出句末符等掃描緩沖區 ↑ ↑ 起點 搜索指示器 指示器一、輸入、預處理 WhatALong…Word … WhatALong…Wo rdrd… WhatALong…Word… WhatALong…Wo二、單詞符號的識別:超前搜索1 基本字識別:例如:DO99K=1,10 DO 99 K = 1,10 IF(5.EQ.M)GOTO55 IF (5.EQ.M) GOTO 55DO99K=1.10IF(5)=55需要超前搜索才能確定哪些是基本字2 標識符識別:字母開頭的字母數字串,后跟界符或算符3 常數識別:識別出算術常數并將其轉變為二進制內碼表示。有些也要超前搜索。 5.EQ.M 5.E084 算符和界符的識別把多個字符符合而成的算符和界符拼合成一個單一單詞符號。:=, **, .EQ. , ++,--,>=三、狀態轉換圖1 概念狀態轉換圖是一張有限方向圖。213XY結點代表狀態,用圓圈表示。狀態之間用箭弧連結,箭弧上的標記(字符)代表射出結狀態下可能出現的輸入字符或字符類。一張轉換圖只包含有限個狀態,其中有一個為初態,至少要有一個終態。識別標識符的狀態轉換圖123字母其他字母或數字*識別整常數的狀態轉換圖123數字其他數字*一個狀態轉換圖可用于識別(或接受)一定的字符串。2 例子助憶符:直接用編碼表示不便于記憶,因此用助憶符來表示。省略部分。q,a)= ?1(q,a), 當q?S1-{f1}, a??1∪{?}(b) ?(q,a)= ?2(q,a), 當q?S2, a??2∪{?}(c) ?(f1,?)={q2} M的狀態轉換如右圖所示。 L(M)=L(M1)L(M2) =L(r1)L(r2)=L(r)。?M1q1f1M2q2f2情形3:r=r1*。設M1同情形1。令M=,其中q0, f0?S1,?定義如下:(a) ?(q0,?)=?(f1,?)={q1, f0}(b) ?(q,a)= ?1(q, a), 當q?S1-{f1}, a??1∪{?}。M的狀態轉換如右圖所示。L(M) = L(M1)* = L(r1)* = L(r)至此,結論2獲證。?M1q1f1q0f0???1) 構造?上的NFA M’ 使得 L(V)=L(M’)首先,把V表示成XYV上述證明過程實質上是一個將正規表達式轉換為有限自動機的算法。代之為ijV1V2kikV1V2代之為ijV1|V2ijV2V1代之為ikV1*ij??kV1然后,按下面的三條規則對V進行分裂逐步把這個圖轉變為每條弧只標記為?上的一個字符或?,最后得到一個NFA M’,顯然L(M’)=L(V)(a|b)*(aa|bb)(a|b)*XY(a|b)*(aa|bb)(a|b)*XY?514236ab???abababIIaIb{X,5,1}{5,3,1}{5,4,1}{5,3,1}{5,2,3,1,6,Y}{5,4,1}{5,4,1}{5,3,1}{5,2,4,1,6,Y}{5,2,3,1,6,Y}{5,2,3,1,6,Y}{5,4,6,1,Y}{5,4,6,1,Y}{5,3,6,1,Y}{5,2,4,1,6,Y}{5,2,4,1,6,Y}{5,3,6,1,Y}{5,2,4,1,6,Y}{5,3,6,1,Y}{5,2,3,1,6,Y}{5,4,6,1,Y}XY?514236ab???abababIab0121322143344655656340123546aabbbabaabababFA正規集正規式DFANFA正規文法3.3.13.3.23.3.33.3.43.3.5DFA3.3.63.3.6 確定有限自動機的化簡對DFA M的化簡:尋找一個狀態數比M少的DFA M’,使得L(M)=L(M’)假設s和t為M的兩個狀態,稱s和t等價:如果從狀態s出發能讀出某個字?而停止于終態,那么同樣,從t出發也能讀出?而停止于終態;反之亦然。兩個狀態不等價,則稱它們是可區別的。對一個DFA M最少化的基本思想: 把M的狀態集劃分為一些不相交的子集,使得任何兩個不同子集的狀態是可區別的,而同一子集的任何兩個狀態是等價的。最后,讓每個子集選出一個代表,同時消去其他狀態。具體做法: 對M的狀態集進行劃分首先,把S劃分為終態和非終態兩個子集,形成基本劃分?。 假定到某個時候,?已含m個子集,記為?={I(1),I(2),?,I(m)},檢查?中的每個子集看是否能進一步劃分:對某個I(i),令I(i)={s1,s2, ?,sk},若存在一個輸入字符a使得Ia(i) 不會包含在現行?的某個子集I(j)中,則至少應把I(i)分為兩個部分。例如,假定狀態s1和s2經a弧分別到達t1和t2,而t1和t2屬于現行?中的兩個不同子集,說明有一個字?, t1讀出?后到達終態,而t2讀出?后不能到達終態,或者反之,那么對于字a? , s1讀出a?后到達終態,而s2讀出a?不能到達終態,或者反之,所以s1和s2不等價。s1t1as2t2a?i?j則將I(i)分成兩半,使得一半含有s1 : I(i1)={s|s?I(i)且s經a弧到達t, 且t與t1屬于現行?中的同一子集} 另一半含有s2 : I(i2)=I(i)-I(i1)s1t1as2t2a?i?j一般地,對某個a和I(i),若Ia(i) 落入現行?中 N個不同子集,則應把I(i)劃分成N個不相交的組,使得每個組J的Ja都落入的?同一子集。這樣構成新的劃分。重復上述過程,直到?所含子集數不再增長。對于上述最后劃分?中的每個子集,我們選取每個子集I中的一個狀態代表其他狀態,則可得到化簡后的DFA M’。若I含有原來的初態,則其代表為新的初態,若I含有原來的終態,則其代表為新的終態。0123546aabbbabaabababI(1)={0, 1, 2} I(2)={3, 4, 5, 6} Ia(1) ={1, 3} I(11) ={0, 2} I(12) ={1}I(2)={3, 4, 5, 6} I(11) ={0, 2}Ia(11) ={1} Ib(11) ={2, 5} I(111) ={0} I(112) ={2}I(12) ={1} I(2)={3, 4, 5, 6} Ia(2) ={3, 6} Ia(2) ={4, 5} 0123546aabbbabaababab0123aabbbaabFA正規集正規式DFANFA正規文法3.3.13.3.23.3.33.3.43.3.5DFA3.3.63.4 詞法分析器的自動產生--LEX詞法分析程序自動產生器詞法分析程序LLEX源程序 詞法分析程序L單詞符號輸入串狀態轉換矩陣控制執行程序AUXILIARY DEFINITIONletter?A|B|...|Zdigit ?0|1|...|9RECOGNITION RULES1 DIM { RETURN (1,-) } 2 IF { RETURN (2,-) }3 DO { RETURN (3,-) }4 STOP { RETURN (4,-) }5 END { RETURN (5,-) }6 letter(letter|digit) * { RETURN (6, TOKEN) } 7 digit(digit)* { RETURN (7, DTB) }8 = { RETURN (8, -) }9 + { RETURN (9,-) }10 * { RETURN (10,-) } 11 ** { RETURN (11,-) } 12 , { RETURN (12,-) } 13 ( { RETURN (13,-) } 14 ) { RETURN (14,-) }正規式LEX的工作過程:首先,對每條識別規則Pi構造一個相應的非確定有限自動機Mi;然后,引進一個新初態X,通過?弧,將這些自動機連接成一個新的NFA;最后,把M確定化、最小化,生成該DFA的狀態轉換表和控制執行程序X?P2???M1MmM2P1Pm??作業P64-7,8,12,14 例: 對下圖NFA M構造其DFA.aabbbXY解: 用子集法構造轉換矩陣不可識別ba !{1, 2} {0}ba,bab021DFA M’a,bab01化簡后的DFA M’ ba ?。?!
關 鍵 詞:
第三 編譯 原理
 天天文庫所有資源均是用戶自行上傳分享,僅供網友學習交流,未經上傳用戶書面授權,請勿作他用。
關于本文
本文標題:編譯原理課件 第三章.ppt
鏈接地址: http://www.476824.live/p-51497019.html
關于我們 - 網站聲明 - 網站地圖 - 資源地圖 - 友情鏈接 - 網站客服點擊這里,給天天文庫發消息,QQ:1290478887 - 聯系我們

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

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

粵ICP備19057495號 

收起
展開
球探网即时蓝球比分 内蒙古快三快3豹子玩法 股票融资比例下调了 河北快三玩法大小 黑龙江11选5开奖基本走势 吉林快三和走势图全图 股票日k线走势图怎么看 广西快3下载安装到手机 同花顺怎么新手买股票 四川快乐十二软件下载 腾讯分分彩是腾讯的吗