← Back to branch summary

~ubuntu-branches/ubuntu/wily/aspectc++/wily

« back to all changes in this revision

Viewing changes to Puma/tools/orange/orange.cc

  • Committer: Bazaar Package Importer
  • Author(s): Reinhard Tartler
  • Date: 2005-12-23 10:49:40 UTC
  • Revision ID: james.westby@ubuntu.com-20051223104940-ig4klhoi991zs7km
Tags: upstream-0.99+1.0pre2
Import upstream version 0.99+1.0pre2

Show diffs side-by-side

added added

removed removed

Lines of Context:
Puma/tools/orange/orange.cc
 
1
/* 
 
2
$Id: orange.cc,v 1.1.1.1 2003/07/02 16:32:07 matthias.urban Exp $
 
3
*/
 
4
/* 
 
5
$Log: orange.cc,v $
 
6
Revision 1.1.1.1  2003/07/02 16:32:07  matthias.urban
 
7
PUMA version 1.0 imported.
 
8
 
 
9
Revision 1.4  2002/05/08 14:06:35  murban
 
10
Several bugs fixed.
 
11
 
 
12
Revision 1.3  2002/01/21 09:03:33  olaf
 
13
made generated tables static
 
14
 
 
15
Revision 1.2  2001/03/30 11:44:52  olaf
 
16
added support for expression type mapping
 
17
 
 
18
Revision 1.1.1.1  2000/01/05 12:43:41  murban
 
19
New Puma repository created. Puma directory tree imported as initial version.
 
20
 
 
21
Revision 1.1  1999/08/26 10:38:55  olaf
 
22
Integration of the Orange scanner generator
 
23
 
 
24
Revision 1.3  1994/07/06 18:24:55  olaf
 
25
Bessere Formatierung.
 
26
 
 
27
 * Revision 1.2  1994/07/06  18:23:34  olaf
 
28
 * Einf�gen der RCS Id und Log Eintr�ge.
 
29
 *
 
30
*/
 
31
 
 
32
# include "scanner.h"
 
33
# include "symbol.h"
 
34
# include "charconst.h"
 
35
# include "classes.h"
 
36
# include "automaton.h"
 
37
# include "expr_names.h"
 
38
# include <stdio.h>
 
39
 
 
40
int  ParseSource (char*& Name, Automaton& Automaton, ExprNames& Exprs,
 
41
                  int& NumExprs);
 
42
int  ParseClasses (void);
 
43
int  ParseClassDef (CharSet& CharClass);
 
44
int  ParseTable (char*& Name, Automaton& Automaton, ExprNames& Exprs,
 
45
                 int& NumExprs);
 
46
int  ParseLookAheadExpr (Automaton& Automaton, int Expr);
 
47
int  ParseRegExpr (Automaton& Automaton);
 
48
int  ParseCatExprs (Automaton& Automaton);
 
49
int  ParseCatExpr (Automaton& Automaton);
 
50
int  ParseBasicExpr (Automaton& Automaton);
 
51
void ParsingError (char* Expected);
 
52
void NormalizeNFA (Automaton& Automaton);
 
53
void ConstructDFA (Automaton& NFA, Automaton& DFA, State **ExprTab);
 
54
void EpsilonClosure (List& States, List& Closure);
 
55
void Move (List& States, ClassId Id, List& Result);
 
56
void OptimizeDFA (Automaton& In, Automaton& Out,
 
57
                  State **ExprTab, int NumOfExprs);
 
58
int  PartitionGroup (List* Group, int& MaxGroup, List& Partitions);
 
59
int  InOneGroup (State* State1, State* State2);
 
60
void PrintCharMap (char *Name);
 
61
void SetStateNumbers (Automaton& Automaton);
 
62
void PrintExprTab (char* Name, Automaton& OptimizedDFA,
 
63
                   State **ExprTab, int NumOfExprs);
 
64
void PrintTransitionTable (char* Name, Automaton& Automaton);
 
65
int  MaxSize (State* State);
 
66
int PositionState (State* State, int *TransitionTab, int *ControlTab, 
 
67
                   int& End);
 
68
 
 
69
Token LookAhead;
 
70
 
 
71
int main (int argc, char **argv)
 
72
 { Automaton NFA, DFA, OptimizedDFA;
 
73
   ExprNames Exprs;
 
74
   char* Name;
 
75
   State **ExprTab;
 
76
   int NumOfExprs, CurrExpr;
 
77
   
 
78
   if (argc != 2)
 
79
    { printf ("usage: ttgen filename\n");
 
80
      return 1;
 
81
    }
 
82
   if (BeginScanning (argv[1]) == -1)
 
83
    { printf ("ttgen: unable to open source file %s.\n", argv[1]);
 
84
      return 1;
 
85
    }  
 
86
 
 
87
   NextToken(&LookAhead);
 
88
   if (ParseSource (Name, NFA, Exprs, NumOfExprs)== -1)
 
89
      return 1;
 
90
   ExprTab = new State*[NumOfExprs];
 
91
   for (CurrExpr = 0; CurrExpr < NumOfExprs; CurrExpr++)
 
92
      ExprTab[CurrExpr] = (State*)-1;
 
93
 
 
94
/*
 
95
   printf ("Map of Char Sets\n");
 
96
   PrintClasses ();
 
97
   printf ("\nRelationList\n");
 
98
   PrintRelationList ();
 
99
*/
 
100
   NormalizeNFA (NFA);
 
101
   ConstructDFA (NFA, DFA, ExprTab);
 
102
/*   DFA.Print (); */
 
103
   OptimizeDFA (DFA, OptimizedDFA, ExprTab, NumOfExprs);
 
104
/*   OptimizedDFA.Print (); */
 
105
   PrintCharMap (Name);
 
106
   Exprs.print (Name);
 
107
   SetStateNumbers (OptimizedDFA);
 
108
   PrintExprTab (Name, OptimizedDFA, ExprTab, NumOfExprs);
 
109
   PrintTransitionTable (Name, OptimizedDFA);
 
110
   delete[] ExprTab;
 
111
   DeleteAllSymbols ();
 
112
   EndScanning ();
 
113
   return 0;
 
114
 }
 
115
 
 
116
void ParsingError (char* Expected)
 
