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