編譯原理習題(1-4)(編輯修改稿)
2025-08-28 15:29 本頁面
【文章內(nèi)容簡介】 L)|a, L?L,S|S b)試建立下列句子的分析樹 iii)(a,((a,a),(a,a))) ： S ? (L)|a, L?L,S|S c)構造最左推導 iii)(a,((a,a),(a,a))) ： S ? (L)|a, L?L,S|S d)構造最右推導 ： S ? (L)|a, L?L,S|S e)該文法產(chǎn)生的是什么語言 ? 答：包含元素 a的二元廣義表 考慮文法 S ? aSbS | bSaS |? a)為句子 abab構造兩個不同的最左推導，以證明該文法是二義的 字串 abab的兩種最左推導 S?lm aSbS ?lm abS ?lmabaSbS ?lm ababS ?lm abab S?lm aSbS ?lm abSaSbS ?lm abaSbS ?lm ababS ?lm abab 考慮文法 S ? aSbS | bSaS |? b)為 abab構造相應的最右推導 考慮文法 S ? aSbS | bSaS |? c)為 abab構造相應的分析樹 考慮文法 S ? aSbS | bSaS |? d)該文法產(chǎn)生的語言是什么？ 答： ?或 包含相同個數(shù)的 a和 b組成的串 注意 ：該文法不是正則語言，不能用 RG描述 考慮文法 bexpr ? bexpr or bterm | bterm bterm ?bterm and bfactor | bfactor bfactor ? not bfactor | (bexpr) | true | false a) 為句子 not(true or false) 構造分析樹 b e x p rb t e r mb f a c t o rn o t b f a c t o r( )b e x p rb e x p r o r b t e r mb t e r mb f a c t o rb f a c t o rt r u ef a l s e 考慮文法 bexpr ? bexpr or bterm | bterm bterm ?bterm and bfactor | bfactor bfactor ? not bfactor | (bexpr) | true | false b) 試證明該文法產(chǎn)生所有的布爾表達式 證明：采用數(shù)學歸納法 當布爾表達式包含有 n=1個布爾值 (true或 false)時，顯然可以由 bexpr?bterm?bfactor?true|false，產(chǎn)生。 假設該文法能夠所有由 n≤k個布爾值組成的表達式。 當布爾表達式 B由 n=k+1個布爾值組成時，布爾表達式在去除最外層括號后得 B’，可以拆分成 B1 and B2 或 B1 or B2兩中，其中 B1,B2的布爾值個數(shù)均 ≤k。故 B1,B2可以由該文法產(chǎn)生。所以 B’可以由該文法產(chǎn)生，進而 B可以由該文法產(chǎn)生。 考慮文法 bexpr ? bexpr or bterm | bterm bterm ?bterm and bfactor | bfactor bfactor ? not bfactor | (bexpr) | true | false c)該文法是二義的嗎？為什么？ 答：該文法不是二義的，由于該文法將布爾運算的各個操作符劃分了不同的優(yōu)先級，使得對任意一個字串都只有一個對應的分析樹（或最左推導），故該文法不是二義的。 )消除 答：消除左遞歸得如下文法 ? S ? (L) | a ? L ?SL39。 ? L39。 ? ,SL39。 | ? )為 (a)的文法構造預測語法分析器。給出該語法分析器在分析練習 (b)中的句子時的行為 ? S ? (L) | a ? L ?SL39。 ? L39。 ? ,SL39。 | ? First(S)={a (}, First(L)={a (}, First(L’)={? ,} Follow(S)={$ ? , ( )}, Follow(L) = {)}, Follow(L’)={)} 非終結(jié)符 號 輸入符號 ( ) , a $ S S ?( L ) S ? a L L ? SL39。 L ? SL39。 L39。 L’ ? ? L39。 ? ,SL39。 )為 (a)的文法構造預測語法分析器。給出該語法分析器在分析練習 (b)中的句子時的行為 L39。 非終結(jié)符號 輸入符號 ( ) , a $ S S ?( L ) S ? a L L ? SL39。 L ? SL39。 L39。 L’ ? ? L39。 ? ,SL39。 L39。 棧 輸入 輸出 $S (a, (a, a)) $ $)L( (a, (a, a))$ S (L) $)L a, (a, a))$ $)L39。S a, (a, a))$ L SL39。 $)L39。a a, (a, a))$ S a $)L39。 , (a, a))$ $)L39。S, , (a, a))$ L39。 , SL39。 $)L39。S (a, a))$ $)L39。)L( (a, a))$
范文總結(jié)相關推薦
鄂ICP備17016276號-1