117
 { printf ("Parsing Error: expected ");
 
118
   printf (Expected);
 
119
   printf (" instead of ");
 
120
   switch (LookAhead.Type)
 
121
    { case NAME :
 
122
         printf ("Name %s", GetSymbolText (LookAhead.Index));
 
123
         break;
 
124
      case STRING :
 
125
         printf ("String \"%s\"", GetSymbolText (LookAhead.Index));
 
126
         break;
 
127
      case CHAR :
 
128
         printf ("Character \'%s\'", GetSymbolText (LookAhead.Index));
 
129
         break;
 
130
      case OPEN_BRACKET :
 
131
         printf ("\'(\'");
 
132
         break;
 
133
      case CLOSE_BRACKET :
 
134
         printf ("\')\'");
 
135
         break;
 
136
      case OPEN_SQUARE_BRACKET :
 
137
         printf ("\'[\'");
 
138
         break;
 
139
      case CLOSE_SQUARE_BRACKET :
 
140
         printf ("\']\'");
 
141
         break;
 
142
      case COLON :
 
143
         printf ("\':\'");
 
144
         break;
 
145
      case IS :
 
146
         printf ("\'=\'");
 
147
         break;
 
148
      case TO :
 
149
         printf ("\'-\'");
 
150
         break;
 
151
      case HASH_MARK :
 
152
         printf ("\'#\'");
 
153
         break;
 
154
      case MAP_TO :
 
155
         printf ("\'=>\'");
 
156
         break;
 
157
      case LOOK_AHEAD :
 
158
         printf ("\'/\'");
 
159
         break;
 
160
      case OR :
 
161
         printf ("\'|\'");
 
162
         break;
 
163
      case STAR :
 
164
         printf ("\'*\'");
 
165
         break;
 
166
      case PLUS :
 
167
         printf ("\'+\'");
 
168
         break;
 
169
      case EPSILON :
 
170
         printf ("\'E\'");
 
171
         break;
 
172
      case TABLE :
 
173
         printf ("\'TABLE\'");
 
174
         break;
 
175
      case CLASSES :
 
176
         printf ("\'CLASSES\'");
 
177
         break;
 
178
      case END :
 
179
         printf ("end of file");
 
180
         break;
 
181
      case ERROR :
 
182
         printf ("invalid token");
 
183
         break;
 
184
      default :
 
185
         printf ("unknown token");
 
186
         break;
 
187
    }
 
188
   printf (" at %02ld,%02ld.\n", 
 
189
           GetSymbolRow (LookAhead.Index),
 
190
           GetSymbolColumn (LookAhead.Index));
 
191
 }
 
192
 
 
193
 
 
194
int ParseSource (char*& Name, Automaton& Automaton, ExprNames& Exprs,
 
195
                 int& NumExprs)
 
196
 { 
 
197
   if (LookAhead.Type == CLASSES)
 
198
    { NextToken(&LookAhead);
 
199
      if (ParseClasses ()== -1)
 
200
         return -1;
 
201
    }
 
202
   if (LookAhead.Type == TABLE)
 
203
    { NextToken(&LookAhead);
 
204
      if (ParseTable (Name, Automaton, Exprs, NumExprs) == -1)
 
205
         return -1;
 
206
    }
 
207
   if (LookAhead.Type != END)
 
208
    { ParsingError("End");
 
209
      return -1;
 
210
    }
 
211
 
 
212
   return 0;
 
213
 }
 
214
 
 
215
int ParseClasses (void)
 
216
 { CharSet    CharClass;
 
217
   TableIndex ClassName;
 
218
 
 
219
   if (LookAhead.Type != COLON)
 
220
    { ParsingError ("Symbol \':\'");
 
221
      return -1;
 
222
    }
 
223
   NextToken (&LookAhead);
 
224
   while (LookAhead.Type == NAME)
 
225
    { ClassName = LookAhead.Index;
 
226
      NextToken (&LookAhead);
 
227
      if (LookAhead.Type != IS)
 
228
       { ParsingError ("\'=\'");
 
229
         return -1;
 
230
       }
 
231
      NextToken (&LookAhead);
 
232
      if (ParseClassDef (CharClass) == -1)
 
233
          return -1;
 
234
      NewClass ((char *)GetSymbolText (ClassName),
 
235
                CharClass);
 
236
      CharClass.DeleteAll ();
 
237
    }
 
238
   return 0;
 
239
 }
 
240
 
 
241
int ParseClassDef (CharSet& CharClass)
 
242
 { unsigned char From, To;
 
243
 
 
244
   do
 
245
    { if (LookAhead.Type != CHAR)
 
246
       { ParsingError ("Character Constant");
 
247
         return -1;
 
248
       }
 
249
      StringToChar (GetSymbolText(LookAhead.Index), From);
 
250
      NextToken(&LookAhead);
 
251
      if (LookAhead.Type == TO)
 
252
       { NextToken (&LookAhead);
 
253
         if (LookAhead.Type != CHAR)
 
254
          { ParsingError ("Second Character Constant");
 
255
            return -1;
 
256
          }
 
257
         StringToChar(GetSymbolText(LookAhead.Index), To);
 
258
         NextToken (&LookAhead);
 
259
       }
 
260
      else
 
261
         To = From;
 
262
      CharClass.Insert (From, To);
 
263
    }
 
264
   while (LookAhead.Type == CHAR);
 
265
   return 0;
 
266
 }
 
267
 
 
268
int ParseTable (char*& Name, Automaton& BuildAutomaton, ExprNames& Exprs,
 
269
                int& NumExprs)
 
