1 /* This file is part of kdev-pg-qt
2 Copyright (C) 2005 Roberto Raggi <roberto@kdevelop.org>
3 Copyright (C) 2006 Jakob Petsovits <jpetso@gmx.at>
4 Copyright (C) 2006 Alexander Dymo <adymo@kdevelop.org>
5 Copyright (C) 2010 Jonathan Schmidt-Dominé <devel@the-user.org>
6
7 This library is free software; you can redistribute it and/or
8 modify it under the terms of the GNU Library General Public
9 License as published by the Free Software Foundation; either
10 version 2 of the License, or (at your option) any later version.
11
12 This library 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 GNU
15 Library General Public License for more details.
16
17 You should have received a copy of the GNU Library General Public License
18 along with this library; see the file COPYING.LIB. If not, write to
19 the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
20 Boston, MA 02110-1301, USA.
21 */
22
23 #include "kdev-pg-follow.h"
24 #include "kdev-pg-pretty-printer.h"
25
26 #include <QTextStream>
27
28 //uncomment this to see debug output for follow dependency calculation
29 // #define followDepsEP_DEBUG
30
31 /*
32 * Computing LL(k)-follow-sets
33 */
34
35 namespace KDevPG
36 {
37
38 extern QTextStream checkOut;
39
40 #ifdef FOLLOWDEP_DEBUG
DebugFollowDep(Model::Node * dest,Model::Node * dep,const QString & message)41 void DebugFollowDep(Model::Node *dest, Model::Node *dep, const QString &message)
42 {
43 checkOut << "=============================" << endl;
44 PrettyPrinter p(QTextStream( stderr ));
45 checkOut << "adding " << message << " ";
46 p(dep);
47 checkOut << " (" << (uint*)dep << ")";
48 checkOut << " to follow ";
49 p(dest);
50 checkOut << " (" << (uint*)dest << ")";
51 checkOut << "{" << dest->kind << "}";
52 if (dest->kind == Model::Node_kind_nonTerminal)
53 {
54 Model::SymbolItem *s = ((Model::NonTerminalItem*)dest)->mSymbol;
55 if (s)
56 checkOut << "__"; p(s); checkOut << "__";
57 }
58 checkOut << endl;
59 }
60
debugFirstToFollowDep(Model::Node * dest,Model::Node * dep)61 void debugFirstToFollowDep(Model::Node *dest, Model::Node *dep)
62 {
63 DebugFollowDep(dest, dep, "first");
64 }
65
debugFollowToFollowDep(Model::Node * dest,Model::Node * dep)66 void debugFollowToFollowDep(Model::Node *dest, Model::Node *dep)
67 {
68 DebugFollowDep(dest, dep, "follow");
69 }
70 #endif
71
72 //
73 // Calculating the FOLLOW set depends on the first set being already available
74 // and is in principle quite easy. There are only a few simple rules:
75 //
76 // 1. Put EOF at the end of the start rule
77 // 2. For every rule "items -> rulename", put FOLLOW(rulename) into FOLLOW(items)
78 // 3. For every item sequence "item1 item2", put first(item2) into FOLLOW(item1)
79 // 4. For every rule "item1 item2 -> rulename", put FOLLOW(rulename)
80 // into FOLLOW(item1) if item2 can derive to epsilon ("0").
81 // 5. Propagate the FOLLOW sets down to the symbols where appropriate.
82 // 6. Loop for all rules until there are no changes in any FOLLOW set anymore.
83 //
84
NextFollow(bool & changed)85 NextFollow::NextFollow(bool &changed)
86 : mChanged(changed)
87 {
88 Model::TerminalItem *teof = globalSystem.pushTerminal("EOF", "end of file");
89 for(auto i = globalSystem.rules.begin(); i != globalSystem.rules.end(); ++i)
90 {
91 if(globalSystem.start.contains((*i)->mSymbol))
92 {
93 globalSystem.follow(*i).insert(teof);
94 globalSystem.follow((*i)->mSymbol).insert(teof);
95 globalSystem.follow((*i)->mItem).insert(teof);
96 }
97 }
98 }
99
operator ()(Model::Node * node)100 void NextFollow::operator()(Model::Node *node)
101 {
102 Model::EvolveItem *e = nodeCast<Model::EvolveItem*>(node);
103 Q_ASSERT(e != nullptr);
104 mSymbol = e->mSymbol;
105 visitNode(node);
106 }
107
merge(Model::Node * __dest,World::NodeSet const & source)108 void NextFollow::merge(Model::Node*__dest, World::NodeSet const &source)
109 {
110 if (nodeCast<Model::ZeroItem*>(__dest) != nullptr
111 || nodeCast<Model::TerminalItem*>(__dest) != nullptr)
112 {
113 return;
114 }
115
116 World::NodeSet &dest = globalSystem.follow(__dest);
117
118 for (World::NodeSet::const_iterator it = source.begin(); it != source.end(); ++it)
119 {
120 if (Model::TerminalItem *t = nodeCast<Model::TerminalItem*>(*it))
121 {
122 if( !dest.contains(t) )
123 {
124 mChanged = true;
125 dest.insert(t);
126 }
127 }
128 }
129 }
130
visitCons(Model::ConsItem * node)131 void NextFollow::visitCons(Model::ConsItem *node)
132 {
133 merge(node->mRight, globalSystem.follow(node));
134 addFollowToFollowDep(node->mRight, node);
135
136 merge(node->mLeft, globalSystem.first(node->mRight));
137 addFirstToFollowDep(node->mLeft, node->mRight);
138
139 if (reducesToEpsilon(node->mRight))
140 {
141 merge(node->mLeft, globalSystem.follow(node));
142 addFollowToFollowDep(node->mLeft, node);
143 }
144
145 DefaultVisitor::visitCons(node);
146 }
147
visitAlternative(Model::AlternativeItem * node)148 void NextFollow::visitAlternative(Model::AlternativeItem *node)
149 {
150 merge(node->mLeft, globalSystem.follow(node));
151 addFollowToFollowDep(node->mLeft, node);
152 merge(node->mRight, globalSystem.follow(node));
153 addFollowToFollowDep(node->mRight, node);
154
155 DefaultVisitor::visitAlternative(node);
156 }
157
visitNode(Model::Node * node)158 void NextFollow::visitNode(Model::Node* node)
159 {
160 if(node == nullptr)
161 return;
162
163 if(mVisited.contains(node))
164 return;
165
166 mVisited.insert(node);
167
168 KDevPG::Visitor::visitNode(node);
169
170 mVisited.remove(node);
171 }
172
preCopy(Model::Node * from,Model::Node * to)173 void NextFollow::preCopy(Model::Node* from, Model::Node* to)
174 {
175 if(from != nullptr && to != nullptr)
176 {
177 merge(from, globalSystem.follow(to));
178 addFollowToFollowDep(from, to);
179 }
180 }
181
copy(Model::Node * from,Model::Node * to)182 void NextFollow::copy(Model::Node* from, Model::Node* to)
183 {
184 Q_UNUSED(from);
185 Q_UNUSED(to);
186 }
187
addFirstToFollowDep(Model::Node * dest,Model::Node * dep)188 void NextFollow::addFirstToFollowDep(Model::Node *dest, Model::Node *dep)
189 {
190 if (dest->kind == Model::NodeKindNonTerminal)
191 {
192 Model::SymbolItem *s = nodeCast<Model::NonTerminalItem*>(dest)->mSymbol;
193 if (s)
194 globalSystem.followDep(s).first.insert(dep);
195 }
196 else
197 globalSystem.followDep(dest).first.insert(dep);
198 #ifdef FOLLOWDEP_DEBUG
199 debugFirstToFollowDep(dest, dep);
200 #endif
201 }
202
addFollowToFollowDep(Model::Node * dest,Model::Node * dep)203 void NextFollow::addFollowToFollowDep(Model::Node *dest, Model::Node *dep)
204 {
205 if (dest->kind == Model::NodeKindNonTerminal)
206 {
207 Model::SymbolItem *s = nodeCast<Model::NonTerminalItem*>(dest)->mSymbol;
208 if (s)
209 globalSystem.followDep(s).second.insert(dep);
210 }
211 else
212 globalSystem.followDep(dest).second.insert(dep);
213 #ifdef FOLLOWDEP_DEBUG
214 debugFollowToFollowDep(dest, dep);
215 #endif
216 }
217
computeFollow()218 void computeFollow()
219 {
220 bool changed = true;
221 NextFollow next(changed);
222 while (true)
223 {
224 for(QList<Model::EvolveItem*>::iterator it = globalSystem.rules.begin(); it != globalSystem.rules.end(); ++it)
225 {
226 next(*it);
227 }
228 if(!changed) // for the eof in the first iteration
229 break;
230 changed = false;
231 }
232 }
233
234 }
235
236 // kate: space-indent on; indent-width 2; tab-width 2; show-tabs on;
237