2 * Copyright 2001-2008 Adrian Thurston <thurston@complang.org>
5 /* This file is part of Ragel.
7 * Ragel 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.
12 * Ragel 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.
17 * You should have received a copy of the GNU General Public License
18 * along with Ragel; if not, write to the Free Software
19 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
36 #include "parsetree.h"
46 struct FactorWithLabel;
58 typedef DList<LongestMatch> LmList;
61 /* Graph dictionary. */
64 public AvlTreeEl<GraphDictEl>,
65 public DListEl<GraphDictEl>
67 GraphDictEl( const char *k )
68 : key(k), value(0), isInstance(false) { }
69 GraphDictEl( const char *k, VarDef *value )
70 : key(k), value(value), isInstance(false) { }
72 const char *getKey() { return key; }
78 /* Location info of graph definition. Points to variable name of assignment. */
82 typedef AvlTree<GraphDictEl, const char*, CmpStr> GraphDict;
83 typedef DList<GraphDictEl> GraphList;
85 /* Priority name dictionary. */
86 typedef AvlMapEl<char*, int> PriorDictEl;
87 typedef AvlMap<char*, int, CmpStr> PriorDict;
89 /* Local error name dictionary. */
90 typedef AvlMapEl<const char*, int> LocalErrDictEl;
91 typedef AvlMap<const char*, int, CmpStr> LocalErrDict;
93 /* Tree of instantiated names. */
94 typedef BstMapEl<const char*, NameInst*> NameMapEl;
95 typedef BstMap<const char*, NameInst*, CmpStr> NameMap;
96 typedef Vector<NameInst*> NameVect;
97 typedef BstSet<NameInst*> NameSet;
99 /* Node in the tree of instantiated names. */
102 NameInst( const InputLoc &loc, NameInst *parent, const char *name, int id, bool isLabel ) :
103 loc(loc), parent(parent), name(name), id(id), isLabel(isLabel),
104 isLongestMatch(false), numRefs(0), numUses(0), start(0), final(0) {}
108 /* Keep parent pointers in the name tree to retrieve
109 * fully qulified names. */
120 /* Names underneath us, excludes anonymous names. */
123 /* All names underneath us in order of appearance. */
126 /* Join scopes need an implicit "final" target. */
127 NameInst *start, *final;
129 /* During a fsm generation walk, lists the names that are referenced by
130 * epsilon operations in the current scope. After the link is made by the
131 * epsilon reference and the join operation is complete, the label can
132 * have its refcount decremented. Once there are no more references the
133 * entry point can be removed from the fsm returned. */
134 NameVect referencedNames;
136 /* Pointers for the name search queue. */
137 NameInst *prev, *next;
139 /* Check if this name inst or any name inst below is referenced. */
143 typedef DList<NameInst> NameInstList;
145 /* Stack frame used in walking the name tree. */
148 NameInst *prevNameInst;
150 NameInst *prevLocalScope;
153 /* Class to collect information about the machine during the
157 /* Create a new parse data object. This is done at the beginning of every
158 * fsm specification. */
159 ParseData( const char *fileName, char *sectionName, const InputLoc §ionLoc );
163 * Setting up the graph dict.
166 /* Initialize a graph dict with the basic fsms. */
167 void initGraphDict();
168 void createBuiltin( const char *name, BuiltinMachine builtin );
170 /* Make a name id in the current name instantiation scope if it is not
172 NameInst *addNameInst( const InputLoc &loc, const char *data, bool isLabel );
173 void makeRootNames();
174 void makeNameTree( GraphDictEl *gdNode );
175 void makeExportsNameTree();
176 void fillNameIndex( NameInst *from );
177 void printNameTree();
179 /* Increments the usage count on entry names. Names that are no longer
180 * needed will have their entry points unset. */
181 void unsetObsoleteEntries( FsmAp *graph );
183 /* Resove name references in action code and epsilon transitions. */
184 NameSet resolvePart( NameInst *refFrom, const char *data, bool recLabelsOnly );
185 void resolveFrom( NameSet &result, NameInst *refFrom,
186 const NameRef &nameRef, int namePos );
187 NameInst *resolveStateRef( const NameRef &nameRef, InputLoc &loc, Action *action );
188 void resolveNameRefs( InlineList *inlineList, Action *action );
189 void resolveActionNameRefs();
191 /* Set the alphabet type. If type types are not valid returns false. */
192 bool setAlphType( const InputLoc &loc, char *s1, char *s2 );
193 bool setAlphType( const InputLoc &loc, char *s1 );
195 /* Override one of the variables ragel uses. */
196 bool setVariable( char *var, InlineList *inlineList );
198 /* Unique actions. */
199 void removeDups( ActionTable &actionTable );
200 void removeActionDups( FsmAp *graph );
202 /* Dumping the name instantiation tree. */
203 void printNameInst( NameInst *nameInst, int level );
205 /* Make the graph from a graph dict node. Does minimization. */
206 FsmAp *makeInstance( GraphDictEl *gdNode );
207 FsmAp *makeSpecific( GraphDictEl *gdNode );
210 /* Checking the contents of actions. */
211 void checkAction( Action *action );
212 void checkInlineList( Action *act, InlineList *inlineList );
214 void analyzeAction( Action *action, InlineList *inlineList );
215 void analyzeGraph( FsmAp *graph );
218 void prepareMachineGen( GraphDictEl *graphDictEl );
219 void prepareMachineGenTBWrapped( GraphDictEl *graphDictEl );
220 void generateXML( ostream &out );
221 void generateReduced( InputData &inputData );
223 bool generatingSectionSubset;
228 * Data collected during the parse.
231 /* Dictionary of graphs. Both instances and non-instances go here. */
234 /* The list of instances. */
235 GraphList instanceList;
237 /* Dictionary of actions. Lets actions be defined and then referenced. */
238 ActionDict actionDict;
240 /* Dictionary of named priorities. */
243 /* Dictionary of named local errors. */
244 LocalErrDict localErrDict;
246 /* List of actions. Will be pasted into a switch statement. */
247 ActionList actionList;
249 /* The id of the next priority name and label. */
250 int nextPriorKey, nextLocalErrKey, nextNameId, nextCondId;
252 /* The default priority number key for a machine. This is active during
253 * the parse of the rhs of a machine assignment. */
256 int curDefLocalErrKey;
259 HostType *userAlphType;
261 InputLoc alphTypeLoc;
263 /* Element type and get key expression. */
264 InlineList *getKeyExpr;
265 InlineList *accessExpr;
267 /* Stack management */
268 InlineList *prePushExpr;
269 InlineList *postPopExpr;
271 /* Overriding variables. */
277 InlineList *stackExpr;
279 InlineList *tokstartExpr;
280 InlineList *tokendExpr;
281 InlineList *dataExpr;
283 /* The alphabet range. */
284 char *lowerNum, *upperNum;
286 InputLoc rangeLowLoc, rangeHighLoc;
288 /* The name of the file the fsm is from, and the spec name. */
289 const char *fileName;
293 /* Counting the action and priority ordering. */
297 /* Root of the name tree. One root is for the instantiated machines. The
298 * other root is for exported definitions. */
300 NameInst *exportsRootName;
302 /* Name tree walking. */
303 NameInst *curNameInst;
306 /* The place where resolved epsilon transitions go. These cannot go into
307 * the parse tree because a single epsilon op can resolve more than once
308 * to different nameInsts if the machine it's in is used more than once. */
309 NameVect epsilonResolvedLinks;
310 int nextEpsilonResolvedLink;
312 /* Root of the name tree used for doing local name searches. */
313 NameInst *localNameScope;
315 void setLmInRetLoc( InlineList *inlineList );
316 void initLongestMatchData();
317 void setLongestMatchData( FsmAp *graph );
319 void initExportsNameWalk();
320 NameInst *nextNameScope() { return curNameInst->childVect[curNameChild]; }
321 NameFrame enterNameScope( bool isLocal, int numScopes );
322 void popNameScope( const NameFrame &frame );
323 void resetNameScope( const NameFrame &frame );
325 /* Make name ids to name inst pointers. */
326 NameInst **nameIndex;
328 /* Counter for assigning ids to longest match items. */
329 int nextLongestMatchId;
330 bool lmRequiresErrorState;
332 /* List of all longest match parse tree items. */
335 Action *newAction( const char *name, InlineList *inlineList );
337 Action *initTokStart;
349 void beginProcessing()
351 ::condData = &thisCondData;
352 ::keyOps = &thisKeyOps;
355 CondData thisCondData;
358 ExportList exportList;
361 void afterOpMinimize( FsmAp *fsm, bool lastInSeq = true );
362 Key makeFsmKeyHex( char *str, const InputLoc &loc, ParseData *pd );
363 Key makeFsmKeyDec( char *str, const InputLoc &loc, ParseData *pd );
364 Key makeFsmKeyNum( char *str, const InputLoc &loc, ParseData *pd );
365 Key makeFsmKeyChar( char c, ParseData *pd );
366 void makeFsmKeyArray( Key *result, char *data, int len, ParseData *pd );
367 void makeFsmUniqueKeyArray( KeySet &result, char *data, int len,
368 bool caseInsensitive, ParseData *pd );
369 FsmAp *makeBuiltin( BuiltinMachine builtin, ParseData *pd );
370 FsmAp *dotFsm( ParseData *pd );
371 FsmAp *dotStarFsm( ParseData *pd );
373 void errorStateLabels( const NameSet &locations );
383 std::ostringstream data;
385 Vector<char *> writeArgs;
389 InputItem *prev, *next;
398 typedef AvlMap<char*, Parser *, CmpStr> ParserDict;
399 typedef AvlMapEl<char*, Parser *> ParserDictEl;
401 typedef DList<InputItem> InputItemList;
403 extern ParserDict parserDict;
404 extern InputItemList inputItems;