編譯原理練習(xí)第1頁2文法和語言符號和符號串文法類型文法和語言形式化定義句型分析語法樹文法和語言二義性上下文無關(guān)文法文法定義推導(dǎo)定義語言定義第三章字母表和符號串符號串運(yùn)算集合閉包運(yùn)算第2頁第三章1、作業(yè)P48第5題寫一文法，使其語言是偶正整數(shù)集合。要求：允許0打頭。思緒：首先依據(jù)集合描述設(shè)計(jì)幾個(gè)句子，然后從句子中找出規(guī)律（或共性），把它們性質(zhì)用產(chǎn)生式表示出來。提醒：（1）生成偶正數(shù)應(yīng)不包含，若干個(gè)0。（2）將偶正數(shù)分為兩類：一類為允許若干個(gè)0（0個(gè)數(shù)>=0）后跟不以0開頭偶正數(shù)；一類為允許若干個(gè)0后跟2|4|6|8偶正數(shù)（如0002，即不允許只含有若干0）。2、為只包含數(shù)字、

,表示式，比如9

2

5等結(jié)構(gòu)一個(gè)文法，使得

和

運(yùn)算滿足右結(jié)合，運(yùn)算優(yōu)先級高于。提醒：結(jié)合性和運(yùn)算優(yōu)先性能夠依據(jù)語法樹層次考慮。進(jìn)而思索左遞歸產(chǎn)生式與運(yùn)算符結(jié)合性關(guān)系。3、一個(gè)上下文無關(guān)文法生成句子abbaa推導(dǎo)樹以下：(1)給出串a(chǎn)bbaa最左推導(dǎo)、最右推導(dǎo)。(2)該文法終止符、非終止符、產(chǎn)生式集合P可能有哪些元素？(3)找出該句子全部短語、直接短語、句柄。提醒：知識點(diǎn)：語法樹結(jié)構(gòu)，文法組成，短語等概念。4、給出生成下述語言三型文法：{anbmck|n,k>=1，m>0}提醒：（1）三型文法中產(chǎn)生式特點(diǎn)（2）可參考P49第16題第3頁第4頁第5頁第6頁第7頁詞法分析自動結(jié)構(gòu)工具{正規(guī)集}正規(guī)式有窮自動機(jī)（NFADFA)正規(guī)文法第四章知識結(jié)構(gòu)①⑤⑥②③④第8頁1、已知正規(guī)式b(ab)*和(ba)*b(1)分別結(jié)構(gòu)上述兩個(gè)正規(guī)式對應(yīng)DFA，(2)將(1)結(jié)構(gòu)DFA最小化，(3)利用DFA證實(shí)b(ab)*=(ba)*b(4)結(jié)構(gòu)該語言正規(guī)文法。提醒：使用知識點(diǎn)：正規(guī)式

NFA，NFADFA，DFA最小化，DFA正規(guī)文法。由轉(zhuǎn)化得到相同最小化DFA，進(jìn)而證實(shí)兩個(gè)正規(guī)式等價(jià)。2、(1)由偶數(shù)個(gè)0和奇數(shù)個(gè)1組成全部01串ＤＦＡ。（2）寫出由0和1個(gè)數(shù)都是偶數(shù)01串正規(guī)式。提醒：見下頁P(yáng)PT第9頁第10頁第11頁12參考課件例2：接收0和1個(gè)數(shù)都是偶數(shù)字符串DFA312