| 1 | # Exercising Bison Grammar Sets. -*- Autotest -*- |
| 2 | # Copyright (C) 2001-2002, 2005, 2007, 2009-2010 Free Software |
| 3 | # Foundation, 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 |