tests/sets.at

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