1 /*
2   Copyright 2002-2004 John Plevyak, All Rights Reserved
3 */
4 #ifndef _parse_H_
5 #define _parse_H_
6 
7 #define NO_DPN ((D_ParseNode *)0x1)
8 #define DPN_TO_PN(_dpn) ((PNode *)(((char *)dpn) - (intptr_t)(&((PNode *)0)->parse_node)))
9 #define is_epsilon_PNode(_pn) ((_pn)->parse_node.start_loc.s == (_pn)->parse_node.end)
10 
11 /* #define TRACK_PNODES	1 */
12 
13 struct PNode;
14 struct SNode;
15 struct ZNode;
16 struct Parser;
17 
18 typedef Vec(struct ZNode *) VecZNode;
19 typedef Vec(VecZNode *) VecVecZNode;
20 typedef Vec(struct SNode *) VecSNode;
21 typedef Vec(struct PNode *) VecPNode;
22 
23 typedef struct PNodeHash {
24   struct PNode **v;
25   uint i; /* size index (power of 2) */
26   uint m; /* max size (highest prime < i ** 2) */
27   uint n; /* size */
28   struct PNode *all;
29 } PNodeHash;
30 
31 typedef struct SNodeHash {
32   struct SNode **v;
33   uint i; /* size index (power of 2) */
34   uint m; /* max size (highest prime < i ** 2) */
35   uint n; /* size */
36   struct SNode *all;
37   struct SNode *last_all;
38 } SNodeHash;
39 
40 typedef struct Reduction {
41   struct ZNode *znode;
42   struct SNode *snode;
43   struct D_Reduction *reduction;
44   struct SNode *new_snode;
45   int new_depth;
46   struct Reduction *next;
47 } Reduction;
48 
49 typedef struct Shift {
50   struct SNode *snode;
51   struct Shift *next;
52 } Shift;
53 
54 typedef struct Parser {
55   D_Parser user;
56   /* string to parse */
57   char *start, *end;
58   struct D_ParserTables *t;
59   /* statistics */
60   int states, pnodes, scans, shifts, reductions, compares, ambiguities;
61   /* parser state */
62   PNodeHash pnode_hash;
63   SNodeHash snode_hash;
64   Reduction *reductions_todo;
65   Shift *shifts_todo;
66   D_Scope *top_scope;
67   struct SNode *accept;
68   int last_syntax_error_line;
69   /* memory management */
70   Reduction *free_reductions;
71   Shift *free_shifts;
72   int live_pnodes;
73   struct PNode *free_pnodes;
74   struct SNode *free_snodes;
75   struct ZNode *free_znodes;
76   Vec(D_Reduction *) error_reductions;
77   ShiftResult *shift_results;
78   int nshift_results;
79   D_Shift *code_shifts;
80   int ncode_shifts;
81   /* comments */
82   struct Parser *whitespace_parser;
83   /* interface support */
84   void *pinterface1;
85 #ifdef TRACK_PNODES
86   struct PNode *xall;
87 #endif
88 } Parser;
89 
90 /*
91   Parse Node - the 'symbol' and the constructed parse subtrees.
92 */
93 typedef struct PNode {
94   uint hash;
95   AssocKind assoc;
96   int priority;
97   AssocKind op_assoc;
98   int op_priority;
99   D_Reduction *reduction;
100   D_Shift *shift;
101 #ifndef USE_GC
102   uint32 refcount;
103 #endif
104   VecPNode children;
105   uint height; /* max tree height */
106   uint8 evaluated;
107   uint8 error_recovery;
108   struct PNode *all_next;
109   struct PNode *bucket_next;
110   struct PNode *ambiguities;
111   struct PNode *latest; /* latest version of this PNode */
112   char *ws_before;
113   char *ws_after;
114   D_Scope *initial_scope;
115   void *initial_globals;
116   D_ParseNode parse_node; /* public fields */
117 #ifdef TRACK_PNODES
118   struct PNode *xnext;
119   struct PNode *xprev;
120 #endif
121 } PNode;
122 
123 /*
124   State Node - the 'state'.
125 */
126 typedef struct SNode {
127   D_State *state;
128   D_Scope *initial_scope;
129   void *initial_globals;
130   d_loc_t loc;
131   uint depth; /* max stack depth (less loops) */
132   PNode *last_pn;
133   VecZNode zns;
134 #ifndef USE_GC
135   uint32 refcount;
136 #endif
137   struct SNode *bucket_next;
138   struct SNode *all_next;
139 } SNode;
140 
141 /*
142   (Z)Symbol Node - holds one of the symbols associated with a state.
143 */
144 typedef struct ZNode {
145   PNode *pn;
146   VecSNode sns;
147 } ZNode;
148 #define znode_next(_z) (*(ZNode **)&((_z)->pn))
149 
150 D_ParseNode *ambiguity_count_fn(D_Parser *pp, int n, D_ParseNode **v);
151 
152 #endif
153