123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541 |
- /*++
- 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:
- yygen.c
- Abstract:
- This module implements the Minoca grammar generator.
- Author:
- Evan Green 9-Apr-2016
- Environment:
- Build
- --*/
- //
- // ------------------------------------------------------------------- Includes
- //
- #include "yygenp.h"
- #include <stdlib.h>
- #include <string.h>
- //
- // ---------------------------------------------------------------- Definitions
- //
- //
- // ------------------------------------------------------ Data Type Definitions
- //
- //
- // ----------------------------------------------- Internal Function Prototypes
- //
- YY_STATUS
- YypInitializeGeneratorContext (
- PYYGEN_CONTEXT Context
- );
- //
- // -------------------------------------------------------------------- Globals
- //
- //
- // ------------------------------------------------------------------ Functions
- //
- YY_STATUS
- YyGenerateGrammar (
- PYY_GRAMMAR_DESCRIPTION Description,
- ULONG Flags,
- PYYGEN_CONTEXT *NewContext
- )
- /*++
- Routine Description:
- This routine converts a given grammar description into an LALR(1) grammar.
- Arguments:
- Description - Supplies a pointer to the grammar description.
- Flags - Supplies a bitfield of flags. See YYGEN_FLAG_* definitions.
- NewContext - Supplies a pointer where a pointer to the grammar context will
- be returned on success.
- Return Value:
- YY status.
- --*/
- {
- PYYGEN_CONTEXT Context;
- YY_STATUS YyStatus;
- Context = YypAllocate(sizeof(YYGEN_CONTEXT));
- if (Context == NULL) {
- YyStatus = YyStatusNoMemory;
- goto GenerateGrammarEnd;
- }
- memset(Context, 0, sizeof(YYGEN_CONTEXT));
- Context->Flags = Flags;
- Context->Elements = Description->Elements;
- Context->TokenCount = Description->TokenCount;
- Context->SymbolCount = Description->SymbolCount;
- Context->ExpectedShiftReduceConflicts =
- Description->ExpectedShiftReduceConflicts;
- Context->ExpectedReduceReduceConflicts =
- Description->ExpectedReduceReduceConflicts;
- Context->VariablePrefix = Description->VariablePrefix;
- Context->OutputFileName = Description->OutputFileName;
- YyStatus = YypInitializeGeneratorContext(Context);
- if (YyStatus != YyStatusSuccess) {
- goto GenerateGrammarEnd;
- }
- //
- // Start by creating the LR(0) parser.
- //
- YyStatus = YypGenerateLr0Grammar(Context);
- if (YyStatus != YyStatusSuccess) {
- goto GenerateGrammarEnd;
- }
- //
- // Augment with lookaheads to produce an LALR(1) parser.
- //
- YyStatus = YypGenerateLalr(Context);
- if (YyStatus != YyStatusSuccess) {
- goto GenerateGrammarEnd;
- }
- //
- // Allocate and initialize the parser constructs.
- //
- YyStatus = YypBuildParser(Context);
- if (YyStatus != YyStatusSuccess) {
- goto GenerateGrammarEnd;
- }
- GenerateGrammarEnd:
- if (YyStatus != YyStatusSuccess) {
- if (Context != NULL) {
- YyDestroyGeneratorContext(Context);
- Context = NULL;
- }
- }
- *NewContext = Context;
- return YyStatus;
- }
- VOID
- YyDestroyGeneratorContext (
- PYYGEN_CONTEXT Context
- )
- /*++
- Routine Description:
- This routine destroys a grammar generator context structure.
- Arguments:
- Context - Supplies a pointer to the generator context.
- Return Value:
- None.
- --*/
- {
- PYYGEN_ACTION Action;
- YY_VALUE Index;
- PVOID Next;
- PYYGEN_REDUCTIONS Reduction;
- PYYGEN_SHIFTS Shift;
- PYYGEN_STATE State;
- if (Context->Nullable != NULL) {
- YypFree(Context->Nullable);
- }
- if (Context->Items != NULL) {
- YypFree(Context->Items);
- }
- if (Context->Rules != NULL) {
- YypFree(Context->Rules);
- }
- if (Context->Derives != NULL) {
- YypFree(Context->Derives);
- }
- if (Context->ItemSet != NULL) {
- YypFree(Context->ItemSet);
- }
- if (Context->RuleSet != NULL) {
- YypFree(Context->RuleSet);
- }
- if (Context->FirstDerives != NULL) {
- YypFree(Context->FirstDerives);
- }
- if (Context->StateTable != NULL) {
- YypFree(Context->StateTable);
- }
- State = Context->FirstState;
- while (State != NULL) {
- Next = State->Next;
- YypFree(State);
- State = Next;
- }
- if (Context->ShiftTable != NULL) {
- YypFree(Context->ShiftTable);
- }
- Shift = Context->FirstShift;
- while (Shift != NULL) {
- Next = Shift->Next;
- YypFree(Shift);
- Shift = Next;
- }
- if (Context->ReductionTable != NULL) {
- YypFree(Context->ReductionTable);
- }
- Reduction = Context->FirstReduction;
- while (Reduction != NULL) {
- Next = Reduction->Next;
- YypFree(Reduction);
- Reduction = Next;
- }
- if (Context->Lookaheads != NULL) {
- YypFree(Context->Lookaheads);
- }
- if (Context->LookaheadSets != NULL) {
- YypFree(Context->LookaheadSets);
- }
- if (Context->LookaheadRule != NULL) {
- YypFree(Context->LookaheadRule);
- }
- if (Context->GotoMap != NULL) {
- YypFree(Context->GotoMap);
- }
- if (Context->FromState != NULL) {
- YypFree(Context->FromState);
- }
- if (Context->ToState != NULL) {
- YypFree(Context->ToState);
- }
- if (Context->Parser != NULL) {
- for (Index = 0; Index < Context->StateCount; Index += 1) {
- Action = Context->Parser[Index];
- while (Action != NULL) {
- Next = Action->Next;
- YypFree(Action);
- Action = Next;
- }
- }
- YypFree(Context->Parser);
- }
- if (Context->ShiftReduceConflicts != NULL) {
- YypFree(Context->ShiftReduceConflicts);
- }
- if (Context->ReduceReduceConflicts != NULL) {
- YypFree(Context->ReduceReduceConflicts);
- }
- if (Context->DefaultReductions != NULL) {
- YypFree(Context->DefaultReductions);
- }
- YypFree(Context);
- return;
- }
- VOID
- YyGetConflictCounts (
- PYYGEN_CONTEXT Context,
- PYY_VALUE ShiftReduceConflicts,
- PYY_VALUE ReduceReduceConflicts
- )
- /*++
- Routine Description:
- This routine returns the number of conflicts in the grammar, minus the
- number of expected conflicts.
- Arguments:
- Context - Supplies a pointer to the generator context.
- ShiftReduceConflicts - Supplies an optional pointer where the number of
- shift-reduce conflicts will be returned.
- ReduceReduceConflicts - Supplies an optional pointer where the number of
- reduce-reduce conflicts will be returned.
- Return Value:
- None.
- --*/
- {
- if (ShiftReduceConflicts != NULL) {
- *ShiftReduceConflicts = Context->ShiftReduceConflictCount -
- Context->ExpectedShiftReduceConflicts;
- }
- if (ReduceReduceConflicts != NULL) {
- *ReduceReduceConflicts = Context->ReduceReduceConflictCount -
- Context->ExpectedReduceReduceConflicts;
- }
- return;
- }
- 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 Allocation;
- Allocation = calloc(Size, 1);
- return Allocation;
- }
- 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.
- --*/
- {
- PVOID NewAllocation;
- NewAllocation = realloc(Allocation, NewSize);
- return NewAllocation;
- }
- 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.
- --*/
- {
- free(Allocation);
- return;
- }
- //
- // --------------------------------------------------------- Internal Functions
- //
- YY_STATUS
- YypInitializeGeneratorContext (
- PYYGEN_CONTEXT Context
- )
- /*++
- Routine Description:
- This routine initializes a grammar context structure.
- Arguments:
- Context - Supplies a pointer to the generator context.
- Return Value:
- YY status.
- --*/
- {
- PYY_VALUE Components;
- YY_VALUE ElementIndex;
- YY_VALUE ItemCount;
- YY_VALUE RuleCount;
- //
- // Verify that the tokens do not have productions.
- //
- for (ElementIndex = 0;
- ElementIndex < Context->TokenCount;
- ElementIndex += 1) {
- if (Context->Elements[ElementIndex].Components != NULL) {
- return YyStatusInvalidSpecification;
- }
- }
- if (Context->SymbolCount <= Context->TokenCount) {
- return YyStatusInvalidSpecification;
- }
- if (Context->Elements[ElementIndex].Components != NULL) {
- return YyStatusInvalidSpecification;
- }
- //
- // Count the productions and items. There are 3 extra rules:
- // Rule 0 is invalid (since it can't be negated).
- // Rule 1 is empty.
- // Rule 2 is the start rule.
- // Token zero is always assumed to be the end-of-file marker.
- //
- ItemCount = 4;
- RuleCount = 3;
- for (ElementIndex = Context->TokenCount + 1;
- ElementIndex < Context->SymbolCount;
- ElementIndex += 1) {
- if ((Context->Elements[ElementIndex].Flags & YY_ELEMENT_START) != 0) {
- if (Context->StartSymbol != 0) {
- return YyStatusInvalidSpecification;
- }
- Context->StartSymbol = ElementIndex;
- }
- Components = Context->Elements[ElementIndex].Components;
- if (Components == NULL) {
- return YyStatusInvalidSpecification;
- }
- while (*Components != 0) {
- if (*Components < 0) {
- RuleCount += 1;
- }
- ItemCount += 1;
- Components += 1;
- }
- }
- Context->ItemCount = ItemCount;
- Context->RuleCount = RuleCount;
- //
- // The first symbol is the start symbol.
- //
- Context->NonTerminalCount = Context->SymbolCount - Context->TokenCount;
- return YyStatusSuccess;
- }
|