1# Exercising Bison Grammar Sets. -*- Autotest -*- 2# Copyright (C) 2001, 2002, 2005 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 2, or (at your option) 7# 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, write to the Free Software 16# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 17# 02110-1301, USA. 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. 25m4_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]]) 53AT_CHECK([sed -f extract.sed $1], 0, [stdout]) 54AT_CHECK([mv stdout $2]) 55]) 56 57 58 59AT_BANNER([[Grammar Sets (Firsts etc.).]]) 60 61 62## ---------- ## 63## Nullable. ## 64## ---------- ## 65 66AT_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 76AT_DATA([[input.y]], 77[[%% 78e: 'e' | /* Nothing */; 79]]) 80 81AT_CHECK([[bison --trace=sets input.y]], [], [], [stderr]) 82AT_EXTRACT_SETS([stderr], [sets]) 83AT_CHECK([[cat sets]], [], 84[[DERIVES 85 $accept derives 86 0 e $end 87 e derives 88 1 'e' 89 2 /* empty */ 90NULLABLE 91 $accept: no 92 e: yes 93FIRSTS 94 $accept firsts 95 $accept 96 e 97 e firsts 98 e 99FDERIVES 100 $accept derives 101 0 e $end 102 1 'e' 103 2 /* empty */ 104 e derives 105 1 'e' 106 2 /* empty */ 107]]) 108 109AT_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 151AT_SETUP([Broken Closure]) 152 153AT_DATA([input.y], 154[[%% 155a: b; 156b: c; 157c: d; 158d: e; 159e: f; 160f: g; 161g: h; 162h: 'h'; 163]]) 164 165AT_CHECK([[bison --trace=sets input.y]], [], [], [stderr]) 166 167AT_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 `---------' 182RTC: Firsts Output END 183]]) 184 185AT_CLEANUP 186 187 188 189## -------- ## 190## Firsts. ## 191## -------- ## 192 193AT_SETUP([Firsts]) 194 195AT_DATA([input.y], 196[[%nonassoc '<' '>' 197%left '+' '-' 198%right '^' '=' 199%% 200exp: 201 exp '<' exp 202 | exp '>' exp 203 | exp '+' exp 204 | exp '-' exp 205 | exp '^' exp 206 | exp '=' exp 207 | "exp" 208 ; 209]]) 210 211AT_CHECK([[bison --trace=sets input.y]], [], [], [stderr]) 212AT_EXTRACT_SETS([stderr], [sets]) 213AT_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" 225NULLABLE 226 $accept: no 227 exp: no 228FIRSTS 229 $accept firsts 230 $accept 231 exp 232 exp firsts 233 exp 234FDERIVES 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 254AT_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 269AT_SETUP([Accept]) 270 271AT_DATA([input.y], 272[[%token END 0 273%% 274input: 275 'a' 276| '(' input ')' 277| '(' error END 278; 279]]) 280 281AT_CHECK([[bison -v -o input.c input.y]]) 282 283# Get the final state in the parser. 284AT_CHECK([[sed -n 's/.*define YYFINAL *\([0-9][0-9]*\)/final state \1/p' input.c]], 285 0, [stdout]) 286mv stdout expout 287 288# Get the final state in the report, from the "accept" action.. 289AT_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 302AT_CLEANUP 303