src/gmxlib/selection/parser.y

   1 /*
   2  *
   3  *                This source code is part of
   4  *
   5  *                 G   R   O   M   A   C   S
   6  *
   7  *          GROningen MAchine for Chemical Simulations
   8  *
   9  * Written by David van der Spoel, Erik Lindahl, Berk Hess, and others.
  10  * Copyright (c) 1991-2000, University of Groningen, The Netherlands.
  11  * Copyright (c) 2001-2009, The GROMACS development team,
  12  * check out http://www.gromacs.org for more information.
  13
  14  * This program is free software; you can redistribute it and/or
  15  * modify it under the terms of the GNU General Public License
  16  * as published by the Free Software Foundation; either version 2
  17  * of the License, or (at your option) any later version.
  18  *
  19  * If you want to redistribute modifications, please consider that
  20  * scientific software is very special. Version control is crucial -
  21  * bugs must be traceable. We will be happy to consider code for
  22  * inclusion in the official distribution, but derived work must not
  23  * be called official GROMACS. Details are found in the README & COPYING
  24  * files - if they are missing, get the official version at www.gromacs.org.
  25  *
  26  * To help us fund GROMACS development, we humbly ask that you cite
  27  * the papers on the package - you can find them in the top README file.
  28  *
  29  * For more info, check our website at http://www.gromacs.org
  30  */
  31 /*! \internal \file
  32  * \brief Grammar description and parser for the selection language.
  33  */
  34 %{
  35 /*! \internal \file parser.c
  36  * \brief Generated (from parser.y by Bison) parser for the selection language.
  37  */
  38 /*! \internal \file parser.h
  39  * \brief Generated (from parser.y by Bison) parser include file.
  40  */
  41 #ifdef HAVE_CONFIG_H
  42 #include <config.h>
  43 #endif
  44
  45 #include <string2.h>
  46
  47 #include "parsetree.h"
  48 #include "selelem.h"
  49
  50 #include "scanner.h"
  51
  52 static t_selexpr_value *
  53 process_value_list(t_selexpr_value *values, int *nr);
  54 static t_selexpr_param *
  55 process_param_list(t_selexpr_param *params);
  56
  57 static void
  58 yyerror(yyscan_t, char const *s);
  59
  60 // Work around compiler warnings that result from bison not correctly
  61 // dealing with stdlib.h with ICC on Windows.
  62 #if (defined __INTEL_COMPILER && defined _WIN32)
  63 #define YYMALLOC malloc
  64 #define YYFREE free
  65 #endif
  66 %}
  67
  68 %union{
  69     int                         i;
  70     real                        r;
  71     char                       *str;
  72     struct gmx_ana_selmethod_t *meth;
  73
  74     struct t_selelem           *sel;
  75
  76     struct t_selexpr_value     *val;
  77     struct t_selexpr_param     *param;
  78 };
  79 /* NOTE: The Intel compiler seems to report warnings for the above line about
  80  * "definition at end of file not followed by a semicolon or a declarator".
  81  * This is due to the compiler misinterpreting #line directives in the
  82  * generated files parser.c/.h, and changing them would be more trouble than
  83  * it's worth. */
  84
  85 /* Invalid token to report lexer errors */
  86 %token INVALID
  87
  88 /* Tokens for help requests */
  89 %token         HELP
  90 %token <str>   HELP_TOPIC
  91
  92 /* Simple input tokens */
  93 %token <i>     TOK_INT
  94 %token <r>     TOK_REAL
  95 %token <str>   STR
  96 %token <str>   IDENTIFIER
  97 %token         CMD_SEP
  98
  99 /* Simple keyword tokens */
 100 %token         GROUP
 101 %token         TO
 102
 103 /* Variable tokens */
 104 %token <sel>   VARIABLE_NUMERIC
 105 %token <sel>   VARIABLE_GROUP
 106 %token <sel>   VARIABLE_POS
 107
 108 /* Selection method tokens */
 109 %token <meth>  KEYWORD_NUMERIC
 110 %token <meth>  KEYWORD_STR
 111 %token <str>   KEYWORD_POS
 112 %token <meth>  KEYWORD_GROUP
 113 %token <meth>  METHOD_NUMERIC
 114 %token <meth>  METHOD_GROUP
 115 %token <meth>  METHOD_POS
 116 %token <meth>  MODIFIER
 117 /* Empty token that should precede any non-position KEYWORD/METHOD token that
 118  * is not preceded by KEYWORD_POS. This is used to work around reduce/reduce
 119  * conflicts that appear when a lookahead token would require a reduction of
 120  * a rule with empty RHS before shifting, and there is an alternative reduction
 121  * available. Replacing the empty RHS with a dummy token makes these conflicts
 122  * only shift/reduce conflicts. Another alternative would be to remove the
 123  * pos_mod non-terminal completely and split each rule that uses it into two,
 124  * but this would require duplicating six rules in the grammar. */
 125 %token         EMPTY_POSMOD
 126
 127 %token <str>   PARAM
 128 %token         END_OF_METHOD
 129
 130 %token          OF
 131 /* Comparison operators have lower precedence than parameter reduction
 132  * to make it possible to parse, e.g., "mindist from resnr 1 < 2" without
 133  * parenthesis. */
 134 %nonassoc <str> CMP_OP
 135 /* A dummy token that determines the precedence of parameter reduction */
 136 %nonassoc       PARAM_REDUCT
 137 /* Boolean operator tokens */
 138 %left           OR XOR
 139 %left           AND
 140 %left           NOT
 141 /* Arithmetic operator tokens */
 142 %left           '+' '-'
 143 %left           '*' '/'
 144 %right          UNARY_NEG   /* Dummy token for unary negation precedence */
 145 %right          '^'
 146 %nonassoc       NUM_REDUCT  /* Dummy token for numerical keyword reduction precedence */
 147
 148 /* Simple non-terminals */
 149 %type <r>     integer_number
 150 %type <r>     real_number number
 151 %type <str>   string
 152 %type <str>   pos_mod
 153
 154 /* Expression non-terminals */
 155 %type <sel>   commands command cmd_plain
 156 %type <sel>   selection
 157 %type <sel>   sel_expr
 158 %type <sel>   num_expr
 159 %type <sel>   str_expr
 160 %type <sel>   pos_expr
 161
 162 /* Parameter/value non-terminals */
 163 %type <param> method_params method_param_list method_param
 164 %type <val>   value_list value_list_contents value_item value_item_range
 165 %type <val>   basic_value_list basic_value_list_contents basic_value_item
 166
 167 %destructor { free($$);                     } HELP_TOPIC STR IDENTIFIER CMP_OP string
 168 %destructor { if($$) free($$);              } PARAM
 169 %destructor { if($$) _gmx_selelem_free($$); } command cmd_plain
 170 %destructor { _gmx_selelem_free_chain($$);  } selection
 171 %destructor { _gmx_selelem_free($$);        } sel_expr num_expr str_expr pos_expr
 172 %destructor { _gmx_selexpr_free_params($$); } method_params method_param_list method_param
 173 %destructor { _gmx_selexpr_free_values($$); } value_list value_list_contents value_item value_item_range
 174 %destructor { _gmx_selexpr_free_values($$); } basic_value_list basic_value_list_contents basic_value_item
 175
 176 %expect 50
 177 %debug
 178 %pure-parser
 179
 180 /* If you change these, you also need to update the prototype in parsetree.c. */
 181 %name-prefix="_gmx_sel_yyb"
 182 %parse-param { yyscan_t                 scanner }
 183 %lex-param   { yyscan_t                 scanner }
 184
 185 %%
 186
 187 /* The start rule: allow one or more commands */
 188 commands:    /* empty */        { $$ = NULL }
 189            | commands command
 190              {
 191                  $$ = _gmx_sel_append_selection($2, $1, scanner);
 192                  if (_gmx_sel_parser_should_finish(scanner))
 193                      YYACCEPT;
 194              }
 195 ;
 196
 197 /* A command is formed from an actual command and a separator */
 198 command:     cmd_plain CMD_SEP  { $$ = $1; }
 199            | error CMD_SEP
 200              {
 201                  $$ = NULL;
 202                  _gmx_selparser_error("invalid selection '%s'",
 203                                       _gmx_sel_lexer_pselstr(scanner));
 204                  _gmx_sel_lexer_clear_method_stack(scanner);
 205                  if (_gmx_sel_is_lexer_interactive(scanner))
 206                  {
 207                      _gmx_sel_lexer_clear_pselstr(scanner);
 208                      yyerrok;
 209                  }
 210                  else
 211                  {
 212                      YYABORT;
 213                  }
 214              }
 215 ;
 216
 217 /* Commands can be selections or variable assignments */
 218 cmd_plain:   /* empty */
 219              {
 220                  $$ = NULL;
 221                  _gmx_sel_handle_empty_cmd(scanner);
 222              }
 223            | help_request       { $$ = NULL; }
 224            | TOK_INT
 225              {
 226                  t_selelem *s, *p;
 227                  s = _gmx_sel_init_group_by_id($1, scanner);
 228                  if (s == NULL) YYERROR;
 229                  p = _gmx_sel_init_position(s, NULL, scanner);
 230                  if (p == NULL) YYERROR;
 231                  $$ = _gmx_sel_init_selection(strdup(s->name), p, scanner);
 232              }
 233            | string
 234              {
 235                  t_selelem *s, *p;
 236                  s = _gmx_sel_init_group_by_name($1, scanner);
 237                  free($1);
 238                  if (s == NULL) YYERROR;
 239                  p = _gmx_sel_init_position(s, NULL, scanner);
 240                  if (p == NULL) YYERROR;
 241                  $$ = _gmx_sel_init_selection(strdup(s->name), p, scanner);
 242              }
 243            | selection
 244              { $$ = _gmx_sel_init_selection(NULL, $1, scanner); }
 245            | string selection
 246              { $$ = _gmx_sel_init_selection($1, $2, scanner);   }
 247            | IDENTIFIER '=' sel_expr
 248              { $$ = _gmx_sel_assign_variable($1, $3, scanner);  }
 249            | IDENTIFIER '=' num_expr
 250              { $$ = _gmx_sel_assign_variable($1, $3, scanner);  }
 251            | IDENTIFIER '=' pos_expr
 252              { $$ = _gmx_sel_assign_variable($1, $3, scanner);  }
 253 ;
 254
 255 /* Help requests */
 256 help_request:
 257              HELP                   { _gmx_sel_handle_help_cmd(NULL, scanner); }
 258            | help_topic
 259 ;
 260
 261 help_topic:  HELP HELP_TOPIC        { _gmx_sel_handle_help_cmd($2, scanner); }
 262            | help_topic HELP_TOPIC  { _gmx_sel_handle_help_cmd($2, scanner); }
 263 ;
 264
 265 /* Selection is made of an expression and zero or more modifiers */
 266 selection:   pos_expr           { $$ = $1; }
 267            | sel_expr
 268              {
 269                  $$ = _gmx_sel_init_position($1, NULL, scanner);
 270                  if ($$ == NULL) YYERROR;
 271              }
 272            | '(' selection ')'  { $$ = $2; }
 273            | selection MODIFIER method_params
 274              {
 275                  $$ = _gmx_sel_init_modifier($2, $3, $1, scanner);
 276                  if ($$ == NULL) YYERROR;
 277              }
 278 ;
 279
 280 /********************************************************************
 281  * BASIC NON-TERMINAL SYMBOLS
 282  ********************************************************************/
 283
 284 integer_number:
 285              TOK_INT            { $$ = $1; }
 286            | '-' TOK_INT        { $$ = -$2; }
 287 ;
 288
 289 real_number:
 290              TOK_REAL           { $$ = $1; }
 291            | '-' TOK_REAL       { $$ = -$2; }
 292 ;
 293
 294 number:      integer_number     { $$ = $1; }
 295            | real_number        { $$ = $1; }
 296 ;
 297
 298 string:      STR                { $$ = $1; }
 299            | IDENTIFIER         { $$ = $1; }
 300 ;
 301
 302 /********************************************************************
 303  * ATOM SELECTION EXPRESSIONS
 304  ********************************************************************/
 305
 306 /* Boolean expressions and grouping */
 307 sel_expr:    NOT sel_expr
 308              {
 309                  $$ = _gmx_selelem_create(SEL_BOOLEAN);
 310                  $$->u.boolt = BOOL_NOT;
 311                  $$->child = $2;
 312              }
 313            | sel_expr AND sel_expr
 314              {
 315                  $$ = _gmx_selelem_create(SEL_BOOLEAN);
 316                  $$->u.boolt = BOOL_AND;
 317                  $$->child = $1; $$->child->next = $3;
 318              }
 319            | sel_expr OR  sel_expr
 320              {
 321                  $$ = _gmx_selelem_create(SEL_BOOLEAN);
 322                  $$->u.boolt = BOOL_OR;
 323                  $$->child = $1; $$->child->next = $3;
 324              }
 325 /*           | sel_expr XOR sel_expr
 326              {
 327                  $$ = _gmx_selelem_create(SEL_BOOLEAN);
 328                  $$->u.boolt = BOOL_XOR;
 329                  $$->child = $1; $$->child->next = $3;
 330              }*/
 331            | '(' sel_expr ')'   { $$ = $2; }
 332 ;
 333
 334 /* Numeric comparisons */
 335 sel_expr:    num_expr CMP_OP num_expr
 336              {
 337                  $$ = _gmx_sel_init_comparison($1, $3, $2, scanner);
 338                  if ($$ == NULL) YYERROR;
 339              }
 340 ;
 341
 342 /* External groups */
 343 sel_expr:    GROUP string
 344              {
 345                  $$ = _gmx_sel_init_group_by_name($2, scanner);
 346                  free($2);
 347                  if ($$ == NULL) YYERROR;
 348              }
 349            | GROUP TOK_INT
 350              {
 351                  $$ = _gmx_sel_init_group_by_id($2, scanner);
 352                  if ($$ == NULL) YYERROR;
 353              }
 354 ;
 355
 356 /* Position modifiers for selection methods */
 357 pos_mod:     EMPTY_POSMOD       { $$ = NULL; }
 358            | KEYWORD_POS        { $$ = $1;   }
 359 ;
 360
 361 /* Keyword selections */
 362 sel_expr:    pos_mod KEYWORD_GROUP
 363              {
 364                  $$ = _gmx_sel_init_keyword($2, NULL, $1, scanner);
 365                  if ($$ == NULL) YYERROR;
 366              }
 367            | pos_mod KEYWORD_STR basic_value_list
 368              {
 369                  $$ = _gmx_sel_init_keyword($2, process_value_list($3, NULL), $1, scanner);
 370                  if ($$ == NULL) YYERROR;
 371              }
 372            | pos_mod KEYWORD_NUMERIC basic_value_list
 373              {
 374                  $$ = _gmx_sel_init_keyword($2, process_value_list($3, NULL), $1, scanner);
 375                  if ($$ == NULL) YYERROR;
 376              }
 377 ;
 378
 379 /* Custom selection methods */
 380 sel_expr:    pos_mod METHOD_GROUP method_params
 381              {
 382                  $$ = _gmx_sel_init_method($2, $3, $1, scanner);
 383                  if ($$ == NULL) YYERROR;
 384              }
 385 ;
 386
 387 /********************************************************************
 388  * NUMERICAL EXPRESSIONS
 389  ********************************************************************/
 390
 391 /* Basic numerical values */
 392 num_expr:    TOK_INT
 393              {
 394                  $$ = _gmx_selelem_create(SEL_CONST);
 395                  _gmx_selelem_set_vtype($$, INT_VALUE);
 396                  _gmx_selvalue_reserve(&$$->v, 1);
 397                  $$->v.u.i[0] = $1;
 398              }
 399            | TOK_REAL
 400              {
 401                  $$ = _gmx_selelem_create(SEL_CONST);
 402                  _gmx_selelem_set_vtype($$, REAL_VALUE);
 403                  _gmx_selvalue_reserve(&$$->v, 1);
 404                  $$->v.u.r[0] = $1;
 405              }
 406 ;
 407
 408 /* Numeric selection methods */
 409 num_expr:    pos_mod KEYWORD_NUMERIC    %prec NUM_REDUCT
 410              {
 411                  $$ = _gmx_sel_init_keyword($2, NULL, $1, scanner);
 412                  if ($$ == NULL) YYERROR;
 413              }
 414            | pos_mod METHOD_NUMERIC method_params
 415              {
 416                  $$ = _gmx_sel_init_method($2, $3, $1, scanner);
 417                  if ($$ == NULL) YYERROR;
 418              }
 419 ;
 420
 421 /* Arithmetic evaluation and grouping */
 422 num_expr:    num_expr '+' num_expr
 423              { $$ = _gmx_sel_init_arithmetic($1, $3, '+', scanner); }
 424            | num_expr '-' num_expr
 425              { $$ = _gmx_sel_init_arithmetic($1, $3, '-', scanner); }
 426            | num_expr '*' num_expr
 427              { $$ = _gmx_sel_init_arithmetic($1, $3, '*', scanner); }
 428            | num_expr '/' num_expr
 429              { $$ = _gmx_sel_init_arithmetic($1, $3, '/', scanner); }
 430            | '-' num_expr %prec UNARY_NEG
 431              { $$ = _gmx_sel_init_arithmetic($2, NULL, '-', scanner); }
 432            | num_expr '^' num_expr
 433              { $$ = _gmx_sel_init_arithmetic($1, $3, '^', scanner); }
 434            | '(' num_expr ')'   { $$ = $2; }
 435 ;
 436
 437 /********************************************************************
 438  * STRING EXPRESSIONS
 439  ********************************************************************/
 440
 441 str_expr:    string
 442              {
 443                  $$ = _gmx_selelem_create(SEL_CONST);
 444                  _gmx_selelem_set_vtype($$, STR_VALUE);
 445                  _gmx_selvalue_reserve(&$$->v, 1);
 446                  $$->v.u.s[0] = $1;
 447              }
 448            | pos_mod KEYWORD_STR
 449              {
 450                  $$ = _gmx_sel_init_keyword($2, NULL, $1, scanner);
 451                  if ($$ == NULL) YYERROR;
 452              }
 453 ;
 454
 455 /********************************************************************
 456  * POSITION EXPRESSIONS
 457  ********************************************************************/
 458
 459 /* Constant position expressions */
 460 pos_expr:    '[' number ',' number ',' number ']'
 461              { $$ = _gmx_sel_init_const_position($2, $4, $6); }
 462 ;
 463
 464 /* Grouping of position expressions */
 465 pos_expr:    '(' pos_expr ')'   { $$ = $2; }
 466 ;
 467
 468 /* Expressions with a position value */
 469 pos_expr:    METHOD_POS method_params
 470              {
 471                  $$ = _gmx_sel_init_method($1, $2, NULL, scanner);
 472                  if ($$ == NULL) YYERROR;
 473              }
 474 ;
 475
 476 /* Evaluation of positions using a keyword */
 477 pos_expr:    KEYWORD_POS OF sel_expr    %prec PARAM_REDUCT
 478              {
 479                  $$ = _gmx_sel_init_position($3, $1, scanner);
 480                  if ($$ == NULL) YYERROR;
 481              }
 482 ;
 483
 484 /********************************************************************
 485  * VARIABLES
 486  ********************************************************************/
 487
 488 sel_expr:    VARIABLE_GROUP
 489              { $$ = _gmx_sel_init_variable_ref($1); }
 490 ;
 491
 492 num_expr:    VARIABLE_NUMERIC
 493              { $$ = _gmx_sel_init_variable_ref($1); }
 494 ;
 495
 496 pos_expr:    VARIABLE_POS
 497              { $$ = _gmx_sel_init_variable_ref($1); }
 498 ;
 499
 500 /********************************************************************
 501  * METHOD PARAMETERS
 502  ********************************************************************/
 503
 504 method_params:
 505              method_param_list
 506              { $$ = process_param_list($1); }
 507            | method_param_list END_OF_METHOD
 508              { $$ = process_param_list($1); }
 509 ;
 510
 511 method_param_list:
 512              /* empty */        { $$ = NULL;              }
 513            | method_param_list method_param
 514                                 { $2->next = $1; $$ = $2; }
 515 ;
 516
 517 method_param:
 518              PARAM value_list
 519              {
 520                  $$ = _gmx_selexpr_create_param($1);
 521                  $$->value = process_value_list($2, &$$->nval);
 522              }
 523 ;
 524
 525 value_list:  /* empty */                         { $$ = NULL; }
 526            | value_list_contents                 { $$ = $1;   }
 527            | '{' value_list_contents '}'         { $$ = $2;   }
 528 ;
 529
 530 value_list_contents:
 531              value_item          { $$ = $1; }
 532            | value_list_contents value_item
 533                                  { $2->next = $1; $$ = $2; }
 534            | value_list_contents ',' value_item
 535                                  { $3->next = $1; $$ = $3; }
 536 ;
 537
 538 basic_value_list:
 539              basic_value_list_contents           { $$ = $1; }
 540            | '{' basic_value_list_contents '}'   { $$ = $2; }
 541 ;
 542
 543 basic_value_list_contents:
 544              basic_value_item    { $$ = $1; }
 545            | basic_value_list_contents basic_value_item
 546                                  { $2->next = $1; $$ = $2; }
 547            | basic_value_list_contents ',' basic_value_item
 548                                  { $3->next = $1; $$ = $3; }
 549 ;
 550
 551 value_item:  sel_expr            %prec PARAM_REDUCT
 552              { $$ = _gmx_selexpr_create_value_expr($1); }
 553            | pos_expr            %prec PARAM_REDUCT
 554              { $$ = _gmx_selexpr_create_value_expr($1); }
 555            | num_expr            %prec PARAM_REDUCT
 556              { $$ = _gmx_selexpr_create_value_expr($1); }
 557            | str_expr            %prec PARAM_REDUCT
 558              { $$ = _gmx_selexpr_create_value_expr($1); }
 559            | value_item_range    { $$ = $1; }
 560 ;
 561
 562 basic_value_item:
 563              integer_number      %prec PARAM_REDUCT
 564              {
 565                  $$ = _gmx_selexpr_create_value(INT_VALUE);
 566                  $$->u.i.i1 = $$->u.i.i2 = $1;
 567              }
 568            | real_number         %prec PARAM_REDUCT
 569              {
 570                  $$ = _gmx_selexpr_create_value(REAL_VALUE);
 571                  $$->u.r.r1 = $$->u.r.r2 = $1;
 572              }
 573            | string              %prec PARAM_REDUCT
 574              {
 575                  $$ = _gmx_selexpr_create_value(STR_VALUE);
 576                  $$->u.s = $1;
 577              }
 578            | value_item_range    { $$ = $1; }
 579 ;
 580
 581 value_item_range:
 582              integer_number TO integer_number
 583              {
 584                  $$ = _gmx_selexpr_create_value(INT_VALUE);
 585                  $$->u.i.i1 = $1; $$->u.i.i2 = $3;
 586              }
 587            | integer_number TO real_number
 588              {
 589                  $$ = _gmx_selexpr_create_value(REAL_VALUE);
 590                  $$->u.r.r1 = $1; $$->u.r.r2 = $3;
 591              }
 592            | real_number TO number
 593              {
 594                  $$ = _gmx_selexpr_create_value(REAL_VALUE);
 595                  $$->u.r.r1 = $1; $$->u.r.r2 = $3;
 596              }
 597 ;
 598
 599 %%
 600
 601 static t_selexpr_value *
 602 process_value_list(t_selexpr_value *values, int *nr)
 603 {
 604     t_selexpr_value *val, *pval, *nval;
 605
 606     /* Count values (if needed) and reverse list */
 607     if (nr)
 608     {
 609         *nr  = 0;
 610     }
 611     pval = NULL;
 612     val  = values;
 613     while (val)
 614     {
 615         if (nr)
 616         {
 617             ++*nr;
 618         }
 619         nval = val->next;
 620         val->next = pval;
 621         pval = val;
 622         val = nval;
 623     }
 624     values = pval;
 625
 626     return values;
 627 }
 628
 629 static t_selexpr_param *
 630 process_param_list(t_selexpr_param *params)
 631 {
 632     t_selexpr_param *par, *ppar, *npar;
 633
 634     /* Reverse list */
 635     ppar = NULL;
 636     par  = params;
 637     while (par)
 638     {
 639         npar = par->next;
 640         par->next = ppar;
 641         ppar = par;
 642         par = npar;
 643     }
 644     params = ppar;
 645
 646     return params;
 647 }
 648
 649 static void
 650 yyerror(yyscan_t scanner, char const *s)
 651 {
 652     _gmx_selparser_error("%s", s);
 653 }
 654
 655