[理學]編譯原理第三章-在線瀏覽
2024-12-03 21:34本頁面
【正文】 錯誤的行號，因此詞法分析時不能刪除。 六、向前看多個字符的處理 例如： x:10..100。 修正的方法 ? 從剩余的輸入中刪除一個字符； ? 向剩余的輸入中插入一個遺漏的字符； ? 用一個字符替換另一個字符； ? 交換兩個相鄰字符； ? 將出錯部分作為一個特殊的 token保留，以便進行后期的語法矯正 一、基本概念 ? 字母表 :任何語言均有固定的字母表。 ? 符號串長度： | ? |=0 ? 語言：給定字母表上一個任意的可數(shù)的串的集合。 ? 是正則表達式 , L( ? )={ } ? 是正則表達式 , L(? ) = {? } a ? ? 是正則表達式 , L( a )= { a } 例、以 00結尾的二進制數(shù)字串對應的正則表達式為： 設 A,B? , 則 : R ? (A) ? R? , L((A) )=L(A)。 AB ? R? , L(AB)= L(A) L(B)。 由于正則定義可以引入變量，因此正則定義比正則表達式的表達能力強。 二、有窮自動機分為： 不確定自動機 NFA 確定自動機 DFA 三、不確定有窮自動機 NFA 不確定有窮自動機的組成 ? 符號集 ?； ? 狀態(tài)集合 S={S0,S1,… .Sn}。 稱字符串 a1,a2,…an 被有窮自動機所接受，如果存在 狀態(tài)序列 S0， S1， …Sn, 使得 S0 S1, S1 S2, …, Sn 1 Sn 其中 S0為初始狀態(tài)， Sn為一個終止狀態(tài)，中間狀態(tài)可以為初始狀態(tài)，也可為一個終止狀態(tài)。 例： P92 a1 a2 an 確定有窮自動機 確定有窮自動機是不確定有窮自動機的一個特例，它要求滿足： 1）沒有 ?邊； 2）對于每個狀態(tài) s和每個輸入符號 a，有且僅有一條標有 a的邊 離開，即從一個狀態(tài)出發(fā)的邊上不允許標有相同的字符 例如：接受整數(shù)、實數(shù)和標識符的自動機 確定有窮自動機的實現(xiàn) (1)采用狀態(tài)轉換表的實現(xiàn)方式 int scanner(char input[]){ in=0。 ch=input[in++]。amp。 ch=input[in++]。amp。 else return(0)。 getch(ch)。amp。break。break。break。 case 2: switch(ch) { case a: state=3。 case b: state=2。 default: state=0。} break。break。break。break。 getch( )。amp。 return(
教學課件相關推薦
鄂ICP備17016276號-1