Even faster generalized LR parsing
Even faster generalized LR parsing
复制标题
更快的广义 LR 解析
DOI：
10.1007/pl00013319
复制
发表时间：
2001
期刊：
影响因子：
0.6
通讯作者：
B. Melichar
中科院分区：
文献类型：
--
作者：
John Aycock;N. Horspool;Jan Janousek;B. Melichar
抽象。我们证明了广义LR（GLR）分析的一个属性-如果语法没有右和隐藏的左递归，那么两个相邻符号的移位之间的连续减少的数量不能大于一个常数。此外，我们表明，这个属性可以用于构建我们的GLR解析器的优化版本。与标准的GLR解析器相比，我们优化的解析器在每个转换上读取一个符号，并执行显着减少的堆栈操作。我们的时间表明，特别是高度模糊的语法，我们的解析器是显着快于标准的GLR解析器。
Abstract. We prove a property of generalized LR (GLR) parsing – if the grammar is without right and hidden left recursions, then the number of consecutive reductions between the shifts of two adjacent symbols cannot be greater than a constant. Further, we show that this property can be used for constructing an optimized version of our GLR parser. Compared with a standard GLR parser, our optimized parser reads one symbol on every transition and performs significantly fewer stack operations. Our timings show that, especially for highly ambiguous grammars, our parser is significantly faster than a standard GLR parser.