LALR(1)分析器快速生成

摘要

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