1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
|
/* Copyright (c) 1994 Sun Wu, Udi Manber, Burra Gopal. All Rights Reserved. */
/*************************************************************
* *
* Macros defining special characters. *
* *
*************************************************************/
#define NUL '\0'
#define ASCII_MIN '\001'
#define ASCII_MAX '\177'
/*************************************************************
* *
* Macros defining lexical categories. *
* *
*************************************************************/
#define C_LIT 0 /* individual character literal */
#define C_SET 1 /* character set literal */
#define EOS 0 /* end-of-string */
#define LITERAL 1
#define OPSTAR 2
#define OPALT 3
#define OPOPT 4
#define OPCAT 5
#define LPAREN 6
#define RPAREN 7
/*************************************************************
* *
* Macros for manipulating syntax tree nodes. *
* *
*************************************************************/
#define lit_type(x) (x->l_type)
#define lit_pos(x) (x->pos)
#define lit_char(x) ((x->val).c)
#define lit_cset(x) ((x->val).cset)
#define tok_type(x) (x->type)
#define tok_val(x) (x->val)
#define tok_op(x) (x->val->op)
#define tok_lit(x) ((x->val->refs).lit)
#define Op(x) (x->op)
#define Lit(x) ((x->refs).lit)
#define Child(x) ((x->refs).child)
#define Lchild(x) ((x->refs).children.l_child)
#define Rchild(x) ((x->refs).children.r_child)
#define Nullable(x) (x->nullable)
#define Firstpos(x) (x->firstposn)
#define Lastpos(x) (x->lastposn)
/*************************************************************
* *
* Macros for manipulating DFA states and sets of states. *
* *
*************************************************************/
#define Positions(x) (x->posns)
#define Final_St(x) (x->final)
#define Goto(x, c) ((x->trans)[c])
#define Next_State(x) ((x)->next_state)
/*************************************************************/
#define new_node(type, l, x) \
{\
extern void *malloc();\
\
(l) = (type) malloc(sizeof(*(x)));\
if ((l) == NULL) {\
fprintf(stderr, "malloc failure in new_node\n");\
exit(2);\
}\
memset((l), '\0', sizeof(*(x)));\
}
typedef struct { /* character range literals */
char low_bd, hi_bd;
} *Ch_Range;
typedef struct ch_set { /* character set literals */
Ch_Range elt; /* rep. as list of ranges */
struct ch_set *rest;
} *Ch_Set;
typedef struct { /* regular expression literal */
int pos; /* position in syntax tree */
short l_type; /* type of literal */
union {
char c; /* for character literals */
Ch_Set cset; /* for character sets */
} val;
} *Re_Lit, *(*Re_lit_array)[];
typedef struct pnode {
int posnum;
struct pnode *nextpos;
} *Pset, *(*Pset_array)[];
typedef struct rnode { /* regular expression node */
short op; /* operator at that node */
union {
Re_Lit lit; /* child is a leaf node */
struct rnode *child; /* child of unary op */
struct {
struct rnode *l_child;
struct rnode *r_child;
} children; /* children of binary op */
} refs;
short nullable;
Pset firstposn, lastposn;
} *Re_node;
typedef struct { /* token node */
short type;
Re_node val;
} *Tok_node;
typedef struct snode {
Re_node val;
int size;
struct snode *next;
} *Stack;
typedef struct dfa_st {
Pset posns;
int final; /* 1 if the state is a final state, 0 o/w */
struct dfa_st *trans[128];
} *Dfa_state;
typedef struct dfa_stset {
Dfa_state st;
struct dfa_stset *next_state;
} *Dfa_state_set;
|