270
 { Automaton NextAutomaton;
 
271
 
 
272
   if (LookAhead.Type != NAME)
 
273
    { ParsingError ("Name of Table");
 
274
      return -1;
 
275
    }
 
276
   Name = (char *)GetSymbolText (LookAhead.Index);
 
277
   NextToken (&LookAhead);
 
278
   if (LookAhead.Type != COLON)
 
279
    { ParsingError ("\':\'");
 
280
      return -1;
 
281
    }
 
282
   NextToken (&LookAhead);
 
283
   BuildAutomaton.Start = BuildAutomaton.AddState ();
 
284
   BuildAutomaton.End   = NULL;  /* mehrere Enden */
 
285
   NumExprs = 0;
 
286
   do
 
287
    { if (ParseLookAheadExpr (NextAutomaton, NumExprs) == -1)
 
288
         return -1;
 
289
      if (LookAhead.Type == MAP_TO)
 
290
       { NextToken (&LookAhead);
 
291
         if (LookAhead.Type != NAME)
 
292
          { ParsingError ("Name for expression");
 
293
            return -1;
 
294
          }
 
295
         Exprs.add ((char*)GetSymbolText (LookAhead.Index));
 
296
       }
 
297
      else if (LookAhead.Type == HASH_MARK)
 
298
       { Exprs.add ((char*)0);
 
299
       }
 
300
      else
 
301
       { ParsingError ("Expression Delimiter \'#\'");
 
302
         return -1;
 
303
       }
 
304
      BuildAutomaton.ShiftStates (NextAutomaton);
 
305
      BuildAutomaton.Start->AddTransition (EPSILON_TRANS, NextAutomaton.Start);
 
306
      NextToken (&LookAhead);
 
307
      NumExprs++;
 
308
    }
 
309
   while (LookAhead.Type!=END);
 
310
   return 0;
 
311
 }
 
312
 
 
313
int ParseLookAheadExpr (Automaton& BuildAutomaton, int Expr)
 
314
 { Automaton LookAheadAutomaton;
 
315
 
 
316
   if (ParseRegExpr (BuildAutomaton) == -1)
 
317
      return -1;
 
318
   if (LookAhead.Type == LOOK_AHEAD)
 
319
    { NextToken (&LookAhead);
 
320
      if (ParseRegExpr (LookAheadAutomaton) == -1)
 
321
         return -1;
 
322
      BuildAutomaton.ShiftStates (LookAheadAutomaton);
 
323
      BuildAutomaton.End->ShiftTransitionList (LookAheadAutomaton.Start);
 
324
      BuildAutomaton.End->Type      = NORMAL_STATE;
 
325
      BuildAutomaton.End->Expr (Expr);
 
326
      BuildAutomaton.End->LookAhead = 1;
 
327
      BuildAutomaton.RemoveState (LookAheadAutomaton.Start);
 
328
      BuildAutomaton.End = LookAheadAutomaton.End;
 
329
      BuildAutomaton.End->Type      = LOOK_AHEAD_END_STATE;
 
330
      BuildAutomaton.End->Expr (Expr);
 
331
    }
 
332
   else
 
333
    { BuildAutomaton.End->Type = END_STATE;
 
334
      BuildAutomaton.End->Expr (Expr);
 
335
    }
 
336
   return 0;
 
337
 }
 
338
 
 
339
int ParseRegExpr (Automaton& BuildAutomaton)
 
340
 { Automaton NextAutomaton;
 
341
   State* OldStart;
 
342
   State* OldEnd;
 
343
 
 
344
   if (ParseCatExprs (BuildAutomaton) == -1)
 
345
      return -1;
 
346
   if (LookAhead.Type != OR)
 
347
      return 0;
 
348
   OldStart = BuildAutomaton.Start;
 
349
   OldEnd   = BuildAutomaton.End;
 
350
   BuildAutomaton.Start = BuildAutomaton.AddState ();
 
351
   BuildAutomaton.Start->AddTransition (EPSILON_TRANS, OldStart);
 
352
   BuildAutomaton.End   = BuildAutomaton.AddState ();
 
353
   OldEnd->AddTransition (EPSILON_TRANS, BuildAutomaton.End);
 
354
   do
 
355
    { NextToken (&LookAhead);
 
356
      if (ParseCatExprs (NextAutomaton) == -1)
 
357
         return -1;
 
358
      BuildAutomaton.ShiftStates (NextAutomaton);
 
359
      BuildAutomaton.Start->AddTransition (EPSILON_TRANS, NextAutomaton.Start);
 
360
      NextAutomaton.End->AddTransition (EPSILON_TRANS, BuildAutomaton.End);
 
361
    } while (LookAhead.Type == OR);
 
362
   return 0;
 
363
 }
 
364
 
 
365
int ParseCatExprs (Automaton& BuildAutomaton)
 
366
 { Automaton NextAutomaton;
 
367
 
 
368
   if (ParseCatExpr (BuildAutomaton) == -1)
 
369
      return -1;
 
370
   while ((LookAhead.Type == STRING)             ||
 
371
          (LookAhead.Type == NAME)               ||
 
372
          (LookAhead.Type == EPSILON)            ||
 
373
          (LookAhead.Type == CHAR)               ||
 
374
          (LookAhead.Type == OPEN_BRACKET)       ||
 
375
          (LookAhead.Type == OPEN_SQUARE_BRACKET)   )
 
376
    { if (ParseCatExpr (NextAutomaton) == -1)
 
377
         return -1;
 
378
      BuildAutomaton.ShiftStates (NextAutomaton);
 
379
      BuildAutomaton.End->ShiftTransitionList (NextAutomaton.Start);
 
380
      BuildAutomaton.RemoveState (NextAutomaton.Start);
 
381
      BuildAutomaton.End = NextAutomaton.End;
 
382
    }
 
383
   return 0;
 
384
 }
 
385
 
 
386
int ParseCatExpr (Automaton& BuildAutomaton)
 
387
 { State* NewStart;
 
388
   State* NewEnd;
 
389
 
 
390
   if (ParseBasicExpr (BuildAutomaton) == -1)
 
391
      return -1;
 
392
   switch (LookAhead.Type)
 
393
    { case STAR:
 
394
         NextToken (&LookAhead);
 
395
         BuildAutomaton.End->AddTransition (EPSILON_TRANS, 
 
396
                                            BuildAutomaton.Start);
 
397
         NewStart = BuildAutomaton.AddState ();
 
398
         NewEnd   = BuildAutomaton.AddState ();
 
399
         NewStart->AddTransition (EPSILON_TRANS, BuildAutomaton.Start);
 
400
         BuildAutomaton.End->AddTransition (EPSILON_TRANS, NewEnd);
 
401
         NewStart->AddTransition (EPSILON_TRANS, NewEnd);
 
402
         BuildAutomaton.Start = NewStart;
 
403
         BuildAutomaton.End   = NewEnd;
 
404
         break;
 
405
      case PLUS:
 
406
         NextToken (&LookAhead);
 
407
         BuildAutomaton.End->AddTransition (EPSILON_TRANS, 
 
408
                                            BuildAutomaton.Start);
 
409
         NewStart = BuildAutomaton.AddState ();
 
410
         NewEnd   = BuildAutomaton.AddState ();
 
411
         NewStart->AddTransition (EPSILON_TRANS, BuildAutomaton.Start);
 
412
         BuildAutomaton.End->AddTransition (EPSILON_TRANS, NewEnd);
 
413
         BuildAutomaton.Start = NewStart;
 
414
         BuildAutomaton.End   = NewEnd;
 
415
         break;
 
416
    }
 
417
   while ((LookAhead.Type == STAR)||(LookAhead.Type == PLUS))
 
418
    { printf ("Ingnored * or + ");
 
419
      NextToken (&LookAhead);
 
420
    }
 
421
   return 0;
 
422
 }
 
