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