A T-IDP-based HPSG parsing algorithm

Some HPSG (head-driven phrase structure grammar) parsing algorithm did not consider the cross-schemata attribute passing paths or bounded attribute-passing paths which exist in certain-natural language structures. Therefore, based on the concept of attribute grammars, the attribute dependencies of HPSG parse trees are defined and the T-IDP-based HPSG parsing algorithm is forwarded. The feature of the parsing algorithm is that it has inductive mechanism T-IDP (induced attribute dependencies of structure tree), which induces the whole attributed structure tree out of separate instances of attribute dependencies and gives the formal description of the attributed structure tree. The computational efficiency of the T-IDP-based HPSG parsing algorithm is in the cubic time, and thus the algorithm is efficient. Finally an application example was examined.