423
 
 
424
int ParseBasicExpr (Automaton& BuildAutomaton)
 
425
 { unsigned char NewChar;
 
426
   unsigned char* StringScanContext;
 
427
   State* NewState;
 
428
 
 
429
   switch (LookAhead.Type)
 
430
    { case STRING : 
 
431
         BuildAutomaton.Start = BuildAutomaton.End = 
 
432
          BuildAutomaton.AddState ();
 
433
         StringScanContext = GetSymbolText (LookAhead.Index);
 
434
         while ((NewChar = ScanString (StringScanContext)) != '\0')
 
435
          { NewSingleChar (NewChar);
 
436
            NewState = BuildAutomaton.AddState ();
 
437
            BuildAutomaton.End->AddTransition (CHAR_TRANS, NewChar, NewState);
 
438
            BuildAutomaton.End = NewState;
 
439
          }
 
440
         NextToken (&LookAhead);
 
441
         break;
 
442
      case NAME : 
 
443
         BuildAutomaton.Start = BuildAutomaton.AddState ();
 
444
         BuildAutomaton.End   = BuildAutomaton.AddState ();
 
445
         BuildAutomaton.Start->AddTransition (CLASS_NAME_TRANS, (char*)
 
446
                                              GetSymbolText (LookAhead.Index),
 
447
                                              BuildAutomaton.End);
 
448
         NextToken (&LookAhead);
 
449
         break;
 
450
      case EPSILON : 
 
451
         BuildAutomaton.Start = BuildAutomaton.AddState ();
 
452
         BuildAutomaton.End   = BuildAutomaton.AddState ();
 
453
         BuildAutomaton.Start->AddTransition (EPSILON_TRANS, 
 
454
                                              BuildAutomaton.End);
 
455
         NextToken (&LookAhead);
 
456
         break;
 
457
      case CHAR : 
 
458
         if (StringToChar (GetSymbolText (LookAhead.Index),
 
459
             NewChar) == -1)
 
460
          { ParsingError ("Correct Char Const");
 
461
            return -1;
 
462
          }
 
463
         NewSingleChar (NewChar);
 
464
         BuildAutomaton.Start = BuildAutomaton.AddState ();
 
465
         BuildAutomaton.End   = BuildAutomaton.AddState ();
 
466
         BuildAutomaton.Start->AddTransition (CHAR_TRANS, NewChar, 
 
467
                                              BuildAutomaton.End);
 
468
         NextToken (&LookAhead);
 
469
         break;
 
470
      case OPEN_BRACKET:
 
471
         NextToken (&LookAhead);
 
472
         if (ParseRegExpr (BuildAutomaton) == -1)
 
473
            return -1;
 
474
         if (LookAhead.Type != CLOSE_BRACKET)
 
475
          { ParsingError ("Closing Bracket \')\'");
 
476
            return -1;
 
477
          }
 
478
         NextToken (&LookAhead);
 
479
         break;
 
480
      case OPEN_SQUARE_BRACKET:
 
481
         NextToken (&LookAhead);
 
482
         if (ParseRegExpr (BuildAutomaton) == -1)
 
483
            return -1;
 
484
         if (LookAhead.Type != CLOSE_SQUARE_BRACKET)
 
485
          { ParsingError ("Closing Bracket \']\'");
 
486
            return -1;
 
487
          }
 
488
         BuildAutomaton.Start->AddTransition (EPSILON_TRANS, 
 
489
                                              BuildAutomaton.End);
 
490
         NextToken (&LookAhead);
 
491
         break;
 
492
      default:
 
493
         ParsingError ("String, Class Name, Epsilon, Character "
 
494
                       "or Opening Bracket");
 
495
         return -1;
 
496
    }
 
497
   return 0;
 
498
 }
 
499
 
 
500
void NormalizeNFA (Automaton& BuildAutomaton)
 
501
 { ListEntry* StateContext;
 
502
   ListEntry* TransitionContext;
 
503
   State* CurrState;
 
504
   Transition* CurrTransition;
 
505
   struct ClassIdEntry* IdContext;
 
506
   ClassId Id;
 
507
 
 
508
   BuildAutomaton.ScanStates (StateContext);
 
509
   while ((CurrState = BuildAutomaton.NextState (StateContext)) != NULL)
 
510
    { CurrState->NonEpsilonTransitions.StartScanning (TransitionContext);
 
511
      CurrTransition = (Transition*)
 
512
       (CurrState->NonEpsilonTransitions.GetNext (TransitionContext));
 
513
      if (CurrTransition != NULL)
 
514
       { switch (CurrTransition->Type)
 
515
          { case CHAR_TRANS:
 
516
               CurrTransition->Id = FindClassId (CurrTransition->Temp.Char);
 
517
               CurrTransition->Type = CHAR_CLASS_TRANS;
 
518
               break;
 
519
            case CLASS_NAME_TRANS:
 
520
               ScanIds (IdContext, CurrTransition->Temp.Name);
 
521
               FindClassIds (IdContext, CurrTransition->Id);
 
522
               CurrTransition->Type = CHAR_CLASS_TRANS;
 
523
               while (FindClassIds (IdContext, Id))
 
524
                  CurrState->AddTransition (CHAR_CLASS_TRANS, Id, 
 
525
                                            CurrTransition->TransitionState);
 
526
               break;
 
527
          }
 
528
       }
 
529
    }
 
530
 }
 
531
 
 
532
void ConstructDFA (Automaton& NFA, Automaton& DFA, State **ExprTab)
 
