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