1 /*
2
3 This file is part of the Maude 2 interpreter.
4
5 Copyright 1997-2003 SRI International, Menlo Park, CA 94025, USA.
6
7 This program is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2 of the License, or
10 (at your option) any later version.
11
12 This program is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with this program; if not, write to the Free Software
19 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307, USA.
20
21 */
22
23 /************************************************
24 ** SCP Parsing Algorithm **
25 ** Maude Implementation **
26 ** Jose F. Quesada **
27 ** CSL - SRI Int. 1998 **
28 ************************************************/
29
30 /*******
31 ******* scp_compiler.cc
32 *******/
33
34 #include "scp_parser.hh"
35
36 static int auxntm;
37 static int auxpbase;
38
insertProd(int xlhs,const Vector<int> & xrhs,int xprec,const Vector<int> & xgather)39 void ScpParser::insertProd(int xlhs, const Vector<int>& xrhs,
40 int xprec, const Vector<int>& xgather)
41 {
42 register int regrhs;
43 register int reggather;
44 register int regcounter;
45 curprodtn ++;
46
47 Assert(!compiled,
48 "SCP-ERROR: call to insertProd after parseSentence" << endl);
49
50 Assert(xlhs < 0,
51 "SCP-ERROR: Bad LHS (" << xlhs << ") " <<
52 "in production " << curprodtn-1 << endl);
53 Assert(xrhs.length() > 0,
54 "SCP-ERROR: RHS empty " <<
55 "in production " << curprodtn-1 << endl);
56
57 if (curprodtn >= lenprodtn) {
58 ScpProdtn* xmemprodtn = new ScpProdtn[lenprodtn+ADDPRODTN];
59 memcpy(xmemprodtn,memprodtn,lenprodtn*sizeof(ScpProdtn));
60 memset(xmemprodtn+lenprodtn,0,ADDPRODTN*sizeof(ScpProdtn));
61 lenprodtn += ADDPRODTN;
62 delete [] memprodtn;
63 memprodtn = xmemprodtn;
64 }
65
66 ScpProdtn* prodtn = &memprodtn[curprodtn];
67
68 prodtn->lhs = insertBasePrecNT(xlhs,xprec);
69 memabslnt[-prodtn->lhs].lhsdefs ++;
70
71 regrhs = xrhs.length();
72 prodtn->lrhs = regrhs;
73 if (currhs+regrhs > lenrhs) {
74 int* xmemrhs = new int[lenrhs+regrhs+ADDRHS];
75 memcpy(xmemrhs,memrhs,lenrhs*sizeof(int));
76 lenrhs += regrhs+ADDRHS;
77 delete [] memrhs;
78 memrhs = xmemrhs;
79 }
80 prodtn->rhs = currhs;
81 reggather = 0;
82 for (regcounter=0; regrhs; regrhs--) {
83 if (xrhs[regcounter] < 0) {
84 Assert(reggather < xgather.length(),
85 "SCP-ERROR: Insufficient gather values " <<
86 "in production " << curprodtn-1 << endl);
87 memrhs[currhs++] = insertBasePrecNT(xrhs[regcounter++],
88 xgather[reggather++]);
89 } else {
90 if (xrhs[regcounter] > maxtermn)
91 maxtermn = xrhs[regcounter];
92 memrhs[currhs++] = xrhs[regcounter++];
93 }
94 }
95 prodtn->lgather = reggather;
96 prodtn->bubble = 0;
97 }
98
insertBasePrecNT(int baseNT,int precNT)99 int ScpParser::insertBasePrecNT(int baseNT,int precNT)
100 {
101 if (baseNT < maxbasent) {
102 maxbasent = baseNT;
103 if (-baseNT >= lenbasent) {
104 ScpBaseNT* xmembasent = new ScpBaseNT[-baseNT+ADDBASENT];
105 memcpy(xmembasent,membasent,lenbasent*sizeof(ScpBaseNT));
106 memset(xmembasent+lenbasent,-1,
107 (-baseNT+ADDBASENT-lenbasent)*sizeof(ScpBaseNT));
108 lenbasent = -baseNT+ADDBASENT;
109 delete [] membasent;
110 membasent = xmembasent;
111 }
112 }
113
114 if (membasent[-baseNT].smallestPrec == -1) {
115 membasent[-baseNT].smallestPrec = precNT;
116 membasent[-baseNT].largestPrec = precNT;
117 maxabslnt--;
118 if (-maxabslnt >= lenabslnt) {
119 ScpAbslNT* xmemabslnt = new ScpAbslNT[lenabslnt+ADDABSLNT];
120 memcpy(xmemabslnt,memabslnt,lenabslnt*sizeof(ScpAbslNT));
121 memset(xmemabslnt+lenabslnt,0,ADDABSLNT*sizeof(ScpAbslNT));
122 lenabslnt += ADDABSLNT;
123 delete [] memabslnt;
124 memabslnt = xmemabslnt;
125 }
126 memabslnt[-maxabslnt].baseNT = baseNT;
127 memabslnt[-maxabslnt].precNT = precNT;
128 memabslnt[-maxabslnt].nextNT = 0;
129 membasent[-baseNT].firstAbs = maxabslnt;
130 membasent[-baseNT].lastAbs = maxabslnt;
131 return maxabslnt;
132 } else if (precNT < membasent[-baseNT].smallestPrec) {
133 membasent[-baseNT].smallestPrec = precNT;
134 maxabslnt--;
135 if (-maxabslnt >= lenabslnt) {
136 ScpAbslNT* xmemabslnt = new ScpAbslNT[lenabslnt+ADDABSLNT];
137 memcpy(xmemabslnt,memabslnt,lenabslnt*sizeof(ScpAbslNT));
138 memset(xmemabslnt+lenabslnt,0,ADDABSLNT*sizeof(ScpAbslNT));
139 lenabslnt += ADDABSLNT;
140 delete [] memabslnt;
141 memabslnt = xmemabslnt;
142 }
143 memabslnt[-maxabslnt].baseNT = baseNT;
144 memabslnt[-maxabslnt].precNT = precNT;
145 memabslnt[-maxabslnt].nextNT = membasent[-baseNT].firstAbs;
146 membasent[-baseNT].firstAbs = maxabslnt;
147 return maxabslnt;
148 } else if (precNT > membasent[-baseNT].largestPrec) {
149 membasent[-baseNT].largestPrec = precNT;
150 maxabslnt--;
151 if (-maxabslnt >= lenabslnt) {
152 ScpAbslNT* xmemabslnt = new ScpAbslNT[lenabslnt+ADDABSLNT];
153 memcpy(xmemabslnt,memabslnt,lenabslnt*sizeof(ScpAbslNT));
154 memset(xmemabslnt+lenabslnt,0,ADDABSLNT*sizeof(ScpAbslNT));
155 lenabslnt += ADDABSLNT;
156 delete [] memabslnt;
157 memabslnt = xmemabslnt;
158 }
159 memabslnt[-maxabslnt].baseNT = baseNT;
160 memabslnt[-maxabslnt].precNT = precNT;
161 memabslnt[-maxabslnt].nextNT = 0;
162 memabslnt[-membasent[-baseNT].lastAbs].nextNT = maxabslnt;
163 membasent[-baseNT].lastAbs = maxabslnt;
164 return maxabslnt;
165 } else if (precNT == membasent[-baseNT].smallestPrec) {
166 return membasent[-baseNT].firstAbs;
167 } else if (precNT == membasent[-baseNT].largestPrec) {
168 return membasent[-baseNT].lastAbs;
169 } else {
170 int curAbs = membasent[-baseNT].firstAbs;
171 int nexAbs = memabslnt[-curAbs].nextNT;
172 while (precNT >= memabslnt[-nexAbs].precNT) {
173 if (precNT == memabslnt[-nexAbs].precNT) {
174 return nexAbs;
175 }
176 curAbs = nexAbs;
177 nexAbs = memabslnt[-curAbs].nextNT;
178 }
179 maxabslnt--;
180 if (-maxabslnt >= lenabslnt) {
181 ScpAbslNT* xmemabslnt = new ScpAbslNT[lenabslnt+ADDABSLNT];
182 memcpy(xmemabslnt,memabslnt,lenabslnt*sizeof(ScpAbslNT));
183 memset(xmemabslnt+lenabslnt,0,ADDABSLNT*sizeof(ScpAbslNT));
184 lenabslnt += ADDABSLNT;
185 delete [] memabslnt;
186 memabslnt = xmemabslnt;
187 }
188 memabslnt[-maxabslnt].baseNT = baseNT;
189 memabslnt[-maxabslnt].precNT = precNT;
190 memabslnt[-maxabslnt].nextNT = nexAbs;
191 memabslnt[-curAbs].nextNT = maxabslnt;
192 return maxabslnt;
193 }
194 }
195
getBaseNT(int absl)196 int ScpParser::getBaseNT(int absl)
197 {
198 return memabslnt[-absl].baseNT;
199 }
200
getPrecNT(int absl)201 int ScpParser::getPrecNT(int absl)
202 {
203 return memabslnt[-absl].precNT;
204 }
205
206
insertProd(int nonTerminal,int lowBound,int upperBound,int leftParenToken,int rightParenToken,const Vector<int> & exceptionTokenList)207 void ScpParser::insertProd( int nonTerminal,int lowBound,int upperBound,
208 int leftParenToken,int rightParenToken,
209 const Vector<int>& exceptionTokenList )
210 {
211 register int reglength;
212 register int regcounter;
213 curprodtn ++;
214
215 Assert(!compiled,
216 "SCP-ERROR: call to insertProd after parseSentence" << endl);
217
218 Assert(nonTerminal < 0,
219 "SCP-ERROR: Bad nonTerminal(bubble) (" <<
220 nonTerminal << ") " <<
221 "in production " << curprodtn << endl);
222 if (curprodtn >= lenprodtn) { // changed from > to fix bug 3/8/02 SME
223 ScpProdtn* xmemprodtn = new ScpProdtn[lenprodtn+ADDPRODTN];
224 memcpy(xmemprodtn,memprodtn,lenprodtn*sizeof(ScpProdtn));
225 memset(xmemprodtn+lenprodtn,0,ADDPRODTN*sizeof(ScpProdtn));
226 lenprodtn += ADDPRODTN;
227 delete [] memprodtn;
228 memprodtn = xmemprodtn;
229 }
230
231 ScpProdtn* prodtn = &memprodtn[curprodtn];
232
233 // Store the bubble in membubble
234 curbubble ++;
235 prodtn->bubble = curbubble;
236 prodtn->lgather = 0;
237
238 if (curbubble > lenbubble) {
239 ScpBubble* xmembubble = new ScpBubble[lenbubble+ADDBUBBLE];
240 memcpy(xmembubble,membubble,lenbubble*sizeof(ScpBubble));
241 lenbubble += ADDBUBBLE;
242 delete [] membubble;
243 membubble = xmembubble;
244 }
245 ScpBubble* bubble = &membubble[curbubble];
246 bubble->abslnt = insertBasePrecNT(nonTerminal,0);
247 memabslnt[-bubble->abslnt].bubbletermn = curbubble;
248 bubble->lbound = lowBound;
249 bubble->ubound = upperBound;
250 if (leftParenToken > maxtermn)
251 maxtermn = leftParenToken;
252 bubble->lparen = leftParenToken;
253 if (rightParenToken > maxtermn)
254 maxtermn = rightParenToken;
255 bubble->rparen = rightParenToken;
256 bubble->prodtn = curprodtn;
257
258 reglength = exceptionTokenList.length();
259 bubble->lexcept = reglength;
260 if (curexcept+reglength > lenexcept) {
261 int* xmemexcept = new int[lenexcept+ADDEXCEPT];
262 memcpy(xmemexcept,memexcept,lenexcept*sizeof(int));
263 lenexcept += ADDEXCEPT;
264 delete [] memexcept;
265 memexcept = xmemexcept;
266 }
267 bubble->except = curexcept;
268 for (regcounter=0; reglength; reglength--) {
269 if (exceptionTokenList[regcounter] > maxtermn)
270 maxtermn = exceptionTokenList[regcounter];
271 memexcept[curexcept++] = exceptionTokenList[regcounter++];
272 }
273 }
274
compileParser()275 void ScpParser::compileParser()
276 {
277 if (compiled)
278 return;
279
280 compiled = 1;
281 maxtermn ++; // 0-maxtermn => maxtermn+1
282 maxnontm = -maxabslnt+1;
283
284 /* Prod 0 */
285 memprodtn[0].lrhs = 2;
286 memprodtn[0].rhs = currhs;
287 memprodtn[0].lgather = 1;
288 /*
289 We seem to have MEMORY CORRUPTION when currhs == lenrhs or
290 currhs+1 == lenrhs because the memrhs is not being reallocated.
291
292 cerr << memprodtn[0].rhs << '\t' << currhs << '\t' << lenrhs << endl;
293
294 We add the following lines to fix this problem. 3/20/02 SME
295 */
296 const int extrarhs = 2;
297 if (currhs+extrarhs > lenrhs) {
298 int* xmemrhs = new int[lenrhs+extrarhs+ADDRHS];
299 memcpy(xmemrhs,memrhs,lenrhs*sizeof(int));
300 lenrhs += extrarhs+ADDRHS;
301 delete [] memrhs;
302 memrhs = xmemrhs;
303 }
304 /*
305 End of added code.
306 */
307 memrhs[memprodtn[0].rhs+1] = maxtermn + 10; // MEMORY CORRUPTION
308 memprodtn[0].bubble = 0;
309
310 /* covnttb ldertmtb ldernttb rdernttb invrdernttb */
311 /* covtmtb */
312 int lentbl = (maxnontm + maxtermn + maxnontm + maxnontm + 1) * (maxnontm);
313 covtbl = new int[lentbl];
314 memset(covtbl,0,lentbl*sizeof(int));
315 covnttb = covtbl;
316 ldertmtb = covtmtb = covnttb + (maxnontm*maxnontm);
317 ldernttb = ldertmtb + (maxtermn*maxnontm);
318 rdernttb = ldernttb + (maxnontm*maxnontm);
319 invrdernttb = rdernttb + (maxnontm*maxnontm);
320
321 /* rdernttb adjtb */
322 lentbl = (maxnontm + maxtermn) * (maxnontm);
323 adjtb = new char[lentbl];
324 memset(adjtb,0,lentbl*sizeof(char));
325
326 if (curbubble) {
327 lentbl = curbubble * maxtermn;
328 bubexcept = new char[lentbl];
329 memset(bubexcept,0,lentbl*sizeof(char));
330 }
331
332 compileDerivationTables();
333 compileCoverageTables();
334 compileAdjacencyTables();
335
336 memprodruntoken = new int[(curprodtn+1)*2];
337 memprodrunnode = memprodruntoken+(curprodtn+1);
338 }
339
compileDerivationTables()340 void ScpParser::compileDerivationTables()
341 {
342 register int tm;
343 register int addrbase = 0;
344
345 addrtermn = new int[maxtermn+maxnontm];
346 addrnontm = addrtermn+maxtermn;
347 for (tm = 0; tm < maxtermn; tm++,addrbase+=maxnontm)
348 addrtermn[tm] = addrbase;
349
350 register int ntm;
351 addrbase = maxnontm;
352 for (ntm = 1; ntm < maxnontm; ntm++,addrbase+=maxnontm)
353 addrnontm[ntm] = addrbase;
354
355 /* ldgrprodtn ldgrabslnt ldgrtermn */
356 /* rdgrprodtn rdgrabslnt rdgrtermn */
357 int lentbl = ((curprodtn+1) + maxnontm + maxtermn) * 2;
358
359 ldgrprodtn = new int[lentbl];
360
361 memset(ldgrprodtn,0,(lentbl)*sizeof(int));
362 ldgrabslnt = ldgrprodtn + (curprodtn+1);
363 ldgrtermn = ldgrabslnt + maxnontm;
364 rdgrprodtn = ldgrtermn + maxtermn;
365 rdgrabslnt = rdgrprodtn + (curprodtn+1);
366 rdgrtermn = rdgrabslnt + maxnontm;
367
368 compileLDerGraph();
369 compileLDerTable();
370 compileRDerGraph();
371 compileRDerTable();
372 }
373
compileLDerGraph()374 void ScpParser::compileLDerGraph()
375 {
376 register int ip;
377 register int rhs0;
378 register int lhs;
379 register int ldergraph;
380 register int prevldergraph;
381 register int addedldergraph;
382 ScpProdtn* prodtn;
383
384 for (ip = 1; ip <= curprodtn; ip++) {
385 prodtn = &memprodtn[ip];
386 if (!prodtn->bubble) {
387 rhs0 = memrhs[prodtn->rhs];
388 if (rhs0 < 0) {
389 // lhs = memrhs[prodtn->lhs];
390 lhs = prodtn->lhs;
391 ldergraph = ldgrabslnt[-rhs0];
392 if (!ldergraph)
393 ldgrabslnt[-rhs0] = ip;
394 else {
395 if (lhs == memprodtn[ldergraph].lhs) {
396 ldgrprodtn[ip] = ldergraph;
397 ldgrabslnt[-rhs0] = ip;
398 } else if (lhs > memprodtn[ldergraph].lhs) {
399 ldgrprodtn[ip] = ldergraph;
400 ldgrabslnt[-rhs0] = ip;
401 } else {
402 prevldergraph = ldergraph;
403 addedldergraph = 0;
404 ldergraph = ldgrprodtn[ldergraph];
405 while (!addedldergraph && ldergraph) {
406 if (lhs == memprodtn[ldergraph].lhs) {
407 ldgrprodtn[ip] = ldergraph;
408 ldgrprodtn[prevldergraph] = ip;
409 addedldergraph = 1;
410 } else if (lhs > memprodtn[ldergraph].lhs) {
411 ldgrprodtn[ip] = ldergraph;
412 ldgrprodtn[prevldergraph] = ip;
413 addedldergraph = 1;
414 } else {
415 prevldergraph = ldergraph;
416 ldergraph = ldgrprodtn[ldergraph];
417 }
418 }
419 if (!addedldergraph)
420 ldgrprodtn[prevldergraph] = ip;
421 }
422 }
423 } else {
424 // lhs = memrhs[prodtn->lhs];
425 lhs = prodtn->lhs;
426 ldergraph = ldgrtermn[rhs0];
427 if (!ldergraph) {
428 ldgrtermn[rhs0] = ip;
429 } else {
430 if (lhs == memprodtn[ldergraph].lhs) {
431 ldgrprodtn[ip] = ldergraph;
432 ldgrtermn[rhs0] = ip;
433 } else if (lhs > memprodtn[ldergraph].lhs) {
434 ldgrprodtn[ip] = ldergraph;
435 ldgrtermn[rhs0] = ip;
436 } else {
437 prevldergraph = ldergraph;
438 addedldergraph = 0;
439 ldergraph = ldgrprodtn[ldergraph];
440 while (!addedldergraph && ldergraph) {
441 if (lhs == memprodtn[ldergraph].lhs) {
442 ldgrprodtn[ip] = ldergraph;
443 ldgrprodtn[prevldergraph] = ip;
444 addedldergraph = 1;
445 } else if (lhs > memprodtn[ldergraph].lhs) {
446 ldgrprodtn[ip] = ldergraph;
447 ldgrprodtn[prevldergraph] = ip;
448 addedldergraph = 1;
449 } else {
450 prevldergraph = ldergraph;
451 ldergraph = ldgrprodtn[ldergraph];
452 }
453 }
454 if (!addedldergraph)
455 ldgrprodtn[prevldergraph] = ip;
456 }
457 }
458 }
459 }
460 }
461 }
462
compileLDerTable()463 void ScpParser::compileLDerTable()
464 {
465 for (auxntm = 1,auxpbase = maxnontm; auxntm < maxnontm; auxntm++,auxpbase+=maxnontm)
466 insertLDerNT(auxntm);
467 }
468
insertLDerNT(int lder)469 void ScpParser::insertLDerNT(int lder)
470 {
471 int curnt = lder;
472 while (curnt) {
473 if (!ldernttb[auxpbase+curnt]) {
474 ldernttb[auxpbase+curnt] = ldernttb[auxpbase]+1;
475 ldernttb[auxpbase] = curnt;
476 ldernttb[auxntm]++;
477 int ldergraph = ldgrabslnt[curnt];
478 while (ldergraph) {
479 if (!ldernttb[auxpbase-memprodtn[ldergraph].lhs])
480 insertLDerNT(-memprodtn[ldergraph].lhs);
481 ldergraph = ldgrprodtn[ldergraph];
482 }
483 }
484 curnt = -memabslnt[curnt].nextNT;
485 }
486 }
487
compileRDerGraph()488 void ScpParser::compileRDerGraph()
489 {
490 register int ip;
491 register int rhsN;
492 register int lhs;
493 register int rdergraph;
494 register int prevrdergraph;
495 register int addedrdergraph;
496 ScpProdtn* prodtn;
497
498 for (ip = 1; ip <= curprodtn; ip++) {
499 prodtn = &memprodtn[ip];
500 if (!prodtn->bubble) {
501 rhsN = memrhs[prodtn->rhs+prodtn->lrhs-1];
502 if (rhsN < 0) {
503 // lhs = memrhs[prodtn->lhs];
504 lhs = prodtn->lhs;
505 rdergraph = rdgrabslnt[-rhsN];
506 if (!rdergraph)
507 rdgrabslnt[-rhsN] = ip;
508 else {
509 if (lhs == memprodtn[rdergraph].lhs)
510 ;
511 else if (lhs > memprodtn[rdergraph].lhs) {
512 rdgrprodtn[ip] = rdergraph;
513 rdgrabslnt[-rhsN] = ip;
514 } else {
515 prevrdergraph = rdergraph;
516 addedrdergraph = 0;
517 rdergraph = rdgrprodtn[rdergraph];
518 while (!addedrdergraph && rdergraph) {
519 if (lhs == memprodtn[rdergraph].lhs)
520 addedrdergraph = 1;
521 else if (lhs > memprodtn[rdergraph].lhs) {
522 rdgrprodtn[ip] = rdergraph;
523 rdgrprodtn[prevrdergraph] = ip;
524 addedrdergraph = 1;
525 } else {
526 prevrdergraph = rdergraph;
527 rdergraph = rdgrprodtn[rdergraph];
528 }
529 }
530 if (!addedrdergraph)
531 rdgrprodtn[prevrdergraph] = ip;
532 }
533 }
534 } else {
535 // lhs = memrhs[prodtn->lhs];
536 lhs = prodtn->lhs;
537 rdergraph = rdgrtermn[rhsN];
538 if (!rdergraph)
539 rdgrtermn[rhsN] = ip;
540 else {
541 if (lhs == memprodtn[rdergraph].lhs)
542 ;
543 else if (lhs > memprodtn[rdergraph].lhs) {
544 rdgrprodtn[ip] = rdergraph;
545 rdgrtermn[rhsN] = ip;
546 } else {
547 prevrdergraph = rdergraph;
548 addedrdergraph = 0;
549 rdergraph = rdgrprodtn[rdergraph];
550 while (!addedrdergraph && rdergraph) {
551 if (lhs == memprodtn[rdergraph].lhs)
552 addedrdergraph = 1;
553 else if (lhs > memprodtn[rdergraph].lhs) {
554 rdgrprodtn[ip] = rdergraph;
555 rdgrprodtn[prevrdergraph] = ip;
556 addedrdergraph = 1;
557 } else {
558 prevrdergraph = rdergraph;
559 rdergraph = rdgrprodtn[rdergraph];
560 }
561 }
562 if (!addedrdergraph)
563 rdgrprodtn[prevrdergraph] = ip;
564 }
565 }
566 }
567 }
568 }
569 }
570
compileRDerTable()571 void ScpParser::compileRDerTable()
572 {
573 for (auxntm = 1,auxpbase = maxnontm; auxntm < maxnontm; auxntm++,auxpbase+=maxnontm)
574 insertRDerNT(auxntm);
575 }
576
insertRDerNT(int rder)577 void ScpParser::insertRDerNT(int rder)
578 {
579 int curnt = rder;
580 while (curnt) {
581 if (!rdernttb[auxpbase+curnt]) {
582 rdernttb[auxpbase+curnt] = rdernttb[curnt]+1;
583 rdernttb[curnt] = auxntm;
584 int rdergraph = rdgrabslnt[curnt];
585 while (rdergraph) {
586 if (!rdernttb[auxpbase-memprodtn[rdergraph].lhs])
587 insertRDerNT(-memprodtn[rdergraph].lhs);
588 rdergraph = rdgrprodtn[rdergraph];
589 }
590 }
591 curnt = -memabslnt[curnt].nextNT;
592 }
593 }
594
compileCoverageTables()595 void ScpParser::compileCoverageTables()
596 {
597 register int ltcov = 1;
598 register int ntm;
599 register int addrbase = 0;
600
601 for (ntm = 1; ntm < maxnontm; ntm++)
602 ltcov += memabslnt[ntm].lhsdefs * ldernttb[ntm];
603
604 register int bub;
605 for (bub = 1; bub <= curbubble; bub++)
606 ltcov += ldernttb[-membubble[bub].abslnt];
607
608 memcov = new ScpCov[ltcov];
609
610 register int last;
611 ltcov = 0;
612
613 register int xldgr;
614 register int addrbaset;
615 register int lhs;
616
617 for (ntm = 1; ntm < maxnontm; ntm++) {
618 if (ldgrabslnt[ntm]) {
619 xldgr = ldgrabslnt[ntm];
620 addrbaset = addrnontm[ntm];
621 while (xldgr) {
622 lhs = -memprodtn[xldgr].lhs;
623 addrbase = addrnontm[lhs];
624 last = ldernttb[addrbase];
625 while (last) {
626 ltcov ++;
627 memcov[ltcov].prodtn = xldgr;
628 memcov[ltcov].next = covnttb[addrbaset+last];
629 covnttb[addrbaset+last] = ltcov;
630 last = ldernttb[addrbase+last]-1;
631 }
632 xldgr = ldgrprodtn[xldgr];
633 }
634 }
635 }
636
637 register int tm;
638 for (tm = 0; tm < maxtermn; tm++) {
639 if (ldgrtermn[tm]) {
640 xldgr = ldgrtermn[tm];
641 addrbaset = addrtermn[tm];
642 while (xldgr) {
643 lhs = -memprodtn[xldgr].lhs;
644 addrbase = addrnontm[lhs];
645 last = ldernttb[addrbase];
646 while (last) {
647 ltcov ++;
648 memcov[ltcov].prodtn = xldgr;
649 if (covtmtb[addrbaset+last]) {
650 memcov[ltcov].ldernext = memcov[covtmtb[addrbaset+last]].ldernext;
651 memcov[ltcov].next = covtmtb[addrbaset+last];
652 } else {
653 memcov[ltcov].ldernext = invrdernttb[last];
654 memcov[ltcov].next = 0;
655 }
656 invrdernttb[last] = tm + 1;
657 covtmtb[addrbaset+last] = ltcov;
658 last = ldernttb[addrbase+last]-1;
659 }
660 xldgr = ldgrprodtn[xldgr];
661 }
662 }
663 }
664
665 if (!curbubble)
666 return;
667
668 int xbubexcept = 0;
669 for (bub = 1; bub <= curbubble; bub++) {
670 int abslnt = -membubble[bub].abslnt;
671 addrbase = addrnontm[abslnt];
672 last = ldernttb[addrbase];
673 while (last) {
674 ltcov ++;
675 memcov[ltcov].prodtn = membubble[bub].prodtn;
676 memcov[ltcov].next = memabslnt[last].bubblecov;
677 memabslnt[last].bubblecov = ltcov;
678 last = ldernttb[addrbase+last]-1;
679 }
680 membubble[bub].addrbubexcept = xbubexcept;
681 int lexcept = membubble[bub].lexcept;
682 int except = membubble[bub].except;
683 for (int ex=0; ex < lexcept; ex++)
684 bubexcept[xbubexcept+memexcept[except+ex]] = (char)1;
685 xbubexcept += maxtermn;
686
687 abslnt = -memabslnt[abslnt].nextNT;
688 while (abslnt) {
689 memabslnt[abslnt].bubbletermn = 1;
690 abslnt = -memabslnt[abslnt].nextNT;
691 }
692 }
693
694 int lenbubcov = MEMBUBCOV;
695 bubcov = new ScpCov[lenbubcov];
696 int curbubcov = 0;
697
698 register int pro;
699 for (pro = 1; pro <= curprodtn; pro++) {
700 if (!memprodtn[pro].bubble &&
701 ((ntm = memrhs[memprodtn[pro].rhs]) < 0) &&
702 (memabslnt[-ntm].bubblecov)) {
703 ntm = -ntm;
704 if (ldgrabslnt[ntm]) {
705 int bcov = memabslnt[ntm].bubblecov;
706 while (bcov) {
707 xldgr = ldgrabslnt[ntm];
708 addrbaset = addrnontm[ntm];
709 while (xldgr) {
710 lhs = -memprodtn[xldgr].lhs;
711 addrbase = addrnontm[lhs];
712 last = ldernttb[addrbase];
713 while (last) {
714 curbubcov++;
715 if (curbubcov >= lenbubcov) {
716 ScpCov* xbubcov = new ScpCov[lenbubcov+ADDBUBCOV];
717 memcpy(xbubcov,bubcov,lenbubcov*sizeof(ScpCov));
718 lenbubcov += ADDBUBCOV;
719 delete [] bubcov;
720 bubcov = xbubcov;
721 }
722 int found = 0;
723 int blastcov = memabslnt[last].bubbleev;
724 while (!found && blastcov) {
725 if (bubcov[blastcov].prodtn == pro)
726 found = 1;
727 else
728 blastcov = bubcov[blastcov].next;
729 }
730 if (!found) {
731 bubcov[curbubcov].prodtn = pro;
732 bubcov[curbubcov].next = memabslnt[last].bubbleev;
733 memabslnt[last].bubbleev = curbubcov;
734 }
735 last = ldernttb[addrbase+last]-1;
736 }
737 xldgr = ldgrprodtn[xldgr];
738 }
739 bcov = memcov[bcov].next;
740 }
741 }
742 }
743 }
744 }
745
compileAdjacencyTables()746 void ScpParser::compileAdjacencyTables()
747 {
748 register int ip;
749 register int rhs;
750 ScpProdtn* prodtn;
751 register int rhsN0;
752 register int rhsN1;
753 register int addrbase;
754 int *rhsN;
755
756 for (ip = 1; ip <= curprodtn; ip++) {
757 prodtn = &memprodtn[ip];
758 if (!prodtn->bubble && (prodtn->lrhs > 1)) {
759 rhsN = &memrhs[prodtn->rhs];
760 for (rhs = 1; rhs < prodtn->lrhs; rhs++) {
761 if (*rhsN < 0) {
762 rhsN0 = -(*rhsN);
763 rhsN1 = *(rhsN+1);
764 if (rhsN1 >= 0) {
765 addrbase = addrtermn[rhsN1];
766 if (!adjtb[addrbase+rhsN0]) {
767 // adjtb[addrbase+rhsN0] = 1;
768 insertAdjTM(addrbase,rhsN0);
769 }
770 } else {
771 if (memabslnt[-rhsN1].bubblecov) {
772 int xnext = -membasent[-memabslnt[rhsN0].baseNT].firstAbs;
773 while (xnext != rhsN0) {
774 memabslnt[xnext].adjbubble = 1;
775 xnext = -memabslnt[xnext].nextNT;
776 }
777 memabslnt[rhsN0].adjbubble = 1;
778 }
779 insertAdjNT(-rhsN1,rhsN0);
780 }
781 }
782 rhsN++;
783 }
784 }
785 }
786 }
787
insertAdjTM(int pbase,int adj)788 void ScpParser::insertAdjTM(int pbase,int adj)
789 {
790 int last = rdernttb[adj];
791 while (last) {
792 adjtb[pbase+last] = 1;
793 last = rdernttb[addrnontm[last]+adj]-1;
794 }
795 }
796
insertAdjNT(int base,int adj)797 void ScpParser::insertAdjNT(int base,int adj)
798 {
799 int last = invrdernttb[base];
800 while (last) {
801 if (!adjtb[addrtermn[last-1]+adj])
802 insertAdjTM(addrtermn[last-1],adj);
803 last = memcov[ldertmtb[addrtermn[last-1]+base]].ldernext;
804 }
805 }
806
printGrammar()807 void ScpParser::printGrammar()
808 {
809 cout << "============================" << endl;
810 cout << "Grammar" << endl;
811 cout << "============================" << endl;
812 cout << " Number of productions ..........: " << curprodtn << endl;
813 cout << " Number of bubbles ..............: " << curbubble << endl;
814 cout << " Max/Number base-nonterminal ....: " << maxbasent << endl;
815 cout << " Max/Number absl-nonterminal ....: " << maxabslnt << endl;
816 cout << " Max terminal ...................: " << maxtermn-1 << endl;
817 cout << " Number of terminals ............: " << maxtermn << endl;
818 cout << " curprodtn ...: " << curprodtn << endl;
819 cout << " lenprodtn ...: " << lenprodtn << endl;
820 cout << " currhs ......: " << currhs << endl;
821 cout << " lenrhs ......: " << lenrhs << endl;
822 cout << " curbubble ...: " << curbubble << endl;
823 cout << " lenbubble ...: " << lenbubble << endl;
824 cout << " curexcept ...: " << curexcept << endl;
825 cout << " lenexcept ...: " << lenexcept << endl;
826
827 cout << endl;
828 cout << "============================" << endl;
829 cout << "Base/Absl Translation Model" << endl;
830 cout << "============================" << endl;
831 for (int basent = -1; basent >= maxbasent; basent--) {
832 cout << " BaseNT: " << basent << endl;
833 cout << " (smP:" << membasent[-basent].smallestPrec << "," <<
834 "lgP:" << membasent[-basent].largestPrec << "," <<
835 "ftA:" << membasent[-basent].firstAbs << "," <<
836 "ltA:" << membasent[-basent].lastAbs << ")" << endl;
837 int cA = membasent[-basent].firstAbs;
838 while (cA) {
839 cout << " AbslNT: " << cA << " [" <<
840 "baseNT:" << memabslnt[-cA].baseNT << "," <<
841 "precNT:" << memabslnt[-cA].precNT << "," <<
842 "nextNT:" << memabslnt[-cA].nextNT << "]" <<
843 endl;
844 cA = memabslnt[-cA].nextNT;
845 }
846 cout << endl;
847 }
848
849 cout << endl;
850 cout << "============================" << endl;
851 cout << "Productions" << endl;
852 cout << "============================" << endl;
853 for (int ip = 1; ip <= curprodtn; ip++) {
854 if (!memprodtn[ip].bubble) {
855 cout << "(" << ip-1 << ") production: " << memprodtn[ip].lhs ;
856 cout << "<" << getBaseNT(memprodtn[ip].lhs) << "/";
857 cout << getPrecNT(memprodtn[ip].lhs) << ">";
858 cout << " ::= " ;
859 for (int rh = 0; rh < memprodtn[ip].lrhs; rh ++) {
860 cout << memrhs[memprodtn[ip].rhs+rh];
861 if (memrhs[memprodtn[ip].rhs+rh] < 0) {
862 cout << "<" <<
863 getBaseNT(memrhs[memprodtn[ip].rhs+rh]) << "/" <<
864 getPrecNT(memrhs[memprodtn[ip].rhs+rh]) << ">";
865 }
866 cout << " ";
867 }
868 cout << endl;
869 } else {
870 cout << "(" << ip-1 << ") production: " ;
871 ScpBubble* bubble = &membubble[memprodtn[ip].bubble];
872 cout << bubble->abslnt;
873 cout << "<" << getBaseNT(bubble->abslnt) << "/";
874 cout << getPrecNT(bubble->abslnt) << ">";
875 cout << ", ";
876 cout << bubble->lbound << ", " ;
877 cout << bubble->ubound << ", " ;
878 cout << bubble->lparen << ", " ;
879 cout << bubble->rparen << ", " ;
880 for (int ex = 0; ex < bubble->lexcept; ex ++)
881 cout << memexcept[bubble->except+ex] << " ";
882 cout << " || ";
883 for (int tm = 0; tm < maxtermn; tm++)
884 if (bubexcept[bubble->addrbubexcept + tm])
885 cout << tm << " ";
886 cout << endl;
887 }
888 }
889
890 cout << endl;
891 cout << "============================" << endl;
892 cout << "Non-Terminals " << endl;
893 cout << "============================" << endl;
894 for (int nt=1; nt <= -maxabslnt ; nt ++) {
895 printf(" Non-Terminal: [%4d]\n",-nt);
896
897 if (ldgrabslnt[nt]) {
898 int linderg;
899 cout << " LDerGraph: " ;
900 int lderg = ldgrabslnt[nt];
901 linderg = 0;
902 while (lderg) {
903 if (linderg > 10) {
904 cout << endl << " " ;
905 linderg = 0;
906 }
907 printf("(%4d) ",lderg);
908 lderg = ldgrprodtn[lderg];
909 linderg ++ ;
910 }
911 cout << endl;
912 }
913
914 cout << " LDerTable: " ;
915 int linderg = 0;
916 for (int lder = 1; lder <= -maxabslnt; lder++) {
917 if (ldernttb[addrnontm[nt]+lder]) {
918 if (linderg > 7) {
919 cout << endl << " " ;
920 linderg = 0;
921 }
922 printf("[%4d] ",-lder);
923 linderg ++;
924 }
925 }
926 cout << endl;
927
928 if (rdgrabslnt[nt]) {
929 int linderg;
930 cout << " RDerGraph: " ;
931 int rderg = rdgrabslnt[nt];
932 linderg = 0;
933 while (rderg) {
934 if (linderg > 10) {
935 cout << endl << " " ;
936 linderg = 0;
937 }
938 printf("(%4d) ",rderg);
939 rderg = rdgrprodtn[rderg];
940 linderg ++ ;
941 }
942 cout << endl;
943 }
944
945 cout << " RDerTable: " ;
946 linderg = 0;
947 for (int rder = 1; rder < maxnontm; rder++) {
948 if (rdernttb[addrnontm[nt]+rder]) {
949 if (linderg > 7) {
950 cout << endl << " " ;
951 linderg = 0;
952 }
953 printf("[%4d] ",-rder);
954 linderg ++;
955 }
956 }
957 cout << endl;
958
959 cout << " TMCovTable: " << endl;
960 for (int tm = 0; tm < maxtermn; tm++) {
961 int tmaddrbase = addrtermn[tm];
962 if (covtmtb[tmaddrbase+nt]) {
963 printf(" [%4d]: ",tm);
964 int lincov = 0;
965 int cov = covtmtb[tmaddrbase+nt];
966 while (cov) {
967 if (lincov > 8) {
968 cout << endl << " " ;
969 lincov = 0;
970 }
971 lincov++;
972 printf("(%4d) ",memcov[cov].prodtn-1);
973 cov = memcov[cov].next;
974 }
975 cout << endl;
976 }
977 }
978
979 cout << " NTCovTable: " << endl;
980 for (int ntm = 1; ntm <= -maxabslnt; ntm++) {
981 int ntaddrbase = addrnontm[ntm];
982 if (covnttb[ntaddrbase+nt]) {
983 printf(" [%4d]: ",-ntm);
984 int lincov = 0;
985 int cov = covnttb[ntaddrbase+nt];
986 while (cov) {
987 if (lincov > 8) {
988 cout << endl << " " ;
989 lincov = 0;
990 }
991 lincov++;
992 printf("(%4d) ",memcov[cov].prodtn-1);
993 cov = memcov[cov].next;
994 }
995 cout << endl;
996 }
997 }
998
999 if (memabslnt[nt].bubblecov) {
1000 cout << " BubbleCov: " ;
1001 int bcov = memabslnt[nt].bubblecov;
1002 int lincov = 0;
1003 while (bcov) {
1004 if (lincov > 8) {
1005 cout << endl << " " ;
1006 lincov = 0;
1007 }
1008 lincov++;
1009 printf("(%4d) ",memcov[bcov].prodtn-1);
1010 bcov = memcov[bcov].next;
1011 }
1012 cout << endl;
1013 }
1014
1015 if (memabslnt[nt].bubbletermn)
1016 cout << " BubbleTermn: 1" << endl;
1017
1018 if (memabslnt[nt].bubbleev) {
1019 cout << " BubbleEv: ";
1020 int bcov = memabslnt[nt].bubbleev;
1021 int lincov = 0;
1022 while (bcov) {
1023 if (lincov > 8) {
1024 cout << endl << " " ;
1025 lincov = 0;
1026 }
1027 lincov++;
1028 printf("(%4d) ",bubcov[bcov].prodtn-1);
1029 bcov = bubcov[bcov].next;
1030 }
1031 cout << endl;
1032 }
1033
1034 cout << " AdjTable: ";
1035 int linadj = 0;
1036 for (int tm = 0; tm < maxtermn; tm++) {
1037 if (adjtb[addrtermn[tm]+nt]) {
1038 if (linadj > 8) {
1039 cout << endl << " " ;
1040 linadj = 0;
1041 }
1042 printf("[%4d] ",tm);
1043 linadj++;
1044 }
1045 }
1046 cout << endl;
1047
1048 if (memabslnt[nt].adjbubble)
1049 cout << " AdjBubble: 1 " << endl;
1050
1051 cout << " ----------------------------" << endl;
1052 }
1053
1054 cout << endl;
1055 cout << "============================" << endl;
1056 cout << "Terminals" << endl;
1057 cout << "============================" << endl;
1058 for (int term = 0; term < maxtermn; term ++) {
1059 printf(" Terminal: [%4d]\n",term);
1060
1061 cout << " LDerTable: " ;
1062 int linderg = 0;
1063 for (int lder = 1; lder <= -maxabslnt; lder++) {
1064 if (ldertmtb[addrtermn[term]+lder]) {
1065 if (linderg > 7) {
1066 cout << endl << " " ;
1067 linderg = 0;
1068 }
1069 printf("[%4d] ",-lder);
1070 linderg ++;
1071 }
1072 }
1073 cout << endl;
1074 }
1075 }
1076
1077