533
 { List StartList;
 
534
   List* MoveList;
 
535
   DFAStateDescriptor* Closure;
 
536
   DFAStateDescriptor* CurrState;
 
537
   DFAStateDescriptor* NextState;
 
538
   Stack Unmarked;
 
539
   Stack Marked;
 
540
   ClassId Id;
 
541
   ListEntry* Context;
 
542
   ListEntry* NFAContext;
 
543
   int Found;
 
544
   State* NFAState;
 
545
 
 
546
   StartList.Append (NFA.Start);
 
547
   Closure = new DFAStateDescriptor;
 
548
   EpsilonClosure (StartList, Closure->NFAStates);
 
549
   Closure->DFAState = DFA.Start = DFA.AddState ();
 
550
   Unmarked.Push (Closure);
 
551
 
 
552
   while (!Unmarked.Empty ())
 
553
    { CurrState = (DFAStateDescriptor *)Unmarked.Pop ();
 
554
      Marked.Push (CurrState);
 
555
      ScanClassIds ();
 
556
      while (NextClassId (Id) != -1)
 
557
       { MoveList = new List;
 
558
         Move (CurrState->NFAStates, Id, *MoveList);
 
559
         if (!MoveList->Empty ())
 
560
          { Closure = new DFAStateDescriptor;
 
561
            EpsilonClosure (*MoveList, Closure->NFAStates);
 
562
            delete MoveList;
 
563
 
 
564
            Found = 0;
 
565
            Unmarked.StartScanning (Context);
 
566
            while (!Found &&
 
567
                   ((NextState = (DFAStateDescriptor*)
 
568
                   (Unmarked.GetNext (Context))) != NULL))
 
569
             { if (NextState->NFAStates.IsEqual (Closure->NFAStates))
 
570
                  Found = 1;
 
571
             }
 
572
            Marked.StartScanning (Context);
 
573
            while (!Found &&
 
574
                   ((NextState = (DFAStateDescriptor*)
 
575
                   (Marked.GetNext (Context))) != NULL))
 
576
             { if (NextState->NFAStates.IsEqual (Closure->NFAStates))
 
577
                  Found = 1;
 
578
             }
 
579
            if (!Found)
 
580
             { Closure->DFAState = DFA.AddState ();
 
581
               Unmarked.Push (Closure);
 
582
               CurrState->DFAState->AddTransition (CHAR_CLASS_TRANS, Id,
 
583
                                                   Closure->DFAState);
 
584
             }
 
585
            else
 
586
             { delete Closure;
 
587
               CurrState->DFAState->AddTransition (CHAR_CLASS_TRANS, Id,
 
588
                                                   NextState->DFAState);
 
589
             }
 
590
          }
 
591
         else
 
592
            delete MoveList;
 
593
       }
 
594
    }
 
595
   Marked.StartScanning (Context);
 
596
   while ((CurrState = (DFAStateDescriptor*)Marked.GetNext (Context)) !=
 
597
          NULL)
 
598
    { CurrState->NFAStates.StartScanning (NFAContext);
 
599
      while ((NFAState = (State*)(CurrState->NFAStates.GetNext (NFAContext)))
 
600
             != NULL)
 
601
       { if (NFAState->LookAhead)
 
602
          { CurrState->DFAState->LookAhead = 1;
 
603
            ExprTab[NFAState->Expr ()] = CurrState->DFAState;
 
604
          }
 
605
         if (NFAState->Type != NORMAL_STATE)
 
606
          { if (CurrState->DFAState->Type != NORMAL_STATE)
 
607
             { if (NFAState->Expr () < CurrState->DFAState->Expr ())
 
608
                { CurrState->DFAState->Expr (NFAState->Expr ());
 
609
                  CurrState->DFAState->Type = NFAState->Type;
 
610
                }
 
611
             }
 
612
            else
 
613
             { CurrState->DFAState->Expr (NFAState->Expr ());
 
614
               CurrState->DFAState->Type = NFAState->Type;
 
615
             }
 
616
          }
 
617
       }
 
618
      delete CurrState;
 
619
    }
 
620
 }
 
621
 
 
622
void EpsilonClosure (List& States, List& Closure)
 
623
 { Stack       xStack;
 
624
   State*      xState;
 
625
   ListEntry*  Context;
 
626
   Transition* xTransition;
 
627
 
 
628
   Closure.CopyEntries (States);
 
629
   xStack.PushList (States);
 
630
 
 
631
   while (!xStack.Empty ())
 
632
    { xState = (State*)(xStack.Pop ());
 
633
      xState->EpsilonTransitions.StartScanning (Context);
 
634
      while ((xTransition = (Transition*)
 
635
              (xState->EpsilonTransitions.GetNext (Context))) != NULL)
 
636
       { if (!Closure.IsIn (xTransition->TransitionState))
 
637
          { Closure.Append (xTransition->TransitionState);
 
638
            xStack.Push (xTransition->TransitionState);
 
639
          }
 
640
       }
 
641
    }
 
642
 }
 
643
 
 
644
void Move (List& States, ClassId Id, List& Result)
 
645
 { ListEntry* StateContext;
 
646
   ListEntry* TransitionContext;
 
647
   State* CurrState;
 
648
   Transition* CurrTransition;
 
649
 
 
650
   States.StartScanning (StateContext);
 
651
   while ((CurrState = (State*)(States.GetNext (StateContext))) != NULL)
 
652
    { CurrState->NonEpsilonTransitions.StartScanning (TransitionContext);
 
653
      while ((CurrTransition = (Transition*)
 
654
       (CurrState->NonEpsilonTransitions.GetNext (TransitionContext))) != NULL)
 
655
       { if (CurrTransition->Id == Id)
 
656
            Result.Append (CurrTransition->TransitionState);
 
657
       }
 
658
    }
 
659
 }
 
660
 
 
661
 
 
662
void OptimizeDFA (Automaton& In, Automaton& Out,
 
663
                  State **ExprTab, int NumOfExprs)
 
