tests/sets.at

   1 # Exercising Bison Grammar Sets.                      -*- Autotest -*-
   2 # Copyright (C) 2001, 2002, 2005, 2007 Free Software Foundation, Inc.
   3
   4 # This program is free software: you can redistribute it and/or modify
   5 # it under the terms of the GNU General Public License as published by
   6 # the Free Software Foundation, either version 3 of the License, or
   7 # (at your option) any later version.
   8 #
   9 # This program is distributed in the hope that it will be useful,
  10 # but WITHOUT ANY WARRANTY; without even the implied warranty of
  11 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12 # GNU General Public License for more details.
  13 #
  14 # You should have received a copy of the GNU General Public License
  15 # along with this program.  If not, see <http://www.gnu.org/licenses/>.
  16
  17
  18 # AT_EXTRACT_SETS(INPUT, OUTPUT)
  19 # ------------------------------
  20 # Extract the information about the grammar sets from a bison
  21 # trace output (INPUT), and save it in OUTPUT.
  22 # And remember, there is no alternation in portable sed.
  23 m4_define([AT_EXTRACT_SETS],
  24 [AT_DATA([extract.sed],
  25 [[#n
  26 /^NULLABLE$/ {
  27    :null
  28    p
  29    n
  30    /^[   ]*$/ !b null
  31 }
  32 /^FIRSTS$/ {
  33    :firsts
  34    p
  35    n
  36    /^[   ]*$/ !b firsts
  37 }
  38 /^FDERIVES$/ {
  39    :fderiv
  40    p
  41    n
  42    /^[   ]*$/ !b fderiv
  43 }
  44 /^DERIVES$/ {
  45    :deriv
  46    p
  47    n
  48    /^[   ]*$/ !b deriv
  49 }
  50 ]])
  51 AT_CHECK([sed -f extract.sed $1], 0, [stdout])
  52 AT_CHECK([mv stdout $2])
  53 ])
  54
  55
  56
  57 AT_BANNER([[Grammar Sets (Firsts etc.).]])
  58
  59
  60 ## ---------- ##
  61 ## Nullable.  ##
  62 ## ---------- ##
  63
  64 AT_SETUP([Nullable])
  65
  66 # At some point, nullable had been smoking grass, and managed to say:
  67 #
  68 # Entering set_nullable
  69 # NULLABLE
  70 #         'e': yes
  71 #         (null): no
  72 # ...
  73
  74 AT_DATA([[input.y]],
  75 [[%%
  76 e: 'e' | /* Nothing */;
  77 ]])
  78
  79 AT_BISON_CHECK([[--trace=sets input.y]], [], [], [stderr])
  80 AT_EXTRACT_SETS([stderr], [sets])
  81 AT_CHECK([[cat sets]], [],
  82 [[DERIVES
  83         $accept derives
  84                   0  e $end
  85         e derives
  86                   1  'e'
  87                   2  /* empty */
  88 NULLABLE
  89         $accept: no
  90         e: yes
  91 FIRSTS
  92         $accept firsts
  93                 $accept
  94                 e
  95         e firsts
  96                 e
  97 FDERIVES
  98         $accept derives
  99                   0  e $end
 100                   1  'e'
 101                   2  /* empty */
 102         e derives
 103                   1  'e'
 104                   2  /* empty */
 105 ]])
 106
 107 AT_CLEANUP
 108
 109
 110 ## ---------------- ##
 111 ## Broken Closure.  ##
 112 ## ---------------- ##
 113
 114 # TC was once broken during a massive `simplification' of the code.
 115 # It resulted in bison dumping core on the following grammar (the
 116 # computation of FIRSTS uses TC).  It managed to produce a pretty
 117 # exotic closure:
 118 #
 119 # TC: Input
 120 #
 121 #    01234567
 122 #   +--------+
 123 #  0| 1      |
 124 #  1|  1     |
 125 #  2|   1    |
 126 #  3|    1   |
 127 #  4|     1  |
 128 #  5|      1 |
 129 #  6|       1|
 130 #  7|        |
 131 #   +--------+
 132 #
 133 # TC: Output
 134 #
 135 #    01234567
 136 #   +--------+
 137 #  0| 1      |
 138 #  1| 111    |
 139 #  2| 111    |
 140 #  3| 1111   |
 141 #  4| 111 1  |
 142 #  5| 111  1 |
 143 #  6| 111   1|
 144 #  7| 111    |
 145 #   +--------+
 146 #
 147 # instead of that below.
 148
 149 AT_SETUP([Broken Closure])
 150
 151 AT_DATA([input.y],
 152 [[%%
 153 a: b;
 154 b: c;
 155 c: d;
 156 d: e;
 157 e: f;
 158 f: g;
 159 g: h;
 160 h: 'h';
 161 ]])
 162
 163 AT_BISON_CHECK([[--trace=sets input.y]], [], [], [stderr])
 164
 165 AT_CHECK([[sed -n 's/[   ]*$//;/^RTC: Firsts Output BEGIN/,/^RTC: Firsts Output END/p' stderr]], [],
 166 [[RTC: Firsts Output BEGIN
 167
 168    012345678
 169   .---------.
 170  0|111111111|
 171  1| 11111111|
 172  2|  1111111|
 173  3|   111111|
 174  4|    11111|
 175  5|     1111|
 176  6|      111|
 177  7|       11|
 178  8|        1|
 179   `---------'
 180 RTC: Firsts Output END
 181 ]])
 182
 183 AT_CLEANUP
 184
 185
 186
 187 ## -------- ##
 188 ## Firsts.  ##
 189 ## -------- ##
 190
 191 AT_SETUP([Firsts])
 192
 193 AT_DATA([input.y],
 194 [[%nonassoc '<' '>'
 195 %left '+' '-'
 196 %right '^' '='
 197 %%
 198 exp:
 199    exp '<' exp
 200  | exp '>' exp
 201  | exp '+' exp
 202  | exp '-' exp
 203  | exp '^' exp
 204  | exp '=' exp
 205  | "exp"
 206  ;
 207 ]])
 208
 209 AT_BISON_CHECK([[--trace=sets input.y]], [], [], [stderr])
 210 AT_EXTRACT_SETS([stderr], [sets])
 211 AT_CHECK([[cat sets]], [],
 212 [[DERIVES
 213         $accept derives
 214                   0  exp $end
 215         exp derives
 216                   1  exp '<' exp
 217                   2  exp '>' exp
 218                   3  exp '+' exp
 219                   4  exp '-' exp
 220                   5  exp '^' exp
 221                   6  exp '=' exp
 222                   7  "exp"
 223 NULLABLE
 224         $accept: no
 225         exp: no
 226 FIRSTS
 227         $accept firsts
 228                 $accept
 229                 exp
 230         exp firsts
 231                 exp
 232 FDERIVES
 233         $accept derives
 234                   0  exp $end
 235                   1  exp '<' exp
 236                   2  exp '>' exp
 237                   3  exp '+' exp
 238                   4  exp '-' exp
 239                   5  exp '^' exp
 240                   6  exp '=' exp
 241                   7  "exp"
 242         exp derives
 243                   1  exp '<' exp
 244                   2  exp '>' exp
 245                   3  exp '+' exp
 246                   4  exp '-' exp
 247                   5  exp '^' exp
 248                   6  exp '=' exp
 249                   7  "exp"
 250 ]])
 251
 252 AT_CLEANUP
 253
 254
 255
 256
 257 ## -------- ##
 258 ## Accept.  ##
 259 ## -------- ##
 260
 261 # In some weird cases Bison could compute an incorrect final state
 262 # number.  This happens only if the $end token is used in the user
 263 # grammar, which is a very suspicious accidental feature introduced as
 264 # a side effect of allowing the user to name $end using `%token END 0
 265 # "end of file"'.
 266
 267 AT_SETUP([Accept])
 268
 269 AT_DATA([input.y],
 270 [[%token END 0
 271 %%
 272 input:
 273   'a'
 274 | '(' input ')'
 275 | '(' error END
 276 ;
 277 ]])
 278
 279 AT_BISON_CHECK([[-v -o input.c input.y]])
 280
 281 # Get the final state in the parser.
 282 AT_CHECK([[sed -n 's/.*define YYFINAL *\([0-9][0-9]*\)/final state \1/p' input.c]],
 283          0, [stdout])
 284 mv stdout expout
 285
 286 # Get the final state in the report, from the "accept" action..
 287 AT_CHECK([sed -n '
 288            /^state \(.*\)/{
 289              s//final state \1/
 290              x
 291            }
 292            / accept/{
 293              x
 294              p
 295              q
 296            }
 297         ' input.output],
 298         0, [expout])
 299
 300 AT_CLEANUP