LALR(1)分析器快速生成

李虎; 杨晓津; 刘超

LALR(1)分析器快速生成

1.
北京航空航天大学计算机学院, 北京 100083
2. 总参第61研究所, 北京 100039

基金项目: 国家自然科学基金资助项目(60573084,60703057); 国家高技术研究发展(863)计划资助项目(2006AA01Z176)

详细信息

中图分类号: TP 310
计量
- 文章访问数: 3101
- HTML全文浏览量: 145
- PDF下载量: 1738
- 被引次数: 19
出版历程
- 收稿日期: 2007-01-15
- 网络出版日期: 2008-01-31

Faster generation of LALR(1) parsers

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

摘要

摘要: 根据LR(0)自动机的构造理论及Deremer和Pennello的LALR(1)向前看符号集计算公式,提出求解公式中的lookback关系和includes关系的高效算法. 研究过程表明,LR(0)项目集闭包计算和项目集的查找是LR(0)分析器构造过程中的主要性能瓶颈.对这两个计算过程给出了高效的数据结构和算法设计,实现了LALR(1)分析器的快速生成.系统实现及实验数据表明,LALR(1)分析器的生成速度超过了自由软件基金会的LALR(1)分析器生成器Bison.
- 语法分析器生成 /
- 自底向上分析 /
- 向前看符号集
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.
- parser generation /
- LALR(1) /
- lookaheads

HTML全文

参考文献(1)

[1] 李虎. GLR分析器自动生成及相关研究 .北京:北京航空航天大学计算机学院, 2006 Li Hu. On GLR parser generation and related issues . Beijing: School of Computer Science and Technology, Beijing University of Aeronautics and Astronautics, 2006(in Chinese)[2] Park J C H, Choe K M, Chang C H. A new analysis of LALR formalism[J]. ACM Transactions on Programming Languages and Systems, 1985, 7(1): 159-175[3] Alfred V A,Ravi S,Jeffrey D U. Compilers: principles,techniques,and tools[M]. Beijing: China Post and Telecommunications Press, 2002[4] Deremer F, Pennello T. Efficient computation of LALR(1) look-ahead sets[J]. ACMTOPLAS, 1982, 4(4): 615-649[5] Sippu S, Soisalon-Soininen E. Parsing theory, Vol.II: LR( k ) & LL( k ) parsing[M]. Berlin: Springer-Verlag, 1990[6] Donnelly C, Stallmen R. The Bison manual: using the YACC-compatible parser generator, for Bison version 1.875[M]. Boston: GNU Press, 2004[7] Manuel Astudillo. GOLD parsing system .2007 .

施引文献

期刊类型引用(7)

1.	胡晨霄，李健，杨惠淋，武辰辉. 基于VACP多资源理论的高速列车驾驶室设计探究. 鞋类工艺与设计. 2025(02): 135-137 . 百度学术
2.	邹晓海，吴泓瑾. 基于多重资源理论的智能座舱移动办公交互设计研究. 包装与设计. 2025(01): 104-105 . 百度学术
3.	贺强，胥涛. 基于眼动和脑电的复合材料胶接挖补工作负荷研究. 科学技术与工程. 2024(26): 11449-11456 . 百度学术
4.	沈超，易灿南，李照鑫，胡鸿，吴文. 基于VACP的数字化核电厂主控室操纵员工作负荷评价. 安全. 2023(09): 66-72 . 百度学术
5.	于铮，杨聚芬，刘志钢，宋皓晨. 基于任务分层的地铁驾驶员应急处置作业工作负荷评价. 人类工效学. 2022(02): 73-76 . 百度学术
6.	姜兴宇，马明宇，齐鹏，马生顺，侯志权，刘伟军. 基于JACK的盾构机换刀作业人员工作负荷评估模型. 沈阳工业大学学报. 2021(05): 542-549 . 百度学术
7.	耿赫，周颖伟，张宜静，刘静，钮建伟，施锦寿. 复杂系统中多人协同作业的团队工作负荷评价综述. 航天医学与医学工程. 2020(05): 464-470 . 百度学术