Return to state.h CVS log

Up to [Apple XNU] / GNUtools / bison

Annotation of GNUtools/bison/state.h, revision 1.1

1.1     ! root        1: /* Type definitions for nondeterministic finite state machine for bison,
        !             2:    Copyright (C) 1984, 1989 Free Software Foundation, Inc.
        !             3: 
        !             4: This file is part of Bison, the GNU Compiler Compiler.
        !             5: 
        !             6: Bison is free software; you can redistribute it and/or modify
        !             7: it under the terms of the GNU General Public License as published by
        !             8: the Free Software Foundation; either version 2, or (at your option)
        !             9: any later version.
        !            10: 
        !            11: Bison is distributed in the hope that it will be useful,
        !            12: but WITHOUT ANY WARRANTY; without even the implied warranty of
        !            13: MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
        !            14: GNU General Public License for more details.
        !            15: 
        !            16: You should have received a copy of the GNU General Public License
        !            17: along with Bison; see the file COPYING.  If not, write to
        !            18: the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  */
        !            19: 
        !            20: 
        !            21: /* These type definitions are used to represent a nondeterministic
        !            22:    finite state machine that parses the specified grammar.
        !            23:    This information is generated by the function generate_states
        !            24:    in the file LR0.
        !            25: 
        !            26: Each state of the machine is described by a set of items --
        !            27: particular positions in particular rules -- that are the possible
        !            28: places where parsing could continue when the machine is in this state.
        !            29: These symbols at these items are the allowable inputs that can follow now.
        !            30: 
        !            31: A core represents one state.  States are numbered in the number field.
        !            32: When generate_states is finished, the starting state is state 0
        !            33: and nstates is the number of states.  (A transition to a state
        !            34: whose state number is nstates indicates termination.)  All the cores
        !            35: are chained together and first_state points to the first one (state 0).
        !            36: 
        !            37: For each state there is a particular symbol which must have been the
        !            38: last thing accepted to reach that state.  It is the accessing_symbol
        !            39: of the core.
        !            40: 
        !            41: Each core contains a vector of nitems items which are the indices
        !            42: in the ritems vector of the items that are selected in this state.
        !            43: 
        !            44: The link field is used for chaining buckets that hash states by
        !            45: their itemsets.  This is for recognizing equivalent states and
        !            46: combining them when the states are generated.
        !            47: 
        !            48: The two types of transitions are shifts (push the lookahead token
        !            49: and read another) and reductions (combine the last n things on the
        !            50: stack via a rule, replace them with the symbol that the rule derives,
        !            51: and leave the lookahead token alone).  When the states are generated,
        !            52: these transitions are represented in two other lists.
        !            53: 
        !            54: Each shifts structure describes the possible shift transitions out
        !            55: of one state, the state whose number is in the number field.
        !            56: The shifts structures are linked through next and first_shift points to them.
        !            57: Each contains a vector of numbers of the states that shift transitions
        !            58: can go to.  The accessing_symbol fields of those states' cores say what kind
        !            59: of input leads to them.
        !            60: 
        !            61: A shift to state zero should be ignored.  Conflict resolution
        !            62: deletes shifts by changing them to zero.
        !            63: 
        !            64: Each reductions structure describes the possible reductions at the state
        !            65: whose number is in the number field.  The data is a list of nreds rules,
        !            66: represented by their rule numbers.   first_reduction points to the list
        !            67: of these structures.
        !            68: 
        !            69: Conflict resolution can decide that certain tokens in certain
        !            70: states should explicitly be errors (for implementing %nonassoc).
        !            71: For each state, the tokens that are errors for this reason
        !            72: are recorded in an errs structure, which has the state number
        !            73: in its number field.  The rest of the errs structure is full
        !            74: of token numbers.
        !            75: 
        !            76: There is at least one shift transition present in state zero.
        !            77: It leads to a next-to-final state whose accessing_symbol is
        !            78: the grammar's start symbol.  The next-to-final state has one shift
        !            79: to the final state, whose accessing_symbol is zero (end of input).
        !            80: The final state has one shift, which goes to the termination state
        !            81: (whose number is nstates-1).
        !            82: The reason for the extra state at the end is to placate the parser's
        !            83: strategy of making all decisions one token ahead of its actions.  */
        !            84: 
        !            85: 
        !            86: typedef
        !            87:   struct core
        !            88:     {
        !            89:       struct core *next;
        !            90:       struct core *link;
        !            91:       short number;
        !            92:       short accessing_symbol;
        !            93:       short nitems;
        !            94:       short items[1];
        !            95:     }
        !            96:   core;
        !            97: 
        !            98: 
        !            99: 
        !           100: typedef
        !           101:   struct shifts
        !           102:     {
        !           103:       struct shifts *next;
        !           104:       short number;
        !           105:       short nshifts;
        !           106:       short shifts[1];
        !           107:     }
        !           108:   shifts;
        !           109: 
        !           110: 
        !           111: 
        !           112: typedef
        !           113:   struct errs
        !           114:     {
        !           115:       short nerrs;
        !           116:       short errs[1];
        !           117:     }
        !           118:   errs;
        !           119: 
        !           120: 
        !           121: 
        !           122: typedef
        !           123:   struct reductions
        !           124:     {
        !           125:       struct reductions *next;
        !           126:       short number;
        !           127:       short nreds;
        !           128:       short rules[1];
        !           129:     }
        !           130:   reductions;
        !           131: 
        !           132: 
        !           133: 
        !           134: extern int nstates;
        !           135: extern core *first_state;
        !           136: extern shifts *first_shift;
        !           137: extern reductions *first_reduction;

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.