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

GLR分析方法主要用于自然语言的处理分析,较少应用于软件逆向工程领域的语法分析.针对软件逆向工程领域的语法分析特点,分析传统确定性分析算法的局限性,阐述采用GLR分析算法的目的.通过实例剖析GLR算法的主要性能瓶颈,从分析表构造、分析动作执行等多个层面对算法进行优化,提出一种面向软件逆向工程的GLR优化算法.该算法已在一个可视化语法分析器自动生成环境中实现.实验结果表明,在分析无二义性输入串时,该优化算法与传统的LALR(1)文法具有可比性,实用价值较高.     

一个高效的语法分析器生成工具

VPGE(Visual Parser Generation Environment)是一个可视化语法分析器集成开发环境,除了具有良好的界面和强大的调试功能,其LALR(1)分析器的生成速度达到并超过公认的分析器生成速度最快的LALR(1)分析器自动生成器Bison,所能处理的文法规模也优于Bison.本文在DeRemer和Pennello的LALR(1)分析器自动生成基本原理的基础上,在设计数据结构和算法实现中采用了大量优化技术.     

一个高效的语法分析器生成工具

VPGE(VisualParserGenerationEnvironment)是一个可视化语法分析器集成开发环境,除了具有良好的界面和强大的调试功能,其LALR(1)分析器的生成速度达到并超过公认的分析器生成速度最快的LALR(1)分析器自动生成器Bison,所能处理的文法规模也优于Bison.本文在DeRemer和Pen-nello的LALR(1)分析器自动生成基本原理的基础上,在设计数据结构和算法实现中采用了大量优化技术.     

LR(K)语法分析器的优化及加速

本文提出了构造优化和加速LR(K)语法分析器的一个新算法。它作为多功能LR语法分析器自动构造系统——XYZ/PG的主体,已用PASCAL语言在NORD-500型计算机上实现。与目前堪称最优的Pager算法相比较,本文算法通常可得到体积更小的LR(K)语法分析器。     

LR分析法在词法分析器自动构造中的应用

提出了一种新的自动构造编译程序词法分析器的方法,LR分析法通常用于语法分析,但只要适当修改LR分析总控程序,就可将LR分析法用于词法分析器的自动构造。该方法的优点不仅在于将词法分析器自动构造方法与语法分析器自动构造方法统一,简化了编译程序的设计和构造,而且该方法自动化程序较高,只要确定描述单词的文法和词形编码表,便可自动生成任何程序设计语言编译程序的词法分析器。     

多功能LR语法分析器构造系统XYZ/PG的理论与实现

:本文详细地讨论了正则LR(K)分析表(canonical LR(K)parsing table)与优化LR(K)分析表之间的转换关系,并在这一讨论的基础上提出了构造优化和加速LR(K)语法分析器的一个新算法。同时,文中给出了算法的正确性证明。作为多功能LR语法分析器构造系统——XYZ/PG的主体,本文算法已用PASCAL语言在NORD-500型计算机及DAUL 68000微型计算机上实现。与目前堪称最优的Pager算法相比本文算法通常可得到体积更小的LR(K)语法分析器。     

基于Z规格的LR(k)形式化分析及验证

在编译器的构造中,常由于语义的二义性等问题导致不正确的目标程序.为解决此问题,提出了一种新型的语法及语义正确性验证方案,即建立LR (k)文法和Z规格说明的联系,以此构造LR (k)文法的形式化描述及其形式化验证.实验结果表明,该方案能有效描述并检测LR (k)文法分析器中的语法错误及语义二义性,有助于提高分析器的有效性.     

基于状态回朔技术的规范LR分析算法

LR分析技术以其自身的优点在实际当中有着非常广泛的应用,但是,能够识别LR(1)语言的规范LR分析器由于其下推自动机的复杂性,其实用性受到比较大的限制.通过回朔下推自动机的状态迁移路径能够从根本上解决这一问题.主要讨论了基于状态回朔技术的规范型LR分析器的基本原理与构造技术.     

一种有效的GLR分析器错误恢复方法

