diff --git a/lex.js b/lex.js index c49c67d..7f2215a 100644 --- a/lex.js +++ b/lex.js @@ -33,7 +33,12 @@ peek(type = undefined, tokenValue = undefined) { - if (this.index < 0 || this.index >= this.tokens.length) + return this.peekAt(0, type, tokenValue); + } + + peekAt(forwardAmount, type = undefined, tokenValue = undefined) + { + if (this.index + forwardAmount < 0 || this.index + forwardAmount >= this.tokens.length) { let msg = "Unexpected EOF"; if (type !== undefined) @@ -47,7 +52,7 @@ return { error: { msg: msg, ...this.stringPosToLinePos(this.inputLength - 1) } }; } - const token = this.tokens[this.index]; + const token = this.tokens[this.index + forwardAmount]; if (type) { @@ -86,6 +91,21 @@ return token; } + consumeCount(amount) + { + let { error } = this.peekAt(amount - 1); + if (error) return { error: error }; + + for (let saved of this.savedLocations) + { + saved.matched += amount; + } + + this.index += amount; + + return { error: null }; + } + startMatch() { this.savedLocations.push({ index: this.index, matched: 0 }); diff --git a/lex.js b/lex.js index c49c67d..7f2215a 100644 --- a/lex.js +++ b/lex.js @@ -33,7 +33,12 @@ peek(type = undefined, tokenValue = undefined) { - if (this.index < 0 || this.index >= this.tokens.length) + return this.peekAt(0, type, tokenValue); + } + + peekAt(forwardAmount, type = undefined, tokenValue = undefined) + { + if (this.index + forwardAmount < 0 || this.index + forwardAmount >= this.tokens.length) { let msg = "Unexpected EOF"; if (type !== undefined) @@ -47,7 +52,7 @@ return { error: { msg: msg, ...this.stringPosToLinePos(this.inputLength - 1) } }; } - const token = this.tokens[this.index]; + const token = this.tokens[this.index + forwardAmount]; if (type) { @@ -86,6 +91,21 @@ return token; } + consumeCount(amount) + { + let { error } = this.peekAt(amount - 1); + if (error) return { error: error }; + + for (let saved of this.savedLocations) + { + saved.matched += amount; + } + + this.index += amount; + + return { error: null }; + } + startMatch() { this.savedLocations.push({ index: this.index, matched: 0 }); diff --git a/parse.js b/parse.js index f72846d..7b132a3 100644 --- a/parse.js +++ b/parse.js @@ -22,6 +22,7 @@ ".": [100, 101], "?": [6, 5], "=": [2, 1], + "..": [4, 3], }); /* How powerfully a prefix operator binds the value to its right @@ -42,6 +43,29 @@ "(": 60, }); +let InfixOpTree = {}; +let PrefixOpTree = {}; +let PostfixOpTree = {}; +function buildOpTree(allOps, opTree) +{ + for (let op in allOps) + { + let currentOpTree = opTree; + for (let i = 0; i < op.length; i++) + { + if (currentOpTree[op[i]] === undefined) + { + currentOpTree[op[i]] = { more: {} }; + } + if (i == op.length - 1) + { + currentOpTree[op[i]].op = allOps[op]; + } + currentOpTree = currentOpTree[op[i]].more; + } + } +} + // all reserved keywords const Keywords = Object.freeze([ "if", "on", "wait", "for", "map", "in" ]); @@ -57,6 +81,7 @@ ExprStatement:8, // a full statement that is just an expression Statements:9, // a continuous text block of statements Block:10, // a set of statements in a { } block + If:11, // if statement with condition, trueCase, and optional falseCase }); const StatementsWithSemicolon = Object.freeze([ @@ -145,16 +170,44 @@ ifStmt() { let error; - error = this.tokenStream.consume(lex.TokenType.Word, "if").error; + error = this.tokenStream.consume(lex.TokenType.Word, "if").error; if (error) return this.getError(error); + + error = this.tokenStream.consume(lex.TokenType.Op, "(").error; + if (error) return this.getError(error, true); + + let condition; + ({ ast:condition, error } = this.attemptSubtree(this.expression)); + if (error) return this.getError(error, true); + + error = this.tokenStream.consume(lex.TokenType.Op, ")").error; + if (error) return this.getError(error, true); + + let trueCase; + ({ ast:trueCase, error } = this.attemptSubtree(this.block)); + if (error) return this.getError(error, true); + + let ret = { ast: { node: ASTNode.If, condition: condition, trueCase: trueCase }, error: null }; + + if (!this.tokenStream.consume(lex.TokenType.Word, "else").error) + { + let falseCase; + ({ ast:falseCase, error } = this.attemptSubtree(this.block)); + if (error) return this.getError(error, true); + + ret.ast.falseCase = falseCase; + } + + return ret; } statementInternal() { return this.choice( [ - { parse: this.expression, handle: ast => ({ node: ASTNode.ExprStatement, expr: ast }) } + { parse: this.expression, handle: ast => ({ node: ASTNode.ExprStatement, expr: ast }) }, + { parse: this.ifStmt, handle: ast => ast }, ], "Expecting statement"); let error, bestError, numMatched, bestNumMatched = 0; @@ -213,20 +266,27 @@ return this.getError(error); } } - else if ((power = PrefixBindingPower[token]) !== undefined) - { - // this is a prefix operator of the given power - // get the expression it applies to... - let { ast:rhs, error } = this.attemptSubtree(this.expressionInternal, power); - if (error) return this.getError(error); - - // ... and generate an AST node for it - // this becomes the new LHS of the operator we are parsing - lhs = { node:ASTNode.PrefixOp, rhs:rhs, op:token }; - } else { - return this.getError({ msg: "Invalid Op '" + token + "'", ...this.tokenStream.stringPosToLinePos(pos) }); + const largestOp = this.matchLargestOp(PrefixOpTree, token, true); + if (largestOp) + { + token = largestOp.op; + let power = largestOp.value; + + // this is a prefix operator of the given power + // get the expression it applies to... + let { ast:rhs, error } = this.attemptSubtree(this.expressionInternal, power); + if (error) return this.getError(error); + + // ... and generate an AST node for it + // this becomes the new LHS of the operator we are parsing + lhs = { node:ASTNode.PrefixOp, rhs:rhs, op:token }; + } + else + { + return this.getError({ msg: "Invalid Op '" + token + "'", ...this.tokenStream.stringPosToLinePos(pos) }); + } } } else if (type == lex.TokenType.Word) @@ -272,17 +332,21 @@ let { type:opType, token:opToken, pos:opPos, error } = this.tokenStream.peek(lex.TokenType.Op); if (error) return this.getError(error); - if (PostfixBindingPower[opToken] !== undefined) + let largestOp = this.matchLargestOp(PostfixOpTree, opToken); + if (largestOp) { + opToken = largestOp.op; + let power = largestOp.value + // this is a post-fix operator, but it may apply to... - if (PostfixBindingPower[opToken] < minBindingPower) + if (power < minBindingPower) { //... some outer expression (we were too low power to bind to lhs) break; } //... or our current lhs, in which case we get to consume the token - this.tokenStream.consume(); + this.tokenStream.consumeCount(token.length); if (opToken == "[") { @@ -352,20 +416,22 @@ continue; } + largestOp = this.matchLargestOp(InfixOpTree, opToken, false); // if we didn't get an infix operator, we are done this expression - if (InfixBindingPower[opToken] === undefined) + if (!largestOp) { break; } - let [ leftBindingPower, rightBindingPower ] = InfixBindingPower[opToken]; + opToken = largestOp.op; + let [ leftBindingPower, rightBindingPower ] = largestOp.value; // if the binding power is too low, we are done parsing the current subexpression, leave // the current operator for our caller... if (leftBindingPower < minBindingPower) break; //... otherwise, this operator is for us, so consume it - this.tokenStream.consume(); + this.tokenStream.consumeCount(opToken.length); if (opToken == "?") { @@ -408,6 +474,46 @@ return { ast: lhs, error: null }; } + matchLargestOp(opTree, op, opAlreadyConsumed) + { + const ret = this.matchLargestOpInternal(opTree, op); + if (ret && ret.op.length > 1 && opAlreadyConsumed) + { + this.tokenStream.consumeCount(ret.op.length - 1); + } + return ret; + } + + matchLargestOpInternal(opTree, op) + { + const lastOp = op[op.length - 1]; + if (opTree[lastOp] !== undefined) + { + let bestOp = null, bestOpLength = 0; + for (let nextOp in opTree[lastOp].more) + { + if (!this.tokenStream.peekAt(op.length, lex.TokenType.Op, nextOp).error) + { + let betterOp = this.matchLargestOpInternal(opTree[op].more, op + nextOp); + if (betterOp && betterOp.op.length > bestOpLength) + { + bestOp = betterOp; + bestOpLength = bestOp.op.length; + } + } + } + if (bestOp) + { + return bestOp; + } + if (opTree[lastOp].op) + { + return { op: op, value: opTree[lastOp].op }; + } + } + return null; + } + attemptSubtree(parseFunction, ...args) { this.tokenStream.startMatch(); @@ -463,4 +569,10 @@ return ast.mapKey("node", v => ASTNode.keyName(v)); } +(function() { + buildOpTree(InfixBindingPower, InfixOpTree); + buildOpTree(PrefixBindingPower, PrefixOpTree); + buildOpTree(PostfixBindingPower, PostfixOpTree); +})(); + module.exports = { Parser: Parser, getPrettyAST: getPrettyAST };