664
 { List        Groups, Partitions, NewPartitions;
 
665
   List*       MainGroup;
 
666
   List*       EndStateGroup;
 
667
   List*       CurrGroup;
 
668
   State*      CurrState;
 
669
   State*      FirstState;
 
670
   ListEntry*  Context1;
 
671
   ListEntry*  Context2;
 
672
   ListEntry*  Context3;
 
673
   int         MaxGroup;
 
674
   int         Found;
 
675
   int         Changed;
 
676
   int         CurrExpr;
 
677
   Transition* CurrTransition;
 
678
   
 
679
   /* Initialisierung */
 
680
 
 
681
   MaxGroup = 0;
 
682
   MainGroup = new List;
 
683
   In.ScanStates (Context1);
 
684
   while ((CurrState = In.NextState (Context1)) != NULL)
 
685
    { if (CurrState->Type == NORMAL_STATE)
 
686
       { CurrState->Group = 0;
 
687
         MainGroup->Append (CurrState);
 
688
       }
 
689
      else
 
690
       { Groups.StartScanning (Context2);
 
691
         Found = 0;
 
692
         while (((CurrGroup = (List *)(Groups.GetNext (Context2))) != NULL) &&
 
693
                (!Found))
 
694
          { CurrGroup->StartScanning (Context3);
 
695
            FirstState = (State *)(CurrGroup->GetNext (Context3));
 
696
            if (FirstState->Expr () == CurrState->Expr ())
 
697
             { Found = 1;
 
698
               EndStateGroup = CurrGroup;
 
699
               CurrState->Group = FirstState->Group;
 
700
             }
 
701
          }
 
702
         if (Found)
 
703
            EndStateGroup->Append (CurrState);
 
704
         else
 
705
         { CurrState->Group = ++MaxGroup;
 
706
           EndStateGroup = new List;
 
707
           EndStateGroup->Append (CurrState);
 
708
           Groups.Append (EndStateGroup);
 
709
         }
 
710
       }
 
711
    }
 
712
   Groups.Append (MainGroup);
 
713
 
 
714
   /* Partitionieren */
 
715
 
 
716
   do
 
717
    { Changed = 0;
 
718
      Groups.StartScanning (Context1);
 
719
      while ((CurrGroup = (List *)(Groups.GetNext (Context1))) != NULL)
 
720
       { if (PartitionGroup (CurrGroup, MaxGroup, NewPartitions))
 
721
            Changed = 1;
 
722
         Partitions.ShiftEntries (NewPartitions);
 
723
       }      
 
724
      Groups.ShiftEntries (Partitions);
 
725
    } while (Changed);
 
726
 
 
727
   /* Resultat erstellen */
 
728
 
 
729
   Groups.StartScanning (Context1);
 
730
   while ((CurrGroup = (List *)(Groups.GetNext (Context1))) != NULL)
 
731
    { CurrGroup->StartScanning (Context2);
 
732
      FirstState = (State *)(CurrGroup->GetNext (Context2));
 
733
      FirstState->Representative = FirstState;
 
734
      while ((CurrState = (State *)(CurrGroup->GetNext (Context2))) != NULL)
 
735
       { CurrState->Representative = FirstState;
 
736
         if (CurrState->LookAhead)
 
737
          { FirstState->LookAhead = 1;
 
738
            for (CurrExpr = 0; CurrExpr < NumOfExprs; CurrExpr++)
 
739
               if (ExprTab[CurrExpr] == CurrState)
 
740
                  ExprTab[CurrExpr] = CurrState->Representative;
 
741
          }
 
742
         if (CurrState->Type != NORMAL_STATE)
 
743
          { if (FirstState->Type != NORMAL_STATE)
 
744
             { if (CurrState->Expr () < FirstState->Expr ())
 
745
                { FirstState->Expr (CurrState->Expr ());
 
746
                  FirstState->Type = CurrState->Type;
 
747
                }
 
748
             }
 
749
            else
 
750
             { FirstState->Expr (CurrState->Expr ());
 
751
               FirstState->Type = CurrState->Type;
 
752
             }
 
753
          }
 
754
       }
 
755
    }
 
756
   Groups.StartScanning (Context1);
 
757
   while ((CurrGroup = (List *)(Groups.GetNext (Context1))) != NULL)
 
758
    { CurrGroup->StartScanning (Context2);
 
759
      FirstState = (State *)(CurrGroup->GetNext (Context2));
 
760
      Out.ShiftState (In, FirstState);
 
761
      FirstState->NonEpsilonTransitions.StartScanning (Context3);
 
762
      while ((CurrTransition = (Transition *)
 
763
              (FirstState->NonEpsilonTransitions.GetNext (Context3))) != NULL)
 
764
         CurrTransition->TransitionState = CurrTransition->TransitionState->Representative;
 
765
    }
 
766
   Out.Start = In.Start->Representative;
 
767
 }
 
768
 
 
769
int PartitionGroup (List* Group, int& MaxGroup, List& Partitions)
 
770
 { ListEntry* Context;
 
771
   List*      OtherGroup;
 
772
   State*     FirstState;
 
773
   State*     CurrState;
 
774
 
 
775
   OtherGroup = new List;
 
776
   Group->StartScanning (Context);
 
777
   FirstState = (State*)(Group->GetNext (Context));
 
778
   while ((CurrState = (State*)(Group->GetNext (Context))) != NULL)
 
779
    { if (!InOneGroup (FirstState, CurrState))
 
780
       { OtherGroup->Append (CurrState);
 
781
         Group->Remove (CurrState);
 
782
         CurrState->Group = MaxGroup + 1;
 
783
       }
 
784
    }
 
785
   if (!OtherGroup->Empty ())
 
786
    { MaxGroup++;
 
787
      PartitionGroup (OtherGroup, MaxGroup, Partitions);
 
788
      Partitions.Append(OtherGroup);
 
789
      return 1;
 
790
    }
 
791
   else
 
792
    { delete OtherGroup;
 
793
      return 0;
 
794
    }
 
795
 }
 
796
 
 
797
int InOneGroup (State* State1, State* State2)
 
