The parsing algorithm of HPSG-deductive system

Parsing as logic deduction has become a latest approach in linguistics. HDS is an HPSG-deductive system basing on Martin-Lof typed lambda calculus. However, HDS is a formal system. HDS does not overtly include concrete parsing process. Therefore this paper presents an algorithm, which automatically finds out HDS deduction for concrete parsing. The feature of the algorithm is that it is type-driven and it is able to discover the possible phonologically null traces in a sentence and to fill traces with information so as to normalize these sentences. An application example shows validity of the algorithm.