形式語言自動(dòng)機(jī)——翻譯原理

1、第六章 翻譯原理“翻譯” 由一對(duì)字符串組成的對(duì)偶集合。編譯程序 - <源程序，目標(biāo)程序>編譯過程： 1. 詞法分析 - < 字符串，單詞>2. 句法分析 - <單詞的字符串，樹表示的字符串>3代碼生成 - <樹表示的字符串，機(jī)器/匯編語言 >定義翻譯的兩種基本方法： 翻譯式；轉(zhuǎn)換器翻譯式： 模仿語言的文法定義方法，定義一個(gè)對(duì)偶系統(tǒng)（也是一個(gè)文法）,使在句子的推導(dǎo)過程中，相應(yīng)于每個(gè)句型，同時(shí)也推算出其輸出句型（翻譯句型）。這樣，在派生出句子時(shí)，也同時(shí)產(chǎn)生了其翻譯句。轉(zhuǎn)換器：模仿語言的自動(dòng)機(jī)識(shí)別方法，但在自動(dòng)機(jī)的每次動(dòng)作中，還發(fā)送一個(gè)有限長(zhǎng)度的輸出字

2、符串。$6.1 翻譯的形式化一 翻譯的一般定義設(shè)L1 ÍT*，L2 Í*，從L1 到L2 的翻譯是從T * * 的一個(gè)映射關(guān)系。 如果對(duì)于輸入句子x，存在（x, y）在映射H中，則稱句子y為x的輸出。注： 一般的翻譯可能不止一個(gè)輸出，但對(duì)程序語言的翻譯總是單值輸出（最多容許一個(gè)輸出）。例一：簡(jiǎn)單翻譯 （書P222）英文小寫字母 ASCII碼（一一對(duì)應(yīng)）例二：將中綴表達(dá)式翻譯為等價(jià)的前綴、后綴波蘭表達(dá)式中綴： a+b , (a+b)*(c+d)前綴： +ab ,*+ab+cd后綴： ab+ ,ab+cd+*二 句法制導(dǎo)（引導(dǎo)）的翻譯式思路：類似于用有限條文法規(guī)則導(dǎo)出語言的無限

3、條句子，也可運(yùn)用有限條文法規(guī)則定義由無限個(gè)成員組成的翻譯.句法制導(dǎo)（引導(dǎo)）的翻譯式：模仿語言的文法定義來定義一個(gè)對(duì)偶系統(tǒng), 使得這些對(duì)偶的集合符合給定的翻譯要求。直觀的說，“翻譯式”（翻譯格式）類似于在原文法的每條產(chǎn)生式上粘附著一個(gè)“翻譯元素”(Translation Element)的文法。產(chǎn)生式 用于推導(dǎo)輸出句型翻譯元 推算出相應(yīng)于輸入句型的輸出句型例：定義翻譯 （w，w ）| w (a, b) *(生成式, 翻譯元)1.(A -> aA, A = Aa )2.(A -> bA, A = Ab)3.(A -> a, A = a)4.(A -> b, A = b) 類

4、似于句子的推導(dǎo)過程（句型推導(dǎo)），將翻譯的推導(dǎo)過程稱“翻譯型”。初始翻譯型 （A，A）ð (aA , Aa )ð (abA , Aba )ð (abb, bba )例： 中綴算術(shù)表達(dá)式到前綴波蘭表達(dá)式的翻譯(生成式, 翻譯元)1.(S -> S+A, S = +SA) 2.(S -> A, S = A)3.(A -> A*B, A = *AB)4.(A -> B, A = B)5.( B -> (S), B = S)6.(B -> i, B = i )對(duì)于輸入串 （i+i）*i, 按最左推導(dǎo)有初始翻譯型 （S，S）ð (

5、A, A)ð (A*B , *AB )ð (B*B , *BB)ð ( (S)*B , *SB)ð ( (S+A)*B , *+SAB)ð ( (A+A)*B , *+AAB)ð ( (B+A)*B , *+BAB)ð ( ( i +A)*B , *+ i AB)ð ( ( i +B)*B , *+ i BB)ð ( ( i + i )*B , *+ i i B)ð ( ( i + i )*i , *+ i i i )定義：句法制導(dǎo)翻譯式為五元組H = (N,T, , R , S)其中：N 非終

