Conceptio › Archive › Google Patents

Google Patentsopen access

Automated program synthesis from natural language for domain specific computing … — Virginia Tech Intellectual Properties, Inc. (US10843080B2)

Virginia Tech Intellectual Properties, Inc. · Google Patents

Google Patents · Patents · License: Open Access

patent, google patents, intellectual property, US10843080B2, Virginia Tech Intellectual Properties, Inc., Michael S. Hsiao, en, 2020

ABSTRACT

Abstract

Disclosed are various embodiments for automated program synthesis from a natural language for domain specific computing applications. In one embodiment, a natural language processor may be configured to parse words from a sentence of text formed in a natural language, such as English, following a grammatical structure for the natural language. The words may be compared to a dictionary to identify a token. The text formed in the natural language may be converted to an intermediate format of programming code in a programming language, such as C, where the intermediate format includes the token. The token may invoke a function or a routine of a library written in the programming language. The intermediate format may be compiled into executable program code to generate an application, such as a video game, for execution.

Description

CROSS-REFERENCE TO RELATED APPLICATION

This application claims the benefit of and priority to U.S. Provisional Patent Application No. 62/299,047 filed on Feb. 24, 2016 entitled âAUTOMATED PROGRAM SYNTHESIS FROM NATURAL LANGUAGE FOR COMPUTER GAMES,â the content of which being incorporated by reference in its entirety herein.

BACKGROUND

Natural Language Programming (NLPr) refers to a type of programming performed in a human's naturally spoken or written language (e.g., English, Spanish, or other natural language) that can be analyzed and converted to machine executable code. For instance, a sentence or a paragraph written in a natural language (as opposed to a formal programming language) may be parsed and understood as a computational program. If NLPr is successful, the impact can be far-reaching. Not only can it significantly increase productivity in software development, it can provide enormous innovations in software design, execution, and understanding. In terms of computing education, NLPr can help eliminate the inherent fear and frustration of learning a conventional computer programming language. Nevertheless, the ambiguity and nuances of natural language can make NLPr extremely challenging.

DESCRIPTION OF TECHNOLOGY AREA

This disclosure relates to programming code compilation, namely converting natural language text in a spoken or written language into machine executable code for particular domains of applications, such as video games.

BRIEF DESCRIPTION OF THE DRAWINGS

Many aspects of the present disclosure can be better understood with reference to the following drawings. The components in the drawings are not necessarily to scale, with emphasis instead being placed upon clearly illustrating the principles of the disclosure. Moreover, in the drawings, like reference numerals designate corresponding parts throughout the several views.

FIG. 1 is a schematic diagram illustrating natural language text compiled into an executable video game according to various embodiments of the present disclosure.

FIG. 2 is a schematic diagram illustrating an order of compilation according to various embodiments of the present disclosure.

FIG. 3 is a drawing of a networked environment according to various embodiments of the present disclosure.

FIG. 4 is a drawing of a client device having a natural language compiler according to various embodiments of the present disclosure.

FIG. 5 is a schematic diagram illustrating a process of generating a language model for a domain specific application according to various embodiments of the present disclosure.

FIGS. 6 and 7 are flowcharts illustrating example functionality implemented as portions of an application executing in a computing environment or a client device according to various embodiments of the present disclosure.

FIGS. 8, 9, and 10 are examples of pseudocode describing operation of functions or routines in a library according to various embodiments of the present disclosure.

FIGS. 11A and 11B are pictorial diagrams of example user interfaces rendered by a client device in the networked environment of FIG. 1 according to various embodiments of the present disclosure.

FIG. 12 is a flowchart illustrating one example of functionality implemented as portions of an application executing in a computing environment or a client device according to various embodiments of the present disclosure.

FIG. 13 is a schematic block diagram that provides one example illustration of a computing environment employed in the networked environment of FIG. 1 according to various embodiments of the present disclosure.

DETAILED DESCRIPTION

The present disclosure relates to automated program synthesis from a natural language for domain specific computing applications. As noted above, natural languages, such as English, have an ambiguous nature and contain many nuances for machine interpretation. Accordingly, various embodiments are disclosed for programmatically compiling natural language text to executable code for particular domains of applications, such as video games. In one embodiment, a user may write a program as a story told in English or other natural language, which is ultimately translated to executable code using token identification; synonym, verb, and pronoun resolution; fuzzy grammar matching; and code generation. Predicates, action verbs, adjectives, and other semantics relevant to a domain may be first obtained to form a dictionary for the application domain space. However, in various embodiments, new terms may be learned automatically. The semantics of each sentence may also be bound to a particular application domain.

One embodiment may include employing a computing device to identify words from at least one sentence of text formed in a natural language following a grammatical structure for the natural language. The words may be compared to a dictionary to identify a token stored in association with the at least one of the words. The text formed in the natural language may be converted to an intermediate format of programming code in a predetermined programming language, where the intermediate format includes the token. In some embodiments, the token is a word or predefined variable that invokes a function or a routine of a library written in the programming language. The intermediate format may be compiled into executable program code to generate an application, such as a video game, for execution.

In various embodiments, for a word in a sentence not having a corresponding entry in the dictionary, a meaning of the word may be determined based on a contextual analysis of the sentence, and the word may be stored in the dictionary or a temporary dictionary separate from the dictionary in association with the derived meaning. The contextual analysis may include, for example, analyzing at least one antecedent clause of the sentence and analyzing at least one consequent clause of a subsequent sentence or preceding sentence. Fuzzy matching methodologies may also be employed. In further embodiments, the computing device may generate a certainty metric for the sentence that indicates a degree to which the sentence was understood programmatically. If the certainty metric satisfies (e.g., falls below) an error threshold, an error message may be generated.

In the following discussion, a general description of a system for automated program synthesis from natural language text and its components is provided, followed by a discussion of the operation of the same.

