第二章高級語言及其語法描述(編輯修改稿)
2024-08-16 05:23 本頁面
【文章內容簡介】 生成方式 （文法）：語言中的每個句子可以用嚴格定義的規(guī)則來構造。 識別方式（自動機）：用一個過程，當輸入的一任意串屬于語言時，該過程經有限次計算后就會停止并回答“是”，若不屬于，要麼能停止并回答“不是”，（要麼永遠繼續(xù)下去。） 文法 數學系統(tǒng) ? 一個形式數學系統(tǒng)可由下列基本成分來刻畫：一組基本符號，一組形成規(guī)則，一組公理，一組推理規(guī)則。 文法和語言的形式定義 ? 文法的定義 ? 推導的定義 ? 句型、句子、語言的定義 文法的定義 ? 文法 G定義為四元組（ VN， VT， P， S） – VN ： 非終結符集 – VT ： 終結符集 – P： 產生式（規(guī)則）集合 – S： 開始符號 VN∩ VT= φ ， S∈ VN V=VN∪ VT， 稱為文法 G的文法 符號集合 規(guī)則的定義 ? 規(guī)則（重寫規(guī)則、產生式或生成式），是形如 α → β 或 α ∷= β 的（ α ， β ） 有序對，且 α ∈V +， β ∈V *。 ? α 稱為規(guī)則的左部 (或生成式 的左部 )。 ? β 稱為規(guī)則的右部 (或生成式 的右部 )。 文法的定義 ? 例 文法 G=（ VN， VT， P， S） VN = { S }, VT ={ 0, 1 } P={ S→ 0S1, S→ 01 } S為開始符號 文法的定義 ? 習慣上只將產生式寫出。并有如下約定： – 第一條產生式的左部是開始符號 – 用尖括號括起的是非終結符，否則為終結符?；蛘叽髮懽帜副硎痉墙K結符，小寫字母表示終結符 – G可寫成 G[S]， S是開始符號 G： S→a Ab A→ab A→a Ab A→ ε G[S]： A→ab A→a Ab A→ ε S→a Sb 縮寫形式 G[S]： A→ab |aAb |ε S→a Sb 例 文法 G=（ VN， VT， P， S） VN ={標識符，字母，數字 } VT ={a,b,c,…x,y,z,0,1,…,9} P={標識符 → 字母 標識符 → 標識符 字母 標識符 → 標識符 數字 字母 → a,…, 字母 → z 數字 →0, … , 數字 →9 } S=標識符 推導的定義 ? 直接推導 “ ?” α → β 是文法 G的產生式，若有 v,w滿足： v=γ α δ ,w= γ β δ , 其中 γ ∈V *,δ ∈V * 則稱 v直接推導到 w,記作 v ? w 或 w直接歸約到 v 例： G： S→ 0S1， S→ 01 S ?0S1 ?00S11 ?000S111 ?00001111 程序 ?分程序 . ? 變量說明部分 語句 . ?... ?VAR標識符 。BEGIN READ(標識符 )END. ? VAR A。BEGIN READ(A) END. 推導的定義 ? 若存在 v ?w0 ?w1 ?... ?wn=w,(n0) ? 則稱 v w， v推導出 w， 或 w歸約到 v ? 若有 v w， 或 v=w， ? 則記為 v w *???????*???????*?文法的句型、句子的定義 ? 句型 – 有文法 G， 若 S x， 則稱 x是文法 G的句型。 ? 句子 – 有文法 G， 若 S x， 且 x∈V T*， 則稱 x是文法 G的句子。 例： G： S→ 0S1， S→ 01 S ?0S1 ?00S11 ?000S111 ?00001111 *?*?– 例： G[E]： E→E+T|T T→T*F|F F→(E)|a E?E+T ?T+T ?F+T ?a+T ?a+T*F ?a+F*F ?a+a*F ?a+a*a 表示一切能用符號 a， +， *， (和 )構成的算術表達式 文法，語言的定義 ? 由文法 G生成的語言記為 L(G),它是文法G的一切句子的集合 : L(G)={x|S x， 其中 S為文法的開始符號，且 x ∈V T*} 例： G： S→ 0S1， S→ 01 L(G)={0n1n|n≥ 1} *?? 例 文法 G[S]： （ 1） S→ aSBE （ 2） S→ aBE （ 3） EB→ BE （ 4） aB→ ab （ 5） bB→ bb （ 6） bE→ be （ 7） eE→ ee L（ G） ={ anbnen | n≥ 1 } S ?a S BE
環(huán)評公示相關推薦
鄂ICP備17016276號-1