prop-src/parser.pcc

   1 ///////////////////////////////////////////////////////////////////////////////
   2 //
   3 //      ////////
   4 //     //     //   //////   /////   ///////
   5 //    ////////   //       //   //  //    //
   6 //   //         //       //   //  ///////
   7 //  //         //        /////   //
   8 //                              //      Version 2.3.x
   9 //
  10 //                                      Allen Leung (leunga@cs.nyu.edu)
  11 ///////////////////////////////////////////////////////////////////////////////
  12 #include <stdlib.h>
  13 #include <iostream>
  14 #include <AD/strings/charesc.h>
  15 #include <AD/strings/quark.h>
  16 #include "options.h"
  17 #include "basics.h"
  18 #include "ir.ph"
  19 #include "ast.ph"
  20 #include "parser.ph"
  21 #include "parsegen.ph"
  22 #include "setl-ast.ph"
  23 #include "keywords.ph"
  24 #include "timespace.ph"
  25 #include "type.h"
  26 #include "patenv.h"
  27 #include "compiler.h"
  28 #include "list.h"
  29 #include "matchcom.h"
  30 // #include "wam.h"
  31 // #include "bitfield.ph"
  32 // #include "constraint.ph"
  33 // #include "dataflow.ph"
  34 #include "graphtype.ph"
  35 #include "graphedges.ph"
  36 #include "grsgen.ph"
  37 #include "aggen.ph"
  38
  39 ///////////////////////////////////////////////////////////////////////////////
  40 //
  41 //  Datatypes for processing refine.
  42 //
  43 ///////////////////////////////////////////////////////////////////////////////
  44 datatype RefineTyDecl   : MEM = REFINEtype        (Id, Ids)
  45 and      RefineConsDecl : MEM = REFINEconstructor (Cons, Tys)
  46 where type RefineTyDecls   = List<RefineTyDecl>
  47 and        RefineConsDecls = List<RefineConsDecl>
  48 and        LabTyList       = { lab_list : Ids, ty_list : Tys }
  49 and        QualIdPat       = { label : QualId, pat : Pat }
  50 ;
  51 instantiate datatype RefineTyDecl, RefineConsDecl;
  52
  53 ///////////////////////////////////////////////////////////////////////////////
  54 //  Functions to mark a tree with the current location.
  55 ///////////////////////////////////////////////////////////////////////////////
  56 extern Pat  mark(Pat  p);
  57 extern Exp  mark(Exp  e);
  58 extern Decl mark(Decl d);
  59
  60 ///////////////////////////////////////////////////////////////////////////////
  61 //
  62 //  Functions to build lists.
  63 //
  64 ///////////////////////////////////////////////////////////////////////////////
  65 extern Pat mklistpat  (Id cons, Id nil, Pats ps, Pat p = NOpat);
  66 extern Pat mkvecpat   (Id, Pat, Pat, Pats, Bool = false, Bool  = false);
  67 extern Exp mklistexp  (Id, Id, Exps, Exp = NOexp);
  68 extern Exp mkappexp   (Exp, Exp);
  69 extern Exp mkvecexp   (Id, Exps);
  70 extern Pat extuplepat (Pats);
  71 extern Exp extupleexp (Exps);
  72 extern Ty  extuplety  (Tys);
  73 extern TermDef mklistterm(Id, Ty, Ty, Decls);
  74
  75 ///////////////////////////////////////////////////////////////////////////////
  76 //
  77 //  The Grammar of Prop
  78 //
  79 ///////////////////////////////////////////////////////////////////////////////
  80 syntax PropParser
  81 {
  82
  83 ///////////////////////////////////////////////////////////////////////////////
  84 //
  85 //  Operator precedence
  86 //
  87 ///////////////////////////////////////////////////////////////////////////////
  88 left: 25 ',';
  89 left: 24 '?';
  90 left: 23 "as";
  91 left: 22 "::";
  92 left: 21 "||";
  93 left: 20 "equiv:";
  94 left: 19 "xor:";
  95 left: 18 "implies:";
  96 left: 17 "&&" "and";
  97 right: 16 "|=" "&=" "^=" "<<=" ">>=";
  98 right: 15 '=' ":=" "+=" "-=" "*=" "/=" "%=";
  99 left: 14 '|';
 100 left: 13 ':';
 101 left: 12 ';';
 102 left: 11 '^';
 103 left: 10 '&';
 104 left: 9 "==" "!=";
 105 left: 8 '<' '>' ">=" "<=";
 106 left: 7 "<<" ">>";
 107 left: 6 '+' '-' "with" "less";
 108 left: 5 '*' '/' '%';
 109 left: 4 "++" "--";
 110 left: 3 '!' '~' "arb" "dom" "ran";
 111 left: 2 '[' ']' '{' '}' '.' "->" ;
 112 // left: 1 APP;
 113 left: 1 "class" "const" "collectable" "finalizable" "unsigned" "signed";
 114 expect: 2;
 115
 116 ///////////////////////////////////////////////////////////////////////////////
 117 //
 118 //  Declarations
 119 //
 120 ///////////////////////////////////////////////////////////////////////////////
 121 top:    decl_list       { program = $1; };
 122
 123 ///////////////////////////////////////////////////////////////////////////////
 124 //
 125 //  Special keywords
 126 //
 127 ///////////////////////////////////////////////////////////////////////////////
 128 rewrite_(int):          "rewrite"       { Used::rewriting = Used::quark = true; $$ = line; };
 129 syntax_(int):           "syntax"        { Used::parser = true; $$ = line; };
 130 case_(int):             "case"          { $$ = line; };
 131 lexeme_(int):           "lexeme"        { $$ = line; };
 132 inference_(int):        "inference"     { Used::infer = true; $$ = line; };
 133 persistent_(int):       "persistent"    { Used::persistence = true; $$ = line; };
 134 traced_(int):           "traced"        { Used::refcount = true; $$ = line; };
 135 collectable_(int):      "collectable"   { Used::gc = true; $$ = line; };
 136 finalizable_(int):      "finalizable"   { Used::gc = true; $$ = line; };
 137 printable_(int):        "printable"     { Used::printer = true; $$ = line; };
 138 unifiable_(int):        "unifiable"     { Used::unification = true; $$ = line; };
 139 match_or_matchall(MatchOptions):
 140         "match"         { $$ = MATCHnone; }
 141 |       "match" '*'     { $$ = MATCHnone | MATCHcaseinsensitive; }
 142 |       "matchall"      { $$ = MATCHall; }
 143 |       "matchall" '*'  { $$ = MATCHall | MATCHcaseinsensitive; }
 144 |       "matchscan"     { $$ = MATCHscanner; }
 145 |       "matchscan" '*' { $$ = MATCHscanner | MATCHcaseinsensitive; }
 146 ;
 147 where_or_if:            "if" | "where" | '|'
 148 ;
 149 implies :               LONG_BAR | "=>"
 150 ;
 151 negate:          '~' | '!'
 152 ;
 153
 154
 155 ///////////////////////////////////////////////////////////////////////////////
 156 //
 157 //  Literals
 158 //
 159 ///////////////////////////////////////////////////////////////////////////////
 160 id(Id):                 ID_TOK          { $$ = Quark(lexbuf.text()); };
 161 poly_datatype(Id):      POLY_DATATYPE   { $$ = Quark(lexbuf.text()); };
 162 cons(Cons):             CONS_TOK        { $$ = my_cons; };
 163 id_or_cons(Id):         id              { $$ = $1; }
 164 |                       cons            { $$ = $1->name; }
 165 ;
 166 cons_or_string(Id):     id_or_cons      { $$ = $1; }
 167 |                       string          { $$ = Quark($1); }
 168 ;
 169 cons_id(Cons):          CONS_EXP        { $$ = my_cons; };
 170 string(const char *):   STRING_TOK      { $$ = str_pool(lexbuf.text(),lexbuf.length()); };
 171 regexp(const char *):   REGEXP_TOK      { $$ = str_pool(lexbuf.text(),lexbuf.length()); };
 172 quark(Id):              QUARK_TOK
 173                         { $$ = str_pool(lexbuf.text()+1,lexbuf.length()-1);
 174                           compiler->quark_name($$);
 175                           Used::quark = true;
 176                         };
 177 bigint(Id):             BIGINT_TOK
 178                         { $$ = str_pool(lexbuf.text()+1,lexbuf.length()-1);
 179                           Used::bigint = true;
 180                         };
 181 meta_quote(const char *):
 182                         META_QUOTE      { $$ = str_pool(meta.text(),meta.length());
 183                                           meta.reset();
 184                                         };
 185 integer(int):           INT_TOK         { $$ = atol(lexbuf.text()); };
 186 real(double):           REAL_TOK        { $$ = atof(lexbuf.text()); };
 187 character(char):        CHAR_TOK        { parse_char(lexbuf.text()+1,$$); };
 188 boolean(Bool):  "false"         { $$ = false; }
 189 |               "true"          { $$ = true; }
 190 ;
 191
 192 complex_cons(Cons):
 193                 cons                    { $$ = $1; }
 194 |               '#' '[' ']'             { $$ = lookup_cons("#[]"); }
 195 |               '#' '(' ')'             { $$ = lookup_cons("#()"); }
 196 |               '#' '{' '}'             { $$ = lookup_cons("#{}"); }
 197 |               '#' '[' "..." ']'       { $$ = lookup_cons("#[...]"); }
 198 |               '#' '(' "..." ')'       { $$ = lookup_cons("#(...)"); }
 199 |               '#' '{' "..." '}'       { $$ = lookup_cons("#{...}"); }
 200 |               "[|" "..." "|]"         { $$ = lookup_cons("[|...|]"); }
 201 |               "(|" "..." "|)"         { $$ = lookup_cons("(|...|)"); }
 202 |               "{|" "..." "|}"         { $$ = lookup_cons("{|...|}"); }
 203 ;
 204
 205 non_string_literal Literal:
 206         integer         { $$ = INTlit($1); }
 207 |       boolean         { $$ = BOOLlit($1); }
 208 |       character       { $$ = CHARlit($1); }
 209 |       real            { $$ = REALlit($1); }
 210 |       quark           { $$ = QUARKlit($1); }
 211 |       bigint          { $$ = BIGINTlit($1); }
 212 ;
 213
 214 literal Literal:
 215         non_string_literal      { $$ = $1; }
 216 |       string                  { $$ = STRINGlit($1); }
 217 ;
 218
 219 ///////////////////////////////////////////////////////////////////////////////
 220 //
 221 //  Patterns
 222 //
 223 ///////////////////////////////////////////////////////////////////////////////
 224 top_pat(Pat):   pat                     { $$ = mark($1); }
 225 |               top_pat_list2           { $$ = mark(TUPLEpat($1)); }
 226 ;
 227
 228 pat(Pat):       simple_pat              { $$ = $1; }
 229 |               logical_pat             { $$ = $1; }
 230 ;
 231
 232 logical_pat(Pat):
 233         '!' pat                 { $$ = LOGICALpat(NOTpat,$2,NOpat); }
 234 |       pat "&&" pat            { $$ = LOGICALpat(ANDpat,$1,$3); }
 235 |       pat "||" pat            { $$ = LOGICALpat(ORpat,$1,$3); }
 236 |       pat "implies:" pat      { $$ = LOGICALpat(IMPLIESpat,$1,$3); }
 237 |       pat "xor:" pat          { $$ = LOGICALpat(XORpat,$1,$3); }
 238 |       pat "equiv:" pat        { $$ = LOGICALpat(EQUIVpat,$1,$3); }
 239 ;
 240
 241 simple_pat(Pat):        prim_pat        { $$ = $1; }
 242 |                       aggr_pat        { $$ = $1; }
 243 ;
 244
 245 prim_pat(Pat):
 246         id                      { $$ = lookup_patvar($1); }
 247 |       id "as" pat             { $$ = ASpat($1,$3,mkvar(),NOexp); }
 248 |       non_string_literal      { $$ = LITERALpat($1); }
 249 |       string_pat              { $$ = $1; }
 250 |       meta_quote              { $$ = compiler->parse_pat("",$1); }
 251 |       '_'                     { $$ = WILDpat(); }
 252 |       '(' ')'                 { $$ = TUPLEpat(#[]); }
 253 |       '(' pat ')'             { $$ = $2; }
 254 |       '(' pat_list2 ')'       { $$ = TUPLEpat($2); }
 255 |       '{' lab_pat_list '}'    { $$ = RECORDpat($2,false); }
 256 |       '{' lab_pat_list "..." '}'      { $$ = RECORDpat($2,true); }
 257 |       '(' pat ':' ty ')'              { $$ = TYPEDpat($2,$4); }
 258 |       cons                            { $$ = mkconspat($1); }
 259 |       cons simple_pat                 { $$ = APPpat(CONSpat($1),$2); }
 260 |       "<<" cons_list ">>" pat         { $$ = CONTEXTpat($2,$4); }
 261 |       id simple_pat
 262         {  Pat scheme = DatatypeCompiler::lookup_pat($1);
 263            if (scheme != NOpat) $$ = apply_pat(scheme, $2);
 264            else { lookup_cons($1); $$ = WILDpat(); }
 265         }
 266 ;
 267
 268 string_pat(Pat):
 269         regexp { $$ = mk_regexp_pat($1); Used::regexp = true; }
 270 |       string
 271         {  if (options.fast_string_match && ! in_rewrite) {
 272               $$ = ARRAYpat(make_string_pattern($1+1),false);
 273            } else {
 274               $$ = LITERALpat(STRINGlit($1)); Used::string_match = true;
 275            }
 276         }
 277 |       lexeme_ "class" id
 278         {  match (lookup_lexeme_class($3))
 279            {  termdefs as #[TERMdef { id = cons_name ... } ... _]:
 280               {  match (lookup_cons(cons_name))
 281                  {  ONEcons { alg_ty = ty as DATATYPEty({ terms ... },_),
 282                               tag ... }:
 283                        { $$ = LEXEMEpat($3, ty, length(termdefs), terms + tag); }
 284                  |  _: { $$ = LEXEMEpat($3, mkidty($3,#[]), 0, 0); }
 285                  }
 286               }
 287            |  _: { $$ = LEXEMEpat($3, mkidty($3,#[]), 0, 0); }
 288            }
 289            if (me_top >= 0) match_kind[me_top] |= MATCHlexemepat;
 290         }
 291 ;
 292
 293 cons_list(Conses):      cons                    { $$ = #[$1]; }
 294 |                       cons ',' cons_list      { $$ = #[$1 ... $3]; }
 295 ;
 296
 297 aggr_pat(Pat):
 298         '[' pat_list ']'                { $$ = ARRAYpat($2,false); }
 299 |       '[' pat_list "..." ']'          { $$ = ARRAYpat($2,true); }
 300 |       '#' '[' pat_list ']'            { $$ = mklistpat("#[...]","#[]",$3); }
 301 |       '#' '[' pat_list1 "..." pat ']' { $$ = mklistpat("#[...]","#[]",$3,$5);}
 302 |       '#' '{' pat_list '}'            { $$ = mklistpat("#{...}","#{}",$3); }
 303 |       '#' '{' pat_list1 "..." pat '}' { $$ = mklistpat("#{...}","#{}",$3,$5); }
 304 |       '#' '(' pat_list ')'            { $$ = mklistpat("#(...)","#()",$3); }
 305 |       '#' '(' pat_list1 "..." pat ')' { $$ = mklistpat("#(...)","#()",$3,$5); }
 306 |       "[|" "|]"                       { $$ = mkvecpat("[|...|]",NOpat,NOpat,#[]); }
 307 |       "(|" "|)"                       { $$ = mkvecpat("(|...|)",NOpat,NOpat,#[]); }
 308 |       "{|" "|}"                       { $$ = mkvecpat("{|...|}",NOpat,NOpat,#[]); }
 309 |       "[|" dots_opt pat_list1 dots_opt "|]"
 310            { $$ = mkvecpat("[|...|]",NOpat,NOpat,$3,$2,$4); }
 311 |       "(|" dots_opt pat_list1 dots_opt "|)"
 312            { $$ = mkvecpat("(|...|)",NOpat,NOpat,$3,$2,$4); }
 313 |       "{|" dots_opt pat_list1 dots_opt "|}"
 314            { $$ = mkvecpat("{|...|}",NOpat,NOpat,$3,$2,$4); }
 315 |       "[|" '|' pat pat_opt '|' dots_opt pat_list1 dots_opt "|]"
 316            { $$ = mkvecpat("[|...|]",$3,$4,$7,$6,$8); }
 317 |       "(|" '|' pat pat_opt '|' dots_opt pat_list1 dots_opt "|)"
 318            { $$ = mkvecpat("(|...|)",$3,$4,$7,$6,$8); }
 319 |       "{|" '|' pat pat_opt '|' dots_opt pat_list1 dots_opt "|}"
 320            { $$ = mkvecpat("{|...|}",$3,$4,$7,$6,$8); }
 321 |       ".(" pat_list2 ')'      { $$ = EXTUPLEpat($2); }
 322 ;
 323
 324 dots_opt(Bool):         { $$ = false; }
 325 |               "..."   { $$ = true; }
 326 ;
 327
 328 pat_opt(Pat):           { $$ = NOpat; }
 329 |               ':' pat { $$ = $2; }
 330 ;
 331
 332 lab_pat(LabPat):
 333                 id '=' pat      { $$.label = $1; $$.pat = $3; }
 334 |               id              { $$.label = $1; $$.pat = IDpat($1,mkvar(),NOexp); }
 335 ;
 336
 337 ///////////////////////////////////////////////////////////////////////////////
 338 //
 339 //  Pattern lists
 340 //
 341 ///////////////////////////////////////////////////////////////////////////////
 342 pat_list2(Pats):        big_pat ',' big_pat     { $$ = #[ $1, $3 ]; }
 343 |                       big_pat ',' pat_list2   { $$ = #[ $1 ... $3 ]; }
 344 ;
 345
 346 pat_list(Pats):                 { $$ = #[]; }
 347 |               pat_list1       { $$ = $1; }
 348 ;
 349
 350 pat_list1(Pats):        big_pat                 { $$ = #[ $1 ]; }
 351 |                       pat_list2               { $$ = $1; }
 352 ;
 353
 354 big_pat(Pat):   pat                     { $$ = $1; }
 355 |               pat ':' ty              { $$ = TYPEDpat($1,$3); }
 356 ;
 357
 358 top_pat_list2(Pats):    pat ',' pat             { $$ = #[ $1, $3 ]; }
 359 |                       pat ',' top_pat_list2   { $$ = #[ $1 ... $3 ]; }
 360 ;
 361
 362 lab_pat_list(LabPats):                  { $$ = #[]; }
 363 |               lab_pat_list1           { $$ = $1; }
 364 ;
 365
 366 lab_pat_list1(LabPats):
 367                 lab_pat                         { $$ = #[$1]; }
 368 |               lab_pat ',' lab_pat_list1       { $$ = #[$1 ... $3]; }
 369 ;
 370
 371 ///////////////////////////////////////////////////////////////////////////////
 372 //
 373 //  Type expressions
 374 //
 375 ///////////////////////////////////////////////////////////////////////////////
 376 long_ty(Ty):    ty1                     { $$ = $1; }
 377 |               long_ty "->" ty1        { $$ = mkfunty($1,$3); }
 378 ;
 379
 380 ty1(Ty):        "type"          { $$ = mktypety(); }
 381 |               ty              { $$ = $1; }
 382 ;
 383
 384 ty Ty:  ty '=' exp              { $$ = DEFVALty($1,$3); }
 385 |       simple_ty               { $$ = $1; }
 386 |       ty '*'                  { $$ = mkptrty($1); }
 387 |       ty '&'                  { $$ = mkrefty($1); }
 388 |       ty '[' ']'              { $$ = mkptrty($1); }
 389 |       ty '[' exp ']'          { $$ = mkarrayty($1,$3); }
 390 ;
 391
 392 return_ty(Ty):
 393         simple_ty1                      { $$ = $1; }
 394 |       return_ty '*'                   { $$ = mkptrty($1); }
 395 |       return_ty '&'                   { $$ = mkrefty($1); }
 396 |       return_ty '[' ']'               { $$ = mkptrty($1); }
 397 |       return_ty '[' exp ']'           { $$ = mkarrayty($1,$3); }
 398 ;
 399
 400 inherit_ty(Ty): id ty_args              { $$ = mkidty($1,$2); }
 401 ;
 402
 403 simple_ty1(Ty):
 404         "class" ty              { $$ = QUALty(QUALclass,$2); }
 405 |       "const" ty              { $$ = QUALty(QUALconst,$2); }
 406 |       "collectable" ty        { $$ = QUALty(QUALcollectable,$2); }
 407 |       "finalizable" ty        { $$ = QUALty(QUALfinalizable | QUALcollectable,$2); }
 408 |       "unsigned" ty           { $$ = QUALty(QUALunsigned,$2); }
 409 |       "signed" ty             { $$ = QUALty(QUALsigned,$2); }
 410 |       qualified_ty            { $$ = $1; }
 411 |       '(' ')'                 { $$ = mktuplety(#[]); }
 412 |       '(' ty ')'              { $$ = $2; }
 413 |       '(' ty_list2 ')'        { $$ = mktuplety($2); }
 414 |       ".[" ty_list2 ']'       { $$ = extuplety($2); }
 415 |       setl_ty                 { $$ = $1; }
 416 ;
 417
 418 simple_ty(Ty):
 419         simple_ty1              { $$ = $1; }
 420 |       labeled_ty              { $$ = $1; }
 421 ;
 422
 423 labeled_ty(Ty): '{' lab_ty_list '}'     { $$ = mkrecordty($2.lab_list,$2.ty_list,false); }
 424 ;
 425
 426 qualified_ty(Ty):       id_ty                   { $$ = $1; }
 427 |                       qualified_ty "::" id_ty { $$ = NESTEDty($1,$3); }
 428 ;
 429
 430 qual_id(QualId): id                     { $$ = SIMPLEid($1); }
 431 |                id_ty "::" qual_id     { $$ = NESTEDid($1,$3); }
 432 ;
 433
 434 id_ty(Ty):      id                      { $$ = lookup_tyvar($1); }
 435 |               id '<' ty_list '>'      { $$ = mkidty($1, $3); }
 436 ;
 437
 438 lab_ty(LabTy):  id ':' ty       { $$.label = $1; $$.ty = $3; }
 439 ;
 440
 441 ty_args(Tys):                   { $$ = #[]; }
 442 |               '<' ty_list '>' { $$ = $2; }
 443 ;
 444
 445 ty_list(Tys):   ty              { $$ = #[ $1 ]; }
 446 |               ty_list2        { $$ = $1; }
 447 ;
 448
 449 ty_list2(Tys):  ty ',' ty       { $$ = #[ $1, $3 ]; }
 450 |               ty ',' ty_list2 { $$ = #[ $1 ... $3 ]; }
 451 ;
 452
 453 lab_ty_list(LabTyList):         { $$.lab_list = #[]; $$.ty_list = #[]; }
 454 |               lab_ty          { $$.lab_list = #[ $1.label ];
 455                                   $$.ty_list  = #[ $1.ty ];
 456                                 }
 457 |               lab_ty_list2    { $$ = $1; }
 458 ;
 459
 460 lab_ty_list2(LabTyList):
 461                 lab_ty ',' lab_ty
 462                 { $$.lab_list = #[ $1.label, $3.label ];
 463                   $$.ty_list  = #[ $1.ty, $3.ty ];
 464                 }
 465 |               lab_ty ',' lab_ty_list2
 466                 { $$.lab_list = #[ $1.label ... $3.lab_list ];
 467                   $$.ty_list  = #[ $1.ty ... $3.ty_list ];
 468                 }
 469 ;
 470
 471 ///////////////////////////////////////////////////////////////////////////////
 472 //
 473 //  Expressions
 474 //
 475 ///////////////////////////////////////////////////////////////////////////////
 476 exp(Exp):
 477         app_exp                 { $$ = $1; }
 478 |       exp '+' exp             { $$ = BINOPexp("+",$1,$3); }
 479 |       exp '-' exp             { $$ = BINOPexp("-",$1,$3); }
 480 |       exp '*' exp             { $$ = BINOPexp("*",$1,$3); }
 481 |       exp '/' exp             { $$ = BINOPexp("/",$1,$3); }
 482 |       exp '%' exp             { $$ = BINOPexp("%",$1,$3); }
 483 |       exp '=' exp             { $$ = ASSIGNexp($1,$3); }
 484 |       exp ":=" exp            { $$ = ASSIGNexp($1,$3); }
 485 |       exp '<' exp             { $$ = BINOPexp("<",$1,$3); }
 486 |       exp '>' exp             { $$ = BINOPexp(">",$1,$3); }
 487 |       exp '|' exp             { $$ = BINOPexp("|",$1,$3); }
 488 |       exp '&' exp             { $$ = BINOPexp("&",$1,$3); }
 489 |       exp '^' exp             { $$ = BINOPexp("^",$1,$3); }
 490 |       exp "+=" exp            { $$ = BINOPexp("+=",$1,$3); }
 491 |       exp "-=" exp            { $$ = BINOPexp("-=",$1,$3); }
 492 |       exp "*=" exp            { $$ = BINOPexp("*=",$1,$3); }
 493 |       exp "/=" exp            { $$ = BINOPexp("/=",$1,$3); }
 494 |       exp "%=" exp            { $$ = BINOPexp("%=",$1,$3); }
 495 |       exp "&=" exp            { $$ = BINOPexp("&=",$1,$3); }
 496 |       exp "|=" exp            { $$ = BINOPexp("|=",$1,$3); }
 497 |       exp "^=" exp            { $$ = BINOPexp("^=",$1,$3); }
 498 |       exp ">=" exp            { $$ = BINOPexp(">=",$1,$3); }
 499 |       exp "<=" exp            { $$ = BINOPexp("<=",$1,$3); }
 500 |       exp "==" exp            { $$ = BINOPexp("==",$1,$3); }
 501 |       exp "!=" exp            { $$ = BINOPexp("!=",$1,$3); }
 502 |       exp "||" exp            { $$ = BINOPexp("||",$1,$3); }
 503 |       exp "&&" exp            { $$ = BINOPexp("&&",$1,$3); }
 504 |       exp "<<" exp            { $$ = BINOPexp("<<",$1,$3); }
 505 |       exp ">>" exp            { $$ = BINOPexp(">>",$1,$3); }
 506 |       exp "<<=" exp           { $$ = BINOPexp("<<=",$1,$3); }
 507 |       exp ">>=" exp           { $$ = BINOPexp(">>=",$1,$3); }
 508 |       exp "++"                { $$ = POSTFIXexp("++",$1); }
 509 |       exp "--"                { $$ = POSTFIXexp("--",$1); }
 510 |       '-' exp                 { $$ = PREFIXexp("-",$2); }
 511 |       '!' exp                 { $$ = PREFIXexp("!",$2); }
 512 |       "++" exp                { $$ = PREFIXexp("++",$2); }
 513 |       "--" exp                { $$ = PREFIXexp("--",$2); }
 514 |       '&' exp                 { $$ = PREFIXexp("&",$2); }
 515 |       '~' exp                 { $$ = PREFIXexp("~",$2); }
 516 |       '*' exp                 { $$ = DEREFexp($2); }
 517 |       exp '?' exp ':' exp     { $$ = IFexp($1,$3,$5); }
 518 |       setl_exp                { $$ = $1; }
 519 ;
 520
 521 app_exp(Exp):   simple_exp              { $$ = $1; }
 522 |               app_exp simple_exp      { $$ = mkappexp($1,$2); }
 523 ;
 524
 525 primitive_app_exp(Exp): primitive_exp                   { $$ = $1; }
 526 |                       primitive_app_exp simple_exp    { $$ = mkappexp($1,$2); }
 527 ;
 528
 529 primitive_exp(Exp):
 530         id              { $$ = lookup_exp($1); }
 531 |       literal         { $$ = LITERALexp($1); }
 532 |       cons            { $$ = my_cons->ty == NOty
 533                              ? CONSexp(my_cons,#[],NOexp) : IDexp($1->name);
 534                         }
 535 ;
 536
 537 simple_exp(Exp):
 538         primitive_exp                   { $$ = $1; }
 539 |        '(' ')'                        { $$ = TUPLEexp(#[]); }
 540 |       '(' exp ')'                     { $$ = $2; }
 541 |       '(' exp_list2 ')'               { $$ = TUPLEexp($2); }
 542 |       tick '{' lab_exp_list '}'       { $$ = RECORDexp($3); }
 543 |       list_exp                        { $$ = $1; }
 544 |       cons_exp                        { $$ = $1; }
 545 |       meta_exp                        { $$ = $1; }
 546 |       simple_exp '.' id               { $$ = DOTexp($1,$3); }
 547 |       simple_exp '.' '#' integer      { $$ = DOTexp($1,Quark("_",$4)); }
 548 |       simple_exp '[' exp ']'          { $$ = INDEXexp($1,$3); }
 549 |       simple_exp "->" id              { $$ = ARROWexp($1,$3); }
 550 |       simple_exp "->" '#' integer     { $$ = ARROWexp($1,Quark("_",$4)); }
 551 |       id "::" id                      { $$ = QUALexp(lookup_tyvar($1),$3); }
 552 ;
 553
 554 tick:
 555 |       '\'' tick
 556 ;
 557
 558 list_exp(Exp):
 559         '#' '[' exp_list ']'    { $$ = mklistexp("#[...]","#[]",$3); }
 560 |       '#' '(' exp_list ')'    { $$ = mklistexp("#(...)","#()",$3); }
 561 |       '#' '{' exp_list '}'    { $$ = mklistexp("#{...}","#{}",$3); }
 562 |       '#' '[' exp_list "..." exp ']'  { $$ = mklistexp("#[...]","#[]",$3,$5); }
 563 |       '#' '(' exp_list "..." exp ')'  { $$ = mklistexp("#(...)","#()",$3,$5); }
 564 |       '#' '{' exp_list "..." exp '}'  { $$ = mklistexp("#{...}","#{}",$3,$5); }
 565 |       "[|" exp_list "|]"      { $$ = mkvecexp("[|...|]",$2); }
 566 |       "(|" exp_list "|)"      { $$ = mkvecexp("(|...|)",$2); }
 567 |       "{|" exp_list "|}"      { $$ = mkvecexp("{|...|}",$2); }
 568 |       ".(" exp_list2 ')'      { $$ = extupleexp($2); }
 569 ;
 570
 571 cons_exp(Exp):  cons_id tick '{' lab_exp_list '}'
 572                 { $$ = CONSexp($1,#[],RECORDexp($4)); }
 573 |               cons_id tick '(' exp_list ')' '{' lab_exp_list '}'
 574                 { $$ = CONSexp($1,$4,RECORDexp($7)); }
 575 |               cons_id tick '(' exp_list ')' '(' exp_list ')'
 576                 { $$ = CONSexp($1,$4,TUPLEexp($7)); }
 577 ;
 578
 579 meta_exp(Exp):  meta_quote
 580                 { $$ = compiler->parse_exp("",$1); }
 581 ;
 582
 583 lab_exp(LabExp):        id '=' exp      { $$.label = $1; $$.exp = $3; }
 584 ;
 585
 586 paren_exp(Exp): '(' exp ')'     { $$ = $2; }
 587 ;
 588
 589 ///////////////////////////////////////////////////////////////////////////////
 590 //
 591 // Expression lists
 592 //
 593 ///////////////////////////////////////////////////////////////////////////////
 594 exp_list(Exps):                 { $$ = #[]; }
 595 |               exp             { $$ = #[ $1 ]; }
 596 |               exp_list2       { $$ = $1; }
 597 ;
 598
 599 exp_list2(Exps):
 600                 exp ',' exp             { $$ = #[ $1, $3 ]; }
 601 |               exp ',' exp_list2       { $$ = #[ $1 ... $3 ]; }
 602 ;
 603
 604 lab_exp_list(LabExps):          { $$ = #[]; }
 605 |               lab_exp         { $$ = #[ $1 ]; }
 606 |               lab_exp_list2   { $$ = $1; }
 607 ;
 608
 609 lab_exp_list2(LabExps):
 610                 lab_exp ',' lab_exp             { $$ = #[ $1, $3 ]; }
 611 |               lab_exp ',' lab_exp_list2       { $$ = #[ $1 ... $3 ]; }
 612 ;
 613
 614 ///////////////////////////////////////////////////////////////////////////////
 615 //
 616 //  Pattern matching rules
 617 //
 618 ///////////////////////////////////////////////////////////////////////////////
 619 match_decl(Decl):
 620                 match_or_matchall match_ty match_options match_exps
 621                 { compute_match_variables(me_stack[++me_top] = $4);
 622                   match_kind[me_top] = $1;
 623                   match_rule = 0;
 624                 }
 625                 '{' case_or_bar_rules '}'
 626                 { $$ = MATCHdecl($4,$7,$1 | $3 | match_kind[me_top],$2);
 627                   me_top--;
 628                 }
 629 |               match_or_matchall match_ty match_options match_exps "of"
 630                 { compute_match_variables(me_stack[++me_top] = $4);
 631                   match_kind[me_top] = $1;
 632                   match_rule = 0;
 633                 }
 634                 case_or_bar_rules "end" "match" ';'
 635                 { $$ = MATCHdecl($4,$7,$1 | $3 | match_kind[me_top],$2);
 636                   me_top--;
 637                 }
 638 ;
 639
 640 match_options(MatchOptions):            { $$ = MATCHnone; }
 641 |                               "while" { $$ = MATCHwhile; }
 642 ;
 643
 644 match_ty(Ty):                   { $$ = NOty; }
 645 |               '[' ty ']'      { $$ = $2; }
 646 ;
 647
 648 match_exps(MatchExps):
 649                 match_exp                       { $$ = #[ $1 ]; }
 650 |               match_exp "and" match_exps      { $$ = #[ $1 ... $3 ]; }
 651 ;
 652
 653 match_exp(MatchExp):    paren_exp { $$ = MATCHexp(mark($1),0); }
 654 ;
 655
 656 case_or_bar_rules(MatchRules):
 657                         case_rules      { $$ = $1; }
 658 |                       bar_rules       { $$ = $1; }
 659 ;
 660
 661 case_rules(MatchRules):
 662                 a_case_rule             { $$ = #[ $1 ]; }
 663 |               a_case_rule case_rules  { $$ = #[ $1 ... $2 ]; }
 664 ;
 665
 666 bar_rules(MatchRules):
 667                 a_bar_rule                      { $$ = #[ $1 ]; }
 668 |               a_bar_rule '|' bar_rules        { $$ = #[ $1 ... $3 ]; }
 669 ;
 670
 671 a_case_rule MatchRule:
 672                 rewrite_mode case_rule { $$ = $2; }
 673 ;
 674
 675 a_bar_rule MatchRule:
 676                 rewrite_mode bar_rule rewrite_mode { $$ = $2; }
 677 ;
 678
 679 case_rule(MatchRule):
 680                 case_ top_pat
 681                 { pv_env.new_scope(! options.nonlinear_patterns);
 682                   decor(me_stack[me_top],$2,pv_env,match_rule);
 683                   if (in_rewrite) {
 684                      decor_rewrite($2,rule_count,pv_env); rule_count++;
 685                   }
 686                 }
 687                 guard_exp cost ':'
 688                 { start_statement(); }
 689                 decl_list
 690                 { end_statement();
 691                   $$ = MATCHrule(0,$2,pv_env.guard($4),$5,$8);
 692                   $$->begin_line = $1;
 693                   $$->mode = rw_stack[rw_top].mode;
 694                   $$->option = rw_stack[rw_top].option;
 695                   pv_env.old_scope();
 696                   match_rule++;
 697                 }
 698 ;
 699
 700 guard_exp(Exp):                 { $$ = NOexp; }
 701 |               where_or_if exp { $$ = mark($2); }
 702 ;
 703
 704 bar_rule(MatchRule):
 705                 line_number id_or_cons "->" top_pat
 706                 { pv_env.new_scope(! in_rewrite && ! options.nonlinear_patterns,
 707                                    in_rewrite,
 708                                    rw_stack[rw_top].qual & QUALtreeparser);
 709                   decor(me_stack[me_top],$4,pv_env,match_rule);
 710                   if (in_rewrite) {
 711                      decor_rewrite($4,rule_count,pv_env); rule_count++;
 712                   }
 713                 }
 714                 guard_exp cost ':' bar_rule_action
 715                 { $$ = MATCHrule($2,$4,pv_env.guard($6),$7,$9);
 716                   $$->begin_line = $1;
 717                   pv_env.old_scope();
 718                   match_rule++;
 719                 }
 720 |               line_number top_pat
 721                 { pv_env.new_scope(! options.nonlinear_patterns,
 722                                    in_rewrite,
 723                                    rw_stack[rw_top].qual & QUALtreeparser);
 724                   decor(me_stack[me_top],$2,pv_env,match_rule);
 725                   if (in_rewrite) {
 726                      decor_rewrite($2,rule_count,pv_env); rule_count++;
 727                   }
 728                 }
 729                 guard_exp cost ':' bar_rule_action
 730                 { $$ = MATCHrule(0,$2,pv_env.guard($4),$5,$7);
 731                   $$->begin_line = $1;
 732                   $$->mode = rw_stack[rw_top].mode;
 733                   $$->option = rw_stack[rw_top].option;
 734                   pv_env.old_scope();
 735                   match_rule++;
 736                 }
 737 ;
 738
 739 line_number(int):       { $$ = line; }
 740 ;
 741
 742 bar_rule_action(Decls):
 743                 brace_body                      { $$ = $1; }
 744 |               replacement_decl semi_opt       { $$ = #[ mark($1) ]; }
 745 |               replacement_exp_decl semi_opt   { $$ = $1; }
 746 |               return_exp semi_opt             { $$ = $1; }
 747 |               compound_stmt                   { $$ = #[mark(SETLSTMTdecl($1))]; }
 748 |                                               { $$ = #[]; }
 749 ;
 750
 751 replacement_exp_decl(Decls):
 752         replacement_exp
 753         {  if (in_rewrite) {
 754               $$ = #[ mark(REPLACEMENTdecl($1,rw_stack[rw_top].mode))];
 755               rw_stack[rw_top].option |= MatchRuleInfo::REPLACEMENT;
 756            } else {
 757               $$ = #[ mark(EXPdecl{ prefix = "",
 758                                     exp    = $1,
 759                                     suffix = ";" }) ];
 760            }
 761         }
 762 ;
 763
 764 return_exp(Decls):      "return" replacement_exp
 765                         { $$ = #[ mark(EXPdecl{ prefix = "return ",
 766                                          exp    = $2,
 767                                          suffix = ";"
 768                                        }) ];
 769                         }
 770 ;
 771
 772 semi_opt:       | ';'
 773 ;
 774
 775 replacement_exp(Exp):
 776                  primitive_app_exp      { $$ = $1; }
 777 |                list_exp               { $$ = $1; }
 778 |                '(' exp ')'            { $$ = $2; }
 779 ;
 780
 781 cost(Cost):     { $$ = NOcost; }
 782 |               '\\' exp
 783                 {  match ($2)
 784                    {  LITERALexp (INTlit i):
 785                       { if (i < 0) error ("%Lnegative cost %i is illegal\n",i);
 786                         if (i <= 0) $$ = NOcost;
 787                         else        $$ = INTcost(i);
 788                       }
 789                    |  e: { $$ = EXPcost(e,NOty); }
 790                    }
 791                 }
 792 ;
 793
 794 brace_body(Decls):
 795                 '{'
 796                 { start_statement(); first_line = line; }
 797                 decl_list
 798                 { this->end_statement(); }
 799                 '}'
 800                 { $$ = $3; first_line = line; }
 801 ;
 802
 803 begin_end_body Decls:
 804                 "begin"
 805                 { start_statement(); first_line = line; }
 806                 decl_list
 807                 { this->end_statement(); }
 808                 "end"
 809 ;
 810
 811 brace_body_opt(Decls):                  { $$ = #[]; }
 812 |                       brace_body      { $$ = $1; }
 813 ;
 814
 815 ///////////////////////////////////////////////////////////////////////////////
 816 //
 817 //  Scoping
 818 //
 819 ///////////////////////////////////////////////////////////////////////////////
 820 scope(Scope):   "public"        { $$ = PUBLICscope; }
 821 |               "protected"     { $$ = PROTECTEDscope; }
 822 |               "private"       { $$ = PRIVATEscope; }
 823 ;
 824
 825 scope_opt(Scope):               { $$ = PUBLICscope; }
 826 |               scope           { $$ = $1; }
 827 ;
 828
 829 ///////////////////////////////////////////////////////////////////////////////
 830 //
 831 //  Prop declarations
 832 //
 833 ///////////////////////////////////////////////////////////////////////////////
 834 decl(Decl):     one_decl
 835                 { $$ = options.emit_code ? mark($1) : NOdecl; end_sc(); }
 836 |               ATTRIB_ID
 837                 { $$ = options.emit_code ? EXPdecl(my_exp) : NOdecl; end_sc(); }
 838 |               "classof" id_or_cons
 839                 { $$ = options.emit_code ? CLASSOFdecl($2) : NOdecl; end_sc(); }
 840 |               typeexp_decl
 841                 { $$ = options.emit_code ? $1 : NOdecl; end_sc(); }
 842 ;
 843
 844 one_decl(Decl):
 845         datatype_decl           { $$ = $1; }
 846 |       type_decl               { $$ = $1; }
 847 |       refine_decl             { $$ = $1; }
 848 |       instantiate_decl        { $$ = $1; }
 849 |       inference_class_decl    { $$ = $1; }
 850 |       inference_decl          { $$ = $1; }
 851 // |    constraint_decl         { $$ = $1; }
 852 |       rewrite_class_decl      { $$ = $1; }
 853 |       rewrite_decl            { $$ = $1; }
 854 |       rewriting_decl          { $$ = $1; }
 855 |       syntax_class_decl       { $$ = $1; }
 856 |       syntax_decl             { $$ = $1; }
 857 |       attribgram_class_decl   { $$ = $1; }
 858 |       attribgram_decl         { $$ = $1; }
 859 |       fun_decl                { $$ = $1; }
 860 |       match_decl              { $$ = $1; }
 861 |       exp_decl                { $$ = $1; }
 862 |       replacement_decl ';'    { $$ = $1; }
 863 |       lexeme_decl             { $$ = NOdecl; }
 864 // |    bitfield_decl           { $$ = $1; }
 865 |       compound_stmt           { $$ = SETLSTMTdecl($1); }
 866 |       compound_def            { $$ = SETLDEFdecl($1); }
 867 |       graph_class_decl        { $$ = $1; }
 868 |       graph_rewrite_decl      { $$ = $1; }
 869 //|     dataflow_class_decl     { $$ = $1; }
 870 //|     dataflow_decl           { $$ = $1; }
 871 |       ? ';'                   { $$ = NOdecl; }
 872 ;
 873
 874 ///////////////////////////////////////////////////////////////////////////////
 875 //
 876 //  Declaration lists
 877 //
 878 ///////////////////////////////////////////////////////////////////////////////
 879 decl_list(Decls):
 880                 { $$ = mkcode(#[]); }
 881 |               { if (code_top >= MAX_LEXICAL_DEPTH)
 882                      bug("code stack overflow");
 883                   code_stack[code_top++] = mkcode(#[]);
 884                 }
 885                 decl decl_list
 886                 { if (code_top <= 0) bug ("code stack underflow");
 887                   $$ = code_stack[--code_top];
 888                   if ($$ == #[])
 889                     if ($2 == NOdecl) $$ = $3;
 890                     else $$ = #[ $2 ... $3 ];
 891                   else
 892                     if ($2 == NOdecl) $$->_2 = $3;
 893                     else $$->_2 = #[ $2 ... $3 ];
 894                 }
 895 ;
 896
 897 ///////////////////////////////////////////////////////////////////////////////
 898 //
 899 //  Bitfield declaration
 900 //
 901 ///////////////////////////////////////////////////////////////////////////////
 902 /*
 903  *  Ignore for now
 904 bitfield_decl(Decl):
 905                 "bitfield" id '(' integer ')' '=' field_defs
 906                 opt_field_laws ';'
 907                 { $$ = BITFIELDdecl''{
 908                           name        = $2,
 909                           width       = $4,
 910                           field_names = $7,
 911                           laws        = $8
 912                        };
 913                 }
 914 ;
 915
 916 field_defs(FieldDefs):
 917                 field_def                       { $$ = #[ $1 ]; }
 918 |               field_def '|' field_defs        { $$ = #[ $1 ... $3 ]; }
 919 ;
 920
 921 field_def(FieldDef):
 922                 id_or_cons '(' integer ':' integer ')' signedness
 923                 { $$ = FIELDdef''{ field_name = $1,
 924                                    from_bit   = $3,
 925                                    to_bit     = $5,
 926                                    is_signed  = $7
 927                                  };
 928                 }
 929 |               id_or_cons ty
 930                 { $$ = FIELDCONdef''{ field_name = $1, ty = $2 }; }
 931 ;
 932
 933 signedness(Bool):
 934                 "signed"        { $$ = true; }
 935 |               "unsigned"      { $$ = false; }
 936 |                               { $$ = false; }
 937 ;
 938
 939 opt_field_laws(FieldLaws):              { $$ = #[]; }
 940 |               "law" field_laws        { $$ = $2; }
 941 ;
 942
 943 field_laws(FieldLaws):
 944                 field_law                       { $$ = #[$1]; }
 945 |               field_law "and" field_laws      { $$ = #[$1 ... $3]; }
 946 ;
 947
 948 field_law(FieldLaw):
 949                 id
 950                 { var_top = 0; }
 951                 patvars guard_exp2 '=' exp
 952                 { var_top = 0;
 953                   $$ = FIELDlaw''{ id = $1, args = $3, guard = $4, exp = $6 };
 954                 }
 955 ;
 956 */
 957
 958 ///////////////////////////////////////////////////////////////////////////////
 959 //
 960 //  Special expression declarations
 961 //
 962 ///////////////////////////////////////////////////////////////////////////////
 963 exp_decl(Decl): cons_exp        { $$ = EXPdecl($1); }
 964 |               list_exp        { $$ = EXPdecl($1); }
 965 |               quark           { $$ = EXPdecl(LITERALexp(QUARKlit($1))); }
 966 |               bigint          { $$ = EXPdecl(LITERALexp(BIGINTlit($1))); }
 967 |               meta_exp        { $$ = EXPdecl($1); }
 968 ;
 969
 970 typeexp_decl(Decl):     poly_datatype '<' ty_list '>'
 971                                 { $$ = TYPEEXPdecl(TYCONty(IDtycon($1),$3)); }
 972 |                       ".[" ty_list2 ']'
 973                                 { $$ = TYPEEXPdecl(extuplety($2)); }
 974 ;
 975
 976 ///////////////////////////////////////////////////////////////////////////////
 977 //
 978 //  Datatype declarations
 979 //
 980 ///////////////////////////////////////////////////////////////////////////////
 981 datatype_decl(Decl):
 982                 "datatype" datatype_defs0 view_defs_opt law_defs_opt ty_defs_opt ';'
 983                 { $$ = DATATYPEdecl($2,$3,$4,$5); }
 984 ;
 985
 986 datatype_defs0(DatatypeDefs):                   { $$ = #[]; }
 987 |               datatype_defs                   { $$ = $1; }
 988 ;
 989
 990 datatype_defs(DatatypeDefs):
 991                 datatype_def                     { $$ = #[ $1 ]; }
 992 |               datatype_def "and" datatype_defs { $$ = #[ $1 ... $3 ]; }
 993 ;
 994
 995 datatype_def(DatatypeDef):
 996                 id tyvars inherit_list_opt qualifiers_opt '='
 997                 {  // add hook for view accessors expressions
 998                    if (is_view_def = ($4 & QUALview))
 999                    {  Ty junk_ty = NOty;
1000                       pv_env.new_scope();
1001                       pv_env.add(#"this",RELexp(0),junk_ty);
1002                    }
1003                 }
1004                 switch_exp
1005                 terms
1006                 {  var_top = 0;
1007                    if (is_view_def) // view accessors
1008                    {  pv_env.old_scope();
1009                       is_view_def = false;
1010                    }
1011                 }
1012                 datatype_body
1013                 { $$ = DATATYPEdef($1,$2,$3,$4,$8,$10);
1014                   compiler->preprocess_def($$);
1015                   match ($$)
1016                   {  DATATYPEdef(_,_,_,_,terms,_):
1017                      { add_datatype($$->loc(),$1,$2,$3,$4,$7,terms,$10); }
1018                   }
1019                 }
1020 |               id tyvars inherit_list_opt qualifiers_opt
1021                 { $$ = DATATYPEdef($1,$2,$3,$4,#[],#[]); var_top = 0; }
1022 ;
1023
1024 switch_exp(Exp):                        { $$ = NOexp; }
1025 |                "match" paren_exp      { $$ = $2; }
1026 ;
1027
1028 datatype_body(Decls):                   { $$ = #[]; }
1029 |               scope ':' brace_body    { $$ = $3; }
1030 ;
1031
1032 tyvars(TyVars):                         { $$ = #[]; }
1033 |               '<' var_list '>'        { $$ = $2; }
1034 ;
1035
1036 var(TyVar):     id
1037                 { $$ = var_stack[var_top] = $1;
1038                   pat_stack[var_top] = NOpat;
1039                   var_top++;
1040                 }
1041 ;
1042
1043 var_list0(TyVars):                      { $$ = #[]; }
1044 |                       var_list        { $$ = $1; }
1045 ;
1046
1047 var_list(TyVars):       var                     { $$ = #[ $1 ]; }
1048 |                       var ',' var_list        { $$ = #[ $1 ... $3 ]; }
1049 ;
1050
1051 terms(TermDefs):                        { $$ = #[]; }
1052 |               terms1                  { $$ = $1; }
1053 ;
1054
1055 terms1(TermDefs):
1056                 term                    { $$ = $1; }
1057 |               term '|' terms1         { $$ = append($1,$3); }
1058 ;
1059
1060 term(TermDefs): '_' inherit_list_opt opt_with
1061                 {  $$ = #[TERMdef{id = 0, inherits = $2, ty = NOty, decls = $3}]; }
1062 |               simple_term inherit_list_opt opt_with view_predicate
1063                 {  $1->inherits = $2;
1064                    $1->decls = $3;
1065                    if ($1->view_predicate == NOexp) $1->view_predicate = $4;
1066                    $$ = #[$1];
1067                 }
1068 |               simple_term inherit_list_opt "=>" print_formats opt_with
1069                 view_predicate
1070                 {  $1->inherits = $2;
1071                    $1->decls = $5;
1072                    $1->print_formats = $4;
1073                    Used::printer = true;
1074                    if ($1->view_predicate == NOexp) $1->view_predicate = $6;
1075                    $$ = #[$1];
1076                 }
1077 |               lexeme_ "class" id
1078                 { $$ = lookup_lexeme_class($3); }
1079 ;
1080
1081 view_predicate(Exp):                    { $$ = NOexp; }
1082 |               "if" app_exp            { $$ = $2; }
1083 ;
1084
1085 opt_with(Decls):                        { $$ = #[]; }
1086 |               "with" brace_body       { $$ = $2; }
1087 ;
1088
1089 ///////////////////////////////////////////////////////////////////////////////
1090 //
1091 //  Datatype terms.
1092 //
1093 ///////////////////////////////////////////////////////////////////////////////
1094 simple_term(TermDef):
1095         simple_term1             { $$ = $1; }
1096 |       simple_term1 '!'         { $$ = $1; $$->opt = OPTunboxed; }
1097 |       "view" exp "=>" simple_term { $$ = $4; $$->view_predicate = $2; }
1098 |       "virtual" simple_term    { $$ = $2; $$->qual |= QUALvirtualdestr; }
1099 ;
1100
1101 simple_term1(TermDef):
1102                 id_or_cons              { $$ = TERMdef''{ id = $1, ty = NOty }; }
1103 |               id_or_cons string       { $$ = TERMdef''{ id = $1, ty = NOty, pat = LITERALpat(STRINGlit($2)) }; }
1104 |               id_or_cons regexp       { $$ = TERMdef''{ id = $1, ty = NOty, pat = mk_regexp_pat($2) }; }
1105 |               id_or_cons "<=>" string
1106                 { $$ = TERMdef''{ id = $1, ty = NOty,
1107                                   pat = LITERALpat(STRINGlit($3)),
1108                                   print_formats = #[TERMSTRINGsym($3)]
1109                                 };
1110                   Used::printer = true;
1111                 }
1112 |               string
1113                 { $$ = TERMdef''{ id = $1, ty = NOty,
1114                                   print_formats = #[TERMSTRINGsym($1)]
1115                                 };
1116                   Used::printer = true;
1117                 }
1118 |               cons_or_string opt_of ty        { $$ = TERMdef''{ id = $1, ty = $3 }; }
1119 |               cons_or_string opt_of ty_list2  { $$ = TERMdef''{ id = $1, ty = mktuplety($3) }; }
1120 |               '#' '[' ']'             { $$ = TERMdef''{ id = "#[]", ty = NOty }; }
1121 |               '#' '(' ')'             { $$ = TERMdef''{ id = "#()", ty = NOty }; }
1122 |               '#' '{' '}'             { $$ = TERMdef''{ id = "#{}", ty = NOty }; }
1123 |               '#' '[' ty "..." ty ']' { $$ = mklistterm("#[...]",$3,$5,#[]); }
1124 |               '#' '(' ty "..." ty ')' { $$ = mklistterm("#(...)",$3,$5,#[]); }
1125 |               '#' '{' ty "..." ty '}' { $$ = mklistterm("#{...}",$3,$5,#[]); }
1126 |               "[|" ty "|]"            { $$ = TERMdef''{id = "[|...|]",ty = $2}; }
1127 |               "(|" ty "|)"            { $$ = TERMdef''{id = "(|...|)",ty = $2}; }
1128 |               "{|" ty "|}"            { $$ = TERMdef''{id = "{|...|}",ty = $2}; }
1129 ;
1130
1131 opt_of:
1132 |               "of"
1133 ;
1134
1135 ///////////////////////////////////////////////////////////////////////////////
1136 //
1137 //  Pretty printing formats
1138 //
1139 ///////////////////////////////////////////////////////////////////////////////
1140 print_formats(PrintFormats):                    { $$ = #[]; }
1141 |               print_format print_formats      { $$ = #[ $1 ... $2 ]; }
1142 ;
1143
1144 print_format ProductionSymbol:
1145                 integer                 { $$ = POSNONTERMsym($1); }
1146 |               id                      { $$ = NONTERMsym($1); }
1147 |               string                  { $$ = TERMSTRINGsym($1); }
1148 |               character               { $$ = TERMsym($1); }
1149 |               special_print_format    { $$ = SPECIALsym($1); }
1150 ;
1151
1152 special_print_format(char):
1153                 '{'             { $$ = '{'; }
1154 |               '}'             { $$ = '}'; }
1155 |               '('             { $$ = '('; }
1156 |               ')'             { $$ = ')'; }
1157 |               '['             { $$ = '['; }
1158 |               ']'             { $$ = ']'; }
1159 |               '^'             { $$ = '^'; }
1160 |               '_'             { $$ = '_'; }
1161 |               '/'             { $$ = '/'; }
1162 ;
1163
1164 ty_defs_opt(TyDefs):                            { $$ = #[]; }
1165 |               "where" "type" type_defs        { $$ = $3; }
1166 ;
1167
1168 type_decl(Decl): "type" type_defs ';'    { $$ = DATATYPEdecl(#[],#[],#[],$2); }
1169 ;
1170
1171 type_defs(TyDefs):
1172                 type_def                        { $$ = #[ $1 ]; }
1173 |               type_def and_or_bar type_defs   { $$ = #[ $1 ... $3 ]; }
1174 ;
1175
1176 type_def(TyDef):
1177                 sharing_opt id tyvars '=' ty
1178                 { $$ = TYdef($2,$3,$5,$1);
1179                   add_type($2,$3,$5);
1180                   var_top = 0;
1181                 }
1182 ;
1183
1184 sharing_opt(Bool):              { $$ = true; }
1185 |               "sharing"       { $$ = false; }
1186 ;
1187
1188 view_defs_opt(ViewDefs):                        { $$ = #[]; }
1189 |               "type" "view" id view_defs      { $$ = $4; }
1190 ;
1191
1192 view_defs(ViewDefs):    view_def                { $$ = #[ $1 ]; }
1193 |                       view_def '|' view_defs  { $$ = #[ $1 ... $3 ]; }
1194 ;
1195
1196 view_def(ViewDef):
1197                 { pv_env.new_scope(! options.nonlinear_patterns); }
1198                 simple_pat ':' app_exp selectors_opt
1199                 { $$ = VIEWdef($2,$4,$5);
1200                   pv_env.old_scope();
1201                 }
1202 ;
1203
1204 selectors_opt(LabExps):                 { $$ = #[]; }
1205 |                       "and" selectors { $$ = $2; }
1206 ;
1207
1208 selectors(LabExps):
1209                 selector                        { $$ = #[ $1 ]; }
1210 |               selector "and" selectors        { $$ = #[ $1 ... $3 ]; }
1211 ;
1212
1213 selector(LabExp):
1214                 id '=' app_exp  { $$.label = $1; $$.exp = $3; }
1215 ;
1216
1217 ///////////////////////////////////////////////////////////////////////////////
1218 //
1219 //  Pattern law definitions
1220 //
1221 ///////////////////////////////////////////////////////////////////////////////
1222 law_defs_opt(LawDefs):                  { $$ = #[]; }
1223 |                       "law" law_defs  { $$ = $2; }
1224 ;
1225
1226 law_defs(LawDefs):
1227                 law_def                         { $$ = #[ $1 ]; }
1228 |               law_def and_or_bar law_defs     { $$ = #[ $1 ... $3 ]; }
1229 ;
1230
1231 and_or_bar:     "and" | '|'
1232 ;
1233
1234 law_def(LawDef):
1235                 invertible
1236                 id
1237                 { var_top = 0; }
1238                 patvars guard_exp2 '=' pat
1239                 { $$ = LAWdef''{ id = $2, args = $4,
1240                                  guard = $5, pat = $7, invert = $1 };
1241                   var_top = 0;
1242                   DatatypeCompiler::add_law($$);
1243                 }
1244 ;
1245
1246 invertible(Bool):       "inline"        { $$ = true; }
1247 |                                       { $$ = false; }
1248 ;
1249
1250 guard_exp2(Exp):                        { $$ = NOexp; }
1251 |               where_or_if paren_exp   { $$ = $2; }
1252 ;
1253
1254 patvars(TyVars):                        { $$ = #[]; }
1255 |               var_list                { $$ = $1; }
1256 |               '(' var_list0 ')'       { $$ = $2; }
1257 ;
1258
1259 ///////////////////////////////////////////////////////////////////////////////
1260 //
1261 //  Datatype refinement declarations.
1262 //
1263 ///////////////////////////////////////////////////////////////////////////////
1264 refine_decl(Decl):
1265                 "refine" refine_defs ';'        { $$ = NOdecl; }
1266 ;
1267
1268 refine_defs:    refine_def
1269 |               refine_def "and" refine_defs
1270 ;
1271
1272 refine_def:     refine_ty_list inherit_list_opt qualifiers_opt brace_body_opt
1273                 {  for_each (RefineTyDecl, r, $1)
1274                    {  match (r)
1275                       {  REFINEtype(id,tys):
1276                          { update_datatype(id,tys,$2,$3,$4); }
1277                       }
1278                    }
1279                 }
1280 |               refine_cons_list inherit_list_opt brace_body_opt
1281                 {  for_each (RefineConsDecl, r, $1)
1282                    {  match (r)
1283                       {  REFINEconstructor(c,tys):
1284                          { if (c) update_constructor(c->name, tys, $2, #[], $3);
1285                          }
1286                       }
1287                    }
1288                 }
1289 |               printable_ printing_decls { }
1290 |               persistent_ persistent_decls { }
1291 |               "class" id_or_cons "::" id_or_cons '(' ')' brace_body
1292                 {  ClassDefinition::add_constructor_code($2,$4,$7);
1293                 }
1294 |               "class" id_or_cons "::" '~' id_or_cons '(' ')' brace_body
1295                 {  ClassDefinition::add_destructor_code($2,$5,$8);
1296                 }
1297 ;
1298
1299 refine_ty(RefineTyDecl):
1300                 id tyvars { $$ = REFINEtype($1,$2); var_top = 0; }
1301 ;
1302
1303 refine_ty_list(RefineTyDecls):
1304                 refine_ty                       { $$ = #[ $1 ]; }
1305 |               refine_ty ',' refine_ty_list    { $$ = #[ $1 ... $3 ]; }
1306 ;
1307
1308 refine_cons(RefineConsDecl):
1309                 complex_cons ty_args { $$ = REFINEconstructor($1,$2); }
1310 ;
1311
1312 refine_cons_list(RefineConsDecls):
1313                 refine_cons                      { $$ = #[ $1 ]; }
1314 |               refine_cons ',' refine_cons_list { $$ = #[ $1 ... $3 ]; }
1315 ;
1316
1317 ///////////////////////////////////////////////////////////////////////////////
1318 //
1319 //  Pretty printing declarations.
1320 //
1321 ///////////////////////////////////////////////////////////////////////////////
1322 printing_decls: printing_decl
1323 |               printing_decl '|' printing_decls
1324 ;
1325
1326 printing_decl:  complex_cons ty_args "=>" print_formats
1327                 { if ($1) update_constructor($1->name,$2,#[],$4,#[]); }
1328 ;
1329
1330 ///////////////////////////////////////////////////////////////////////////////
1331 //
1332 //  Persistence ID definition
1333 //
1334 ///////////////////////////////////////////////////////////////////////////////
1335 persistent_decls: persistent_decl
1336 |                 persistent_decl '|' persistent_decls
1337 ;
1338
1339 persistent_decl: id ty_args "=>" pid { update_persistent($1,$2,$4); }
1340 ;
1341
1342 pid(Pid):       string  { $$ = PERSISTid($1); }
1343 ;
1344
1345 inherit_list_opt(Inherits):             { $$ = #[]; }
1346 |               ':' inherit_list        { $$ = $2; }
1347 ;
1348
1349 inherit_list(Inherits):
1350                 inherit                         { $$ = #[ $1 ]; }
1351 |               inherit ',' inherit_list        { $$ = #[ $1 ... $3 ]; }
1352 ;
1353
1354 inherit(Inherit):
1355                 qualifiers scope_opt inherit_ty
1356                 { $$ = INHERIT'{ qualifiers = $1,
1357                                  scope = $2,
1358                                  super_class = $3};
1359                 }
1360 ;
1361
1362 qualifiers_opt(TyQual):                 { $$ = 0; }
1363 |               '!' qualifiers_opt      { $$ = $2 | QUALtaggedpointer; }
1364 |               "::" qualifiers         { $$ = $2; }
1365 ;
1366
1367 qualifiers(TyQual):                     { $$ = 0; }
1368 |               qualifier qualifiers    { $$ = $1 | $2; }
1369 ;
1370
1371 qualifier(TyQual):
1372                 printable_      { $$ = QUALprintable; }
1373 |               collectable_    { $$ = QUALcollectable | QUALvirtualdestr; }
1374 |               lexeme_         { $$ = QUALlexeme; }
1375 |               finalizable_    { $$ = QUALfinalizable | QUALcollectable | QUALvirtualdestr; }
1376 |               rewrite_        { $$ = QUALrewritable; }
1377 |               persistent_     { $$ = QUALpersistent | QUALvirtualdestr; }
1378 |               traced_         { $$ = QUALtracable; }
1379 |               unifiable_      { $$ = QUALunifiable; }
1380 |               "relation"      { $$ = QUALrelation | QUALvirtualdestr; Used::infer = true; }
1381 |               "virtual"       { $$ = QUALvirtual; }
1382 |               "const"         { $$ = QUALconst; }
1383 |               "applicative"   { $$ = QUALapplicative; }
1384 |               "treeparser"    { $$ = QUALtreeparser; }
1385 |               "view"          { $$ = QUALview; }
1386 |               "bitfield"      { $$ = QUALbitfield; }
1387 |               "inline"        { $$ = QUALinline; }
1388 |               "extern"        { $$ = QUALextern; }
1389 ;
1390
1391 ///////////////////////////////////////////////////////////////////////////////
1392 //
1393 //  Datatype instantiation declaration
1394 //
1395 ///////////////////////////////////////////////////////////////////////////////
1396 instantiate_decl(Decl): "instantiate" extern_opt "datatype" ty_list ';'
1397                         { $$ = INSTANTIATEdecl($2,$4); }
1398 ;
1399
1400 extern_opt(Bool):                       { $$ = false; }
1401 |                       "extern"        { $$ = true; }
1402 ;
1403
1404 ///////////////////////////////////////////////////////////////////////////////
1405 //
1406 //  Inference class declaration
1407 //
1408 ///////////////////////////////////////////////////////////////////////////////
1409 inference_class_decl(Decl):
1410                 inference_ "class" id
1411                 inherit_list_opt qualifiers_opt brace_body ';'
1412                 { $$ = CLASSDEFdecl(new InferenceClass($3,$4,$5,$6)); }
1413 ;
1414
1415 ///////////////////////////////////////////////////////////////////////////////
1416 //
1417 //  Inference declaration
1418 //
1419 ///////////////////////////////////////////////////////////////////////////////
1420 inference_decl(Decl):   inference_ id '{' inference_rules '}' ';'
1421                         { $$ = INFERENCEdecl($2,$4); }
1422 ;
1423
1424 inference_rules(InferenceRules):                { $$ = #[]; }
1425 |               inference_rule inference_rules  { $$ = #[ $1 ... $2 ]; }
1426 ;
1427
1428 inference_rule(InferenceRule):
1429                 { antecedent_count = 0;
1430                   me_stack[++me_top] = #[];
1431                   pv_env.new_scope(! options.nonlinear_patterns, true);
1432                 }
1433                 antecedents LONG_BAR conclusions ';'
1434                 { $$ = INFERENCErule($2, pv_env.guard(), $4);
1435                   me_top--;
1436                   pv_env.old_scope();
1437                 }
1438 ;
1439
1440 antecedents(MatchRules):                        { $$ = #[]; }
1441 |               antecedents2                    { $$ = $1; }
1442 ;
1443
1444 antecedents2(MatchRules):
1445                 antecedent                      { $$ = #[ $1 ]; }
1446 |               antecedent "and" antecedents2   { $$ = #[ $1 ... $3 ]; }
1447 ;
1448
1449 antecedent(MatchRule):
1450                 simple_antecedent
1451                 { $$ = $1; $$->negated = false; $$->rewriting = false; }
1452 |               "match" simple_antecedent
1453                 { $$ = $2; $$->negated = false; $$->rewriting = true; }
1454 |               '~' simple_antecedent
1455                 { $$ = $2; $$->negated = true; $$->rewriting = false; }
1456 ;
1457
1458 simple_antecedent(MatchRule):
1459                 pat
1460                 { me_stack[me_top] = #[];
1461                   decor(me_stack[me_top],$1,pv_env,match_rule,antecedent_count);
1462                   $$ = MATCHrule(0,$1,NOexp,NOcost,#[]);
1463                   $$->ty = NOty;
1464                   antecedent_count++;
1465                 }
1466 |               pat where_or_if
1467                 { me_stack[me_top] = #[];
1468                   decor(me_stack[me_top],$1,pv_env,match_rule,antecedent_count);
1469                 }
1470                 exp
1471                 { $$ = MATCHrule(0,$1,$4,NOcost,#[]);
1472                   $$->ty = NOty;
1473                   antecedent_count++;
1474                 }
1475 ;
1476
1477 conclusions(Conclusions):
1478                 conclusion                      { $$ = #[ $1 ]; }
1479 |               conclusion "and" conclusions    { $$ = #[ $1 ... $3 ]; }
1480 ;
1481
1482 conclusion(Conclusion):
1483                 primitive_app_exp       { $$ = ASSERTaction($1); }
1484 |               '~' primitive_app_exp   { $$ = RETRACTaction($2); }
1485 |               brace_body              { $$ = STMTaction($1); }
1486 ;
1487
1488 ///////////////////////////////////////////////////////////////////////////////
1489 //
1490 //  Syntax class declaration
1491 //
1492 ///////////////////////////////////////////////////////////////////////////////
1493 syntax_class_decl(Decl):
1494         syntax_ "class" id inherit_list_opt qualifiers_opt brace_body ';'
1495         {  $$ = CLASSDEFdecl(
1496                new SyntaxClass(ClassDefinition::SYNTAX_CLASS, $3,$4,$5,$6));
1497         }
1498 ;
1499
1500 ///////////////////////////////////////////////////////////////////////////////
1501 //
1502 //  Syntax declaration
1503 //
1504 ///////////////////////////////////////////////////////////////////////////////
1505 syntax_decl(Decl):      syntax_ id
1506                         { symbol_count = 0; }
1507                         '{' prec_rules expect_
1508                         { symbol_count = 0; }
1509                             bnf_rules
1510                         '}' ';'
1511                         { $$ = SYNTAXdecl ($2,EXPgram($5,$6,$8)); }
1512 ;
1513
1514 prec_rules(PrecRules):                          { $$ = #[]; }
1515 |                       prec_rule prec_rules    { $$ = #[ $1 ... $2 ]; }
1516 ;
1517
1518 prec_rule(PrecRule):    "left:" integer production ';'
1519                         { $$ = PRECrule(LEFTassoc, $2, $3); }
1520 |                       "right:" integer production ';'
1521                         { $$ = PRECrule(RIGHTassoc, $2, $3); }
1522 ;
1523
1524 expect_(int):                                   { $$ = -1; }
1525 |                       "expect:" integer ';'   { $$ = $2; }
1526 |                       "expect:" '_' ';'       { $$ = -2; }
1527 ;
1528
1529 bnf_rules(BNFs):                                { $$ = #[]; }
1530 |                       bnf_rule bnf_rules      { $$ = #[ $1 ... $2 ]; }
1531 ;
1532
1533 bnf_rule(BNF):          line_number id ty_opt ':' alt_productions ';'
1534                         {  $$ = BNFrule($2,$3,$5); $$->begin_line = $1; }
1535 ;
1536
1537 ///////////////////////////////////////////////////////////////////////////////
1538 //
1539 //  Attribute grammar class declaration
1540 //
1541 ///////////////////////////////////////////////////////////////////////////////
1542 attribgram_class_decl Decl:
1543         "attributegrammar" "class"
1544            id inherit_list_opt qualifiers_opt brace_body ';'
1545         {  Used::parser = true;
1546            $$ = CLASSDEFdecl(new AttributeGrammarClass($3,$4,$5,$6));
1547         }
1548 ;
1549
1550 ///////////////////////////////////////////////////////////////////////////////
1551 //
1552 //  Attribute grammar declaration
1553 //
1554 ///////////////////////////////////////////////////////////////////////////////
1555 attribgram_decl Decl:   "attributegrammar" id
1556                         { symbol_count = 0; }
1557                         '{' prec_rules expect_
1558                         { symbol_count = 0; }
1559                             bnf_rules
1560                         '}' ';'
1561                         { $$ = ATTRIBUTEGRAMMARdecl ($2,EXPgram($5,$6,$8)); }
1562 ;
1563
1564 ///////////////////////////////////////////////////////////////////////////////
1565 //
1566 //   Lexeme declaration
1567 //
1568 ///////////////////////////////////////////////////////////////////////////////
1569 lexeme_decl:            lexeme_ lexeme_rules ';' { }
1570 |                       lexeme_ "class" lexeme_class_rules ';' { }
1571 ;
1572
1573 lexeme_rules:           lexeme_rule { }
1574 |                       lexeme_rule and_or_bar lexeme_rules { }
1575 ;
1576
1577 lexeme_rule:            id '=' string_pat
1578                         { update_lexeme($1,#[],$3); }
1579 ;
1580
1581 lexeme_class_rules:     lexeme_class_rule { }
1582 |                       lexeme_class_rule "and" lexeme_class_rules { }
1583 ;
1584
1585 lexeme_class_rule:      id '=' terms
1586                         { update_lexeme_class($1,$3); }
1587 ;
1588
1589 ty_opt(Ty):                     { $$ = NOty; }
1590 |                       ty      { $$ = $1; }
1591 ;
1592
1593 alt_productions(List<ProductionSymbols>):
1594                 production                      { $$ = #[ $1 ]; }
1595 |               production '|' alt_productions  { $$ = #[ $1 ... $3 ]; }
1596 ;
1597
1598 production(ProductionSymbols):
1599                 {  pv_env.new_scope();
1600                    ++symbol_count;
1601                    item_count = 0;
1602                    nonterm_count = 0;
1603                    add_parse_stack_binding(0,symbol_count,0);
1604                 }
1605                 a_production
1606                 {  $$ = $2;
1607                    pv_env.old_scope();
1608                 }
1609 ;
1610
1611 a_production(ProductionSymbols):
1612                                         { $$ = #[]; }
1613 |               { ++symbol_count; ++item_count; }
1614                 symbol a_production     { $$ = #[ $2 ... $3 ]; }
1615 ;
1616
1617 symbol(ProductionSymbol):
1618                 id              { $$ = NONTERMsym($1);
1619                                   ++nonterm_count;
1620                                   add_parse_stack_binding(item_count,symbol_count,nonterm_count);
1621                                 }
1622 |               cons            { $$ = TOKENsym($1); }
1623 |               character       { $$ = TERMsym($1); }
1624 |               string          { $$ = TOKENsym(lookup_token($1)); }
1625 |               regexp          { $$ = TERMREGEXPsym($1); }
1626 |               paren_exp       { ++nonterm_count; $$ = PREDICATEsym($1); }
1627 |               brace_body      { ++nonterm_count; $$ = ACTIONsym($1); }
1628 |               '?'             { $$ = ERRORsym(); }
1629 |               "prec:" cons    { $$ = PRECsym($2); }
1630 ;
1631
1632 ///////////////////////////////////////////////////////////////////////////////
1633 //
1634 //  Rewriting class declaration
1635 //
1636 ///////////////////////////////////////////////////////////////////////////////
1637 rewrite_class_decl(Decl):
1638         rewrite_ "class" id '(' protocols ')'
1639         inherit_list_opt
1640         qualifiers_opt
1641         brace_body ';'
1642         { $$ = CLASSDEFdecl(new RewriteClass($3,$5,$7,$8,$9)); }
1643 ;
1644
1645 protocols_opt(Protocols):                       { $$ = #[]; }
1646 |                       '(' protocols ')'       { $$ = $2; }
1647 ;
1648
1649 protocols(Protocols):   protocol                { $$ = #[ $1 ]; }
1650 |                       protocol ',' protocols  { $$ = #[ $1 ... $3 ]; }
1651 ;
1652
1653 protocol(Protocol):     ty inherited_opt synthesized_opt
1654                         { $$ = PROTOCOL($1,$2,$3); }
1655 ;
1656
1657 inherited_opt(Ty):                              { $$ = NOty; }
1658 |                       "inherited" ty          { $$ = $2; }
1659 ;
1660
1661 synthesized_opt(Ty):                            { $$ = NOty; }
1662 |                       "synthesized" ty        { $$ = $2; }
1663 |                       ':' ty                  { $$ = $2; }
1664 ;
1665
1666 ///////////////////////////////////////////////////////////////////////////////
1667 //
1668 //   Rewriting declaration
1669 //
1670 ///////////////////////////////////////////////////////////////////////////////
1671 rewrite_decl(Decl):     rewrite_ id
1672                         { in_rewrite = true;
1673                           rule_count = 0;
1674                           push_rw_stack();
1675                           ClassDefinition * C =
1676                              ClassDefinition::lookup_class(
1677                                 ClassDefinition::REWRITE_CLASS,$2);
1678                           if (C) rw_stack[rw_top].qual = C->qualifiers;
1679                           me_stack[++me_top] = #[ MATCHexp(IDexp("redex"),0) ];
1680                         }
1681                         '{' rewrite_indexings case_or_bar_rules '}' ';'
1682                         { $$ = REWRITEdecl($2,$5,$6);
1683                           in_rewrite = false; me_top--;
1684                           pop_rw_stack();
1685                         }
1686 ;
1687
1688 rewriting_decl(Decl):   rewrite_ paren_exp opt_dest "type" '(' protocols ')'
1689                         qualifiers_opt
1690                         { in_rewrite = true;
1691                           rule_count = 0;
1692                           me_stack[++me_top] = #[ MATCHexp(IDexp("redex"),0) ];
1693                           push_rw_stack();
1694                           rw_stack[rw_top].qual = $8;
1695                         }
1696                         '{' rewrite_indexings case_or_bar_rules '}'
1697                         { $$ = REWRITINGdecl($6,$2,$3,$11,$12,$8);
1698                           in_rewrite = false; me_top--;
1699                           pop_rw_stack();
1700                         }
1701 |                       rewrite_ paren_exp opt_dest "type" '(' protocols ')'
1702                         qualifiers_opt
1703                         { in_rewrite = true;
1704                           rule_count = 0;
1705                           me_stack[++me_top] = #[ MATCHexp(IDexp("redex"),0) ];
1706                           push_rw_stack();
1707                           rw_stack[rw_top].qual = $8;
1708                         }
1709                         "of" rewrite_indexings case_or_bar_rules
1710                         "end" "rewrite" ';'
1711                         { $$ = REWRITINGdecl($6,$2,$3,$11,$12,$8);
1712                           in_rewrite = false; me_top--;
1713                           pop_rw_stack();
1714                         }
1715 ;
1716
1717 rewrite_indexings RewriteIndexings:
1718         "index:" rewrite_indices ';'    { $$ = $2; }
1719 |                                       { $$ = #[]; }
1720 ;
1721
1722 rewrite_indices RewriteIndexings:
1723         rewrite_index                           { $$ = #[$1]; }
1724 |       rewrite_index ',' rewrite_indices       { $$ = #[$1 ... $3]; }
1725 ;
1726
1727 rewrite_index RewriteIndexing *:
1728         simple_ty '=' id_or_cons
1729                 { $$ = new RewriteIndexing($1,$3,false); }
1730 |       simple_ty '=' "extern" id_or_cons
1731                 { $$ = new RewriteIndexing($1,$4,true); }
1732 ;
1733
1734 opt_dest(Exp):                  { $$ = NOexp; }
1735 |               "=>" exp        { $$ = $2; }
1736 ;
1737
1738 replacement_decl(Decl):
1739         rewrite_ paren_exp
1740         {  if (in_rewrite) {
1741               $$ = REPLACEMENTdecl($2,rw_stack[rw_top].mode);
1742               rw_stack[rw_top].option |= MatchRuleInfo::REPLACEMENT;
1743            } else {
1744               error("%Lreplacement not in rewrite class: rewrite %e\n",$2);
1745               $$ = NOdecl;
1746            }
1747         }
1748 |       "cutrewrite" paren_exp
1749         { $$ = CUTREWRITEdecl($2,rw_stack[rw_top].mode);
1750           rw_stack[rw_top].option |= MatchRuleInfo::CUTREWRITE;
1751         }
1752 |       "cutrewrite"
1753         { $$ = CUTREWRITEdecl(NOexp,rw_stack[rw_top].mode);
1754           rw_stack[rw_top].option |= MatchRuleInfo::CUTREWRITE;
1755         }
1756 |       "failrewrite"
1757         { $$ = FAILREWRITEdecl(rw_stack[rw_top].mode);
1758           rw_stack[rw_top].option |= MatchRuleInfo::FAILREWRITE;
1759         }
1760 ;
1761
1762 rewrite_mode:
1763 |       "topdown:"      { rw_stack[rw_top].mode = MatchRuleInfo::TOPDOWN; }
1764 |       "bottomup:"     { rw_stack[rw_top].mode = MatchRuleInfo::BOTTOMUP; }
1765 |       "before:"       { rw_stack[rw_top].mode = MatchRuleInfo::BEFORE; }
1766 |       "preorder:"     { rw_stack[rw_top].mode = MatchRuleInfo::PREORDER; }
1767 |       "postorder:"    { rw_stack[rw_top].mode = MatchRuleInfo::POSTORDER; }
1768 ;
1769
1770 ///////////////////////////////////////////////////////////////////////////////
1771 //
1772 //   Function declaration
1773 //
1774 ///////////////////////////////////////////////////////////////////////////////
1775 fun_decl(Decl):         "fun" fun_rules_list ';'        { $$ = FUNdecl($2); }
1776 ;
1777
1778 fun_rules_list(FunDefs):
1779                 this_fun_rules
1780                 { $$ = #[ FUNdef($1.id, NOty, $1.return_ty, $1.rules) ]; }
1781 |               this_fun_rules "and" fun_rules_list
1782                 { $$ = #[ FUNdef($1.id, NOty, $1.return_ty, $1.rules) ... $3 ]; }
1783 ;
1784
1785 this_fun_rules(LabMatchRules):
1786                 { me_stack[++me_top] = #[]; }
1787                 fun_rules
1788                 { $$ = $2; me_top--; }
1789 ;
1790
1791 fun_rules(LabMatchRules):
1792                 fun_rule
1793                 { $$.id = $1.id; $$.rules = #[ $1.rule ];
1794                   $$.return_ty = $1.return_ty;
1795                 }
1796 |               fun_rule '|' fun_rules
1797                 { $$.id = $1.id; $$.rules = #[ $1.rule ... $3.rules ];
1798                   if ($1.return_ty == NOty) $$.return_ty = $3.return_ty;
1799                   else if ($3.return_ty == NOty) $$.return_ty = $1.return_ty;
1800                   else {
1801                      if (! unify($1.return_ty, $3.return_ty))
1802                         error("%Ltype mismatch in rule %r\n"
1803                               "%Lexpecting %T but found %T\n",
1804                               $1.rule, $1.return_ty, $3.return_ty);
1805                      $$.return_ty = $1.return_ty;
1806                   }
1807                   if (! qualid_equal($1.id, $3.id))
1808                      error("%Lfunction name mismatch: expecting %q ...\n"
1809                            "%Lbut found %q %r\n",
1810                            $1.id, $3.id, $1.rule);
1811                 }
1812 ;
1813
1814
1815 fun_rule_head(QualIdPat):
1816                 qual_id top_pat
1817                 { pv_env.new_scope(! options.nonlinear_patterns);
1818                   decor(me_stack[me_top],$2,pv_env,match_rule);
1819                   $$.label = $1; $$.pat = $2;
1820                 }
1821 ;
1822
1823 fun_rule(LabMatchRule):
1824                 fun_rule_head ':' return_ty where_or_if exp ':' fun_action
1825                 { $$.id = $1.label;
1826                   $$.rule = MATCHrule(0,$1.pat, $5, NOcost, $7);
1827                   $$.return_ty = $3;
1828                   pv_env.old_scope();
1829                 }
1830 |               fun_rule_head where_or_if exp ':' fun_action
1831                 { $$.id = $1.label;
1832                   $$.rule = MATCHrule(0,$1.pat, $3, NOcost, $5);
1833                   $$.return_ty = NOty;
1834                   pv_env.old_scope();
1835                 }
1836 |               fun_rule_head ':' return_ty ':' fun_action
1837                 { $$.id = $1.label;
1838                   $$.rule = MATCHrule(0,$1.pat, NOexp, NOcost, $5);
1839                   $$.return_ty = $3;
1840                   pv_env.old_scope();
1841                 }
1842 |               fun_rule_head ':' fun_action
1843                 { $$.id = $1.label;
1844                   $$.rule = MATCHrule(0,$1.pat, NOexp, NOcost, $3);
1845                   $$.return_ty = NOty;
1846                   pv_env.old_scope();
1847                 }
1848 ;
1849
1850 fun_action(Decls):      brace_body              { $$ = $1; }
1851 |                       return_exp              { $$ = $1; }
1852 //|                     replacement_exp_decl    { $$ = $1; }
1853 ;
1854
1855 ///////////////////////////////////////////////////////////////////////////////
1856 //
1857 //  Definitions
1858 //
1859 ///////////////////////////////////////////////////////////////////////////////
1860 def(Def):       id ':' ty ';'
1861                         { $$ = VARdef'{ id = $1, ty = $3 }; }
1862 |               id ':' ty ":=" exp ';'
1863                         { $$ = VARdef'{ id = $1, ty = $3, init_exp = $5 }; }
1864 |               datatype_decl   { $$ = TYPEdef($1); }
1865 |               type_decl       { $$ = TYPEdef($1); }
1866 |               compound_def    { $$ = $1; }
1867 ;
1868
1869 compound_def(Def):      function_def    { $$ = $1; }
1870 |                       module_def      { $$ = $1; }
1871 |                       signature_def   { $$ = $1; }
1872 ;
1873
1874 ///////////////////////////////////////////////////////////////////////////////
1875 //
1876 //  Function/procedure definition
1877 //
1878 ///////////////////////////////////////////////////////////////////////////////
1879 function_def(Def):
1880         "function" cons_or_string '(' fun_args ')' "return" ty "is"
1881         defs "begin" stmt_list "end" ';'
1882                 { $$ = FUNCTIONdef'{ id         = $2,
1883                                      args       = $4,
1884                                      return_ty  = $7,
1885                                      local_defs = $9,
1886                                      body       = $11
1887                                    };
1888                 }
1889
1890 |       "procedure" cons_or_string '(' fun_args ')' "is"
1891         defs "begin" stmt_list "end" ';'
1892                 { $$ = FUNCTIONdef'{ id         = $2,
1893                                      args       = $4,
1894                                      return_ty  = void_ty,
1895                                      local_defs = $7,
1896                                      body       = $9
1897                                    };
1898                 }
1899 ;
1900
1901 fun_args LabTys:                                { $$ = #[]; }
1902 |                       fun_args1               { $$ = $1; }
1903 ;
1904
1905 fun_args1 LabTys:       fun_arg                 { $$ = #[$1]; }
1906 |                       fun_arg ',' fun_args    { $$ = #[$1 ... $3]; }
1907 ;
1908
1909 fun_arg(LabTy):         id ':' ty               { $$.label = $1; $$.ty = $3; }
1910 ;
1911
1912 ///////////////////////////////////////////////////////////////////////////////
1913 //
1914 //  Module definition
1915 //
1916 ///////////////////////////////////////////////////////////////////////////////
1917 module_def(Def):        "module" cons_or_string module_args module_sig "is"
1918                         "begin" defs "end" ';'
1919                         { $$ = MODULEdef'{ id   = $2,
1920                                            args = $3,
1921                                            sig  = $4,
1922                                            body = $7
1923                                          };
1924                         }
1925 ;
1926
1927 module_args(LabSigs):                           { $$ = #[]; }
1928 |                       '(' labeled_sigs ')'    { $$ = $2; }
1929 ;
1930
1931 labeled_sigs(LabSigs):  labeled_sig                     { $$ = #[$1]; }
1932 |                       labeled_sig ',' labeled_sigs    { $$ = #[$1 ... $3]; }
1933 ;
1934
1935 labeled_sig(LabSig):    id ':' sig              { $$.id = $1; $$.sig = $3; }
1936 ;
1937
1938 module_sig(Sig):                        { $$ = NOsig; }
1939 |                       ':' sig         { $$ = $2; }
1940 ;
1941
1942 ///////////////////////////////////////////////////////////////////////////////
1943 //
1944 //  Signature definition
1945 //
1946 ///////////////////////////////////////////////////////////////////////////////
1947 signature_def(Def):     "signature" cons_or_string module_args "is" sig ';'
1948                         { $$ = SIGNATUREdef'{ id   = $2,
1949                                               args = $3,
1950                                               sig  = $5
1951                                             };
1952                         }
1953 ;
1954
1955 ///////////////////////////////////////////////////////////////////////////////
1956 //
1957 //  Signature expression
1958 //
1959 ///////////////////////////////////////////////////////////////////////////////
1960 sig(Sig):       id                      { $$ = IDsig($1); }
1961 |               sig '(' sigs ')'        { $$ = APPsig($1,$3); }
1962 |               sig '.' id              { $$ = DOTsig($1,$3); }
1963 |               "begin" defs "end"      { $$ = DEFsig($2); }
1964 ;
1965
1966 sigs(Sigs):     sig                     { $$ = #[$1]; }
1967 |               sig ',' sigs            { $$ = #[$1 ... $3]; }
1968 ;
1969
1970 ///////////////////////////////////////////////////////////////////////////////
1971 //
1972 //  Definition lists
1973 //
1974 ///////////////////////////////////////////////////////////////////////////////
1975 defs(Defs):                     { $$ = #[]; }
1976 |               def defs        { $$ = #[$1 ... $2]; }
1977 ;
1978
1979 ///////////////////////////////////////////////////////////////////////////////
1980 //
1981 //  Statements
1982 //
1983 ///////////////////////////////////////////////////////////////////////////////
1984 stmt(Stmt):
1985         exp ":=" exp ';'
1986                 { $$ = ASSIGNstmt($1,$3); }
1987 |       "while" exp "loop" stmt_list "end" "loop" ';'
1988                 { $$ = WHILEstmt($2,BLOCKstmt(#[],$4)); }
1989 |       "if" exp "then" stmt_list else_clause ';'
1990                 { $$ = IFstmt($2,BLOCKstmt(#[],$4),$5); }
1991 |       "forall" generator_list "loop" stmt_list "end" "loop" ';'
1992                 { $$ = FORALLstmt($2,BLOCKstmt(#[],$4)); }
1993 |       "return" exp ';'         { $$ = RETURNstmt($2); }
1994 |       match_decl               { $$ = MATCHstmt($1); }
1995 |       rewriting_decl           { $$ = REWRITEstmt($1); }
1996 |       replacement_decl ';'     { $$ = REPLACEMENTstmt($1); }
1997 |       compound_stmt            { $$ = $1; }
1998 ;
1999
2000 else_clause(Stmt):
2001         "end" "if"
2002                 { $$ = NOstmt; }
2003 |       "else" stmt_list "end" "if"
2004                 { $$ = BLOCKstmt(#[],$2); }
2005 |       "elsif" exp "then" stmt_list else_clause
2006                 { $$ = IFstmt($2,BLOCKstmt(#[],$4),$5); }
2007 ;
2008
2009 stmt_list(Stmts):       stmt            { $$ = #[$1]; }
2010 |                       stmt stmt_list  { $$ = #[$1 ... $2]; }
2011 ;
2012
2013 compound_stmt(Stmt):    "begin" stmt_list "end" ';'
2014                                 { $$ = BLOCKstmt(#[],$2); }
2015 |                       "declare" defs "begin" stmt_list "end" ';'
2016                                 { $$ = BLOCKstmt($2,$4); }
2017 ;
2018
2019 ///////////////////////////////////////////////////////////////////////////////
2020 //
2021 //  Generators
2022 //
2023 ///////////////////////////////////////////////////////////////////////////////
2024 generator_list(Generators):
2025         generator                       { $$ = #[$1]; }
2026 |       generator ',' generator_list    { $$ = #[$1 ... $3]; }
2027 ;
2028
2029 generator(Generator):   pat guard_exp "<-" exp
2030                         { $$ = GENERATOR'{ pat = $1, guard = $2, exp = $4 }; }
2031 ;
2032
2033 ///////////////////////////////////////////////////////////////////////////////
2034 //
2035 //  SETL-style collection types
2036 //
2037 ///////////////////////////////////////////////////////////////////////////////
2038 setl_ty(Ty):    "listof" '<' ty '>'             { $$ = mklistty($3); }
2039 |               "tupleof" '<' ty_list2 '>'      { $$ = mktuplety($3); }
2040 |               "setof" '<' ty '>'              { $$ = mksetty($3); }
2041 |               "bagof" '<' ty '>'              { $$ = mkbagty($3); }
2042 |               "mapof" '<' ty ',' ty '>'       { $$ = mkmapty($3,$5); }
2043 |               "multimapof" '<' ty ',' ty '>'  { $$ = mkmultimapty($3,$5); }
2044 |               "queueof" '<' ty '>'            { $$ = mkqueuety($3); }
2045 |               "priqueueof" '<' ty '>'         { $$ = mkpriqueuety($3); }
2046 |               "dequeof" '<' ty '>'            { $$ = mkdequety($3); }
2047 ;
2048
2049 ///////////////////////////////////////////////////////////////////////////////
2050 //
2051 //  SETL-like expressions:
2052 //
2053 ///////////////////////////////////////////////////////////////////////////////
2054 setl_exp(Exp):
2055         "arb" exp               { $$ = SETLexp(ARBop,#[$2]); }
2056 |       "dom" exp               { $$ = SETLexp(DOMop,#[$2]); }
2057 |       "ran" exp               { $$ = SETLexp(RANop,#[$2]); }
2058 |       exp "with" exp          { $$ = SETLexp(WITHop,#[$1,$3]); }
2059 |       exp "less" exp          { $$ = SETLexp(LESSop,#[$1,$3]); }
2060 |       exp "with" ":=" exp     { $$ = SETLexp(WITHASSIGNop,#[$1,$4]); }
2061 |       exp "less" ":=" exp     { $$ = SETLexp(LESSASSIGNop,#[$1,$4]); }
2062 |       set_comprehension       { $$ = $1; }
2063 ;
2064
2065 ///////////////////////////////////////////////////////////////////////////////
2066 //
2067 //  Set comprehension expression
2068 //
2069 ///////////////////////////////////////////////////////////////////////////////
2070 set_comprehension Exp:
2071         "setof" '{' exp ':' generator_list guard_exp3 '}'
2072         { $$ = NOexp; }
2073 ;
2074
2075 guard_exp3 Exp:                 { $$ = NOexp; }
2076 |               "where" exp     { $$ = $2; }
2077 ;
2078
2079 ///////////////////////////////////////////////////////////////////////////////
2080 //
2081 //  Complexity
2082 //
2083 ///////////////////////////////////////////////////////////////////////////////
2084 complexity(Complexity):
2085         id_or_cons                      { $$ = Var($1); }
2086 |       '(' complexity ')'              { $$ = $2; }
2087 |       complexity '+' complexity       { $$ = Add($1,$3); }
2088 |       complexity '*' complexity       { $$ = Mul($1,$3); }
2089 |       complexity '/' complexity       { $$ = Div($1,$3); }
2090 |       complexity '^' complexity       { $$ = Power($1,$3); }
2091 |       integer                         { $$ = Const($1); }
2092 |       real                            { $$ = Const($1); }
2093 |       id_or_cons complexity
2094         {  match ($1)
2095            { "O":     { $$ = BigOh($2); }
2096            | "o":     { $$ = LittleOh($2); }
2097            | "Omega": { $$ = Omega($2); }
2098            | "log":   { $$ = Log($2); }
2099            | _:       { error("%LUnknown complexity operator: %s\n",$1);
2100                         $$ = BigOh($2);
2101                       }
2102            }
2103         }
2104 ;
2105
2106 ///////////////////////////////////////////////////////////////////////////////
2107 //
2108 //  Constraint specifications
2109 //
2110 ///////////////////////////////////////////////////////////////////////////////
2111 /*
2112  *  Ignore for now
2113  *
2114 constraint_decl(Decl):
2115         "constraint" id '=' "begin" constraint_defs "end" "constraint" ';'
2116         { $$ = CONSTRAINTdecl($2,CONSTRAINTset($5)); }
2117 |       "constraint" id '{' constraint_defs '}' ';'
2118         { $$ = CONSTRAINTdecl($2,CONSTRAINTset($4)); }
2119 ;
2120
2121 constraint_defs(ConstraintDefs):
2122         constraint_def                  { $$ = #[$1]; }
2123 |       constraint_def constraint_defs  { $$ = #[$1 ... $2]; }
2124 ;
2125
2126 constraint_def(ConstraintDef):
2127         constraint_rule                 { $$ = CONSTRAINTruledef($1); }
2128 |       id '=' pat ';'                  { $$ = CONSTRAINTinstness($1,$3); }
2129 |       id ':' long_ty ';'              { $$ = CONSTRAINTtype($1,$3); }
2130 |       id "::" pat_list "is" deter ';' { $$ = CONSTRAINTdet($1,$3,$5); }
2131 ;
2132
2133 deter(Determinism): id
2134         {  match ($1)
2135            { "det":             { $$ = DET; }
2136            | "semidet":         { $$ = SEMI_DET; }
2137            | "multidet":        { $$ = MULTI_DET; }
2138            | "nondet":          { $$ = NON_DET; }
2139            | "fail":            { $$ = FAIL_DET; }
2140            | "error":           { $$ = ERROR_DET; }
2141            | _:                 { error ("%Ldeterminism %s not recognized",$1);
2142                                   $$ = VAR_DET(UNKNOWN_DET);
2143                                 }
2144            }
2145         }
2146 ;
2147
2148 constraint_rule(ConstraintRule):
2149         id
2150         {  me_stack[++me_top] = #[]; }
2151         top_pat
2152         {  pv_env.new_scope(false); // allow non-linear patterns.
2153            decor(me_stack[me_top],$3,pv_env,constraint_rule);
2154         }
2155         constraint_rule_body ';'
2156         {  pv_env.old_scope();
2157            me_top--;
2158            $$ = CONSTRAINTrule'{ id = $1, pat = $3, body = $5 };
2159         }
2160 ;
2161
2162 constraint_rule_body(ConstraintBody):   { $$ = CONSTRAINTnone; }
2163 |               ":-" constraint_body    { $$ = $2; }
2164 ;
2165
2166 constraint_body(ConstraintBody):
2167         constraint_body ',' constraint_body
2168                         { $$ = CONSTRAINTand($1,$3); }
2169 |       "if" constraint_body "then" constraint_body
2170         "else" constraint_body "end" "if"
2171                         { $$ = CONSTRAINTif($2,$4,$6); }
2172 |       exp             { $$ = CONSTRAINTcall($1); }
2173 |       compound_stmt   { $$ = CONSTRAINTbody(#[mark(SETLSTMTdecl($1))]); }
2174 |       '!'             { $$ = CONSTRAINTcut; }
2175 // |    brace_body      { $$ = CONSTRAINTbody($1); }
2176 ;
2177 */
2178
2179 ///////////////////////////////////////////////////////////////////////////////
2180 //
2181 //  Graph class specifications
2182 //
2183 ///////////////////////////////////////////////////////////////////////////////
2184 graph_class_decl Decl:
2185         "graphtype" id inherit_list_opt qualifiers_opt '('
2186         {  Used::graph_type = true;
2187            graphtype_def = new GraphTypeDef($2,$3,$4);
2188         }
2189         node_spec
2190         {  graphtype_def->set_nodes($7); }
2191         edge_spec
2192         ')'
2193         brace_body ';'
2194         {  graphtype_def->set_edges($9);
2195            graphtype_def->set_body($11);
2196            $$ = CLASSDEFdecl(graphtype_def);
2197         }
2198 ;
2199
2200 node_spec NodeDefs:             { $$ = #[]; }
2201 |       "nodes:" node_defs      { $$ = $2; }
2202 ;
2203
2204 node_defs NodeDefs:     node_def                        { $$ = #[$1]; }
2205 |                       node_def "and" node_defs        { $$ = #[$1 ... $3]; }
2206 |                       node_def '|' node_defs  { $$ = #[$1 ... $3]; }
2207 ;
2208
2209 node_def NodeDef *:     id
2210                         { $$ = new NodeDef(graphtype_def,$1); }
2211 |                       id opt_of ty hashfun eqfun
2212                         { $$ = new NodeDef(graphtype_def,$1,$3,$4,$5); }
2213
2214 ;
2215
2216 hashfun Id:                             { $$ = 0; }
2217 |                       "hash:" id      { $$ = $2; }
2218 ;
2219
2220 eqfun Id:                               { $$ = 0; }
2221 |                       "equality:" id  { $$ = $2; }
2222 ;
2223
2224 edge_spec EdgeDefs:             { $$ = #[]; }
2225 |       "edges:" edge_defs      { $$ = $2; }
2226 ;
2227
2228 edge_defs EdgeDefs:     edge_def                        { $$ = #[$1]; }
2229 |                       edge_def "and" edge_defs        { $$ = #[$1 ... $3]; }
2230 |                       edge_def '|' edge_defs          { $$ = #[$1 ... $3]; }
2231 ;
2232
2233 edge_def EdgeDef *:
2234         id opt_of node "->"  node indexing
2235                 { $$ = new MapEdge(graphtype_def,$1,$3,$5,$6); }
2236 |       id opt_of node "<->" node indexing
2237                 { $$ = new BijectionEdge(graphtype_def,$1,$3,$5,$6); }
2238 |       id opt_of node "<=>" node indexing
2239                 { $$ = new MultiMapEdge(graphtype_def,$1,$3,$5,$6); }
2240 |       id opt_of node "<=>" '*' node indexing
2241                 { $$ = new EquivRelationEdge(graphtype_def,$1,$3,$6,$7); }
2242 ;
2243
2244 node NodeDef *: id      { $$ = graphtype_def->lookup_node($1); }
2245 ;
2246
2247 indexing GraphIndexing:                         { $$ = NOindex; }
2248 |                       "index:" index_types    { $$ = $2; }
2249 ;
2250
2251 index_types GraphIndexing:
2252                 index_type                      { $$ = $1; }
2253 |               index_type index_types          { $$ = $1 | $2; }
2254 |               index_type ',' index_types      { $$ = $1 | $3; }
2255 ;
2256
2257 index_type GraphIndexing:
2258         "dom"                   { $$ = DOMindex; }
2259 |       "ran"                   { $$ = RANindex; }
2260 |       "dom" "->" "ran"        { $$ = FORWARDindex; }
2261 |       "dom" "<-" "ran"        { $$ = INVERSEindex; }
2262 |       "ran" "->" "dom"        { $$ = INVERSEindex; }
2263 |       "dom" "<->" "ran"       { $$ = FORWARDindex | INVERSEindex; }
2264 ;
2265
2266 ///////////////////////////////////////////////////////////////////////////////
2267 //
2268 //  Graph rewrite system declarations
2269 //
2270 ///////////////////////////////////////////////////////////////////////////////
2271 graph_rewrite_decl Decl:
2272         "graphrewrite" id '(' fun_args ')' '{' grs_sections '}'
2273         { $$ = GRAPHREWRITEdecl'{ name = $2, args = $4, rules = $7 }; }
2274 |       "graphrewrite" id '(' fun_args ')' '='
2275         "begin" grs_sections "end" "graphrewrite" ';'
2276         { $$ = GRAPHREWRITEdecl'{ name = $2, args = $4, rules = $8 }; }
2277 ;
2278
2279 grs_sections GraphRewritingRules:
2280         grs_data_declarations
2281         grs_index_declarations
2282         grs_strata
2283         {  $$ = $3; }
2284 ;
2285
2286 grs_data_declarations:
2287 ;
2288
2289 grs_index_declarations:
2290 ;
2291
2292 grs_strata GraphRewritingRules:
2293                 grs_stratum                     { $$ = $1; }
2294 ;
2295
2296 grs_stratum GraphRewritingRules:
2297                 grs_rules                       { $$ = $1; }
2298
2299 ;
2300
2301 grs_rules GraphRewritingRules:                  { $$ = #[]; }
2302 |               grs_rule grs_rules              { $$ = #[$1 ... $2]; }
2303 ;
2304
2305 grs_rule GraphRewritingRule:
2306         grs_pat implies grs_conclusions ';'
2307                 { $$ = GRSrule'{ lhs = $1, rhs = $3 }; }
2308 ;
2309
2310 grs_pat GRSPat:
2311         grs_simple_pat                  { $$ = $1; }
2312 |       "if" '(' exp ')'                { $$ = GUARDgpat($3); }
2313 |       "forall" id '.' grs_simple_pat  { $$ = FORALLgpat($2,$4); }
2314 |       grs_pat ',' grs_pat             { $$ = ANDgpat($1,$3); }
2315 |       grs_pat "and" grs_pat           { $$ = ANDgpat($1,$3); }
2316 |       grs_pat "||" grs_pat            { $$ = ORgpat($1,$3); }
2317 |       '(' grs_pat ')'                 { $$ = $2; }
2318 ;
2319
2320 grs_simple_pat GRSPat:
2321         id_or_cons '(' pat_list1 ')'        { $$ = EDGEgpat($1,$3); }
2322 |       negate id_or_cons '(' pat_list1 ')' { $$ = NOTgpat(EDGEgpat($2,$4)); }
2323 ;
2324
2325 grs_conclusions GRSConclusions:
2326                 grs_conclusion                          { $$ = #[$1]; }
2327 |               grs_conclusion "and" grs_conclusions    { $$ = #[$1 ... $3]; }
2328 |               grs_conclusion ',' grs_conclusions      { $$ = #[$1 ... $3]; }
2329 ;
2330
2331 grs_conclusion GRSConclusion:
2332         id_or_cons '(' exp_list ')'     { $$ = ADDEDGEaction($1,$3); }
2333 |       negate id_or_cons '(' exp_list ')' { $$ = DELETEEDGEaction($2,$4); }
2334 |       '+' exp                         { $$ = ADDNODEaction($2); }
2335 |       '-' exp                         { $$ = DELETENODEaction($2); }
2336 |       brace_body                      { $$ = ::EMBEDDEDaction($1); }
2337 //|     compound_stmt                   { $$ = EMBEDDEDaction($1); }
2338 ;
2339
2340 ///////////////////////////////////////////////////////////////////////////////
2341 //
2342 //  Dataflow class declarations
2343 //
2344 ///////////////////////////////////////////////////////////////////////////////
2345 /*
2346 dataflow_class_decl Decl:
2347         "dataflow" "class" id inherit_list_opt qualifiers_opt brace_body ';'
2348         {  $$ = CLASSDEFdecl(new DataflowClass($3,$4,$5,$6)); }
2349 ;
2350
2351 dataflow_decl Decl:
2352         "dataflow" id '{' '}' ';'
2353         {  $$ = DATAFLOWdecl'{ name = $2 }; }
2354 ;
2355 */
2356 };