Apparatus and method for generating finite state transducer for use in incremental parsing

A computer-readable recording medium storing a program for generating a finite state transducer for use in incremental parsing, the program comprising:

• a recursive transition network creating routine that creates a recursive transition network, there cursive transition network being a set of networks, each network representing a set of grammar rules based on a context-free grammar by states and arcs connecting the states, each arc having an input label and an output label, each network having a recursive structure where each transition labeled with a non-terminal symbol included in each of the networks is defined by another network;
• an arc replacement routine that replaces an arc having an input label representing a start symbol included in the finite state transducer in an initial state by a network corresponding to the input label of the arc in the recursive transition network and further recursively repeats an arc replacement operation for replacing each arc, which is newly created from a replaced network, by another network in the recursive transition network;
• and
• a priority calculating routine that calculates a derivation probability to derive a node of a parse tree corresponding to each of arcs whose input labels are non-terminal symbols in the finite state transducer based on statistical information regarding frequency of applying grammar rules and determines an arc replacement priority in terms of an obtained derivation probability;
• wherein the arc replacement routine continues applying the arc replacement operation to each arc included in the finite state transducer in descending order of the arc replacement priority until the finite state transducer reaches a predetermined size.

A method for generating a finite state transducer for use in incremental parsing comprising the steps of:

• creating a recursive transition network, the recursive transition network being a set of networks, each network representing a set of grammar rules based on a context-free grammar by states and arcs connecting the states, each arc having an input label and an output label, each network having a recursive structure where each transition labeled with a non-terminal symbol included in each of the networks is defined by another network;
• replacing an arc having an input label representing a start symbol included in the finite state transducer in an initial state by a network corresponding to the input label of the arc in the recursive transition network and further recursively repeating an arc replacement operation for replacing each arc, which is newly created from a replaced network, by another network in the recursive transition network;
• and
• calculating a derivation probability to derive a node of a parse tree corresponding to each of arcs whose input labels are non-terminal symbols in the finite state transducer based on statistical information regarding frequency of applying grammar rules and determines an arc replacement priority in terms of an obtained derivation probability;
• wherein, in the step of replacing an arc, continuing applying the arc replacement operation to each arc included in the finite state transducer in descending order of the arc replacement priority until the finite state transducer reaches a predetermined size.