Referring first to FIG. 1 , a schematic diagram 100 is shown that includes natural language text 103 or, in other words, text formed in a natural language, such as English. For instance, a user may write or verbally dictate a story using voice-to-text software in English or other language to create a computer application using grammatical rules for a particular language. As may be appreciated, a user may be more comfortable and familiar with grammatical requirements for forming a proper sentence in their native (or non-native) language, as opposed to memorizing rules or required constructs for a potentially complicated programming language, such as C or C++.

As a non-limiting example, if a developer wishes to write a video game involving a rabbit, fox, and carrots, the developer may write an amount of natural language text 103 that includes:

Ten carrots are scattered all over the field. There are two foxes and one rabbit. You control the rabbit with keyboard. When the rabbit encounters a carrot, the carrot is eaten by the rabbit. However, the rabbit must avoid the wandering foxes. When a fox sees the rabbit, it starts chasing the rabbit. When the fox catches the rabbit, the game is over.

The natural language text 103 shown in FIG. 1 includes both unconditional and conditional sentences. For example, âThe fox wanders aroundâ is an example of an unconditional sentence. On the other hand, a conditional sentence includes âWhen a fox catches a rabbit, the rabbit dies.â The sentence is conditional as it depends on the outcome of the predicate (e.g., whether the fox catches the rabbit). The grammar for all possible sentences involving the actions and predicates may be derived as a set of grammatical rules. Alternatively, semantics of the natural language text 103 may be obtained using a classification system. In either case, an intermediate format for each sentence may be generated. The intermediate format may include code generated in a predetermined programming language. For example, the sentence that states, âThe fox wanders around,â may be converted to âwander(fox),â where âwanderâ is a function in a library and âfoxâ is a parameter of the function. Similarly, the sentence that states, âWhen a fox catches a rabbit, the rabbit dies,â may be converted to âif catch(fox, rabbit), die(rabbit),â where âcatchâ and âdieâ are functions in a library and âfoxâ and ârabbitâ are parameters of the respective functions.

Ultimately, the natural language text 103 is converted to one or more intermediate programming languages, which may be ultimately compiled into machine-executable code. In one example, the natural language text 103 shown in the non-limiting example of FIG. 1 is used to generate a video game 106 , where a player may use an input device, such as a keyboard, mouse, joystick, or other suitable input device, to control a rabbit 109 . Using the input device, a user may navigate the rabbit 109 across a field to collect carrots 112 a . . . 112 j (collectively âcarrots 112 â) while trying to avoid foxes 115 a . . . 115 b (collectively âfoxes 115 â). As specified in the natural language text 103 , if the fox catches the rabbit, the game will end. The video game 106 or other type of application may be rendered in a display, such as a computer monitor, television, tablet display, smartphone display, or other appropriate display, as will be described.

Turning now to FIG. 2 , a schematic diagram 200 is shown illustrating an order of compilation for a computer application according to various embodiments of the present disclosure. Starting at the top, natural language text 103 , or text written in a natural language (e.g., English, Spanish, French, Italian, Japanese, Mandarin or German), is generated by a developer or other user. As discussed above, the natural language text 103 may follow grammatical rules for the given language. A compiler may parse the natural language text 103 and convert the natural language text 103 into one or more intermediate formats. In one embodiment, the natural language text 103 is converted from its natural language to a scripting language, such as Perl, Python, Shell, or Java, or other similar scripting language. The scripting language may then be converted into a high- or middle-level programming language, such as C, C++, Objective C, or other language. In another embodiment, the natural language text 103 is converted directly into a high- or middle-level programming language, such as C, C++, Objective C, or other language.

The compilation may proceed, for example, by continuously compiling the program from the intermediate format to an assembly language, such as IntelÂ® x86, which is then compiled into hexadecimal representations of binary code. Ultimately, the natural language text 103 is compiled or otherwise converted to binary code or other code capable of interpretation by hardware, such as a processor. As shown in FIG. 2 , programming complexity is shown where natural language text 103 is the easiest for a human to understand while binary code is the most difficult.

With reference to FIG. 3 , shown is a networked environment 300 according to various embodiments. The networked environment 300 includes a computing environment 303 and a client device 306 , which are in data communication with each other via a <figure-callout id="309" label="network" filenames="US10843080-20201124-

CROSS-REFERENCE TO RELATED APPLICATION

BACKGROUND

DESCRIPTION OF TECHNOLOGY AREA

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 is a schematic diagram illustrating natural language text compiled into an executable video game according to various embodiments of the present disclosure.

FIG. 2 is a schematic diagram illustrating an order of compilation according to various embodiments of the present disclosure.

FIG. 3 is a drawing of a networked environment according to various embodiments of the present disclosure.

FIG. 4 is a drawing of a client device having a natural language compiler according to various embodiments of the present disclosure.

FIG. 5 is a schematic diagram illustrating a process of generating a language model for a domain specific application according to various embodiments of the present disclosure.

FIGS. 8, 9, and 10 are examples of pseudocode describing operation of functions or routines in a library according to various embodiments of the present disclosure.

FIGS. 11A and 11B are pictorial diagrams of example user interfaces rendered by a client device in the networked environment of FIG. 1 according to various embodiments of the present disclosure.

DETAILED DESCRIPTION

As a non-limiting example, if a developer wishes to write a video game involving a rabbit, fox, and carrots, the developer may write an amount of natural language text 103 that includes:

With reference to FIG. 3 , shown is a networked environment 300 according to various embodiments. The networked environment 300 includes a computing environment 303 and a client device 306 , which are in data communication with each other via a network 309 . The network 309 includes, for example, the Internet, intranets, extranets, wide area networks (WANs), local area networks (LANs), wired networks, wireless networks, or other suitable networks, etc., or any combination of two or more such networks. For example, such networks may comprise satellite networks, cable networks, Ethernet networks, and other types of networks.

The computing environment 303 may comprise, for example, a server computer or any other system providing computing capability. Alternatively, the computing environment 303 may employ a plurality of computing devices that may be arranged, for example, in one or more server banks or computer banks or other arrangements. Such computing devices may be located in a single installation or may be distributed among many different geographical locations. For example, the computing environment 303 may include a plurality of computing devices that together may comprise a hosted computing resource, a grid computing resource, or any other distributed computing arrangement. In some cases, the computing environment 303 may correspond to an elastic computing resource where the allotted capacity of processing, network, storage, or other computing-related resources may vary over time.

