Automatic detection and replacement of syntactic constructs causing shift/reduce conflicts

A method is described for repairing some shift/reduce conflicts caused by limited lookahead in LALR(1) parsers such as those built by bison. Also, six types of Extended BNF (EBNF) construct are identified that cause a shift/reduce conflict when a Yet Another Compiler Compiler (YACC) file translated directly from EBNF is processed by bison. For each type, a replacement EBNF construct is described representing the same grammar and causing no shift/reduce conflict when its YACC equivalent is processed by bison. Algorithms are given for identifying instances of each type and transforming them into their replacements. The algorithms are implemented in an automatic parser builder that builds parsers for subsets of the DMIS language. The parser builder reads an EBNF file and writes C++ classes, a YACC file, and a Lex file, which are then processed to build a parser. The parsers build a parse tree using the C++ classes. The EBNF for DMIS is written in natural terms so that natural C++ classes are generated. However, if translated directly into YACC, the natural EBNF leads to 22 shift/reduce conflicts that fall into the six types. The parser builder recognizes the six constructs and replaces them automatically before generating YACC. The YACC that is generated parses in terms of unnatural constructs while building a parse tree using natural C++ classes. The six types of construct may occur in any statement‐based language that uses a minor separator, such as a comma; hence knowing how to recognize and replace them may be broadly useful. Published in 2010 by John Wiley & Sons, Ltd.     

基于ANTLR的NC代码编译器的设计与实现

采用了扩展的巴科斯范式（EBNF）定义NC程序语法规则,提出了一种基于语言识别工具（ANTLR）的NC代码编译器的设计模型。该模型采用Java语言开发,具有良好的平台无关性;分别从词法分析、语法和语义分析、信息提取等方面进行编译器的设计与实现。实际运行结果表明：该模型能够高效地构建编译器原型;可快速、准确地对NC代码进行编译;具有良好的可扩展性。     

基于JavaCC的SQL编译器的设计与实现

采用扩展的巴科斯范式(EBNF)定义SQL语言的语法规则,提出了一种基于分析器自动生成工具(JavaCC)的SQL语言编译器的设计模型。该模型采用Java语言开发,具有良好的平台无关性;分别从词法、语法和语义分析、信息提取等方面进行编译器的设计与实现。实际运行结果表明:该模型能够快速高效地构建SQL编译器,且具有良好的可扩展性。     

基于EBNF和二次爬取策略的XSS漏洞检测技术*

跨站脚本（XSS）攻击是目前互联网安全的最大威胁之一。针对传统基于渗透测试技术的漏洞检测方法中攻击向量复杂度低易被过滤、整体检测流程繁琐等问题,提出了一种基于扩展巴科斯范式（EBNF）的攻击向量自动生成方法和XSS漏洞二次爬取策略。通过定义EBNF规则生成规则解析树,按层次遍历获得高复杂度攻击向量。在首次爬取页面时,将输入点信息嵌入到攻击向量后请求注入,之后进行二次爬取,请求合法参数获得返回页面。最后设计实现了原型系统,并使用两个平台进行漏洞检测。通过对比实验证明,该系统检测流程简单,在一定程度上提高了漏洞检测数,降低了漏洞误报率。     

面向PMVS算法的自动两级并行翻译方法

当使用高分辨率的图像作为图像处理算法的输入时会降低算法运行速度,将算法并行化可提升执行效率,但手动将串行程序转换为并行程序则较为繁琐,并且现有自动并行翻译工具性能不稳定,同时翻译后的程序是单一并行模式。面向基于面片的三维多视角立体视觉(PMVS)算法,提出一种从C到CUDA的自动两级并行翻译方法。使用ANTLR自动解析源C代码,通过分析数据依赖关系和循环数组私有化来识别可并行化的循环结构,将算法翻译成CPU多线程和GPU两级并行结构的代码。在算法执行过程中,将输入图像在CPU和GPU上分别进行处理,降低了算法总执行时间。实验结果表明,该方法的计算加速比随着输入图像分辨率的增加逐渐提高,最高约达到32,相比于PPCG和OpenACC自动并行翻译方法提升明显。