798
 { ListEntry*  Context1;
 
799
   ListEntry*  Context2;
 
800
   Transition* Transition1;
 
801
   Transition* Transition2;
 
802
   int         IdFound;
 
803
 
 
804
   if (State1->NonEpsilonTransitions.Length () !=
 
805
       State2->NonEpsilonTransitions.Length ())
 
806
      return 0;
 
807
   State1->NonEpsilonTransitions.StartScanning (Context1);
 
808
   while ((Transition1 = (Transition*)
 
809
           (State1->NonEpsilonTransitions.GetNext (Context1))) != NULL)
 
810
    { IdFound = 0;
 
811
      State2->NonEpsilonTransitions.StartScanning (Context2);
 
812
      while ((Transition2 = (Transition*)
 
813
              (State2->NonEpsilonTransitions.GetNext (Context2))) != NULL)
 
814
       { if (Transition1->Id == Transition2->Id)
 
815
          { IdFound = 1;
 
816
            if (Transition1->TransitionState->Group != 
 
817
                Transition2->TransitionState->Group)
 
818
               return 0;
 
819
          }
 
820
       }
 
821
      if (!IdFound)
 
822
         return 0;
 
823
    }
 
824
   return 1;
 
825
 }
 
826
 
 
827
void PrintCharMap (char *Name)
 
828
 { CharSet       CurrChars;
 
829
   int           Id;
 
830
   int           CharMap[256];
 
831
   int           Char;
 
832
   int           Line;
 
833
 
 
834
   for (Char = 0; Char < 256; Char++)
 
835
      CharMap[Char] = -1;
 
836
   ScanClassMap ();
 
837
   while (NextEntry (Id, CurrChars) != -1)
 
838
      for (Char = 0; Char < 256; Char++)
 
839
         if (CurrChars.In ((unsigned char)Char))
 
840
            CharMap[Char] = (int)Id;
 
841
   printf ("static char %sMap[256] =\n", Name);
 
842
   for (Line = 0; Line < 32; Line++)
 
843
      switch (Line)
 
844
       { case 0 :
 
845
            printf (" { %3d, %3d, %3d, %3d, %3d, %3d, %3d, %3d,\n",
 
846
                    CharMap[0], CharMap[1], CharMap[2], CharMap[3],
 
847
                    CharMap[4], CharMap[5], CharMap[6], CharMap[7]);
 
848
            break;
 
849
         case 31:
 
850
            printf ("   %3d, %3d, %3d, %3d, %3d, %3d, %3d, %3d\n };\n\n",
 
851
                    CharMap[248], CharMap[249], CharMap[250], CharMap[251],
 
852
                    CharMap[252], CharMap[253], CharMap[254], CharMap[255]);
 
853
            break;
 
854
         default:
 
855
            printf ("   %3d, %3d, %3d, %3d, %3d, %3d, %3d, %3d,\n",
 
856
                    CharMap[8 * Line + 0], CharMap[8 * Line + 1], 
 
857
                    CharMap[8 * Line + 2], CharMap[8 * Line + 3],
 
858
                    CharMap[8 * Line + 4], CharMap[8 * Line + 5],
 
859
                    CharMap[8 * Line + 6], CharMap[8 * Line + 7]);
 
860
            break;
 
861
       }
 
862
 }
 
863
 
 
864
void SetStateNumbers (Automaton& Automaton)
 
865
 { ListEntry* Context;
 
866
   int        Number;
 
867
   State*     CurrState;
 
868
 
 
869
   Number = 0;
 
870
   Automaton.ScanStates (Context);
 
871
   while ((CurrState = Automaton.NextState (Context)) != NULL)
 
872
      CurrState->Number = Number++;
 
873
 }
 
874
 
 
875
void PrintExprTab (char* Name, Automaton& OptimizedDFA,
 
876
                   State **ExprTab, int NumOfExprs)
 
877
 { int        CurrExpr;
 
878
   int        Lines, CurrLine;
 
879
 
 
880
   for (CurrExpr = 0, Lines = 0; CurrExpr < NumOfExprs; CurrExpr++)
 
881
      if (ExprTab[CurrExpr] != (State *)-1)
 
882
         Lines++;
 
883
 
 
884
   for (CurrExpr = 0, CurrLine = 0; CurrExpr < NumOfExprs; CurrExpr++)
 
885
    { if (ExprTab[CurrExpr] != (State *)-1)
 
886
       { if (CurrLine == 0)
 
887
            printf ("static int %sLookAheadTab[][2] =\n { ", Name);
 
888
         else
 
889
            printf ("   ");
 
890
         printf (" { %3d, %3d }", CurrExpr, ExprTab[CurrExpr]->Number);
 
891
         if (CurrLine < Lines - 1)
 
892
             printf (",\n");
 
893
         else
 
894
             printf ("\n };\n\n");
 
895
         CurrLine++;
 
896
       }
 
897
    }
 
898
 }
 
899
 
 
900
void PrintTransitionTable (char* Name, Automaton& Automaton)
 
