File indexing completed on 2024-04-28 15:54:24
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) 2010 Jonathan Schmidt-Dominé <devel@the-user.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-first.h" 0023 0024 #include <cassert> 0025 0026 namespace KDevPG 0027 { 0028 0029 void initializeFirst() 0030 { 0031 globalSystem.first(globalSystem.zero()).insert(globalSystem.zero()); 0032 for(auto i = globalSystem.terminals.begin(); 0033 i != globalSystem.terminals.end(); 0034 ++i) 0035 { 0036 globalSystem.first(*i).insert(*i); 0037 } 0038 } 0039 0040 NextFirst::NextFirst(bool &changed): mChanged(changed) 0041 { 0042 } 0043 0044 void NextFirst::operator ()(Model::Node *node) 0045 { 0046 assert(nodeCast<Model::EvolveItem*>(node)); 0047 mMergeZeroBlocked = false; 0048 visitNode(node); 0049 } 0050 0051 bool NextFirst::blockZeroMerge(bool block) 0052 { 0053 bool old = mMergeZeroBlocked; 0054 mMergeZeroBlocked = block; 0055 return old; 0056 } 0057 0058 void NextFirst::merge(Model::Node *__dest, Model::Node *__source, int K) 0059 { 0060 if(__source == nullptr || __dest == nullptr) 0061 return; 0062 0063 World::NodeSet &dest = globalSystem.first(__dest, K); 0064 World::NodeSet &source = globalSystem.first(__source, K); 0065 0066 for (World::NodeSet::iterator it = source.begin(); it != source.end(); ++it) 0067 { 0068 if (mMergeZeroBlocked && nodeCast<Model::ZeroItem*>(*it)) 0069 { 0070 continue; 0071 } 0072 if( !dest.contains(*it) ) 0073 { 0074 dest.insert(*it); 0075 mChanged = true; 0076 } 0077 } 0078 } 0079 0080 void NextFirst::visitNode(Model::Node *node) 0081 { 0082 if(node == nullptr) 0083 return; 0084 0085 if(mVisited.contains(node)) 0086 return; 0087 0088 mVisited.insert(node); 0089 0090 DefaultVisitor::visitNode(node); 0091 0092 mVisited.remove(node); 0093 } 0094 0095 void NextFirst::visitAlternative(Model::AlternativeItem *node) 0096 { 0097 DefaultVisitor::visitAlternative(node); 0098 0099 merge(node, node->mLeft); 0100 merge(node, node->mRight); 0101 } 0102 0103 void NextFirst::visitCons(Model::ConsItem *node) 0104 { 0105 visitNode(node->mRight); 0106 0107 bool zero_blocked = mMergeZeroBlocked; 0108 if (!reducesToEpsilon(node->mRight)) 0109 zero_blocked = blockZeroMerge(true); 0110 0111 visitNode(node->mLeft); 0112 merge(node, node->mLeft); 0113 0114 if (reducesToEpsilon(node->mLeft)) 0115 { 0116 visitNode(node->mRight); 0117 merge(node, node->mRight); 0118 } 0119 0120 blockZeroMerge(zero_blocked); 0121 } 0122 0123 void computeFirst() // the closure of the FIRST sets 0124 { 0125 initializeFirst(); 0126 0127 bool changed = true; 0128 NextFirst next(changed); 0129 while (changed) 0130 { 0131 changed = false; 0132 for(QList<Model::EvolveItem*>::iterator it = globalSystem.rules.begin(); it != globalSystem.rules.end(); ++it) 0133 { 0134 next(*it); 0135 } 0136 } 0137 } 0138 0139 }