6、結(jié)符T 輸入字符集合（終結(jié)符）， 輸出符號(hào)S 起始符R 規(guī)則的有限集合，形如Aà, (NÈT)*, (NÈ)*且中的非終結(jié)符是中非終結(jié)符的一個(gè)排列。如 A à B(1)aAB(2), B(2)AaB(1)翻譯式H產(chǎn)生的全部翻譯的集合為：t(H) = (x，y) | （S，S）=> * (x，y), xT*, y* 定義: 簡(jiǎn)單句法制導(dǎo)翻譯式設(shè)H = (N, T, , R , S)是句法制導(dǎo)翻譯式，若對(duì)于R中的每個(gè)規(guī)則Aà,都有,中所有非終結(jié)符的排列次序相同，則稱H為簡(jiǎn)單句法制導(dǎo)翻譯式。它定義的翻譯稱為簡(jiǎn)單句法制導(dǎo)翻譯。例： 規(guī)則R是簡(jiǎn)單句

7、法制導(dǎo)翻譯規(guī)則E -> E(1)*E(2), *E(1)E(2)E -> F, FF -> i, i $6.2 轉(zhuǎn)換器轉(zhuǎn)換器實(shí)質(zhì)是一種帶輸出的自動(dòng)機(jī)。該自動(dòng)機(jī)的輸入端在接收到字符串的同時(shí)，在它的輸出端能夠輸出的翻譯。一 有限轉(zhuǎn)換器定義：有限轉(zhuǎn)換器為六元組， M=(Q, T, , q0, F)其中：Q 有限狀態(tài)集合 T 輸入字母表， 輸出字母表q0 初始狀態(tài)，q0QF: 終止?fàn)顟B(tài)集 FÍQ 從 Q×（T）到Q×* 的子集的映射(非確定的自動(dòng)機(jī))定義：當(dāng)上面定義中的滿足下述條件時(shí)， M便是一個(gè)確定的轉(zhuǎn)換器。對(duì) "qQ， "aT,

8、有 (q，a ) 只有一個(gè)選擇，且（q，）或者(q， ) 只有一個(gè)選擇，且（q，a）有限轉(zhuǎn)換器的格局： q 當(dāng)前狀態(tài)格局(q, ,) 當(dāng)前待輸入的字符串 當(dāng)前已輸出的字符串其中qQ , T*，*例： 若有 (p，x) （q，a）則有 (q, a, ) (p, , x)。若有 (q0, , ) * (q, , ), qF，則稱是的輸出。有限轉(zhuǎn)換器M的所有輸出字符串的集合稱為M的翻譯。t(M) = (,) | (q0, , ) * (q, , )且 qF，例：設(shè)計(jì)一個(gè)有限轉(zhuǎn)換器M, 可以識(shí)別算術(shù)表達(dá)式，并能從表達(dá)式中刪除多余運(yùn)算符。E à a+E | a-E | +E | -E |a例如

9、: -a+-a a+a二 下推轉(zhuǎn)換器下推轉(zhuǎn)換器是有輸出的下推自動(dòng)機(jī)。定義：下推轉(zhuǎn)換器M是八元組，M（Q，T，q0，z0，F(xiàn)）其中： Q：有限控制器的狀態(tài)集合 T：有限輸入字母表 ：有限下推棧字母表 輸出字母表 ：轉(zhuǎn)換函數(shù) q0：初始狀態(tài)，q0Q z0：下推棧的起始符號(hào)，z0 F：終態(tài)集合，F(xiàn) Í Q：Q ×（T）× Q×*×*的子集的映射。 下推轉(zhuǎn)換器的格局： (q, ,) q 當(dāng)前狀態(tài)格局(q, ,) -當(dāng)前待輸入的字符串當(dāng)前棧中的內(nèi)容 已輸出的字符串例： 若有 (p，,x) （q，a,Z）則有 (q, a,Z, ) (p, , , x)。終

