資源描述：
《編譯原理例題與習(xí)題解答.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。
1、例題與習(xí)題解答第二章1回顧程序語言的定義一個(gè)程序語言是一個(gè)記號(hào)系統(tǒng),它主要由以下方面定義：語法語義每個(gè)句子構(gòu)成的規(guī)律研究語言每個(gè)句子的含義語法語義2語法={詞法規(guī)則+語法規(guī)則}詞法規(guī)則：?jiǎn)卧~符號(hào)的形成規(guī)則。單詞符號(hào)是語言中具有獨(dú)立意義的最基本結(jié)構(gòu)。一般包括：常數(shù)、標(biāo)識(shí)符、基本字、算符、界符等。描述工具：正規(guī)式和有限自動(dòng)機(jī)理論語法規(guī)則：語法單位的形成規(guī)則。語法單位通常包括：表達(dá)式、語句、子程序、過程、函數(shù)、程序等;描述工具：上下文無關(guān)文法回顧3標(biāo)識(shí)符與名字標(biāo)識(shí)符：以字母開頭的，由字母數(shù)字組成的字符串。標(biāo)識(shí)符與名字兩者有本質(zhì)區(qū)別：標(biāo)識(shí)符是語法概念名字有確切
2、的意義和屬性回顧4上下文無關(guān)文法的定義：一個(gè)上下文無關(guān)文法G是一個(gè)四元式G=(VT，VN，S，P)，其中VT：終結(jié)符集合(非空)VN：非終結(jié)符集合(非空)，且VT?VN=?S：文法的開始符號(hào)，S?VNP：產(chǎn)生式集合(有限)，每個(gè)產(chǎn)生式形式為P??，P?VN，??(VT?VN)*開始符S至少必須在某個(gè)產(chǎn)生式的左部出現(xiàn)一次?；仡?假定G是一個(gè)文法，S是它的開始符號(hào)。如果S??，則稱?是一個(gè)句型。僅含終結(jié)符號(hào)的句型是一個(gè)句子。文法G所產(chǎn)生的句子的全體是一個(gè)語言，將它記為L(zhǎng)(G)L(G)=｛?
3、S??&?∈VT*｝文法產(chǎn)生語言*+回顧6定義：如果一個(gè)文法存在某
4、個(gè)句子對(duì)應(yīng)兩顆不同的語法樹，則說這個(gè)文法是二義的。語言的二義性：一個(gè)語言是二義性的，如果對(duì)它不存在無二義性的文法?？赡艽嬖贕和G’，一個(gè)為二義的，一個(gè)為無二義的。但L(G)=L(G’)回顧文法和語言的二義性7例題2.1：有一個(gè)文法G=({S,A,B},{a,b},P,S),其中P:S?aB
5、bAA?a
6、aS
7、bAAB?b
8、bS
9、aBB采用最左推導(dǎo)產(chǎn)生句子aabbab并畫出相應(yīng)的語法樹。S?aB?aaBB?aabSB?aabbAB?aabbaB?aabbabSaBaBBbSbbAa8例題2.2試構(gòu)造生成語言L={anbnci
10、n?1,i?0}的文法分析：
11、要求a和b的個(gè)數(shù)一樣多，并至少為一個(gè)，而c的個(gè)數(shù)為0個(gè)以上即可，所以可以用一個(gè)終結(jié)符去生成anbn串，用另一個(gè)非終結(jié)符去生成ci。G(Z):Z?ABA?aAb
12、abB?cB
13、?9例題2.3請(qǐng)證實(shí)文法G(E):E?EiT
14、TT?T+F
15、iF
16、FF?E*
17、(是一個(gè)二義文法。10P36-6.文法G6為:N→D
18、NDD→0
19、1
20、2
21、3
22、4
23、5
24、6
25、7
26、8
27、9（1）G6的語言L(G6)是什么?G6的語言是：0~9的數(shù)字組成的任意非空數(shù)字串L(G6)={x
28、x∈{0,1,2,3,4,5,6,7,8,9}+}（2）給出句子0127、34和568的最左和最右推導(dǎo)。11
29、注意：1)步驟，?和?的區(qū)別；2)?不能寫為→解：0127的最左推導(dǎo)：N?ND?NDD?NDDD?DDDD?0DDD?01DD?012D?01270127的最右推導(dǎo)：N?ND?N7?ND7?N27?ND27?N127?D127?0127+P36-7寫一文法,使其語言是奇數(shù)集,但不允許出現(xiàn)以0打頭的奇數(shù)。解:將奇數(shù)劃分為三個(gè)部分：最高位允許出現(xiàn)1～9,用非終結(jié)符B表示;中間部分可出現(xiàn)任意多位數(shù)字0～9,每一位用非終結(jié)符D表示;最低位只出現(xiàn)1,3,5,7,9,用A表示。由于中間部分可任意位,故需另引入一非終結(jié)符M,它包括最高位和中間部分。13MB…最高位中
30、間位DDDA最低位14解:奇數(shù)集文法G[N]為:G=({0,1,…,9},{N,A,M,B,D},N,ξ)ξ:N→A
31、MAM→B
32、MDA→1
33、3
34、5
35、7
36、9B→1
37、2
38、3
39、4
40、5
41、6
42、7
43、8
44、9D→0
45、B158.令文法為E→T
46、E+T
47、E-TT→F
48、T*F
49、T/FF→(E)
50、i(1)給出i+i*i、i*(i+i)的最左推導(dǎo)和最右推導(dǎo)。解：此處僅以i*(i+i)為例給出答案最左推導(dǎo)E?T?T*F?F*F?i*F?i*(E)?i*(E+T)?i*(T+T)?i*(F+T)?i*(i+T)?i*(i+F)?i*(i+i)最右推導(dǎo)E?T?T*F?T*(E)?T
51、*(E+T)?T*(E+F)?T*(E+i)?T*(T+i)?T*(F+i)?T*(i+i)?F*(i+i)?i*(i+i)8.令文法為E→T
52、E+T
53、E-TT→F
54、T*F
55、T/FF→(E)
56、iEE-TE-TTFFiFiii-i-i的語法樹(2)給出i+i+i、i+i*i和i-i-i的語法樹。EE+TE+TTFFiFiii+i+i的語法樹i+i*i的語法樹EE+TTTFFiFii*注意：樹枝和符號(hào)均不可隨意增減！9、證明文法:S→iSeS
57、iS
58、i是二義的。二義性的含義:如果文法存在某個(gè)句子對(duì)應(yīng)兩棵以上不同的語法樹，或者兩種以上不同的最左/右推導(dǎo)，則稱
59、這個(gè)文法是二義的。首先：找到此文法對(duì)應(yīng)的一個(gè)句子iiiei其次：構(gòu)造與之對(duì)應(yīng)的兩棵語法樹SiS
