Vectorized LR parsing of computer programs

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.

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.