1 /* $NetBSD: llparse.c,v 1.7 2002/05/16 19:30:41 wiz Exp $ */
2
3 /*
4 * ************************* NOTICE *******************************
5 * This code is in the public domain. It cannot be copyrighted.
6 * This ll parser was originally written by Keith Thompson for the
7 * University of Wisconsin Crystal project.
8 * It was based on an FMQ lr parser written by Jon Mauney at the
9 * University of Wisconsin.
10 * It was subsequently modified very slightly by Nancy Hall at the
11 * University of Wisconsin for the Crystal project.
12 * ****************************************************************
13 */
14
15 #include <sys/cdefs.h>
16 __KERNEL_RCSID(0, "$NetBSD: llparse.c,v 1.7 2002/05/16 19:30:41 wiz Exp $");
17
18 #include "xebec.h"
19 #include "llparse.h"
20 #include "main.h"
21 #include <stdio.h>
22
23 #include "debug.h"
24
25 #define LLMINACTION -LLINF
26
27 short llparsestack[STACKSIZE];
28 short llstackptr = 0;
29 LLtoken lltoken;
30
31 void prt_token();
32
33 int
34 llparse()
35 {
36 register int havetoken = FALSE;
37 register int sym;
38 register LLtoken *t = &lltoken;
39 register int parseaction;
40 register int accepted = FALSE;
41
42 llpushprod(llnprods-1); /* $$$ ::= <start symbol> */
43
44 do {
45 sym = llparsestack[llstackptr];
46 IFDEBUG(L)
47 printf("llparse() top of loop, llstackptr=%d, sym=%d\n",
48 llstackptr, sym);
49 ENDDEBUG
50
51 if(sym < 0) {
52 /* action symbol */
53 if(sym <= LLMINACTION) {
54 for(;sym<=LLMINACTION;sym++) {
55 llaction(1, t); /* calls llfinprod */
56 }
57 llstackptr--;
58 continue;
59 } else { llaction(-sym, t);
60 llstackptr--;
61 continue;
62 }
63 }
64
65 if(sym < llnterms) {
66
67 /* it's a terminal symbol */
68
69 if(!havetoken) {
70 llgettoken(t);
71 havetoken = TRUE;
72 }
73
74 if(sym == t->llterm) {
75 llpushattr(t->llattrib);
76 llaccept(t);
77 llstackptr--; /* pop terminal */
78 if(t->llterm == llnterms-1) { /* end symbol $$$ */
79 accepted = TRUE;
80 } else {
81 havetoken = FALSE;
82 }
83 } else {
84 llparsererror(t); /* wrong terminal on input */
85 havetoken = FALSE;
86 }
87 continue;
88 }
89
90 /* non terminal */
91
92 if(!havetoken) {
93 llgettoken(t);
94 havetoken = TRUE;
95 }
96
97 /* consult parse table for new production */
98 parseaction = llfindaction(sym, t->llterm);
99
100 if(parseaction == 0) {
101 /* error entry */
102 llparsererror(t);
103 havetoken = FALSE;
104 continue;
105 }
106
107 if(llepsilon[parseaction]) {
108 /* epsilon production */
109 if(llepsilonok(t->llterm)) {
110 llstackptr--; /* pop nonterminal */
111 llpushprod(parseaction); /* push rhs of production */
112 } else {
113 llparsererror(t);
114 havetoken = FALSE;
115 }
116 } else {
117 llstackptr--; /* pop nonterminal */
118 llpushprod(parseaction); /* push rhs of production */
119 }
120 } while(!accepted);
121
122 return(0);
123 }
124
125 void
126 llpushprod(prod) /* recognize production prod - push rhs on stack */
127 short prod;
128 {
129 register int start;
130 register int length;
131 register int count;
132
133 start = llprodindex[prod].llprodstart;
134 length = llprodindex[prod].llprodlength;
135
136 IFDEBUG(L)
137 printf("llpushprod(%d) llstackptr=0x%x(%d), length = 0x%x(%d)\n",
138 prod, llstackptr, llstackptr, length , length);
139 /*
140 dump_parse_stack();
141 */
142 ENDDEBUG
143 if(llstackptr+length >= STACKSIZE) {
144 fprintf(stderr,"Parse stack overflow. llstackptr=0x%x, length=0x%x\n",
145 llstackptr, length);
146 Exit(-1);
147 }
148
149
150 llsetattr(llprodindex[prod].llprodtlen);
151
152 /* put a marker on the stack to mark beginning of production */
153 if(llparsestack[llstackptr] <= LLMINACTION) {
154 (llparsestack[llstackptr]) --; /* if there's already one there, don't
155 put another on; just let it represent all of
156 the adjacent markers */
157 }
158 else {
159 llstackptr++;
160 llparsestack[llstackptr] = LLMINACTION;
161 }
162
163 for(count=0; count<length; count++) {
164 llstackptr++;
165 llparsestack[llstackptr] = llproductions[start++];
166 }
167 if(llstackptr > STACKSIZE) {
168 fprintf(stderr, "PARSE STACK OVERFLOW! \n"); Exit(-1);
169 Exit(-1);
170 }
171 }
172
173 int
174 llepsilonok(term)
175 {
176 register int ptr;
177 register int sym;
178 register int pact;
179 register int nomore;
180 register int rval;
181
182 IFDEBUG(L)
183 printf("llepsilonok() enter\n");
184 ENDDEBUG
185 rval = TRUE;
186
187 ptr = llstackptr;
188
189 do {
190 sym = llparsestack[ptr];
191
192 if(sym < 0) {
193 ptr--;
194 nomore = ptr == 0;
195 continue;
196 }
197
198 if(sym < llnterms) {
199 nomore = TRUE;
200 rval = sym == term;
201 continue;
202 }
203
204 pact = llfindaction(sym, term);
205
206 if(pact == 0) {
207 nomore = TRUE;
208 rval = FALSE;
209 continue;
210 }
211
212 if(llepsilon[pact] == TRUE) {
213 ptr--;
214 nomore = ptr == 0;
215 }
216 else {
217 nomore = TRUE;
218 }
219
220 } while(!nomore);
221
222 return(rval);
223 }
224
225
226 short
227 llfindaction(sym, term)
228 {
229 register int index;
230
231 IFDEBUG(L)
232 printf("llfindaction(sym=%d, term=%d) enter \n", sym, term);
233 ENDDEBUG
234 index = llparseindex[sym];
235
236 while(llparsetable[index].llterm != 0) {
237 if(llparsetable[index].llterm == term) {
238 return(llparsetable[index].llprod);
239 }
240 index++;
241 }
242 return(0);
243 }
244
245 void
246 llparsererror(token)
247 LLtoken *token;
248 {
249 IFDEBUG(L)
250 fprintf(stderr,"llparsererror() enter\n");
251 prt_token(token);
252 ENDDEBUG
253
254 fprintf(stderr, "Syntax error: ");
255 prt_token(token);
256 dump_buffer();
257 Exit(-1);
258 }
259
260 void
261 llgettoken(token)
262 LLtoken *token;
263 {
264 llscan(token);
265 token->llstate = NORMAL;
266 IFDEBUG(L)
267 printf("llgettoken(): ");
268 prt_token(token);
269 ENDDEBUG
270 }
271
272
273 /******************************************************************************
274
275 Attribute support routines
276
277 ******************************************************************************/
278 /*
279 ** attribute stack
280 **
281 ** AttrStack = stack of record
282 ** values : array of values;
283 ** ptr : index;
284 ** end;
285 **
286 */
287
288 LLattrib llattributes[LLMAXATTR];
289 int llattrtop = 0;
290
291 struct llattr llattrdesc[LLMAXDESC];
292
293 int lldescindex = 1;
294
295 void
296 llsetattr(n)
297 int n;
298 {
299 register struct llattr *ptr;
300
301 IFDEBUG(L)
302 printf("llsetattr(%d) enter\n",n);
303 ENDDEBUG
304 if(lldescindex >= LLMAXDESC) {
305 fprintf(stdout, "llattribute stack overflow: desc\n");
306 fprintf(stdout,
307 "lldescindex=0x%x, llattrtop=0x%x\n",lldescindex, llattrtop);
308 Exit(-1);
309 }
310 ptr = &llattrdesc[lldescindex];
311 ptr->llabase = &llattributes[llattrtop];
312 ptr->lloldtop = ++llattrtop;
313 ptr->llaindex = 1;
314 ptr->llacnt = n+1; /* the lhs ALWAYS uses an attr; it remains on the
315 stack when the production is recognized */
316 lldescindex++;
317 }
318
319 void
320 llpushattr(attr)
321 LLattrib attr;
322 {
323 struct llattr *a;
324
325 IFDEBUG(L)
326 printf("llpushattr() enter\n");
327 ENDDEBUG
328 if(llattrtop + 1 > LLMAXATTR) {
329 fprintf(stderr, "ATTRIBUTE STACK OVERFLOW!\n");
330 Exit(-1);
331 }
332 a = &llattrdesc[lldescindex-1];
333 llattributes[llattrtop++] = attr;
334 a->llaindex++; /* inc count of attrs on the stack for this prod */
335 }
336
337 void
338 llfinprod()
339 {
340 IFDEBUG(L)
341 printf("llfinprod() enter\n");
342 ENDDEBUG
343 lldescindex--;
344 llattrtop = llattrdesc[lldescindex].lloldtop;
345 llattrdesc[lldescindex-1].llaindex++; /* lhs-of-prod.attr stays on
346 the stack; it is now one of the rhs attrs of the now-top production
347 on the stack */
348 }
349
350 #ifndef LINT
351 #ifdef DEBUG
352 void
353 dump_parse_stack()
354 {
355 int ind;
356
357 printf("PARSE STACK:\n");
358 for(ind=llstackptr; ind>=0; ind--) {
359 printf("%d\t%d\t%s\n",
360 ind, llparsestack[ind],
361 llparsestack[ind]<0? "Action symbol" : llstrings[llparsestack[ind]]);
362 }
363 }
364
365 #endif /* DEBUG */
366 #endif /* !LINT */
367
368 void
369 prt_token(t)
370 LLtoken *t;
371 {
372 fprintf(stdout, "t at 0x%p\n", t);
373 fprintf(stdout, "t->llterm=0x%x\n", t->llterm); (void) fflush(stdout);
374 fprintf(stdout, "TOK: %s\n", llstrings[t->llterm]);
375 (void) fflush(stdout);
376 #ifdef LINT
377 /* to make lint shut up */
378 fprintf(stdout, "", llnterms, llnsyms, llnprods, llinfinite);
379 #endif /* LINT */
380 }
Cache object: bd3821d48e9ceddbac66302cc3190368
|