Automatic code generation via natural language processing

• US 7,765,097 B1
• Filed: 03/20/2006
• Issued: 07/27/2010
• Est. Priority Date: 03/20/2006
• Status: Active Grant

• Current Assignee: Intuit, Inc.
• Original Assignee: Intuit, Inc.
• Inventors: Yu, Jay Jie-Bing, Fleming, Adam M.
• Primary Examiner(s): Smits; Talivaldis I
• Assistant Examiner(s): Borsetti; Greg A
• Application Number:
  US11/385,319
• Time in Patent Office: 1,590 Days
• Field of Search: 704/9, 717/144
• US Class Current: 704/9
• CPC Class Codes: G06F 40/174 Form filling; Merging
• CPC Class Codes: G06F 40/211 Syntactic parsing, e.g. based on context-free grammar [CFG] or unification grammars
• CPC Class Codes: G06F 8/30 Creation or generation of source code

Abstract

A method for automatic code generation that includes obtaining a parse tree, wherein the parse tree represents at least one instruction and wherein the instruction is in a natural language, and wherein the at least one instruction is free-form, determining a plurality of sentence subparts from the parse tree, creating at least one instantiated concept for each of the plurality of sentence subparts, inserting the instantiated concept in an instantiated concept map, traversing the instantiated concept map, wherein traversing the instantiated concept map includes for each instantiated concept in the instantiated concept map obtaining a code output rule according to the instantiated concept, and outputting code according to the code output rule be completed upon finalization of claims.

Claims

1. A method for automatic code generation comprising:

obtaining a parse tree, wherein the parse tree represents at least one instruction and wherein the instruction is in a natural language, and wherein the at least one instruction is free-form;

identifying a functional word in the parse tree;

identifying a regular expression matching the functional word, wherein the regular expression matches the functional word when the regular expression comprises at least one selected from a group consisting of a concept with a matching name as the functional word and a concept with a matching type as the functional word, and wherein the regular expression specifies a sentence subpart corresponding to the functional word;

identifying the sentence subpart from the parse tree according to the regular expression and based on an identifier of the sentence subpart at a same distance from the root as an identifier of the functional word;

creating, using a processor, a first instantiated concept for the sentence subpart by;

obtaining a first concept based on the first concept mapping to a first word in the sentence subpart, wherein the first concept assigns a type to the first word, and

creating the first instantiated concept from the first concept;

inserting the first instantiated concept in an instantiated concept map, wherein the instantiated concept map defines relationships between instantiated concepts in the instantiated concept map;

identifying, using a processor, a second instantiated concept for the sentence subpart by;

obtaining a second concept based on the second concept mapping to a second word in the sentence subpart, wherein the second concept is obtained based on the second concept comprising a parameter identifying the first concept, and wherein the second concept maps to a plurality of heterogeneous words, and

determining that the second instantiated concept representing the second concept is already located in the instantiated concept map;

inserting, in the second instantiated concept already located in the instantiated concept map, a link to the first instantiated concept based on the second concept comprising the parameter identifying the first concept, wherein inserting the link creates at least two paths between at least two instantiated concepts in the instantiated concept map;

traversing the instantiated concept map,

wherein traversing the instantiated concept map comprises for each instantiated concept in the instantiated concept map;

obtaining a code output rule according to the instantiated concept; and

outputting code to memory according to the code output rule.

2. The method of claim 1, further comprising:

normalizing the parse tree to identify the functional word.

3. The method of claim 2, wherein normalizing the parse tree comprises removing at least one filler word from the parse tree.

4. The method of claim 1, wherein obtaining the parse tree comprises using the Stanford natural language parser.

5. The method of claim 1, wherein the first concept comprises a property and a name.

6. The method of claim 5, wherein the property denotes an inheritance relationship.

7. A method for generating executable code to process a form comprising:

obtaining the form, wherein the form comprises a plurality of fields;

obtaining an instruction for each field in the plurality of fields, wherein the instruction is written in a natural language, and wherein the instruction is free-form; and

generating, using a processor, code for the instruction for each field in the plurality of fields to obtain generated code, wherein the generated code processes the form, wherein, for the instruction in at least one field of the plurality of fields, generating code comprises performing;

obtaining a parse tree representing the instruction;

identifying a functional word from the parse tree;

identifying a regular expression matching the functional word, wherein the regular expression matches the functional word when the regular expression comprises at least one selected from a group consisting of a concept with a matching name as the functional word and a concept with a matching type as the functional word, and wherein the regular expression specifies a sentence subpart corresponding to the functional word;

identifying the sentence subpart from the parse tree according to the regular expression and based on an identifier of the sentence subpart at a same distance from the root as an identifier of the functional word;

creating a first instantiated concept for the sentence subpart by;

obtaining a first concept based on the first concept mapping to a first word in the sentence subpart, wherein the first concept assigns a type to the first word, and

creating the first instantiated concept from the first concept;

