Vectorized LR parsing of computer programs

• US 5,193,192 A
• Filed: 08/23/1990
• Issued: 03/09/1993
• Est. Priority Date: 12/29/1989
• Status: Expired due to Term

• Current Assignee: RPX Corporation
• Original Assignee: Supercomputer Systems Limited Partnership
• Inventors: Seberger, David A.
• Primary Examiner(s): Kulik, Paul V.
• Application Number:
  US07/571,502
• Time in Patent Office: 929 Days
• Field of Search: 395/700, 364/419
• US Class Current: 717/143
• CPC Class Codes: B44C 5/02 Mountings for pictures; Mountings of horns on plates
• CPC Class Codes: G06F 12/023 Free address space management
• CPC Class Codes: G06F 12/08 in hierarchically structured memory systems, e.g. virtual memory systems
• CPC Class Codes: G06F 12/12 Replacement control
• CPC Class Codes: G06F 8/41 Compilation
• CPC Class Codes: G06F 8/427 Parsing
• CPC Class Codes: G06F 8/433 Dependency analysis; Data or control flow analysis
• CPC Class Codes: G06F 8/445 Exploiting fine grain parallelism, i.e. parallelism at instruction level run-time instruction scheduling G06F9/3836
• CPC Class Codes: G06F 8/45 Exploiting coarse grain parallelism in compilation, i.e. parallelism between groups of instructions
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

A parser for parsing computer programs in a compiler has parsing tables arranged as linear vectors. In a reduction portion of the parser, a production table and a lookahead set table have paired entries at identical address offsets such that a one-to-one relationship exists between each lookahead set in the lookahead set table and the representation of the lookahead set in the lookahead set table. In a read transition portion of the parser, an entrance symbol table has entries paired with transition state representations and each pair being at an identical address offset in the respective tables. For a reduction or read transition operation, the lookahead set table or the entrance symbol table is scanned to find the appropriate entry. Once the appropriate entry is found, the production table or the transition state table is addressed using the offset of the appropriate entry found during the scanning process.

Claims

1. In a machine-effected method of operating a parser portion of a compiler for parsing a computer program in an input stream, said computer program being written in a predetermined programming language having a given grammar, including the machine-executed steps of:

automatically generating a parser state table means having a plurality of state indicating entries, one entry means for indicating each possible state of the parser, each of said state indicating entries including a declaration of said predetermined programming language in said given grammar;

automatically generating a linearized vector table means having an input table including a given plurality of input entries respectively related to the parser state table means entries such that one or more of the input entries relate to a one of the state indicating entries, respectively, and an output table having a predetermined plurality of output entries, arranged said output entries to be identically addressable within the output table as the input entries are respectively addressed within the input table, said predetermined plurality of being equal to said given plurality; and

parsing the computer program in the input stream using the established parser state table means and said linearized table means.

2. In the machine-effected method set forth in claim 1 further including the machine-executed steps of:

while generating the linearized table means, generating a given plurality of independent portions in the linearized table means, each said portion having a separate input table and an output table, arranging said input table and said output table in each said portion of the linearized table means to be identically addressable, respectively;

during said parsing step, identifying a program sentence in the computer program; and

processing an identified program sentence using one of said plurality of independent portions.

3. In the machine-effected method set forth in claim 2, wherein the parsing includes read transitions between reduction steps, further including the machine-executed steps of:

in said step for generating said linearized table means, generating a reduction portion as a first one of the independent portions for reducing the identified program sentence; and

in said step for generating said linearized table means, generating a read transition portion as a second one of the independent portions for processing said read transitions.

4. In the machine-effected method set forth in claim 3 further including the machine-executed steps of:

generating a production table that defines reductions for tokens being analyzed to be the input table of said reduction portion, generating a lookahead set table having sets of predetermined terminal symbols to be the output table of said reduction portion; and

generating a table of entrance symbols as the input table in said read transition portion and generating a transition state table as the output table in said read transition portion.