Various applications or other functionality may be executed in the computing environment 303 according to various embodiments. In addition, various data is stored in a data store 312 that is accessible to the computing environment 303 . The data store 312 may be representative of a plurality of data stores 312 as can be appreciated. The data stored in the data store 312 , for example, is associated with the operation of the various applications and/or functional entities described below.

The components executed on the computing environment 303 , for example, include a network site application 315 , one or more remote compilers 321 , a web service 324 , and potentially other applications, services, processes, systems, engines, or functionality not discussed in detail herein. One of the remote compilers 321 may include, for example, a natural language compiler 327 , as will be described.

The network site application 315 is executed to generate network pages, such as web pages or other types of network content that may be provided to client devices 306 for the purposes of receiving the natural language text 103 , as will be discussed. For instance, the network site application 315 may generate user interface data that comprises a text box or other user interface component that allows a developer to write a program in a natural language.

The remote compilers 321 may include one or more compilers used to convert natural language text 103 into executable code, or code capable of being interpreted by hardware of a computing device (e.g., a processor). In various embodiments, one of the remote compilers 321 includes a natural language compiler 327 while other ones of the remote compilers 321 may include, for example, C compilers, C++ compilers, assembly compilers, and so forth.

The natural language compiler 327 is executed to analyze a sentence to programmatically determine a meaning or âintentâ of the sentence. According to various embodiments, the natural language compiler 327 may be configured to identify and resolve nouns, verbs, pronouns, or other parts of speech. Additionally, the natural language compiler 327 may be configured to compare words 345 or phrases 348 used in a sentence to a dictionary 330 in the data store 312 to determine whether identical or fuzzy matched entries are identified. When a word 345 or phrase 348 of a sentence is identified, the natural language compiler 327 may generate code in an intermediate format, such as C, C++, or other programming language. The intermediate format may be generated using token matching, as will be described.

The web service 324 is executed to provide a medium for communication between the computing environment 303 and the client devices 306 over the network 309 . The web service 324 may comprise a web-based application programming interface (API) embodied in software that facilitates programmatic service calls (or API calls) made by a client application to communicate with the components of the computing environment 303 , such as the network site application 315 , the remote compilers 321 , the natural language compiler 327 , or other services or applications not described herein. According to various embodiments, the web-based API may further comprise a representational state transfer (REST) API, a simple object access protocol (SOAP) API, or another suitable API. Programmatic service calls may be performed using a hypertext transfer protocol (HTTP), a secure hypertext transfer protocol (HTTPS), or other similar protocol. Non web-based user interfaces are also possible, such as one generated by a local client application.

The data stored in the data store 312 includes, for example, a dictionary 330 , grammatical rules 333 , certainty metrics 336 , libraries 339 , language models 342 , and potentially other data. The dictionary 330 may include a listing of words 345 and phrases 348 for a particular domain of applications, such as video games. In the domain of video games, some examples of words 345 may include ârun,â âcatch,â âjump,â âhide,â âscared,â as well as variations of those words 345 , such as âran,â ârunning,â âcaught,â etc. Each of the words 345 or phrases 348 may be associated with a token 352 . A token 352 may include a keyword, a function name, a variable name, or other entity that may be used to replace a word 345 or a phrase 348 to generate programming code in an intermediate format.

In some instances, the token 352 may be identical to a corresponding word 345 or phrase 348 . For instance, the sentence âA catches Bâ may be analyzed, where âcatchesâ is an entry in the dictionary 330 and the token 352 associated with âcatchesâ is âcatches.â The natural language compiler 327 may use the token 352 to generate an intermediate format of âcatches(A,B),â where catch is a name of a function in a library 339 . In other instances, the token 352 may be different than a word 345 or phrase 348 . For instance, the sentence âA catches Bâ may be analyzed, where âcatchesâ is an entry in the dictionary 330 and the token 352 associated with âcatchesâ is âcatch.â The natural language compiler 327 may use the token 352 to generate an intermediate format of âcatch(A,B),â where catch is a name of a function or a routine in a library 339 .

The grammar for all possible sentences involving actions and predicates can be derived as a set of grammatical rules 333 . An intermediate format for each sentence may be generated using the grammatical rules 333 . For example, âThe fox wanders aroundâ may be converted by the natural language compiler 327 to âwander(fox).â Similarly, âWhen a fox catches a rabbit, the rabbit diesâ may be converted to âif catch(fox, rabbit), die(rabbit).â

The certainty metrics 336 may include metrics determined for each sentence of natural language text 103 . In one embodiment, a certainty metric 336 includes a number that reflects a percentage that the natural language compiler 327 is certain about an understanding of the sentence in English or other natural language. In some embodiments, the certainty metric may be computed as a function of token matching and grammatical matching. For instance, different weights can be given to token matching and grammatical matching. If tokens are matched and grammar (or semantics) are capable of being understood, a high certainty metric may be generated. Conversely, if tokens are unable to be matched and grammar (or semantics) are not capable of being understood, a low certainty metric may be generated.

The libraries 339 may include predefined (or prewritten) functions/ routines 355 and global variables 358 for a given domain or type of applications, as may be appreciated. For instance, in the domain of video games 106 , the functions/ routines 355 may include âcatch( )â ârun( )â âjump( )â âcontrol( )â or other function/routine 355 that may be needed to compile an executable video game 106 . Global variables 358 may include predetermined variables that may be used in generating code in an intermediate format that can be compiled, as may be appreciated.

The client device 306 is representative of a plurality of client devices that may be coupled to the network 309 . The client device 306 may comprise, for example, a processor-based system such as a computer system. Such a computer system may be embodied in the form of a desktop computer, a laptop computer, personal digital assistants, cellular telephones, smartphones, set-top boxes, music players, web pads, tablet computer systems, game consoles, electronic book readers, or other devices with like capability. The client device 306 may include a display 366 . The display 366 may comprise, for example, one or more devices such as liquid crystal display (LCD) displays, gas plasma-based flat panel displays, organic light emitting diode (OLED) displays, electrophoretic ink (E ink) displays, LCD projectors, or other types of display devices, etc.

