程序设计语言的GLR优化分析  

Optimized GLR Parsing for Programming Languages

作　　者：李虎[1] 金茂忠[1] 许福[1] 张敏[1] 

机构地区：[1]北京航空航天大学计算机学院,北京100083

出　　处：《软件学报》2005年第2期174-183,共10页Journal of Software

基　　金：国家高技术研究发展计划(863)~~

摘　　要：阐述了在程序设计语言语法分析器的构造中采用通用 LR(generalized LR,简称 GLR)分析算法的动机.提出了一个多层次的优化策略,加快了 GLR 分析器的分析速度.为基本的 GLR 算法增加了必要的运行时控制机制,以实现语法分析时调用文法规则附带的语义动作,化解输入串的二义性,同时避免 GLR 分析器可能存在的语义动作延迟问题.优化后的算法已在一个可视化语法分析器自动生成环境 VPGE 中实现.实验结果表明,在分析确定性的编程语言时,自动生成的 GLR 分析器的分析速度与自由软件基金会的 Bison 生成的 LALR(1)分析器的分析速度有可比性.The motivation of adopting the Generalized LR (GLR) parsing algorithm to construct parsers for programming languages is presented. A multi-level strategy for optimizing a GLR parser and the necessary runtime control mechanisms are introduced to the GLR parsers for flexible disambiguation and for invoking semantic actions attached to grammar rules while avoiding the “delayed semantic action” problem. The algorithm has been implemented in VPGE, a visual parser generation environment. Experimental results show that the speed of the generated GLR parsers is comparable to LALR(1) parsers generated by GNU’s Bison when parsing deterministic programming languages.

关 键 词：LR分析 通用LR分析 二义性化解 语义动作 分析森林 

分 类 号：TP314[自动化与计算机技术—计算机软件与理论]