/*++ Copyright (c) 2016 Minoca Corp. This file is licensed under the terms of the GNU General Public License version 3. Alternative licensing terms are available. Contact info@minocacorp.com for details. See the LICENSE file at the root of this project for complete licensing information. Module Name: yygenp.h Abstract: This header contains internal definitions for the grammar generator library. Author: Evan Green 9-Apr-2016 --*/ // // ------------------------------------------------------------------- Includes // #include #include #include #include #include // // ---------------------------------------------------------------- Definitions // #define YYGEN_BITS_PER_WORD (sizeof(ULONG) * BITS_PER_BYTE) // // This macro computes the number of words needed to accomodate a bitmap that // holds at least the given number of bits. // #define YYGEN_BITMAP_WORD_COUNT(_Bits) \ (((_Bits) + (YYGEN_BITS_PER_WORD - 1)) / YYGEN_BITS_PER_WORD) // // This macro sets a bit in the bitmap. // #define YYGEN_BITMAP_SET(_Row, _Bit) \ (((PULONG)(_Row))[(_Bit) / YYGEN_BITS_PER_WORD] |= \ 1 << ((_Bit) & (YYGEN_BITS_PER_WORD - 1))) // // This macro evaluates to non-zero if the given bit is set in the bitmap. // #define YYGEN_BITMAP_IS_SET(_Row, _Bit) \ ((((PULONG)(_Row))[(_Bit) / YYGEN_BITS_PER_WORD] & \ (1 << ((_Bit) & (YYGEN_BITS_PER_WORD - 1)))) != 0) // // ------------------------------------------------------ Data Type Definitions // typedef enum _YY_ACTION_CODE { YyActionInvalid, YyActionShift, YyActionReduce } YY_ACTION_CODE, *PYY_ACTION_CODE; typedef enum _YYGEN_SUPPRESSION { YyNotSuppressed, YySuppressedNoisily, YySuppressedQuietly } YYGEN_SUPPRESSION, *PYYGEN_SUPPRESSION; typedef YY_VALUE YY_RULE_INDEX, *PYY_RULE_INDEX; typedef YY_VALUE YY_ITEM_INDEX, *PYY_ITEM_INDEX; typedef YY_VALUE YY_STATE_INDEX, *PYY_STATE_INDEX; typedef YY_VALUE YY_GOTO_INDEX, *PYY_GOTO_INDEX; typedef YY_VALUE YY_ACTION_INDEX, *PYY_ACTION_INDEX; typedef struct _YYGEN_STATE YYGEN_STATE, *PYYGEN_STATE; typedef struct _YYGEN_SHIFTS YYGEN_SHIFTS, *PYYGEN_SHIFTS; typedef struct _YYGEN_REDUCTIONS YYGEN_REDUCTIONS, *PYYGEN_REDUCTIONS; typedef struct _YYGEN_ACTION YYGEN_ACTION, *PYYGEN_ACTION; /*++ Structure Description: This structure defines an individual grammar rule. Members: LeftSide - Stores the left side of the rule. RightSide - Stores an index into the items array where the right side of this rule resides. Precedence - Stores the precedence for the rule. Associativity - Stores an associativity for the rule. Used - Stores a boolean indicating whether or not the rules were used. --*/ typedef struct _YYGEN_RULE { YY_VALUE LeftSide; YY_ITEM_INDEX RightSide; ULONG Precedence; YY_ASSOCIATIVITY Associativity; BOOL Used; } YYGEN_RULE, *PYYGEN_RULE; /*++ Structure Description: This structure contains the core state structure of the LR(0) state machine. Members: Next - Stores a pointer to the next state globally in the state machine. Link - Stores a pointer to next element in this bucket in the hash table of states. Number - Stores the state number. AccessingSymbol - Stores the shift symbol that causes entrance into this state. ItemCount - Stores the number of elements in the items array. Items - Stores an array of indices into the item array representing the right hand sides of all the rules in this state. --*/ struct _YYGEN_STATE { PYYGEN_STATE Next; PYYGEN_STATE Link; YY_STATE_INDEX Number; YY_VALUE AccessingSymbol; YY_VALUE ItemsCount; PYY_ITEM_INDEX Items; }; /*++ Structure Description: This structure contains the set of reductions for a state in the LR(0) state machine. Members: Next - Stores a pointer to the next set of reductions globally in the state machine. Number - Stores the state number these reductions correspond to. Count - Stores the number of elements in the rules array. Rules - Stores the set of rules that reduce in this state. --*/ struct _YYGEN_REDUCTIONS { PYYGEN_REDUCTIONS Next; YY_STATE_INDEX Number; YY_VALUE Count; PYY_RULE_INDEX Rules; }; /*++ Structure Description: This structure descibes the set of shifts out of a given state. Members: Next - Stores a pointer to the next set of shifts in the state machine. Number - Stores the state number of the shifts. Count - Stores the number of shift states in the array. States - Stores an array of state numbers to possible next states, sorted. --*/ struct _YYGEN_SHIFTS { PYYGEN_SHIFTS Next; YY_STATE_INDEX Number; YY_VALUE Count; PYY_STATE_INDEX States; }; /*++ Structure Description: This structure descibes a parser action. Members: Next - Stores a pointer to the next action. Symbol - Stores the action symbol. Number - Stores the action index. Precedence - Stores the action precedence. Associativity - Stores the associativity of the action. Code - Stores the action type: shift or reduce. Suppression - Stores the suppression state of this action. --*/ struct _YYGEN_ACTION { PYYGEN_ACTION Next; YY_VALUE Symbol; YY_ACTION_INDEX Number; YY_VALUE Precedence; YY_ASSOCIATIVITY Associativity; YY_ACTION_CODE Code; YYGEN_SUPPRESSION Suppression; }; /*++ Structure Description: This structure contains the working state for the grammar generator. Members: Flags - Stores the global flags. See YYGEN_FLAG_* definitions. Elements - Stores the array of elements. VariablePrefix - Stores the prefix to prepend to all the variable names. OutputFileName - Stores the name of the output file, which is printed in the output source. TokenCount - Stores the first invalid token number. Any value below this is assumed to be a token. SymbolCount - Stores the number of tokens plus non-terminals. NonTerminalCount - Stores the number of non-terminals, including the start symbol. StartSymbol - Stores the starting symbol of the grammar. ItemCount - Stores the total count of all the elements in all the rules. RuleCount - Stores the number of rules. Nullable - Stores an array of booleans indexed by symbol that indicates if that production is empty. Items - Stores an array of all right sides of all rules. This establishes a total order of item sets by rule. The arrays are also terminated by a negative number, the rule index. Rules - Stores an array of rules. Derives - Stores an array of pointers to the set of rules for each left hand side. That is, these are indices into the rules array for each production. This is index by symbol. ItemSet - Stores the item set for the state currently being built. ItemSetEnd - Stores the end of the current item set. RuleSet - Stores a bitmap of the rule set. FirstDerives - Stores an array of bitmaps. Each column represents a rule, and the rows are the non-terminals. The bitmap describes the rules in the FIRST set for each production. The FIRST set is the set of non-terminals that can appear first for any production. FirstState - Stores a pointer to the first state in the LR(0) state machine. StateCount - Stores the number of states in the LR(0) state machine. FirstReduction - Stores the head of the singly linked list of reductions. LastReduction - Stores the tail of the singly linked list of reductions. FirstShift - Stores the head of the singly linked list of shifts. LastShift - Stores the tail of the singly linked list of shifts. StateTable - Stores a pointer to the final states. AccessingSymbol - Stores an array of shift symbols that cause entrance to the state at each index. ShiftTable - Stores an array of shifts to other states, indexed by starting state. ReductionTable - Stores an array of reductions at each state. Lookaheads - Stores the array of indices into the lookahead sets, indexed by state. That is, for a given state, the element in this array shows where in the lookahead sets array to begin. LookaheadSets - Stores an array of token (terminal) bitmaps showing the lookaheads for every reduction in every state. LookaheadRule - Stores an array that runs parallel to the lookahead sets pointing back to a rule for the array index. GotoMap - Stores an array of indices into the FromState/ToState arrays where the gotos using a particular non-terminal symbol start. That is, given a symbol (minus the number of tokens), this array shows the index to start looking in the FromState/ToState arrays for gotos using this symbol. FromState - Stores the array of starting states for all the gotos. ToState - Stores the array of destination goto states, running parallel to the FromState array. Parser - Stores the combined action table. FinalState - Stores the state index of the "accept" state. UnusedRules - Stores the count of unused rules. ShiftReduceConflicts - Stores an array of counts of shift-reduce conflicts for each state. ReduceReduceConflicts - Stores an array of counts of reduce-reduce conflicts for each state. ShiftReduceConflictCount - Stores the total number of shift-reduce conflicts. ReduceReduceConflictCount - Stores the total number of reduce-reduce conflicts. ExpectedShiftReduceConflicts - Stores the expected number of shift-reduce conflicts. ExpectedReduceReduceConflicts - Stores the expected number of reduce-reduce conflicts. DefaultReductions - Stores the table of rules to reduce by, indexed by state. --*/ struct _YYGEN_CONTEXT { ULONG Flags; PYY_ELEMENT Elements; PSTR VariablePrefix; PSTR OutputFileName; YY_VALUE TokenCount; YY_VALUE SymbolCount; YY_VALUE NonTerminalCount; YY_VALUE StartSymbol; ULONG ItemCount; ULONG RuleCount; PBOOL Nullable; PYY_VALUE Items; PYYGEN_RULE Rules; PYY_RULE_INDEX Derives; PYY_ITEM_INDEX ItemSet; PYY_ITEM_INDEX ItemSetEnd; PULONG RuleSet; PULONG FirstDerives; PYYGEN_STATE FirstState; YY_STATE_INDEX StateCount; PYYGEN_REDUCTIONS FirstReduction; PYYGEN_REDUCTIONS LastReduction; PYYGEN_SHIFTS FirstShift; PYYGEN_SHIFTS LastShift; PYYGEN_STATE *StateTable; PYY_VALUE AccessingSymbol; PYYGEN_SHIFTS *ShiftTable; PYYGEN_REDUCTIONS *ReductionTable; PYY_VALUE Lookaheads; PULONG LookaheadSets; PYY_RULE_INDEX LookaheadRule; PYY_GOTO_INDEX GotoMap; PYY_STATE_INDEX FromState; PYY_STATE_INDEX ToState; PYYGEN_ACTION *Parser; YY_STATE_INDEX FinalState; ULONG UnusedRules; PYY_VALUE ShiftReduceConflicts; PYY_VALUE ReduceReduceConflicts; YY_VALUE ShiftReduceConflictCount; YY_VALUE ReduceReduceConflictCount; YY_VALUE ExpectedShiftReduceConflicts; YY_VALUE ExpectedReduceReduceConflicts; PYY_RULE_INDEX DefaultReductions; }; // // -------------------------------------------------------------------- Globals // // // -------------------------------------------------------- Function Prototypes // YY_STATUS YypGenerateLr0Grammar ( PYYGEN_CONTEXT Context ); /*++ Routine Description: This routine generates an LR(0) grammar based on the description. Arguments: Context - Supplies a pointer to the generator context. Return Value: YY status. --*/ VOID YypEstablishClosure ( PYYGEN_CONTEXT Context, PYYGEN_STATE State ); /*++ Routine Description: This routine creates a closure on the itemset of the current state. Arguments: Context - Supplies a pointer to the generator context. State - Supplies a pointer to the state to create the closure of. Return Value: None. --*/ YY_STATUS YypGenerateLalr ( PYYGEN_CONTEXT Context ); /*++ Routine Description: This routine generates an LALR(1) state machine based on an LR(0) state machine. Arguments: Context - Supplies a pointer to the generator context. Return Value: YY status. --*/ YY_STATUS YypBuildParser ( PYYGEN_CONTEXT Context ); /*++ Routine Description: This routine generates the parser data structures based on the LALR(1) construction. Arguments: Context - Supplies a pointer to the generator context. Return Value: YY status. --*/ PVOID YypAllocate ( UINTN Size ); /*++ Routine Description: This routine allocates and clears a region of memory. Arguments: Size - Supplies the size in bytes of the allocation. Return Value: Returns a pointer to the new memory on success. NULL on failure. --*/ PVOID YypReallocate ( PVOID Allocation, UINTN NewSize ); /*++ Routine Description: This routine reallocates previously allocated memory. Arguments: Allocation - Supplies an optional pointer to the memory to reallocate. NewSize - Supplies the desired size of the allocation. Return Value: Returns a pointer to the newly sized buffer on success. This might be the same buffer passed in or a new buffer. The old buffer will be invalid after this. NULL on reallocation failure. The old buffer will remain valid and still needs to be freed. --*/ VOID YypFree ( PVOID Allocation ); /*++ Routine Description: This routine frees a previously allocated region of memory. Arguments: Allocation - Supplies a pointer to the allocation to free. Return Value: None. --*/