传统的分析器生成器多采用LALR(1)、LL(1)等确定性分析方法.近年来,随着软件再(逆向)工程的发展,GLR等非确定性的分析方法逐渐应用到分析器生成器中,但目前尚未有公开发表的文献提出并解决了自动生成的GLR分析器的错误处理和恢复问题.文中提出了一种基于子串分析的错误恢复方法,实验结果表明,该方法可以有效侦测和恢复输入串中的语法错误,具有较高的错误处理效率,有望应用到以GLR为核心算法的分析器生成器中.     

一个实用的语法分析器自动生成系统

一、前言LR分析算法是knuth 1965年首先提出的.LR分析器能自动生成,运行效率高,查错功能强,识别语法类大,可用于大多数由上下文无关文法描述的程序语言.然而,由于一般的LR分析器状态数量极多,需要大量的存储空间,很不实用.为此,人们做了许多努力.以后演变出的SLR、LALR文法都是对LR文法加以某种限制,所识别的文法类是LR文法的一个子集,因此可以比较有效地实现.     

语法分析方法研究评述及其应用

语法分析作为编译过程中一个不可缺少的步骤,对其进行研究有着非常重要的意义.阐述了语法分析方法研究的现状,并对之进行了具体的分析和探讨,介绍了语法分析方法的各种应用,对语法分析方法进行了总结和展望.     

LR分析的教学法探讨

LR分析法是编译程序语法分析中最常用且有效的自下而上的分析方法,理论较完善,适用于大多数上下文无关语言的分析。本文主要探讨LR分析的教学方法,采用"启发+关联式"教学法,引导学生理解LR分析的内涵。     

On a method for optimizing LR parsers

It is shown that if the basic method for eliminating single productions from canonical LR parsers developed by Pager is applied to an SLR parser and the resulting parser is free of conflicts, then the resulting parser is a valid parser which accepts exactly the strings in the language. However, if the elimination process is performed during the construction of an SLR parser, then the resulting parser may be invalid even if it were free of conflicts.     

Error handling in a parallel LR substring parser

Parallel parsing is currently receiving attention but there is little discussion about the adaptation of sequential error handling techniques to these parallel algorithms. We describe a noncorrecting error handler implemented with a parallel LR substring parser. The parser used is a parallel version of Cormack's LR substring parser. The applicability of noncorrecting error handling for parallel parsing is discussed. The error information provided for a standard set of 118 erroneous Pascal programs is analysed. The programs are run on the sequential LR substring parser.     

A convenient way to incorporate semantic actions in two-pass compiling schemes

We present a simple method for connecting semantic actions to parsers. Although applicable to any kind of parser it is especially suited for LR parsers. The method is based on the idea of separating syntax analysis and semantic processing and executing semantic actions by procedures, similar to those of a recursive descent compiler. The procedures are driven by structural information about the source program, which is collected during parsing. The method is applicable to L-attributed grammars. It can be incorporated easily into any existing parser.     

Software visualization of LR parsing and synthesized attribute evaluation

Visual YACC is a tool that automatically creates visualizations of the YACC LR parsing process and synthesized attribute computation. The Visual YACC tool works by instrumenting a standard YACC grammar with graphics calls that draw the appropriate data structures given the current actions by the parser. The new grammar is processed by the YACC tools and the resulting parser displays the parse stack and parse tree for every step of the parsing process of a given input string. Visual YACC was initially designed to be used in compiler construction courses to supplement the teaching of parsing and syntax directed evaluation. We have also found it to be useful in the difficult task of debugging YACC grammars. In this paper, we describe this tool and how it is used in both contexts. We also detail two different implementations of this tool: one that produces a parser written in C with calls to Motif; and a second implementation that generates Java source code. Copyright © 1999 John Wiley & Sons, Ltd.     

A practical minimum distance method for syntax error handling

We present a method for recovering from syntax errors encountered during parsing. The method provides a form of minimum distance repair, has linear time complexity, and is completely automatic. A formal method is presented for evaluating the performance of error recovery methods, based on global minimum-distance error correction. The minimum-distance error recovery method achieves a theoretically best performance on 80% of Pascal programs in the weighted Ripley-Druseikis collection. Comparisons of performance with other error recovery methods are given.     

编译原理中的LR类分析方法的教学研究

编译原理课程的教学不仅要介绍编译的基本原理和技术,还要培养学生的学习兴趣、专业思维和科学研究的方法及能力,文章以LR类分析方法为例,以还原知识的发现过程为主线,重现解决问题的思路与方法,以期培养学生的专业学习兴趣和科研能力。