2 * Copyright 2001-2006 Adrian Thurston <thurston@cs.queensu.ca>
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
35 #include "parsetree.h"
45 struct FactorWithLabel;
56 typedef DList<LongestMatch> LmList;
59 /* Graph dictionary. */
62 public AvlTreeEl<GraphDictEl>,
63 public DListEl<GraphDictEl>
65 GraphDictEl( char *k )
66 : key(k), value(0), isInstance(false) { }
67 GraphDictEl( char *k, VarDef *value )
68 : key(k), value(value), isInstance(false) { }
70 const char *getKey() { return key; }
76 /* Location info of graph definition. Points to variable name of assignment. */
80 typedef AvlTree<GraphDictEl, char*, CmpStr> GraphDict;
81 typedef DList<GraphDictEl> GraphList;
83 /* Priority name dictionary. */
84 typedef AvlMapEl<char*, int> PriorDictEl;
85 typedef AvlMap<char*, int, CmpStr> PriorDict;
87 /* Local error name dictionary. */
88 typedef AvlMapEl<char*, int> LocalErrDictEl;
89 typedef AvlMap<char*, int, CmpStr> LocalErrDict;
91 /* Tree of instantiated names. */
92 typedef BstMapEl<char*, NameInst*> NameMapEl;
93 typedef BstMap<char*, NameInst*, CmpStr> NameMap;
94 typedef Vector<NameInst*> NameVect;
95 typedef BstSet<NameInst*> NameSet;
97 /* Node in the tree of instantiated names. */
100 NameInst( const InputLoc &loc, NameInst *parent, char *name, int id, bool isLabel ) :
101 loc(loc), parent(parent), name(name), id(id), isLabel(isLabel),
102 isLongestMatch(false), numRefs(0), numUses(0), start(0), final(0) {}
106 /* Keep parent pointers in the name tree to retrieve
107 * fully qulified names. */
118 /* Names underneath us, excludes anonymous names. */
121 /* All names underneath us in order of appearance. */
124 /* Join scopes need an implicit "final" target. */
125 NameInst *start, *final;
127 /* During a fsm generation walk, lists the names that are referenced by
128 * epsilon operations in the current scope. After the link is made by the
129 * epsilon reference and the join operation is complete, the label can
130 * have its refcount decremented. Once there are no more references the
131 * entry point can be removed from the fsm returned. */
132 NameVect referencedNames;
134 /* Pointers for the name search queue. */
135 NameInst *prev, *next;
137 /* Check if this name inst or any name inst below is referenced. */
141 typedef DList<NameInst> NameInstList;
143 /* Stack frame used in walking the name tree. */
146 NameInst *prevNameInst;
148 NameInst *prevLocalScope;
151 /* Class to collect information about the machine during the
155 /* Create a new parse data object. This is done at the beginning of every
156 * fsm specification. */
157 ParseData( char *fileName, char *sectionName, const InputLoc §ionLoc );
161 * Setting up the graph dict.
164 /* Initialize a graph dict with the basic fsms. */
165 void initGraphDict();
166 void createBuiltin( char *name, BuiltinMachine builtin );
168 /* Make a name id in the current name instantiation scope if it is not
170 NameInst *addNameInst( const InputLoc &loc, char *data, bool isLabel );
171 void makeRootNames();
172 void makeNameTree( GraphDictEl *gdNode );
173 void makeExportsNameTree();
174 void fillNameIndex( NameInst *from );
175 void printNameTree();
177 /* Increments the usage count on entry names. Names that are no longer
178 * needed will have their entry points unset. */
179 void unsetObsoleteEntries( FsmAp *graph );
181 /* Resove name references in action code and epsilon transitions. */
182 NameSet resolvePart( NameInst *refFrom, char *data, bool recLabelsOnly );
183 void resolveFrom( NameSet &result, NameInst *refFrom,
184 const NameRef &nameRef, int namePos );
185 NameInst *resolveStateRef( const NameRef &nameRef, InputLoc &loc, Action *action );
186 void resolveNameRefs( InlineList *inlineList, Action *action );
187 void resolveActionNameRefs();
189 /* Set the alphabet type. If type types are not valid returns false. */
190 bool setAlphType( const InputLoc &loc, char *s1, char *s2 );
191 bool setAlphType( const InputLoc &loc, char *s1 );
193 /* Override one of the variables ragel uses. */
194 bool setVariable( char *var, InlineList *inlineList );
196 /* Unique actions. */
197 void removeDups( ActionTable &actionTable );
198 void removeActionDups( FsmAp *graph );
200 /* Dumping the name instantiation tree. */
201 void printNameInst( NameInst *nameInst, int level );
203 /* Make the graph from a graph dict node. Does minimization. */
204 FsmAp *makeInstance( GraphDictEl *gdNode );
205 FsmAp *makeSpecific( GraphDictEl *gdNode );
208 /* Checking the contents of actions. */
209 void checkAction( Action *action );
210 void checkInlineList( Action *act, InlineList *inlineList );
212 void analyzeAction( Action *action, InlineList *inlineList );
213 void analyzeGraph( FsmAp *graph );
216 void prepareMachineGen( GraphDictEl *graphDictEl );
217 void prepareMachineGenTBWrapped( GraphDictEl *graphDictEl );
218 void generateXML( ostream &out );
220 bool generatingSectionSubset;
225 * Data collected during the parse.
228 /* Dictionary of graphs. Both instances and non-instances go here. */
231 /* The list of instances. */
232 GraphList instanceList;
234 /* Dictionary of actions. Lets actions be defined and then referenced. */
235 ActionDict actionDict;
237 /* Dictionary of named priorities. */
240 /* Dictionary of named local errors. */
241 LocalErrDict localErrDict;
243 /* List of actions. Will be pasted into a switch statement. */
244 ActionList actionList;
246 /* The id of the next priority name and label. */
247 int nextPriorKey, nextLocalErrKey, nextNameId, nextCondId;
249 /* The default priority number key for a machine. This is active during
250 * the parse of the rhs of a machine assignment. */
253 int curDefLocalErrKey;
256 HostType *userAlphType;
258 InputLoc alphTypeLoc;
260 /* Element type and get key expression. */
261 InlineList *getKeyExpr;
262 InlineList *accessExpr;
264 /* Overriding variables. */
269 InlineList *stackExpr;
271 InlineList *tokstartExpr;
272 InlineList *tokendExpr;
273 InlineList *dataExpr;
275 /* The alphabet range. */
276 char *lowerNum, *upperNum;
278 InputLoc rangeLowLoc, rangeHighLoc;
280 /* The name of the file the fsm is from, and the spec name. */
285 /* Counting the action and priority ordering. */
289 /* Root of the name tree. One root is for the instantiated machines. The
290 * other root is for exported definitions. */
292 NameInst *exportsRootName;
294 /* Name tree walking. */
295 NameInst *curNameInst;
298 /* The place where resolved epsilon transitions go. These cannot go into
299 * the parse tree because a single epsilon op can resolve more than once
300 * to different nameInsts if the machine it's in is used more than once. */
301 NameVect epsilonResolvedLinks;
302 int nextEpsilonResolvedLink;
304 /* Root of the name tree used for doing local name searches. */
305 NameInst *localNameScope;
307 void setLmInRetLoc( InlineList *inlineList );
308 void initLongestMatchData();
309 void setLongestMatchData( FsmAp *graph );
311 void initExportsNameWalk();
312 NameInst *nextNameScope() { return curNameInst->childVect[curNameChild]; }
313 NameFrame enterNameScope( bool isLocal, int numScopes );
314 void popNameScope( const NameFrame &frame );
315 void resetNameScope( const NameFrame &frame );
317 /* Make name ids to name inst pointers. */
318 NameInst **nameIndex;
320 /* Counter for assigning ids to longest match items. */
321 int nextLongestMatchId;
322 bool lmRequiresErrorState;
324 /* List of all longest match parse tree items. */
327 Action *newAction( char *name, InlineList *inlineList );
329 Action *initTokStart;
341 void beginProcessing()
343 ::condData = &thisCondData;
344 ::keyOps = &thisKeyOps;
347 CondData thisCondData;
350 ExportList exportList;
353 void afterOpMinimize( FsmAp *fsm, bool lastInSeq = true );
354 Key makeFsmKeyHex( char *str, const InputLoc &loc, ParseData *pd );
355 Key makeFsmKeyDec( char *str, const InputLoc &loc, ParseData *pd );
356 Key makeFsmKeyNum( char *str, const InputLoc &loc, ParseData *pd );
357 Key makeFsmKeyChar( char c, ParseData *pd );
358 void makeFsmKeyArray( Key *result, char *data, int len, ParseData *pd );
359 void makeFsmUniqueKeyArray( KeySet &result, char *data, int len,
360 bool caseInsensitive, ParseData *pd );
361 FsmAp *makeBuiltin( BuiltinMachine builtin, ParseData *pd );
362 FsmAp *dotFsm( ParseData *pd );
363 FsmAp *dotStarFsm( ParseData *pd );
365 void errorStateLabels( const NameSet &locations );
367 /* Data used by the parser specific to the current file. Supports the include
368 * system, since a new parser is executed for each included file. */
371 InputData( char *fileName, char *includeSpec, char *includeTo ) :
372 pd(0), sectionName(0), defaultParseData(0),
373 first_line(1), first_column(1),
374 last_line(1), last_column(0),
375 fileName(fileName), includeSpec(includeSpec),
376 includeTo(includeTo), active(true)
379 /* For collecting a name references. */
381 NameRefList nameRefList;
383 /* The parse data. For each fsm spec, the parser collects things that it parses
384 * in data structures in here. */
388 ParseData *defaultParseData;
397 /* If this is an included file, this contains the specification to search
398 * for. IncludeTo will contain the spec name that does the includng. */
408 typedef AvlMap<char*, Parser *, CmpStr> ParserDict;
409 typedef AvlMapEl<char*, Parser *> ParserDictEl;
411 extern ParserDict parserDict;
414 #endif /* _PARSEDATA_H */