10、態(tài)接受：t(M) = (,) | (q0, ,Z0,) * (q, , , )且 qF，*空棧接受：t(M) = (,) | (q0, ,Z0,) * (q, , , ) 例：設(shè)計(jì)下推轉(zhuǎn)換器M, 將翻譯為它的逆t(M) = (, ) | (q0, ,Z0,) * (q, , , )， a,b*思路：(1). 將輸入字符不斷進(jìn)棧，直至輸入為空，其間不輸出。(2). 當(dāng)輸入為空時(shí)，開始退棧并輸出之，直至棧空。例：將前綴表達(dá)式變后綴表達(dá)式。M=( q, +,*,a, +,*,a, +,*,a, q, E, q )（q，,E）= （q，, a）（q，+,E）= （q，EE+, ）（q，*,E）= （q

11、，EE*, ）（q，,+）= （q，, +）（q，,*）= （q，, *）例如：(q, +*aaa,E,) * (q, , , aa*a+)(q, +*aaa,E,) (q, *aaa,EE+,) (q, aaa,EE*E+,) (q, aa,E*E+,a) (q, a,*E+,aa) (q, a,E+,aa*) (q, ,+,aa*a) (q, , ,aa*a+)定理：簡(jiǎn)單句法制導(dǎo)翻譯式與下推轉(zhuǎn)換器之間是等價(jià)的。證明略。6.3 詞法分析編譯器的掃描或詞法分析階段可將源程序讀作字符文件并將其分為若干個(gè)記號(hào)（token ）,即單詞。典型的Token：關(guān)鍵字: 如if 和while ，它們是字母的

12、固定串；標(biāo)識(shí)符: 通常由字母和數(shù)字組成并由一個(gè)字母開頭；特殊符號(hào): 如算術(shù)符號(hào)+和*、一些多字符符號(hào)，如> = 和< >。在掃描過程中, 最主要的格式說明和識(shí)別方法是正則表達(dá)式和有窮自動(dòng)機(jī)。有窮自動(dòng)機(jī)是對(duì)由正則表達(dá)式給出的串格式的識(shí)別算法。例: 帶有出錯(cuò)轉(zhuǎn)換的標(biāo)識(shí)符的有窮自動(dòng)機(jī)例: 浮點(diǎn)數(shù)的有窮自動(dòng)機(jī) 用代碼實(shí)現(xiàn)有窮自動(dòng)機(jī)例： 模擬接受標(biāo)識(shí)符的D FA 。模擬這個(gè)D FA, 最簡(jiǎn)單的方法是下面的偽代碼： starting in state 1 if the next character is a letter t h e nadvance the input; now in

13、state 2 while the next character is a letter or a digit doadvance the input; stay in state 2 end while; go to state 3 without advancing the input accept ;else error or other cases end if;這段代碼使用代碼中的位置來隱含狀態(tài)。適用于沒有太多的狀態(tài)（要求有許多嵌套層）且D FA 中的循環(huán)較小的情況。類似的代碼可用來編寫小型的掃描程序。該方法有兩個(gè)缺點(diǎn)：它是特殊的，即必須用不同的方法處理各個(gè)DFA ，而且將每個(gè)DFA

14、 翻譯為代碼的算法也較難。其次：當(dāng)狀態(tài)增多時(shí)，以及當(dāng)任意路徑增多時(shí)，代碼會(huì)變得非常復(fù)雜。例：接受注釋（C 風(fēng)格的注釋）的D FA可用以下的編碼來實(shí)現(xiàn). state 1 if the next character is “ / ” t h e nadvance the input: state 2 if the next character is “*” thenadvance the input ； state 3 done := false;while not done d owhile the next input character is not “*” d oadvance the i

15、nput ；end while;advance the input ； state 4 while the next input character is “*” d oadvance the input;end while;if the next input character is “ / ” thendone : = true ;end if;advance the input;end while;accept; state 5 else other processing end if;else other processing end if;這樣做的復(fù)雜性已大大增加了，且還需要利用布爾

16、變量done 來處理涉及到狀態(tài)3和狀態(tài)4 的循環(huán)。一種更好的實(shí)現(xiàn)方法是：利用一個(gè)變量保持當(dāng)前的狀態(tài)，并將轉(zhuǎn)換寫成一個(gè)雙層嵌套的case 語句而不是一個(gè)循環(huán)。其中第1 個(gè)case 語句測(cè)試當(dāng)前的狀態(tài)，嵌套著的第2 層測(cè)試輸入字符及所給狀態(tài)。例如，標(biāo)識(shí)符的D FA 可翻譯為下面的的代碼模式：state := 1; start while state = 1 or 2 d ocase state of1: case input character ofletter: advance the input ；state := 2;else state := error or other;end case

