基于边的图文法产生式选择无关条件的判断  

Selection-free judgment for productions based on edge-based context-sensitive graph grammar

作　　者：王毅[1] 丁函[1] 

机构地区：[1]湖北文理学院数学与计算机科学学院,湖北襄阳441053

出　　处：《计算机应用》2014年第11期3180-3183,共4页journal of Computer Applications

基　　金：湖北省教育厅科学研究计划项目(Q20142607)

摘　　要：为了降低归约算法的时间复杂度,在基于边的上下文相关图文法(EGG)形式化的基础上,通过对产生式形式的适当约束,提出了EGG的产生式选择无关条件的判断方法。通过此方法可有效判断EGG产生式的选择无关性。对于选择无关的产生式,由于归约过程中产生式的使用顺序不会影响归约的结果,从而避免了回溯,能够有效地降低归约算法的时间复杂度。In order to reduce the time complexity of parsing algorithm, based on the Edge-based context-sensitive Graph Grammar（ EGG）, a selection-free judgment method was proposed for the productions of EGG with appropriate constraints.This method can effectively judge the selection independence of the productions of EGG. For the selection-free productions,using the order of the productions will not affect the result of the parsing, thus the parsing process can avoid backtracking and the time complexity of the parsing algorithm can be effectively reduced.

关 键 词：选择无关 归约算法 时间复杂度 基于边的上下文相关图文法 

分 类 号：TP391.4[自动化与计算机技术—计算机应用技术]