【正文】 導致失敗的原因是在分析中對A的選擇不是正確的。 VN= K ?句子 有文法 G，若 S =* x，且 x∈V T*，則稱 x是文法 G的句子。語言的有窮表示有兩個途經： 生成方式 （文法）：語言中的每個句子可以用嚴格 定義的規(guī)則來構造。其識別系統(tǒng)是線性界限自動機。因為可能有兩個不同的文法 G和 G′ ，其中 G是二義的，但是卻有 L(G)=L(G′) ，也就是說，這兩個文法所產生的語言是相同的。 57 上下文無關文法中的 ε規(guī)則 上下文無關文法中某些規(guī)則可具有形式 A→ ε，稱這種規(guī)則為 ε規(guī)則 因為 ε規(guī)則會使得有關文法的一些討論和證明變得復雜 ,有時會限制這種規(guī)則的出現 兩種定義的唯一差別是 ε句子在不在語言中 文法構思的啟示是要找出語言的有窮描述，而如果語言 L有一個有窮的描述，則 L1=L∪ ｛ ε｝也同樣有一個有窮的描述，并且可以證明，若 L是上下文有關語言、上下文無關語言或正規(guī)語言，則L∪ ｛ ε｝和 L｛ ε｝分別是上下文有關語言、上下文無關語言和正規(guī)語言。 從左到右的分析算法 ，即 總是從 左 到 右 地 識別輸入符號串 ，首先識別符號串中的 最左符號，進而 依次識別右邊 的一個符號， 直到分析結束 。 A=S 6 文法的定義 例 文法 G=（ VN， VT， P， S） VN = { S }, VT ={ 0, 1 } P={ S→ 0S1, S→ 01 } S為開始符號 例 文法 G=（ VN， VT， P， S） VN ={標識符，字母，數字 } VT ={a,b,c,…x,y,z,0,1,…,9} P={標識符 → 字母 標識符 → 標識符 字母 標識符 → 標識符 數字 字母 → a … 字母 →z 數字 →0 … 數字 →9 } S=標識符 8 文法的寫法 元 符號 : → ∷= | 習慣 大寫字母表示非終結符 小寫字母表示終結符 (1) G： S→aA b A→ab A→aA b A→ ε (2) G[S]： A→ab A→aA b A→ ε S→aS b (3) G[S]:A→ab |aA b |ε S→aS b 9 推導的定義 直接推導 “ ?” α → β 是文法 G的產生式，若有 v,w滿足：v=γ α δ ,w= γ β δ , 其中 γ ∈V *,δ ∈V * 則稱 v直接 推導 到 w,記作 v ? w 也稱 w直接 歸約 到 v 例： G： S→ 0S1， S→ 01 0S1 ?00S11 00S11 ?000S111 000S111 ?00001111 S ?0S1 10 推導 程序 ?分程序 . (程序 ? 分程序 . ) 分程序 . ? 變量說明部分 語句 . (分程序 ? 變量說明部分 語句 ) VAR標識符 。 ? 稱為規(guī)則的左部， ? 稱作規(guī)則的右部。 K= VN ∪{ N}, N為一個新狀態(tài) ,它不在 VN中 分析算法又稱 識別算法 。 58 練習 1. 寫一文法，使其語言是偶正整數的集合。 二義文法改造為無二義文法 G‘[E]:E → i G[E] ： E → T|E+T E → E+E T → F|T*F E → E*E F → （ E） |i E → (E) 規(guī)定算符優(yōu)先性和結合性 如果產生上下文無關語言的每一個文法都是二義的，則說此語言是先天二義的。 26 帶 a0 a1 a2 a3 a4 a5 a6 a7 a8 … an1 an 有限控制器 磁頭 任何能用圖靈機描述的計算都能機械實現，任何能在現代計算機上實現的計算都能用圖靈機描述 27 2型文法（上下文無關文法 CFG）：產生式的形式為 A→ β ， β 取代 A時與 A的上下文無關。 識別方式 （自動機）：用一個過程，當輸入的一任意串屬于語言時，該過程經有限次計算后就會停止并回答“是”，若不屬于，要么能停止并回答“不是”，要么永遠繼續(xù)下去。BEGIN READ( A) END. (標識符 ?A) 11 推導的定義 若存在 v =w0 ?w1 ?... ?wn=w,(n0) 則記為 v =+ w，稱作 v推導出 w，或 w歸約到 v 若有 v =+ w 或 v=w， 則記為 v =* w 12 例： G： S→ 0S1， S→ 01 0S1 ?00S11