17、;2: case input character ofletter,digit: advance the input ； state := 2; actually unnecessary else state := 3;end case;end case;end while;if state = 3 then accept else error ；接受C 風(fēng)格注釋的DFA可由以下的編碼實(shí)現(xiàn)：state := 1; start while state = 1 to 4 d ocase state of1: case input character of“/”: advance the input

18、 ；state := 2;else state := error or other;end case;2: case input character of“*”: advance the input ；state := 3; else state := error or other;end case;3: case input character of“*”: advance the input ；state := 4; else advance the input and stay in state 3;end case;4: case input character of“/”: adva

19、nce the input ；state := 5;“*”: advance the input and stay in state 4; else advance the input;state := 3; end case;end case;end while;if state = 5 then accept else error ；此外,還可將DFA 表示為二維轉(zhuǎn)換表（transition table ），由表示轉(zhuǎn)換函數(shù)T 值的狀態(tài)和輸入字符來索引：例如：標(biāo)識(shí)符的DFA 可表示為如下的轉(zhuǎn)換表：在表格中，假設(shè)列中的第1 個(gè)狀態(tài)是初始狀態(tài)。空表項(xiàng)表示未在DFA 圖中顯示的轉(zhuǎn)換（即：它們表示到

20、錯(cuò)誤狀態(tài)或其他過程的轉(zhuǎn)換）。但是，這個(gè)表格尚未指出哪些狀態(tài)正在接受以及哪些轉(zhuǎn)換不消耗它們的輸入?？闪韺⒁恍┬畔⑻砑拥缴厦娴霓D(zhuǎn)換表中（指出接受狀態(tài)并指出“未消耗輸入”的轉(zhuǎn)換）。例： C 注釋的DFA 表格:相應(yīng)代碼:state := 1;ch : = next input character;while not Acceptstate and not errorstate donewstate := T state, ch;if Advance state, ch then ch := next input char;state := newstate;end while;if Accept s

21、tate then accept;類似的算法被稱作表驅(qū)動(dòng)（table driven ），因?yàn)樗鼈兝帽砀駚硪龑?dǎo)算法的過程。表驅(qū)動(dòng)的優(yōu)點(diǎn)：代碼的長(zhǎng)度縮短了，相同的代碼可以解決許多不同的問題，代碼較易維護(hù)。表驅(qū)動(dòng)的缺點(diǎn)：表格會(huì)變得非常大，從而使程序要求使用的空間也變得非常大。(實(shí)際上，數(shù)組中的許多空間都是浪費(fèi)的)。$ 6.4 句法分析分析句子的結(jié)構(gòu)： 自上而下的分析 à 左解析自下而上的分析 à 右解析例： 文法 G = (S, B , a, b , P, S )產(chǎn)生式按序號(hào)分別為：1. Sà bBS2. Sà b3. Bà SaB4. B

22、4; ab最左推導(dǎo)： S Þ1 b B S Þ3 b SaB SÞ2 b baB S Þ4 b ba ab SÞ2 b ba ab b最左推導(dǎo)所用的產(chǎn)生式序號(hào) 13242 稱為 bbaabb 的左解析。最右推導(dǎo)：S Þ1 b B S Þ2 b B bÞ3 b SaB b Þ4 b Sa ab bÞ2 b b a ab b序號(hào)序列之逆 24321 稱為 bbaabb 的右解析(自下而上的歸約)?？赏ㄟ^翻譯式找左解析、右解析。定義. 設(shè)2型文法G=(N, T, P, S), 生成式序號(hào)為1, 2,

23、, nH=(N, T, 1, 2, , n , R, S)其中R為Aàa, b 若Aàa是P中序號(hào)為k的生成式, 則b是ka且a是刪去終結(jié)符的a.例: G的生成式為1. S àbBS2. S àb3. B àSaB4. B àab則H=(S, B, a, b, 1, 2, 3, 4, R, S )其中R為1) S àbBS, 1BS2) S àb, 23) B àSaB, 3SB4) B àab, 4用最左推導(dǎo), 有bbaabb的左解析為(S, S) Þ ( b B S, 1BS)Þ ( b Sa B S, 1 3S BS)Þ ( b b a B S, 1 3 2 BS)Þ ( b b a