上下文无关语言CFL的判定问题.ppt
上下文无关语言(CFL)的判定问题,问题描述,上下文无关文法(Context-Free Grammar, CFG)是一个4元组G=(V, T, S, P),其中,V和T是不相交的有限集,SV,P是一组有限的产生式规则集,形如A,其中AV,且(VT)*。V的元素称为非终结符,T的元素称为终结符,S是一个特殊的非终结符,称为文法开始符。 设G=(V, T, S, P)是一个CFG,则G产生的语言是所有可由G产生的字符串组成的集合,即L(G)=xT* | Sx。一个语言L是上下文无关语言(Context-Free Language, CFL),当且仅当存在一个CFG G,使得L=L(G)。 * 例如,设文法G:SAB AaA|a BbB|b 则L(G)=anbm | n,m=1 其中非终结符都是大写字母,开始符都是S,终结符都是小写字母。,编程任务: 给定一个上下文无关文法的n条产生式规则,编程判断该文法对应的语言是否为空。若为空,则输出yes,否则输出no。 数据输入: 由文件input.txt提供输入数据。文件的第1行是规则数n。接下来n行是具体的规则,每行的开始是规则的左边,接着是规则的右边,中间用空格隔开。 结果输出: 将判定结果输出到文件output.txt中。,算法思想,题目理解: 判断一个非终结符是否能转化为终结符也就是一个大写字母能 否用小写字母来表示。那判断该文法对应的语言是否为空,也 就是判断S是否能用一连串的小写字母来表示。 扫描思想: 从第一个规则式到最后一个规则式进行一次全扫描:如果发现S 还不能转化为小写字符且至少有一个新的其他大写字母能转化 为小写字母,则又开始进行一次全扫描;如果发现S能转化为小 写字母,则跳出程序,输出no;如果发现没有新的大写字母可 以化为小写字母且S目前也没办法化为小写字母,则跳出程序, 输出yes。,算法总流程,从上往做全扫描,最多也只能做26次 第一个规则 最后一个规则,数据结构,动态生成一维数组 char *left=new char n+1; 存储规则式左边的非终结符号 动态生成二维数组 char* right=new char* n+1;存储规则式右边的一串字符 设置一个固定一维数组 short int flag26;标志对应的非终结符是否可化为终结符 如果值为1 表示该非终结符在这些规则下可以转化为终结 符,如果值为0 表示不可以最终转化为终结符,一条规则的判断流程,Left right flag A B - Z (1)、数组left取出该规则的左部大写字母,接着到flag数组中查看该字母是否可以化为非终结符。可以的话,则跳出,对下一条规则进行判断,如果不可以的则继续往下执行 (2)、从判断right中的第一个字母开始: 如果是小写字母的话,判断下一个字母;如果该字母是大写的话,则去flag数组中查看该字母目前是否可以转化为非终结符号,如果可以的话,判断下一个字母 不可以的话, 跳出该循环判断过程。 (3)、判断目前指针指向的是否为空,如果为空的话,说明该规则left对应的大写字母能够转化为小写字母来表示,则把该字母在数组flag中对应的值改为1。如果不为空,则表示该字母目前还没办法转化为小写字母来表示,所以继续判断下一条规则。,具体的一个例子,SAB AaB A cB BbB Bb 第一次从上往全部扫描结束后,发现B终结符可以转化为非终结符,则: flag1=1 而S对应的flag18=0,而且出现一个新的非终结符B 可以转化 为终结符,所以从头进行第三次全扫描。 第二次从上往全部扫描结束后,发现A终结符可以转化为非终结符,则: flag0=1 而S对应的flag18=0,而且出现一个新的非终结符A 可以转化 为终结符,所以从头进行第三次全扫描。 第三次扫描的结束后,发现S也可以转化为非终结 符,则 置flag18=1,退出程序运行。 (PS:具体流程请参见代码),