Method for specifying equivalence of language grammars and automatically translating sentences in one language to sentences in another language in a computer environment

• US 7,529,658 B2
• Filed: 07/26/2002
• Issued: 05/05/2009
• Est. Priority Date: 07/26/2002
• Status: Expired due to Fees

• Current Assignee: Sankhya Technologies Private Limited
• Original Assignee: Sankhya Technologies Private Limited
• Inventors: Bulusu, Gopi Kumar, Gopala Subramanian, Seethalakshmi, Muthumula, Ranga Swami Reddy, Desikan, Murali
• Primary Examiner(s): Dorvil; Richemond
• Assistant Examiner(s): Colucci; Michael C
• Application Number:
  US10/522,328
• Publication Number:
  US 20050256699A1
• Time in Patent Office: 2,475 Days
• Field of Search: 704/9, 704/10, 717/143
• US Class Current: 704/200
• CPC Class Codes: G06F 40/55 Rule-based translation

Abstract

A method for specifying equivalence of language grammars and automatically translating sentences in one language to sentences in another language in a computer environment. The method uses a unified grammar specification of grammars of different languages in a single unified representation of all the individual grammars where equivalent production rules of each of the grammars are merged into a single unified production rule. This method can be used to represent the equivalence of computer languages like high level language, assembly language and machine language and for translating sentences in any of these languages to another language.

Claims

1. A method of automatic translation of sentences from a source language L_s selected from language L₁ to L_n to a target language L_t selected from languages L₁ to L_n, in which steps thereof are implemented by a computer, comprising the steps of:

(i) providing grammars G₁ to G_n of all the languages L₁ to L_n respectively, in which each grammar is unique to that particular language, and a text ‘

S’

in the source language L_s as inputs;

(ii) creating a unified grammar specification UG for the grammars G₁ to G_n, in which equivalent grammar production rules of each grammar G₁ to G_n are combined into a single unified production rule;

(iii) separating the input text ‘

S’

in the source language L_s into a list of tokens using a lexical analyser for the source language L_s;

(iv) setting a current non-terminal symbol to the start symbol of the unified grammar specification UG;

(v) obtaining a set of the grammar production rules from the united grammar specification UG, which contain the current non-terminal symbol as their target non-terminal;

(vi) for each unified grammar production rule P in the set of the grammar production rules obtained from the previous step (v), taking each symbol one by one from a list of terminal symbols and/or non-terminal symbols corresponding to the source language grammar G_s, determining whether it is a terminal symbol or a non-terminal symbol;

(vii) for each terminal symbol obtained from the previous step, which is equivalent to a corresponding symbol in the list of tokens T of the input text in the source language L_s, considering the next symbol in said list of terminal symbols and/or non-terminal symbols corresponding to the source language grammar G_s and for each non-terminal symbol E_s obtained from the previous step, repeating step (v) onwards with E_s as the current non-terminal symbol;

(viii) if all the symbols in the said list of terminal symbols and/or non-terminal symbols corresponding to the source language grammar G_s match with all the symbols in the list of tokens T of the input text in the source language L_s, obtaining a list of symbols t corresponding to the target language grammar G_t from the unified grammar production rule P and for those symbols which do not match, repeating step (vi) onwards for a next unified grammar production rule P defined for the non-terminal symbol ‘

E’

;

(ix) taking each symbol one by one, from the list of symbols t corresponding to the target grammar G_t and determining whether it is a terminal symbol or a non-terminal symbol;

(x) for each terminal symbol obtained from the previous step outputting the symbol, and considering the next symbol and for each non-terminal obtained from the previous step, obtaining another unified grammar production rule P corresponding to that non-terminal symbol and repeating the previous step with the new unified grammar production rule, till all the symbols in the list of symbols t corresponding to the target language grammar G_t are exhausted.

2. The method as claimed in claim 1, wherein the unified grammar specification UG, for the grammars G₁ to G_n of languages L₁ to L_n, is created by the steps of:

(i) for every production rule P of the grammars G₁ to G_n, of the languages L₁ to L_n, defining a unified production rule P₁ in the unified grammar specification UG having the target non-terminal symbol of the production rule P as its target non-terminal symbol; and

(ii) for each grammar G₁ to G_n creating a list of terminal symbols and/or non-terminal symbols in the said production rule P₁ and adding each and every symbol in the list of terminal symbols and/or non-terminal symbols that are represented by the target non-terminal symbol in the production rule P to the said unified production rule P₁ and repeating previous step for the next production rule of the grammars G₁ to G_n.

3. An apparatus for automatic translation of sentences from a source language L_s selected from language L₁ to L_n to a target language L_t selected from languages L₁ to L_n comprising:

(i) means for providing grammars G₁ to G_n of all the languages L₁ to L_n respectively, in which each grammar is unique to that particular language, and a text ‘

S’

