blob: fa27300b20fe320b5682c90a05008fc895007060 [file] [log] [blame]
Guido van Rossumf70e43a1991-02-19 12:39:46 +00001
Guido van Rossum85a5fbb1990-10-14 12:07:46 +00002/* Grammar implementation */
3
Tim Peters1ca12962001-12-04 03:18:48 +00004#include "Python.h"
Guido van Rossum3f5da241990-12-20 15:06:42 +00005#include "pgenheaders.h"
6
Guido van Rossum85a5fbb1990-10-14 12:07:46 +00007#include <ctype.h>
8
Guido van Rossum85a5fbb1990-10-14 12:07:46 +00009#include "token.h"
10#include "grammar.h"
11
Guido van Rossum86bea461997-04-29 21:03:06 +000012extern int Py_DebugFlag;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000013
14grammar *
Thomas Wouters23c9e002000-07-22 19:20:54 +000015newgrammar(int start)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000016{
17 grammar *g;
18
Thomas Wouters49fd7fa2006-04-21 10:40:58 +000019 g = (grammar *)PyObject_MALLOC(sizeof(grammar));
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000020 if (g == NULL)
Guido van Rossum86bea461997-04-29 21:03:06 +000021 Py_FatalError("no mem for new grammar");
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000022 g->g_ndfas = 0;
23 g->g_dfa = NULL;
24 g->g_start = start;
25 g->g_ll.ll_nlabels = 0;
26 g->g_ll.ll_label = NULL;
Guido van Rossum588633d1994-12-30 15:46:02 +000027 g->g_accel = 0;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000028 return g;
29}
30
31dfa *
Thomas Wouters23c9e002000-07-22 19:20:54 +000032adddfa(grammar *g, int type, char *name)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000033{
34 dfa *d;
35
Thomas Wouters49fd7fa2006-04-21 10:40:58 +000036 g->g_dfa = (dfa *)PyObject_REALLOC(g->g_dfa,
37 sizeof(dfa) * (g->g_ndfas + 1));
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000038 if (g->g_dfa == NULL)
Guido van Rossum86bea461997-04-29 21:03:06 +000039 Py_FatalError("no mem to resize dfa in adddfa");
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000040 d = &g->g_dfa[g->g_ndfas++];
41 d->d_type = type;
Guido van Rossumd3ab37f2003-04-17 14:55:42 +000042 d->d_name = strdup(name);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000043 d->d_nstates = 0;
44 d->d_state = NULL;
45 d->d_initial = -1;
46 d->d_first = NULL;
47 return d; /* Only use while fresh! */
48}
49
50int
Thomas Wouters23c9e002000-07-22 19:20:54 +000051addstate(dfa *d)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000052{
53 state *s;
54
Thomas Wouters49fd7fa2006-04-21 10:40:58 +000055 d->d_state = (state *)PyObject_REALLOC(d->d_state,
56 sizeof(state) * (d->d_nstates + 1));
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000057 if (d->d_state == NULL)
Guido van Rossum86bea461997-04-29 21:03:06 +000058 Py_FatalError("no mem to resize state in addstate");
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000059 s = &d->d_state[d->d_nstates++];
60 s->s_narcs = 0;
61 s->s_arc = NULL;
Guido van Rossum588633d1994-12-30 15:46:02 +000062 s->s_lower = 0;
63 s->s_upper = 0;
64 s->s_accel = NULL;
65 s->s_accept = 0;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000066 return s - d->d_state;
67}
68
69void
Thomas Wouters23c9e002000-07-22 19:20:54 +000070addarc(dfa *d, int from, int to, int lbl)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000071{
72 state *s;
73 arc *a;
74
75 assert(0 <= from && from < d->d_nstates);
76 assert(0 <= to && to < d->d_nstates);
77
78 s = &d->d_state[from];
Thomas Wouters49fd7fa2006-04-21 10:40:58 +000079 s->s_arc = (arc *)PyObject_REALLOC(s->s_arc, sizeof(arc) * (s->s_narcs + 1));
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000080 if (s->s_arc == NULL)
Guido van Rossum86bea461997-04-29 21:03:06 +000081 Py_FatalError("no mem to resize arc list in addarc");
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000082 a = &s->s_arc[s->s_narcs++];
83 a->a_lbl = lbl;
84 a->a_arrow = to;
85}
86
87int
Thomas Wouters23c9e002000-07-22 19:20:54 +000088addlabel(labellist *ll, int type, char *str)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000089{
90 int i;
91 label *lb;
92
93 for (i = 0; i < ll->ll_nlabels; i++) {
94 if (ll->ll_label[i].lb_type == type &&
95 strcmp(ll->ll_label[i].lb_str, str) == 0)
96 return i;
97 }
Thomas Wouters49fd7fa2006-04-21 10:40:58 +000098 ll->ll_label = (label *)PyObject_REALLOC(ll->ll_label,
99 sizeof(label) * (ll->ll_nlabels + 1));
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000100 if (ll->ll_label == NULL)
Guido van Rossum86bea461997-04-29 21:03:06 +0000101 Py_FatalError("no mem to resize labellist in addlabel");
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000102 lb = &ll->ll_label[ll->ll_nlabels++];
103 lb->lb_type = type;
Guido van Rossumd3ab37f2003-04-17 14:55:42 +0000104 lb->lb_str = strdup(str);
105 if (Py_DebugFlag)
Guido van Rossumc6966172004-03-20 22:34:14 +0000106 printf("Label @ %8p, %d: %s\n", ll, ll->ll_nlabels,
Guido van Rossumd3ab37f2003-04-17 14:55:42 +0000107 PyGrammar_LabelRepr(lb));
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000108 return lb - ll->ll_label;
109}
110
111/* Same, but rather dies than adds */
112
113int
Thomas Wouters23c9e002000-07-22 19:20:54 +0000114findlabel(labellist *ll, int type, char *str)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000115{
116 int i;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000117
118 for (i = 0; i < ll->ll_nlabels; i++) {
119 if (ll->ll_label[i].lb_type == type /*&&
120 strcmp(ll->ll_label[i].lb_str, str) == 0*/)
121 return i;
122 }
123 fprintf(stderr, "Label %d/'%s' not found\n", type, str);
Guido van Rossum86bea461997-04-29 21:03:06 +0000124 Py_FatalError("grammar.c:findlabel()");
Guido van Rossumfd8a3931996-12-02 18:27:33 +0000125 return 0; /* Make gcc -Wall happy */
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000126}
127
Guido van Rossum3f5da241990-12-20 15:06:42 +0000128/* Forward */
Tim Petersdbd9ba62000-07-09 03:09:57 +0000129static void translabel(grammar *, label *);
Guido van Rossum3f5da241990-12-20 15:06:42 +0000130
131void
Thomas Wouters23c9e002000-07-22 19:20:54 +0000132translatelabels(grammar *g)
Guido van Rossum3f5da241990-12-20 15:06:42 +0000133{
134 int i;
Guido van Rossum588633d1994-12-30 15:46:02 +0000135
Guido van Rossum408027e1996-12-30 16:17:54 +0000136#ifdef Py_DEBUG
Guido van Rossum3f5da241990-12-20 15:06:42 +0000137 printf("Translating labels ...\n");
Guido van Rossum588633d1994-12-30 15:46:02 +0000138#endif
Guido van Rossum3f5da241990-12-20 15:06:42 +0000139 /* Don't translate EMPTY */
140 for (i = EMPTY+1; i < g->g_ll.ll_nlabels; i++)
141 translabel(g, &g->g_ll.ll_label[i]);
142}
143
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000144static void
Thomas Wouters23c9e002000-07-22 19:20:54 +0000145translabel(grammar *g, label *lb)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000146{
147 int i;
148
Guido van Rossum86bea461997-04-29 21:03:06 +0000149 if (Py_DebugFlag)
150 printf("Translating label %s ...\n", PyGrammar_LabelRepr(lb));
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000151
152 if (lb->lb_type == NAME) {
153 for (i = 0; i < g->g_ndfas; i++) {
154 if (strcmp(lb->lb_str, g->g_dfa[i].d_name) == 0) {
Guido van Rossum86bea461997-04-29 21:03:06 +0000155 if (Py_DebugFlag)
156 printf(
157 "Label %s is non-terminal %d.\n",
158 lb->lb_str,
159 g->g_dfa[i].d_type);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000160 lb->lb_type = g->g_dfa[i].d_type;
Guido van Rossumd3ab37f2003-04-17 14:55:42 +0000161 free(lb->lb_str);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000162 lb->lb_str = NULL;
163 return;
164 }
165 }
166 for (i = 0; i < (int)N_TOKENS; i++) {
Guido van Rossum86bea461997-04-29 21:03:06 +0000167 if (strcmp(lb->lb_str, _PyParser_TokenNames[i]) == 0) {
168 if (Py_DebugFlag)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000169 printf("Label %s is terminal %d.\n",
170 lb->lb_str, i);
171 lb->lb_type = i;
Guido van Rossumd3ab37f2003-04-17 14:55:42 +0000172 free(lb->lb_str);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000173 lb->lb_str = NULL;
174 return;
175 }
176 }
177 printf("Can't translate NAME label '%s'\n", lb->lb_str);
178 return;
179 }
180
181 if (lb->lb_type == STRING) {
Neal Norwitz30b5c5d2005-12-19 06:05:18 +0000182 if (isalpha(Py_CHARMASK(lb->lb_str[1])) ||
183 lb->lb_str[1] == '_') {
Guido van Rossum1d5735e1994-08-30 08:27:36 +0000184 char *p;
Guido van Rossumd3ab37f2003-04-17 14:55:42 +0000185 char *src;
186 char *dest;
187 size_t name_len;
Guido van Rossum86bea461997-04-29 21:03:06 +0000188 if (Py_DebugFlag)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000189 printf("Label %s is a keyword\n", lb->lb_str);
190 lb->lb_type = NAME;
Guido van Rossumd3ab37f2003-04-17 14:55:42 +0000191 src = lb->lb_str + 1;
192 p = strchr(src, '\'');
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000193 if (p)
Guido van Rossumd3ab37f2003-04-17 14:55:42 +0000194 name_len = p - src;
195 else
196 name_len = strlen(src);
Thomas Wouters49fd7fa2006-04-21 10:40:58 +0000197 dest = (char *)malloc(name_len + 1);
Thomas Wouters00ee7ba2006-08-21 19:07:27 +0000198 if (!dest) {
199 printf("Can't alloc dest '%s'\n", src);
200 return;
201 }
Guido van Rossumd3ab37f2003-04-17 14:55:42 +0000202 strncpy(dest, src, name_len);
203 dest[name_len] = '\0';
204 free(lb->lb_str);
205 lb->lb_str = dest;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000206 }
Guido van Rossumc64d04d1991-10-20 20:20:00 +0000207 else if (lb->lb_str[2] == lb->lb_str[0]) {
Guido van Rossum86bea461997-04-29 21:03:06 +0000208 int type = (int) PyToken_OneChar(lb->lb_str[1]);
Guido van Rossumc64d04d1991-10-20 20:20:00 +0000209 if (type != OP) {
210 lb->lb_type = type;
Guido van Rossumd3ab37f2003-04-17 14:55:42 +0000211 free(lb->lb_str);
Guido van Rossumc64d04d1991-10-20 20:20:00 +0000212 lb->lb_str = NULL;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000213 }
214 else
Guido van Rossumc64d04d1991-10-20 20:20:00 +0000215 printf("Unknown OP label %s\n",
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000216 lb->lb_str);
217 }
Guido van Rossumc64d04d1991-10-20 20:20:00 +0000218 else if (lb->lb_str[2] && lb->lb_str[3] == lb->lb_str[0]) {
Guido van Rossum86bea461997-04-29 21:03:06 +0000219 int type = (int) PyToken_TwoChars(lb->lb_str[1],
Guido van Rossumc64d04d1991-10-20 20:20:00 +0000220 lb->lb_str[2]);
221 if (type != OP) {
222 lb->lb_type = type;
Guido van Rossumd3ab37f2003-04-17 14:55:42 +0000223 free(lb->lb_str);
Guido van Rossumc64d04d1991-10-20 20:20:00 +0000224 lb->lb_str = NULL;
225 }
226 else
227 printf("Unknown OP label %s\n",
228 lb->lb_str);
229 }
Thomas Wouters434d0822000-08-24 20:11:32 +0000230 else if (lb->lb_str[2] && lb->lb_str[3] && lb->lb_str[4] == lb->lb_str[0]) {
231 int type = (int) PyToken_ThreeChars(lb->lb_str[1],
232 lb->lb_str[2],
233 lb->lb_str[3]);
234 if (type != OP) {
235 lb->lb_type = type;
Guido van Rossumd3ab37f2003-04-17 14:55:42 +0000236 free(lb->lb_str);
Thomas Wouters434d0822000-08-24 20:11:32 +0000237 lb->lb_str = NULL;
238 }
239 else
240 printf("Unknown OP label %s\n",
241 lb->lb_str);
242 }
Guido van Rossumc64d04d1991-10-20 20:20:00 +0000243 else
244 printf("Can't translate STRING label %s\n",
245 lb->lb_str);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000246 }
247 else
Guido van Rossum86bea461997-04-29 21:03:06 +0000248 printf("Can't translate label '%s'\n",
249 PyGrammar_LabelRepr(lb));
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000250}