123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585 |
- /*++
- 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 <stdio.h>
- #include <minoca/lib/types.h>
- #include <minoca/lib/status.h>
- #include <minoca/lib/yy.h>
- #include <minoca/lib/yygen.h>
- //
- // ---------------------------------------------------------------- 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.
- --*/
|