Full LR(1) parser generator Hyacc and study on the performance of LR(1) algorithms
Full LR(1) parser generator Hyacc and study on the performance of LR(1) algorithms
复制标题
完整的 LR(1) 解析器生成器 Hyacc 以及 LR(1) 算法性能研究
DOI：
10.1145/1992896.1992907
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
D. Pager
中科院分区：
文献类型：
--
作者：
Xin Chen;D. Pager
尽管诸如Yacc/野牛之类的LALR（1）解析器生成器和诸如ANTLR之类的LL解析器生成器非常流行，但由于昂贵的性能和实现困难，健壮有效的LR（1）解析器生成器很少。本文采用Knuth规范算法、Pager实用通用方法、车道跟踪算法、单位产生式消除算法及其扩展、边推进算法等相关算法，实现了一个高效、实用、兼容Yacc/Bison的开源解析器生成器Hyacc，该生成器支持完全LR（0）/LALR（1）/LR（1）和部分LR（k）。在实现的基础上，对LR（1）分析器生成算法和LALR（1）分析器生成算法进行了比较。结果表明，LR（1）分析器生成的基础上改进的算法和仔细选择的数据结构可以是足够有效的，是实际使用的现代计算设施。
Despite the popularity of LALR(1) parser generators such as Yacc/Bison and LL parser generators such as ANTLR, robust and effective LR(1) parser generators are rare due to expensive performance and implementation difficulty. This work employed relevant algorithms, including the Knuth canonical algorithm, Pager's practical general method, lane-tracing algorithm, unit production elimination algorithm and its extension, and the edge-pushing algorithm, implemented an efficient, practical and Yacc/Bison-compatible open-source parser generator Hyacc, which supports full LR(0)/LALR(1)/LR(1) and partial LR(k). Based on the implementation, an empirical study was conducted comparing different LR(1) parser generation algorithms and LALR(1) algorithms. The result shows that LR(1) parser generation based upon improved algorithms and carefully selected data structures can be sufficiently efficient to be of practical use with modern computing facilities.