Configuration-preserving preprocessor and configuration-preserving parser

A method for configuration preserving parsing for a grammar of a language using a parser comprising one or more subparsers and one or more merged parsers, the method comprising:

• parsing a plurality of tokens, wherein the plurality of tokens comprise language tokens and conditional tokens, wherein various configurations are possible based upon the conditional tokens, wherein the parser comprises a head and a stack, wherein the stack comprises previously parsed tokens, and wherein the head comprises a current token;
• creating, for each conditional token in the plurality of tokens using a processor, a token follow-set consisting of each possible language token that can immediately follow the conditional token;
• determining, for each conditional token, whether to fork a subparser for the conditional token in each of the token follow-sets, wherein the subparser parses a portion of the plurality of tokens including a token from the token follow-set of the conditional token;
• forking one or more subparsers based upon determining whether to fork a subparser for the conditional token in each of the token follow-sets, wherein each of the one or more subparsers have the same parser stack and comprises one or more previously parsed tokens up to and including the conditional token used to fork the one or more subparsers, wherein each of the one or more subparsers includes a presence condition based on the conditional token and a head that are unique to other subparsers, wherein each subparser has a head that is a token from the token follow-set, and wherein each subparser represents a distinct configuration associated with the presence condition;
• merging two or more subparsers into a merged parser when the two or more subparsers have the same head and stack, wherein a presence condition for the merged parser is a disjunction of the presence conditions of the two or more subparsers, and wherein a head of the merged parser is the head of the two or more subparsers;
• and
• generating a syntax tree from the plurality of tokens that preserves all possible configurations based upon the subparsers and the merged parser.

The method of 5, further comprising:

• determining if each token in the token follow-set will result in a shift;
• forking a single sub-parser based upon the token follow-set;
• and
• delaying forking remaining sub-parsers from the token follow-set based upon the determining that each token in the token follow-set will result in a shift.

A non-transitory computer-readable medium having instructions stored thereon, the instructions for configuration preserving parsing for a grammar of a language using a parser comprising one or more subparsers and one or more merged parsers, the instructions comprising:

• instructions to parse a plurality of tokens, wherein the plurality of tokens comprise language tokens and conditional tokens, wherein various configurations are possible based upon the conditional tokens, wherein the parser comprises a head and a stack, wherein the stack comprises previously parsed tokens, and wherein the head comprises a current token;
• instructions to create, for each conditional token in the plurality of tokens, a token follow-set consisting of each possible language token that can immediately follow the conditional token;
• instructions to determine, for each conditional token, whether to fork a subparser for the conditional token in each of the token follow-sets, wherein the subparser parses a portion of the plurality of tokens including a token from the token follow-set of the conditional token;
• instructions to fork one or more subparsers based upon determining whether to fork a subparser for the conditional token in each of the token follow-sets, wherein each of the one or more subparsers have the same parser stack and comprises one or more previously parsed tokens up to and including the conditional token used to fork the one or more subparsers, wherein each of the one or more subparsers includes a presence condition based on the conditional token and a head that are unique to other subparsers, wherein each subparser has a head that is a token from the token follow-set, and wherein each subparser represents a distinct configuration associated with the presence condition;
• instructions to merge two or more subparsers into a merged parser when the two or more subparsers have the same head and stack, wherein a presence condition for the merged parser is a disjunction of the presence conditions of the two or more subparsers, and wherein a head of the merged parser is the head of the two or more subparsers;
• and
• instructions to generate a syntax tree from the plurality of tokens that preserves all possible configurations based upon the subparsers and the merged parser.