File indexing completed on 2024-04-28 15:54:23
0001 /* This file is part of kdev-pg-qt 0002 Copyright (C) 2005 Roberto Raggi <roberto@kdevelop.org> 0003 Copyright (C) 2006 Jakob Petsovits <jpetso@gmx.at> 0004 Copyright (C) 2006 Alexander Dymo <adymo@kdevelop.org> 0005 0006 This library is free software; you can redistribute it and/or 0007 modify it under the terms of the GNU Library General Public 0008 License as published by the Free Software Foundation; either 0009 version 2 of the License, or (at your option) any later version. 0010 0011 This library is distributed in the hope that it will be useful, 0012 but WITHOUT ANY WARRANTY; without even the implied warranty of 0013 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 0014 Library General Public License for more details. 0015 0016 You should have received a copy of the GNU Library General Public License 0017 along with this library; see the file COPYING.LIB. If not, write to 0018 the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, 0019 Boston, MA 02110-1301, USA. 0020 */ 0021 0022 #include "kdev-pg-checker.h" 0023 #include "kdev-pg-pretty-printer.h" 0024 #include "kdev-pg-bnf-visitor.h" 0025 0026 #include <QDebug> 0027 0028 //uncomment this to see debug output for follow checker 0029 // #define FOLLOW_CHECKER_DEBUG 0030 0031 namespace KDevPG 0032 { 0033 0034 QTextStream checkOut(stderr); 0035 0036 int ProblemSummaryPrinter::mFirstFirstConflictCount = 0; 0037 int ProblemSummaryPrinter::mFirstFollowConflictCount = 0; 0038 int ProblemSummaryPrinter::mErrorCount = 0; 0039 0040 void FirstFirstConflictChecker::operator()(Model::Node *node) 0041 { 0042 Model::EvolveItem *e = nodeCast<Model::EvolveItem*>(node); 0043 Q_ASSERT(e != nullptr); 0044 mSymbol = e->mSymbol; 0045 visitNode(node); 0046 } 0047 0048 void FirstFirstConflictChecker::visitAlternative(Model::AlternativeItem *node) 0049 { 0050 DefaultVisitor::visitAlternative(node); 0051 0052 mCheckedNode = node; 0053 check(node->mLeft, node->mRight); 0054 } 0055 0056 void FirstFirstConflictChecker::visitInlinedNonTerminal(Model::InlinedNonTerminalItem* node) 0057 { 0058 Q_UNUSED(node); 0059 } 0060 0061 void FirstFirstConflictChecker::check(Model::Node *left, Model::Node *right) 0062 { 0063 World::NodeSet const &left_first = globalSystem.first(left); 0064 World::NodeSet const &right_first = globalSystem.first(right); 0065 0066 QSet<Model::Node*> U = left_first; 0067 U.intersect( right_first ); 0068 0069 if (!U.empty()) 0070 { 0071 QTextStream& str( checkOut ); 0072 PrettyPrinter printer(str); 0073 str << "** WARNING found FIRST/FIRST conflict in " 0074 << mSymbol->mName << ":" << endl << "\tRule ``"; 0075 printer(mCheckedNode); 0076 // p(left); 0077 str << "''" << endl << "\tTerminals [" << endl; 0078 0079 QSet<Model::Node*>::iterator it = U.begin(); 0080 while (it != U.end()) 0081 { 0082 Model::Node *n = *it++; 0083 0084 str << "\t\t" << n; 0085 if (it != U.end()) 0086 str << ", "; 0087 str << endl; 0088 } 0089 str << "\t]" << endl << endl; 0090 ProblemSummaryPrinter::reportFirstFirstConflict(); 0091 } 0092 } 0093 0094 void FirstFirstConflictChecker::visitEvolve(Model::EvolveItem *node) 0095 { 0096 DefaultVisitor::visitEvolve(node); 0097 0098 World::Environment::iterator it = globalSystem.env.find(node->mSymbol); 0099 while (it != globalSystem.env.end()) 0100 { 0101 Model::SymbolItem *sym = it.key(); 0102 Model::EvolveItem *e = (*it); 0103 ++it; 0104 0105 if (sym != node->mSymbol || node == e) 0106 continue; 0107 0108 mCheckedNode = node; 0109 check(e, node); 0110 } 0111 } 0112 0113 void FirstFollowConflictChecker::operator()(Model::Node *node) 0114 { 0115 Model::EvolveItem *e = nodeCast<Model::EvolveItem*>(node); 0116 Q_ASSERT(e != nullptr); 0117 mSymbol = e->mSymbol; 0118 visitNode(node); 0119 } 0120 0121 void FirstFollowConflictChecker::check(Model::Node *node, Model::Node *sym) 0122 { 0123 if (!sym) 0124 sym = node; 0125 0126 World::NodeSet const &first = globalSystem.first(node); 0127 World::NodeSet const &follow = globalSystem.follow(sym); 0128 0129 QSet<Model::Node*> U = first; 0130 0131 U.intersect(follow); 0132 0133 if (!U.empty()) 0134 { 0135 QTextStream& str( checkOut ); 0136 PrettyPrinter p(str); 0137 str << "** WARNING found FIRST/FOLLOW conflict in " 0138 << mSymbol->mName; 0139 #ifdef FOLLOW_CHECKER_DEBUG 0140 str << "(" << (uint*)mSymbol << ")"; 0141 #endif 0142 str << ":" << endl << "\tRule ``"; 0143 p(node); 0144 #ifdef FOLLOW_CHECKER_DEBUG 0145 str << " [[" << (uint*)node << "]]"; 0146 #endif 0147 str << "''" << endl << "\tTerminals [" << endl; 0148 0149 QSet<Model::Node*>::iterator it = U.begin(); 0150 while (it != U.end()) 0151 { 0152 Model::Node *n = *it++; 0153 if (isZero(n)) 0154 continue; 0155 0156 str << "\t\t" << ((Model::TerminalItem*)n)->mName << ": conflicts with the FIRST set of: " << endl; 0157 FollowDepChecker(n).check(node); 0158 if (it != U.end()) 0159 str << "," << endl; 0160 } 0161 str << "\t]" << endl << endl; 0162 ProblemSummaryPrinter::reportFirstFollowConflict(); 0163 } 0164 } 0165 0166 void FollowDepChecker::check(Model::Node *node) 0167 { 0168 //avoid cyclical follow dependency check 0169 if (mVisited.find(node) != mVisited.end()) 0170 return; 0171 mVisited.insert(node); 0172 0173 World::FollowDep &D = globalSystem.followDep(node); 0174 QList<Model::Node*> FD = D.first.values(); 0175 QList<Model::Node*> FLD = D.second.values(); 0176 QTextStream& str( checkOut ); 0177 PrettyPrinter p(str); 0178 #ifdef FOLLOW_CHECKER_DEBUG 0179 str << "[["; p(node); str << " | " << (uint*)node << "]] "; 0180 str << "{" << node->kind << "}" << endl; 0181 #endif 0182 for (int i = 0; i != FD.size(); ++i) // no iterator → modifiable 0183 { 0184 if(BnfVisitor::isInternal(FD[i])) 0185 { 0186 World::NodeSet set = globalSystem.followDep(FD[i]).second; 0187 World::NodeSet set2 = globalSystem.followDep(FD[i]).first; // :-S has to be verified… 0188 for(auto jt = FD.begin(); jt != FD.end(); ++jt) 0189 { 0190 set.remove(*jt); 0191 set2.remove(*jt); 0192 } 0193 for(auto jt = set2.begin(); jt != set2.end(); ++jt) 0194 if(!BnfVisitor::isInternal(*jt)) 0195 FD.append(*jt); 0196 FD.append(set.values()); 0197 } 0198 else 0199 { 0200 World::NodeSet first = globalSystem.first(FD[i]); 0201 #ifdef FOLLOW_CHECKER_DEBUG 0202 str << " <iterating first "; 0203 for (World::NodeSet::const_iterator fit = first.begin(); fit != first.end(); ++fit) 0204 { 0205 p(*fit); 0206 str << " "; 0207 } 0208 str << ">"; 0209 #endif 0210 if (first.find(mTerminal) != first.end()) 0211 { 0212 str << "\t\t"; 0213 p(FD[i]); 0214 #ifdef FOLLOW_CHECKER_DEBUG 0215 str << " ( in \""; 0216 p(node); 0217 str << " \" )"; 0218 #endif 0219 str << ", " << endl; 0220 } 0221 } 0222 } 0223 for (int i = 0; i != FLD.size(); ++i) 0224 { 0225 if(BnfVisitor::isInternal(FLD[i])) 0226 { 0227 World::NodeSet set = globalSystem.followDep(FLD[i]).second; 0228 for(auto jt = FLD.begin(); jt != FLD.end(); ++jt) 0229 set.remove(*jt); 0230 FLD.append(set.values()); 0231 } 0232 else 0233 { 0234 World::NodeSet first = globalSystem.first(FLD[i]); 0235 #ifdef FOLLOW_CHECKER_DEBUG 0236 str << endl << "\t\t" << "in "; 0237 p(FLD[i]); 0238 str << endl; 0239 #endif 0240 check(FLD[i]); 0241 } 0242 } 0243 } 0244 0245 void FirstFollowConflictChecker::visitAlternative(Model::AlternativeItem *node) 0246 { 0247 DefaultVisitor::visitAlternative(node); 0248 0249 if (isZero(node->mRight)) 0250 return; 0251 0252 if (reducesToEpsilon(node)) 0253 check(node); 0254 } 0255 0256 void FirstFollowConflictChecker::visitCons(Model::ConsItem *node) 0257 { 0258 DefaultVisitor::visitCons(node); 0259 0260 if (reducesToEpsilon(node)) 0261 check(node); 0262 } 0263 0264 void FirstFollowConflictChecker::visitPlus(Model::PlusItem *node) 0265 { 0266 DefaultVisitor::visitPlus(node); 0267 0268 if (reducesToEpsilon(node)) 0269 check(node); 0270 } 0271 0272 void FirstFollowConflictChecker::visitStar(Model::StarItem *node) 0273 { 0274 DefaultVisitor::visitStar(node); 0275 0276 check(node); 0277 } 0278 0279 void FirstFollowConflictChecker::visitInlinedNonTerminal(Model::InlinedNonTerminalItem* node) 0280 { 0281 Q_UNUSED(node); 0282 } 0283 0284 void UndefinedSymbolChecker::visitInlinedNonTerminal(Model::InlinedNonTerminalItem* node) 0285 { 0286 if(node->mSymbol) 0287 visitSymbol(node->mSymbol); 0288 } 0289 0290 void UndefinedSymbolChecker::operator()(Model::Node *node) 0291 { 0292 Model::EvolveItem *e = nodeCast<Model::EvolveItem*>(node); 0293 Q_ASSERT(e != nullptr); 0294 mSymbol = e->mSymbol; 0295 visitNode(node); 0296 } 0297 0298 void UndefinedSymbolChecker::visitSymbol(Model::SymbolItem *node) 0299 { 0300 if (globalSystem.env.count(node) == 0) 0301 { 0302 checkOut << "** ERROR Undefined symbol ``" << node->mName << "'' in " 0303 << mSymbol->mName << endl; 0304 ProblemSummaryPrinter::reportError(); 0305 } 0306 } 0307 0308 void UndefinedSymbolChecker::visitVariableDeclaration(Model::VariableDeclarationItem *node) 0309 { 0310 if (node->mVariableType != Model::VariableDeclarationItem::TypeNode) 0311 return; 0312 0313 Model::SymbolItem *sym; 0314 0315 QString name = node->mType; 0316 World::SymbolSet::iterator it = globalSystem.symbols.find(name); 0317 if (it == globalSystem.symbols.end()) 0318 { 0319 checkOut << "** ERROR Undefined symbol ``" << name 0320 << "'' (rule parameter declaration) in " 0321 << mSymbol->mName << endl; 0322 ProblemSummaryPrinter::reportError(); 0323 return; 0324 } 0325 else 0326 sym = (*it); 0327 0328 if (globalSystem.env.count(sym) == 0) 0329 { 0330 checkOut << "** ERROR Undefined symbol ``" << node->mName 0331 << "'' (rule parameter declaration) in " 0332 << mSymbol->mName << endl; 0333 ProblemSummaryPrinter::reportError(); 0334 } 0335 } 0336 0337 void UndefinedTokenChecker::visitInlinedNonTerminal(Model::InlinedNonTerminalItem* node) 0338 { 0339 Q_UNUSED(node); 0340 } 0341 0342 void UndefinedTokenChecker::operator()(Model::Node *node) 0343 { 0344 Model::EvolveItem *e = nodeCast<Model::EvolveItem*>(node); 0345 Q_ASSERT(e != nullptr); 0346 mSymbol = e->mSymbol; 0347 visitNode(node); 0348 } 0349 0350 void UndefinedTokenChecker::visitTerminal(Model::TerminalItem *node) 0351 { 0352 QString name = node->mName; 0353 if (globalSystem.terminals.find(name) == globalSystem.terminals.end()) 0354 { 0355 checkOut << "** ERROR Undefined token ``" << node->mName << "'' in " 0356 << mSymbol->mName << endl; 0357 ProblemSummaryPrinter::reportError(); 0358 } 0359 } 0360 0361 void EmptyFirstChecker::operator()(Model::Node *node) 0362 { 0363 visitNode(node); 0364 } 0365 0366 void EmptyFirstChecker::visitNonTerminal(Model::NonTerminalItem *node) 0367 { 0368 Q_UNUSED(node); 0369 } 0370 0371 void EmptyFirstChecker::visitInlinedNonTerminal(Model::InlinedNonTerminalItem *node) 0372 { 0373 Q_UNUSED(node); 0374 } 0375 0376 void EmptyFirstChecker::visitSymbol(Model::SymbolItem *node) 0377 { 0378 if (globalSystem.first(node).empty()) 0379 { 0380 checkOut << "** ERROR Empty FIRST set for ``" << node->mName 0381 << "''" << endl; 0382 ProblemSummaryPrinter::reportError(); 0383 } 0384 } 0385 0386 void EmptyOperatorChecker::operator()(Model::Node *node) 0387 { 0388 visitNode(node); 0389 } 0390 0391 void EmptyOperatorChecker::visitOperator(Model::OperatorItem *node) 0392 { 0393 if (reducesToEpsilon((node->mBase->mSymbol))) 0394 { 0395 checkOut << "** ERROR Base symbol ``" << node->mBase->mSymbol->mName << "'' for operator ``" << node->mName << "'' reduces to zero" << endl; 0396 ProblemSummaryPrinter::reportError(); 0397 } 0398 } 0399 0400 void ProblemSummaryPrinter::operator()() 0401 { 0402 if (KDevPG::globalSystem.conflictHandling != KDevPG::World::Ignore) 0403 checkOut << (mFirstFirstConflictCount + mFirstFollowConflictCount) 0404 << " conflicts total: " << mFirstFollowConflictCount 0405 << " FIRST/FOLLOW conflicts, " << mFirstFirstConflictCount 0406 << " FIRST/FIRST conflicts." << endl; 0407 0408 if (mErrorCount > 0) 0409 { 0410 checkOut << mErrorCount << " fatal errors found, exiting." 0411 << endl; 0412 exit(EXIT_FAILURE); 0413 } 0414 0415 if (KDevPG::globalSystem.conflictHandling == KDevPG::World::Strict && mFirstFirstConflictCount + mFirstFollowConflictCount > 0) 0416 { 0417 checkOut << "Conflicts found, exiting." 0418 << endl; 0419 exit(EXIT_FAILURE); 0420 } 0421 } 0422 0423 void ProblemSummaryPrinter::reportFirstFirstConflict() 0424 { 0425 ++mFirstFirstConflictCount; 0426 } 0427 0428 void ProblemSummaryPrinter::reportFirstFollowConflict() 0429 { 0430 ++mFirstFollowConflictCount; 0431 } 0432 0433 void ProblemSummaryPrinter::reportError() 0434 { 0435 ++mErrorCount; 0436 } 0437 0438 } 0439 0440 // kate: space-indent on; indent-width 2; tab-width 2; show-tabs on;