第二章高級(jí)語言及其語法描述(已改無錯(cuò)字)
2022-08-17 05:23:33 本頁面
【正文】 (S→ aSBE) ?a aBEBE (S→ aBE) ?aabEBE ( aB→ ab ) ?aabBEE ( EB→ BE ) ?aabbEE （ bB→ bb) ?aabbeE （ bE→ be) ?aabbee （ eE→ ee) ? G生成的每個(gè)串都在 L(G)中 L(G)中的每個(gè)串確實(shí)能被 G生成 ? 已知語言描述，寫出文法 – 例：若語言由 0、 1符號(hào)串組成，串中 0和 1的個(gè)數(shù)相同，構(gòu)造其文法。 A → 0B|1C B → 1|1A|0BB C → 0|0A|1CC ? 已知文法，寫出語言描述 – 例： G[E]： E→E+T|T T→T*F|F F→(E)|a 推導(dǎo)的定義 ? 若存在 v ?w0 ?w1 ?... ?wn=w,(n0) ? 則稱 v w， v推導(dǎo)出 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 表示一切能用符號(hào) a， +， *， (和 )構(gòu)成的算術(shù)表達(dá)式 文法，語言的定義 ? 由文法 G生成的語言記為 L(G),它是文法G的一切句子的集合 : L(G)={x|S x， 其中 S為文法的開始符號(hào)，且 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 (S→ aSBE) ?a aBEBE (S→ aBE) ?aabEBE ( aB→ ab ) ?aabBEE ( EB→ BE ) ?aabbEE （ bB→ bb) ?aabbeE （ bE→ be) ?aabbee （ eE→ ee) ? G生成的每個(gè)串都在 L(G)中 L(G)中的每個(gè)串確實(shí)能被 G生成 ? 已知語言描述，寫出文法 – 例：若語言由 0、 1符號(hào)串組成，串中 0和 1的個(gè)數(shù)相同，構(gòu)造其文法。 A → 0B|1C B → 1|1A|0BB C → 0|0A|1CC ? 已知文法，寫出語言描述 – 例： G[E]： E→E+T|T T→T*F|F F→(E)|a 文法的等價(jià) ? 若 L（ G1） =L（ G2）， 則稱文法 G1和 G2是等價(jià)的。 如文法 G1[A]： A→0R 與 G2[S]： S→0S1 等價(jià) A→01 S→01 R→A1 文法的類型 ? 通過對(duì)產(chǎn)生式施加不同的限制， Chomsky將文法分為四種類型： – 0型文法：對(duì)任一產(chǎn)生式 α → β ， 都有α ∈(V N∪V T)+， β ∈(V N∪V T)* – 1型文法： 對(duì)任一產(chǎn)生式 α → β ， 都有|β |≥| α |， 僅僅 S→ ε 除外 – 2型文法： 對(duì)任一產(chǎn)生式 α → β ， 都有 α ∈V N ， β ∈(V N∪V T)* – 3型文法： 任一產(chǎn)生式 α → β 的形式都為 A→aB或 A→a ， 其中 A∈V N ， B∈V N ， a∈V T 文法的類型 ? 例： 1型（上下文有關(guān)）文法 文法 G[S]： S→ aSBE S→ aBE EB→ BE aB→ ab bB→ bb bE→ be eE→ ee 文法的類型 ? 例： 1型（上下文有關(guān)）文法 文法 G[S]： S→CD Ab→bA C→aCA Ba→aB C→bCB Bb→bB AD→aD C→ ε BD→bD D→ ε Aa→bD L(G)={ww|w∈{a,b} *} 文法的類型 ? 例： 2型（上下文無關(guān)）文法 文法 G[
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1