The client device 306 may be configured to execute various applications such as a client application 369 and/or other applications. The client application 369 may be executed in a client device 306 , for example, to access network content served up by the computing environment 303 or other servers, thereby rendering a user interface 372 on the display 366 . To this end, the client application 369 may comprise, for example, a browser, a dedicated application, etc., and the user interface 372 may comprise a network page, an application screen, etc. The client device 306 may be configured to execute applications beyond the client application 369 such as, for example, email applications, social networking applications, word processors, spreadsheets, or other applications.

Next, a general description of the operation of the various components of the networked environment 300 is provided. To begin, a user may desire to write a computer application, but may not be familiar with a high-, medium-, or low-level programming language. As such, the user may execute a client application 369 on his or her client device 306 to access a network site offered through the network site application 315 . For instance, a user may execute a web browser and navigate to a particular website where the network site application 315 generates user interface data 399 that causes a user interface 372 to be rendered by the web browser. The user interface 372 may include a text box or similar field to receive text 103 in a natural language. For instance, the user may write natural language text 103 and submit the natural language text 103 to the computing environment 303 after completion, such that the computing environment 303 can compile the natural language text 103 into an executable application remotely.

To this end, the natural language compiler 327 may be employed to parse the natural language text 103 written by a user and identify words 345 or phrases 348 in each sentence of the natural language text 103 . Based on the words 345 and phrases 348 identified in each sentence, grammatical rules 333 may be used to identify semantics of the sentence. The grammatical rules 333 may be defined such that different ways of saying the same sentence are captured. For example, a sentence may state, âWhen a rabbit is caught by a fox, the rabbit dies.â The natural language compiler 327 may identify entities (or nouns), such as ârabbitâ and âfox.â Moreover, the natural language compiler 327 may identify âcaughtâ and âdiesâ as actions performed on the rabbit. In various embodiments, the parsing performed by the natural language compiler 327 may be performed by an application service independent from the natural language compiler 327 .

To identify semantics, words 345 or phrases 348 from the natural language text 103 are compared to entries in the dictionary 330 . In the above example, the words 345 ârabbit,â âfox,â and âcarrotsâ may be entries in the dictionary 330 . Each entry in the dictionary 330 may have a corresponding token 352 , where the token 352 is used in the place of the word 345 or phrase 348 when generating an intermediate format. The token 352 may include a name of a prewritten function/routine 355 or routine stored in the library 339 . For example, if the word 345 of âcaughtâ is used in the natural language text 103 , the dictionary 330 may indicate that a token 352 to be used in the intermediate format is âcatch.â The token 352 of âcatchâ may correspond to the function/routine 355 âcatch( )â in the library 339 . Similarly, another token 352 , such as âdieâ may be associated with âdies,â âis executed,â âkill,â or other related words 345 . Thus, an intermediate format of âif catch(fox, rabbit), die(rabbit)â may be generated by the natural language compiler 327 .

If semantics of the sentence are not identifiable by the natural language compiler 327 , the remote compiler 321 may return an error message. In some embodiments, the network site application 315 may cause the user interface 372 to suggest the user to write the sentence in a different way. Also, in some embodiments, the network site application 315 may provide additional error messaging as to how or why the sentence was not understood. In further embodiments, suggestions on how to make the natural language text 103 more understandable may be provided to the user.

As may be appreciated, the dictionary 330 , the libraries 339 , other data, and operation of the natural language processors 318 and remote compilers 321 may be tailored to a particular domain (or type) of computer application. In other words, the dictionary 330 , the libraries 339 , and operations performed by the natural language compiler 327 may be unique to video games 106 as opposed to other types of applications. To this end, the natural language text 103 may be parsed or analyzed differently based on a domain specified by a user. In some embodiments, the application domain may include, for example, a video game 106 , a web browser, a word processing application, a social networking application, or other type of computer application, as may be appreciated.

Given a specific domain, the remote compiler 321 may construct a language model 342 for the domain. Succinctly, a language model 342 , L, may be described as a tuple, where L=(E, A, T, P, S, G). E refers to a set of entities, A refers to a set of actions, T refers to a set of attributes. P refers to a set of optional predicates and S refers to a set of selectors. Finally, G refers to an underlying grammar binding words 345 and phrases 348 for the domain. The items in sets E, A, T, P, and S may include words 345 or phrases 348 .

The extent to which these sets encompass a language model 342 may also determine the expressiveness of the resulting natural language for the domain of computing applications. To understand the sentences, grammatical rules 333 may be employed by the natural language compiler 327 to analyze a sentence in which a varying number of phrases 348 from each of the five aforementioned sets is comprised. The <figure-callout id="327" label="natural language compiler" filenames="US10843080-20201124-D00003.png,US10843080-20201124-D00004.png" state="{{state}

CLAIMS

Claims ( 20 )

Therefore, the following is claimed:

1. A system, comprising:

at least one computing device comprising at least one hardware processor; and

program instructions executable in the at least one computing device that, when executed, cause the at least one computing device to:

identify a plurality of words from at least one sentence of text formed in a natural language following a grammatical structure for the natural language;

compare the plurality of words to a dictionary to determine whether individual ones of the plurality of words have a corresponding entry in the dictionary;

in response to a first one of the plurality of words having a corresponding entry in the dictionary, identify a first token stored in association with the corresponding entry for the first one of the plurality of words;

in response to a second one of the plurality of words not having a corresponding entry in the dictionary:

identify an object from the plurality of words of the at least one sentence of text;

determine a meaning for the second one of the plurality of words based at least in part on a contextual analysis of an antecedent clause of the at least one sentence of text and a consequent clause of a subsequent or preceding sentence of text of the at least one sentence of text, and store a second token in association with a corresponding entry for the second one of the plurality of words; and