901
 { ListEntry* Context;
 
902
   State*     CurrState;
 
903
   int        Size;
 
904
   int        TabEnd;
 
905
   int        Start;
 
906
   int        Count;
 
907
   int        Elem;
 
908
   int        NumOfStates;
 
909
   int        *StartTab;
 
910
   int        *TransitionTab;
 
911
   int        *ControlTab;
 
912
 
 
913
   printf ("static int %sStart = %d;\n\n", Name, Automaton.Start->Number);
 
914
   Size = 0;
 
915
   NumOfStates = 0;
 
916
   Automaton.ScanStates (Context);
 
917
   while ((CurrState = Automaton.NextState (Context)) != NULL)
 
918
    { Size += MaxSize (CurrState);
 
919
      NumOfStates++;
 
920
    }
 
921
   StartTab      = new int[NumOfStates];
 
922
   TransitionTab = new int[Size];
 
923
   ControlTab    = new int[Size];
 
924
   for (Count = 0; Count < Size; Count++)
 
925
    { TransitionTab[Count] = -1;
 
926
      ControlTab[Count]    = -1;
 
927
    }
 
928
 
 
929
   printf ("#ifndef __TTGEN__\n"
 
930
           "#  define __TTGEN__\n\n"
 
931
           "   typedef struct\n"
 
932
           "    { unsigned char Type;\n"
 
933
           "      unsigned char LookAhead;\n"
 
934
           "      int           Expression;\n"
 
935
           "      int           Start;\n"
 
936
           "    } States;\n\n"
 
937
           "#endif\n\n"
 
938
           "static States %sStates[] =\n", Name);
 
939
   TabEnd   = 0;
 
940
   Automaton.ScanStates (Context);
 
941
   while ((CurrState = Automaton.NextState (Context)) != NULL)
 
942
    { Start = PositionState (CurrState, TransitionTab, ControlTab, TabEnd);
 
943
      StartTab[CurrState->Number] = Start;
 
944
      if (CurrState->Number == 0)
 
945
         printf (" { ");
 
946
      else
 
947
         printf ("   ");
 
948
      printf (" { %1d, %1d, %5d, %5d }", CurrState->Type, 
 
949
              CurrState->LookAhead, CurrState->Expr (), Start);
 
950
      if (CurrState->Number == NumOfStates - 1)
 
951
         printf ("\n };\n");
 
952
      else
 
953
         printf (",\n");
 
954
    }
 
955
   printf ("\n");
 
956
   for (Count = 0; Count <= TabEnd; Count += 8)
 
957
    { if (Count < 8)
 
958
         printf ("static int %sNext[] =\n"
 
959
                 " { ", Name);
 
960
      else
 
961
         printf ("   ");
 
962
      if (TabEnd - Count >= 8)
 
963
         printf ("%5d, %5d, %5d, %5d, %5d, %5d, %5d, %5d,\n",
 
964
                 TransitionTab[Count + 0], TransitionTab[Count + 1],
 
965
                 TransitionTab[Count + 2], TransitionTab[Count + 3],
 
966
                 TransitionTab[Count + 4], TransitionTab[Count + 5],
 
967
                 TransitionTab[Count + 6], TransitionTab[Count + 7]);
 
968
      else
 
969
         for (Elem = Count; Elem <= TabEnd; Elem++)
 
970
            if (Elem < TabEnd)
 
971
               printf ("%5d, ", TransitionTab[Elem]);
 
972
            else
 
973
               printf ("%5d\n };\n", TransitionTab[Elem]);
 
974
    }
 
975
   printf ("\n");
 
976
   for (Count = 0; Count <= TabEnd; Count += 8)
 
977
    { if (Count < 8)
 
978
         printf ("static int %sControl[] =\n"
 
979
                 " { ", Name);
 
980
      else
 
981
         printf ("   ");
 
982
      if (TabEnd - Count >= 8)
 
983
         printf ("%5d, %5d, %5d, %5d, %5d, %5d, %5d, %5d,\n",
 
984
                 ControlTab[Count + 0], ControlTab[Count + 1],
 
985
                 ControlTab[Count + 2], ControlTab[Count + 3],
 
986
                 ControlTab[Count + 4], ControlTab[Count + 5],
 
987
                 ControlTab[Count + 6], ControlTab[Count + 7]);
 
988
      else
 
989
         for (Elem = Count; Elem <= TabEnd; Elem++)
 
990
            if (Elem < TabEnd)
 
991
               printf ("%5d, ", ControlTab[Elem]);
 
992
            else
 
993
               printf ("%5d\n };\n", ControlTab[Elem]);
 
994
    }
 
995
   printf ("\n");
 
996
   delete[] TransitionTab;
 
997
   delete[] ControlTab;
 
998
   delete[] StartTab;
 
999
 }
 
1000
 
 
1001
int MaxSize (State* State)
 
1002
 { int         MinId, MaxId;
 
1003
   ListEntry*  Context;
 
1004
   Transition* CurrTransition;
 
1005
   
 
1006
   State->NonEpsilonTransitions.StartScanning (Context);
 
1007
   CurrTransition = (Transition*)
 
1008
      (State->NonEpsilonTransitions.GetNext (Context));
 
1009
   if (CurrTransition == NULL)
 
1010
      return 0;
 
1011
   MinId = CurrTransition->Id.GetId ();
 
1012
   MaxId = CurrTransition->Id.GetId ();
 
1013
   while ((CurrTransition = (Transition*)
 
1014
      (State->NonEpsilonTransitions.GetNext (Context))) != NULL)
 
1015
    { if (CurrTransition->Id.GetId () < MinId)
 
1016
         MinId = CurrTransition->Id.GetId ();
 
1017
      if (CurrTransition->Id.GetId () > MaxId)
 
1018
         MaxId = CurrTransition->Id.GetId ();
 
1019
    }
 
1020
   return MaxId - MinId + 1;
 
1021
 }
 
1022
 
 
1023
int PositionState (State* State, int *TransitionTab, int *ControlTab, int& End)
 
1024
 { int         MinId, MaxId;
 
1025
   ListEntry*  Context;
 
1026
   Transition* CurrTransition;
 
1027
   int         Start;
 
1028
   int         Pos;
 
1029
   int         Collision;
 
1030
 
 
1031
   State->NonEpsilonTransitions.StartScanning (Context);
 
1032
   CurrTransition = (Transition*)
 
1033
      (State->NonEpsilonTransitions.GetNext (Context));
 
1034
   if (CurrTransition == NULL)
 
1035
      return 0;
 
1036
   MinId = CurrTransition->Id.GetId ();
 
1037
   while ((CurrTransition = (Transition*)
 
1038
      (State->NonEpsilonTransitions.GetNext (Context))) != NULL)
 
1039
      if (CurrTransition->Id.GetId () < MinId)
 
1040
         MinId = CurrTransition->Id.GetId ();
 
1041
   Start = - MinId;
 
1042
   do
 
1043
    { State->NonEpsilonTransitions.StartScanning (Context);
 
1044
      Collision = 0;
 
1045
      do
 
1046
       { CurrTransition = (Transition*)
 
1047
          (State->NonEpsilonTransitions.GetNext (Context));
 
1048
         if (CurrTransition != NULL)
 
1049
            if (ControlTab[Start + CurrTransition->Id.GetId ()] != -1)
 
1050
               Collision = 1;
 
1051
       } while (CurrTransition != NULL && (!Collision));
 
1052
      if (Collision)
 
1053
         Start++;
 
1054
    } while (Collision);
 
1055
   State->NonEpsilonTransitions.StartScanning (Context);
 
1056
   while ((CurrTransition = (Transition*)
 
1057
      (State->NonEpsilonTransitions.GetNext (Context))) != NULL)
 
1058
    { Pos = Start + CurrTransition->Id.GetId ();
 
1059
      TransitionTab[Pos] = CurrTransition->TransitionState->Number;
 
1060
      ControlTab[Pos]    = State->Number;
 
1061
      if (Pos > End)
 
1062
         End = Pos;
 
1063
    }
 
1064
   return Start;
 
1065
 }