A parsing forest algorithm for combinatory categorial grammar

作者：Wang Qingjiang^*; Zhang Lin

来源：ICIC Express Letters, 2014, 8(12): 3535-3540.

• Combinatory categorial grammar
• Decision algorithms
• Parsing tree
• Recursive algorithms
• Sub trees

To find all parsing trees under category combination ambiguity, a forest algorithm was proposed. The basic CYK decision algorithm was extended to keep combinatory information in table elements, and an auxiliary stack was used to exploit com-binatory ambiguity. Elements with more than one combination were pushed into stack, and elements with no combination available were popped from stack. The forest algorithm iteratively built parsing trees from scratch until the auxiliary stack became empty. Each parsing tree was built by recursive algorithm seeking subtree with an element as its root. If the recursive algorithm could not generate all leaf nodes within the element span, the subtree failed to finish. Example shows that the forest algorithm works as expected, and can find all parsing trees.

• 出版日期2014
• 单位河南大学