bind the second one of the plurality of words to the object such that the second one of the plurality of words is a variable for the object that can be consulted during execution of an application;

in response to a third one of the plurality of words not having a corresponding entry in the dictionary and a meaning of the third one of the plurality of words unable to be determined, generate an error message to provide on the at least one computing device;

in response to an error associated with the third one of the plurality of words being resolved, convert the text formed in the natural language to an intermediate format of programming code in a predetermined programming language, wherein the intermediate format comprises the first token or the second token, the first token and the second token invoking at least one function or at least one routine of a library written in the predetermined programming language; and

compile the intermediate format into executable program code to generate the application configured for execution.

2. The system of claim 1 , wherein:

the application is a video game application; and

the library comprises a plurality of functions or a plurality of routines corresponding to a video game application domain.

3. The system of claim 1 , further comprising program instructions executable in the at least one computing device that, when executed, cause the at least one computing device to store the at least one of the plurality of words in the dictionary or a temporary dictionary separate from the dictionary in association with the meaning.

4. The system of claim 1 , wherein the contextual analysis comprises:

analyzing the antecedent clause of the at least one sentence and analyzing the consequent clause of a subsequent sentence of the at least one sentence; or

analyzing the antecedent clause of the at least one sentence and analyzing the consequent clause of a preceding sentence of the at least one sentence.

5. The system of claim 1 , wherein comparing the plurality of words to the dictionary comprises applying a fuzzy matching methodology.

6. The system of claim 1 , further comprising program instructions executable in the at least one computing device that, when executed, cause the at least one computing device to generate user interface data for rendering a user interface in a display of a client device, wherein the user interface comprises a text field for entry of the text formed in the natural language.

7. The system of claim 6 , wherein the at least one computing device is a device located remotely from the client device on which the text is provided, the text being received by the computing device from the client device over a network.

8. The system of claim 1 , wherein the at least one computing device is a client device, the program instructions being executed locally on the client device.

9. The system of claim 1 , further comprising program instructions executable in the at least one computing device that, when executed, cause the at least one computing device to generate a certainty metric for the sentence that indicates a degree to which the sentence was understood programmatically.

10. The system of claim 9 , further comprising program instructions executable in the at least one computing device that, when executed, cause the at least one computing device to generate the error message in response to the certainty metric satisfying an error threshold.

11. A computer-implemented method, comprising:

identifying, by at least one computing device, a plurality of words from at least one sentence of text formed in a natural language following a grammatical structure for the natural language;

comparing, by the at least one computing device, the plurality of words to a dictionary to determine whether individual ones of the plurality of words have a corresponding entry in the dictionary;

in response to at least a first one of the plurality of words having a corresponding entry in the dictionary, identifying, by the at least one computing device, a first token stored in association with the corresponding entry for the first one of the plurality of words;

in response to a second one of the plurality of words not having a corresponding entry in the dictionary:

identifying an object from the plurality of words of the at least one sentence of text;

determining a meaning of the second one of the words based at least in part on a contextual analysis of an antecedent clause of the at least one sentence and a consequent clause of a subsequent or preceding sentence of text of the at least one sentence of text, and storing a second token in association with a corresponding entry for the second; and

binding the second one of the plurality of words to the object such that the second one of the plurality of words is a variable for the object that can be consulted during execution of an application;

in response to a third one of the plurality of words not having a corresponding entry in the dictionary and a meaning of the third one of the plurality of words unable to be determined, generating an error message to provide on the at least one computing device;

in response to an error associated with the third one of the plurality of words being resolved, converting, by the at least one computing device, the text formed in the natural language to an intermediate format of programming code in a predetermined programming language, wherein the intermediate format comprises the first token or the second token, the first token and the second token invoking at least one function or at least one routine of a library written in the predetermined programming language; and

compiling, by the at least one computing device, the intermediate format into executable program code to generate the application configured for execution.

12. The computer-implemented method of claim 11 , wherein:

the application is a video game application; and

the library comprises a plurality of functions or a plurality of routines corresponding to a video game application domain.

13. The computer-implemented method of claim 11 , further comprising storing, by the at least one computing device, the at least a first word in the dictionary or a temporary dictionary separate from the dictionary in association with the meaning.

14. The computer-implemented method of claim 11 , wherein the contextual analysis comprises:

analyzing the antecedent clause of the at least one sentence and analyzing the consequent clause of a subsequent sentence of the at least one sentence; or

analyzing the antecedent clause of the at least one sentence and analyzing the consequent clause of a preceding sentence of the at least one sentence.

15. The computer-implemented method of claim 11 , wherein comparing the plurality of words to the dictionary comprises applying, by the at least one computing device, a fuzzy matching methodology.

16. The computer-implemented method of claim 11 , further comprising generating, by the at least one computing device, user interface data for rendering a user interface in a display of a client device, wherein the user interface comprises a text field for entry of the text formed in the natural language.

17. The computer-implemented method of claim 16 , wherein the at least one computing device is a device located remotely from the client device on which the text is provided, the text being received by the computing device from the client device over a network.

18. The computer-implemented method of claim 11 , wherein the at least one computing device is a client device, the computer-implemented method being performed locally on the client device.

19. The computer-implemented method of claim 11 , further comprising generating, by the computing device, a certainty metric for the sentence that indicates a degree to which the sentence was understood programmatically.

20. The computer-implemented method of claim 19 , further comprising generating, by the computing device, the error message in response to the certainty metric satisfying an error threshold.

US15/440,490

2016-02-24

2017-02-23

Automated program synthesis from natural language for domain specific computing applications

Active

2037-10-21

US10843080B2

( en )

Priority Applications (1)

Application Number

Priority Date

Filing Date

Title

US15/440,490

US10843080B2

( en )

2016-02-24

2017-02-23

Automated program synthesis from natural language for domain specific computing applications

Applications Claiming Priority (2)

Application Number

Priority Date

Filing Date

Title

US201662299047P

2016-02-24

US15/440,490

US10843080B2

( en )

2016-02-24

2017-02-23

Automated program synthesis from natural language for domain specific computing applications

