KMP算法在正则文法中的应用  

作　　者：徐建金 

机构地区：[1]江西省鹰潭市职业中等专业学校,江西鹰潭335000

出　　处：《计算机光盘软件与应用》2013年第20期91-92,共2页Computer CD Software and Application

摘　　要：KMP又被称作克努特——莫里斯——普拉特操作(简称KMP算法)它是一种模式匹配算法,这个算法的关键是根据给定的模式串W1,m,定义一个next函数。本文阐述了利用KMP算法的匹配思想,解决不包含莫字符串系列的正则文法,该正则文法主要是用在词法分析过程中找出程序中的错误的代码,且对应的自动机中无等价的状态。本文根据KMP、正则文法和自动机的定义和基本原理证明了此技术的可行性和正确性,为编译程序设计提供自动生成最小化正则文法的技术和实现程序以供参考。

关 键 词：KMP算法 正则文法 左线性文法 右线性文法 混合线性文法 L(GL) 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]