第二章高級(jí)語言及其語法描述-wenkub.com
2025-07-17 05:23 本頁面
【正文】 上下文無關(guān)文法的語法樹 ? 給定文法 G， 對(duì)于 G的任何句型都能構(gòu)造與之關(guān)聯(lián)的語法樹（推導(dǎo)樹）。其識(shí)別系統(tǒng)是不確定的下推自動(dòng)機(jī)。 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à)的。 例： 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)造其文法?；蛘叽髮懽帜副硎痉墙K結(jié)符，小寫字母表示終結(jié)符 – G可寫成 G[S]， S是開始符號(hào) 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 ={標(biāo)識(shí)符，字母，數(shù)字 } VT ={a,b,c,…x,y,z,0,1,…,9} P={標(biāo)識(shí)符 → 字母 標(biāo)識(shí)符 → 標(biāo)識(shí)符 字母 標(biāo)識(shí)符 → 標(biāo)識(shí)符 數(shù)字 字母 → a,…, 字母 → z 數(shù)字 →0, … , 數(shù)字 →9 } S=標(biāo)識(shí)符 推導(dǎo)的定義 ? 直接推導(dǎo) “ ?” α → β 是文法 G的產(chǎn)生式，若有 v,w滿足： v=γ α δ ,w= γ β δ , 其中 γ ∈V *,δ ∈V * 則稱 v直接推導(dǎo)到 w,記作 v ? w 或 w直接歸約到 v 例： G： S→ 0S1， S→ 01 S ?0S1 ?00S11 ?000S111 ?00001111 程序 ?分程序 . ? 變量說明部分 語句 . ?... ?VAR標(biāo)識(shí)符 。 ? α 稱為規(guī)則的左部 (或生成式 的左部 )。兩個(gè)途經(jīng)： 生成方式 （文法）：語言中的每個(gè)句子可以用嚴(yán)格定義的規(guī)則來構(gòu)造。 ?即 ? ?是一個(gè)語言。 ? 例： Σ ={a,b} Σ *={ε ,a,b,aa,ab,ba,bb,aaa,aab,… } Σ +={a,b,aa,ab,ba,bb,aaa,aab,… } ? . . . . . .}{ 2* ??????? ?. . . . . .}{ 32** ?????????????? ? ?? 語言：字母表 ?上 的一個(gè)語言是 ?上的一些符號(hào)串的集合 (?上 的每個(gè)語言是 ?*的一個(gè)子集 )。 ? 兩個(gè)符號(hào)串集合 A和 B的乘積定義為 AB =?xy|x?A且 y?B? 若 集合 A=?ab,cde? B = ?0,1? 則 AB =?ab1,ab0,cde0,cde1? ? 使用 ?* 表示 ?上的一切符號(hào)串（包括 ε ）組成
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1