上下文无关语言（CFL）的判定问题.ppt

《上下文无关语言（CFL）的判定问题.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、上下文无关语言(CFL)的判定问题问题描述上下文无关文法（Context-FreeGrammar,CFG）是一个4元组G=(V,T,S,P)，其中，V和T是不相交的有限集，S∈V，P是一组有限的产生式规则集，形如A→α，其中A∈V，且α∈(V∪T)*。V的元素称为非终结符，T的元素称为终结符，S是一个特殊的非终结符，称为文法开始符。设G=(V,T,S,P)是一个CFG，则G产生的语言是所有可由G产生的字符串组成的集合，即L(G)={x∈T*

2、Sx}。一个语言L是上下文无关语言（Context-FreeLanguage,CFL），当且仅当存在一个CFG

3、G，使得L=L(G)。*⇒例如，设文法G：S→ABA→aA

4、aB→bB

5、b则L(G)={a^nb^m

6、n,m>=1}其中非终结符都是大写字母，开始符都是S，终结符都是小写字母。编程任务：给定一个上下文无关文法的n条产生式规则，编程判断该文法对应的语言是否为空。若为空，则输出yes，否则输出no。数据输入：由文件input.txt提供输入数据。文件的第1行是规则数n。接下来n行是具体的规则，每行的开始是规则的左边，接着是规则的右边，中间用空格隔开。结果输出:将判定结果输出到文件output.txt中。算法思想题目理解：判断一个非终结符是否能转化为终结符

7、也就是一个大写字母能否用小写字母来表示。那判断该文法对应的语言是否为空，也就是判断S是否能用一连串的小写字母来表示。扫描思想：从第一个规则式到最后一个规则式进行一次全扫描：如果发现S还不能转化为小写字符且至少有一个新的其他大写字母能转化为小写字母，则又开始进行一次全扫描；如果发现S能转化为小写字母，则跳出程序，输出no；如果发现没有新的大写字母可以化为小写字母且S目前也没办法化为小写字母，则跳出程序，输出yes。算法总流程从上往做全扫描，最多也只能做26次第一个规则最后一个规则数据结构动态生成一维数组char*left=newchar[n+1];存储

8、规则式左边的非终结符号动态生成二维数组char**right=newchar*[n+1];存储规则式右边的一串字符设置一个固定一维数组shortintflag[26]；标志对应的非终结符是否可化为终结符如果值为1表示该非终结符在这些规则下可以转化为终结符，如果值为0表示不可以最终转化为终结符一条规则的判断流程LeftrightflagAB----------Z(1)、数组left取出该规则的左部大写字母,接着到flag数组中查看该字母是否可以化为非终结符。可以的话，则跳出，对下一条规则进行判断，如果不可以的则继续往下执行(2)、从判断right中的第

9、一个字母开始：⑴如果是小写字母的话，判断下一个字母；⑵如果该字母是大写的话，则去flag数组中查看该字母目前是否可以转化为非终结符号，①如果可以的话，判断下一个字母②不可以的话，跳出该循环判断过程。(3)、判断目前指针指向的是否为空，如果为空的话，说明该规则left对应的大写字母能够转化为小写字母来表示，则把该字母在数组flag中对应的值改为1。如果不为空，则表示该字母目前还没办法转化为小写字母来表示，所以继续判断下一条规则。具体的一个例子S→ABA→aBA→cBB→bBB→b第一次从上往全部扫描结束后，发现B终结符可以转化为非终结符，则：flag[

10、1]=1而S对应的flag[18]=0，而且出现一个新的非终结符B可以转化为终结符，所以从头进行第三次全扫描。第二次从上往全部扫描结束后，发现A终结符可以转化为非终结符，则：flag[0]=1而S对应的flag[18]=0，而且出现一个新的非终结符A可以转化为终结符，所以从头进行第三次全扫描。第三次扫描的结束后，发现S也可以转化为非终结符，则置flag[18]=1，退出程序运行。（PS：具体流程请参见代码）