Publications (2)

Publication Number

Publication Date

US20170239576A1

US20170239576A1 ( en )

2017-08-24

US10843080B2

true

US10843080B2 ( en )

2020-11-24

Family

ID=59629246

Family Applications (1)

Application Number

Title

Priority Date

Filing Date

US15/440,490

Active

2037-10-21

US10843080B2

( en )

2016-02-24

2017-02-23

Automated program synthesis from natural language for domain specific computing applications

Country Status (1)

Country

Link

( 1 )

US10843080B2

( en )

Cited By (3)

* Cited by examiner, â Cited by third party

Publication number

Priority date

Publication date

Assignee

Title

US20220413847A1

( en )

2021-06-25

2022-12-29

International Business Machines Corporation

Compliance content generation

US12423503B2

( en )

2021-11-10

2025-09-23

Graf Research Corporation

Computer-implemented verification of a hardware design implementation against a natural language description of the hardware design or software code against a natural language description of a software application

US12547845B2

( en )

2023-07-24

2026-02-10

Bank Of America Corporation

Systems, methods, and apparatuses for implementing natural language processing to determine natural language from computer programming language in an electronic environment

Families Citing this family (25)

* Cited by examiner, â Cited by third party

Publication number

Priority date

Publication date

Assignee

Title

US11222266B2

( en )

2016-07-15

2022-01-11

Intuit Inc.

System and method for automatic learning of functions

US10579721B2

( en )

2016-07-15

2020-03-03

Intuit Inc.

Lean parsing: a natural language processing system and method for parsing domain-specific languages

US11049190B2

( en )

2016-07-15

2021-06-29

Intuit Inc.

System and method for automatically generating calculations for fields in compliance forms

US10725896B2

( en )

2016-07-15

2020-07-28

Intuit Inc.

System and method for identifying a subset of total historical users of a document preparation system to represent a full set of test scenarios based on code coverage

JP6810757B2

( en )

2016-12-27

2021-01-06

ã·ã£ã¼ãæ ªå¼ä¼ç¤¾

Response device, control method of response device, and control program

US10740190B2

( en )

2017-09-15

2020-08-11

Iron Mountain Incorporated

Secure data protection and recovery

EP3570188A1

( en )

2018-05-14

2019-11-20

Fortia Financial Solutions

Generating an executable code based on a document

US11481389B2

( en )

2017-12-18

2022-10-25

Fortia Financial Solutions

Generating an executable code based on a document

FR3077656A1

( en )

2018-02-07

2019-08-09

Christophe Leveque

METHOD FOR TRANSFORMING A SEQUENCE TO MAKE IT EXECUTABLE BY A MACHINE

US11194800B2

( en )

2018-04-26

2021-12-07

Microsoft Technology Licensing, Llc

Parallel search in program synthesis

CN113366430B

( en )

2019-01-10

2024-08-16

å¸è±æ©è®¤ç¥ç§äººæéå¬å¸

Natural Solutions Language

US12039279B2

( en )

2019-01-10

2024-07-16

Brane Cognitives Pte. Ltd.

Natural solution language

US11790263B2

( en )

2019-02-25

2023-10-17

International Business Machines Corporation

Program synthesis using annotations based on enumeration patterns

US11163956B1

( en )

2019-05-23

2021-11-02

Intuit Inc.

System and method for recognizing domain specific named entities using domain specific word embeddings

CN110287001A

( en )

2019-06-18

2019-09-27

å±±ä¸å·¥åå¦é¢

Program Synthesis Virtual Machine

US11494558B2

( en )

2020-01-06

2022-11-08

Netiq Corporation

Conversion of script with rule elements to a natural language format

US11783128B2

( en )

2020-02-19

2023-10-10

Intuit Inc.

Financial document text conversion to computer readable operations

JP6812583B1

( en )

2020-02-28

2021-01-13

æ ªå¼ä¼ç¤¾ï¼£ï½ï½ï½ï½ï½ï½

Systems and methods to assist in the creation of game scripts

US20220387887A1

( en )

2020-03-13

2022-12-08

Google Llc

Game content choreography based on game context using semantic natural language processing and machine learning

WO2021183160A1

( en )

2020-03-13

2021-09-16

Google Llc

Controlling agents in a video game using semantic machine learning and a natural language action grammar

WO2021183159A1

( en )

2020-03-13

2021-09-16

Google Llc

Re-ranking results from semantic natural language processing machine learning algorithms for implementation in video games

US11532309B2

( en )

2020-05-04

2022-12-20

Austin Cox

Techniques for converting natural speech to programming code

US11604626B1

( en )

2021-06-24

2023-03-14

Amazon Technologies, Inc.

Analyzing code according to natural language descriptions of coding practices

US12079602B2

( en )

2022-03-07

2024-09-03

Salesforce, Inc.

Systems and methods for a conversational framework of program synthesis

US20230359819A1

( en )

2022-05-06

2023-11-09

Sap Se

Intelligent qr code compression

Citations (28)

* Cited by examiner, â Cited by third party

Publication number

Priority date

Publication date

Assignee

Title

EP0182460A1

( en )

1984-10-23

1986-05-28

Profit Technology, Inc.

Multi-image communications system

US5038296A

( en )

1989-04-04

1991-08-06

Kabushiki Kaisha Toshiba

Automatic program synthisizer

US6173441B1

( en )

1998-10-16

2001-01-09

Peter A. Klein

Method and system for compiling source code containing natural language instructions

US6246986B1

( en )

1998-12-31

2001-06-12

At&T Corp.

User barge-in enablement in large vocabulary speech recognition systems

US20020120647A1

( en )

2000-09-27

2002-08-29

Ibm Corporation

Application data error correction support

US6499013B1

( en )

1998-09-09

2002-12-24

One Voice Technologies, Inc.

Interactive user interface using speech recognition and natural language processing

US20030212541A1

( en )

2002-05-13

2003-11-13

Gary Kinder

Method for editing and enhancing readability of authored documents

US20050005266A1

( en )

1997-05-01

2005-01-06

