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_parser.cc
32 *******/
33
34 #include "scp_parser.hh"
35
36
parseSentence(Vector<int> & term,int root,int errorRecover)37 int ScpParser::parseSentence(Vector<int>& term,int root,int errorRecover)
38 {
39 // Control: compile grammar
40 if (!compiled)
41 compileParser();
42
43 // Init EventTerm
44 lengthterm = term.length()+1;
45 if (lengthterm > maxlenterm) {
46 maxlenterm = lengthterm + ADDLENTERM;
47 delete [] nodeterm;
48 nodeterm = new int[maxlenterm*5];
49 eventterm = nodeterm+maxlenterm;
50 inputterm = eventterm+maxlenterm;
51 errorlist = inputterm+maxlenterm;
52 errorlevel = errorlist+maxlenterm;
53 }
54 memset(eventterm,0,(lengthterm+1)*sizeof(int));
55 memset(nodeterm,0,(lengthterm+1)*sizeof(int));
56
57 // ErrorRecover
58 parseErrorRecover = errorRecover;
59 if (errorRecover) {
60 curdetect = 0;
61 lasttokendetect = 0;
62 prevlasttokendetect = -1;
63 }
64
65 // Init Counters and Flags
66 rootterm = membasent[-root].lastAbs;
67
68 register int tk;
69 // Copy term(Vector<int>) to inputterm(int*)
70 for (tk = 0; tk < lengthterm-1; tk++)
71 inputterm[tk] = term[tk];
72 // End Token
73 inputterm[tk] = maxtermn + 10;
74
75 // Prod 0
76 memprodtn[0].lhs = rootterm;
77 memrhs[memprodtn[0].rhs] = rootterm;
78
79 // Initial Flags
80 curevent = 0; /* event 0 is not used */
81 curnode = 0; /* node 0 is not used */
82 curanal = 0; /* anal 0 is not used */
83 rootnode = 0;
84 ambnodes = 0;
85 prevnextanal = 0;
86
87 #ifdef SCPTRACE
88 cout << "==============================================" << endl;
89 cout << "parse: ";
90 for (tk = 0; tk < lengthterm-1; tk++)
91 cout << inputterm[tk] << " " ;
92 cout << endl;
93 #endif
94
95
96 tryEvent(0,0,0,0,0,0);
97
98 if (curbubble) {
99 for (tk = 0; tk < lengthterm; tk++)
100 if (eventterm[tk])
101 runTokenBubble(tk);
102 } else {
103 for (tk = 0; tk < lengthterm-1; tk++)
104 if ((inputterm[tk] < maxtermn) &&
105 (eventterm[tk]))
106 runToken(tk);
107 }
108
109 #ifdef SCPTRACE
110 cout << "parse: ";
111 for (tk = 0; tk < lengthterm-1; tk++)
112 cout << inputterm[tk] << " " ;
113 cout << endl;
114
115 cout << "Length: " << lengthterm-1 << " RootNode: " << rootnode << endl;
116 cout << " Nodes: " << curnode << " Events: " << curevent
117 << " Anals: " << curanal << endl;
118 #endif
119
120 if (!errorRecover)
121 curerrorlist = 0;
122
123 if (!rootnode) {
124 if (errorRecover) {
125 errorRecovery();
126 } else {
127 memset(errorlist,0,(lengthterm+1)*sizeof(int));
128 memset(errorlevel,0,(lengthterm+1)*sizeof(int));
129 parseSentence(term,root,1);
130 }
131 return 0;
132 } else if (rootnode && !ambnodes)
133 return 1;
134 else {
135 if (prevambnode)
136 memset(memambnode,0,(curnode+1)*sizeof(int));
137 prevambnode = 1;
138 return setAmbNode(rootnode);
139 }
140 }
141
tryEvent(int prod,int idot,int fpos,int lpos,int prevnode=0,int prevevent=0)142 void ScpParser::tryEvent(int prod,int idot,int fpos,int lpos,
143 int prevnode = 0,int prevevent = 0)
144 {
145 #ifdef SCPTRACE
146 cout << "SCPtrace$$ tryEvent ("
147 << " prod:" << prod-1
148 << " symbol:" << printSymbol(memprodtn[prod].lhs)
149 << " idot:" << idot
150 << " fpos:" << fpos
151 << " lpos:" << lpos
152 << " )" << endl;
153 #endif
154 int pos = lpos;
155 int dot = idot;
156 int rhs = memprodtn[prod].rhs+dot;
157 while ((dot < memprodtn[prod].lrhs) &&
158 (memrhs[rhs] >= 0) &&
159 (pos < lengthterm)) {
160 if (memrhs[rhs] == inputterm[pos]) {
161 #ifdef SCPTRACE
162 cout << "SCPtrace$$ tryEvent:skipTerm ("
163 << " pos:" << pos
164 << " token:" << inputterm[pos]
165 << " )" << endl;
166 #endif
167 rhs ++;
168 pos ++;
169 dot ++;
170 } else {
171 #ifdef SCPTRACE
172 cout << "SCPtrace$$ FAIL:tryEvent:skipTerm ("
173 << " pos:" << pos
174 << " inputToken:" << inputterm[pos]
175 << " neededToken:" << memrhs[rhs]
176 << " )" << endl;
177 #endif
178 if (parseErrorRecover) {
179 if (pos >= lasttokendetect) {
180 errorDetect(pos,memrhs[rhs]);
181
182 curevent ++;
183 if (curevent >= lenevent) {
184 ScpEvent* xmemevent = new ScpEvent[lenevent+ADDEVENT];
185 memcpy(xmemevent,memevent,lenevent*sizeof(ScpEvent));
186 lenevent += ADDEVENT;
187 delete [] memevent;
188 memevent = xmemevent;
189 }
190 ScpEvent* event = &memevent[curevent];
191 event->prodtn = prod;
192 event->dot = dot;
193 event->fpos = fpos;
194 event->nextsymbol = memrhs[rhs];
195 if (event->nextsymbol >= 0) {
196 if (event->nextsymbol < maxtermn)
197 event->addrnextsymbol = addrtermn[event->nextsymbol];
198 else
199 event->addrnextsymbol = 0;
200 }
201 else
202 event->addrnextsymbol = addrnontm[-event->nextsymbol];
203 event->subsumed = 1;
204 event->prevnode = prevnode;
205 event->prevevent = prevevent;
206 #ifdef SCPTRACE
207 cout << "SCPtrace$$ tryEvent:newEvent[" << curevent << "] ( "
208 << " prod:" << prod-1
209 << " symbol:" << printSymbol(memprodtn[prod].lhs)
210 << " dot:" << dot
211 << " nextsymbol: " << memrhs[rhs]
212 << " fpos:" << fpos
213 << " lpos:" << pos
214 << endl;
215 cout << "SCPtrace$$ tryEvent:addEvent[" << pos << "] ADD " << curevent << endl;
216 #endif
217 if (!eventterm[pos]) {
218 event->nextevent = 0;
219 eventterm[pos] = curevent;
220 } else {
221 if (curbubble && (lpos == fpos)) {
222 int xevents = eventterm[pos];
223 while (memevent[xevents].nextevent)
224 xevents = memevent[xevents].nextevent;
225 memevent[xevents].nextevent = curevent;
226 event->nextevent = 0;
227 } else {
228 event->nextevent = eventterm[pos];
229 eventterm[pos] = curevent;
230 }
231 }
232 }
233 }
234 return;
235 }
236 }
237
238 if (dot < memprodtn[prod].lrhs) {
239 if ((memabslnt[-memrhs[rhs]].bubblecov) ||
240 ((inputterm[pos] < maxtermn) &&
241 (ldertmtb[addrtermn[inputterm[pos]]-memrhs[rhs]]))) {
242 #ifdef SCPTRACE
243 cout << "SCPtrace$$ tryEvent:LDerControl ("
244 << " symbol:" << printSymbol(memrhs[rhs])
245 << " token:" << inputterm[pos]
246 << " ) => 1" << endl;
247 #endif
248 curevent ++;
249 if (curevent >= lenevent) {
250 ScpEvent* xmemevent = new ScpEvent[lenevent+ADDEVENT];
251 memcpy(xmemevent,memevent,lenevent*sizeof(ScpEvent));
252 lenevent += ADDEVENT;
253 delete [] memevent;
254 memevent = xmemevent;
255 }
256 ScpEvent* event = &memevent[curevent];
257 event->prodtn = prod;
258 event->dot = dot;
259 event->fpos = fpos;
260 event->nextsymbol = memrhs[rhs];
261 event->addrnextsymbol = addrnontm[-event->nextsymbol];
262 event->subsumed = 0;
263 event->prevnode = prevnode;
264 event->prevevent = prevevent;
265 #ifdef SCPTRACE
266 cout << "SCPtrace$$ tryEvent:newEvent[" << curevent << "] ( "
267 << " prod:" << prod-1
268 << " symbol:" << printSymbol(memprodtn[prod].lhs)
269 << " dot:" << dot
270 << " nextsymbol: " << printSymbol(memrhs[rhs])
271 << " fpos:" << fpos
272 << " lpos:" << pos
273 << endl;
274 // << "SCPtrace$$ "
275 // << " prevnode:" << prevnode
276 // << " prevevent:" << prevevent
277 // << " )" << endl;
278 cout << "SCPtrace$$ tryEvent:addEvent[" << pos << "] ADD " << curevent << endl;
279 #endif
280 if (!eventterm[pos]) {
281 event->nextevent = 0;
282 eventterm[pos] = curevent;
283 } else {
284 int xevents = eventterm[pos];
285 int sub = 0;
286 while (!sub && xevents) {
287 if (memevent[xevents].nextsymbol < 0) {
288 if (ldernttb[event->addrnextsymbol - memevent[xevents].nextsymbol]) {
289 #ifdef SCPTRACE
290 cout << "SCPtrace$$ tryEvent:subsume event " << xevents
291 << " to " << curevent << endl;
292 #endif
293 event->subsumed = 1;
294 sub = 1;
295 } else if (ldernttb[memevent[xevents].addrnextsymbol - event->nextsymbol]){
296 #ifdef SCPTRACE
297 cout << "SCPtrace$$ tryEvent:subsume event " << curevent
298 << " to " << xevents << endl;
299 #endif
300 memevent[xevents].subsumed = 1;
301 }
302 }
303 xevents = memevent[xevents].nextevent;
304 }
305 if (curbubble && (lpos == fpos)) {
306 xevents = eventterm[pos];
307 while (memevent[xevents].nextevent)
308 xevents = memevent[xevents].nextevent;
309 memevent[xevents].nextevent = curevent;
310 event->nextevent = 0;
311 } else {
312 event->nextevent = eventterm[pos];
313 eventterm[pos] = curevent;
314 }
315 }
316 } else {
317 #ifdef SCPTRACE
318 cout << "SCPtrace$$ FAIL:tryEvent:LDerControl ("
319 << " symbol:" << printSymbol(memrhs[rhs])
320 << " token:" << inputterm[pos]
321 << " ) => 0" << endl;
322 #endif
323 if (parseErrorRecover) {
324 if (pos >= lasttokendetect) {
325 errorDetect(pos,memrhs[rhs]);
326 if ((inputterm[pos] < maxtermn) &&
327 (!ldertmtb[addrtermn[inputterm[pos]]-memrhs[rhs]])) {
328 #ifdef SCPTRACE
329 cout << "SCPtrace$$ ErrorRecoveryPhase: cancelling FAIL" << endl;
330 #endif
331 curevent ++;
332 if (curevent >= lenevent) {
333 ScpEvent* xmemevent = new ScpEvent[lenevent+ADDEVENT];
334 memcpy(xmemevent,memevent,lenevent*sizeof(ScpEvent));
335 lenevent += ADDEVENT;
336 delete [] memevent;
337 memevent = xmemevent;
338 }
339 ScpEvent* event = &memevent[curevent];
340 event->prodtn = prod;
341 event->dot = dot;
342 event->fpos = fpos;
343 event->nextsymbol = memrhs[rhs];
344 event->addrnextsymbol = addrnontm[-event->nextsymbol];
345 event->subsumed = 1;
346 event->prevnode = prevnode;
347 event->prevevent = prevevent;
348 #ifdef SCPTRACE
349 cout << "SCPtrace$$ tryEvent:newEvent[" << curevent << "] ( "
350 << " prod:" << prod-1
351 << " symbol:" << printSymbol(memprodtn[prod].lhs)
352 << " dot:" << dot
353 << " nextsymbol: " << printSymbol(memrhs[rhs])
354 << " fpos:" << fpos
355 << " lpos:" << pos
356 << endl;
357 cout << "SCPtrace$$ tryEvent:addEvent[" << pos << "] ADD " << curevent << endl;
358 #endif
359 if (!eventterm[pos]) {
360 event->nextevent = 0;
361 eventterm[pos] = curevent;
362 } else {
363 int xevents = eventterm[pos];
364 int sub = 0;
365 while (!sub && xevents) {
366 if (memevent[xevents].nextsymbol < 0) {
367 if (ldernttb[event->addrnextsymbol - memevent[xevents].nextsymbol]) {
368 #ifdef SCPTRACE
369 cout << "SCPtrace$$ tryEvent:subsume event " << xevents
370 << " to " << curevent << endl;
371 #endif
372 event->subsumed = 1;
373 sub = 1;
374 } else if (ldernttb[memevent[xevents].addrnextsymbol - event->nextsymbol]){
375 #ifdef SCPTRACE
376 cout << "SCPtrace$$ tryEvent:subsume event " << curevent
377 << " to " << xevents << endl;
378 #endif
379 memevent[xevents].subsumed = 1;
380 }
381 }
382 xevents = memevent[xevents].nextevent;
383 }
384 if (curbubble && (lpos == fpos)) {
385 xevents = eventterm[pos];
386 while (memevent[xevents].nextevent)
387 xevents = memevent[xevents].nextevent;
388 memevent[xevents].nextevent = curevent;
389 event->nextevent = 0;
390 } else {
391 event->nextevent = eventterm[pos];
392 eventterm[pos] = curevent;
393 }
394 }
395 }
396 }
397 }
398 }
399 } else {
400 if (pos == lengthterm) {
401 #ifdef SCPTRACE
402 cout << "SCPtrace$$ AssigningRootNode: " << prevnode << endl;
403 #endif
404 rootnode = prevnode;
405 } else
406 tryNode(prod,fpos,pos,prevnode,prevevent);
407 }
408 }
409
runToken(int token)410 void ScpParser::runToken(int token)
411 {
412 #ifdef SCPTRACE
413 cout << "SCPtrace$$ runToken ("
414 << " token:" << inputterm[token]
415 << " post:" << token
416 << " )" << endl;
417 #endif
418 int prememprodruntoken;
419 int curmemprodruntoken = 0;
420 int event = eventterm[token];
421 int addrtoken = addrtermn[inputterm[token]];
422 while (event) {
423 if (!memevent[event].subsumed) {
424 int cov = covtmtb[addrtoken-memevent[event].nextsymbol];
425 prememprodruntoken = curmemprodruntoken-1;
426 while (cov) {
427 int pro = memcov[cov].prodtn;
428 int run = 0;
429 for (int rt = prememprodruntoken; (!run) && (rt >= 0); rt--)
430 if (memprodruntoken[rt] == pro)
431 run = 1;
432 if (run) {
433 #ifdef SCPTRACE
434 cout << "SCPtrace$$ runToken:triggerCoverage-Run:"
435 << memcov[cov].prodtn - 1
436 << " runToken ("
437 << " token:" << inputterm[token]
438 << " post:" << token
439 << " )" << endl;
440 #endif
441 } else {
442 #ifdef SCPTRACE
443 cout << "SCPtrace$$ runToken:triggerCoverage:" << memcov[cov].prodtn -1
444 << " runToken ("
445 << " token:" << inputterm[token]
446 << " post:" << token
447 << " )" << endl;
448 #endif
449 memprodruntoken[curmemprodruntoken++] = pro;
450 tryEvent(pro,0,token,token,0,0);
451 }
452 cov = memcov[cov].next;
453 }
454 }
455 event = memevent[event].nextevent;
456 }
457 }
458
459
runTokenBubble(int token)460 void ScpParser::runTokenBubble(int token)
461 {
462 #ifdef SCPTRACE
463 cout << "SCPtrace$$ runToken ("
464 << " token:" << inputterm[token]
465 << " post:" << token
466 << " )" << endl;
467 #endif
468 int prememprodruntoken;
469 int curmemprodruntoken = 0;
470 int event = eventterm[token];
471 int addrtoken;
472 if (inputterm[token] < maxtermn)
473 addrtoken = addrtermn[inputterm[token]];
474 int bcov;
475 int ecov;
476 while (event) {
477 if ((inputterm[token] < maxtermn) && (!memevent[event].subsumed)) {
478 int cov = covtmtb[addrtoken-memevent[event].nextsymbol];
479 prememprodruntoken = curmemprodruntoken-1;
480 while (cov) {
481 int pro = memcov[cov].prodtn;
482 int run = 0;
483 for (int rt = prememprodruntoken; (!run) && (rt >= 0); rt--)
484 if (memprodruntoken[rt] == pro)
485 run = 1;
486 if (run) {
487 #ifdef SCPTRACE
488 cout << "SCPtrace$$ runToken:triggerCoverage-Run:"
489 << memcov[cov].prodtn -1
490 << " runToken ("
491 << " token:" << inputterm[token]
492 << " post:" << token
493 << " )" << endl;
494 #endif
495 } else {
496 #ifdef SCPTRACE
497 cout << "SCPtrace$$ runToken:triggerCoverage:" << memcov[cov].prodtn -1
498 << " runToken ("
499 << " token:" << inputterm[token]
500 << " post:" << token
501 << " )" << endl;
502 #endif
503 memprodruntoken[curmemprodruntoken++] = pro;
504 tryEvent(pro,0,token,token,0,0);
505 }
506 cov = memcov[cov].next;
507 }
508 }
509 if (!memevent[event].subsumed) {
510 if (ecov = memabslnt[-memevent[event].nextsymbol].bubbleev) {
511 while (ecov) {
512 if (bcov = memabslnt[-memrhs[memprodtn[bubcov[ecov].prodtn].rhs]].bubblecov) {
513 while (bcov) {
514 runBubble(bubcov[ecov].prodtn,0,
515 token,memcov[bcov].prodtn,token,0);
516 bcov = memcov[bcov].next;
517 }
518 }
519 ecov = bubcov[ecov].next;
520 }
521 }
522 }
523
524 if (memevent[event].nextsymbol < 0) {
525 if (memabslnt[-memevent[event].nextsymbol].bubbletermn) {
526 if (bcov = memabslnt[-memevent[event].nextsymbol].bubblecov) {
527 while (bcov) {
528 runBubble(memevent[event].prodtn,memevent[event].dot,
529 memevent[event].fpos,memcov[bcov].prodtn,token,event);
530 bcov = memcov[bcov].next;
531 }
532 }
533 }
534 }
535 event = memevent[event].nextevent;
536 }
537 }
538
tryNode(int prod,int fpos,int lpos,int prevnode,int prevevent)539 void ScpParser::tryNode(int prod,int fpos,int lpos,int prevnode,int prevevent)
540 {
541 #ifdef SCPTRACE
542 cout << "SCPtrace$$ tryNode ("
543 << " prod:" << prod -1;
544 if (memprodtn[prod].bubble)
545 cout << " symbol:" << printSymbol(membubble[memprodtn[prod].bubble].abslnt);
546 else
547 cout << " symbol:" << printSymbol(memprodtn[prod].lhs);
548 cout << " fpos:" << fpos
549 << " lpos:" << lpos
550 << " )" << endl;
551 #endif
552 if (lpos >= lengthterm)
553 return;
554
555 // Adjacency Control
556 int nextterm = inputterm[lpos];
557 int lhs;
558 if (memprodtn[prod].bubble)
559 lhs = membubble[memprodtn[prod].bubble].abslnt;
560 else
561 lhs = memprodtn[prod].lhs;
562 if (lpos < (lengthterm-1)) {
563 if (nextterm >= maxtermn) {
564 ;
565 } else if (adjtb[addrtermn[nextterm]-lhs]) {
566 #ifdef SCPTRACE
567 cout << "SCPtrace$$ tryNode:AdjControl ("
568 << " symbol:" << printSymbol(lhs)
569 << " token:" << nextterm
570 << " ) => 1" << endl;
571 #endif
572 } else if (memabslnt[-lhs].adjbubble) {
573 #ifdef SCPTRACE
574 cout << "SCPtrace$$ tryNode:AdjControl ("
575 << " symbol:" << printSymbol(lhs)
576 << " ) => (adjBubble) 1" << endl;
577 #endif
578 } else {
579 #ifdef SCPTRACE
580 cout << "SCPtrace$$ FAIL:tryNode:AdjControl ("
581 << " symbol:" << printSymbol(lhs)
582 << " token:" << nextterm
583 << " ) => 0" << endl;
584 #endif
585 if (!parseErrorRecover)
586 return;
587 else {
588 #ifdef SCPTRACE
589 cout << "SCPtrace$$ ErrorRecoveryPhase: cancelling FAIL" << endl;
590 #endif
591 }
592 }
593 } else {
594 if (rdernttb[addrnontm[-lhs]-rootterm]) {
595 #ifdef SCPTRACE
596 cout << "SCPtrace$$ tryNode:AdjControl:RMS ("
597 << " symbol:" << printSymbol(lhs)
598 << " ) => 1" << endl;
599 #endif
600 } else if (memabslnt[-lhs].adjbubble) {
601 #ifdef SCPTRACE
602 cout << "SCPtrace$$ tryNode:AdjControl:RMS ("
603 << " symbol:" << printSymbol(lhs)
604 << " ) => (adjBubble) 1" << endl;
605 #endif
606 } else {
607 #ifdef SCPTRACE
608 cout << "SCPtrace$$ FAIL:tryNode:AdjControl:RMS ("
609 << " symbol:" << printSymbol(lhs)
610 << " ) => 0" << endl;
611 #endif
612 if (!parseErrorRecover)
613 return;
614 else {
615 #ifdef SCPTRACE
616 cout << "SCPtrace$$ ErrorRecoveryPhase: cancelling FAIL" << endl;
617 #endif
618 }
619 }
620 }
621
622 int symbol = lhs;
623
624 // Local Ambiguity control
625 int xnode = nodeterm[fpos];
626 while (xnode) {
627 if ((memnode[xnode].lpos == lpos) && (memnode[xnode].symbol == symbol)) {
628 if (memprodtn[prod].bubble || parseErrorRecover)
629 return;
630 curanal++;
631 if (curanal >= lenanal) {
632 ScpAnal* xmemanal = new ScpAnal[lenanal+ADDANAL];
633 memcpy(xmemanal,memanal,lenanal*sizeof(ScpAnal));
634 lenanal += ADDANAL;
635 delete [] memanal;
636 memanal = xmemanal;
637 }
638 ScpAnal* anal = &memanal[curanal];
639 anal->prodtn = prod;
640 anal->prevnode = prevnode;
641 anal->prevevent = prevevent;
642 anal->nextanal = memnode[xnode].initanal;
643 memnode[xnode].initanal = curanal;
644 ambnodes = 1;
645 #ifdef SCPTRACE
646 cout << "SCPtrace$$ tryNode:LocalAmbiguity with node " << xnode << endl;
647 cout << "SCPtrace$$ tryNode:newAnal[" << curanal << "] ("
648 << " prod:" << prod -1
649 << " prevnode:" << prevnode
650 << " prevevent:" << prevevent
651 << " nextanal:" << anal->nextanal
652 << ")" << endl;
653 #endif
654 return;
655 }
656 xnode = memnode[xnode].nextnode;
657 }
658
659 // Node Creation
660 curnode ++;
661 if (curnode >= lennode) {
662 ScpNode* xmemnode = new ScpNode[lennode+ADDNODE];
663 memcpy(xmemnode,memnode,lennode*sizeof(ScpNode));
664 int* xmemambnode = new int[lennode+ADDNODE];
665 lennode += ADDNODE;
666 delete [] memnode;
667 memnode = xmemnode;
668 delete [] memambnode;
669 memambnode = xmemambnode;
670 prevambnode = 1;
671 }
672 curanal++;
673 if (curanal >= lenanal) {
674 ScpAnal* xmemanal = new ScpAnal[lenanal+ADDANAL];
675 memcpy(xmemanal,memanal,lenanal*sizeof(ScpAnal));
676 lenanal += ADDANAL;
677 delete [] memanal;
678 memanal = xmemanal;
679 }
680 ScpNode* node = &memnode[curnode];
681 ScpAnal* anal = &memanal[curanal];
682 node->fpos = fpos;
683 node->lpos = lpos;
684 node->symbol = symbol;
685 node->nextnode = nodeterm[fpos];
686 nodeterm[fpos] = curnode;
687 node->initanal = curanal;
688 anal->prodtn = prod;
689 anal->prevnode = prevnode;
690 anal->prevevent = prevevent;
691 anal->nextanal = 0;
692
693 #ifdef SCPTRACE
694 cout << "SCPtrace$$ tryNode:newNode[" << curnode << "] ("
695 << " symbol:" << printSymbol(node->symbol)
696 << " fpos:" << fpos
697 << " lpos:" << lpos
698 << " initanal: " << curanal
699 << ")" << endl;
700 cout << "SCPtrace$$ tryNode:newAnal[" << curanal << "] ("
701 << " prod:" << prod-1
702 << " prevnode:" << prevnode
703 << " prevevent:" << prevevent
704 << " nextanal:" << 0
705 << ")" << endl;
706 #endif
707
708
709 // Run Node
710 int event;
711 int inode = curnode;
712 ScpEvent* pevent;
713 int prememprodrunnode;
714 int curmemprodrunnode = 0;
715 while (symbol) {
716 int addrlhs = addrnontm[-symbol];
717 event = eventterm[fpos];
718 while (event) {
719 if (!memevent[event].subsumed) {
720 int cov = covnttb[addrlhs-memevent[event].nextsymbol];
721 prememprodrunnode = curmemprodrunnode-1;
722 while (cov) {
723 int pro = memcov[cov].prodtn;
724 int run = 0;
725 for (int rt = prememprodrunnode; (!run) && (rt >= 0); rt--)
726 if (memprodrunnode[rt] == pro)
727 run = 1;
728 if (run) {
729 #ifdef SCPTRACE
730 cout << "SCPtrace$$ runNode:triggerCoverage-Run:" << memcov[cov].prodtn -1
731 << " runNode ("
732 << " node:" << inode
733 << " as symbol:" << printSymbol(symbol)
734 << " )" << endl;
735 #endif
736 } else {
737 #ifdef SCPTRACE
738 cout << "SCPtrace$$ runNode:triggerCoverage:" << memcov[cov].prodtn -1
739 << " runNode ("
740 << " node:" << inode
741 << " as symbol:" << printSymbol(symbol)
742 << " )" << endl;
743 #endif
744 tryEvent(memcov[cov].prodtn,1,fpos,lpos,inode);
745 memprodrunnode[curmemprodrunnode++] = pro;
746 }
747 cov = memcov[cov].next;
748 }
749 }
750 event = memevent[event].nextevent;
751 }
752 event = eventterm[fpos];
753 while (event) {
754 pevent = &memevent[event];
755 if (pevent->nextsymbol == symbol) {
756 #ifdef SCPTRACE
757 cout << "SCPtrace$$ runNode:linkEvent:" << event
758 << " runNode ("
759 << " node:" << inode
760 << " as symbol:" << printSymbol(symbol)
761 << " )" << endl;
762 #endif
763 tryEvent(pevent->prodtn,pevent->dot+1,pevent->fpos,lpos,inode,event);
764 }
765 event = memevent[event].nextevent;
766 }
767 symbol = memabslnt[-symbol].nextNT;
768 }
769 }
770
runBubble(int evprod,int dot,int evfpos,int bprod,int fpos,int event)771 void ScpParser::runBubble(int evprod,int dot,int evfpos,
772 int bprod,int fpos,int event)
773 {
774 #ifdef SCPTRACE
775 cout << "SCPtrace$$ runBubble("
776 << " evprodtn:" << evprod-1
777 << " evdot:" << dot
778 << " evfpos:" << evfpos
779 << " bprod:" << bprod-1
780 << " lpos:" << fpos
781 << " event:" << event
782 << " )" << endl;
783 #endif
784
785 ScpBubble* bubble = &membubble[memprodtn[bprod].bubble];
786 int lpos = fpos;
787 int lbnd = bubble->lbound;
788 int ubnd = bubble->ubound;
789 int lpar = bubble->lparen;
790 int rpar = bubble->rparen;
791 int pars = 0;
792
793 // LBound Tokens
794 #ifdef SCPTRACE
795 cout << "SCPtrace$$ lbound:" << bubble->lbound << endl;
796 cout << "SCPtrace$$ ubound:" << bubble->ubound << endl;
797 cout << "SCPtrace$$ lparen:" << bubble->lparen << endl;
798 cout << "SCPtrace$$ rparen:" << bubble->rparen << endl;
799 #endif
800 while ((lbnd>0 || pars) && ubnd && (lpos < lengthterm-1)) {
801 #ifdef SCPTRACE
802 cout << "SCPtrace$$ skipLBound: " << inputterm[lpos] << endl;
803 #endif
804 if ((inputterm[lpos] < maxtermn) &&
805 (bubexcept[bubble->addrbubexcept + inputterm[lpos]])) {
806 #ifdef SCPTRACE
807 cout << "SCPtrace$$ exceptionError: " << inputterm[lpos] << endl;
808 #endif
809 if (parseErrorRecover && (lpos > lasttokendetect)) {
810 errorDetect(lpos,inputterm[lpos],EXCEPTION_ERROR,bubble->abslnt);
811 errorRecovery(1);
812 } else
813 return;
814 } else if (inputterm[lpos] == rpar) {
815 #ifdef SCPTRACE
816 cout << "SCPtrace$$ closeParenthesis: pars=" << pars-1 << endl;
817 #endif
818 if (pars <= 0) {
819 #ifdef SCPTRACE
820 cout << "SCPtrace$$ ERROR-No Open Parenthesis" << endl;
821 #endif
822 if (parseErrorRecover && (lpos > lasttokendetect)) {
823 errorDetect(lpos,inputterm[lpos],CLOSEPAR_ERROR,bubble->abslnt);
824 errorRecovery(1);
825 pars++;
826 } else
827 return; /* Error: over-closed parenthesis */
828 }
829 pars--;
830 } else if (inputterm[lpos] == lpar) {
831 pars++;
832 #ifdef SCPTRACE
833 cout << "SCPtrace$$ openParenthesis: pars=" << pars << endl;
834 #endif
835 }
836 lbnd --;
837 ubnd --;
838 lpos ++;
839 }
840
841 if (lbnd > 0)
842 return;
843
844 dot ++;
845 int lrhs = memprodtn[evprod].lrhs;
846 int rhs = memprodtn[evprod].rhs;
847 int bubbleend;
848 int bubbletermn;
849 int bubblenexttermn;
850 int bubblenexttermnlen;
851 int bubblenext;
852 if (dot < lrhs) {
853 bubbleend = 0;
854 if (memrhs[rhs+dot] >= 0) {
855 bubbletermn = 1;
856 bubblenexttermn = memrhs[rhs+dot];
857 bubblenexttermnlen = 1;
858 int xdot = dot + 1;
859 bubblenext = 0;
860 while (!bubblenext && (xdot < lrhs)) {
861 if (memrhs[rhs+xdot] < 0) {
862 bubblenext = memrhs[rhs+xdot];
863 } else {
864 xdot++;
865 bubblenexttermnlen ++;
866 }
867 }
868 if (!bubblenext) {
869 bubbleend = 1;
870 bubblenext = memprodtn[evprod].lhs;
871 }
872 } else {
873 bubbletermn = 0;
874 bubblenext = memrhs[memprodtn[evprod].rhs+dot];
875 }
876 } else {
877 bubbletermn = 0;
878 bubbleend = 1;
879 bubblenext = memprodtn[evprod].lhs;
880 }
881
882 #ifdef SCPTRACE
883 cout << "SCPtrace$$ bubbleend :" << bubbleend << endl;
884 cout << "SCPtrace$$ bubbletermn:" << bubbletermn << endl;
885 cout << "SCPtrace$$ bubblenext :" << printSymbol(bubblenext) << endl;
886 if (bubbletermn)
887 cout << "SCPtrace$$ bubblenextt:" << bubblenexttermn << endl;
888 #endif
889
890 int termerror;
891 int xlpos = lpos;
892 int poslpos;
893 if (!pars)
894 poslpos = lpos;
895 else
896 poslpos = 0;
897 int found = 0;
898 while (!found && (lpos <= lengthterm-1)) {
899 #ifdef SCPTRACE
900 cout << "SCPtrace$$ seekFirstCandidate: "
901 << " lpos=" << lpos
902 << " token=" << inputterm[lpos]
903 << endl;
904 #endif
905
906 xlpos = lpos;
907 termerror = 0;
908 if (bubbletermn && !pars) {
909 int xdot = dot;
910 int blen = 1;
911 for (blen = 1; !termerror && (blen <= bubblenexttermnlen); blen++) {
912 #ifdef SCPTRACE
913 cout << "SCPtrace$$ skipNextTerminal: "
914 << " xlpos=" << xlpos
915 << " xdot=" << xdot
916 << " rhs=" << memrhs[rhs+xdot]
917 << " token=" << inputterm[xlpos]
918 << endl;
919 #endif
920 if (xlpos > lengthterm -1)
921 termerror = 1;
922 else if (inputterm[xlpos] != memrhs[rhs+xdot])
923 termerror = 1;
924 else {
925 xlpos++;
926 xdot++;
927 }
928 }
929 if (blen < bubblenexttermnlen)
930 termerror = 1;
931 }
932
933 if (!pars && !termerror) {
934 if (xlpos <= lengthterm) {
935 if (!pars)
936 poslpos = xlpos;
937 if (xlpos == lengthterm) {
938 if (rdernttb[addrnontm[-bubble->abslnt]-rootterm])
939 found = 1;
940 } else if (xlpos == lengthterm-1) {
941 if (bubbleend)
942 found = 1;
943 else if (!bubbleend && memabslnt[-bubblenext].bubblecov)
944 found = 1;
945 } else if (inputterm[xlpos] >= maxtermn) {
946 if (bubbleend) {
947 if (memabslnt[-bubblenext].adjbubble)
948 found = 1;
949 else if (memabslnt[-bubble->abslnt].adjbubble)
950 found = 1;
951 } else {
952 if (memabslnt[-bubblenext].bubblecov)
953 found = 1;
954 }
955 } else if (bubbleend) {
956 if (adjtb[addrtermn[inputterm[xlpos]]-bubblenext])
957 found = 1;
958 else if (adjtb[addrtermn[inputterm[xlpos]]-bubble->abslnt])
959 found = 1;
960 /* Incorporated 2/13/99 to solve p13 problem */
961 else if (memabslnt[-bubblenext].bubblecov)
962 found = 1;
963 } else {
964 if (memabslnt[-bubblenext].bubblecov)
965 found = 1;
966 else if (covtmtb[addrtermn[inputterm[xlpos]]-bubblenext])
967 found = 1;
968 }
969 }
970 } else {
971 if (parseErrorRecover) {
972 if (!pars)
973 poslpos = xlpos;
974 }
975 }
976 if (!found && (ubnd == 0))
977 break;
978 else if (!found) {
979 if ((inputterm[lpos] < maxtermn) &&
980 (bubexcept[bubble->addrbubexcept + inputterm[lpos]])) {
981 #ifdef SCPTRACE
982 cout << "SCPtrace$$ exceptionError: " << inputterm[lpos] << endl;
983 #endif
984 if (parseErrorRecover && (lpos >= lasttokendetect)) {
985 #ifdef SCPTRACE
986 cout << "SCPtrace$$ ErrorRecoveryPhase: cancelling FAIL" << endl;
987 #endif
988 // errorDetect(lpos,inputterm[lpos],EXCEPTION_ERROR,bubble->abslnt);
989 break;
990 } else
991 return;
992 } else if (inputterm[lpos] == rpar) {
993 #ifdef SCPTRACE
994 cout << "SCPtrace$$ closeParenthesis: pars=" << pars-1 << endl;
995 #endif
996 if (pars <= 0) {
997 #ifdef SCPTRACE
998 cout << "SCPtrace$$ ERROR-No Open Parenthesis" << endl;
999 #endif
1000 if (parseErrorRecover && (lpos >= lasttokendetect)) {
1001 #ifdef SCPTRACE
1002 cout << "SCPtrace$$ ErrorRecoveryPhase: cancelling FAIL" << endl;
1003 #endif
1004 break;
1005 // errorDetect(lpos,inputterm[lpos],CLOSEPAR_ERROR,bubble->abslnt);
1006 } else
1007 return;
1008 }
1009 pars--;
1010 } else if (inputterm[lpos] == lpar) {
1011 pars++;
1012 #ifdef SCPTRACE
1013 cout << "SCPtrace$$ openParenthesis: pars=" << pars << endl;
1014 #endif
1015 }
1016 lpos++;
1017 ubnd--;
1018 }
1019 }
1020
1021 if (found)
1022 tryNode(bprod,fpos,lpos,0,0);
1023 else if (parseErrorRecover && poslpos && (poslpos >= lasttokendetect))
1024 tryNode(bprod,fpos,poslpos,0,0);
1025 }
1026
errorDetect(int pos,int symbol,int type,int bubbleabslnt)1027 void ScpParser::errorDetect(int pos,int symbol,int type,int bubbleabslnt)
1028 {
1029 if (pos > lasttokendetect) {
1030 if (!lendetect) {
1031 lendetect = MEMDETECT;
1032 memdetect = new int[lendetect];
1033 typedetect = new int[lendetect];
1034 }
1035 #ifdef SCPTRACE
1036 cout << "SCPtrace$$ ErrorDetect: "
1037 << " position: " << pos
1038 << " type: " << type
1039 << " #detect: " << 0
1040 << " symbolNeeded: " << symbol;
1041 if (type == EXCEPTION_ERROR)
1042 cout << " type: ExceptionError, bubble: " << bubbleabslnt;
1043 else if (type == CLOSEPAR_ERROR)
1044 cout << " type: CloseParenthesisError, bubble: " << bubbleabslnt;
1045 cout << endl;
1046 #endif
1047 if (type == STANDARD_ERROR)
1048 memdetect[0] = symbol;
1049 else
1050 memdetect[0] = bubbleabslnt;
1051 typedetect[0] = type;
1052 curdetect = 1;
1053 lasttokendetect = pos;
1054 } else if (pos == lasttokendetect) {
1055 if (curdetect >= lendetect) {
1056 int* xmemdetect = new int[lendetect+ADDDETECT];
1057 memcpy(xmemdetect,memdetect,lendetect*sizeof(int));
1058 int* xtypedetect = new int[lendetect+ADDDETECT];
1059 memcpy(xtypedetect,typedetect,lendetect*sizeof(int));
1060 lendetect += ADDDETECT;
1061 delete [] memdetect;
1062 memdetect = xmemdetect;
1063 delete [] typedetect;
1064 typedetect = xtypedetect;
1065 }
1066 #ifdef SCPTRACE
1067 cout << "SCPtrace$$ ErrorDetect: "
1068 << " position: " << pos
1069 << " type: " << type
1070 << " #detect: " << curdetect
1071 << " symbolNeeded: " << symbol;
1072 if (type == EXCEPTION_ERROR)
1073 cout << " type: ExceptionError";
1074 else if (type == CLOSEPAR_ERROR)
1075 cout << " type: CloseParenthesisError";
1076 cout << endl;
1077 #endif
1078 if (type == STANDARD_ERROR)
1079 memdetect[curdetect] = symbol;
1080 else
1081 memdetect[curdetect] = bubbleabslnt;
1082 typedetect[curdetect] = type;
1083 curdetect ++;
1084 }
1085 }
1086
errorRecovery(int bubblerecovery)1087 void ScpParser::errorRecovery(int bubblerecovery)
1088 {
1089 int erlevel;
1090
1091 if (lasttokendetect > prevlasttokendetect) {
1092 prevlasttokendetect = lasttokendetect;
1093
1094 curerrorlist++;
1095
1096 if (curerrorlist > lenalter) {
1097 char* xmemalter = new char[(maxtermn+(maxnontm*2))*(lenalter+ADDALTER)];
1098 memcpy(xmemalter,memalter,(maxtermn+(maxnontm*2))*lenalter*sizeof(char));
1099 lenalter += ADDALTER;
1100 delete [] memalter;
1101 memalter = xmemalter;
1102 }
1103
1104 int lasttokenerror = lasttokendetect;
1105 int addralter = (curerrorlist-1)*(maxtermn+(maxnontm*2));
1106 memset(memalter+addralter,0,maxtermn+(maxnontm*2));
1107
1108 errorlist[curerrorlist] = lasttokenerror+1;
1109 errorlevel[curerrorlist] = 1;
1110 erlevel = 2;
1111
1112 for (int i=0; i<curdetect; i++) {
1113 if (typedetect[i] == STANDARD_ERROR) {
1114 if (memdetect[i] >= 0) {
1115 if (memdetect[i] < maxtermn)
1116 memalter[addralter+memdetect[i]] = 1;
1117 } else {
1118 for (int tm = 0; tm < maxtermn; tm++)
1119 if (covtmtb[addrtermn[tm]-memdetect[i]])
1120 memalter[addralter+tm] = 1;
1121 }
1122 } else if (typedetect[i] == EXCEPTION_ERROR)
1123 memalter[addralter+maxtermn-memdetect[i]] = 1;
1124 else if (typedetect[i] == CLOSEPAR_ERROR)
1125 memalter[addralter+maxtermn+maxnontm-memdetect[i]] = 1;;
1126 }
1127 } else {
1128 errorlevel[curerrorlist] = errorlevel[curerrorlist]+1;
1129 erlevel = errorlevel[curerrorlist];
1130 }
1131
1132 if (erlevel > MAXERRORLEVEL)
1133 return;
1134
1135 if (bubblerecovery)
1136 return;
1137
1138 #ifdef SCPTRACE
1139 cout << "SCPtrace$$ ErroRecoveryStrategy" << endl;
1140 #endif
1141
1142 int success = 0;
1143
1144 // InputSkip Strategy
1145 #ifdef SCPTRACE
1146 cout << "SCPtrace$$ InputSkipStrategy" << endl;
1147 #endif
1148
1149 int lasttokenerror = lasttokendetect;
1150 int event = eventterm[lasttokenerror];
1151 while (event) {
1152 #ifdef SCPTRACE
1153 cout << "SCPtrace$$ InputSkipEvent: " << event
1154 << " nextsymbol: " << memevent[event].nextsymbol
1155 << endl;
1156 #endif
1157 int foundskip = 0;
1158 int pos = lasttokenerror;
1159 int nextsymbol = memevent[event].nextsymbol;
1160 if (nextsymbol >= 0) {
1161 int xerlevel = 0;
1162 while (!foundskip && (xerlevel++ <= erlevel) && (pos < lengthterm-1)) {
1163 if (inputterm[pos] == nextsymbol)
1164 foundskip = 1;
1165 else
1166 pos ++;
1167 }
1168 } else {
1169 int xerlevel = 1;
1170 while (!foundskip && (pos < lengthterm-1)) {
1171 if ((inputterm[pos] < maxtermn) && (ldertmtb[addrtermn[inputterm[pos]]-nextsymbol]))
1172 foundskip = 1;
1173 else
1174 pos ++;
1175 }
1176 }
1177 if (foundskip) {
1178 success = 1;
1179 tryEvent(memevent[event].prodtn,memevent[event].dot,
1180 memevent[event].fpos,pos,
1181 memevent[event].prevnode,memevent[event].prevevent);
1182 }
1183 event = memevent[event].nextevent;
1184 }
1185
1186
1187 // RuleSkip Strategy
1188 #ifdef SCPTRACE
1189 cout << "SCPtrace$$ RuleSkipStrategy" << endl;
1190 #endif
1191
1192 event = eventterm[lasttokenerror];
1193 while (event) {
1194 #ifdef SCPTRACE
1195 cout << "SCPtrace$$ RuleSkipEvent: " << event
1196 << " nextsymbol: " << memevent[event].nextsymbol
1197 << endl;
1198 #endif
1199 int foundskip = 0;
1200 int dot = memevent[event].dot;
1201 int pro = memevent[event].prodtn;
1202 int lrhs = memprodtn[pro].lrhs;
1203 int xerlevel = 1;
1204 while (!foundskip && (xerlevel++ <= erlevel) && (dot < lrhs)) {
1205 int nextsymbol = memrhs[memprodtn[pro].rhs+dot];
1206 if (nextsymbol >= 0) {
1207 if (inputterm[lasttokenerror] == nextsymbol)
1208 foundskip = 1;
1209 else
1210 dot ++;
1211 } else {
1212 if ((inputterm[lasttokenerror] < maxtermn) && (ldertmtb[addrtermn[inputterm[lasttokenerror]]-nextsymbol]))
1213 foundskip = 1;
1214 else
1215 dot ++;
1216 }
1217 }
1218 if (dot == lrhs)
1219 foundskip = 1;
1220 if (foundskip) {
1221 success = 1;
1222 tryEvent(memevent[event].prodtn,dot,
1223 memevent[event].fpos,lasttokenerror,
1224 memevent[event].prevnode,memevent[event].prevevent);
1225 }
1226 event = memevent[event].nextevent;
1227 }
1228
1229
1230 // InputRuleSkip Strategy
1231 #ifdef SCPTRACE
1232 cout << "SCPtrace$$ InputRuleSkipStrategy" << endl;
1233 #endif
1234
1235 event = eventterm[lasttokenerror];
1236 while (event) {
1237 #ifdef SCPTRACE
1238 cout << "SCPtrace$$ InputRuleSkipEvent: " << event
1239 << " nextsymbol: " << memevent[event].nextsymbol
1240 << endl;
1241 #endif
1242 int foundskip = 0;
1243 int dot = memevent[event].dot;
1244 int pos = lasttokenerror;
1245 int pro = memevent[event].prodtn;
1246 int lrhs = memprodtn[pro].lrhs;
1247 int xerlevel = 1;
1248 while (!foundskip && (xerlevel++ <= erlevel) && (dot < lrhs) && (pos < lengthterm-1)) {
1249 int nextsymbol = memrhs[memprodtn[pro].rhs+dot];
1250 if (nextsymbol >= 0) {
1251 if (inputterm[pos] == nextsymbol)
1252 foundskip = 1;
1253 else {
1254 dot ++;
1255 pos ++;
1256 }
1257 } else {
1258 if ((inputterm[pos] < maxtermn) && (ldertmtb[addrtermn[inputterm[pos]]-nextsymbol]))
1259 foundskip = 1;
1260 else {
1261 dot ++;
1262 pos ++;
1263 }
1264 }
1265 }
1266 if (dot == lrhs)
1267 foundskip = 1;
1268
1269 if (foundskip) {
1270 success = 1;
1271 tryEvent(memevent[event].prodtn,dot,
1272 memevent[event].fpos,pos,
1273 memevent[event].prevnode,memevent[event].prevevent);
1274 }
1275 event = memevent[event].nextevent;
1276 }
1277
1278
1279 if (!success) {
1280 errorRecovery(bubblerecovery);
1281 return;
1282 }
1283
1284 // Parsing Continuation
1285 int tk;
1286 if (curbubble) {
1287 for (tk = lasttokenerror; tk < lengthterm; tk++)
1288 if (eventterm[tk])
1289 runTokenBubble(tk);
1290 } else {
1291 for (tk = lasttokenerror; tk < lengthterm-1; tk++)
1292 if ((inputterm[tk] < maxtermn) &&
1293 (eventterm[tk]))
1294 runToken(tk);
1295 }
1296
1297 if (!rootnode)
1298 errorRecovery(bubblerecovery);
1299 }
1300
getRootNode()1301 int ScpParser::getRootNode()
1302 {
1303 return rootnode;
1304 }
1305
getProductionNumber(int node)1306 int ScpParser::getProductionNumber(int node)
1307 {
1308 if (node > 0)
1309 return memanal[memnode[node].initanal].prodtn-1;
1310 else
1311 return -1;
1312 }
1313
getFirstPosition(int node)1314 int ScpParser::getFirstPosition(int node)
1315 {
1316 if (node > 0)
1317 return memnode[node].fpos;
1318 else
1319 return -1;
1320 }
1321
getLastPosition(int node)1322 int ScpParser::getLastPosition(int node)
1323 {
1324 if (node > 0)
1325 return memnode[node].lpos;
1326 else
1327 return -1;
1328 }
1329
getNumberOfChildren(int node)1330 int ScpParser::getNumberOfChildren(int node)
1331 {
1332 if (node > 0)
1333 return memprodtn[memanal[memnode[node].initanal].prodtn].lgather;
1334 else
1335 return -1;
1336 }
1337
getChild(int node,int number)1338 int ScpParser::getChild(int node,int number)
1339 {
1340 int nchildren;
1341 if ((node > 0) && ((nchildren = getNumberOfChildren(node)) > number)) {
1342 int position = nchildren - number - 1;
1343 if (!position)
1344 return memanal[memnode[node].initanal].prevnode;
1345 else {
1346 int prevevent = memanal[memnode[node].initanal].prevevent;
1347 while (prevevent && (--position))
1348 prevevent = memevent[prevevent].prevevent;
1349 if (prevevent)
1350 return memevent[prevevent].prevnode;
1351 }
1352 }
1353 return -1;
1354 }
1355
getLHSProduction(int prod)1356 int ScpParser::getLHSProduction(int prod)
1357 {
1358 if (prod < curprodtn) {
1359 if (memprodtn[prod+1].bubble)
1360 return memabslnt[-membubble[memprodtn[prod+1].bubble].abslnt].baseNT;
1361 else
1362 return memabslnt[-memprodtn[prod+1].lhs].baseNT;
1363 } else
1364 return 0;
1365 }
1366
getNumberOfErrors()1367 int ScpParser::getNumberOfErrors()
1368 {
1369 return curerrorlist;
1370 }
1371
getErrorPosition(int errornumber)1372 int ScpParser::getErrorPosition(int errornumber)
1373 {
1374 if ((errornumber > 0) && (errornumber <= curerrorlist))
1375 return errorlist[errornumber]-1;
1376 else
1377 return -1;
1378 }
1379
getAlternativesStandardError(int errornumber)1380 Vector<int> ScpParser::getAlternativesStandardError(int errornumber)
1381 {
1382 Vector<int> alter (0);
1383 if ((errornumber > 0) && (errornumber <= curerrorlist)) {
1384 int addralter = (errornumber-1)*(maxtermn+(maxnontm*2));
1385 int index = 0;
1386 for (int tm=0; tm < maxtermn; tm++) {
1387 if (memalter[addralter+tm]) {
1388 alter.expandBy(1);
1389 alter[index++] = tm;
1390 }
1391 }
1392 }
1393 return alter;
1394 }
1395
getBubblesExceptionError(int errornumber)1396 Vector<int> ScpParser::getBubblesExceptionError(int errornumber)
1397 {
1398 Vector<int> bexcep (0);
1399 if ((errornumber > 0) && (errornumber <= curerrorlist)) {
1400 int addrbexcep = ((errornumber-1)*(maxtermn+(maxnontm*2)))+maxtermn;
1401 int index = 0;
1402 for (int nt=1; nt<maxnontm; nt++) {
1403 if (memalter[addrbexcep+nt]) {
1404 bexcep.expandBy(1);
1405 bexcep[index++] = getBaseNT(-nt);
1406 }
1407 }
1408 }
1409 return bexcep;
1410 }
1411
getBubblesCloseParenthesisError(int errornumber)1412 Vector<int> ScpParser::getBubblesCloseParenthesisError(int errornumber)
1413 {
1414 Vector<int> cparen (0);
1415 if ((errornumber > 0) && (errornumber <= curerrorlist)) {
1416 int addrcparen = ((errornumber-1)*(maxtermn+(maxnontm*2)))+maxtermn+maxnontm;
1417 int index = 0;
1418 for (int nt=1; nt<maxnontm; nt++) {
1419 if (memalter[addrcparen+nt]) {
1420 cparen.expandBy(1);
1421 cparen[index++] = getBaseNT(-nt);
1422 }
1423 }
1424 }
1425 return cparen;
1426 }
1427
nextAnalysis()1428 int ScpParser::nextAnalysis()
1429 {
1430 if (rootnode) {
1431 if (!prevnextanal) {
1432 initAnalysis();
1433 prevnextanal = 1;
1434 }
1435 return skipAnalysis(rootnode);
1436 }
1437 return 0;
1438 }
1439
initAnalysis()1440 void ScpParser::initAnalysis()
1441 {
1442 for (int nd=1; nd <= curnode; nd++)
1443 memnode[nd].skipanal = memnode[nd].initanal;
1444 }
1445
skipAnalysis(int node)1446 int ScpParser::skipAnalysis(int node)
1447 {
1448 if (node <= 0)
1449 return 0;
1450 for (int nch=0; nch<getNumberOfChildren(node); nch++) {
1451 int ch = getChild(node,nch);
1452 if (skipAnalysis(ch))
1453 return 1;
1454 }
1455 if (memanal[memnode[node].initanal].nextanal) {
1456 memnode[node].initanal = memanal[memnode[node].initanal].nextanal;
1457 return 1;
1458 } else {
1459 memnode[node].initanal = memnode[node].skipanal;
1460 return 0;
1461 }
1462 }
1463
1464 /* Be careful with MAXINT */
setAmbNode(int node)1465 int ScpParser::setAmbNode(int node)
1466 {
1467 int pnode;
1468 int pevent;
1469 int ambnode = 0;
1470 int ambanal;
1471 int anal = memnode[node].initanal;
1472 while (anal) {
1473 ambanal = 1;
1474 if (pnode = memanal[anal].prevnode) {
1475 if (memambnode[pnode])
1476 ambanal *= memambnode[pnode];
1477 else
1478 ambanal *= setAmbNode(pnode);
1479 }
1480 pevent = memanal[anal].prevevent;
1481 while (pevent) {
1482 if (pnode = memevent[pevent].prevnode) {
1483 if (memambnode[pnode])
1484 ambanal *= memambnode[pnode];
1485 else
1486 ambanal *= setAmbNode(pnode);
1487 }
1488 pevent = memevent[pevent].prevevent;
1489 }
1490 anal = memanal[anal].nextanal;
1491 ambnode += ambanal;
1492 }
1493 memambnode[node] = ambnode;
1494 return ambnode;
1495 }
1496
freeCurrentParse()1497 void ScpParser::freeCurrentParse()
1498 {
1499 maxlenterm = 0;
1500 delete [] nodeterm;
1501 nodeterm = 0;
1502
1503 lenevent = 0;
1504 delete [] memevent;
1505 memevent = 0;
1506
1507 lennode = 0;
1508 delete [] memnode;
1509 memnode = 0;
1510 delete [] memambnode;
1511 memambnode = 0;
1512
1513 lenanal = 0;
1514 delete [] memanal;
1515 memanal = 0;
1516
1517 lendetect = 0;
1518 delete [] memdetect;
1519 memdetect = 0;
1520 delete [] typedetect;
1521 typedetect = 0;
1522
1523 lenalter = 0;
1524 delete [] memalter;
1525 memalter = 0;
1526 }
1527
printCurrentParse()1528 void ScpParser::printCurrentParse()
1529 {
1530 cout << " *** MSCP: printCurrentParse *** " << endl;
1531 int root = getRootNode();
1532 cout << " getRootNode = " << root << endl;
1533 int nextana;
1534 do {
1535 cout << "#############################" << endl;
1536 printNode(root);
1537 nextana = nextAnalysis();
1538 cout << "# nextAnalysis = " << nextana << endl;
1539 } while (nextana);
1540 }
1541
printNode(int node)1542 void ScpParser::printNode(int node)
1543 {
1544 cout << "*****************************" << endl;
1545 cout << "* Node: " << node << endl;
1546 int first = getFirstPosition(node);
1547 cout << "getFirstPosition = " << first << endl;
1548 int last = getLastPosition(node);
1549 cout << "getLastPosition = " << last << endl;
1550 int prod = getProductionNumber(node);
1551 cout << "getProductionNumber = " << prod << endl;
1552 int nch = getNumberOfChildren(node);
1553 cout << "getNumberOfChildren = " << nch << endl;
1554 int xch;
1555 for (int ch=0; ch < nch; ch++) {
1556 xch = getChild(node,ch);
1557 cout << "getChild (" << ch << ") = " << xch << endl;
1558 }
1559 cout << "*****************************" << endl;
1560 for (int ch=0; ch < nch; ch++) {
1561 xch = getChild(node,ch);
1562 printNode(xch);
1563 }
1564 }
1565
1566
printSentence()1567 void ScpParser::printSentence()
1568 {
1569 cout << "###############################" << endl;
1570 cout << "## printSentence " << endl;
1571
1572 for (int nd=1; nd<=curnode; nd++) {
1573 cout << "=====================" << endl;
1574 cout << " Node: " << nd << endl;
1575 cout << " Symbol: " << printSymbol(memnode[nd].symbol) << endl;
1576 cout << " First position: " << memnode[nd].fpos << endl;
1577 cout << " Last position: " << memnode[nd].lpos << endl;
1578 int anal = memnode[nd].initanal;
1579 while (anal) {
1580 cout << " Anal: " << anal << endl;
1581 cout << " Production: " << memanal[anal].prodtn-1 << endl;
1582 cout << " Nodes: ";
1583 printAnalNodes(memanal[anal].prevevent);
1584 if (memanal[anal].prevnode)
1585 cout << memanal[anal].prevnode << " ";
1586 anal = memanal[anal].nextanal;
1587 cout << endl;
1588 }
1589 }
1590 }
1591
printAnalNodes(int event)1592 void ScpParser::printAnalNodes(int event)
1593 {
1594 if (event) {
1595 printAnalNodes(memevent[event].prevevent);
1596 if (memevent[event].prevnode)
1597 cout << memevent[event].prevnode << " ";
1598 }
1599 }
1600
printSymbol(int absl)1601 char* ScpParser::printSymbol(int absl)
1602 {
1603 char p[100];
1604
1605 sprintf(p,"%d<%d/%d>",absl,getBaseNT(absl),getPrecNT(absl));
1606 return strdup(p);
1607 }
1608
printErrorDetect()1609 void ScpParser::printErrorDetect()
1610 {
1611 cout << " *** MSCP: printErrorDetection *** " << endl;
1612
1613 for (int er=1; er <= curerrorlist; er++) {
1614 cout << "#############################" << endl;
1615 cout << "# ErrorNumber: " << er << endl;
1616 cout << "# Position: " << errorlist[er]-1 << endl;
1617 cout << "# Alternatives: ";
1618 int linalt = 0;
1619 int addralter = (er-1)*maxtermn;
1620 for (int tm=0; tm < maxtermn; tm++) {
1621 if (memalter[addralter+tm]) {
1622 if (linalt > 8) {
1623 cout << endl << "# ";
1624 linalt++;
1625 }
1626 printf("%4d ",tm);
1627 linalt++;
1628 }
1629 }
1630 cout << endl;
1631 }
1632 }
1633
1634
1635
1636
1637