计算机理论论文ＲＧ识别关键技术钻研

所属栏目：计算机应用论文
发布时间：2013-11-12 16:11:15  更新时间：2013-11-12 16:42:14

　　摘要：RG是形式语言中最典型的一类文法。主要讨论和分析了RG的一种识别分析方法，给出了该方法的主要算法及实现的关键技术。对文法识别和自动机生成有决定性的作用。可给后续研究提供支持。

　　关键词：RegularGrammar,识别,自动机

　　1引言

　　乔姆斯基把文法分成四种类型，即0型、1型、2型和3型。这几类文法的差别在于对产生式施加不同的限制。设G=(VN，VT，P，S)，若P中的每一个产生式的形式都是A→Ba或A→a，其中A和B都是非终结符，a是终结符，则G是3型文法或正规文法，即RG.RG又有左线性和右线性之分，即右部为“Ba”则为左线性，为“aB”则为右线性，本文仅以左线性情形，右线性情形就不赘述。

　　本文是在设计了一个识别输入文法是否为RG的软件的基础上，着重对基本原理和关键技术做研究和分析，给出了一种识别方法的原理，在更好的加深巩固形式语言这一重要理论的同时，使得该理论更紧密的与实践相联系。

　　2相关定义及理论

　　定义2.1文法与自动机等价

　　根据形式语言理论，三型文法产生的语言是有穷自动机(FA)所接受的串集合。可以给出3型文法和相应识别系统FA间的转换规则。

　　采用下面的规则可从正规文法G（假定G为右线性文法）直接构造一个有穷自动机NFAM；使得L(M)=L(G)：?

　　①字母表与G的终结符集相同；

　　②为G中的每个非终结符生成M的一个状态，(不妨取成相同的名字)G的开始符号S是开始状态S；

　　③增加一个新状态Z，做为NFA的终态；

　　④对G中的形如A→tB其中t为终结符或ε，A和B为非终结符的产生式，构造M的一个转换函数f(A,t)=B；

　　⑤对G中形如A→t的产生式，构造M的一个转换函数f(A,t)=Z。

　　定义2.2NFA的确定化

　　在有穷自动机的理论里，有这样的定理：设L为一个由不确定的有穷自动机接受的集合，则存在一个接受L的确定的有穷自动机。将NFA转换成接受同样语言的DFA的算法称为子集法。详细证明可查阅参考文献[1]。

　　3文法的识别主要算法分析

　　识别的关键是对所输入的符号串的格式上的判断，左部需要满足为单个的大写英文，而右部应是单个小写或是一个小写和一个大写的组合，只有这样才满足RG的要求，此处给出对右部的进行识别的部分主要过程。

　　if(rlen==1)

　　{

　　charva=rs.GetAt(0);

　　findvalue(va,End,C);

　　rlen=-1;

　　}

　　以上算法是对文法右部的检查,即判断右部为单个小写的情况.

　　if(rlen==2)

　　{

　　charVT1=rs.GetAt(0);

　　charVT2=rs.GetAt(1);

　　intfa=0;

　　while(fa<=maxlen)

　　{

　　if(fa==maxlen)

　　{D=0;fa++;}

　　else

　　{

　　if(VT1==Noend[fa].value)

　　{

　　intfb=0;

　　while(fb<=maxlen)

　　{

　　if(fb==maxlen){D=0;fb++;fa=maxlen+1;}

　　else

　　{

　　if(VT2==End[fb].value)//是终结符号:

　　{fb=maxlen+1;fa=maxlen+1;}//检查全部完毕:

　　else{fb++;}

　　}

　　}

　　}

　　else{fa++;}

　　}

　　以上是对小写加大写的情况的分析。对经过判断后的文法存储，便可由接下的步骤完成文法到自动机的转换。这样就完成了一个较为完整的RG识别过程。

　　4结论

　　本文主要根据RG的特点，在设计了一个识别过程的基础上，完成文法判断及到自动机的转换。希望能够对词法分析的初学者提供一些帮助。下步待继续的工作是在自动机的基础上完成对输入句子的运行识别.

　　参考文献：

　　[1]张幸儿.计算机编译原理[M].2版.北京:科学出版社,2003:31-34.

　　[2]陈火旺,等.程序设计语言编译原理[M].3版.北京:国防工业出版社,2000:34-35.

　　[3]王育坚.VC++面向对象编程教程[M].北京:清华大学出版社,2003.