5. In the machine-effected method set forth in claim 4 further including the machine-executed steps of:

performing said parsing step as a parse loop including automatically selecting a reduction loop or a transition loop;

in said reduction loop using only the reduction portion of said linearized table means including detecting a FINAL STATE for ending the parsing; and

in said transition loop using only the transition portion of said linearized table means and always performing a reduction loop before ending the parsing.

6. In a machine-effected method of parsing a computer program in an input stream having tokens in the input stream that represent a sequence of structure of the computer program, during said parsing, sequentially creating parser states that respectively indicate status of the syntactical analysis for verifying structure and specification of the computer program expressions, one of said parsing states being a current parser state that indicates a current parsing step, including the machine-executed steps of:

generating first look tables, each of said first look tables including entries in said first look tables for identifying the parser states;

linear vector parsing means including generating an input means and generating input indicia in said input means such that each of the input indicia are in respective vectors, generating addresses for the input means having addresses respectively addressable from the first look tables, generating an output means including generating output indicia in said output means respectively in the same vectors as the input indicia; and

parsing the computer program of the input stream including detecting a current parser state in the first look tables, then scanning the input indicia identifiable with the current parser state and then taking the output indicia in the respective vectors of the input indicia for reading a predetermined token from the input stream.

7. In the machine-effected method set forth in claim 6 further including a the machine-executed steps of:

in said linear vector parsing means output means, generating a given plurality of independent portions, and, in each of said independent portions, generating a separate input table and an output table including generating identical addresses for said input and output tables in each of said generated independent portions;

during said parsing step, identifying a program sentence in the computer program; and

parsing the identified program sentence using only one of said plurality of independent portions.

8. In the machine-effected method set forth in claim 7 further including the machine-executed steps of:

in said output table means, generating a reduction portion in one of the independent portions for reducing the identified program sentence; and

in said output table means, generating a read transition portion in a second one of the independent portions for processing read transitions.

9. In the machine-effected method set forth in claim 8 further including the machine-executed steps of:

in said reduction portion, generating a table of productions for defining reductions and a lookahead set table, generating entries in each of said reduction portion and lookahead set table at a same offset in said reduction portion and lookahead set table, respectively, for creating pairs of said respective reduction generated entries and respective generated entries in the lookahead set table; and

in said read transition portion, generating table of entrance symbols for respectively representing a predetermined number of entrances to the parser states and generating a transition state table having a number of transition states equal to said predetermined number of entrance symbols, placing the entrance symbols and the transition states in the respective table of entrance symbols and transition state table at identical offsets for creating pairs so that a scan of the entrance symbols identifies the offset in the transition table of its identified transition state whereby a single scan of the entrance symbol table identifies an offset in the transition state table of the respective identified transition state.

10. In the machine-effected method set forth in claim 9 further including the machine-executed steps of:

performing said parsing step as a parse loop including automatically selecting a reduction loop or a transition loop;

in said reduction loop using only the table of productions and the lookahead set table and detecting a FINAL STATE for ending the parsing; and

in said transition loop using only the table of entrance symbols and the transition state table and always performing a reduction loop before ending the parsing.

11. In apparatus for parsing a computer program, including, in combination:

state means for indicating a current parser state;

reduction means for reducing program expressions and including a production table having a first number of productions and a lookahead set table having a second number of lookahead set entries, said second number being equal to said first number, each of the productions being paired with a respective one of the lookahead set entries and each respective paired lookahead set and production having an identical offset address in the respective tables in the reduction means;

read transition means for identifying read transitions in the computer program parsing and including an entrance symbol table having a second number of entrance symbols for entering respective ones of the parser states and a transition state table having a second number of representations of transition states, each of the entrance symbols being paired with a respective one of the transition states and being at an address offset in the entrance symbol table identical to the address offset of the respective paired representation of transition states; and

parse loop means connected to the state means, to the reduction means and to the read transition means for activating either the reduction means or the read transition means for each state indicated in the state means and including changing the state indicated in the state means only when the transition means is used.