Datig William E.

Method of and apparatus for realizing synthetic knowledge processes in devices for useful applications

US20060293894A1

( en )

2005-06-23

2006-12-28

Microsoft Corporation

Using strong data types to express speech recognition grammars in software programs

US20070072678A1

( en )

2005-09-28

2007-03-29

Dagres Todd A

Method and system of online gaming organization

US7302383B2

( en )

2002-09-12

2007-11-27

Luis Calixto Valles

Apparatus and methods for developing conversational applications

US7346490B2

( en )

2000-09-29

2008-03-18

Axonwave Software Inc.

Method and system for describing and identifying concepts in natural language text for information retrieval and processing

US20090244071A1

( en )

2007-08-09

2009-10-01

China Motor Corporation.

Synthetic image automatic generation system and method thereof

US7853623B2

( en )

2006-12-18

2010-12-14

Hitachi, Ltd.

Data mining system, data mining method and data retrieval system

US7966182B2

( en )

2006-06-20

2011-06-21

Lunis Orcutt

Voiced programming system and method

US8402032B1

( en )

2010-03-25

2013-03-19

Google Inc.

Generating context-based spell corrections of entity names

US20140379334A1

( en )

2013-06-20

2014-12-25

Qnx Software Systems Limited

Natural language understanding automatic speech recognition post processing

US9069814B2

( en )

2011-07-27

2015-06-30

Wolfram Alpha Llc

Method and system for using natural language to generate widgets

US20150220618A1

( en )

2014-01-31

2015-08-06

Verint Systems Ltd.

Tagging relations with n-best

US20160379629A1

( en )

2015-06-25

2016-12-29

Intel Corporation

Method and system of automatic speech recognition with dynamic vocabularies

US20160379633A1

( en )

2015-06-29

2016-12-29

Disney Enterprises, Inc.

Speech-Controlled Actions Based on Keywords and Context Thereof

US20170004374A1

( en )

2015-06-30

2017-01-05

Yahoo! Inc.

Methods and systems for detecting and recognizing text from images

US9594737B2

( en )

2013-12-09

2017-03-14

Wolfram Alpha Llc

Natural language-aided hypertext document authoring

US9594740B1

( en )

2016-06-21

2017-03-14

International Business Machines Corporation

Forms processing system

US9619209B1

( en )

2016-01-29

2017-04-11

International Business Machines Corporation

Dynamic source code generation

US20170263248A1

( en )

2016-03-14

2017-09-14

Apple Inc.

Dictation that allows editing

US9851950B2

( en )

2011-11-15

2017-12-26

Wolfram Alpha Llc

Programming in a precise syntax using natural language

US20180144064A1

( en )

2016-11-21

2018-05-24

Accenture Global Solutions Limited

Closed-loop natural language query pre-processor and response synthesizer architecture

2017

2017-02-23

US15/440,490

patent/US10843080B2/en

active

Active

Patent Citations (28)

* Cited by examiner, â Cited by third party

Publication number

Priority date

Publication date

Assignee

Title

EP0182460A1

( en )

1984-10-23

1986-05-28

Profit Technology, Inc.

Multi-image communications system

US5038296A

( en )

1989-04-04

1991-08-06

Kabushiki Kaisha Toshiba

Automatic program synthisizer

US20050005266A1

( en )

1997-05-01

2005-01-06

Datig William E.

Method of and apparatus for realizing synthetic knowledge processes in devices for useful applications

US6499013B1

( en )

1998-09-09

2002-12-24

One Voice Technologies, Inc.

Interactive user interface using speech recognition and natural language processing

US6173441B1

( en )

1998-10-16

2001-01-09

Peter A. Klein

Method and system for compiling source code containing natural language instructions

US6246986B1

( en )

1998-12-31

2001-06-12

At&T Corp.

User barge-in enablement in large vocabulary speech recognition systems

US20020120647A1

( en )

2000-09-27

2002-08-29

Ibm Corporation

Application data error correction support

US7346490B2

( en )

2000-09-29

2008-03-18

Axonwave Software Inc.

Method and system for describing and identifying concepts in natural language text for information retrieval and processing

US20030212541A1

( en )

2002-05-13

2003-11-13

Gary Kinder

Method for editing and enhancing readability of authored documents

US7302383B2

( en )

2002-09-12

2007-11-27

Luis Calixto Valles

Apparatus and methods for developing conversational applications

US20060293894A1

( en )

2005-06-23

2006-12-28

Microsoft Corporation

Using strong data types to express speech recognition grammars in software programs

US20070072678A1

( en )

2005-09-28

2007-03-29

Dagres Todd A

Method and system of online gaming organization

US7966182B2

( en )

2006-06-20

2011-06-21

Lunis Orcutt

Voiced programming system and method

US7853623B2

( en )

2006-12-18

2010-12-14

Hitachi, Ltd.

Data mining system, data mining method and data retrieval system

US20090244071A1

( en )

2007-08-09

2009-10-01

China Motor Corporation.

Synthetic image automatic generation system and method thereof

US8402032B1

( en )

2010-03-25

2013-03-19

Google Inc.

Generating context-based spell corrections of entity names

US9069814B2

( en )

2011-07-27

2015-06-30

Wolfram Alpha Llc

Method and system for using natural language to generate widgets

US9851950B2

( en )

2011-11-15

2017-12-26

Wolfram Alpha Llc

Programming in a precise syntax using natural language

US20140379334A1

( en )

2013-06-20

2014-12-25

Qnx Software Systems Limited

Natural language understanding automatic speech recognition post processing

US9594737B2

( en )

2013-12-09

2017-03-14

Wolfram Alpha Llc

Natural language-aided hypertext document authoring

US20150220618A1

( en )

2014-01-31

2015-08-06

Verint Systems Ltd.

Tagging relations with n-best

US20160379629A1

( en )

2015-06-25

2016-12-29

Intel Corporation

Method and system of automatic speech recognition with dynamic vocabularies

US20160379633A1

( en )

2015-06-29

2016-12-29

Disney Enterprises, Inc.

