(12) A Study on Parallel Robust Parsing based on GLR Algorithm

In this research, we propose a parallel robust parser based on generalized LR algorithm and implement the parser as a basic natural language processing system on PIM and general-propose computers. The proposed system can parse not only a grammatical sentence but also an ill-formed sentence which is defined as a sentence where one or more terminals(words) and/or nonterminals(phrases) are deleted/added/substituted. In the process of parsing an ill-formed sentence, there is a problem caused by high ambiguity of locations and types of grammatical errors in the sentences. To deal with this problem, we develop a scoring mechanism to rank the candidates (parsing trees) of the parsing result. At the present time, the scoring mechanism is performed based on syntactical information, such as types and locations of errors, and its effectiveness is shown by some preliminary experiments. Moreover, we also propose a method to parallelize our parsing algorithm to reduce the computational cost. There are two variants of the proposed parallel parser based on load balancing applied: random dynamic and on-demand dynamic load balancing. A user of the system can define his own error weight to optimize the ranking process and also can select load balancing to improve the parsing time. Our parsers are implemented by SICSTUS Prolog and KL1 languages and executed on both PIM and general-purpose computers where Prolog is installed.