編譯原理練習(xí)文檔資料

1、編譯原理練習(xí)文法和語言文法和語言符號和符號串符號和符號串文法的類型文法的類型文法和語言的文法和語言的形式化定義形式化定義句型分析句型分析語法樹語法樹文法和語言的二義性文法和語言的二義性上下文無關(guān)文法上下文無關(guān)文法文法的定義文法的定義推導(dǎo)的定義推導(dǎo)的定義語言的定義語言的定義第三章第三章字母表和符號串字母表和符號串符號串的運算符號串的運算集合的閉包運算集合的閉包運算第三章第三章1、作業(yè)、作業(yè)p48 第第5題題 寫一文法，使其語言是偶正整數(shù)的集合。寫一文法，使其語言是偶正整數(shù)的集合。 要求：要求： 允許允許 0 打頭。打頭。思路：思路：首先根據(jù)集合的描述設(shè)計幾個句子，然后從句子中找出規(guī)律（或共性首先

2、根據(jù)集合的描述設(shè)計幾個句子，然后從句子中找出規(guī)律（或共性），把它們的性質(zhì)用產(chǎn)生式表示出來。），把它們的性質(zhì)用產(chǎn)生式表示出來。提示提示：（：（1）生成的偶正數(shù)應(yīng)不包括，若干個生成的偶正數(shù)應(yīng)不包括，若干個0。（2）將偶正數(shù)分為兩類：一類為允許若干個）將偶正數(shù)分為兩類：一類為允許若干個0（0個數(shù)個數(shù)=0）后跟不以）后跟不以0開頭開頭的偶正數(shù)；一類為允許若干個的偶正數(shù)；一類為允許若干個0后跟后跟2|4|6|8的偶正數(shù)（如的偶正數(shù)（如0002，即不允許只含，即不允許只含有若干有若干0 ）。）。2、為只包含數(shù)字、為只包含數(shù)字、 , 的表達式，例如的表達式，例如 9 2 5等構(gòu)造一個文法，使得等構(gòu)造一個文法

3、，使得 和和 運算滿足右結(jié)合，運算滿足右結(jié)合， 的運算優(yōu)先級高于的運算優(yōu)先級高于 。提示：結(jié)合性和運算優(yōu)先性可以根據(jù)語法樹的層次考慮。進而思考左遞歸產(chǎn)提示：結(jié)合性和運算優(yōu)先性可以根據(jù)語法樹的層次考慮。進而思考左遞歸產(chǎn)生式與運算符的結(jié)合性的關(guān)系。生式與運算符的結(jié)合性的關(guān)系。3、一個上下文無關(guān)文法生成句子、一個上下文無關(guān)文法生成句子 abbaa 的推導(dǎo)樹如下：的推導(dǎo)樹如下： (1)給出串給出串 abbaa 最左推導(dǎo)、最右推導(dǎo)。最左推導(dǎo)、最右推導(dǎo)。 (2)該文法的終結(jié)符、非終結(jié)符、產(chǎn)生式集合該文法的終結(jié)符、非終結(jié)符、產(chǎn)生式集合 p 可能有哪些元素？可能有哪些元素？ (3)找出該句子的所有短語、直接短

4、語、句柄。找出該句子的所有短語、直接短語、句柄。 提示：知識點：語法樹的構(gòu)造，文法的組成，短語等概念。提示：知識點：語法樹的構(gòu)造，文法的組成，短語等概念。4、給出生成下述語言的三型文法：、給出生成下述語言的三型文法：anbmck|n, k=1，m0 提示：（提示：（1）三型文法中產(chǎn)生式的特點）三型文法中產(chǎn)生式的特點（2）可參考）可參考p49 第第16題題詞法分析詞法分析自動構(gòu)造工具自動構(gòu)造工具正規(guī)集正規(guī)集正規(guī)式正規(guī)式有窮自動機（有窮自動機（nfa dfa)正規(guī)文法正規(guī)文法第四章第四章 知識結(jié)構(gòu)知識結(jié)構(gòu)n1 1、已知正規(guī)式、已知正規(guī)式b(ab)b(ab)* *和和(ba)(ba)* *b b(1

5、)(1)分別構(gòu)造上述兩個正規(guī)式相應(yīng)的分別構(gòu)造上述兩個正規(guī)式相應(yīng)的dfadfa，(2) (2) 將將(1)(1)構(gòu)造的構(gòu)造的dfadfa最小化，最小化，(3)(3)利用利用dfadfa證明證明b(ab)b(ab)* *=(ba)=(ba)* *b b(4)(4)構(gòu)造該語言的正規(guī)文法。構(gòu)造該語言的正規(guī)文法。n提示：提示：q使用的知識點：正規(guī)式使用的知識點：正規(guī)式 nfanfa，nfanfadfadfa，dfadfa的最小的最小化，化，dfa dfa 正規(guī)文法。正規(guī)文法。q由轉(zhuǎn)化得到的相同的最小化由轉(zhuǎn)化得到的相同的最小化dfadfa，進而證明兩個正規(guī)式，進而證明兩個正規(guī)式等價。等價。n2 2、(1)(1)由偶數(shù)個由偶數(shù)個0 0和奇數(shù)個和奇數(shù)個1 1構(gòu)成的所有構(gòu)成的所有0101串的。串的。（2 2）寫出）寫出由由0 0和和1 1的個數(shù)都是偶數(shù)的的個數(shù)都是偶數(shù)的0101串的正規(guī)式。串的正規(guī)式。q提示：見下頁提示：見下頁pptppt參考課件參考課件 例例2