Guido van Rossum | 85a5fbb | 1990-10-14 12:07:46 +0000 | [diff] [blame] | 1 | /* Parser generator */ |
| 2 | |
| 3 | /* For a description, see the comments at end of this file */ |
| 4 | |
Tim Peters | 1ca1296 | 2001-12-04 03:18:48 +0000 | [diff] [blame] | 5 | #include "Python.h" |
Guido van Rossum | 3f5da24 | 1990-12-20 15:06:42 +0000 | [diff] [blame] | 6 | #include "pgenheaders.h" |
Guido van Rossum | 85a5fbb | 1990-10-14 12:07:46 +0000 | [diff] [blame] | 7 | #include "token.h" |
| 8 | #include "node.h" |
| 9 | #include "grammar.h" |
| 10 | #include "metagrammar.h" |
| 11 | #include "pgen.h" |
| 12 | |
Guido van Rossum | 86bea46 | 1997-04-29 21:03:06 +0000 | [diff] [blame] | 13 | extern int Py_DebugFlag; |
Neal Norwitz | 5352d8c | 2002-05-31 13:11:40 +0000 | [diff] [blame] | 14 | extern int Py_IgnoreEnvironmentFlag; /* needed by Py_GETENV */ |
Guido van Rossum | 85a5fbb | 1990-10-14 12:07:46 +0000 | [diff] [blame] | 15 | |
| 16 | |
| 17 | /* PART ONE -- CONSTRUCT NFA -- Cf. Algorithm 3.2 from [Aho&Ullman 77] */ |
| 18 | |
| 19 | typedef struct _nfaarc { |
Antoine Pitrou | c83ea13 | 2010-05-09 14:46:46 +0000 | [diff] [blame] | 20 | int ar_label; |
| 21 | int ar_arrow; |
Guido van Rossum | 85a5fbb | 1990-10-14 12:07:46 +0000 | [diff] [blame] | 22 | } nfaarc; |
| 23 | |
| 24 | typedef struct _nfastate { |
Antoine Pitrou | c83ea13 | 2010-05-09 14:46:46 +0000 | [diff] [blame] | 25 | int st_narcs; |
| 26 | nfaarc *st_arc; |
Guido van Rossum | 85a5fbb | 1990-10-14 12:07:46 +0000 | [diff] [blame] | 27 | } nfastate; |
| 28 | |
| 29 | typedef struct _nfa { |
Antoine Pitrou | c83ea13 | 2010-05-09 14:46:46 +0000 | [diff] [blame] | 30 | int nf_type; |
| 31 | char *nf_name; |
| 32 | int nf_nstates; |
| 33 | nfastate *nf_state; |
| 34 | int nf_start, nf_finish; |
Guido van Rossum | 85a5fbb | 1990-10-14 12:07:46 +0000 | [diff] [blame] | 35 | } nfa; |
| 36 | |
Guido van Rossum | 71f477c | 1991-04-03 19:09:02 +0000 | [diff] [blame] | 37 | /* Forward */ |
Tim Peters | dbd9ba6 | 2000-07-09 03:09:57 +0000 | [diff] [blame] | 38 | static void compile_rhs(labellist *ll, |
Antoine Pitrou | c83ea13 | 2010-05-09 14:46:46 +0000 | [diff] [blame] | 39 | nfa *nf, node *n, int *pa, int *pb); |
Tim Peters | dbd9ba6 | 2000-07-09 03:09:57 +0000 | [diff] [blame] | 40 | static void compile_alt(labellist *ll, |
Antoine Pitrou | c83ea13 | 2010-05-09 14:46:46 +0000 | [diff] [blame] | 41 | nfa *nf, node *n, int *pa, int *pb); |
Tim Peters | dbd9ba6 | 2000-07-09 03:09:57 +0000 | [diff] [blame] | 42 | static void compile_item(labellist *ll, |
Antoine Pitrou | c83ea13 | 2010-05-09 14:46:46 +0000 | [diff] [blame] | 43 | nfa *nf, node *n, int *pa, int *pb); |
Tim Peters | dbd9ba6 | 2000-07-09 03:09:57 +0000 | [diff] [blame] | 44 | static void compile_atom(labellist *ll, |
Antoine Pitrou | c83ea13 | 2010-05-09 14:46:46 +0000 | [diff] [blame] | 45 | nfa *nf, node *n, int *pa, int *pb); |
Guido van Rossum | 71f477c | 1991-04-03 19:09:02 +0000 | [diff] [blame] | 46 | |
Guido van Rossum | 85a5fbb | 1990-10-14 12:07:46 +0000 | [diff] [blame] | 47 | static int |
Thomas Wouters | 23c9e00 | 2000-07-22 19:20:54 +0000 | [diff] [blame] | 48 | addnfastate(nfa *nf) |
Guido van Rossum | 85a5fbb | 1990-10-14 12:07:46 +0000 | [diff] [blame] | 49 | { |
Antoine Pitrou | c83ea13 | 2010-05-09 14:46:46 +0000 | [diff] [blame] | 50 | nfastate *st; |
| 51 | |
| 52 | nf->nf_state = (nfastate *)PyObject_REALLOC(nf->nf_state, |
| 53 | sizeof(nfastate) * (nf->nf_nstates + 1)); |
| 54 | if (nf->nf_state == NULL) |
| 55 | Py_FatalError("out of mem"); |
| 56 | st = &nf->nf_state[nf->nf_nstates++]; |
| 57 | st->st_narcs = 0; |
| 58 | st->st_arc = NULL; |
| 59 | return st - nf->nf_state; |
Guido van Rossum | 85a5fbb | 1990-10-14 12:07:46 +0000 | [diff] [blame] | 60 | } |
| 61 | |
| 62 | static void |
Thomas Wouters | 23c9e00 | 2000-07-22 19:20:54 +0000 | [diff] [blame] | 63 | addnfaarc(nfa *nf, int from, int to, int lbl) |
Guido van Rossum | 85a5fbb | 1990-10-14 12:07:46 +0000 | [diff] [blame] | 64 | { |
Antoine Pitrou | c83ea13 | 2010-05-09 14:46:46 +0000 | [diff] [blame] | 65 | nfastate *st; |
| 66 | nfaarc *ar; |
| 67 | |
| 68 | st = &nf->nf_state[from]; |
| 69 | st->st_arc = (nfaarc *)PyObject_REALLOC(st->st_arc, |
| 70 | sizeof(nfaarc) * (st->st_narcs + 1)); |
| 71 | if (st->st_arc == NULL) |
| 72 | Py_FatalError("out of mem"); |
| 73 | ar = &st->st_arc[st->st_narcs++]; |
| 74 | ar->ar_label = lbl; |
| 75 | ar->ar_arrow = to; |
Guido van Rossum | 85a5fbb | 1990-10-14 12:07:46 +0000 | [diff] [blame] | 76 | } |
| 77 | |
| 78 | static nfa * |
Thomas Wouters | 23c9e00 | 2000-07-22 19:20:54 +0000 | [diff] [blame] | 79 | newnfa(char *name) |
Guido van Rossum | 85a5fbb | 1990-10-14 12:07:46 +0000 | [diff] [blame] | 80 | { |
Antoine Pitrou | c83ea13 | 2010-05-09 14:46:46 +0000 | [diff] [blame] | 81 | nfa *nf; |
| 82 | static int type = NT_OFFSET; /* All types will be disjunct */ |
| 83 | |
| 84 | nf = (nfa *)PyObject_MALLOC(sizeof(nfa)); |
| 85 | if (nf == NULL) |
| 86 | Py_FatalError("no mem for new nfa"); |
| 87 | nf->nf_type = type++; |
| 88 | nf->nf_name = name; /* XXX strdup(name) ??? */ |
| 89 | nf->nf_nstates = 0; |
| 90 | nf->nf_state = NULL; |
| 91 | nf->nf_start = nf->nf_finish = -1; |
| 92 | return nf; |
Guido van Rossum | 85a5fbb | 1990-10-14 12:07:46 +0000 | [diff] [blame] | 93 | } |
| 94 | |
| 95 | typedef struct _nfagrammar { |
Antoine Pitrou | c83ea13 | 2010-05-09 14:46:46 +0000 | [diff] [blame] | 96 | int gr_nnfas; |
| 97 | nfa **gr_nfa; |
| 98 | labellist gr_ll; |
Guido van Rossum | 85a5fbb | 1990-10-14 12:07:46 +0000 | [diff] [blame] | 99 | } nfagrammar; |
| 100 | |
Guido van Rossum | 71f477c | 1991-04-03 19:09:02 +0000 | [diff] [blame] | 101 | /* Forward */ |
Tim Peters | dbd9ba6 | 2000-07-09 03:09:57 +0000 | [diff] [blame] | 102 | static void compile_rule(nfagrammar *gr, node *n); |
Guido van Rossum | 71f477c | 1991-04-03 19:09:02 +0000 | [diff] [blame] | 103 | |
Guido van Rossum | 85a5fbb | 1990-10-14 12:07:46 +0000 | [diff] [blame] | 104 | static nfagrammar * |
Thomas Wouters | 23c9e00 | 2000-07-22 19:20:54 +0000 | [diff] [blame] | 105 | newnfagrammar(void) |
Guido van Rossum | 85a5fbb | 1990-10-14 12:07:46 +0000 | [diff] [blame] | 106 | { |
Antoine Pitrou | c83ea13 | 2010-05-09 14:46:46 +0000 | [diff] [blame] | 107 | nfagrammar *gr; |
| 108 | |
| 109 | gr = (nfagrammar *)PyObject_MALLOC(sizeof(nfagrammar)); |
| 110 | if (gr == NULL) |
| 111 | Py_FatalError("no mem for new nfa grammar"); |
| 112 | gr->gr_nnfas = 0; |
| 113 | gr->gr_nfa = NULL; |
| 114 | gr->gr_ll.ll_nlabels = 0; |
| 115 | gr->gr_ll.ll_label = NULL; |
| 116 | addlabel(&gr->gr_ll, ENDMARKER, "EMPTY"); |
| 117 | return gr; |
Guido van Rossum | 85a5fbb | 1990-10-14 12:07:46 +0000 | [diff] [blame] | 118 | } |
| 119 | |
| 120 | static nfa * |
Thomas Wouters | 23c9e00 | 2000-07-22 19:20:54 +0000 | [diff] [blame] | 121 | addnfa(nfagrammar *gr, char *name) |
Guido van Rossum | 85a5fbb | 1990-10-14 12:07:46 +0000 | [diff] [blame] | 122 | { |
Antoine Pitrou | c83ea13 | 2010-05-09 14:46:46 +0000 | [diff] [blame] | 123 | nfa *nf; |
| 124 | |
| 125 | nf = newnfa(name); |
| 126 | gr->gr_nfa = (nfa **)PyObject_REALLOC(gr->gr_nfa, |
| 127 | sizeof(nfa*) * (gr->gr_nnfas + 1)); |
| 128 | if (gr->gr_nfa == NULL) |
| 129 | Py_FatalError("out of mem"); |
| 130 | gr->gr_nfa[gr->gr_nnfas++] = nf; |
| 131 | addlabel(&gr->gr_ll, NAME, nf->nf_name); |
| 132 | return nf; |
Guido van Rossum | 85a5fbb | 1990-10-14 12:07:46 +0000 | [diff] [blame] | 133 | } |
| 134 | |
Guido van Rossum | 408027e | 1996-12-30 16:17:54 +0000 | [diff] [blame] | 135 | #ifdef Py_DEBUG |
Guido van Rossum | 85a5fbb | 1990-10-14 12:07:46 +0000 | [diff] [blame] | 136 | |
| 137 | static char REQNFMT[] = "metacompile: less than %d children\n"; |
| 138 | |
Serhiy Storchaka | 6a35bf6 | 2016-10-08 09:58:08 +0300 | [diff] [blame] | 139 | #define REQN(i, count) do { \ |
Antoine Pitrou | c83ea13 | 2010-05-09 14:46:46 +0000 | [diff] [blame] | 140 | if (i < count) { \ |
| 141 | fprintf(stderr, REQNFMT, count); \ |
| 142 | Py_FatalError("REQN"); \ |
Serhiy Storchaka | 6a35bf6 | 2016-10-08 09:58:08 +0300 | [diff] [blame] | 143 | } \ |
| 144 | } while (0) |
Guido van Rossum | 85a5fbb | 1990-10-14 12:07:46 +0000 | [diff] [blame] | 145 | |
| 146 | #else |
Antoine Pitrou | c83ea13 | 2010-05-09 14:46:46 +0000 | [diff] [blame] | 147 | #define REQN(i, count) /* empty */ |
Guido van Rossum | 85a5fbb | 1990-10-14 12:07:46 +0000 | [diff] [blame] | 148 | #endif |
| 149 | |
| 150 | static nfagrammar * |
Thomas Wouters | 23c9e00 | 2000-07-22 19:20:54 +0000 | [diff] [blame] | 151 | metacompile(node *n) |
Guido van Rossum | 85a5fbb | 1990-10-14 12:07:46 +0000 | [diff] [blame] | 152 | { |
Antoine Pitrou | c83ea13 | 2010-05-09 14:46:46 +0000 | [diff] [blame] | 153 | nfagrammar *gr; |
| 154 | int i; |
Guido van Rossum | 25dfe2c | 2001-09-11 16:43:16 +0000 | [diff] [blame] | 155 | |
Antoine Pitrou | c83ea13 | 2010-05-09 14:46:46 +0000 | [diff] [blame] | 156 | if (Py_DebugFlag) |
| 157 | printf("Compiling (meta-) parse tree into NFA grammar\n"); |
| 158 | gr = newnfagrammar(); |
| 159 | REQ(n, MSTART); |
| 160 | i = n->n_nchildren - 1; /* Last child is ENDMARKER */ |
| 161 | n = n->n_child; |
| 162 | for (; --i >= 0; n++) { |
| 163 | if (n->n_type != NEWLINE) |
| 164 | compile_rule(gr, n); |
| 165 | } |
| 166 | return gr; |
Guido van Rossum | 85a5fbb | 1990-10-14 12:07:46 +0000 | [diff] [blame] | 167 | } |
| 168 | |
Guido van Rossum | fd8a393 | 1996-12-02 18:27:33 +0000 | [diff] [blame] | 169 | static void |
Thomas Wouters | 23c9e00 | 2000-07-22 19:20:54 +0000 | [diff] [blame] | 170 | compile_rule(nfagrammar *gr, node *n) |
Guido van Rossum | 85a5fbb | 1990-10-14 12:07:46 +0000 | [diff] [blame] | 171 | { |
Antoine Pitrou | c83ea13 | 2010-05-09 14:46:46 +0000 | [diff] [blame] | 172 | nfa *nf; |
| 173 | |
| 174 | REQ(n, RULE); |
| 175 | REQN(n->n_nchildren, 4); |
| 176 | n = n->n_child; |
| 177 | REQ(n, NAME); |
| 178 | nf = addnfa(gr, n->n_str); |
| 179 | n++; |
| 180 | REQ(n, COLON); |
| 181 | n++; |
| 182 | REQ(n, RHS); |
| 183 | compile_rhs(&gr->gr_ll, nf, n, &nf->nf_start, &nf->nf_finish); |
| 184 | n++; |
| 185 | REQ(n, NEWLINE); |
Guido van Rossum | 85a5fbb | 1990-10-14 12:07:46 +0000 | [diff] [blame] | 186 | } |
| 187 | |
Guido van Rossum | fd8a393 | 1996-12-02 18:27:33 +0000 | [diff] [blame] | 188 | static void |
Thomas Wouters | 23c9e00 | 2000-07-22 19:20:54 +0000 | [diff] [blame] | 189 | compile_rhs(labellist *ll, nfa *nf, node *n, int *pa, int *pb) |
Guido van Rossum | 85a5fbb | 1990-10-14 12:07:46 +0000 | [diff] [blame] | 190 | { |
Antoine Pitrou | c83ea13 | 2010-05-09 14:46:46 +0000 | [diff] [blame] | 191 | int i; |
| 192 | int a, b; |
| 193 | |
| 194 | REQ(n, RHS); |
| 195 | i = n->n_nchildren; |
| 196 | REQN(i, 1); |
| 197 | n = n->n_child; |
| 198 | REQ(n, ALT); |
| 199 | compile_alt(ll, nf, n, pa, pb); |
| 200 | if (--i <= 0) |
| 201 | return; |
| 202 | n++; |
| 203 | a = *pa; |
| 204 | b = *pb; |
| 205 | *pa = addnfastate(nf); |
| 206 | *pb = addnfastate(nf); |
| 207 | addnfaarc(nf, *pa, a, EMPTY); |
| 208 | addnfaarc(nf, b, *pb, EMPTY); |
| 209 | for (; --i >= 0; n++) { |
| 210 | REQ(n, VBAR); |
| 211 | REQN(i, 1); |
| 212 | --i; |
| 213 | n++; |
| 214 | REQ(n, ALT); |
| 215 | compile_alt(ll, nf, n, &a, &b); |
| 216 | addnfaarc(nf, *pa, a, EMPTY); |
| 217 | addnfaarc(nf, b, *pb, EMPTY); |
| 218 | } |
Guido van Rossum | 85a5fbb | 1990-10-14 12:07:46 +0000 | [diff] [blame] | 219 | } |
| 220 | |
Guido van Rossum | fd8a393 | 1996-12-02 18:27:33 +0000 | [diff] [blame] | 221 | static void |
Thomas Wouters | 23c9e00 | 2000-07-22 19:20:54 +0000 | [diff] [blame] | 222 | compile_alt(labellist *ll, nfa *nf, node *n, int *pa, int *pb) |
Guido van Rossum | 85a5fbb | 1990-10-14 12:07:46 +0000 | [diff] [blame] | 223 | { |
Antoine Pitrou | c83ea13 | 2010-05-09 14:46:46 +0000 | [diff] [blame] | 224 | int i; |
| 225 | int a, b; |
| 226 | |
| 227 | REQ(n, ALT); |
| 228 | i = n->n_nchildren; |
| 229 | REQN(i, 1); |
| 230 | n = n->n_child; |
| 231 | REQ(n, ITEM); |
| 232 | compile_item(ll, nf, n, pa, pb); |
| 233 | --i; |
| 234 | n++; |
| 235 | for (; --i >= 0; n++) { |
| 236 | REQ(n, ITEM); |
| 237 | compile_item(ll, nf, n, &a, &b); |
| 238 | addnfaarc(nf, *pb, a, EMPTY); |
| 239 | *pb = b; |
| 240 | } |
Guido van Rossum | 85a5fbb | 1990-10-14 12:07:46 +0000 | [diff] [blame] | 241 | } |
| 242 | |
Guido van Rossum | fd8a393 | 1996-12-02 18:27:33 +0000 | [diff] [blame] | 243 | static void |
Thomas Wouters | 23c9e00 | 2000-07-22 19:20:54 +0000 | [diff] [blame] | 244 | compile_item(labellist *ll, nfa *nf, node *n, int *pa, int *pb) |
Guido van Rossum | 85a5fbb | 1990-10-14 12:07:46 +0000 | [diff] [blame] | 245 | { |
Antoine Pitrou | c83ea13 | 2010-05-09 14:46:46 +0000 | [diff] [blame] | 246 | int i; |
| 247 | int a, b; |
| 248 | |
| 249 | REQ(n, ITEM); |
| 250 | i = n->n_nchildren; |
| 251 | REQN(i, 1); |
| 252 | n = n->n_child; |
| 253 | if (n->n_type == LSQB) { |
| 254 | REQN(i, 3); |
| 255 | n++; |
| 256 | REQ(n, RHS); |
| 257 | *pa = addnfastate(nf); |
| 258 | *pb = addnfastate(nf); |
| 259 | addnfaarc(nf, *pa, *pb, EMPTY); |
| 260 | compile_rhs(ll, nf, n, &a, &b); |
| 261 | addnfaarc(nf, *pa, a, EMPTY); |
| 262 | addnfaarc(nf, b, *pb, EMPTY); |
| 263 | REQN(i, 1); |
| 264 | n++; |
| 265 | REQ(n, RSQB); |
| 266 | } |
| 267 | else { |
| 268 | compile_atom(ll, nf, n, pa, pb); |
| 269 | if (--i <= 0) |
| 270 | return; |
| 271 | n++; |
| 272 | addnfaarc(nf, *pb, *pa, EMPTY); |
| 273 | if (n->n_type == STAR) |
| 274 | *pb = *pa; |
| 275 | else |
| 276 | REQ(n, PLUS); |
| 277 | } |
Guido van Rossum | 85a5fbb | 1990-10-14 12:07:46 +0000 | [diff] [blame] | 278 | } |
| 279 | |
Guido van Rossum | fd8a393 | 1996-12-02 18:27:33 +0000 | [diff] [blame] | 280 | static void |
Thomas Wouters | 23c9e00 | 2000-07-22 19:20:54 +0000 | [diff] [blame] | 281 | compile_atom(labellist *ll, nfa *nf, node *n, int *pa, int *pb) |
Guido van Rossum | 85a5fbb | 1990-10-14 12:07:46 +0000 | [diff] [blame] | 282 | { |
Antoine Pitrou | c83ea13 | 2010-05-09 14:46:46 +0000 | [diff] [blame] | 283 | int i; |
| 284 | |
| 285 | REQ(n, ATOM); |
| 286 | i = n->n_nchildren; |
Martin Panter | 646b528 | 2016-06-21 23:58:05 +0000 | [diff] [blame] | 287 | (void)i; /* Don't warn about set but unused */ |
Antoine Pitrou | c83ea13 | 2010-05-09 14:46:46 +0000 | [diff] [blame] | 288 | REQN(i, 1); |
| 289 | n = n->n_child; |
| 290 | if (n->n_type == LPAR) { |
| 291 | REQN(i, 3); |
| 292 | n++; |
| 293 | REQ(n, RHS); |
| 294 | compile_rhs(ll, nf, n, pa, pb); |
| 295 | n++; |
| 296 | REQ(n, RPAR); |
| 297 | } |
| 298 | else if (n->n_type == NAME || n->n_type == STRING) { |
| 299 | *pa = addnfastate(nf); |
| 300 | *pb = addnfastate(nf); |
| 301 | addnfaarc(nf, *pa, *pb, addlabel(ll, n->n_type, n->n_str)); |
| 302 | } |
| 303 | else |
| 304 | REQ(n, NAME); |
Guido van Rossum | 85a5fbb | 1990-10-14 12:07:46 +0000 | [diff] [blame] | 305 | } |
| 306 | |
| 307 | static void |
Thomas Wouters | 23c9e00 | 2000-07-22 19:20:54 +0000 | [diff] [blame] | 308 | dumpstate(labellist *ll, nfa *nf, int istate) |
Guido van Rossum | 85a5fbb | 1990-10-14 12:07:46 +0000 | [diff] [blame] | 309 | { |
Antoine Pitrou | c83ea13 | 2010-05-09 14:46:46 +0000 | [diff] [blame] | 310 | nfastate *st; |
| 311 | int i; |
| 312 | nfaarc *ar; |
| 313 | |
| 314 | printf("%c%2d%c", |
| 315 | istate == nf->nf_start ? '*' : ' ', |
| 316 | istate, |
| 317 | istate == nf->nf_finish ? '.' : ' '); |
| 318 | st = &nf->nf_state[istate]; |
| 319 | ar = st->st_arc; |
| 320 | for (i = 0; i < st->st_narcs; i++) { |
| 321 | if (i > 0) |
| 322 | printf("\n "); |
| 323 | printf("-> %2d %s", ar->ar_arrow, |
| 324 | PyGrammar_LabelRepr(&ll->ll_label[ar->ar_label])); |
| 325 | ar++; |
| 326 | } |
| 327 | printf("\n"); |
Guido van Rossum | 85a5fbb | 1990-10-14 12:07:46 +0000 | [diff] [blame] | 328 | } |
| 329 | |
| 330 | static void |
Thomas Wouters | 23c9e00 | 2000-07-22 19:20:54 +0000 | [diff] [blame] | 331 | dumpnfa(labellist *ll, nfa *nf) |
Guido van Rossum | 85a5fbb | 1990-10-14 12:07:46 +0000 | [diff] [blame] | 332 | { |
Antoine Pitrou | c83ea13 | 2010-05-09 14:46:46 +0000 | [diff] [blame] | 333 | int i; |
| 334 | |
| 335 | printf("NFA '%s' has %d states; start %d, finish %d\n", |
| 336 | nf->nf_name, nf->nf_nstates, nf->nf_start, nf->nf_finish); |
| 337 | for (i = 0; i < nf->nf_nstates; i++) |
| 338 | dumpstate(ll, nf, i); |
Guido van Rossum | 85a5fbb | 1990-10-14 12:07:46 +0000 | [diff] [blame] | 339 | } |
| 340 | |
| 341 | |
| 342 | /* PART TWO -- CONSTRUCT DFA -- Algorithm 3.1 from [Aho&Ullman 77] */ |
| 343 | |
Guido van Rossum | 588633d | 1994-12-30 15:46:02 +0000 | [diff] [blame] | 344 | static void |
Thomas Wouters | 23c9e00 | 2000-07-22 19:20:54 +0000 | [diff] [blame] | 345 | addclosure(bitset ss, nfa *nf, int istate) |
Guido van Rossum | 85a5fbb | 1990-10-14 12:07:46 +0000 | [diff] [blame] | 346 | { |
Antoine Pitrou | c83ea13 | 2010-05-09 14:46:46 +0000 | [diff] [blame] | 347 | if (addbit(ss, istate)) { |
| 348 | nfastate *st = &nf->nf_state[istate]; |
| 349 | nfaarc *ar = st->st_arc; |
| 350 | int i; |
| 351 | |
| 352 | for (i = st->st_narcs; --i >= 0; ) { |
| 353 | if (ar->ar_label == EMPTY) |
| 354 | addclosure(ss, nf, ar->ar_arrow); |
| 355 | ar++; |
| 356 | } |
| 357 | } |
Guido van Rossum | 85a5fbb | 1990-10-14 12:07:46 +0000 | [diff] [blame] | 358 | } |
| 359 | |
| 360 | typedef struct _ss_arc { |
Antoine Pitrou | c83ea13 | 2010-05-09 14:46:46 +0000 | [diff] [blame] | 361 | bitset sa_bitset; |
| 362 | int sa_arrow; |
| 363 | int sa_label; |
Guido van Rossum | 85a5fbb | 1990-10-14 12:07:46 +0000 | [diff] [blame] | 364 | } ss_arc; |
| 365 | |
| 366 | typedef struct _ss_state { |
Antoine Pitrou | c83ea13 | 2010-05-09 14:46:46 +0000 | [diff] [blame] | 367 | bitset ss_ss; |
| 368 | int ss_narcs; |
| 369 | struct _ss_arc *ss_arc; |
| 370 | int ss_deleted; |
| 371 | int ss_finish; |
| 372 | int ss_rename; |
Guido van Rossum | 85a5fbb | 1990-10-14 12:07:46 +0000 | [diff] [blame] | 373 | } ss_state; |
| 374 | |
| 375 | typedef struct _ss_dfa { |
Antoine Pitrou | c83ea13 | 2010-05-09 14:46:46 +0000 | [diff] [blame] | 376 | int sd_nstates; |
| 377 | ss_state *sd_state; |
Guido van Rossum | 85a5fbb | 1990-10-14 12:07:46 +0000 | [diff] [blame] | 378 | } ss_dfa; |
| 379 | |
Guido van Rossum | 71f477c | 1991-04-03 19:09:02 +0000 | [diff] [blame] | 380 | /* Forward */ |
Tim Peters | dbd9ba6 | 2000-07-09 03:09:57 +0000 | [diff] [blame] | 381 | static void printssdfa(int xx_nstates, ss_state *xx_state, int nbits, |
Antoine Pitrou | c83ea13 | 2010-05-09 14:46:46 +0000 | [diff] [blame] | 382 | labellist *ll, char *msg); |
Tim Peters | dbd9ba6 | 2000-07-09 03:09:57 +0000 | [diff] [blame] | 383 | static void simplify(int xx_nstates, ss_state *xx_state); |
| 384 | static void convert(dfa *d, int xx_nstates, ss_state *xx_state); |
Guido van Rossum | 71f477c | 1991-04-03 19:09:02 +0000 | [diff] [blame] | 385 | |
Guido van Rossum | fd8a393 | 1996-12-02 18:27:33 +0000 | [diff] [blame] | 386 | static void |
Thomas Wouters | 23c9e00 | 2000-07-22 19:20:54 +0000 | [diff] [blame] | 387 | makedfa(nfagrammar *gr, nfa *nf, dfa *d) |
Guido van Rossum | 85a5fbb | 1990-10-14 12:07:46 +0000 | [diff] [blame] | 388 | { |
Antoine Pitrou | c83ea13 | 2010-05-09 14:46:46 +0000 | [diff] [blame] | 389 | int nbits = nf->nf_nstates; |
| 390 | bitset ss; |
| 391 | int xx_nstates; |
| 392 | ss_state *xx_state, *yy; |
| 393 | ss_arc *zz; |
| 394 | int istate, jstate, iarc, jarc, ibit; |
| 395 | nfastate *st; |
| 396 | nfaarc *ar; |
Guido van Rossum | 85a5fbb | 1990-10-14 12:07:46 +0000 | [diff] [blame] | 397 | |
Antoine Pitrou | c83ea13 | 2010-05-09 14:46:46 +0000 | [diff] [blame] | 398 | ss = newbitset(nbits); |
| 399 | addclosure(ss, nf, nf->nf_start); |
| 400 | xx_state = (ss_state *)PyObject_MALLOC(sizeof(ss_state)); |
| 401 | if (xx_state == NULL) |
| 402 | Py_FatalError("no mem for xx_state in makedfa"); |
| 403 | xx_nstates = 1; |
| 404 | yy = &xx_state[0]; |
| 405 | yy->ss_ss = ss; |
| 406 | yy->ss_narcs = 0; |
| 407 | yy->ss_arc = NULL; |
| 408 | yy->ss_deleted = 0; |
| 409 | yy->ss_finish = testbit(ss, nf->nf_finish); |
| 410 | if (yy->ss_finish) |
| 411 | printf("Error: nonterminal '%s' may produce empty.\n", |
| 412 | nf->nf_name); |
| 413 | |
| 414 | /* This algorithm is from a book written before |
| 415 | the invention of structured programming... */ |
| 416 | |
| 417 | /* For each unmarked state... */ |
| 418 | for (istate = 0; istate < xx_nstates; ++istate) { |
| 419 | size_t size; |
| 420 | yy = &xx_state[istate]; |
| 421 | ss = yy->ss_ss; |
| 422 | /* For all its states... */ |
| 423 | for (ibit = 0; ibit < nf->nf_nstates; ++ibit) { |
| 424 | if (!testbit(ss, ibit)) |
| 425 | continue; |
| 426 | st = &nf->nf_state[ibit]; |
| 427 | /* For all non-empty arcs from this state... */ |
| 428 | for (iarc = 0; iarc < st->st_narcs; iarc++) { |
| 429 | ar = &st->st_arc[iarc]; |
| 430 | if (ar->ar_label == EMPTY) |
| 431 | continue; |
| 432 | /* Look up in list of arcs from this state */ |
| 433 | for (jarc = 0; jarc < yy->ss_narcs; ++jarc) { |
| 434 | zz = &yy->ss_arc[jarc]; |
| 435 | if (ar->ar_label == zz->sa_label) |
| 436 | goto found; |
| 437 | } |
| 438 | /* Add new arc for this state */ |
| 439 | size = sizeof(ss_arc) * (yy->ss_narcs + 1); |
| 440 | yy->ss_arc = (ss_arc *)PyObject_REALLOC( |
| 441 | yy->ss_arc, size); |
| 442 | if (yy->ss_arc == NULL) |
| 443 | Py_FatalError("out of mem"); |
| 444 | zz = &yy->ss_arc[yy->ss_narcs++]; |
| 445 | zz->sa_label = ar->ar_label; |
| 446 | zz->sa_bitset = newbitset(nbits); |
| 447 | zz->sa_arrow = -1; |
| 448 | found: ; |
| 449 | /* Add destination */ |
| 450 | addclosure(zz->sa_bitset, nf, ar->ar_arrow); |
| 451 | } |
| 452 | } |
| 453 | /* Now look up all the arrow states */ |
| 454 | for (jarc = 0; jarc < xx_state[istate].ss_narcs; jarc++) { |
| 455 | zz = &xx_state[istate].ss_arc[jarc]; |
| 456 | for (jstate = 0; jstate < xx_nstates; jstate++) { |
| 457 | if (samebitset(zz->sa_bitset, |
| 458 | xx_state[jstate].ss_ss, nbits)) { |
| 459 | zz->sa_arrow = jstate; |
| 460 | goto done; |
| 461 | } |
| 462 | } |
| 463 | size = sizeof(ss_state) * (xx_nstates + 1); |
| 464 | xx_state = (ss_state *)PyObject_REALLOC(xx_state, |
| 465 | size); |
| 466 | if (xx_state == NULL) |
| 467 | Py_FatalError("out of mem"); |
| 468 | zz->sa_arrow = xx_nstates; |
| 469 | yy = &xx_state[xx_nstates++]; |
| 470 | yy->ss_ss = zz->sa_bitset; |
| 471 | yy->ss_narcs = 0; |
| 472 | yy->ss_arc = NULL; |
| 473 | yy->ss_deleted = 0; |
| 474 | yy->ss_finish = testbit(yy->ss_ss, nf->nf_finish); |
| 475 | done: ; |
| 476 | } |
| 477 | } |
| 478 | |
| 479 | if (Py_DebugFlag) |
| 480 | printssdfa(xx_nstates, xx_state, nbits, &gr->gr_ll, |
| 481 | "before minimizing"); |
| 482 | |
| 483 | simplify(xx_nstates, xx_state); |
| 484 | |
| 485 | if (Py_DebugFlag) |
| 486 | printssdfa(xx_nstates, xx_state, nbits, &gr->gr_ll, |
| 487 | "after minimizing"); |
| 488 | |
| 489 | convert(d, xx_nstates, xx_state); |
| 490 | |
| 491 | /* XXX cleanup */ |
| 492 | PyObject_FREE(xx_state); |
Guido van Rossum | 85a5fbb | 1990-10-14 12:07:46 +0000 | [diff] [blame] | 493 | } |
| 494 | |
Guido van Rossum | fd8a393 | 1996-12-02 18:27:33 +0000 | [diff] [blame] | 495 | static void |
Thomas Wouters | 23c9e00 | 2000-07-22 19:20:54 +0000 | [diff] [blame] | 496 | printssdfa(int xx_nstates, ss_state *xx_state, int nbits, |
Antoine Pitrou | c83ea13 | 2010-05-09 14:46:46 +0000 | [diff] [blame] | 497 | labellist *ll, char *msg) |
Guido van Rossum | 85a5fbb | 1990-10-14 12:07:46 +0000 | [diff] [blame] | 498 | { |
Antoine Pitrou | c83ea13 | 2010-05-09 14:46:46 +0000 | [diff] [blame] | 499 | int i, ibit, iarc; |
| 500 | ss_state *yy; |
| 501 | ss_arc *zz; |
| 502 | |
| 503 | printf("Subset DFA %s\n", msg); |
| 504 | for (i = 0; i < xx_nstates; i++) { |
| 505 | yy = &xx_state[i]; |
| 506 | if (yy->ss_deleted) |
| 507 | continue; |
| 508 | printf(" Subset %d", i); |
| 509 | if (yy->ss_finish) |
| 510 | printf(" (finish)"); |
| 511 | printf(" { "); |
| 512 | for (ibit = 0; ibit < nbits; ibit++) { |
| 513 | if (testbit(yy->ss_ss, ibit)) |
| 514 | printf("%d ", ibit); |
| 515 | } |
| 516 | printf("}\n"); |
| 517 | for (iarc = 0; iarc < yy->ss_narcs; iarc++) { |
| 518 | zz = &yy->ss_arc[iarc]; |
| 519 | printf(" Arc to state %d, label %s\n", |
| 520 | zz->sa_arrow, |
| 521 | PyGrammar_LabelRepr( |
| 522 | &ll->ll_label[zz->sa_label])); |
| 523 | } |
| 524 | } |
Guido van Rossum | 85a5fbb | 1990-10-14 12:07:46 +0000 | [diff] [blame] | 525 | } |
| 526 | |
| 527 | |
| 528 | /* PART THREE -- SIMPLIFY DFA */ |
| 529 | |
| 530 | /* Simplify the DFA by repeatedly eliminating states that are |
| 531 | equivalent to another oner. This is NOT Algorithm 3.3 from |
| 532 | [Aho&Ullman 77]. It does not always finds the minimal DFA, |
| 533 | but it does usually make a much smaller one... (For an example |
Thomas Wouters | 7e47402 | 2000-07-16 12:04:32 +0000 | [diff] [blame] | 534 | of sub-optimal behavior, try S: x a b+ | y a b+.) |
Guido van Rossum | 85a5fbb | 1990-10-14 12:07:46 +0000 | [diff] [blame] | 535 | */ |
| 536 | |
| 537 | static int |
Thomas Wouters | 23c9e00 | 2000-07-22 19:20:54 +0000 | [diff] [blame] | 538 | samestate(ss_state *s1, ss_state *s2) |
Guido van Rossum | 85a5fbb | 1990-10-14 12:07:46 +0000 | [diff] [blame] | 539 | { |
Antoine Pitrou | c83ea13 | 2010-05-09 14:46:46 +0000 | [diff] [blame] | 540 | int i; |
| 541 | |
| 542 | if (s1->ss_narcs != s2->ss_narcs || s1->ss_finish != s2->ss_finish) |
| 543 | return 0; |
| 544 | for (i = 0; i < s1->ss_narcs; i++) { |
| 545 | if (s1->ss_arc[i].sa_arrow != s2->ss_arc[i].sa_arrow || |
| 546 | s1->ss_arc[i].sa_label != s2->ss_arc[i].sa_label) |
| 547 | return 0; |
| 548 | } |
| 549 | return 1; |
Guido van Rossum | 85a5fbb | 1990-10-14 12:07:46 +0000 | [diff] [blame] | 550 | } |
| 551 | |
| 552 | static void |
Thomas Wouters | 23c9e00 | 2000-07-22 19:20:54 +0000 | [diff] [blame] | 553 | renamestates(int xx_nstates, ss_state *xx_state, int from, int to) |
Guido van Rossum | 85a5fbb | 1990-10-14 12:07:46 +0000 | [diff] [blame] | 554 | { |
Antoine Pitrou | c83ea13 | 2010-05-09 14:46:46 +0000 | [diff] [blame] | 555 | int i, j; |
| 556 | |
| 557 | if (Py_DebugFlag) |
| 558 | printf("Rename state %d to %d.\n", from, to); |
| 559 | for (i = 0; i < xx_nstates; i++) { |
| 560 | if (xx_state[i].ss_deleted) |
| 561 | continue; |
| 562 | for (j = 0; j < xx_state[i].ss_narcs; j++) { |
| 563 | if (xx_state[i].ss_arc[j].sa_arrow == from) |
| 564 | xx_state[i].ss_arc[j].sa_arrow = to; |
| 565 | } |
| 566 | } |
Guido van Rossum | 85a5fbb | 1990-10-14 12:07:46 +0000 | [diff] [blame] | 567 | } |
| 568 | |
Guido van Rossum | fd8a393 | 1996-12-02 18:27:33 +0000 | [diff] [blame] | 569 | static void |
Thomas Wouters | 23c9e00 | 2000-07-22 19:20:54 +0000 | [diff] [blame] | 570 | simplify(int xx_nstates, ss_state *xx_state) |
Guido van Rossum | 85a5fbb | 1990-10-14 12:07:46 +0000 | [diff] [blame] | 571 | { |
Antoine Pitrou | c83ea13 | 2010-05-09 14:46:46 +0000 | [diff] [blame] | 572 | int changes; |
| 573 | int i, j; |
| 574 | |
| 575 | do { |
| 576 | changes = 0; |
| 577 | for (i = 1; i < xx_nstates; i++) { |
| 578 | if (xx_state[i].ss_deleted) |
| 579 | continue; |
| 580 | for (j = 0; j < i; j++) { |
| 581 | if (xx_state[j].ss_deleted) |
| 582 | continue; |
| 583 | if (samestate(&xx_state[i], &xx_state[j])) { |
| 584 | xx_state[i].ss_deleted++; |
| 585 | renamestates(xx_nstates, xx_state, |
| 586 | i, j); |
| 587 | changes++; |
| 588 | break; |
| 589 | } |
| 590 | } |
| 591 | } |
| 592 | } while (changes); |
Guido van Rossum | 85a5fbb | 1990-10-14 12:07:46 +0000 | [diff] [blame] | 593 | } |
| 594 | |
| 595 | |
| 596 | /* PART FOUR -- GENERATE PARSING TABLES */ |
| 597 | |
| 598 | /* Convert the DFA into a grammar that can be used by our parser */ |
| 599 | |
Guido van Rossum | fd8a393 | 1996-12-02 18:27:33 +0000 | [diff] [blame] | 600 | static void |
Thomas Wouters | 23c9e00 | 2000-07-22 19:20:54 +0000 | [diff] [blame] | 601 | convert(dfa *d, int xx_nstates, ss_state *xx_state) |
Guido van Rossum | 85a5fbb | 1990-10-14 12:07:46 +0000 | [diff] [blame] | 602 | { |
Antoine Pitrou | c83ea13 | 2010-05-09 14:46:46 +0000 | [diff] [blame] | 603 | int i, j; |
| 604 | ss_state *yy; |
| 605 | ss_arc *zz; |
| 606 | |
| 607 | for (i = 0; i < xx_nstates; i++) { |
| 608 | yy = &xx_state[i]; |
| 609 | if (yy->ss_deleted) |
| 610 | continue; |
| 611 | yy->ss_rename = addstate(d); |
| 612 | } |
| 613 | |
| 614 | for (i = 0; i < xx_nstates; i++) { |
| 615 | yy = &xx_state[i]; |
| 616 | if (yy->ss_deleted) |
| 617 | continue; |
| 618 | for (j = 0; j < yy->ss_narcs; j++) { |
| 619 | zz = &yy->ss_arc[j]; |
| 620 | addarc(d, yy->ss_rename, |
| 621 | xx_state[zz->sa_arrow].ss_rename, |
| 622 | zz->sa_label); |
| 623 | } |
| 624 | if (yy->ss_finish) |
| 625 | addarc(d, yy->ss_rename, yy->ss_rename, 0); |
| 626 | } |
| 627 | |
| 628 | d->d_initial = 0; |
Guido van Rossum | 85a5fbb | 1990-10-14 12:07:46 +0000 | [diff] [blame] | 629 | } |
| 630 | |
| 631 | |
| 632 | /* PART FIVE -- GLUE IT ALL TOGETHER */ |
| 633 | |
| 634 | static grammar * |
Thomas Wouters | 23c9e00 | 2000-07-22 19:20:54 +0000 | [diff] [blame] | 635 | maketables(nfagrammar *gr) |
Guido van Rossum | 85a5fbb | 1990-10-14 12:07:46 +0000 | [diff] [blame] | 636 | { |
Antoine Pitrou | c83ea13 | 2010-05-09 14:46:46 +0000 | [diff] [blame] | 637 | int i; |
| 638 | nfa *nf; |
| 639 | dfa *d; |
| 640 | grammar *g; |
| 641 | |
| 642 | if (gr->gr_nnfas == 0) |
| 643 | return NULL; |
| 644 | g = newgrammar(gr->gr_nfa[0]->nf_type); |
| 645 | /* XXX first rule must be start rule */ |
| 646 | g->g_ll = gr->gr_ll; |
| 647 | |
| 648 | for (i = 0; i < gr->gr_nnfas; i++) { |
| 649 | nf = gr->gr_nfa[i]; |
| 650 | if (Py_DebugFlag) { |
| 651 | printf("Dump of NFA for '%s' ...\n", nf->nf_name); |
| 652 | dumpnfa(&gr->gr_ll, nf); |
| 653 | printf("Making DFA for '%s' ...\n", nf->nf_name); |
| 654 | } |
| 655 | d = adddfa(g, nf->nf_type, nf->nf_name); |
| 656 | makedfa(gr, gr->gr_nfa[i], d); |
| 657 | } |
| 658 | |
| 659 | return g; |
Guido van Rossum | 85a5fbb | 1990-10-14 12:07:46 +0000 | [diff] [blame] | 660 | } |
| 661 | |
| 662 | grammar * |
Thomas Wouters | 23c9e00 | 2000-07-22 19:20:54 +0000 | [diff] [blame] | 663 | pgen(node *n) |
Guido van Rossum | 85a5fbb | 1990-10-14 12:07:46 +0000 | [diff] [blame] | 664 | { |
Antoine Pitrou | c83ea13 | 2010-05-09 14:46:46 +0000 | [diff] [blame] | 665 | nfagrammar *gr; |
| 666 | grammar *g; |
| 667 | |
| 668 | gr = metacompile(n); |
| 669 | g = maketables(gr); |
| 670 | translatelabels(g); |
| 671 | addfirstsets(g); |
| 672 | PyObject_FREE(gr); |
| 673 | return g; |
Guido van Rossum | 85a5fbb | 1990-10-14 12:07:46 +0000 | [diff] [blame] | 674 | } |
| 675 | |
Guido van Rossum | d3ab37f | 2003-04-17 14:55:42 +0000 | [diff] [blame] | 676 | grammar * |
| 677 | Py_pgen(node *n) |
| 678 | { |
| 679 | return pgen(n); |
| 680 | } |
Guido van Rossum | 85a5fbb | 1990-10-14 12:07:46 +0000 | [diff] [blame] | 681 | |
| 682 | /* |
| 683 | |
| 684 | Description |
| 685 | ----------- |
| 686 | |
| 687 | Input is a grammar in extended BNF (using * for repetition, + for |
| 688 | at-least-once repetition, [] for optional parts, | for alternatives and |
| 689 | () for grouping). This has already been parsed and turned into a parse |
| 690 | tree. |
| 691 | |
| 692 | Each rule is considered as a regular expression in its own right. |
| 693 | It is turned into a Non-deterministic Finite Automaton (NFA), which |
| 694 | is then turned into a Deterministic Finite Automaton (DFA), which is then |
| 695 | optimized to reduce the number of states. See [Aho&Ullman 77] chapter 3, |
| 696 | or similar compiler books (this technique is more often used for lexical |
| 697 | analyzers). |
| 698 | |
| 699 | The DFA's are used by the parser as parsing tables in a special way |
| 700 | that's probably unique. Before they are usable, the FIRST sets of all |
| 701 | non-terminals are computed. |
| 702 | |
| 703 | Reference |
| 704 | --------- |
| 705 | |
| 706 | [Aho&Ullman 77] |
Antoine Pitrou | c83ea13 | 2010-05-09 14:46:46 +0000 | [diff] [blame] | 707 | Aho&Ullman, Principles of Compiler Design, Addison-Wesley 1977 |
| 708 | (first edition) |
Guido van Rossum | 85a5fbb | 1990-10-14 12:07:46 +0000 | [diff] [blame] | 709 | |
| 710 | */ |