1 // Toy interpreter combinator. 2 // 3 // Copyright (C) 2014-2015 Iain Buclaw. 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 3 of the License, or 7 // (at your option) 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, see <http://www.gnu.org/licenses/>. 16 17 // Written by Iain Buclaw <ibuclaw@gdcproject.org> 18 19 module toy.combinator; 20 21 import toy.lex; 22 import toy.ast; 23 import toy.diag; 24 25 import std.algorithm; 26 27 ///// Combinators ///// 28 29 30 /// All combinators return a result. 31 struct Result 32 { 33 Object[] values; 34 int pos; 35 bool inited = false; 36 37 this(Object value, int pos) 38 { 39 this([value], pos); 40 } 41 42 this(Object[] values, int pos) 43 { 44 this.values = values; 45 this.pos = pos; 46 this.inited = true; 47 } 48 } 49 50 /// Base parser class with abstract operators. 51 class Parser 52 { 53 Parser opBinary(string op, T)(T rhs) 54 { 55 static if (op == "+") 56 return new Concat(this, rhs); 57 else static if (op == "*") 58 return new Expr(this, rhs); 59 else static if (op == "|") 60 return new Alternate(this, rhs); 61 else static if (op == "^") 62 return new Process!T(this, rhs); 63 else static if (op == "&") 64 return new Process!T(this, rhs, true); 65 else 66 static assert(false, "Operator " ~ op ~ " not implemented"); 67 } 68 69 Result opCall(Token[] tokens, int pos) 70 { 71 throw new InternalError("opCall not implemented for Parser class: " ~ this.toString()); 72 } 73 } 74 75 /// Top-level parser, consumes all tokens passed. 76 class Phrase : Parser 77 { 78 Parser parser; 79 80 this(Parser parser) 81 { 82 this.parser = parser; 83 } 84 85 override Result opCall(Token[] tokens, int pos) 86 { 87 Result result = this.parser(tokens, pos); 88 89 if (result.inited && result.pos == tokens.length) 90 return result; 91 else 92 throw new ParseError("parsing statement at " ~ tokens[result.pos].value); 93 } 94 } 95 96 /// Parse individual token that matches a particular lex.Tag 97 class TokenTag : Parser 98 { 99 Tag tag; 100 101 this(Tag tag) 102 { 103 this.tag = tag; 104 } 105 106 override Result opCall(Token[] tokens, int pos) 107 { 108 if (pos < tokens.length && tokens[pos].tag == this.tag) 109 return Result(new TokenClass(tokens[pos].value), pos + 1); 110 else 111 return Result(); 112 } 113 } 114 115 /// Parse individual reserved keyword or operator. 116 class Reserved : Parser 117 { 118 string value; 119 120 this(string value) 121 { 122 this.value = value; 123 } 124 125 override Result opCall(Token[] tokens, int pos) 126 { 127 if (pos < tokens.length && tokens[pos].value == this.value && tokens[pos].tag == Tag.Reserved) 128 return Result(new Keyword(tokens[pos].value), pos + 1); 129 else 130 return Result(); 131 } 132 } 133 134 /// Join two parsers together, returning a pair if successful. 135 class Concat : Parser 136 { 137 Parser left, right; 138 139 this(Parser left, Parser right) 140 { 141 this.left = left; 142 this.right = right; 143 } 144 145 override Result opCall(Token[] tokens, int pos) 146 { 147 Result lresult = this.left(tokens, pos); 148 if (lresult.inited) 149 { 150 Result rresult = this.right(tokens, lresult.pos); 151 if (rresult.inited) 152 { 153 lresult.values ~= rresult.values; 154 return Result(lresult.values, rresult.pos); 155 } 156 } 157 return Result(); 158 } 159 } 160 161 /// Applies a parser repeatedly, delimited by a separator until it fails. 162 class Expr : Parser 163 { 164 Parser parser, separator; 165 166 this(Parser parser, Parser separator) 167 { 168 this.parser = parser; 169 this.separator = separator; 170 } 171 172 override Result opCall(Token[] tokens, int pos) 173 { 174 Result result = this.parser(tokens, pos); 175 Parser next = this.separator + this.parser; 176 Result nresult = result; 177 178 while (nresult.inited) 179 { 180 nresult = next(tokens, result.pos); 181 if (nresult.inited) 182 { 183 result.values ~= nresult.values; 184 result.pos = nresult.pos; 185 } 186 } 187 return result; 188 } 189 } 190 191 /// Return either left (higher precedence) or right parser. 192 class Alternate : Parser 193 { 194 Parser left, right; 195 196 this(Parser left, Parser right) 197 { 198 this.left = left; 199 this.right = right; 200 } 201 202 override Result opCall(Token[] tokens, int pos) 203 { 204 Result result = this.left(tokens, pos); 205 if (result.inited) 206 return result; 207 else 208 return this.right(tokens, pos); 209 } 210 } 211 212 /// Returns a successful, even if parsing failed. 213 /// The unsucessful result is represented as 'null'. 214 class Optional : Parser 215 { 216 Parser parser; 217 218 this(Parser parser) 219 { 220 this.parser = parser; 221 } 222 223 override Result opCall(Token[] tokens, int pos) 224 { 225 Result result = this.parser(tokens, pos); 226 if (result.inited) 227 return result; 228 else 229 return Result([null], pos); 230 } 231 } 232 233 /// Applies a parser repeatedly until it fails. 234 class Repetition : Parser 235 { 236 Parser parser; 237 238 this(Parser parser) 239 { 240 this.parser = parser; 241 } 242 243 override Result opCall(Token[] tokens, int pos) 244 { 245 Object[] results; 246 Result result = this.parser(tokens, pos); 247 while (result.inited) 248 { 249 results ~= result.values; 250 pos = result.pos; 251 result = this.parser(tokens, pos); 252 } 253 return Result(results, pos); 254 } 255 } 256 257 /// Manipulates an array of Result values, reducing the result down to a single element. 258 class Process(T) : Parser 259 { 260 Parser parser; 261 T func; 262 bool repeat; 263 264 this(Parser parser, T func, bool repeat = false) 265 { 266 this.parser = parser; 267 this.func = func; 268 this.repeat = repeat; 269 } 270 271 override Result opCall(Token[] tokens, int pos) 272 { 273 Result result = this.parser(tokens, pos); 274 if (result.inited) 275 { 276 static if (is(T : Expression function(TokenClass))) 277 { 278 if (result.values.length != 1) 279 goto LruntimeError; 280 281 TokenClass value = cast(TokenClass) result.values[0]; 282 283 result.values[0] = this.func(value); 284 } 285 else static if (is(T : Expression function(Keyword, Expression))) 286 { 287 if (result.values.length != 2) 288 goto LruntimeError; 289 290 Keyword op = cast(Keyword) result.values[0]; 291 Expression e = cast(Expression) result.values[1]; 292 293 result.values[0] = this.func(op, e); 294 result.values.length = 1; 295 } 296 else static if (is(T : Expression function(Keyword, Expression, Keyword))) 297 { 298 if (result.values.length != 3) 299 goto LruntimeError; 300 301 Keyword l = cast(Keyword) result.values[0]; 302 Expression e = cast(Expression) result.values[1]; 303 Keyword r = cast(Keyword) result.values[2]; 304 305 result.values[0] = this.func(l, e, r); 306 result.values.length = 1; 307 } 308 else static if (is(T : Expression function(Expression, Keyword, Expression))) 309 { 310 if (this.repeat == true) 311 { 312 while (result.values.length != 1) 313 { 314 if (result.values.length < 3) 315 goto LruntimeError; 316 317 Expression l = cast(Expression) result.values[0]; 318 Keyword op = cast(Keyword) result.values[1]; 319 Expression r = cast(Expression) result.values[2]; 320 321 result.values[0] = this.func(l, op, r); 322 result.values = result.values.remove(1, 2); 323 } 324 } 325 else 326 { 327 if (result.values.length != 3) 328 goto LruntimeError; 329 330 Expression l = cast(Expression) result.values[0]; 331 Keyword op = cast(Keyword) result.values[1]; 332 Expression r = cast(Expression) result.values[2]; 333 334 result.values[0] = this.func(l, op, r); 335 result.values.length = 1; 336 } 337 } 338 else static if (is(T : Statement function(Keyword, Expression))) 339 { 340 if (result.values.length != 2) 341 goto LruntimeError; 342 343 Keyword op = cast(Keyword) result.values[0]; 344 Expression s = cast(Expression) result.values[1]; 345 346 result.values[0] = this.func(op, s); 347 result.values.length = 1; 348 } 349 else static if (is(T : Statement function(Keyword, Statement))) 350 { 351 if (result.values.length != 2) 352 goto LruntimeError; 353 354 Keyword op = cast(Keyword) result.values[0]; 355 Statement s = cast(Statement) result.values[1]; 356 357 result.values[0] = this.func(op, s); 358 result.values.length = 1; 359 } 360 else static if (is(T : Statement function(Expression, Keyword, Expression))) 361 { 362 if (result.values.length != 3) 363 goto LruntimeError; 364 365 Expression l = cast(Expression) result.values[0]; 366 Keyword op = cast(Keyword) result.values[1]; 367 Expression r = cast(Expression) result.values[2]; 368 369 result.values[0] = this.func(l, op, r); 370 result.values.length = 1; 371 } 372 else static if (is(T : Statement function(Statement, Keyword, Statement))) 373 { 374 if (this.repeat == true) 375 { 376 while (result.values.length != 1) 377 { 378 if (result.values.length < 3) 379 goto LruntimeError; 380 381 Statement l = cast(Statement) result.values[0]; 382 Keyword op = cast(Keyword) result.values[1]; 383 Statement r = cast(Statement) result.values[2]; 384 385 result.values[0] = this.func(l, op, r); 386 result.values = result.values.remove(1, 2); 387 } 388 } 389 else 390 { 391 if (result.values.length != 3) 392 goto LruntimeError; 393 394 Statement l = cast(Statement) result.values[0]; 395 Keyword op = cast(Keyword) result.values[1]; 396 Statement r = cast(Statement) result.values[2]; 397 398 result.values[0] = this.func(l, op, r); 399 result.values.length = 1; 400 } 401 } 402 else static if (is(T : Statement function(Keyword, Expression, Keyword, Statement, Keyword))) 403 { 404 if (result.values.length != 5) 405 goto LruntimeError; 406 407 Keyword op1 = cast(Keyword) result.values[0]; 408 Expression e1 = cast(Expression) result.values[1]; 409 Keyword op2 = cast(Keyword) result.values[2]; 410 Statement s1 = cast(Statement) result.values[3]; 411 Keyword op3 = cast(Keyword) result.values[4]; 412 413 result.values[0] = this.func(op1, e1, op2, s1, op3); 414 result.values.length = 1; 415 } 416 else static if (is(T : Statement function(Keyword, Expression, Keyword, Statement, Statement, Keyword))) 417 { 418 if (result.values.length != 6) 419 goto LruntimeError; 420 421 Keyword op1 = cast(Keyword) result.values[0]; 422 Expression e1 = cast(Expression) result.values[1]; 423 Keyword op2 = cast(Keyword) result.values[2]; 424 Statement s1 = cast(Statement) result.values[3]; 425 Statement s2 = cast(Statement) result.values[4]; 426 Keyword op3 = cast(Keyword) result.values[5]; 427 428 result.values[0] = this.func(op1, e1, op2, s1, s2, op3); 429 result.values.length = 1; 430 } 431 else 432 static assert(false, "Unhandled type " ~ T.stringof); 433 } 434 return result; 435 436 LruntimeError: 437 throw new InternalError("Result mismatch at " ~ tokens[result.pos].value); 438 } 439 } 440 441 /// For building recursive parsers, delays getting the parser until it's applied. 442 class Lazy : Parser 443 { 444 Parser parser; 445 Parser function() func; 446 447 this(Parser function() func) 448 { 449 this.parser = null; 450 this.func = func; 451 } 452 453 override Result opCall(Token[] tokens, int pos) 454 { 455 if (this.parser is null) 456 this.parser = this.func(); 457 return this.parser(tokens, pos); 458 } 459 } 460