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

• US 20050256699A1
• Filed: 01/25/2005
• Published: 11/17/2005
• Est. Priority Date: 07/26/2002
• Status: Active Grant

• Current Assignee: Sankhya Technologies Private Limited
• Original Assignee: Sankhya Technologies Private Limited
• Inventors: Muthhumula, Ranga Swami Reddy, Bulusu, Gopi Kumar, Desikan, Murali, Gopala Subramanian, Seethalakshmi
• Granted Patent: US 7,529,658 B2
• Time in Patent Office: Days
• US Class Current: 704/2
• 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 comprising the steps of:

(i) providing grammars G₁ to G_n of all the languages L₁ to L_n respectively 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;

(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 non-terminal symbol ‘

E’

to the start symbol of the unified grammar specification UG;

.

(v) obtaining a set of grammar production rules P_e which define the rules to reduce a string of terminal symbols and/or non-terminal symbols to the target non-terminal symbol E from the unified grammar specification UG;

(vi) for each unified grammar production rule P in the set of grammar production rules P_e 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 obtained from the previous step which refers to another non-terminal symbol E_s, of the unified grammar specification UG, repeating step (v) onwards with the new non-terminal symbol E_s;

(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 the 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 outputing 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.