2 * Copyright 2001-2006 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;
57 typedef DList<LongestMatch> LmList;
60 /* Graph dictionary. */
63 public AvlTreeEl<GraphDictEl>,
64 public DListEl<GraphDictEl>
66 GraphDictEl( const char *k )
67 : key(k), value(0), isInstance(false) { }
68 GraphDictEl( const char *k, VarDef *value )
69 : key(k), value(value), isInstance(false) { }
71 const char *getKey() { return key; }
77 /* Location info of graph definition. Points to variable name of assignment. */
81 typedef AvlTree<GraphDictEl, const char*, CmpStr> GraphDict;
82 typedef DList<GraphDictEl> GraphList;
84 /* Priority name dictionary. */
85 typedef AvlMapEl<char*, int> PriorDictEl;
86 typedef AvlMap<char*, int, CmpStr> PriorDict;
88 /* Local error name dictionary. */
89 typedef AvlMapEl<const char*, int> LocalErrDictEl;
90 typedef AvlMap<const char*, int, CmpStr> LocalErrDict;
92 /* Tree of instantiated names. */
93 typedef BstMapEl<const char*, NameInst*> NameMapEl;
94 typedef BstMap<const char*, NameInst*, CmpStr> NameMap;
95 typedef Vector<NameInst*> NameVect;
96 typedef BstSet<NameInst*> NameSet;
98 /* Node in the tree of instantiated names. */
101 NameInst( const InputLoc &loc, NameInst *parent, const char *name, int id, bool isLabel ) :
102 loc(loc), parent(parent), name(name), id(id), isLabel(isLabel),
103 isLongestMatch(false), numRefs(0), numUses(0), start(0), final(0) {}
107 /* Keep parent pointers in the name tree to retrieve
108 * fully qulified names. */
119 /* Names underneath us, excludes anonymous names. */
122 /* All names underneath us in order of appearance. */
125 /* Join scopes need an implicit "final" target. */
126 NameInst *start, *final;
128 /* During a fsm generation walk, lists the names that are referenced by
129 * epsilon operations in the current scope. After the link is made by the
130 * epsilon reference and the join operation is complete, the label can
131 * have its refcount decremented. Once there are no more references the
132 * entry point can be removed from the fsm returned. */
133 NameVect referencedNames;
135 /* Pointers for the name search queue. */
136 NameInst *prev, *next;
138 /* Check if this name inst or any name inst below is referenced. */
142 typedef DList<NameInst> NameInstList;
144 /* Stack frame used in walking the name tree. */
147 NameInst *prevNameInst;
149 NameInst *prevLocalScope;
152 /* Class to collect information about the machine during the
156 /* Create a new parse data object. This is done at the beginning of every
157 * fsm specification. */
158 ParseData( const char *fileName, char *sectionName, const InputLoc §ionLoc );
162 * Setting up the graph dict.
165 /* Initialize a graph dict with the basic fsms. */
166 void initGraphDict();
167 void createBuiltin( const char *name, BuiltinMachine builtin );
169 /* Make a name id in the current name instantiation scope if it is not
171 NameInst *addNameInst( const InputLoc &loc, const char *data, bool isLabel );
172 void makeRootNames();
173 void makeNameTree( GraphDictEl *gdNode );
174 void makeExportsNameTree();
175 void fillNameIndex( NameInst *from );
176 void printNameTree();
178 /* Increments the usage count on entry names. Names that are no longer
179 * needed will have their entry points unset. */
180 void unsetObsoleteEntries( FsmAp *graph );
182 /* Resove name references in action code and epsilon transitions. */
183 NameSet resolvePart( NameInst *refFrom, const char *data, bool recLabelsOnly );
184 void resolveFrom( NameSet &result, NameInst *refFrom,
185 const NameRef &nameRef, int namePos );
186 NameInst *resolveStateRef( const NameRef &nameRef, InputLoc &loc, Action *action );
187 void resolveNameRefs( InlineList *inlineList, Action *action );
188 void resolveActionNameRefs();
190 /* Set the alphabet type. If type types are not valid returns false. */
191 bool setAlphType( const InputLoc &loc, char *s1, char *s2 );
192 bool setAlphType( const InputLoc &loc, char *s1 );
194 /* Override one of the variables ragel uses. */
195 bool setVariable( char *var, InlineList *inlineList );
197 /* Unique actions. */
198 void removeDups( ActionTable &actionTable );
199 void removeActionDups( FsmAp *graph );
201 /* Dumping the name instantiation tree. */
202 void printNameInst( NameInst *nameInst, int level );
204 /* Make the graph from a graph dict node. Does minimization. */
205 FsmAp *makeInstance( GraphDictEl *gdNode );
206 FsmAp *makeSpecific( GraphDictEl *gdNode );
209 /* Checking the contents of actions. */
210 void checkAction( Action *action );
211 void checkInlineList( Action *act, InlineList *inlineList );
213 void analyzeAction( Action *action, InlineList *inlineList );
214 void analyzeGraph( FsmAp *graph );
217 void prepareMachineGen( GraphDictEl *graphDictEl );
218 void prepareMachineGenTBWrapped( GraphDictEl *graphDictEl );
219 void generateXML( ostream &out, XmlParser &xmlParser );
220 void generateReduced( XmlParser &xmlParser );
222 bool generatingSectionSubset;
227 * Data collected during the parse.
230 /* Dictionary of graphs. Both instances and non-instances go here. */
233 /* The list of instances. */
234 GraphList instanceList;
236 /* Dictionary of actions. Lets actions be defined and then referenced. */
237 ActionDict actionDict;
239 /* Dictionary of named priorities. */
242 /* Dictionary of named local errors. */
243 LocalErrDict localErrDict;
245 /* List of actions. Will be pasted into a switch statement. */
246 ActionList actionList;
248 /* The id of the next priority name and label. */
249 int nextPriorKey, nextLocalErrKey, nextNameId, nextCondId;
251 /* The default priority number key for a machine. This is active during
252 * the parse of the rhs of a machine assignment. */
255 int curDefLocalErrKey;
258 HostType *userAlphType;
260 InputLoc alphTypeLoc;
262 /* Element type and get key expression. */
263 InlineList *getKeyExpr;
264 InlineList *accessExpr;
266 /* Stack management */
267 InlineList *prePushExpr;
268 InlineList *postPopExpr;
270 /* Overriding variables. */
276 InlineList *stackExpr;
278 InlineList *tokstartExpr;
279 InlineList *tokendExpr;
280 InlineList *dataExpr;
282 /* The alphabet range. */
283 char *lowerNum, *upperNum;
285 InputLoc rangeLowLoc, rangeHighLoc;
287 /* The name of the file the fsm is from, and the spec name. */
288 const char *fileName;
292 /* Counting the action and priority ordering. */
296 /* Root of the name tree. One root is for the instantiated machines. The
297 * other root is for exported definitions. */
299 NameInst *exportsRootName;
301 /* Name tree walking. */
302 NameInst *curNameInst;
305 /* The place where resolved epsilon transitions go. These cannot go into
306 * the parse tree because a single epsilon op can resolve more than once
307 * to different nameInsts if the machine it's in is used more than once. */
308 NameVect epsilonResolvedLinks;
309 int nextEpsilonResolvedLink;
311 /* Root of the name tree used for doing local name searches. */
312 NameInst *localNameScope;
314 void setLmInRetLoc( InlineList *inlineList );
315 void initLongestMatchData();
316 void setLongestMatchData( FsmAp *graph );
318 void initExportsNameWalk();
319 NameInst *nextNameScope() { return curNameInst->childVect[curNameChild]; }
320 NameFrame enterNameScope( bool isLocal, int numScopes );
321 void popNameScope( const NameFrame &frame );
322 void resetNameScope( const NameFrame &frame );
324 /* Make name ids to name inst pointers. */
325 NameInst **nameIndex;
327 /* Counter for assigning ids to longest match items. */
328 int nextLongestMatchId;
329 bool lmRequiresErrorState;
331 /* List of all longest match parse tree items. */
334 Action *newAction( const char *name, InlineList *inlineList );
336 Action *initTokStart;
348 void beginProcessing()
350 ::condData = &thisCondData;
351 ::keyOps = &thisKeyOps;
354 CondData thisCondData;
357 ExportList exportList;
360 void afterOpMinimize( FsmAp *fsm, bool lastInSeq = true );
361 Key makeFsmKeyHex( char *str, const InputLoc &loc, ParseData *pd );
362 Key makeFsmKeyDec( char *str, const InputLoc &loc, ParseData *pd );
363 Key makeFsmKeyNum( char *str, const InputLoc &loc, ParseData *pd );
364 Key makeFsmKeyChar( char c, ParseData *pd );
365 void makeFsmKeyArray( Key *result, char *data, int len, ParseData *pd );
366 void makeFsmUniqueKeyArray( KeySet &result, char *data, int len,
367 bool caseInsensitive, ParseData *pd );
368 FsmAp *makeBuiltin( BuiltinMachine builtin, ParseData *pd );
369 FsmAp *dotFsm( ParseData *pd );
370 FsmAp *dotStarFsm( ParseData *pd );
372 void errorStateLabels( const NameSet &locations );
382 std::ostringstream data;
384 Vector<char *> writeArgs;
388 InputItem *prev, *next;
397 typedef AvlMap<char*, Parser *, CmpStr> ParserDict;
398 typedef AvlMapEl<char*, Parser *> ParserDictEl;
400 typedef DList<InputItem> InputItemList;
402 extern ParserDict parserDict;
403 extern InputItemList inputItems;
405 #endif /* _PARSEDATA_H */