Efficient parsing algorithm for CFG with robust dependency constraints

D. Toushinbatto, Yoichi Tomiura, Toru Hitaka

Research output: Contribution to journalArticlepeer-review


A context-free grammar (CFG) in which dependency constraints are tucked into production rules has been proposed, where syntactic categories are subdivided by the headword of the phrase. It's difficult to collect all necessary rules expressing dependency constraints in the grammar, so taking superordinate-subordinate relations in the word hierarchy into the grammar as production rules has been considered. However, because there are huge number of syntactic trees for an input sentence in this grammar, how to select a preferable syntactic tree is very important. This paper shows an efficient parsing algorithm, specialized to the heuristics for selecting the most plausible syntactic tree.

Original languageEnglish
Pages (from-to)223-227
Number of pages5
JournalResearch Reports on Information Science and Electrical Engineering of Kyushu University
Issue number2
Publication statusPublished - Sept 2000

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture
  • Engineering (miscellaneous)
  • Electrical and Electronic Engineering


Dive into the research topics of 'Efficient parsing algorithm for CFG with robust dependency constraints'. Together they form a unique fingerprint.

Cite this