in the source language L_s as inputs;

(ii) means for creating a unified grammar specification UG for the grammars G₁ to G_n, in which equivalent grammar production rules of each grammar G₁ to G_n are combined into a single unified production rule;

(iii) means for separating the input text ‘

S’

in the source language L_s into a list of tokens using a lexical analyser for the source language L_s;

(iv) means for setting a current non-terminal symbol to the start symbol of the unified grammar specification UG;

(v) grammar production rule obtaining means for obtaining a set of the grammar production rules from the united grammar specification UG, which contain the current non-terminal symbol as their target non-terminal;

(vi) for each unified grammar production rule P in the set of the grammar production rules obtained from the grammar production rule obtaining means, symbol taking means for taking each symbol one by one from a list of terminal symbols and/or non-terminal symbols corresponding to the source language grammar G_s, determining whether it is a terminal symbol or a non-terminal symbol;

(vii) for each terminal symbol obtained from the symbol taking means, which is equivalent to a corresponding symbol in the list of tokens T of the input text in the source language L_s, means for considering the next symbol in said list of terminal symbols and/or non-terminal symbols corresponding to the source language grammar G_s and for each non-terminal symbol E_s obtained from the symbol taking means, repeating obtaining a set of the grammar production rules from the united grammar specification UG by the grammar production rule obtaining means, onwards with E_s as the current non-terminal symbol;

(viii) if all the symbols in the said list of terminal symbols and/or non-terminal symbols corresponding to the source language grammar G_s match with all the symbols in the list of tokens T of the input text in the source language L_s, means for obtaining a list of symbols t corresponding to the target language grammar G_t from the unified grammar production rule P and for those symbols which do not match,

repeating taking each symbol one by one from a list of terminal symbols and/or non-terminal symbols corresponding to the source language grammar G_s by the symbol taking means, onwards for a next unified grammar production rule P defined for the non-terminal symbol ‘

E’

;

(ix) determining means for taking each symbol one by one, from the list of symbols t corresponding to the target grammar G_t and determining whether it is a terminal symbol or a non-terminal symbol;

(x) for each terminal symbol obtained from the determining means, means for outputting the symbol, and considering the next symbol and for each non-terminal obtained from the determining means, means for obtaining another unified grammar production rule P corresponding to that non-terminal symbol and repeating the determining means with the new unified grammar production rule, till all the symbols in the list of symbols t corresponding to the target language grammar G_t are exhausted.

4. A computer readable medium for automatic translation of sentences from a source language L_s selected from language L₁ to L_n to a target language L_t selected from languages L₁ to L_n, including program instructions executable by a computer system for:

(i) providing grammars G₁ to G_n of all the languages L₁ to L_n respectively, in which each grammar is unique to that particular language, and a text ‘

S’

in the source language L_s as inputs;

(ii) creating a unified grammar specification UG for the grammars G₁ to G_n, in which equivalent grammar production rules of each grammar G₁ to G_n are combined into a single unified production rule;

(iii) separating the input text ‘

S’

in the source language L_s into a list of tokens using a lexical analyser for the source language L_s;

(iv) setting a current non-terminal symbol to the start symbol of the unified grammar specification UG;

(v) obtaining a set of the grammar production rules from the united grammar specification UG, which contain the current non-terminal symbol as their target non-terminal;

(vi) for each unified grammar production rule P in the set of the grammar production rules obtained from the previous step (v), taking each symbol one by one from a list of terminal symbols and/or non-terminal symbols corresponding to the source language grammar G_s, determining whether it is a terminal symbol or a non-terminal symbol;

(vii) for each terminal symbol obtained from the previous step, which is equivalent to a corresponding symbol in the list of tokens T of the input text in the source language L_s, considering the next symbol in said list of terminal symbols and/or non-terminal symbols corresponding to the source language grammar G_s and for each non-terminal symbol E_s obtained from the previous step, repeating step (v) onwards with E_s as the current non-terminal symbol;

(viii) if all the symbols in the said list of terminal symbols and/or non-terminal symbols corresponding to the source language grammar G_s match with all the symbols in the list of tokens T of the input text in the source language L_s, obtaining a list of symbols t corresponding to the target language grammar G_t from the unified grammar production rule P and for those symbols which do not match, repeating step (vi) onwards for a next unified grammar production rule P defined for the non-terminal symbol ‘

E’

;

(ix) taking each symbol one by one, from the list of symbols t corresponding to the target grammar G_t and determining whether it is a terminal symbol or a non-terminal symbol;

(x) for each terminal symbol obtained from the previous step outputting the symbol, and considering the next symbol and for each non-terminal obtained from the previous step, obtaining another unified grammar production rule P corresponding to that non-terminal symbol and repeating the previous step with the new unified grammar production rule, till all the symbols in the list of symbols t corresponding to the target language grammar G_t are exhausted.