|
|||||
|
|
| LALR(1)分析器快速生成 | |
| 引用本文： | 李虎,杨晓津,刘超.LALR(1)分析器快速生成[J].北京航空航天大学学报,2008,34(1):117-121. |
| 作者姓名： | 李虎 杨晓津 刘超 |
| 作者单位： | 1. 北京航空航天大学 计算机学院, 北京 100083; 2. 总参第61研究所, 北京 100039 |
| 基金项目： | 国家自然科学基金，国家高技术研究发展计划(863计划) |
| 摘 要： | 根据LR(0)自动机的构造理论及Deremer和Pennello的LALR(1)向前看符号集计算公式,提出求解公式中的lookback关系和includes关系的高效算法. 研究过程表明,LR(0)项目集闭包计算和项目集的查找是LR(0)分析器构造过程中的主要性能瓶颈.对这两个计算过程给出了高效的数据结构和算法设计,实现了LALR(1)分析器的快速生成.系统实现及实验数据表明,LALR(1)分析器的生成速度超过了自由软件基金会的LALR(1)分析器生成器Bison. |
| 关 键 词： | 语法分析器生成 自底向上分析 向前看符号集 |
| 文章编号： | 1001-5965（2008）01-0117-05 |
| 收稿时间： | 2007-01-15 |
| 修稿时间： | 2007年1月15日 |
Faster generation of LALR(1) parsers |
|
| Li Hu,Yang Xiaojin,Liu Chao.Faster generation of LALR(1) parsers[J].Journal of Beijing University of Aeronautics and Astronautics,2008,34(1):117-121. | |
| Authors: | Li Hu Yang Xiaojin Liu Chao |
| Institution: | 1. School of Computer Science and Technology, Beijing University of Aeronautics and Astronautics, Beijing 100083, China; 2. Institute 61, General Staff PLA, Beijing 100039, Chin |
| Abstract: | Deremer &; Pennello-s formula for computing LALR(1) lookaheads was studied in practice, by introducing a forward searching method for the computation of lookback and includes relations which were defined in the formula. Efficient algorithms for implementing of the two relations were designed. Several experiments were conducted to show that the computation of LR(0) items closure and searching for a sate in LR(0) state machine are the main bottlenecks of parser generation. Effective and efficient data structures and algorithms for the optimization of these two computations were also proposed. Experimental results show that the speed of LALR(1) parser generation implemented by improved algorithm is even faster than the speed of Bison, a well-known defacto industrial standard of LALR(1) parser generator. |
| Keywords: | parser generation LALR(1) lookaheads |
| 本文献已被 维普 万方数据 等数据库收录！ | |
| 点击此处可从《北京航空航天大学学报》浏览原始摘要信息 | |
| 点击此处可从《北京航空航天大学学报》下载免费的PDF全文 | |