Blame

Date:
Message:
rc: add recursive descent parser The old yacc-based parser is available with the -Y flag, which will probably be removed at some point. The new -D flag dumps a parse tree of the input, without executing it. This allows comparing the output of rc -D and rc -DY on different scripts to see that the two parsers behave the same. The rc paper ends by saying: It is remarkable that in the four most recent editions of the UNIX system programmer’s manual the Bourne shell grammar described in the manual page does not admit the command who|wc. This is surely an oversight, but it suggests something darker: nobody really knows what the Bourne shell’s grammar is. Even examination of the source code is little help. The parser is implemented by recursive descent, but the routines corresponding to the syntactic categories all have a flag argument that subtly changes their operation depending on the context. Rc’s parser is implemented using yacc, so I can say precisely what the grammar is. The new recursive descent parser here has no such flags. It is a straightforward translation of the yacc. The new parser will make it easier to handle free carats in more generality as well as potentially allow the use of unquoted = as a word character. Going through this exercise has highlighted a few dark corners here as well. For example, I was surprised to find that x >f | y >f x | y are different commands (the latter redirects y's output). It is similarly surprising that a=b x | y sets a during the execution of y. It is also a bit counter-intuitive x | y | z x | if(c) y | z are not both 3-phase pipelines. These are certainly not things we should change, but they are not entirely obvious from the man page description, undercutting the quoted claim a bit. On the other hand, who | wc is clearly accepted by the grammar in the manual page, and the new parser still handles that test case.
Actions:
History | Blob | Raw File
  1 1bfec89b 2013-03-19 rsc #include <limits.h>

  2 f08fdedc 2003-11-23 devnull #include "rc.h"

  3 f08fdedc 2003-11-23 devnull #include "exec.h"

  4 f08fdedc 2003-11-23 devnull #include "io.h"

  5 f08fdedc 2003-11-23 devnull #include "fns.h"

  6 c8f53842 2007-03-26 devnull int pfmtnest = 0;

  7 c8f53842 2007-03-26 devnull 

  8 c8f53842 2007-03-26 devnull void

  9 c8f53842 2007-03-26 devnull pfmt(io *f, char *fmt, ...)

 10 c8f53842 2007-03-26 devnull {

 11 f08fdedc 2003-11-23 devnull 	va_list ap;

 12 f08fdedc 2003-11-23 devnull 	char err[ERRMAX];

 13 f08fdedc 2003-11-23 devnull 	va_start(ap, fmt);

 14 f08fdedc 2003-11-23 devnull 	pfmtnest++;

 15 f08fdedc 2003-11-23 devnull 	for(;*fmt;fmt++)

 16 c8f53842 2007-03-26 devnull 		if(*fmt!='%')

 17 c8f53842 2007-03-26 devnull 			pchr(f, *fmt);

 18 f08fdedc 2003-11-23 devnull 		else switch(*++fmt){

 19 c8f53842 2007-03-26 devnull 		case '\0':

 20 c8f53842 2007-03-26 devnull 			va_end(ap);

 21 c8f53842 2007-03-26 devnull 			return;

 22 c8f53842 2007-03-26 devnull 		case 'c':

 23 c8f53842 2007-03-26 devnull 			pchr(f, va_arg(ap, int));

 24 c8f53842 2007-03-26 devnull 			break;

 25 c8f53842 2007-03-26 devnull 		case 'd':

 26 c8f53842 2007-03-26 devnull 			pdec(f, va_arg(ap, int));

 27 c8f53842 2007-03-26 devnull 			break;

 28 c8f53842 2007-03-26 devnull 		case 'o':

 29 c8f53842 2007-03-26 devnull 			poct(f, va_arg(ap, unsigned));

 30 c8f53842 2007-03-26 devnull 			break;

 31 c8f53842 2007-03-26 devnull 		case 'p':

 32 c8f53842 2007-03-26 devnull 			pptr(f, va_arg(ap, void*));

 33 c8f53842 2007-03-26 devnull 			break;

 34 c8f53842 2007-03-26 devnull 		case 'Q':

 35 c8f53842 2007-03-26 devnull 			pquo(f, va_arg(ap, char *));

 36 c8f53842 2007-03-26 devnull 			break;

 37 c8f53842 2007-03-26 devnull 		case 'q':

 38 c8f53842 2007-03-26 devnull 			pwrd(f, va_arg(ap, char *));

 39 c8f53842 2007-03-26 devnull 			break;

 40 c8f53842 2007-03-26 devnull 		case 'r':

 41 40402738 2007-03-26 devnull 			rerrstr(err, sizeof err); pstr(f, err);

 42 c8f53842 2007-03-26 devnull 			break;

 43 c8f53842 2007-03-26 devnull 		case 's':

 44 c8f53842 2007-03-26 devnull 			pstr(f, va_arg(ap, char *));

 45 c8f53842 2007-03-26 devnull 			break;

 46 c8f53842 2007-03-26 devnull 		case 't':

 47 47d4646e 2020-05-05 rsc 			pcmd(f, va_arg(ap, tree *));

 48 c8f53842 2007-03-26 devnull 			break;

 49 47d4646e 2020-05-05 rsc 		case 'u':

 50 47d4646e 2020-05-05 rsc 			pcmdu(f, va_arg(ap, tree *));

 51 47d4646e 2020-05-05 rsc 			break;

 52 c8f53842 2007-03-26 devnull 		case 'v':

 53 c8f53842 2007-03-26 devnull 			pval(f, va_arg(ap, struct word *));

 54 c8f53842 2007-03-26 devnull 			break;

 55 c8f53842 2007-03-26 devnull 		default:

 56 c8f53842 2007-03-26 devnull 			pchr(f, *fmt);

 57 c8f53842 2007-03-26 devnull 			break;

 58 f08fdedc 2003-11-23 devnull 		}

 59 f08fdedc 2003-11-23 devnull 	va_end(ap);

 60 c8f53842 2007-03-26 devnull 	if(--pfmtnest==0)

 61 c8f53842 2007-03-26 devnull 		flush(f);

 62 f08fdedc 2003-11-23 devnull }

 63 c8f53842 2007-03-26 devnull 

 64 c8f53842 2007-03-26 devnull void

 65 c8f53842 2007-03-26 devnull pchr(io *b, int c)

 66 f08fdedc 2003-11-23 devnull {

 67 c8f53842 2007-03-26 devnull 	if(b->bufp==b->ebuf)

 68 c8f53842 2007-03-26 devnull 		fullbuf(b, c);

 69 f08fdedc 2003-11-23 devnull 	else *b->bufp++=c;

 70 f08fdedc 2003-11-23 devnull }

 71 c8f53842 2007-03-26 devnull 

 72 c8f53842 2007-03-26 devnull int

 73 c8f53842 2007-03-26 devnull rchr(io *b)

 74 f08fdedc 2003-11-23 devnull {

 75 c8f53842 2007-03-26 devnull 	if(b->bufp==b->ebuf)

 76 c8f53842 2007-03-26 devnull 		return emptybuf(b);

 77 f08fdedc 2003-11-23 devnull 	return *b->bufp++ & 0xFF;

 78 f08fdedc 2003-11-23 devnull }

 79 f08fdedc 2003-11-23 devnull 

 80 c8f53842 2007-03-26 devnull void

 81 c8f53842 2007-03-26 devnull pquo(io *f, char *s)

 82 f08fdedc 2003-11-23 devnull {

 83 f08fdedc 2003-11-23 devnull 	pchr(f, '\'');

 84 f08fdedc 2003-11-23 devnull 	for(;*s;s++)

 85 c8f53842 2007-03-26 devnull 		if(*s=='\'')

 86 c8f53842 2007-03-26 devnull 			pfmt(f, "''");

 87 f08fdedc 2003-11-23 devnull 		else pchr(f, *s);

 88 f08fdedc 2003-11-23 devnull 	pchr(f, '\'');

 89 f08fdedc 2003-11-23 devnull }

 90 c8f53842 2007-03-26 devnull 

 91 c8f53842 2007-03-26 devnull void

 92 c8f53842 2007-03-26 devnull pwrd(io *f, char *s)

 93 f08fdedc 2003-11-23 devnull {

 94 f08fdedc 2003-11-23 devnull 	char *t;

 95 c8f53842 2007-03-26 devnull 	for(t = s;*t;t++) if(!wordchr(*t)) break;

 96 c8f53842 2007-03-26 devnull 	if(t==s || *t)

 97 c8f53842 2007-03-26 devnull 		pquo(f, s);

 98 f08fdedc 2003-11-23 devnull 	else pstr(f, s);

 99 f08fdedc 2003-11-23 devnull }

100 c8f53842 2007-03-26 devnull 

101 c8f53842 2007-03-26 devnull void

102 c8f53842 2007-03-26 devnull pptr(io *f, void *v)

103 f08fdedc 2003-11-23 devnull {

104 f08fdedc 2003-11-23 devnull 	int n;

105 c8f53842 2007-03-26 devnull 	uintptr p;

106 c8f53842 2007-03-26 devnull 

107 c8f53842 2007-03-26 devnull 	p = (uintptr)v;

108 c8f53842 2007-03-26 devnull 	if(sizeof(uintptr) == sizeof(uvlong) && p>>32)

109 c8f53842 2007-03-26 devnull 		for(n = 60;n>=32;n-=4) pchr(f, "0123456789ABCDEF"[(p>>n)&0xF]);

110 c8f53842 2007-03-26 devnull 

111 c8f53842 2007-03-26 devnull 	for(n = 28;n>=0;n-=4) pchr(f, "0123456789ABCDEF"[(p>>n)&0xF]);

112 f08fdedc 2003-11-23 devnull }

113 c8f53842 2007-03-26 devnull 

114 c8f53842 2007-03-26 devnull void

115 c8f53842 2007-03-26 devnull pstr(io *f, char *s)

116 f08fdedc 2003-11-23 devnull {

117 c8f53842 2007-03-26 devnull 	if(s==0)

118 c8f53842 2007-03-26 devnull 		s="(null)";

119 f08fdedc 2003-11-23 devnull 	while(*s) pchr(f, *s++);

120 f08fdedc 2003-11-23 devnull }

121 c8f53842 2007-03-26 devnull 

122 c8f53842 2007-03-26 devnull void

123 c8f53842 2007-03-26 devnull pdec(io *f, int n)

124 f08fdedc 2003-11-23 devnull {

125 f08fdedc 2003-11-23 devnull 	if(n<0){

126 1bfec89b 2013-03-19 rsc 		if(n!=INT_MIN){

127 f08fdedc 2003-11-23 devnull 			pchr(f, '-');

128 1bfec89b 2013-03-19 rsc 			pdec(f, -n);

129 f08fdedc 2003-11-23 devnull 			return;

130 f08fdedc 2003-11-23 devnull 		}

131 f08fdedc 2003-11-23 devnull 		/* n is two's complement minimum integer */

132 1bfec89b 2013-03-19 rsc 		n = -(INT_MIN+1);

133 f08fdedc 2003-11-23 devnull 		pchr(f, '-');

134 f08fdedc 2003-11-23 devnull 		pdec(f, n/10);

135 f08fdedc 2003-11-23 devnull 		pchr(f, n%10+'1');

136 f08fdedc 2003-11-23 devnull 		return;

137 f08fdedc 2003-11-23 devnull 	}

138 c8f53842 2007-03-26 devnull 	if(n>9)

139 c8f53842 2007-03-26 devnull 		pdec(f, n/10);

140 f08fdedc 2003-11-23 devnull 	pchr(f, n%10+'0');

141 f08fdedc 2003-11-23 devnull }

142 c8f53842 2007-03-26 devnull 

143 c8f53842 2007-03-26 devnull void

144 c8f53842 2007-03-26 devnull poct(io *f, unsigned n)

145 f08fdedc 2003-11-23 devnull {

146 c8f53842 2007-03-26 devnull 	if(n>7)

147 c8f53842 2007-03-26 devnull 		poct(f, n>>3);

148 f08fdedc 2003-11-23 devnull 	pchr(f, (n&7)+'0');

149 f08fdedc 2003-11-23 devnull }

150 c8f53842 2007-03-26 devnull 

151 c8f53842 2007-03-26 devnull void

152 c8f53842 2007-03-26 devnull pval(io *f, word *a)

153 f08fdedc 2003-11-23 devnull {

154 f08fdedc 2003-11-23 devnull 	if(a){

155 f08fdedc 2003-11-23 devnull 		while(a->next && a->next->word){

156 f08fdedc 2003-11-23 devnull 			pwrd(f, a->word);

157 f08fdedc 2003-11-23 devnull 			pchr(f, ' ');

158 c8f53842 2007-03-26 devnull 			a = a->next;

159 f08fdedc 2003-11-23 devnull 		}

160 f08fdedc 2003-11-23 devnull 		pwrd(f, a->word);

161 f08fdedc 2003-11-23 devnull 	}

162 f08fdedc 2003-11-23 devnull }

163 c8f53842 2007-03-26 devnull 

164 c8f53842 2007-03-26 devnull int

165 c8f53842 2007-03-26 devnull fullbuf(io *f, int c)

166 f08fdedc 2003-11-23 devnull {

167 f08fdedc 2003-11-23 devnull 	flush(f);

168 f08fdedc 2003-11-23 devnull 	return *f->bufp++=c;

169 f08fdedc 2003-11-23 devnull }

170 c8f53842 2007-03-26 devnull 

171 c8f53842 2007-03-26 devnull void

172 c8f53842 2007-03-26 devnull flush(io *f)

173 f08fdedc 2003-11-23 devnull {

174 f08fdedc 2003-11-23 devnull 	int n;

175 f08fdedc 2003-11-23 devnull 	char *s;

176 f08fdedc 2003-11-23 devnull 	if(f->strp){

177 c8f53842 2007-03-26 devnull 		n = f->ebuf-f->strp;

178 c8f53842 2007-03-26 devnull 		f->strp = realloc(f->strp, n+101);

179 c8f53842 2007-03-26 devnull 		if(f->strp==0)

180 c8f53842 2007-03-26 devnull 			panic("Can't realloc %d bytes in flush!", n+101);

181 c8f53842 2007-03-26 devnull 		f->bufp = f->strp+n;

182 c8f53842 2007-03-26 devnull 		f->ebuf = f->bufp+100;

183 c8f53842 2007-03-26 devnull 		for(s = f->bufp;s<=f->ebuf;s++) *s='\0';

184 f08fdedc 2003-11-23 devnull 	}

185 f08fdedc 2003-11-23 devnull 	else{

186 c8f53842 2007-03-26 devnull 		n = f->bufp-f->buf;

187 f08fdedc 2003-11-23 devnull 		if(n && Write(f->fd, f->buf, n) < 0){

188 f08fdedc 2003-11-23 devnull 			Write(3, "Write error\n", 12);

189 c8f53842 2007-03-26 devnull 			if(ntrap)

190 c8f53842 2007-03-26 devnull 				dotrap();

191 f08fdedc 2003-11-23 devnull 		}

192 c8f53842 2007-03-26 devnull 		f->bufp = f->buf;

193 c8f53842 2007-03-26 devnull 		f->ebuf = f->buf+NBUF;

194 f08fdedc 2003-11-23 devnull 	}

195 f08fdedc 2003-11-23 devnull }

196 c8f53842 2007-03-26 devnull 

197 c8f53842 2007-03-26 devnull io*

198 c8f53842 2007-03-26 devnull openfd(int fd)

199 c8f53842 2007-03-26 devnull {

200 c8f53842 2007-03-26 devnull 	io *f = new(struct io);

201 c8f53842 2007-03-26 devnull 	f->fd = fd;

202 c8f53842 2007-03-26 devnull 	f->bufp = f->ebuf = f->buf;

203 c8f53842 2007-03-26 devnull 	f->strp = 0;

204 f08fdedc 2003-11-23 devnull 	return f;

205 f08fdedc 2003-11-23 devnull }

206 c8f53842 2007-03-26 devnull 

207 c8f53842 2007-03-26 devnull io*

208 c8f53842 2007-03-26 devnull openstr(void)

209 c8f53842 2007-03-26 devnull {

210 c8f53842 2007-03-26 devnull 	io *f = new(struct io);

211 f08fdedc 2003-11-23 devnull 	char *s;

212 f08fdedc 2003-11-23 devnull 	f->fd=-1;

213 c8f53842 2007-03-26 devnull 	f->bufp = f->strp = emalloc(101);

214 c8f53842 2007-03-26 devnull 	f->ebuf = f->bufp+100;

215 c8f53842 2007-03-26 devnull 	for(s = f->bufp;s<=f->ebuf;s++) *s='\0';

216 f08fdedc 2003-11-23 devnull 	return f;

217 f08fdedc 2003-11-23 devnull }

218 f08fdedc 2003-11-23 devnull /*

219 f08fdedc 2003-11-23 devnull  * Open a corebuffer to read.  EOF occurs after reading len

220 f08fdedc 2003-11-23 devnull  * characters from buf.

221 f08fdedc 2003-11-23 devnull  */

222 c8f53842 2007-03-26 devnull 

223 c8f53842 2007-03-26 devnull io*

224 c8f53842 2007-03-26 devnull opencore(char *s, int len)

225 f08fdedc 2003-11-23 devnull {

226 c8f53842 2007-03-26 devnull 	io *f = new(struct io);

227 c8f53842 2007-03-26 devnull 	char *buf = emalloc(len);

228 f08fdedc 2003-11-23 devnull 	f->fd= -1 /*open("/dev/null", 0)*/;

229 c8f53842 2007-03-26 devnull 	f->bufp = f->strp = buf;

230 c8f53842 2007-03-26 devnull 	f->ebuf = buf+len;

231 f08fdedc 2003-11-23 devnull 	Memcpy(buf, s, len);

232 f08fdedc 2003-11-23 devnull 	return f;

233 f08fdedc 2003-11-23 devnull }

234 c8f53842 2007-03-26 devnull 

235 c8f53842 2007-03-26 devnull void

236 2894c70c 2007-03-26 devnull iorewind(io *io)

237 f08fdedc 2003-11-23 devnull {

238 c8f53842 2007-03-26 devnull 	if(io->fd==-1)

239 c8f53842 2007-03-26 devnull 		io->bufp = io->strp;

240 f08fdedc 2003-11-23 devnull 	else{

241 c8f53842 2007-03-26 devnull 		io->bufp = io->ebuf = io->buf;

242 f08fdedc 2003-11-23 devnull 		Seek(io->fd, 0L, 0);

243 f08fdedc 2003-11-23 devnull 	}

244 f08fdedc 2003-11-23 devnull }

245 c8f53842 2007-03-26 devnull 

246 c8f53842 2007-03-26 devnull void

247 c8f53842 2007-03-26 devnull closeio(io *io)

248 f08fdedc 2003-11-23 devnull {

249 c8f53842 2007-03-26 devnull 	if(io->fd>=0)

250 c8f53842 2007-03-26 devnull 		close(io->fd);

251 c8f53842 2007-03-26 devnull 	if(io->strp)

252 c8f53842 2007-03-26 devnull 		efree(io->strp);

253 f08fdedc 2003-11-23 devnull 	efree((char *)io);

254 f08fdedc 2003-11-23 devnull }

255 c8f53842 2007-03-26 devnull 

256 c8f53842 2007-03-26 devnull int

257 c8f53842 2007-03-26 devnull emptybuf(io *f)

258 f08fdedc 2003-11-23 devnull {

259 f08fdedc 2003-11-23 devnull 	int n;

260 c8f53842 2007-03-26 devnull 	if(f->fd==-1 || (n = Read(f->fd, f->buf, NBUF))<=0) return EOF;

261 c8f53842 2007-03-26 devnull 	f->bufp = f->buf;

262 c8f53842 2007-03-26 devnull 	f->ebuf = f->buf+n;

263 f08fdedc 2003-11-23 devnull 	return *f->bufp++&0xff;

264 f08fdedc 2003-11-23 devnull }