Browse Prior Art Database

Creating Compiler Tables with Variable Length Rows

IP.com Disclosure Number: IPCOM000115327D
Original Publication Date: 1995-Apr-01
Included in the Prior Art Database: 2005-Mar-30
Document File: 2 page(s) / 60K

Publishing Venue

IBM

Related People

Feriozi, DT: AUTHOR

Abstract

Described is a method of creating tables with variable length rows for use in computer compiler development. Described is the use of variable length rows in an LL(1) parser.

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

Creating Compiler Tables with Variable Length Rows

      Described is a method of creating tables with variable length
rows for use in computer compiler development.  Described is the use
of variable length rows in an LL(1) parser.

      Many programming applications have a need for an efficient way
to store a table of values in which the length of the rows is
variable.  One such application is an LL(1) parser.  The LL(1)
parsing algorithm requires a table of reversed productions that are
pushed onto a parse stack.  Each production is a row in the table.
The length of the productions varies widely from zero to fifteen
elements, or more.  Since processing the table is a significant part
of the LL(1) algorithm, both storage of and access to the table must
be efficient so that production table processing will not be a
performance bottleneck in the system.  To achieve efficient variable
length tables, the concept described herein uses a one dimensional
array of pointers to dynamically allocated rows.

      The method borrows from the standard C programming language
utilizing a null character as a string terminator.  This makes the
string processing efficient because a string length is not needed.
The only condition is that the null character must not be needed as a
valid string member.  When a string is moved from one area to
another, the end of the string is detected by testing for the null
character as each character is moved, rather than by decrementing a
counter and then testing it for zero.

      The elements of a production table a...