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

Description of equivalent WO 2004012028 A2

0001METHOD FOR SPECIFYING EQUIVALENCE OF LANGUAGE GRAMMARS AND AUTOMATICALLY TRANSLATING

0002SENTENCES IN ONE LANGUAGE TO SENTENCES IN ANOTHER LANGUAGE IN A COMPUTER ENVIRONMENT

0003Field of Invention :

0004The invention relates to a method for specifying equivalence of language

0005grammars and the automatic translation of sentences in one language to sentences

0006in another language in a computer environment.

0007Background of the Invention :

0008A language is basically a set of sentences that can be formed by following

0009certain rules. The basic building block of any language is its alphabet. There are

0010numerous languages existing today in the same way. The sentences are a

0011collection of words that are formed from the letters of the alphabet. There are

0012certain rules to be followed when putting these words together. These rules are

0013called grammar of the language and are unique for each and every language.

0014These rules detennine the valid sentences of the language. Thus one can define

0015grammar as a concise specification using which, it is possible to generate all the

0016valid sentences of the language. A grammar specifies the syntax or stmcture of a language; irrespective of whether it is a language such as English or programming

0017language such as 'C or assembly language.

0018Very often, it is required to convert sentences in one language to equivalent

0019sentences in another language. For example from English to French or from a

0020programming language to assembly language. To perform such tasks the language

0021grammars have to be specified and the source language statements should be

0022validated and translated to sentences in the target language.

0023A method used in the prior art for translating a language to another language used is carried out in the following manner.

0024Define the source language grammar. Parse ttie sentences and convert them

0025to a predefined intermediate format and translate finally, the intermediate format

0026to the target language.

0027The disadvantages in performing a translation by the above mentioned method are the following.

0028(i) This method will not allow equivalence of the source language

0029grammar and target language grammar to be specified. Thus there is no real correspondence between source language grammar and

0030target language grammar,

0031(ii) Normally this method allows the translation from one source

0032language to one target language only. Mapping to multiple target

0033languages will not be possible,

0034(iii) Mapping from a source language to a target language is predefined

0035and thus supporting translations to new languages will be difficult.

0036Object of the Invention :

0037Bearing in mind the problems and detriments of the prior art, the object of

0038ttie present invention is to provide a method to automatically translate sentences

0039from one language to another, overcoming the above mentioned deficiencies.

0040Thus one of the object of the present invention is to be able to specify the

0041equivalence of the source language grammar and target language grammar.

0042Another object of the present invention is to allow mapping to multiple

0043target languages. Method according to the invention should have no restrictions to

0044translating a source language to more than one target languages. Description of the invention :

0045The invention provides a method for representing equivalence of language

0046grammars and for the automatic translation of sentences in one language to

0047sentences in another language in a computer environment.

0048Let Li toL„ be n number of languages and Gi to G„ represent the respective grammars for the languages Li to L„. Each grammar is unique to that particular language. Each grammar Gi to G_n consists of a set of terminal symbols, a set of nonterminal symbols, a unique start symbol which is a nonterminal symbol and a set of production rales. These production rules are the main aspects of the grammar. Production rule define the rules to reduce a string of terminal and/or nonterminal symbols to a target nonterminal symbol.

0049In a grammar, there is at least one production rule that has the start symbol as its target nonterminal symbol. A sentence of a language may be defined as any string derived from the start symbol composed of only terminal symbols.

0050In the method according to the invention, a unified grammar specification is

0051created for the grammars Gi to G_n of all the languages Li to L_n respectively. Then

0052the text in the source language is separated into a list of tokens using conventional

0053lexical analyser for the source language. A nonterminal symbol is set to the start

0054symbol of the unified grammar specification. Then a set of grammar production rules is obtained for the said non-terminal symbol form the unified grammar

0055specifications. Take each symbol one by one from a list of terminal symbols

0056and/or nonterminal symbols corresponding to the source language grammar,

0057determine whether it is a terminal symbol or a nonterminal symbol. For each

0058terminal symbol obtained which is equivalent to a corresponding symbol in the list

0059of tokens form the source language, consider the next symbol in the list of said

0060terminal symbols and/or nonterminal symbols. For each nonterminal symbol

0061obtained which refers to another non-terminal symbol obtain a set of grammar

0062production rules for that nonterminal symbol and repeat the previous steps.

0063If all the symbols in the said list of terminal symbols and/or non-terminal

0064symbols corresponding to the source language grammar match with symbols in the

0065said list of tokens of the input text obtain a list of symbols corresponding to the

0066target language grammar from the said unified grammar production rule. For

0067those symbols in the said list of terminal symbols and/or non-terminal symbols

0068which do not match with symbols in the said list of tokens, repeat the earlier steps

0069considering the next production rule from the set of production rules obtained for

0070the non-terminal.

0071Taking each symbol one by one from the said list of symbols corresponding

