Extensible compiler utilizing a plurality of question handlers

Details Extensible compiler utilizing a plurality of question handlers Extensible compiler utilizing a plurality of question handlers

1999-05-28

2003-12-16

Ingberg, Todd (Department: 2124)

Data processing: software development, installation, and managem

Software program development tool

Translation of code

C717S158000, C717S144000

Reexamination Certificate

active

06665866

ABSTRACT:

A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure, as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever.
TECHNICAL FIELD
This invention relates to compilers, and more particularly to an architecture for an extensible compiler.
BACKGROUND
As computer technology has advanced, computer programs have become correspondingly complex to the point where it is very difficult for a programmer to write an application program in the machine language of the computer. Thus, most programs are written in a high-level language that is easier for the programmer to work with and then converted by a compiler into the machine language of the computer.
The compiler is itself typically a computer program. Compilers can be very complicated to design and construct, often being too complicated for a single individual to design and construct in a timely manner. Teams of individuals working together typically must coordinate their efforts very well in order to have the different portions of the compiler each individual is working on operate together properly. Typically, compilers make it extremely difficult, if not impossible, for an individual not working closely with the team to contribute a portion of the compiler.
Additionally, compilers are typically designed and written for “general” use. That is, rather than writing compilers targeted to specific tasks, industries or fields, a more general type of compiler is written. The result of such generalization is that some functionality (e.g., support for particular instructions) that would be beneficial in other specific tasks, industries or fields is not available in the compiler because such functionality is too specific. In rare cases, compilers are designed and written for specific tasks, industries, or fields. The result of such specialization is that some functionality that would be beneficial for other tasks, industries, or fields is not available in the compiler because such functionality is not needed for the specific task, industry, or field. Typically, neither sort of compiler allows additional functionality to be added, thereby, in the first case, causing additional complexity on the part of the high-level language programmer in order to carry out the desired functions, and in the second case, causing the compiler to fail to be used for the other functions.
The invention described below addresses these disadvantages, providing an extensible compiler architecture.
SUMMARY
A compiler architecture is described herein that provides for easy extensibility. A question and answer methodology is used between a reduction engine and question handlers corresponding to nodes of a graph representing the program being compiled. By using the question and answer methodology, additional functionality can be added to the compiler by users, whether they are part of the original design team of the compiler or a subsequent user.
According to one aspect of the invention, each node in the graph is associated with one or more question handlers. In order to compile the program, the reduction engine dispatches a series of questions to the question handlers, each of which can ask one or more questions of other question handlers. Once all the questions have been answered, the reduction engine is left with a compiled program. All queries to other question handlers are performed via the reduction engine.
According to another aspect of the invention, the information that a question handler obtains is of a semantic rather than structural nature. Each node in the graph is only aware of the other nodes to which it has a direct link, not the entire topology or structure of the graph.
According to another aspect of the invention, a question handler can add new nodes and/or links to the graph, but cannot delete any node or link.
According to another aspect of the invention, by the user adding new nodes, new question handlers for at least some of those new nodes, and possibly new links, new functionality (e.g., instructions) can be supported by the compiler. A question handler corresponding to the new functionality includes the instructions necessary to create additional nodes, links or binary information in the graph, and/or ask questions of other nodes, to carry out the desired functionality.
According to another aspect of the invention, during the compilation process the reduction engine detects when a question was answered with potentially incorrect information. When such a situation is detected, the reduction engine “rolls back” the compilation process, going back to a point where the incorrect information would have been given. The reduction engine then adds a rule that prevents that question from being answered until the appropriate subsequent time, and then proceeds to answer and dispatch other questions.


REFERENCES:
patent: 4667290 (1987-05-01), Goss et al.
patent: 5018075 (1991-05-01), Ryan et al.
patent: 5175856 (1992-12-01), Van Dyke et al.
patent: 5428554 (1995-06-01), Laskoski
patent: 5586020 (1996-12-01), Isozaki
patent: 5673369 (1997-09-01), Kim
patent: 5790863 (1998-08-01), Simonyi
patent: 5815711 (1998-09-01), Sakamoto et al.
patent: 5828883 (1998-10-01), Hall
patent: 5854935 (1998-12-01), Enomoto
patent: 5870564 (1999-02-01), Jensen et al.
patent: 5911072 (1999-06-01), Simonyi
patent: 5950009 (1999-09-01), Bortnikov et al.
patent: 5966537 (1999-10-01), Ravichandran
patent: 5974257 (1999-10-01), Austin
patent: 6006233 (1999-12-01), Schultz
patent: 6237136 (2001-05-01), Sadahiro
patent: 6253369 (2001-06-01), Cloud et al.
patent: 6272673 (2001-08-01), Dale et al.
“Optimization Decision Trees Through Heuristically Guided Search”, Alberto Martelli et al, ACM Communications, Dec. 1978, Vol 21, No 12, pages pp. 1025-1039.*
“Improved Data—Flow analysis with Path Profiles”, Glenn Ammons et al., ACM Apr. 1998, pp. 72-84.*
“Data Path Synthesis Using Path Analysis”, R. Bergamaschi et al., ACM, Jul. 1991, pp. 591-596.*
“Memory Efficient Software Synthesis from Dataflow Graph”, W. Sung et al, IEEE, May 1998, pp. 137-142.*
“Microarchitecture Support for Dynamic Scheduling of Acyclic Task Graph”, Carl Beckmann et al., IEEE Sep. 1992, pp. 140-148.
“Compiler Transformaions for High-Performance Computing”, David F. Bacon et al., ACM Computing Surveys vol 26, No 4, Dec. 1994, pp. 345-419.
“Elimination Algorithm for Data Analysis”, B. Ryder et al., ACM Computing Survey Vol 18, No 3, Sep. 1986, pp. 277-316.
“Understanding C Programs Using the Combined C Graph Representations”, David Kinloch et al., IEEE, Aug. 1994, pp. 172-180.
“Call Graph Construction in Object-Oriented Languages”, David Grove et al., ACM pp. 108-124, Apr. 1997.*
“Demand Driven Compution of Interproredural Data Flow”, Evelyn Duesterwald et al., ACM pp. 37-48, Jan. 1995.*
Compilers Principles, Techniques and Tools, Aifred V. Ano et al Chapters 1-5, Sep. 1985.*
“A Prototype System for Static and Dynamic Program Understanding”, David P. Otshefshi et al., IEEE, pp. 93-106, Mar. 1993.*
“Designing the Vser Interfare”, Ben Shneiderman Third Edition, p. 12, Jul. 23, 1997.*
“Interactive Animation of Visual Program Execution”, Poswig, Vrankar & Moraga, May 1993, IEEE, pp. 180-187.
“6.5.1 Fundamental Definitions”, 3 pages, dated May 11, 1999.

Affiliated with

Also associated with

Rating

Extensible compiler utilizing a plurality of question handlers does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Extensible compiler utilizing a plurality of question handlers, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Extensible compiler utilizing a plurality of question handlers will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3169002