Linear algorithm for lexicographic enumeration of CFG parse trees |
| |
Authors: | YunMei Dong |
| |
Affiliation: | (1) State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, Beijing, 100190, China |
| |
Abstract: | We study CFG parse tree enumeration in this paper. By dividing the set of all parse trees into infinite hierarchies according
to height of parse tree, the hierarchical lexicographic order on the set of parse trees is established. Then grammar-based
algorithms for counting and enumerating CFG parse trees in this order are presented. To generate a parse tree of height n,
the time complexity is O(n). If τ is a lowest parse tree for its yield, then O(n) =O(∥ gt ∥+ 1), where ∥τ ∥ is the length of the sentence (yield) generated by τ. The sentence can be obtained as a by-product
of the parse tree. To compute sentence from its parse tree (needn’t be lowest one), the time complexity is O(node)+O(∥τ ∥ + 1), where node is the number of non-leaf nodes of parse tree τ. To generate both a complete lowest parse tree and
its yield at the same time, the time complexity is O(∥τ ∥ + 1).
Supported by the National Natural Science Foundation of China (Grant Nos. 60273023, 60721061) |
| |
Keywords: | hierarchical construction of set of parse trees lexicographic enumeration of parse trees counting of parse trees |
本文献已被 维普 SpringerLink 等数据库收录! |
|