Browse Prior Art Database

Language Processing Language, Hashed Table Configurability

IP.com Disclosure Number: IPCOM000108223D
Original Publication Date: 1992-May-01
Included in the Prior Art Database: 2005-Mar-22
Document File: 1 page(s) / 48K

Publishing Venue

IBM

Related People

Hidalgo, DS: AUTHOR

Abstract

Disclosed is a feature of the LANGUAGE PROCESSING LANGUAGE (LPL) that supports the configurability of the static hashed table mechanically generated by LPL translator from an LDF (Language Definition File) to support the Predefined Symbol management. A great portion of the execution time of any formal language translator is spent in symbol lookups. The amount of time taken by a symbol lookup is highly dependent on the data structure used to store the symbols. Hashed tables have been proved to be one of the most efficient forms of symbol table structure used by language translators.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 76% of the total text.

Language Processing Language, Hashed Table Configurability

       Disclosed is a feature of the LANGUAGE PROCESSING
LANGUAGE (LPL) that supports the configurability of the static hashed
table mechanically generated by LPL translator from an LDF (Language
Definition File) to support the Predefined Symbol management. A great
portion of the execution time of any formal language translator is
spent in symbol lookups. The amount of time taken by a symbol lookup
is highly dependent on the data structure used to store the symbols.
Hashed tables have been proved to be one of the most efficient forms
of symbol table structure used by language translators.

      The efficiency of a hashed table lookup scheme is very
dependent on the static size of the hashed table. Although there are
guidelines for the selection of an adequate size for a hashed table,
the best figure depends among other factors, on the number of symbols
that will occupy the table.  Since this number is different for every
LPL application, then a method must be provided to the designer for
specifying the choice of static hashed table size. This is
particularly important because a good hashed table size is typically
twice the number of symbols, which implies a certain waste of
computer storage. In fact, the most storage used in this form the
better the performance of the table lookups, up to a certain point.
It must, therefore, be up the LPL user to decide how much storage can
be spared for a particular set...