Efficient Controlling of Parsing-Stack Operation for LR Parsers
Efficient Controlling of Parsing-Stack Operation for LR Parsers
复制标题
LR 解析器解析堆栈操作的有效控制
DOI：
10.1016/s0020-0255(99)00040-7
复制
发表时间：
1999
期刊：
影响因子：
--
通讯作者：
J. Aoe
中科院分区：
文献类型：
--
作者：
M. Fuketa;K. Morita;S. Lee;J. Aoe
提出一种基于堆栈状态和非堆栈状态区分的LR解析新方法。非堆栈状态是不需要压入LR解析堆栈的状态，堆栈状态是要压入其中的状态。通过使用基于这里定义的堆栈控制LR解析器的一些属性，可以显着提高解析速度和解析表的大小，其改进包括消除单元产生式的传统方法。通过对多种编程语言的实证观察，验证了其效率。还讨论了将其扩展到自然语言的广义 LR 解析器。
This paper presents a new method of LR parsing based on the distinction of stack states and non-stack states. Non-stack states are states, which do not need to be pushed into the LR parsing stack, and stack states are states to be pushed into it. By using some properties based on the stack-controlling LR parser defined here, the parsing speed and the size of parsing tables can be remarkably improved and their improvement includes the traditional method eliminating unit productions. By empirical observations for a variety of programming languages, the efficiency is verified. Extending it to the generalized LR parsers for natural language is also discussed.