0072to the target language grammar, determine whether it is a terminal symbol or non- terminal symbol. Each terminal symbol obtained are provided as output. For each

0073nonterminal symbol, obtain another unified grammar production rule

0074corresponding to that nonteπninal symbol and repeat this step till all the symbols

0075in the said list of symbols corresponding to the target language grammar are

0076exhausted.

BRIEF DESCRIPTION OF DRAWINGS :

0078Figure I shows a system with which the method according to the invention can be

0079implemented.

0080Figure II shows the flow chart of the method according to the invention.

0081Figure III shows the steps taken to create the unified grammar specification in the

0082second step shown in figure II.

0083Figure IV shows the steps taken to determine if all symbols in a unified grammar

0084production rule match with the symbols in the token list 'T' in the sixth step of

0085figure II and the seventh step of figure V.

0086Figure V shows the steps taken to determine if a symbol from a unified grammar

0087production rule matches with a symbol from the token list 'T' in the fourth step of

0088figure IV.

0089Figure VI shows the steps taken to obtain the sentence 'I from a unified

0090grammar production rule ' in the eight step of figure II and in the seventh step

0091of figure VI. DESCRIPTION WITH REFERENCE TO THE DRAWINGS :

0092The method according to the invention can be implemented by using a

0093processing device (1) such as a microprocessor, a memory (2) and a user input

0094device (3) connected to said processor (1). The user-input device may be a

0095keyboard or any other device which can provide information signals to the

0096processor. The memory typically consists of a RAM and a ROM. According to

0097the invention, the method of automatic translation of a sentences from a source

0098language L_s selected from a number of languages Lj to L_n to a target language L_t

0099selected from the number of languages Li to L„ comprises the following steps.

0100Step 1 : Grammars Gi to G„ of all the languages Li to L_n respectively and a text

0101^SS' in the source language Lg are provided as inputs.

0102Step 2 : A unified grammar specification UG is created for the grammars G_x to

0103G_n.

0104Step 3 : The input text 'S' in the source language L_s is separated into a list of

0105tokens T using a lexical analyser for the source language Lg.

0106Step 4 : A nonterminal symbol Ε' is set to the start symbol of the unified

0107grammar specification UG.

0108Step 5 : A set of grammar production rules P_e is obtained by selecting the

0109production rules which contain 'E' as their target non-terminal symbol from the

0110unified grammar specification UG. Step 6 : For each unified grammar production rule P in the set of grammar

0111production rules P_e taking each symbol one by one from a list of terminal symbols

0112and/or non-terminal symbols corresponding to the source language grammar G_s,

0113determine whether it is a terminal symbol or a non-terminal symbol.

0114Step 7 : For each terminal symbol obtained from the previous step which is

0115equivalent to a corresponding symbol in the list of tokens T of the input text in the

0116source language L_s, consider the next symbol in said list of terminal symbols

0117and or nonterminal symbols corresponding to the source language grammar G_s and

0118for each nontemiinal symbol obtained fiom the previous step which refers to

0119another nonterminal symbol E_g, of the unified grammar specification UG, repeat

0120step (5) onwards with the new nonterminal E_s.

0121Step 8 : If all the symbols in the said list of terminal symbols and/or non-terminal

0122symbols corresponding to the source language grammar G_s match with all the

0123symbols in the list of tokens T of the input text in the source language L_s, obtain a

0124list of symbols t corresponding to the target language grammar G_t from the

0125unified grammar production rule P and for those symbols which do not match,

0126repeat step 6 onwards for the next unified grammar production rule P defined for

0127the nonterminal symbol Ε\

0128Step 9 : Take each symbol one by one, from the list of symbols t corresponding

0129to the target grammar G_t and determine whether it is a terminal symbol or a non¬

0130terminal symbol. Step 10 : For each terminal symbol obtained from the previous step output the

0131symbol, and consider the next symbol and for each nonterøiinal symbol obtained

0132from the previous step, obtain another unified grammar production rule P

0133corresponding to that nonterminal symbol and repeat the previous step with the

0134new unified grammar production rule, till all the symbols in the list of symbols t

0135corresponding to the target language grammar G_t are exhausted.

0136The unified grammar specification UG, for the grammars Gi to G„ of

0137languages Li to L„, is created by defining a unified production rule ?ι in the

0138unified grammar specification UG having the target nonterminal symbol of the

0139production rule P as its target nonterminal symbol for every production rule P of

0140the grammars Gi to G_n and creating a list of terminal symbols and or nonterminal

0141symbols in the said production rule ?ι for each grammar G_% to G_π; adding each and

0142every symbol in the list of terminal and/or nonterminal symbols that are

0143represented by the target nonterminal symbol in the production rule P to the said

0144unified production rule Pi and repeating previous steps for the next production

0145rule of the grammars Gi to G_n.

0146The method according to the invention can be used to represent the

0147equivalence of multiple language grammars and for translating sentences of one

0148language to another.