tests/reduce.at

   1 # Exercising Bison Grammar Reduction.                      -*- Autotest -*-
   2 # Copyright (C) 2001, 2002, 2007, 2008, 2009 Free Software Foundation,
   3 # Inc.
   4
   5 # This program is free software: you can redistribute it and/or modify
   6 # it under the terms of the GNU General Public License as published by
   7 # the Free Software Foundation, either version 3 of the License, or
   8 # (at your option) any later version.
   9 #
  10 # This program is distributed in the hope that it will be useful,
  11 # but WITHOUT ANY WARRANTY; without even the implied warranty of
  12 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13 # GNU General Public License for more details.
  14 #
  15 # You should have received a copy of the GNU General Public License
  16 # along with this program.  If not, see <http://www.gnu.org/licenses/>.
  17
  18 AT_BANNER([[Grammar Reduction.]])
  19
  20
  21 ## ------------------- ##
  22 ## Useless Terminals.  ##
  23 ## ------------------- ##
  24
  25 AT_SETUP([Useless Terminals])
  26
  27 AT_DATA([[input.y]],
  28 [[%verbose
  29 %output "input.c"
  30
  31 %token useless1
  32 %token useless2
  33 %token useless3
  34 %token useless4
  35 %token useless5
  36 %token useless6
  37 %token useless7
  38 %token useless8
  39 %token useless9
  40
  41 %token useful
  42 %%
  43 exp: useful;
  44 ]])
  45
  46 AT_BISON_CHECK([[input.y]])
  47
  48 AT_CHECK([[sed -n '/^Grammar/q;/^$/!p' input.output]], 0,
  49 [[Terminals unused in grammar
  50    useless1
  51    useless2
  52    useless3
  53    useless4
  54    useless5
  55    useless6
  56    useless7
  57    useless8
  58    useless9
  59 ]])
  60
  61 AT_CLEANUP
  62
  63
  64
  65 ## ---------------------- ##
  66 ## Useless Nonterminals.  ##
  67 ## ---------------------- ##
  68
  69 AT_SETUP([Useless Nonterminals])
  70
  71 AT_DATA([[input.y]],
  72 [[%verbose
  73 %output "input.c"
  74
  75 %nterm useless1
  76 %nterm useless2
  77 %nterm useless3
  78 %nterm useless4
  79 %nterm useless5
  80 %nterm useless6
  81 %nterm useless7
  82 %nterm useless8
  83 %nterm useless9
  84
  85 %token useful
  86 %%
  87 exp: useful;
  88 ]])
  89
  90 AT_BISON_CHECK([[input.y]], 0, [],
  91 [[input.y: warning: 9 nonterminals useless in grammar
  92 input.y:4.8-15: warning: nonterminal useless in grammar: useless1
  93 input.y:5.8-15: warning: nonterminal useless in grammar: useless2
  94 input.y:6.8-15: warning: nonterminal useless in grammar: useless3
  95 input.y:7.8-15: warning: nonterminal useless in grammar: useless4
  96 input.y:8.8-15: warning: nonterminal useless in grammar: useless5
  97 input.y:9.8-15: warning: nonterminal useless in grammar: useless6
  98 input.y:10.8-15: warning: nonterminal useless in grammar: useless7
  99 input.y:11.8-15: warning: nonterminal useless in grammar: useless8
 100 input.y:12.8-15: warning: nonterminal useless in grammar: useless9
 101 ]])
 102
 103 AT_CHECK([[sed -n '/^Grammar/q;/^$/!p' input.output]], 0,
 104 [[Nonterminals useless in grammar
 105    useless1
 106    useless2
 107    useless3
 108    useless4
 109    useless5
 110    useless6
 111    useless7
 112    useless8
 113    useless9
 114 ]])
 115
 116 AT_CLEANUP
 117
 118
 119
 120 ## --------------- ##
 121 ## Useless Rules.  ##
 122 ## --------------- ##
 123
 124 AT_SETUP([Useless Rules])
 125
 126 AT_KEYWORDS([report])
 127
 128 AT_DATA([[input.y]],
 129 [[%verbose
 130 %output "input.c"
 131 %token useful
 132 %%
 133 exp: useful;
 134 useless1: '1';
 135 useless2: '2';
 136 useless3: '3';
 137 useless4: '4';
 138 useless5: '5';
 139 useless6: '6';
 140 useless7: '7';
 141 useless8: '8';
 142 useless9: '9';
 143 ]])
 144
 145 AT_BISON_CHECK([[input.y]], 0, [],
 146 [[input.y: warning: 9 nonterminals useless in grammar
 147 input.y: warning: 9 rules useless in grammar
 148 input.y:6.1-8: warning: nonterminal useless in grammar: useless1
 149 input.y:7.1-8: warning: nonterminal useless in grammar: useless2
 150 input.y:8.1-8: warning: nonterminal useless in grammar: useless3
 151 input.y:9.1-8: warning: nonterminal useless in grammar: useless4
 152 input.y:10.1-8: warning: nonterminal useless in grammar: useless5
 153 input.y:11.1-8: warning: nonterminal useless in grammar: useless6
 154 input.y:12.1-8: warning: nonterminal useless in grammar: useless7
 155 input.y:13.1-8: warning: nonterminal useless in grammar: useless8
 156 input.y:14.1-8: warning: nonterminal useless in grammar: useless9
 157 input.y:6.11-13: warning: rule useless in grammar: useless1: '1'
 158 input.y:7.11-13: warning: rule useless in grammar: useless2: '2'
 159 input.y:8.11-13: warning: rule useless in grammar: useless3: '3'
 160 input.y:9.11-13: warning: rule useless in grammar: useless4: '4'
 161 input.y:10.11-13: warning: rule useless in grammar: useless5: '5'
 162 input.y:11.11-13: warning: rule useless in grammar: useless6: '6'
 163 input.y:12.11-13: warning: rule useless in grammar: useless7: '7'
 164 input.y:13.11-13: warning: rule useless in grammar: useless8: '8'
 165 input.y:14.11-13: warning: rule useless in grammar: useless9: '9'
 166 ]])
 167
 168 AT_CHECK([[sed -n '/^Grammar/q;/^$/!p' input.output]], 0,
 169 [[Nonterminals useless in grammar
 170    useless1
 171    useless2
 172    useless3
 173    useless4
 174    useless5
 175    useless6
 176    useless7
 177    useless8
 178    useless9
 179 Terminals unused in grammar
 180    '1'
 181    '2'
 182    '3'
 183    '4'
 184    '5'
 185    '6'
 186    '7'
 187    '8'
 188    '9'
 189 Rules useless in grammar
 190     2 useless1: '1'
 191     3 useless2: '2'
 192     4 useless3: '3'
 193     5 useless4: '4'
 194     6 useless5: '5'
 195     7 useless6: '6'
 196     8 useless7: '7'
 197     9 useless8: '8'
 198    10 useless9: '9'
 199 ]])
 200
 201 AT_CLEANUP
 202
 203
 204
 205 ## ------------------- ##
 206 ## Reduced Automaton.  ##
 207 ## ------------------- ##
 208
 209 # Check that the automaton is that as the for the grammar reduced by
 210 # hand.
 211
 212 AT_SETUP([Reduced Automaton])
 213
 214 AT_KEYWORDS([report])
 215
 216 # The non reduced grammar.
 217 # ------------------------
 218 AT_DATA([[not-reduced.y]],
 219 [[/* A useless token. */
 220 %token useless_token
 221 /* A useful one. */
 222 %token useful
 223 %verbose
 224 %output "not-reduced.c"
 225
 226 %%
 227
 228 exp: useful            { /* A useful action. */ }
 229    | non_productive    { /* A non productive action. */ }
 230    ;
 231
 232 not_reachable: useful  { /* A not reachable action. */ }
 233              ;
 234
 235 non_productive: non_productive useless_token
 236                        { /* Another non productive action. */ }
 237               ;
 238 %%
 239 ]])
 240
 241 AT_BISON_CHECK([[not-reduced.y]], 0, [],
 242 [[not-reduced.y: warning: 2 nonterminals useless in grammar
 243 not-reduced.y: warning: 3 rules useless in grammar
 244 not-reduced.y:14.1-13: warning: nonterminal useless in grammar: not_reachable
 245 not-reduced.y:11.6-19: warning: nonterminal useless in grammar: non_productive
 246 not-reduced.y:11.6-57: warning: rule useless in grammar: exp: non_productive
 247 not-reduced.y:14.16-56: warning: rule useless in grammar: not_reachable: useful
 248 not-reduced.y:17.17-18.63: warning: rule useless in grammar: non_productive: non_productive useless_token
 249 ]])
 250
 251 AT_CHECK([[sed -n '/^Grammar/q;/^$/!p' not-reduced.output]], 0,
 252 [[Nonterminals useless in grammar
 253    not_reachable
 254    non_productive
 255 Terminals unused in grammar
 256    useless_token
 257 Rules useless in grammar
 258     2 exp: non_productive
 259     3 not_reachable: useful
 260     4 non_productive: non_productive useless_token
 261 ]])
 262
 263 # The reduced grammar.
 264 # --------------------
 265 AT_DATA([[reduced.y]],
 266 [[/* A useless token. */
 267 %token useless_token
 268 /* A useful one. */
 269 %token useful
 270 %verbose
 271 %output "reduced.c"
 272
 273 %%
 274
 275 exp: useful            { /* A useful action. */ }
 276 //   | non_productive    { /* A non productive action. */ } */
 277    ;
 278
 279 //not_reachable: useful  { /* A not reachable action. */ }
 280 //             ;
 281
 282 //non_productive: non_productive useless_token
 283 //                       { /* Another non productive action. */ }
 284 //              ;
 285 %%
 286 ]])
 287
 288 AT_BISON_CHECK([[reduced.y]])
 289
 290 # Comparing the parsers.
 291 cp reduced.c expout
 292 AT_CHECK([sed 's/not-reduced/reduced/g' not-reduced.c], 0, [expout])
 293
 294 AT_CLEANUP
 295
 296
 297
 298 ## ------------------- ##
 299 ## Underivable Rules.  ##
 300 ## ------------------- ##
 301
 302 AT_SETUP([Underivable Rules])
 303
 304 AT_KEYWORDS([report])
 305
 306 AT_DATA([[input.y]],
 307 [[%verbose
 308 %output "input.c"
 309 %token useful
 310 %%
 311 exp: useful | underivable;
 312 underivable: indirection;
 313 indirection: underivable;
 314 ]])
 315
 316 AT_BISON_CHECK([[input.y]], 0, [],
 317 [[input.y: warning: 2 nonterminals useless in grammar
 318 input.y: warning: 3 rules useless in grammar
 319 input.y:5.15-25: warning: nonterminal useless in grammar: underivable
 320 input.y:6.14-24: warning: nonterminal useless in grammar: indirection
 321 input.y:5.15-25: warning: rule useless in grammar: exp: underivable
 322 input.y:6.14-24: warning: rule useless in grammar: underivable: indirection
 323 input.y:7.14-24: warning: rule useless in grammar: indirection: underivable
 324 ]])
 325
 326 AT_CHECK([[sed -n '/^Grammar/q;/^$/!p' input.output]], 0,
 327 [[Nonterminals useless in grammar
 328    underivable
 329    indirection
 330 Rules useless in grammar
 331     2 exp: underivable
 332     3 underivable: indirection
 333     4 indirection: underivable
 334 ]])
 335
 336 AT_CLEANUP
 337
 338
 339
 340 ## ---------------- ##
 341 ## Empty Language.  ##
 342 ## ---------------- ##
 343
 344 AT_SETUP([Empty Language])
 345
 346 AT_DATA([[input.y]],
 347 [[%output "input.c"
 348 %%
 349 exp: exp;
 350 ]])
 351
 352 AT_BISON_CHECK([[input.y]], 1, [],
 353 [[input.y: warning: 2 nonterminals useless in grammar
 354 input.y: warning: 2 rules useless in grammar
 355 input.y:3.1-3: fatal error: start symbol exp does not derive any sentence
 356 ]])
 357
 358 AT_CLEANUP
 359
 360
 361
 362 ## -------------------------- ##
 363 ## %define lr.default_rules.  ##
 364 ## -------------------------- ##
 365
 366 # AT_TEST_LR_DEFAULT_RULES(GRAMMAR, INPUT, TABLES)
 367 # ------------------------------------------------
 368 m4_define([AT_TEST_LR_DEFAULT_RULES],
 369 [
 370 AT_TEST_TABLES_AND_PARSE([[no %define lr.default_rules]],
 371                          [[all]], [[]],
 372                          [[]],
 373                          [$1], [$2], [[]], [$3])
 374 AT_TEST_TABLES_AND_PARSE([[%define lr.default_rules "all"]],
 375                          [[all]], [[]],
 376                          [[%define lr.default_rules "all"]],
 377                          [$1], [$2], [[]], [$3])
 378 AT_TEST_TABLES_AND_PARSE([[%define lr.default_rules "consistent"]],
 379                          [[consistent]], [[]],
 380                          [[%define lr.default_rules "consistent"]],
 381                          [$1], [$2], [[]], [$3])
 382 AT_TEST_TABLES_AND_PARSE([[%define lr.default_rules "accepting"]],
 383                          [[accepting]], [[]],
 384                          [[%define lr.default_rules "accepting"]],
 385                          [$1], [$2], [[]], [$3])
 386 ])
 387
 388 AT_TEST_LR_DEFAULT_RULES([[
 389 /* The start state is consistent and has a shift on 'a' and no reductions.
 390    After pushing the b below, enter an inconsistent state that has a shift and
 391    one reduction with one lookahead.  */
 392 start:
 393     a b
 394   | a b 'a'
 395   | a c 'b'
 396   ;
 397
 398 /* After shifting this 'a', enter a consistent state that has no shift and 1
 399    reduction with multiple lookaheads.  */
 400 a: 'a' ;
 401
 402 /* After the previous reduction, enter an inconsistent state that has no shift
 403    and multiple reductions.  The first reduction has more lookaheads than the
 404    second, so the first should always be preferred as the default rule if
 405    enabled.  The second reduction has one lookahead.  */
 406 b: ;
 407 c: ;
 408 ]],
 409 dnl Visit each state mentioned above.
 410 [['a', 'a']],
 411 [[state 0
 412
 413     0 $accept: . start $end
 414     1 start: . a b
 415     2      | . a b 'a'
 416     3      | . a c 'b'
 417     4 a: . 'a'
 418
 419     'a'  shift, and go to state 1
 420
 421     start  go to state 2
 422     a      go to state 3
 423
 424
 425 state 1
 426
 427     4 a: 'a' .]AT_COND_CASE([[accepting]], [[  [$end, 'a', 'b']
 428
 429     $end  reduce using rule 4 (a)
 430     'a'   reduce using rule 4 (a)
 431     'b'   reduce using rule 4 (a)]], [[
 432
 433     $default  reduce using rule 4 (a)]])[
 434
 435
 436 state 2
 437
 438     0 $accept: start . $end
 439
 440     $end  shift, and go to state 4
 441
 442
 443 state 3
 444
 445     1 start: a . b
 446     2      | a . b 'a'
 447     3      | a . c 'b'
 448     5 b: .  [$end, 'a']
 449     6 c: .  ['b']]AT_COND_CASE([[all]], [[
 450
 451     'b'       reduce using rule 6 (c)
 452     $default  reduce using rule 5 (b)]], [[
 453
 454     $end  reduce using rule 5 (b)
 455     'a'   reduce using rule 5 (b)
 456     'b'   reduce using rule 6 (c)]])[
 457
 458     b  go to state 5
 459     c  go to state 6
 460
 461
 462 state 4
 463
 464     0 $accept: start $end .
 465
 466     $default  accept
 467
 468
 469 state 5
 470
 471     1 start: a b .  [$end]
 472     2      | a b . 'a'
 473
 474     'a'  shift, and go to state 7
 475
 476     ]AT_COND_CASE([[all]], [[$default]], [[$end]])[  reduce using rule 1 (start)
 477
 478
 479 state 6
 480
 481     3 start: a c . 'b'
 482
 483     'b'  shift, and go to state 8
 484
 485
 486 state 7
 487
 488     2 start: a b 'a' .]AT_COND_CASE([[accepting]], [[  [$end]
 489
 490     $end  reduce using rule 2 (start)]], [[
 491
 492     $default  reduce using rule 2 (start)]])[
 493
 494
 495 state 8
 496
 497     3 start: a c 'b' .]AT_COND_CASE([[accepting]], [[  [$end]
 498
 499     $end  reduce using rule 3 (start)]], [[
 500
 501     $default  reduce using rule 3 (start)]])[
 502 ]])