Runtime symbol table for computer programs

Details Runtime symbol table for computer programs Runtime symbol table for computer programs

2000-08-22

2004-12-07

Dam, Tuan (Department: 2122)

Data processing: software development, installation, and managem

Software program development tool

Translation of code

C717S143000

Reexamination Certificate

active

06829760

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates generally to the field of computer programing and more particularly to compiler systems and runtime systems.
BACKGROUND
Conventional symbol tables are constructed during the compilation of a computer program to keep track of constants, variables, functions, key words, and the like in a program and to allocate pointers to (or addresses of) memory locations from where they can be accessed during program execution. Examples of known methods for creating such symbol tables are described by Aho, A. V., Sethi, R., and Ullman, J. D.,
Compilers: Principles, Techniques, and Tools,
Addison-Wesley Publishing Co., Reading, Mass., 1986, at pp. 11, 60-62, 84, 160, 429-440, 473, 475-480 and 703, and Pyster, A. B.,
Compiler Design and Construction,
2
nd
ed., Van Nostrand Reinhold, N.Y., 1988 at pp. 21, 170-172, 182 and 203-204. During the execution of a program, these symbol tables are usually abandoned.
One of the elementary steps in the compilation of a program is to scan the program character by character and pick up key words, numerical constants, operators, variable names, function names, etc. Of these, the constants, variable names, and function names must be assigned addresses in memory from where their values or execution sequence can be picked up. Again, the allocation of these addresses is facilitated by the construction of a symbol table. The symbol table stores information such as the name of the variable or function, its data type, its address, if assigned, and so on. Conventional methods usually have an algorithm that decides how the symbol table is to be populated with the principal objective of being able to determine quickly if a particular entity already exists in the symbol table or not. Certain computational and memory overheads are incurred in such conventional processes, but the overheads are considered worthwhile when programs have a large number of entities for which memory allocations must be made. Such conventional techniques were developed in an era when resources such as CPU cycles, memory space, and the like were scarce and consequently had to be used parsimoniously.
Existing optimizing compilers are complex software products and their abilities are quite limited, especially in reorganizing data to improve cache hits. Such compilers frequently attempt to rearrange the code through such means as rearranging nested loops, constant propagation, common subexpression elimination, moving invariant “if” code out of loops, etc. However, expert human programmers often do much better than optimizing compilers by clever handling of loops and distribution of data in memory because of their additional insight and knowledge about the domain to which the program belongs.
U.S. Pat. No. 5,778,231, issued on 7 Jul. 1998 to van Hoff et al., describes a program compiler that identifies symbols in program source code that references another program. The compiler then determines whether or not the symbol is a reference to a file that is located remotely or locally. If the symbol refers to a remotely located file, the compiler constructs a URL and retrieves, if possible, relevant portions of the compiled program or original source code referred to by the symbol. If the symbol refers to a locally located file, similar operations are preformed. The compiler described by U.S. Pat. No. 5,778,231 attempts to resolve symbols that reference another program in this matter during compilation. The compiler essentially, deals with the problem of gathering, at one place, pieces of a program distributed over a network of computers and integrating the pieces for compilation. U.S. Pat. No. 5,778,231 is directed entirely to compilation of computer programs and does not teach or suggest any post-compilation activities.
A major disadvantage of such conventional approaches is that committed decisions for optimal runtime execution are taken at compile time, thereby depriving the runtime system of utilising optimising opportunities as they arise during the execution of a program.
Thus, a need clearly exists for an improved technique of using symbol tables of computer programs for use by compilers and runtime systems.
SUMMARY
In accordance with a first aspect of the invention, there is provided a method for constructing a runtime symbol table for a computer program, the method including the steps of:
initializing a symbol table for storing one or more entities;
adding into the symbol table one or more tickets for each entity that does not already exist in the symbol table;
inserting an offset address after a predefined token for each ticket in a predefined set of tickets in the symbol table characterised as a sequence of the tickets; and
inserting one or more preassigned addresses in the symbol table for each ticket in the set of tickets that has preassigned addresses.
Preferably, the symbol table is a string of characters.
Preferably, the adding step further includes the step of searching the symbol table to determine if the symbol table already contains an entity. Still more preferably, the adding step further includes the steps of creating a ticket and concatenating the ticket with the symbol table. Yet more preferably, the adding step further includes the step of generating placeholders for each ticket to store incomplete information in the symbol table.
Preferably, the method further includes the step of, before the adding step, mapping an entity name for each of one or more entities having the same entity name as another entity name into a unique entity name for placement in the symbol table. The mapping can, be performed by a precompiler.
Each entity is selected from the group consisting of: a constant; a variable; a pointer; a function name; and a procedure name.
Each ticket includes an entity name and at least one tagged address. The ticket further may include at least one tag for specifying information regarding the corresponding entity. The at least one tagged address is selected from the group consisting of an entity home address, an entity offset address, and a copied address. Optionally, the at least one tagged address can be allocated dynamically by a runtime system.
Preferably, the method further includes the step of copying a tagged address in a ticket of an entity to enable optimisation of memory accesses of the entity. More preferably, the method further includes the step of deleting a tagged address in a ticket of an entity.
Optionally, the method includes the step of generating an error message using the runtime symbol table when an error occurs.
In accordance with a second aspect of the invention, there is disclosed an apparatus for constructing a runtime symbol table for a computer program, the apparatus including:
a device for initializing a symbol table for storing one or more entities;
a device for adding into the symbol table one or more tickets for each entity that does not already exist in the symbol table;
a device for inserting an offset address after a predefined token for each ticket in a predefined set of tickets in the symbol table characterised as a sequence of the tickets; and
a device for inserting one or more preassigned addresses in the symbol table for each ticket in the set of tickets that has preassigned addresses.
In accordance with a third aspect of the invention, there is disclosed a computer program product having a computer readable medium having a computer program recorded therein for constructing a runtime symbol table for a computer program, the computer program product including:
a computer program code module for initializing a symbol table for storing one or more entities;
a computer program code module for adding into the symbol table one or more tickets for each entity that does not already exist in the symbol table;
a computer program code module for inserting an offset address after a predefined token for each ticket in a predefined set of tickets in the symbol table characterised as a sequence of the tickets; and
a computer program code module for inserting one or more preassigned addresses i

Affiliated with

Also associated with

Rating

Runtime symbol table for computer programs does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Runtime symbol table for computer programs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Runtime symbol table for computer programs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3325328