面向软件逆向工程的GLR优化算法  

Optimized GLR Algorithm for Software Reverse Engineering

作　　者：许福[1] 金茂忠[2] 陈志泊[1] 陈飞翔[1] 赖昌庆 

机构地区：[1]北京林业大学信息学院,北京100083 [2]北京航空航天大学计算机学院,北京100191 [3]国家国防科技工业局信息中心,北京100048

出　　处：《计算机工程》2013年第6期12-20,共9页Computer Engineering

基　　金：国家自然科学基金资助项目(60573084);北京林业大学青年科技基金资助项目(2010BLX14)

摘　　要：GLR分析方法主要用于自然语言的处理分析,较少应用于软件逆向工程领域的语法分析。针对软件逆向工程领域的语法分析特点,分析传统确定性分析算法的局限性,阐述采用GLR分析算法的目的。通过实例剖析GLR算法的主要性能瓶颈,从分析表构造、分析动作执行等多个层面对算法进行优化,提出一种面向软件逆向工程的GLR优化算法。该算法已在一个可视化语法分析器自动生成环境中实现。实验结果表明,在分析无二义性输入串时,该优化算法与传统的LALR(1)文法具有可比性,实用价值较高。GLR parsing method is mainly used in the processing and analyzing of natural languages, and is rarely used in the parsing of software reverse engineering. The low parsing speed is an important reason. The limitation of the traditional deterministic parsing methods and the necessity of GLR parsing method are introduced according to the parsing characteristics of software reverse engineering. An optimized GLR method is presented, which is implemented in a visual parser generator. Experimental result shows that this method has comparable parsing speed with the traditional LALR（1） parser, and can be used in the parsing of software reverse engineering.

关 键 词：GLR分析 语法分析器 GLR优化算法 软件再工程 软件逆向工程 分析器生成器 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]