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