inserting the first instantiated concept in an instantiated concept map, wherein the instantiated concept map defines relationships between instantiated concepts in the instantiated concept map;

identifying, a second instantiated concept for the sentence subpart by;

obtaining a second concept based on the second concept mapping to a second word in the sentence subpart, wherein the second concept is obtained based on the second concept comprising a parameter identifying the first concept, and wherein the second concept maps to a plurality of heterogeneous words, and

determining that the second instantiated concept representing the second concept is already located in the instantiated concept map;

inserting, in the second instantiated concept already located in the instantiated concept map, a link to the first instantiated concept based on the second concept comprising the parameter identifying the first concept, wherein inserting the link creates at least two paths between at least two instantiated concepts in the instantiate concept map;

traversing the instantiated concept map,

wherein traversing the instantiated concept map comprises for each instantiated concept in the instantiated concept map;

obtaining a code output rule according to the instantiated concept; and

outputting code according to the code output rule.

8. A system for automatic code generation comprising:

a processor;

a pattern matcher, executing on the processor, and configured to;

obtain a parse tree, wherein the parse tree represents at least one instruction and wherein the instruction is in a natural language;

identify a functional word in the parse tree;

identify a regular expression matching the functional word, wherein the regular expression matches the functional word when the regular expression comprises at least one selected from a group consisting of a concept with a matching name as the functional word and a concept with a matching type as the functional word, and wherein the regular expression specifies a sentence subpart corresponding to the functional word;

identify the sentence subpart from the parse tree according to the regular expression and based on an identifier of the sentence subpart at a same distance from the root as an identifier of the functional word;

create a first instantiated concept for the sentence subpart by;

obtaining a first concept based on the first concept mapping to a first word in the sentence subpart, wherein the first concept assigns a type to the first word, and

creating the first instantiated concept from the first concept;

inserting the first instantiated concept in an instantiated concept map, wherein the instantiated concept map defines relationships between instantiated concepts in the instantiated concept map;

identifying a second instantiated concept for the sentence subpart by;

obtaining a second concept based on the second concept mapping to a second word in the sentence subpart, wherein the second concept is obtained based on the second concept comprising a parameter identifying the first concept, and wherein the second concept maps to a plurality of heterogeneous words, and

determining that the second instantiated concept representing the second concept is already located in the instantiated concept map; and

insert, in the second instantiated concept already located in the instantiated concept map, a link to the first instantiated concept based on the second concept comprising the parameter identifying the first concept, wherein inserting the link creates at least two paths between at least two instantiated concepts in the instantiated concept map; and

a code generator, executing on the processor, and configured to;

traverse the instantiated concept map, wherein traversing the instantiated concept map comprises;

for each instantiated concept in the instantiated concept map obtaining a code output rule according to the instantiated concept; and

output code according to the code output rule.

9. The system of claim 8, further comprising:

a normalizer, executing on the processor, and configured to normalize the parse tree to identify the functional word.

10. The system of claim 9, wherein normalizing the parse tree comprises removing at least one filler word from the parse tree.

11. The system of claim 8, wherein the first concept comprises a property and a name.

12. The system of claim 11, wherein the property denotes an inheritance relationship.

13. A computer readable medium comprising computer program code stored therein for causing a computer system accessing the computer readable medium to:

obtain a parse tree, wherein the parse tree represents at least one instruction and wherein the instruction is in a natural language, and wherein the instruction is free-form;

identify a functional word in the parse tree;

identify a regular expression matching the functional word, wherein the regular expression matches the functional word when the regular expression comprises at least one selected from a group consisting of a concept with a matching name as the functional word and a concept with a matching type as the functional word, and wherein the regular expression specifies a sentence subpart corresponding to the functional word;

identify a sentence subpart from the parse tree according to the regular expression and based on an identifier of the sentence subpart at a same distance from the root as an identifier of the functional word;

create a first instantiated concept for the sentence subpart by;

obtaining a first concept based on the first concept mapping to a first word in the sentence subpart, wherein the first concept assigns a type to the first word, and

creating the first instantiated concept from the first concept;

insert the first instantiated concept in an instantiated concept map, wherein the instantiated concept map defines relationships between instantiated concepts in the instantiated concept map;

identify a second instantiated concept for the sentence subpart by;

obtaining a second concept based on the second concept mapping to a second word in the sentence subpart, wherein the second concept is obtained based on the second concept comprising a parameter identifying the first concept, and wherein the second concept maps to a plurality of heterogeneous words, and

determining that the second instantiated concept representing the second concept is already located in the instantiated concept map;

insert, in the second instantiated concept already located in the instantiated concept map, a link to the first instantiated concept based on the second concept comprising the parameter identifying the first concept, wherein inserting the link creates at least two paths between instantiated concepts in the instantiated concept map;

traverse the instantiated concept map,

wherein traversing the instantiated concept map comprises for each instantiated concept in the instantiated concept map;

obtaining a code output rule according to the instantiated concept; and

output code according to the code output rule.