一般上下文无关文法的一个分析算法

本文给出一般上下文无关文法的一个分析算法。该算法可以看成是LR分析算法的推广,它既是自底向上,又是从左到右。理论分析表明本算法对一般文法具有时间界O(n~3)这里n是输入句子的长度);对有界歧义文法时间界为O(n~2),而对LR文法时间界为O(n)。由于本算法是先将文法转换成分析表,然后用分析表来指导对句子的分析。因而在实际应用中本算法一般要比Earley算法快,另外本算法输出中包含输入句子的所有可能的分析,并且仅需一简单枚举就可从此输出中找出句子的一个分析。

An Efficient Parsing Algorithm for General Context-free Grammars

This paper presents an efficient general context-free parsing algorithm. The algorithm. can be viewed as an extension of the LR parsing algorithm. It is both bottom-up and left-to-right. Theoretical study shows that the algorithm has a time bound O(n3) (where n is the length of the input string.) in general, it has an O(n2) time bound for bounded-ambiguous grammars, and run in linear time on LR grammars. Due to the utilization of LR parsing table, the algorithm appears to be faster than Earley's algorithm in practical runnings. Moreover, the algorithm produces all the parses for an input string in an efficient representation in which a parse can be extracted simply by an enumeration.