An efficient all-parses systolic algorithm for general context-free parsing |
| |
Authors: | Oscar H Ibarra Michael A Palis |
| |
Affiliation: | (1) Department of Computer Science, University of California, Santa Barbara, 93106 Santa Barbara, California;(2) Deparmment of Computer and Information Science, University of Pennsylvania, 19104 Philadelphia, PA |
| |
Abstract: | The problem of outputting all parse trees of a string accepted by a context-free grammar is considered. A systolic algorithms is presented that operates inO(m·n) time, wherem is the number of distinct parse trees andn is the length of the input. The systolic array usesn
2 processors, each of which requires at mostO(logn) bits of storage. This is much more space-efficient that a previously reported systolic algorithm for the same problem, which requiredO(n logn) space per processor. The algorithm also extends previous algorithms that only output a single parse tree of the input.Research squpported in part by NSF Grant DCR-8420935 and DCR-8604603. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|