ragel/parsetree.h

   1 /*
   2  *  Copyright 2001-2006 Adrian Thurston <thurston@cs.queensu.ca>
   3  */
   4
   5 /*  This file is part of Ragel.
   6  *
   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.
  11  *
  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.
  16  *
  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
  20  */
  21
  22 #ifndef _PARSETREE_H
  23 #define _PARSETREE_H
  24
  25 #include "ragel.h"
  26 #include "avlmap.h"
  27 #include "bstmap.h"
  28 #include "vector.h"
  29 #include "dlist.h"
  30
  31 struct NameInst;
  32
  33 /* Types of builtin machines. */
  34 enum BuiltinMachine
  35 {
  36         BT_Any,
  37         BT_Ascii,
  38         BT_Extend,
  39         BT_Alpha,
  40         BT_Digit,
  41         BT_Alnum,
  42         BT_Lower,
  43         BT_Upper,
  44         BT_Cntrl,
  45         BT_Graph,
  46         BT_Print,
  47         BT_Punct,
  48         BT_Space,
  49         BT_Xdigit,
  50         BT_Lambda,
  51         BT_Empty
  52 };
  53
  54
  55 struct ParseData;
  56
  57 /* Leaf type. */
  58 struct Literal;
  59
  60 /* Tree nodes. */
  61
  62 struct Term;
  63 struct FactorWithAug;
  64 struct FactorWithRep;
  65 struct FactorWithNeg;
  66 struct Factor;
  67 struct Expression;
  68 struct Join;
  69 struct JoinOrLm;
  70 struct LongestMatch;
  71 struct LongestMatchPart;
  72 struct LmPartList;
  73 struct Range;
  74
  75 /* Type of augmentation. Describes locations in the machine. */
  76 enum AugType
  77 {
  78         /* Transition actions/priorities. */
  79         at_start,
  80         at_all,
  81         at_finish,
  82         at_leave,
  83
  84         /* Global error actions. */
  85         at_start_gbl_error,
  86         at_all_gbl_error,
  87         at_final_gbl_error,
  88         at_not_start_gbl_error,
  89         at_not_final_gbl_error,
  90         at_middle_gbl_error,
  91
  92         /* Local error actions. */
  93         at_start_local_error,
  94         at_all_local_error,
  95         at_final_local_error,
  96         at_not_start_local_error,
  97         at_not_final_local_error,
  98         at_middle_local_error,
  99
 100         /* To State Action embedding. */
 101         at_start_to_state,
 102         at_all_to_state,
 103         at_final_to_state,
 104         at_not_start_to_state,
 105         at_not_final_to_state,
 106         at_middle_to_state,
 107
 108         /* From State Action embedding. */
 109         at_start_from_state,
 110         at_all_from_state,
 111         at_final_from_state,
 112         at_not_start_from_state,
 113         at_not_final_from_state,
 114         at_middle_from_state,
 115
 116         /* EOF Action embedding. */
 117         at_start_eof,
 118         at_all_eof,
 119         at_final_eof,
 120         at_not_start_eof,
 121         at_not_final_eof,
 122         at_middle_eof
 123 };
 124
 125 /* IMPORTANT: These must follow the same order as the state augs in AugType
 126  * since we will be using this to compose AugType. */
 127 enum StateAugType
 128 {
 129         sat_start = 0,
 130         sat_all,
 131         sat_final,
 132         sat_not_start,
 133         sat_not_final,
 134         sat_middle
 135 };
 136
 137 struct Action;
 138 struct PriorDesc;
 139 struct RegExpr;
 140 struct ReItem;
 141 struct ReOrBlock;
 142 struct ReOrItem;
 143 struct ExplicitMachine;
 144 struct InlineItem;
 145 struct InlineList;
 146
 147 /* Reference to a named state. */
 148 typedef Vector<char*> NameRef;
 149 typedef Vector<NameRef*> NameRefList;
 150 typedef Vector<NameInst*> NameTargList;
 151
 152 /* Structure for storing location of epsilon transitons. */
 153 struct EpsilonLink
 154 {
 155         EpsilonLink( const InputLoc &loc, NameRef &target )
 156                 : loc(loc), target(target) { }
 157
 158         InputLoc loc;
 159         NameRef target;
 160 };
 161
 162 struct Label
 163 {
 164         Label( const InputLoc &loc, char *data )
 165                 : loc(loc), data(data) { }
 166
 167         InputLoc loc;
 168         char *data;
 169 };
 170
 171 /* Structrue represents an action assigned to some FactorWithAug node. The
 172  * factor with aug will keep an array of these. */
 173 struct ParserAction
 174 {
 175         ParserAction( const InputLoc &loc, AugType type, int localErrKey, Action *action )
 176                 : loc(loc), type(type), localErrKey(localErrKey), action(action) { }
 177
 178         InputLoc loc;
 179         AugType type;
 180         int localErrKey;
 181         Action *action;
 182 };
 183
 184 struct Token
 185 {
 186         char *data;
 187         int length;
 188         InputLoc loc;
 189
 190         void prepareLitString( Token &result, bool &caseInsensitive );
 191         void append( const Token &other );
 192         void set( char *str, int len );
 193 };
 194
 195 /* Store the value and type of a priority augmentation. */
 196 struct PriorityAug
 197 {
 198         PriorityAug( AugType type, int priorKey, int priorValue ) :
 199                 type(type), priorKey(priorKey), priorValue(priorValue) { }
 200
 201         AugType type;
 202         int priorKey;
 203         int priorValue;
 204 };
 205
 206 /*
 207  * A Variable Definition
 208  */
 209 struct VarDef
 210 {
 211         VarDef( char *name, JoinOrLm *joinOrLm )
 212                 : name(name), joinOrLm(joinOrLm) { }
 213
 214         /* Parse tree traversal. */
 215         FsmAp *walk( ParseData *pd );
 216         void makeNameTree( const InputLoc &loc, ParseData *pd );
 217         void resolveNameRefs( ParseData *pd );
 218
 219         char *name;
 220         JoinOrLm *joinOrLm;
 221 };
 222
 223
 224 /*
 225  * LongestMatch
 226  *
 227  * Wherever possible the item match will execute on the character. If not
 228  * possible the item match will execute on a lookahead character and either
 229  * hold the current char (if one away) or backup.
 230  *
 231  * How to handle the problem of backing up over a buffer break?
 232  *
 233  * Don't want to use pending out transitions for embedding item match because
 234  * the role of item match action is different: it may sometimes match on the
 235  * final transition, or may match on a lookahead character.
 236  *
 237  * Don't want to invent a new operator just for this. So just trail action
 238  * after machine, this means we can only use literal actions.
 239  *
 240  * The item action may
 241  *
 242  * What states of the machine will be final. The item actions that wrap around
 243  * on the last character will go straight to the start state.
 244  *
 245  * Some transitions will be lookahead transitions, they will hold the current
 246  * character. Crossing them with regular transitions must be restricted
 247  * because it does not make sense. The transition cannot simultaneously hold
 248  * and consume the current character.
 249  */
 250 struct LongestMatchPart
 251 {
 252         LongestMatchPart( Join *join, Action *action,
 253                         InputLoc &semiLoc, int longestMatchId )
 254         :
 255                 join(join), action(action), semiLoc(semiLoc),
 256                 longestMatchId(longestMatchId), inLmSelect(false) { }
 257
 258         InputLoc getLoc();
 259
 260         Join *join;
 261         Action *action;
 262         InputLoc semiLoc;
 263
 264         Action *setActId;
 265         Action *actOnLast;
 266         Action *actOnNext;
 267         Action *actLagBehind;
 268         int longestMatchId;
 269         bool inLmSelect;
 270         LongestMatch *longestMatch;
 271
 272         LongestMatchPart *prev, *next;
 273 };
 274
 275 /* Declare a new type so that ptreetypes.h need not include dlist.h. */
 276 struct LmPartList : DList<LongestMatchPart> {};
 277
 278 struct LongestMatch
 279 {
 280         /* Construct with a list of joins */
 281         LongestMatch( const InputLoc &loc, LmPartList *longestMatchList ) :
 282                 loc(loc), longestMatchList(longestMatchList), name(0),
 283                 lmSwitchHandlesError(false) { }
 284
 285         /* Tree traversal. */
 286         FsmAp *walk( ParseData *pd );
 287         void makeNameTree( ParseData *pd );
 288         void resolveNameRefs( ParseData *pd );
 289         void runLonestMatch( ParseData *pd, FsmAp *graph );
 290         Action *newAction( ParseData *pd, const InputLoc &loc, char *name,
 291                         InlineList *inlineList );
 292         void makeActions( ParseData *pd );
 293         void findName( ParseData *pd );
 294         void restart( FsmAp *graph, TransAp *trans );
 295
 296         InputLoc loc;
 297         LmPartList *longestMatchList;
 298         char *name;
 299
 300         Action *lmActSelect;
 301         bool lmSwitchHandlesError;
 302
 303         LongestMatch *next, *prev;
 304 };
 305
 306
 307 /* List of Expressions. */
 308 typedef DList<Expression> ExprList;
 309
 310 struct JoinOrLm
 311 {
 312         enum Type {
 313                 JoinType,
 314                 LongestMatchType
 315         };
 316
 317         JoinOrLm( Join *join ) :
 318                 join(join), type(JoinType) {}
 319         JoinOrLm( LongestMatch *longestMatch ) :
 320                 longestMatch(longestMatch), type(LongestMatchType) {}
 321
 322         FsmAp *walk( ParseData *pd );
 323         void makeNameTree( ParseData *pd );
 324         void resolveNameRefs( ParseData *pd );
 325
 326         Join *join;
 327         LongestMatch *longestMatch;
 328         Type type;
 329 };
 330
 331 /*
 332  * Join
 333  */
 334 struct Join
 335 {
 336         /* Construct with the first expression. */
 337         Join( Expression *expr );
 338         Join( const InputLoc &loc, Expression *expr );
 339
 340         /* Tree traversal. */
 341         FsmAp *walk( ParseData *pd );
 342         FsmAp *walkJoin( ParseData *pd );
 343         void makeNameTree( ParseData *pd );
 344         void resolveNameRefs( ParseData *pd );
 345
 346         /* Data. */
 347         InputLoc loc;
 348         ExprList exprList;
 349 };
 350
 351 /*
 352  * Expression
 353  */
 354 struct Expression
 355 {
 356         enum Type {
 357                 OrType,
 358                 IntersectType,
 359                 SubtractType,
 360                 StrongSubtractType,
 361                 TermType,
 362                 BuiltinType
 363         };
 364
 365         /* Construct with an expression on the left and a term on the right. */
 366         Expression( Expression *expression, Term *term, Type type ) :
 367                 expression(expression), term(term),
 368                 builtin(builtin), type(type), prev(this), next(this) { }
 369
 370         /* Construct with only a term. */
 371         Expression( Term *term ) :
 372                 expression(0), term(term), builtin(builtin),
 373                 type(TermType) , prev(this), next(this) { }
 374
 375         /* Construct with a builtin type. */
 376         Expression( BuiltinMachine builtin ) :
 377                 expression(0), term(0), builtin(builtin),
 378                 type(BuiltinType), prev(this), next(this) { }
 379
 380         ~Expression();
 381
 382         /* Tree traversal. */
 383         FsmAp *walk( ParseData *pd, bool lastInSeq = true );
 384         void makeNameTree( ParseData *pd );
 385         void resolveNameRefs( ParseData *pd );
 386
 387         /* Node data. */
 388         Expression *expression;
 389         Term *term;
 390         BuiltinMachine builtin;
 391         Type type;
 392
 393         Expression *prev, *next;
 394 };
 395
 396 /*
 397  * Term
 398  */
 399 struct Term
 400 {
 401         enum Type {
 402                 ConcatType,
 403                 RightStartType,
 404                 RightFinishType,
 405                 LeftType,
 406                 FactorWithAugType
 407         };
 408
 409         Term( Term *term, FactorWithAug *factorWithAug ) :
 410                 term(term), factorWithAug(factorWithAug), type(ConcatType) { }
 411
 412         Term( Term *term, FactorWithAug *factorWithAug, Type type ) :
 413                 term(term), factorWithAug(factorWithAug), type(type) { }
 414
 415         Term( FactorWithAug *factorWithAug ) :
 416                 term(0), factorWithAug(factorWithAug), type(FactorWithAugType) { }
 417
 418         ~Term();
 419
 420         FsmAp *walk( ParseData *pd, bool lastInSeq = true );
 421         void makeNameTree( ParseData *pd );
 422         void resolveNameRefs( ParseData *pd );
 423
 424         Term *term;
 425         FactorWithAug *factorWithAug;
 426         Type type;
 427
 428         /* Priority descriptor for RightFinish type. */
 429         PriorDesc priorDescs[2];
 430 };
 431
 432
 433 /* Third level of precedence. Augmenting nodes with actions and priorities. */
 434 struct FactorWithAug
 435 {
 436         FactorWithAug( FactorWithRep *factorWithRep ) :
 437                 priorDescs(0), factorWithRep(factorWithRep) { }
 438         ~FactorWithAug();
 439
 440         /* Tree traversal. */
 441         FsmAp *walk( ParseData *pd );
 442         void makeNameTree( ParseData *pd );
 443         void resolveNameRefs( ParseData *pd );
 444
 445         void assignActions( ParseData *pd, FsmAp *graph, int *actionOrd );
 446         void assignPriorities( FsmAp *graph, int *priorOrd );
 447
 448         void assignConditions( FsmAp *graph );
 449
 450         /* Actions and priorities assigned to the factor node. */
 451         Vector<ParserAction> actions;
 452         Vector<PriorityAug> priorityAugs;
 453         PriorDesc *priorDescs;
 454         Vector<Label> labels;
 455         Vector<EpsilonLink> epsilonLinks;
 456         Vector<ParserAction> conditions;
 457
 458         FactorWithRep *factorWithRep;
 459 };
 460
 461 /* Fourth level of precedence. Trailing unary operators. Provide kleen star,
 462  * optional and plus. */
 463 struct FactorWithRep
 464 {
 465         enum Type {
 466                 StarType,
 467                 StarStarType,
 468                 OptionalType,
 469                 PlusType,
 470                 ExactType,
 471                 MaxType,
 472                 MinType,
 473                 RangeType,
 474                 FactorWithNegType
 475         };
 476
 477          FactorWithRep( const InputLoc &loc, FactorWithRep *factorWithRep,
 478                         int lowerRep, int upperRep, Type type ) :
 479                 loc(loc), factorWithRep(factorWithRep),
 480                 factorWithNeg(0), lowerRep(lowerRep),
 481                 upperRep(upperRep), type(type) { }
 482
 483         FactorWithRep( FactorWithNeg *factorWithNeg )
 484                 : factorWithNeg(factorWithNeg), type(FactorWithNegType) { }
 485
 486         ~FactorWithRep();
 487
 488         /* Tree traversal. */
 489         FsmAp *walk( ParseData *pd );
 490         void makeNameTree( ParseData *pd );
 491         void resolveNameRefs( ParseData *pd );
 492
 493         InputLoc loc;
 494         FactorWithRep *factorWithRep;
 495         FactorWithNeg *factorWithNeg;
 496         int lowerRep, upperRep;
 497         Type type;
 498
 499         /* Priority descriptor for StarStar type. */
 500         PriorDesc priorDescs[2];
 501 };
 502
 503 /* Fifth level of precedence. Provides Negation. */
 504 struct FactorWithNeg
 505 {
 506         enum Type {
 507                 NegateType,
 508                 CharNegateType,
 509                 FactorType
 510         };
 511
 512         FactorWithNeg( const InputLoc &loc, FactorWithNeg *factorWithNeg, Type type) :
 513                 loc(loc), factorWithNeg(factorWithNeg), factor(0), type(type) { }
 514
 515         FactorWithNeg( Factor *factor ) :
 516                 factorWithNeg(0), factor(factor), type(FactorType) { }
 517
 518         ~FactorWithNeg();
 519
 520         /* Tree traversal. */
 521         FsmAp *walk( ParseData *pd );
 522         void makeNameTree( ParseData *pd );
 523         void resolveNameRefs( ParseData *pd );
 524
 525         InputLoc loc;
 526         FactorWithNeg *factorWithNeg;
 527         Factor *factor;
 528         Type type;
 529 };
 530
 531 /*
 532  * Factor
 533  */
 534 struct Factor
 535 {
 536         /* Language elements a factor node can be. */
 537         enum Type {
 538                 LiteralType,
 539                 RangeType,
 540                 OrExprType,
 541                 RegExprType,
 542                 ReferenceType,
 543                 ParenType,
 544                 LongestMatchType,
 545         };
 546
 547         /* Construct with a literal fsm. */
 548         Factor( Literal *literal ) :
 549                 literal(literal), type(LiteralType) { }
 550
 551         /* Construct with a range. */
 552         Factor( Range *range ) :
 553                 range(range), type(RangeType) { }
 554
 555         /* Construct with the or part of a regular expression. */
 556         Factor( ReItem *reItem ) :
 557                 reItem(reItem), type(OrExprType) { }
 558
 559         /* Construct with a regular expression. */
 560         Factor( RegExpr *regExpr ) :
 561                 regExpr(regExpr), type(RegExprType) { }
 562
 563         /* Construct with a reference to a var def. */
 564         Factor( const InputLoc &loc, VarDef *varDef ) :
 565                 loc(loc), varDef(varDef), type(ReferenceType) {}
 566
 567         /* Construct with a parenthesized join. */
 568         Factor( Join *join ) :
 569                 join(join), type(ParenType) {}
 570
 571         /* Construct with a longest match operator. */
 572         Factor( LongestMatch *longestMatch ) :
 573                 longestMatch(longestMatch), type(LongestMatchType) {}
 574
 575         /* Cleanup. */
 576         ~Factor();
 577
 578         /* Tree traversal. */
 579         FsmAp *walk( ParseData *pd );
 580         void makeNameTree( ParseData *pd );
 581         void resolveNameRefs( ParseData *pd );
 582
 583         InputLoc loc;
 584         Literal *literal;
 585         Range *range;
 586         ReItem *reItem;
 587         RegExpr *regExpr;
 588         VarDef *varDef;
 589         Join *join;
 590         LongestMatch *longestMatch;
 591         int lower, upper;
 592         Type type;
 593 };
 594
 595 /* A range machine. Only ever composed of two literals. */
 596 struct Range
 597 {
 598         Range( Literal *lowerLit, Literal *upperLit )
 599                 : lowerLit(lowerLit), upperLit(upperLit) { }
 600
 601         ~Range();
 602         FsmAp *walk( ParseData *pd );
 603         bool verifyRangeFsm( FsmAp *rangeEnd );
 604
 605         Literal *lowerLit;
 606         Literal *upperLit;
 607 };
 608
 609 /* Some literal machine. Can be a number or literal string. */
 610 struct Literal
 611 {
 612         enum LiteralType { Number, LitString };
 613
 614         Literal( const Token &token, LiteralType type )
 615                 : token(token), type(type) { }
 616
 617         FsmAp *walk( ParseData *pd );
 618
 619         Token token;
 620         LiteralType type;
 621 };
 622
 623 /* Regular expression. */
 624 struct RegExpr
 625 {
 626         enum RegExpType { RecurseItem, Empty };
 627
 628         /* Constructors. */
 629         RegExpr() :
 630                 type(Empty), caseInsensitive(false) { }
 631         RegExpr(RegExpr *regExpr, ReItem *item) :
 632                 regExpr(regExpr), item(item),
 633                 type(RecurseItem), caseInsensitive(false) { }
 634
 635         ~RegExpr();
 636         FsmAp *walk( ParseData *pd, RegExpr *rootRegex );
 637
 638         RegExpr *regExpr;
 639         ReItem *item;
 640         RegExpType type;
 641         bool caseInsensitive;
 642 };
 643
 644 /* An item in a regular expression. */
 645 struct ReItem
 646 {
 647         enum ReItemType { Data, Dot, OrBlock, NegOrBlock };
 648
 649         ReItem( const InputLoc &loc, const Token &token )
 650                 : loc(loc), token(token), star(false), type(Data) { }
 651         ReItem( const InputLoc &loc, ReItemType type )
 652                 : loc(loc), star(false), type(type) { }
 653         ReItem( const InputLoc &loc, ReOrBlock *orBlock, ReItemType type )
 654                 : loc(loc), orBlock(orBlock), star(false), type(type) { }
 655
 656         ~ReItem();
 657         FsmAp *walk( ParseData *pd, RegExpr *rootRegex );
 658
 659         InputLoc loc;
 660         Token token;
 661         ReOrBlock *orBlock;
 662         bool star;
 663         ReItemType type;
 664 };
 665
 666 /* An or block item. */
 667 struct ReOrBlock
 668 {
 669         enum ReOrBlockType { RecurseItem, Empty };
 670
 671         /* Constructors. */
 672         ReOrBlock()
 673                 : type(Empty) { }
 674         ReOrBlock(ReOrBlock *orBlock, ReOrItem *item)
 675                 : orBlock(orBlock), item(item), type(RecurseItem) { }
 676
 677         ~ReOrBlock();
 678         FsmAp *walk( ParseData *pd, RegExpr *rootRegex );
 679
 680         ReOrBlock *orBlock;
 681         ReOrItem *item;
 682         ReOrBlockType type;
 683 };
 684
 685 /* An item in an or block. */
 686 struct ReOrItem
 687 {
 688         enum ReOrItemType { Data, Range };
 689
 690         ReOrItem( const InputLoc &loc, const Token &token )
 691                 : loc(loc), token(token), type(Data) {}
 692         ReOrItem( const InputLoc &loc, char lower, char upper )
 693                 : loc(loc), lower(lower), upper(upper), type(Range) { }
 694
 695         FsmAp *walk( ParseData *pd, RegExpr *rootRegex );
 696
 697         InputLoc loc;
 698         Token token;
 699         char lower;
 700         char upper;
 701         ReOrItemType type;
 702 };
 703
 704
 705 /*
 706  * Inline code tree
 707  */
 708 struct InlineList;
 709 struct InlineItem
 710 {
 711         enum Type
 712         {
 713                 Text, Goto, Call, Next, GotoExpr, CallExpr, NextExpr, Ret, PChar,
 714                 Char, Hold, Curs, Targs, Entry, Exec, LmSwitch, LmSetActId,
 715                 LmSetTokEnd, LmOnLast, LmOnNext, LmOnLagBehind, LmInitAct,
 716                 LmInitTokStart, LmSetTokStart, Break
 717         };
 718
 719         InlineItem( const InputLoc &loc, char *data, Type type ) :
 720                 loc(loc), data(data), nameRef(0), children(0), type(type) { }
 721
 722         InlineItem( const InputLoc &loc, NameRef *nameRef, Type type ) :
 723                 loc(loc), data(0), nameRef(nameRef), children(0), type(type) { }
 724
 725         InlineItem( const InputLoc &loc, LongestMatch *longestMatch,
 726                 LongestMatchPart *longestMatchPart, Type type ) : loc(loc), data(0),
 727                 nameRef(0), children(0), longestMatch(longestMatch),
 728                 longestMatchPart(longestMatchPart), type(type) { }
 729
 730         InlineItem( const InputLoc &loc, NameInst *nameTarg, Type type ) :
 731                 loc(loc), data(0), nameRef(0), nameTarg(nameTarg), children(0),
 732                 type(type) { }
 733
 734         InlineItem( const InputLoc &loc, Type type ) :
 735                 loc(loc), data(0), nameRef(0), children(0), type(type) { }
 736
 737         InputLoc loc;
 738         char *data;
 739         NameRef *nameRef;
 740         NameInst *nameTarg;
 741         InlineList *children;
 742         LongestMatch *longestMatch;
 743         LongestMatchPart *longestMatchPart;
 744         Type type;
 745
 746         InlineItem *prev, *next;
 747 };
 748
 749 /* Normally this would be atypedef, but that would entail including DList from
 750  * ptreetypes, which should be just typedef forwards. */
 751 struct InlineList : public DList<InlineItem> { };
 752
 753
 754
 755 #endif /* _PARSETREE_H */