1、上下文無關(guān)語言(CFL)的判定問題 1問題描述上下文無關(guān)文法（Context-Free Grammar, CFG）是一個4元組G=(V, T, S, P)，其中，V和T是不相交的有限集，SV，P是一組有限的產(chǎn)生式規(guī)則集，形如A，其中AV，且(VT)*。V的元素稱為非終結(jié)符，T的元素稱為終結(jié)符，S是一個特殊的非終結(jié)符，稱為文法開始符。 設(shè)G=(V, T, S, P)是一個CFG，則G產(chǎn)生的語言是所有可由G產(chǎn)生的字符串組成的集合，即L(G)=xT* | Sx。一個語言L是上下文無關(guān)語言（Context-Free Language, CFL），當(dāng)且僅當(dāng)存在一個CFG G，使得L=L(G)。 *例如，

2、設(shè)文法G：SAB AaA|a BbB|b 則L(G)=anbm | n,m=1 其中非終結(jié)符都是大寫字母，開始符都是S，終結(jié)符都是小寫字母。 2編程任務(wù)： 給定一個上下文無關(guān)文法的n條產(chǎn)生式規(guī)則，編程判斷該文法對應(yīng)的語言是否為空。若為空，則輸出yes，否則輸出no。 數(shù)據(jù)輸入： 由文件input.txt提供輸入數(shù)據(jù)。文件的第1行是規(guī)則數(shù)n。接下來n行是具體的規(guī)則，每行的開始是規(guī)則的左邊，接著是規(guī)則的右邊，中間用空格隔開。結(jié)果輸出: 將判定結(jié)果輸出到文件output.txt中。 3算法思想題目理解：判斷一個非終結(jié)符是否能轉(zhuǎn)化為終結(jié)符也就是一個大寫字母能否用小寫字母來表示。那判斷該文法對應(yīng)的語言是

3、否為空，也就是判斷S是否能用一連串的小寫字母來表示。掃描思想：從第一個規(guī)則式到最后一個規(guī)則式進(jìn)行一次全掃描：如果發(fā)現(xiàn)S還不能轉(zhuǎn)化為小寫字符且至少有一個新的其他大寫字母能轉(zhuǎn)化為小寫字母，則又開始進(jìn)行一次全掃描；如果發(fā)現(xiàn)S能轉(zhuǎn)化為小寫字母，則跳出程序，輸出no；如果發(fā)現(xiàn)沒有新的大寫字母可以化為小寫字母且S目前也沒辦法化為小寫字母，則跳出程序，輸出yes。4算法總流程從上往做全掃描，最多也只能做26次第一個規(guī)則 最后一個規(guī)則5數(shù)據(jù)結(jié)構(gòu)動態(tài)生成一維數(shù)組 char *left=new char n+1; 存儲規(guī)則式左邊的非終結(jié)符號動態(tài)生成二維數(shù)組char* right=new char* n+1;存儲規(guī)

4、則式右邊的一串字符設(shè)置一個固定一維數(shù)組 short int flag26；標(biāo)志對應(yīng)的非終結(jié)符是否可化為終結(jié)符 如果值為1 表示該非終結(jié)符在這些規(guī)則下可以轉(zhuǎn)化為終結(jié) 符，如果值為0 表示不可以最終轉(zhuǎn)化為終結(jié)符6一條規(guī)則的判斷流程Left right flag A B - Z(1)、數(shù)組left取出該規(guī)則的左部大寫字母,接著到flag數(shù)組中查看該字母是否可以化為非終結(jié)符?？梢缘脑?，則跳出，對下一條規(guī)則進(jìn)行判斷，如果不可以的則繼續(xù)往下執(zhí)行(2)、從判斷right中的第一個字母開始： 如果是小寫字母的話，判斷下一個字母；如果該字母是大寫的話，則去flag數(shù)組中查看該字母目前是否可以轉(zhuǎn)化為非終結(jié)符號，如

5、果可以的話，判斷下一個字母 不可以的話， 跳出該循環(huán)判斷過程。(3)、判斷目前指針指向的是否為空，如果為空的話，說明該規(guī)則left對應(yīng)的大寫字母能夠轉(zhuǎn)化為小寫字母來表示，則把該字母在數(shù)組flag中對應(yīng)的值改為1。如果不為空，則表示該字母目前還沒辦法轉(zhuǎn)化為小寫字母來表示，所以繼續(xù)判斷下一條規(guī)則。7具體的一個例子 SAB AaB A cB BbB Bb第一次從上往全部掃描結(jié)束后，發(fā)現(xiàn)B終結(jié)符可以轉(zhuǎn)化為非終結(jié)符，則：flag1=1 而S對應(yīng)的flag18=0，而且出現(xiàn)一個新的非終結(jié)符B 可以轉(zhuǎn)化為終結(jié)符，所以從頭進(jìn)行第三次全掃描。第二次從上往全部掃描結(jié)束后，發(fā)現(xiàn)A終結(jié)符可以轉(zhuǎn)化為非終結(jié)符，則：flag0=1 而S對應(yīng)的flag18=0，而且出現(xiàn)一個新的非終結(jié)符A