正文內容

第二章語言的基本知識(編輯修改稿)

2025-11-03 14:03 本頁面

　

【文章內容簡介】 α n或者 α 0 α n + ? + ? * ? 二 . 定義直接推導和推導的定義 22 例： E ? E+T ?T+T ?F+T ?a+T? a+F ?a+a ? A ? ? ? ? 產生式 ? ?E ? E+ T E ? E+ T ? ?E+ T ? T+ T E ? T ? +TT+ T ? F +T T ? F ? +TF +T ? a +T F ? a ? +Ta +T ? a +F T ? F a+ ?a +F ? a +a F ? a a+ ?23 設文法 G＝（ VT， VN， S,P）。如果 S α ,則稱 α 是一個句型。僅含終結符號的句型是一個句子。語言 L(G）是由文法 G產生的所有句子所組成的集合： L(G)＝ {α |S α 且 α ∈V T*} 例考慮一個文法 G＝ ({a,b},{S},S， P）其中 P： S?aSb? ab S?aSb ? aaSbb ? a3Sb3 ? …… ? an1Sbn1 ? anbn * ? + ? 三 . 定義：語言的定義 24 設 G=(VT={a,b},VN={S,A,B},S,P} P由下列產生式組成 :S→aB|bA A→a|aS|bAA B→b|bS|aBB L(G)={w|w∈{a,b} +,且 w中有相同個數的 a和 b}。用歸納法證明下面結論（對 w的長度）： (1)S w,當且僅當 w中含有相同個數的 a和 b。 (2)A w,當且僅當 w中 a的個數比 b的個數多一個。 (3)B w,當且僅當 w中 b的個數比 a的個數多一個。歸納基礎當 |w|=1， A?a, B ? b, 不能從 S導出長度為 1的終極行 ,則上述結論顯然成立。 *? *? *? 例 25 設 (1),(2)和 (3)對于長度不超過 k1的所有 w都成立。那么，證明對 |w|=k也成立。對于（ 1），推導的第一步必是 S?aB或 S?bA, 對于第一種情形，必有 w=aw1且 B w1， |w1|=k1，它含的 b個數比 a多一個，因此， w中 a,b的個數相等。推導的第一步是 S?bA,證明完全類似。反之， |w|=k, w中 a,b的個數相等 ,要證 S w。考慮的 S推導，推導出的開始符號，或為 a或為 b。若 S?aB,B w1, |w1|=k1, w1中 b的個數比 a多一個 ,w= aw1。若 S ?bA，證明和類 S?aB類似。（ 2）和（ 3）的證明留給同學們。 *? *? *? 歸納步驟26 : 對于 w和 G, w?L(G)? 是否存在 S w，如何構造 ? 例如， G[E]（例）和 w=a+a ? a E?E+T ?T+T ?F+T ?a+T ?a+T?F ?a+F ?F ?a+a ?F ?a+a?a（最左）特點： ?A? ? ??? (A??) ， ??VT* E?E+T ?E+T ?F ?E+ T ?a ?E+F?a ?E+a?a ?T+a?a ?F+a?a ?a+a?a 特點： ?A? ? ??? (A??)， ? ?VT*（最右） + ? 四 . 最左推導和最右推導 27 令 G[S]是一個文法，如果有 S α Aδ 且 A β 則稱 β 是一個關于非終結符號 A的，句型αβδ 的短語。其次如果有 S α Aδ 且 A?β 則稱 β 是直接短語。一個句型的最左直接短語稱為該句型的句柄。文法（ 2． 1）的一個句型 a1*a2+a3 ，盡管有 E a2＋ a3 ，但是 a2＋ a3 并不是該句型的一個短語 ,因為不存在 E a1*E。短語： a1,a2,a3， a1 *a2,a1*a2+a3 直接短語 :a1， a2 ,a3 句柄 :a1 + ? * ? * ? + ? + ? 定義 28 分析樹和二義性 ?一 . 分析樹的定義 ?二 . 如何畫出分析樹 ?三 . 子樹 ?四 . 二義性文法的定義 ?五 . 在構造編譯程序中如何處理二義性文法 29 設 G=（ VT， VN， S， P） ,G的一棵分析樹滿足如下條件： 1. 每一個結點有一個標記，此標記是 VT∪V N∪{ ε }中的符號。2．根的標記是 S。 3．如果一個結點是內部結點，且有標記 A,那么 A必在 VN中。 4．如果編號為 n的結點有標記 A,結點n1,n2,…,n k是點 n的從左到右的兒子，并分別有標記 X1,X2,… ,Xk，則 A?X1X2… Xk必須是 P中的產生式。 5. 如果結點 n有標記 ε ，那么結點 n是葉子，且是它父親唯一的兒子。一 .分析樹的定義 30

點擊復制文檔內容

教學課件相關推薦

第二章語言的基本知識(編輯修改稿)

[it認證]c語言第二章-資料下載頁

[工學]第二章_c語言-資料下載頁

第二章visualbasic語言基礎-資料下載頁

房地產金融第二章房地產金融基本知識(ppt64)-資料下載頁

第二章知識表示-資料下載頁

第二章基本理論-資料下載頁

第二章知識與知識表示-資料下載頁

無機及分析化學習題第二章-分析化學基本知識-資料下載頁

第二章-金屬材料力學性能基本知識及鋼材的脆化-資料下載頁

知識管理概述(第二章-資料下載頁

第二章基礎知識-資料下載頁

c語言程序設計第二章基本數據類型-資料下載頁

第二章文獻的基礎知識-資料下載頁

第二章平面問題的基本理論-資料下載頁

第二章民法的基本原則-資料下載頁

第二章語言的基本知識-在線瀏覽

第二章語言的基本知識-閱讀頁

第二章語言的基本知識(文件)

第二章語言的基本知識-全文預覽

第二章語言的基本知識-預覽頁