Speech-Controlled Actions Based on Keywords and Context Thereof

US20170004374A1

( en )

2015-06-30

2017-01-05

Yahoo! Inc.

Methods and systems for detecting and recognizing text from images

US9619209B1

( en )

2016-01-29

2017-04-11

International Business Machines Corporation

Dynamic source code generation

US20170263248A1

( en )

2016-03-14

2017-09-14

Apple Inc.

Dictation that allows editing

US9594740B1

( en )

2016-06-21

2017-03-14

International Business Machines Corporation

Forms processing system

US20180144064A1

( en )

2016-11-21

2018-05-24

Accenture Global Solutions Limited

Closed-loop natural language query pre-processor and response synthesizer architecture

Non-Patent Citations (32)

* Cited by examiner, â Cited by third party

Title

" 2015 Sales, Demographic and Usage Data-Essential Facts About the Computer and Video Game Industry. " Entertainment Software Association. pp. 3. 2015.

" Anybody can learn | Code.org, " Code.org, http://code.org (last visited Feb. 23, 2017).

" Computer Programming | Computing, " Khan Academy, https://www.khanacademy.org/computing/computer-programming (last visited Feb. 23, 2017).

" Fact Sheet: President Obama Announces Computer Science for All Initiative, " The White House (Jan. 30, 2016), https://www.whitehouse.gov/the-press-office/2016/01/30/fact-sheet-president-obama-announces-computer-science-all-initiative-0 (last visited Feb. 23, 2017).

" Gamestar Mechanic Learn to design video games, " Gamestar Mechanic, https://gamestarmechanic.com (last visited Feb. 23, 2017).

" Girls Who Code, " http://girlswhocode.com (last visited Feb. 23, 2017).

" Google CS First, " Google, http://cs-first.com (last visited Feb. 23, 2017).

" Hour of Code, " https://hourofcode.com (last visited Feb. 23, 2017).

" Learn to code | Codeacademy, " Codeacademy, http://www.codeacademy.com (last visited Feb. 23, 2017).

" Make 2D Games with Gamemaker, " Yoyo Games, http://yoyogames.com (last visited Feb. 23, 2017).

" Mobile robot programming using natural language " Lauria S., Bugmann G., Kyriacou T., Klein E. (2002) Robotics and Autonomous Systems, 38 (3-4) , pp. 171-181.

" National Center for Women & Information Technology, " http://www.ncwit.org (last visited Feb. 23, 2017).

" Scratch-Imagine, Program, Share, " Scratch, https://scratch.mit.edu (last visited Feb. 23, 2017).

" STEM Attrition: College Students' Paths Into and Out of STEM Fields Statistical Analysis Report, " U.S. Dept. of Education, http://nces.ed.gov/pubs2014/2014001rev.pdf (last visited Feb. 23, 2017).

" Unity-Game Engine, " Unity, http://unity3d.com (last visited Feb. 23, 2017).

" 2015 Sales, Demographic and Usage DataâEssential Facts About the Computer and Video Game Industry. " Entertainment Software Association. pp. 3. 2015.

" ScratchâImagine, Program, Share, " Scratch, https://scratch.mit.edu (last visited Feb. 23, 2017).

" UnityâGame Engine, " Unity, http://unity3d.com (last visited Feb. 23, 2017).

A Cozzieand and S. T. King. " Macho: Writing programs with natural language and examples. " Technical report, University of Illinois at Urbana-Champaign, 2012.

A. W. Biermann and B. W. Ballard, " Toward natural language computation, " Comput. Linguist., vol. 6, No. 2, pp. 71-86, 1980.

G. Little and R. C. Miller. Keyword programming in Java. Autom. Softw. Eng., 16(1):37-71, 2009.

Liu, H, & Lieberman, H. Metaphor: Visualizing Stories as Code. Intelligent User Interfaces Conference (IUI 2005), San Diego CA 2005.

N. Kushman and R. Barzilay, " Using Semantic Unification to Generate Regular Expressions from Natural Language, " NAACL 2013.

N. N. Shirvi and M. H. Panchal, " Translation of English Algorithm in C Program using Syntax Directed Translation Schema, " IJCSMC, vol. 3, No. 2, Feb. 2014, pp. 752-760.

N. Nihalani, S. Silakari, and M. Motwani. Natural language interface for database: A brief review. IJCSI, 8(2), 2011.

NLyze: Interactive programming by natural language for spreadsheet data analysis and manipulation. In SIGMOD, 2014.

R. J. Mooney. Learning for semantic parsing. In CICLing, 2007.

R. Singh and S. Gulwani. Learning semantic string transformations from examples. PVLDB, 5, 2012.

R. Singh and S. Gulwani. Synthesizing number transformations from input-output examples. In CAV, 2012.

T. Gvero and V. Kuncak, " Synthesizing Java expressions from free-form queries, " 2015 ACM OOPSLA, Oct. 2015., pp. 416-432.

T. Kwiatkowski, L. Zettlemoyer, S. Goldwater, and M. Steedman. Lexical generalization in CCG grammar induction for semantic parsing. In EMNLP, 2011.

W. R. Harris and S. Gulwani. Spreadsheet table transformations from examples. In PLDI, 2011.

Cited By (4)

* Cited by examiner, â Cited by third party

Publication number

Priority date

Publication date

Assignee

Title

US20220413847A1

( en )

2021-06-25

2022-12-29

International Business Machines Corporation

Compliance content generation

US11972255B2

( en )

2021-06-25

2024-04-30

International Business Machines Corporation

Compliance content generation

US12423503B2

( en )

2021-11-10

2025-09-23

Graf Research Corporation

US12547845B2

( en )

2023-07-24

2026-02-10

Bank Of America Corporation

Systems, methods, and apparatuses for implementing natural language processing to determine natural language from computer programming language in an electronic environment

Also Published As

Publication number

Publication date

US20170239576A1

( en )

2017-08-24

Automated program synthesis from natural language for domain specific computing … — Virginia Tech Intellectual Properties, Inc. (US10843080B2)

Related documents