00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042
00043
00044
00045
00046
00047
00048
00049
00050
00051
00052
00053
00054
00055
00056
00057
00058 #include <typeinfo>
00059
00060 #include "lanalyzer.hh"
00061 #include "debug.h"
00062 #include "parser_spec.hh"
00063 #include "ebnf_la_node.hh"
00064 #include "ebnf_node_algo.hh"
00065 #include "token_spec.hh"
00066 #include "prop_registry.hh"
00067 #include "vbitset.hh"
00068
00069 static string curProdName;
00070
00074 class ColourResetAlgo : public EbnfNodeAlgo
00075 {
00076 public:
00077
00078 virtual bool operator() (EbnfNode &n) throw (EbnfNodeAlgoException)
00079 {
00080 EbnfLaNode &nn = dynamic_cast<EbnfLaNode&>(n);
00081 if ((nn.laSpec != NULL) && (nn.laSpec->synLa != NULL))
00082 nn.laSpec->synLa->dfTraverse(*this);
00083 nn.colour = EbnfLaNode::white;
00084 return true;
00085 }
00086 };
00087
00088
00093 class LaNumberingAlgo : public EbnfNodeAlgo
00094 {
00095 public:
00096
00097 LaNumberingAlgo () : counter(0)
00098 {}
00099
00100 virtual bool operator () (EbnfNode &n) throw (EbnfNodeAlgoException)
00101 {
00102 NumberedLaSpec *la = dynamic_cast<EbnfLaNode&>(n).laSpec;
00103 if (la != NULL)
00104 {
00105 la->id = counter++;
00106 if (la->synLa != NULL)
00107 la->synLa->dfTraverse(*this);
00108 }
00109 return true;
00110 }
00111
00112 private:
00113 int counter;
00114 };
00115
00121 class NontermFixAlgo : public EbnfNodeAlgo
00122 {
00123 public:
00124
00125 NontermFixAlgo (ParserSpec &pSpec_) : pSpec(pSpec_)
00126 {}
00127
00128 virtual bool operator () (EbnfNode &n) throw (EbnfNodeAlgoException)
00129 {
00130 EbnfLaNode &nn = dynamic_cast<EbnfLaNode&>(n);
00131 if ((nn.laSpec != NULL) && (nn.laSpec->synLa != NULL))
00132 nn.laSpec->synLa->dfTraverse(*this);
00133 if (typeid(n) == typeid(EbnfNonterminalNode))
00134 {
00135 EbnfNonterminalNode &nnn = dynamic_cast<EbnfNonterminalNode&>(n);
00136 if (!pSpec.isProduction(nnn.nontermName))
00137 throw EbnfNodeAlgoException (nnn.getPos(), string("Nonterminal \"") +
00138 nnn.nontermName + "\" was not declared.");
00139 nnn.nonterm = pSpec.getProduction(nnn.nontermName).expansion;
00140 }
00141 return true;
00142 }
00143
00144 private:
00145
00146 ParserSpec &pSpec;
00147 };
00148
00149
00161 class LRecDetectAlgo : public EbnfNodeAlgo
00162 {
00163 virtual bool operator() (EbnfNode &n) throw (EbnfNodeAlgoException)
00164 {
00165 EbnfLaNode &n1 = dynamic_cast<EbnfLaNode&>(n);
00166
00167 if (n1.colour == EbnfLaNode::black)
00168 return false;
00169
00170
00171 if (n1.colour == EbnfLaNode::grey) {
00172
00173
00174 throw EbnfNodeAlgoException(n1.getPos(),
00175 "form a left-reccursive chain.");
00176 }
00177
00178 n1.colour = EbnfLaNode::grey;
00179
00180 if (n1.laSpec != NULL && n1.laSpec->synLa != NULL)
00181 n1.laSpec->synLa->rdfTraverse(*this);
00182
00183 if (typeid(n) == typeid(EbnfCatNode)) {
00184 EbnfCatNode &nn = dynamic_cast<EbnfCatNode&>(n);
00185 nn.post->colour = EbnfLaNode::black;
00186
00187
00188
00189 } else if (typeid(n) == typeid(EbnfNonterminalNode)) {
00190 EbnfNonterminalNode &nn = dynamic_cast<EbnfNonterminalNode&>(n);
00191 try {
00192 if (nn.nonterm != NULL) {
00193 nn.nonterm->rdfTraverse(*this);
00194 }
00195 } catch (EbnfNodeAlgoException &ex) {
00196 throw EbnfNodeAlgoException(ex.where(),
00197 nn.nontermName + " " + ex.what());
00198 }
00199 }
00200
00201 n1.colour = EbnfLaNode::white;
00202 }
00203 };
00204
00205
00212 class EbnfRepetitiveAlgo : public EbnfNodeAlgo
00213 {
00214 public:
00215
00221 void init() { _done = true; }
00222
00226 bool done() { return _done; }
00227
00228 protected:
00229
00234 void markUndone () { _done = false; }
00235
00236 private:
00237 bool _done;
00238 };
00239
00240
00241
00252 void runAlgo (vector<ProductionSpec> &prods, EbnfNodeAlgo &algo,
00253 bool reverse = false) throw (EbnfNodeAlgoException)
00254 {
00255 ColourResetAlgo a;
00256
00257
00258 for (int i = 0; i < prods.size(); i++)
00259 if (prods[i].expansion != NULL)
00260 prods[i].expansion->dfTraverse(a);
00261
00262
00263
00264 for (int i = 0; i < prods.size(); i++)
00265 if (prods[i].expansion != NULL) {
00266 curProdName = prods[i].name;
00267 try {
00268 if (reverse)
00269 prods[i].expansion->rdfTraverse(algo);
00270 else
00271 prods[i].expansion->dfTraverse(algo);
00272 } catch (EbnfNodeAlgoException &ex) {
00273 throw EbnfNodeAlgoException(ex.where(), string("In \"") +
00274 prods[i].name + + "\": " + ex.what());
00275 }
00276 }
00277 }
00278
00279
00294 void runAlgo (vector<ProductionSpec> &prods, EbnfRepetitiveAlgo &algo,
00295 bool reverse = false) throw (EbnfNodeAlgoException)
00296 {
00297 ColourResetAlgo a;
00298 bool done[prods.size()];
00299
00300
00301 for (int i = 0; i < prods.size(); i++)
00302 if (prods[i].expansion != NULL) {
00303 prods[i].expansion->dfTraverse(a);
00304 done[i] = false;
00305 } else
00306 done[i] = true;
00307
00308
00309 bool allDone = false;
00310 while (!allDone) {
00311 allDone = true;
00312
00313 for (int i = 0; i < prods.size(); i++)
00314 if (!done[i]) {
00315 algo.init();
00316 try {
00317 if (reverse)
00318 prods[i].expansion->rdfTraverse(algo);
00319 else
00320 prods[i].expansion->dfTraverse(algo);
00321 } catch (EbnfNodeAlgoException &ex) {
00322 throw EbnfNodeAlgoException(ex.where(), string("In \"") +
00323 prods[i].name + + "\": " + ex.what());
00324 }
00325 if (algo. done())
00326 done[i] = true;
00327 else allDone = false;
00328 }
00329 }
00330 }
00331
00332
00336 class EbnfNullableCompAlgo : public EbnfRepetitiveAlgo
00337 {
00338 public:
00339
00340 virtual bool operator() (EbnfNode &n) throw (EbnfNodeAlgoException)
00341 {
00342 EbnfLaNode &n1 = dynamic_cast<EbnfLaNode&>(n);
00343
00344 if (n1.colour == EbnfLaNode::black)
00345 return true;
00346
00347
00348 n1.colour = EbnfLaNode::grey;
00349
00350 if (n1.laSpec != NULL && n1.laSpec->synLa != NULL)
00351 n1.laSpec->synLa->dfTraverse(*this);
00352
00353 if (typeid(n) == typeid(EbnfOrNode)) {
00354 EbnfOrNode &nn = dynamic_cast<EbnfOrNode&>(n);
00355 nn.nullable = nn.pre->nullable || nn.post->nullable;
00356 if ((nn.pre->colour == EbnfLaNode::black) &&
00357 (nn.post->colour == EbnfLaNode::black))
00358 nn.colour = EbnfLaNode::black;
00359 } else if (typeid(n) == typeid(EbnfCatNode)) {
00360 EbnfCatNode &nn = dynamic_cast<EbnfCatNode&>(n);
00361 nn.nullable = nn.pre->nullable && nn.post->nullable;
00362
00363
00364
00365 if ((nn.pre->colour == EbnfLaNode::black) &&
00366 (nn.post->colour == EbnfLaNode::black))
00367 nn.colour = EbnfLaNode::black;
00368 else
00369 if ((nn.nullable == false) &&
00370 ((nn.pre->colour == EbnfLaNode::black) ||
00371 (nn.post->colour == EbnfLaNode::black)))
00372 nn.colour = EbnfLaNode::black;
00373 } else if (typeid(n) == typeid(EbnfStarNode)) {
00374 EbnfStarNode &nn = dynamic_cast<EbnfStarNode&>(n);
00375 nn.nullable = true;
00376 nn.colour = EbnfLaNode::black;
00377 } else if (typeid(n) == typeid(EbnfTerminalNode)) {
00378 EbnfTerminalNode &nn = dynamic_cast<EbnfTerminalNode&>(n);
00379 nn.nullable = false;
00380 nn.colour = EbnfLaNode::black;
00381 } else if (typeid(n) == typeid(EbnfNonterminalNode)) {
00382 EbnfNonterminalNode &nn = dynamic_cast<EbnfNonterminalNode&>(n);
00383 if (nn.nonterm != NULL) {
00384 nn.nullable = nn.nonterm->nullable;
00385 if (nn.nonterm->colour == EbnfLaNode::black)
00386 nn.colour = EbnfLaNode::black;
00387
00388 } else {
00389
00390
00391
00392
00393
00394
00395
00396 nn.nullable = false;
00397 nn.colour = EbnfLaNode::black;
00398 }
00399 } else if (typeid(n) == typeid(EbnfLambdaNode)) {
00400 EbnfLambdaNode &nn = dynamic_cast<EbnfLambdaNode&>(n);
00401 nn.nullable = true;
00402 nn.colour = EbnfLaNode::black;
00403 }
00404
00405 if (n1.colour != EbnfLaNode::black)
00406
00407
00408 markUndone();
00409
00410 return true;
00411 }
00412 };
00413
00414
00418 class EbnfFirstCompAlgo : public EbnfRepetitiveAlgo
00419 {
00420 public:
00421
00422 EbnfFirstCompAlgo (int maxToken_) : maxToken(maxToken_)
00423 {}
00424
00425 virtual bool operator() (EbnfNode &n) throw (EbnfNodeAlgoException)
00426 {
00427 EbnfLaNode &n1 = dynamic_cast<EbnfLaNode&>(n);
00428
00429 if (n1.colour == EbnfLaNode::black)
00430 return true;
00431
00432
00433
00434 if (n1.laSpec != NULL && n1.laSpec->synLa != NULL)
00435 n1.laSpec->synLa->dfTraverse(*this);
00436
00437 if (typeid(n) == typeid(EbnfOrNode)) {
00438 EbnfOrNode &nn = dynamic_cast<EbnfOrNode&>(n);
00439 nn.first = nn.pre->first;
00440 nn.first |= nn.post->first;
00441 if ((nn.pre->colour == EbnfLaNode::black) &&
00442 (nn.post->colour == EbnfLaNode::black))
00443 nn.colour = EbnfLaNode::black;
00444 } else if (typeid(n) == typeid(EbnfCatNode)) {
00445 EbnfCatNode &nn = dynamic_cast<EbnfCatNode&>(n);
00446 nn.first = nn.pre->first;
00447 if (nn.pre->nullable) {
00448 nn.first |= nn.post->first;
00449
00450 if ((nn.pre->colour == EbnfLaNode::black) &&
00451 (nn.post->colour == EbnfLaNode::black))
00452 nn.colour = EbnfLaNode::black;
00453 } else if (nn.pre->colour == EbnfLaNode::black)
00454 nn.colour = EbnfLaNode::black;
00455
00456 } else if (typeid(n) == typeid(EbnfStarNode)) {
00457 EbnfStarNode &nn = dynamic_cast<EbnfStarNode&>(n);
00458 nn.first = nn.in->first;
00459 if (nn.in->colour == EbnfLaNode::black)
00460 nn.colour = EbnfLaNode::black;
00461 } else if (typeid(n) == typeid(EbnfTerminalNode)) {
00462 EbnfTerminalNode &nn = dynamic_cast<EbnfTerminalNode&>(n);
00463 nn.first.resize(nn.terminal.id() + 1);
00464 nn.first[nn.terminal.id()].set();
00465 nn.colour = EbnfLaNode::black;
00466 } else if (typeid(n) == typeid(EbnfNonterminalNode)) {
00467 EbnfNonterminalNode &nn = dynamic_cast<EbnfNonterminalNode&>(n);
00468 if (nn.nonterm != NULL) {
00469 nn.first = nn.nonterm->first;
00470 if (nn.nonterm->colour == EbnfLaNode::black)
00471 nn.colour = EbnfLaNode::black;
00472 } else {
00473
00474 nn.first.resize(maxToken);
00475 for (vBitset::reference r = nn.first.begin(); r.neq(nn.first.end());
00476 r.next())
00477 r.set();
00478 nn.colour = EbnfLaNode::black;
00479 }
00480
00481 } else if (typeid(n) == typeid(EbnfLambdaNode)) {
00482
00483 EbnfLambdaNode &nn = dynamic_cast<EbnfLambdaNode&>(n);
00484 nn.colour = EbnfLaNode::black;
00485 }
00486
00487 if (n1.colour != EbnfLaNode::black)
00488
00489
00490 markUndone();
00491
00492 return true;
00493 }
00494
00495 private:
00496 int maxToken;
00497
00498 };
00499
00500
00501
00505 class EbnfFollowCompAlgo : public EbnfNodeAlgo
00506 {
00507
00508
00509
00510
00511
00512
00513 virtual bool operator() (EbnfNode &n) throw (EbnfNodeAlgoException)
00514 {
00515 EbnfLaNode &n1 = dynamic_cast<EbnfLaNode&>(n);
00516
00517 if (n1.colour == EbnfLaNode::grey)
00518 return false;
00519
00520 n1.colour = EbnfLaNode::grey;
00521
00522 if (n1.laSpec != NULL && n1.laSpec->synLa != NULL)
00523 n1.laSpec->synLa->rdfTraverse(*this);
00524
00525 if (typeid(n) == typeid(EbnfOrNode)) {
00526 EbnfOrNode &nn = dynamic_cast<EbnfOrNode&>(n);
00527 nn.pre->follow |= nn.follow;
00528 nn.post->follow |= nn.follow;
00529 } else if (typeid(n) == typeid(EbnfCatNode)) {
00530 EbnfCatNode &nn = dynamic_cast<EbnfCatNode&>(n);
00531 nn.pre->follow |= nn.post->first;
00532 if (nn.post->nullable)
00533 nn.pre->follow |= nn.follow;
00534 nn.post->follow |= nn.follow;
00535 } else if (typeid(n) == typeid(EbnfStarNode)) {
00536 EbnfStarNode &nn = dynamic_cast<EbnfStarNode&>(n);
00537 nn.in->follow |= nn.follow;
00538 } else if (typeid(n) == typeid(EbnfNonterminalNode)) {
00539 EbnfNonterminalNode &nn = dynamic_cast<EbnfNonterminalNode&>(n);
00540 if (nn.nonterm != NULL) {
00541 vBitset tmp(nn.nonterm->follow);
00542 nn.nonterm->follow |= nn.follow;
00543 if (tmp != nn.nonterm->follow)
00544 nn.nonterm->rdfTraverse(*this);
00545 }
00546 }
00547
00548 n1.colour = EbnfLaNode::white;
00549 return true;
00550 }
00551 };
00552
00553
00562 class EbnfLl1CheckAlgo : public EbnfNodeAlgo
00563 {
00564 public:
00565
00566 EbnfLl1CheckAlgo (ITokenSpec &tokens_, int globalLa_) :
00567 tokens(tokens_), globalLa(globalLa_), usesLa(false)
00568 {}
00569
00570 virtual bool operator() (EbnfNode &n) throw (EbnfNodeAlgoException)
00571 {
00572 EbnfLaNode &n1 = dynamic_cast<EbnfLaNode&>(n);
00573
00574 if (n1.laSpec != NULL && n1.laSpec->synLa != NULL)
00575 n1.laSpec->synLa->dfTraverse(*this);
00576
00577 if (typeid(n) == typeid(EbnfOrNode)) {
00578 EbnfOrNode &nn = dynamic_cast<EbnfOrNode&>(n);
00579 vBitset v = nn.pre->first & nn.post->first;
00580 if (!v.all0()) {
00581 if (nn.pre->laSpec == NULL) {
00582 if (globalLa > 1) {
00583 nn.pre->laSpec = new NumberedLaSpec(globalLa,
00584 nn.pre->clone(), "",
00585 Position());
00586 usesLa = true;
00587 } else
00588 warn(nn.getPos(), v);
00589 }
00590
00591 if (nn.pre->laSpec != NULL) {
00592 nn.pre->laSpec->ignore = false;
00593 usesLa = true;
00594 }
00595
00596 if (nn.pre->laSpec != NULL &&
00597 (nn.pre->laSpec->fixedLa != 0 || nn.pre->laSpec->synLa != NULL)) {
00598 if (nn.pre->laSpec->fixedLa == 0)
00599 nn.pre->laSpec->fixedLa = INT_MAX;
00600 if (nn.pre->laSpec->synLa == NULL)
00601 nn.pre->laSpec->synLa = nn.pre->clone();
00602 }
00603 }
00604 }
00605
00606 if (n1.nullable && typeid(n1) != typeid(EbnfNonterminalNode)) {
00607 vBitset v = n1.first & n1.follow;
00608 if (!v.all0()) {
00609 EbnfLaNode &nn = dynamic_cast<EbnfLaNode&>(n1[0]);
00610 if (nn.laSpec == NULL) {
00611 if (globalLa > 1) {
00612 nn.laSpec = new NumberedLaSpec(globalLa, nn.clone(),
00613 "", Position());
00614 usesLa = true;
00615 } else
00616 warn(n1.getPos(), v);
00617 }
00618
00619 if (nn.laSpec != NULL) {
00620 nn.laSpec->ignore = false;
00621 usesLa = true;
00622 }
00623
00624
00625 if (nn.laSpec != NULL &&
00626 (nn.laSpec->fixedLa != 0 || nn.laSpec->synLa != NULL)) {
00627 if (nn.laSpec->fixedLa == 0)
00628 nn.laSpec->fixedLa = INT_MAX;
00629 if (nn.laSpec->synLa == NULL)
00630 nn.laSpec->synLa = nn.clone();
00631 }
00632 }
00633 }
00634
00635 return true;
00636 }
00637
00642 void warn (const Position &pos, vBitset v)
00643 {
00644 string msg(" : no lookahead specified at non-LL(1) choice point. Common prefixed are: ");
00645 msg = string("in ") + curProdName + msg;
00646 for (int i = 0; i < v.length(); i++)
00647 if (v[i].get()) {
00648 msg += tokens[i].name();
00649 msg.push_back(' ');
00650 }
00651 cerr << formatWarning(pos, msg) << endl;
00652 }
00653
00658 ITokenSpec &tokens;
00659
00663 int globalLa;
00664
00676 bool usesLa;
00677 };
00678
00679
00680 void LAnalyzer::makeLa (ParserSpec &pSpec) throw (ParseException)
00681 {
00682 vector<ProductionSpec> &productions = pSpec.productions;
00683
00684 #ifdef DEBUG
00685 EbnfLaNode::tokens = &pSpec.tokens;
00686 #endif
00687 try {
00688
00689
00690 NontermFixAlgo nfa(pSpec);
00691 runAlgo(productions, nfa);
00692
00693 LRecDetectAlgo lrda;
00694 runAlgo(productions, lrda, true);
00695
00696
00697 EbnfNullableCompAlgo nca;
00698 runAlgo(productions, nca);
00699
00700
00701 EbnfFirstCompAlgo fca(pSpec.tokens.count());
00702 runAlgo(productions, fca);
00703
00704
00705 EbnfFollowCompAlgo lca;
00706 runAlgo(productions, lca, true);
00707
00708
00709 EbnfLl1CheckAlgo l1ca(pSpec.tokens, registry["DEFAULT_LOOKAHEAD"]);
00710 runAlgo(productions, l1ca);
00711
00712
00713
00714
00715
00716 LaNumberingAlgo lana;
00717 runAlgo(productions, lana);
00718
00719 } catch (EbnfNodeAlgoException &ex) {
00720 throw ParseException(ex.where(), ex.what());
00721 }
00722
00723 #ifdef DEBUG
00724 if (((string)registry["debug"]).find('d') != string::npos) {
00725 cerr << "------------------------------------------------------------"
00726 << endl << "Productions after LA analysis stage: " << endl << endl;
00727 for (int i = 0; i < productions.size(); i++) {
00728 productions[i].dump(cerr);
00729 cerr << endl;
00730 }
00731 cerr << "------------------------------------------------------------"
00732 << endl;
00733 }
00734 #endif
00735
00736 }