IMPLEMENTATION OF PARSER USING TREE ADJOINING GRAMMAR FORMALISM FOR AAI & ROBOTICS APPLICATIONS

Abstract

Parser is a very crucial part of Natural Language Processing (NLP) through computational languages for syntactical analysis of sentences which includes identification of part of speech, phrases in terms of grammatical constituents, syntactic relations between phrases etc. A parser in machine translation analyzes sentences based on grammar formalism and builds a data structure corresponding to that grammar which indicates the syntactic correctness of a sentence. There are different formalisms available that can be used for analyzing sentences in natural language processing among which Tree Adjoining Grammar (TAG) formalism seems to be the most promising formalism for the analysis. A hybrid approach of parser known as Earley-type TAG parser gives better performance which can be further increased by using constraints in the operations of TAG formalism, reduction during the lexical analysis and applying heuristic rules during implementation.

The basic concept of TAG formalism i.e. the trees used for analyzing the sentences, the operations via which the trees are parsed, the recognizer algorithm, the use of TAG formalism for building a Earley-type parser and the constraints and heuristics to improve the performance of Earley-type TAG parser are elaborated in present paper.