Compiling and optimizing a computer code by minimizing a number of states in a finite machine corresponding to the computer code

• US 9,996,328 B1
• Filed: 06/22/2017
• Issued: 06/12/2018
• Est. Priority Date: 06/22/2017
• Status: Active Grant

• Current Assignee: Archeo Futurus, Inc.
• Original Assignee: Archeo Futurus, Inc.
• Inventors: Kluss, Daniel Joseph Bentley
• Primary Examiner(s): Rivera, Anibal
• Application Number:
  US15/630,691
• Time in Patent Office: 355 Days
• CPC Class Codes: G06F 16/00 Information retrieval; Database structures therefor; File system structures therefor
• CPC Class Codes: G06F 21/55 Detecting local intrusion or implementing counter-measures
• CPC Class Codes: G06F 21/552 involving long-term monitoring or reporting
• CPC Class Codes: G06F 21/57 Certifying or maintaining trusted computer platforms, e.g. secure boots or power-downs, version controls, system software checks, secure updates or assessing vulnerabilities
• CPC Class Codes: G06F 21/577 Assessing vulnerabilities and evaluating computer system security
• CPC Class Codes: G06F 2221/034 Test or assess a computer or a system
• CPC Class Codes: G06F 30/33 Design verification, e.g. functional simulation or model checking
• CPC Class Codes: G06F 40/143 Markup, e.g. Standard Generalized Markup Language [SGML] or Document Type Definition [DTD]
• CPC Class Codes: G06F 8/31 Programming languages or programming paradigms
• CPC Class Codes: G06F 8/427 Parsing
• CPC Class Codes: G06F 8/443 Optimisation
• CPC Class Codes: G06F 8/51 Source to source
• CPC Class Codes: G06F 8/76 Adapting program code to run in a different environment; Porting
• CPC Class Codes: G06F 9/44 Arrangements for executing specific programs
• CPC Class Codes: G06F 9/4498 Finite state machines

Abstract

Methods and systems for compiling codes from programming languages into programming languages are disclosed. An example method may include acquiring a first code written in a first language. The method allows generating, based on the first code, a first deterministic finite state machine (DFSM). The method includes optimizing the first DFSM to obtain a second DFSM. The method includes generating, based on the second DFSM, a second code. The second code can be written in a second language. Generating the first DFSM includes parsing the first code into a first abstract syntax tree (AST), translating the first AST into a first non-deterministic finite state machine (NFSM), and converting the first NFSM into the first DFSM. Generating the second code includes translating the second DFSM into a second NFSM, translating the second NFSM into a second AST, and recompiling the second AST into a second code.

Claims

1. A computer-implemented method for compiling and optimizing computer code and translating the computer source code from a first programming language into a second programming language, the method comprising:

acquiring a first source code, the first source code being written in the first programming language;

parsing, via one or more parsing expression grammar (PEG) modules and based on a first grammar associated with the first programming language determined by an augmented Backus-Naur Form (ABNF), the first source code to convert the first source code into a first abstract syntax tree (AST);

converting the first AST into a first non-deterministic finite state machine (NFSM);

converting the first NFSM into a first deterministic finite state machine (DFSM);

optimizing the first DFSM by minimizing a number of states in a finite state machine and by twice reversing the edges of the first DFSM to produce a second NFSM using a standard powerset construction by constructing only the reachable states of the first DFSM to obtain an optimized DFSM; and

converting, via at least the one or more PEG modules, the optimized DFSM into a second source code, the second source code being written in a second programming language wherein the second source code is a translation of the first source code;

the converting the optimized DFSM including converting the optimized DFSM into a third NFSM, converting the third NFSM into a second AST, and recompiling the second AST into the second source code.

2. The method of claim 1, wherein the first programming language or the second programming language includes one of the following:

JavaScript, C, C++, and a domain specific language.

3. The method of claim 1, wherein the first programming language or the second programming language includes one of the following:

a hardware description language and bits native to a field-programmable gate array.

4. The method of claim 1, wherein the first programming language or the second programming language includes a presentation language.

5. The method of claim 1, further comprising prior to generating the second source code, performing, based on a formal specification, a formal verification of the optimized DFSM.

6. A system for compiling source code and translating the source code from a first programming language into a second programming language, the system comprising:

at least one processor; and

a memory communicatively coupled to the at least one processor, the memory storing instructions, which, when executed by the at least one processor, perform a method comprising;

acquiring a first source code, the first source code being written in the first programming language;

parsing, via one or more parsing expression grammar (PEG) modules and based on a first grammar associated with the first programming language determined by an augmented Backus-Naur Form (ABNF), the first source code to convert the first source code into a first abstract syntax tree (AST);

converting the first AST into a first non-deterministic finite state machine (NFSM);

converting the first NFSM into a first deterministic finite state machine (DFSM);

optimizing the first DFSM by minimizing a number of states in a finite state machine and by twice reversing the edges of the first DFSM to produce a second NFSM using a standard powerset construction by constructing only the reachable states of the first DFSM to obtain an optimized DFSM; and

converting, via at least the one or more PEG modules, the optimized DFSM into a second source code, the second source code being written in a second programming language wherein the second source code is a translation of the first source code, the converting the optimized DFSM including converting the optimized DFSM into a third NFSM, converting the third NFSM into a second AST, and recompiling the second AST into the second source code.

7. The system of claim 6, wherein the first programming language or the second programming language includes one of the following:

JavaScript, C, C++, and a domain specific language.

8. The system of claim 6, wherein the first programming language or the second programming language includes one of the following:

a hardware description language and bits native to a field-programmable gate array.

9. A non-transitory computer-readable storage medium having embodied thereon instructions, which, when executed by one or more processors, perform a method for translating source code from a first programming language into a second programming language, the method comprising:

acquiring a first source code, the first source code being written in the first programming language;

parsing, via one or more parsing expression grammar (PEG) modules and based on a first grammar associated with the first programming language, the first source code to convert the first source code into a first abstract syntax tree (AST), wherein the grammar is determined by an augmented Backus-Naur Form;

converting the first AST into a first non-deterministic finite state machine (NFSM);

converting the first NFSM into a first deterministic finite state machine (DFSM);

optimizing the first DFSM by minimizing a number of states in a finite state machine and by twice reversing the edges of the first DFSM to produce a second NFSM using a standard powerset construction by constructing only the reachable states of the first DFSM to obtain an optimized DFSM;

converting the optimized DFSM into a third NFSM;

converting the third NFSM into a second AST; and

recompiling, via the one or more PEG modules and based on a second grammar associated with a second programming language, the second AST into the second source code, the second source code being written in the second programming language wherein the second source code is a translation of the first source code.