Differences
This shows you the differences between two versions of the page.
Both sides previous revision Previous revision | |||
creating:evaluation [2025/04/17 15:34] – Split evaluation tutorial into its own page ahelwer | creating:evaluation [2025/04/17 15:37] (current) – old revision restored (2025/04/17 15:20) ahelwer | ||
---|---|---|---|
Line 1: | Line 1: | ||
- | ======= | + | ======= |
- | This tutorial page covers | + | Now that we can parse expressions, |
- | - [[https:// | + | Here we follow |
- | - [[https://craftinginterpreters.com/parsing-expressions.html|Chapter 6: Parsing Expressions]] | + | It's an exciting chapter, so let's jump in. |
- | Same as the book, we //could// build a parser for our entire minimal TLA⁺ language subset before moving on to interpreting it, but that would be boring! | + | ====== Section 7.1: Representing Values ====== |
- | Instead we focus on a simple vertical slice of the language: expressions. | + | |
- | And not just any expressions, | + | |
- | Just primitive literal values stuck together, not too much more advanced than a simple calculator app. | + | |
- | This will give us a skeleton on which to hang the rest of the language. | + | |
- | Each section in this tutorial corresponds to one or more sections of //Crafting Interpreters/ | + | In [[https://craftinginterpreters.com/evaluating-expressions.html# |
- | First read the section of the book, then read the corresponding commentary & modifications given by this tutorial. | + | Our mapping for TLA⁺ is fairly similar to Lox, although we use '' |
+ | TLA⁺ thankfully lacks '' | ||
- | ====== Chapter 5: Representing Code ====== | + | ^ TLA⁺ type ^ Java representation |
+ | | Any TLA⁺ value | '' | ||
+ | | Boolean | ||
+ | | number | ||
+ | | set | '' | ||
- | [[https:// | + | Java does a huge amount of work for us with the capabilities of the '' |
- | However, since this tutorial is intended to be self-contained code-wise, all necessary code is reproduced. | + | |
- | ===== Section | + | ====== Section |
- | Everything before | + | [[https:// |
- | The ambiguous first-draft grammar for Lox expressions can be adapted to TLA⁺: | + | Create a new file '' |
- | <code eiffel> | + | |
- | expression | + | |
- | | unary | + | |
- | | binary | + | |
- | | ternary | + | |
- | | variadic | + | |
- | | grouping ; | + | |
- | literal | + | <code java [highlight_lines_extra="1,3,4"]> |
- | grouping | + | package tla; |
- | unary → (( " | + | |
- | binary | + | |
- | ternary | + | |
- | variadic | + | |
- | operator | + | |
- | </ | + | |
- | There are a few interesting differences. | + | |
- | The '' | + | |
- | The '' | + | |
- | The operators are changed to the set of operators defined in our TLA⁺ implementation. | + | |
- | These are all the expressions we can use without introducing the concept of identifiers referring to something else. | + | |
- | There is also the '' | + | import java.util.Set; |
- | This one is so named because it's where we'll put operators accepting varying numbers of parameters. | + | import java.util.HashSet; |
- | It's kind of weird to think of the finite set literal '' | + | |
- | The only difference between '' | + | |
- | This is the perspective of a language implementer. | + | |
- | Later on we will extend the definition of '' | + | |
- | ===== Section 5.2: Implementing Syntax Trees ===== | + | class Interpreter implements Expr.Visitor< |
+ | } | ||
+ | </ | ||
- | While some programmers might have an aversion to generating code, the approach taken in the book is actually very convenient - as you will discover if you take some time to prototype & play around with different class representations of the parse tree! | + | If your IDE supports it, get it to automatically add all necessary stub methods to implement |
- | In [[https:// | + | |
- | <code java [highlight_lines_extra=" | + | Let's start with defining the value of literals. |
- | package tool; | + | Our code is completely unchanged from the book; add this '' |
- | import | + | < |
- | import java.io.PrintWriter; | + | |
- | import java.util.Arrays; | + | public |
- | import java.util.List; | + | |
- | + | ||
- | public class GenerateAst { | + | |
- | public | + | |
- | if (args.length != 1) { | + | |
- | System.err.println(" | + | |
- | System.exit(64); | + | |
- | | + | |
- | String outputDir = args[0]; | + | |
- | defineAst(outputDir, | + | |
- | " | + | |
- | " | + | |
- | " | + | |
- | " | + | |
- | " | + | |
- | " | + | |
- | )); | + | |
} | } | ||
- | } | ||
</ | </ | ||
- | In the '' | + | Our code for evaluating grouping (parentheses) is similarly unchanged from the book: |
- | <code java [highlight_lines_extra=" | + | <code java> |
- | | + | |
- | | + | |
- | throws IOException { | + | |
- | String path = outputDir + "/" | + | |
- | PrintWriter writer = new PrintWriter(path, " | + | |
- | + | ||
- | writer.println(" | + | |
- | writer.println(); | + | |
- | writer.println(" | + | |
- | writer.println(); | + | |
- | writer.println(" | + | |
- | + | ||
- | + | ||
- | | + | |
- | for (String type : types) { | + | |
- | String className = type.split(":" | + | |
- | String fields = type.split(":" | + | |
- | defineType(writer, | + | |
- | } | + | |
- | writer.println(" | + | |
- | writer.close(); | + | |
} | } | ||
</ | </ | ||
- | Finally, | + | This uses the '' |
<code java> | <code java> | ||
- | private | + | private |
- | PrintWriter writer, String baseName, | + | |
- | String className, String fieldList) { | + | |
- | | + | |
- | baseName + " {"); | + | |
- | + | ||
- | // Constructor. | + | |
- | writer.println(" | + | |
- | + | ||
- | // Store parameters in fields. | + | |
- | String[] fields = fieldList.split(", | + | |
- | for (String field : fields) { | + | |
- | String name = field.split(" | + | |
- | writer.println(" | + | |
- | } | + | |
- | + | ||
- | writer.println(" | + | |
- | + | ||
- | // Fields. | + | |
- | writer.println(); | + | |
- | for (String field : fields) { | + | |
- | writer.println(" | + | |
- | } | + | |
- | + | ||
- | writer.println(" | + | |
} | } | ||
</ | </ | ||
+ | ==== Evaluating Unary Operators ==== | ||
- | ===== Section 5.3: Working with Trees ===== | + | Our first real difference is in the '' |
+ | Recall that since our '' | ||
+ | Here's how we define the negative prefix operator, casting the parameter to an '' | ||
- | [[https:// | + | <code java [highlight_lines_extra=" |
- | No TLA⁺-specific differences are necessary when modifying '' | + | @Override |
- | Insert this line in '' | + | public Object visitUnaryExpr(Expr.Unary expr) { |
- | <code java [highlight_lines_extra=" | + | |
- | | + | |
- | | + | |
- | + | | |
- | // The AST classes. | + | |
- | </ | + | |
- | + | ||
- | This calls the '' | + | |
- | <code java> | + | |
- | private static void defineVisitor( | + | |
- | PrintWriter writer, String baseName, List< | + | |
- | writer.println(" | + | |
- | + | ||
- | for (String | + | |
- | | + | |
- | | + | |
- | typeName + " " + baseName.toLowerCase() + " | + | |
} | } | ||
- | | + | |
+ | return null; | ||
} | } | ||
</ | </ | ||
- | Again insert some lines in '' | + | Note that the negative prefix operator is not actually a built-in operator of TLA⁺. |
- | <code java [highlight_lines_extra=" | + | It is defined |
- | | + | However, because our minimal TLA⁺ language subset lacks module importing, for convenience we just define some common arithmetic operators as built-in. |
- | } | + | You can find more information about the built-in TLA⁺ operators in chapter 16 of // |
- | // The base accept() method. | + | Our logical-not prefix operator is denoted by the '' |
- | | + | We also have no use for the '' |
- | | + | Add this code to the '' |
- | writer.println("}"); | + | <code java [highlight_lines_extra="2,3"]> |
+ | switch (expr.operator.type) { | ||
+ | case NOT: | ||
+ | return !(boolean)operand; | ||
+ | case MINUS: | ||
</ | </ | ||
- | Finally, insert some lines in '' | + | We still have two more unary operators to define: '' |
- | <code java [highlight_lines_extra=" | + | Both are trivial |
- | writer.println(" | + | For constant expressions, |
+ | Add the highlighted code to the '' | ||
- | // Visitor pattern. | + | <code java [highlight_lines_extra="2,3"]> |
- | writer.println(); | + | |
- | writer.println(" | + | |
- | | + | |
- | | + | case NOT: |
- | | + | |
- | | + | |
- | + | ||
- | // Fields. | + | |
</ | </ | ||
- | Our generated syntax tree node types now support the visitor pattern! | ||
- | ===== Section 5.4: A (Not Very) Pretty Printer ===== | + | Priming a constant expression has no effect on the value of that expression, so just return the operand' |
- | [[https:// | + | <code java [highlight_lines_extra=" |
- | There are a few TLA⁺-specific modifications, | + | |
- | + | case PRIME: | |
- | <code java [highlight_lines_extra=" | + | |
- | package tla; | + | case ENABLED: |
- | + | ||
- | class AstPrinter implements Expr.Visitor< | + | |
- | String print(Expr expr) { | + | |
- | return | + | |
- | } | + | |
- | } | + | |
</ | </ | ||
- | We also have some modifications and additions to the '' | + | ==== Evaluating Binary Operators ==== |
- | <code java [highlight_lines_extra=" | + | Unlike Lox, addition in TLA⁺ is only defined between two numbers |
- | @Override | + | Here's how we define our basic binary arithmetic & comparison operators; add a '' |
- | public String visitBinaryExpr(Expr.Binary expr) { | + | |
- | | + | |
- | expr.left, expr.right); | + | |
- | } | + | |
+ | <code java [highlight_lines_extra=" | ||
@Override | @Override | ||
- | public | + | public |
- | | + | |
- | } | + | |
- | @Override | + | switch |
- | public String visitLiteralExpr(Expr.Literal | + | case MINUS: |
- | | + | return |
- | return | + | case PLUS: |
- | } | + | |
+ | case LESS_THAN: | ||
+ | | ||
+ | case EQUAL: | ||
+ | return left.equals(right); | ||
+ | } | ||
- | @Override | + | // Unreachable. |
- | public String visitUnaryExpr(Expr.Unary expr) { | + | return |
- | return | + | |
- | } | + | |
- | + | ||
- | @Override | + | |
- | public string visitTernaryExpr(Expr.Ternary expr) { | + | |
- | return parenthesize(expr.operator.lexeme, | + | |
- | expr.second, | + | |
- | } | + | |
- | + | ||
- | @Override | + | |
- | public string visitVariadicExpr(Expr.Variadic expr) { | + | |
- | return parenthesize(expr.operator.lexeme, | + | |
- | expr.parameters.toArray(Expr[]:: | + | |
} | } | ||
</ | </ | ||
- | The '' | + | Note that since we don't have to worry about '' |
+ | However, this actually gives us different equality semantics from TLC. | ||
+ | In TLC, evaluating things like '' | ||
+ | In the interest of simplicity we are fine with keeping these looser semantics. | ||
+ | See the challenges at the end of this tutorial page if you're interested in more closely matching the semantics of TLC. | ||
- | <code java> | + | Let's take our first foray into sets by defining the set membership operator in '' |
- | private String parenthesize(String name, Expr... exprs) { | + | |
- | StringBuilder builder = new StringBuilder(); | + | |
- | builder.append("(").append(name); | + | <code java [highlight_lines_extra="2,3"]> |
- | | + | |
- | | + | |
- | | + | |
- | } | + | case MINUS: |
- | builder.append(" | + | |
- | + | ||
- | return builder.toString(); | + | |
- | } | + | |
</ | </ | ||
- | It isn' | + | The question mark is some unusual Java syntax you probably haven' |
+ | It has to do with // | ||
+ | Think of it as casting the right operand to //some kind// of set, so we can access the '' | ||
+ | It is tempting to cast it to '' | ||
- | ====== Chapter 6: Parsing Expressions ====== | + | Similar to equality, we get looser semantics here than with TLC. |
+ | TLC will emit a runtime error when evaluating the expression '' | ||
+ | Again this is acceptable. | ||
- | In [[https:// | + | Now for something more complicated. |
+ | Here's the set construction helper operator '' | ||
- | ===== Section | + | <code java [highlight_lines_extra=" |
+ | switch (expr.operator.type) { | ||
+ | case DOT_DOT: | ||
+ | Set< | ||
+ | int lower = (int)left; | ||
+ | int higher | ||
+ | if (lower <= higher) { | ||
+ | for (int i = lower; i <= higher; i++) { | ||
+ | set.add(i); | ||
+ | } | ||
+ | } | ||
+ | return set; | ||
+ | case IN: | ||
+ | </ | ||
- | First, as in [[https:// | + | So expressions like '' |
- | The way that precedence works in TLA⁺ is different from Lox, and indeed different from most other languages! | + | We use '' |
- | One side-quote from this section of the book reads: | + | It's incredible how much we get for free here; Java sets even implement value-based de-duplication |
- | >While not common these days, some languages specify that certain pairs of operators | + | The only binary |
+ | We actually want '' | ||
+ | Add the highlighted lines near the top of the '' | ||
- | > | + | <code java [highlight_lines_extra=" |
+ | public Object visitBinaryExpr(Expr.Binary expr) { | ||
+ | Object left = evaluate(expr.left); | ||
+ | switch (expr.operator.type) { | ||
+ | case AND: | ||
+ | if (!(boolean)left) return false; | ||
+ | Object right = evaluate(expr.right); | ||
+ | return (boolean)right; | ||
+ | default: | ||
+ | break; | ||
+ | } | ||
- | TLA⁺ has both of these features! | ||
- | Instead of operators occupying a slot in some hierarchy of precedence, each operator has a precedence //range//. | ||
- | When the precedence ranges of two operators overlap it is a parse error. | ||
- | For example, the '' | ||
- | < | ||
- | ENABLED x' | ||
</ | </ | ||
- | Users must add parentheses to indicate their desired grouping in the expression. | ||
- | Similarly, some operators like '' | ||
- | Both of these factors combine to make our operator parsing code quite a bit different from that given in the book. | ||
- | Worry not, it can still be made terse and understandable! | ||
- | ===== Section 6.2: Recursive Descent Parsing ===== | + | In an odd contrast, our '' |
+ | We add it in with the rest of the operators in '' | ||
- | [[https:// | + | <code java [highlight_lines_extra=" |
- | Recursive descent can seem a bit magical even if you're used to reasoning about recursive functions! | + | Object right = evaluate(expr.right); |
- | Unfortunately TLA⁺ requires us to push this magic even further. | + | switch (expr.operator.type) { |
- | We'll take it step by step. | + | case OR: |
+ | | ||
+ | case DOT_DOT: | ||
+ | </ | ||
- | We start with the same basic '' | + | Why are these different? |
- | We also add an import for '' | + | It has to do with how they are used in TLA⁺ formulas. |
+ | Actions are usually defined | ||
+ | For example, consider a variable | ||
+ | People often write expressions like '' | ||
+ | It would be a runtime error to evaluate | ||
+ | It is thus useful to use conjunction as a guard stopping expression interpretation if the first operand is not true. | ||
+ | In contrast, disjunction is used in TLA⁺ to express nondeterminism and so both branches | ||
+ | You can read [[https:// | ||
- | <code java [highlight_lines_extra=" | + | ==== Evaluating Other Operators ==== |
- | package tla; | + | |
- | import java.util.List; | + | Our '' |
- | import java.util.ArrayList; | + | Add this '' |
- | import static tla.TokenType.*; | + | <code java> |
- | + | | |
- | class Parser { | + | |
- | private final List<Token> tokens; | + | |
- | | + | case IF: |
- | + | Object conditional | |
- | | + | return (boolean)conditional ? |
- | | + | evaluate(expr.second) : evaluate(expr.third); |
+ | default: | ||
+ | // Unreachable. | ||
+ | return null; | ||
+ | } | ||
} | } | ||
- | } | ||
</ | </ | ||
- | Now we hit our first major difference. | + | '' |
- | In Lox, precedence is given by a small hierarchy of named rules like '' | + | Note our definition |
- | TLA⁺ is more complicated than that. | + | |
- | The full language | + | Finally, here's how we define the set construction operator; add this '' |
- | If we wanted to match the book' | + | |
- | <code java> | + | |
- | private Expr operatorExpressionPrec1() { ... } | + | |
- | private Expr operatorExpressionPrec2() { ... } | + | |
- | private Expr operatorExpressionPrec3() { ... } | + | |
- | ... | + | |
- | private Expr operatorExpressionPrec15() { ... } | + | |
- | </ | + | |
- | where each '' | + | |
- | Life is too short for this. | + | |
- | Instead, we'll adopt a technique alluded to in the text: | + | |
- | >If you wanted to do some clever Java 8, you could create a helper method for parsing a left-associative series of binary operators given a list of token types, and an operand method handle to simplify this redundant code. | + | |
- | Here's the skeleton of our operator parsing function; the trick is to make the precedence a parameter to the function instead of a component of the name. | ||
- | Add this code after the '' | ||
<code java> | <code java> | ||
- | | + | |
- | | + | public Object visitVariadicExpr(Expr.Variadic expr) { |
- | } | + | |
- | + | case LEFT_BRACE: | |
- | | + | |
- | | + | for (Expr parameter : expr.parameters) { |
- | + | | |
- | Expr expr = operatorExpression(prec + 1); | + | } |
- | + | | |
- | return | + | |
+ | // Unreachable. | ||
+ | return | ||
+ | } | ||
} | } | ||
</ | </ | ||
- | Before filling out '' | + | ====== Section 7.3: Runtime Errors ====== |
- | <code java> | + | In [[https:// |
- | private boolean match(TokenType... types) { | + | |
- | for (TokenType type : types) { | + | |
- | if (check(type)) { | + | |
- | advance(); | + | |
- | return true; | + | |
- | } | + | |
- | } | + | |
- | return false; | + | Here's our variant of the '' |
- | } | + | |
- | | + | <code java [highlight_lines_extra=" |
- | if (isAtEnd()) return | + | |
- | | + | if (operand instanceof Integer) return; |
+ | | ||
} | } | ||
- | private Token advance() { | + | private |
- | if (!isAtEnd()) current++; | + | |
- | | + | if (left instanceof Integer && right instanceof Integer) return; |
- | } | + | |
- | + | ||
- | private boolean isAtEnd() { | + | |
- | return peek().type == EOF; | + | |
- | } | + | |
- | + | ||
- | private Token peek() { | + | |
- | return tokens.get(current); | + | |
- | } | + | |
- | private Token previous() { | + | throw new RuntimeError(operator, " |
- | return tokens.get(current - 1); | + | |
} | } | ||
</ | </ | ||
- | Now we have to define a table of operators with their details. | + | Create |
- | For this, create | + | Contents are identical to that give in the book except for the package name: |
- | <code java> | + | <code java [highlight_lines_extra=" |
package tla; | package tla; | ||
- | enum Fix { | + | class RuntimeError extends RuntimeException |
- | PREFIX, INFIX, POSTFIX | + | final Token token; |
- | } | + | |
- | + | ||
- | class Operator | + | |
- | final Fix fix; | + | |
- | final TokenType | + | |
- | final boolean assoc; | + | |
- | final int lowPrec; | + | |
- | final int highPrec; | + | |
- | | + | |
- | int lowPrec, int highPrec) { | + | |
- | | + | |
this.token = token; | this.token = token; | ||
- | this.assoc = assoc; | ||
- | this.lowPrec = lowPrec; | ||
- | this.highPrec = highPrec; | ||
} | } | ||
} | } | ||
</ | </ | ||
- | For convenience, | + | We also need some helpers for boolean |
- | + | ||
- | <code java [highlight_lines_extra=" | + | |
- | package tla; | + | |
- | + | ||
- | import java.util.List; | + | |
- | import java.util.ArrayList; | + | |
- | + | ||
- | import static tla.TokenType.*; | + | |
- | import static tla.Fix.*; | + | |
- | + | ||
- | class Parser { | + | |
- | </ | + | |
- | + | ||
- | + | ||
- | You can find operator | + | |
- | We use a small subset of these operators. | + | |
- | Record their attributes in a table in '' | + | |
<code java> | <code java> | ||
- | private | + | private |
- | new Operator(PREFIX, | + | |
- | | + | |
- | new Operator(PREFIX, | + | } |
- | new Operator(INFIX, | + | |
- | new Operator(INFIX, | + | |
- | new Operator(INFIX, | + | |
- | new Operator(INFIX, | + | |
- | new Operator(INFIX, | + | |
- | new Operator(INFIX, | + | |
- | new Operator(INFIX, | + | |
- | new Operator(INFIX, | + | |
- | new Operator(POSTFIX, | + | |
- | }; | + | |
- | </ | + | |
- | Here's something a bit odd. | + | private void checkBooleanOperands(Token operator, |
- | In TLA⁺, the infix minus operator | + | if (left instanceof Boolean |
- | In grade school you probably learned acronyms like PEMDAS or BEDMAS to remember the order of operations in arithmetic. | + | throw new RuntimeError(operator, " |
- | Really, you learned parsing rules! | + | |
- | Now when writing our own parsing algorithm we come to understand that the order of these operations is not inscribed in the bedrock of mathematical truth but instead is a simple convention of mathematical notation. | + | |
- | TLA⁺ subverts this by parsing the expression '' | + | |
- | While this design decision is unusual, it is [[https:// | + | |
- | + | ||
- | We need one more helper method before we can start working on '' | + | |
- | Add this code above '' | + | |
- | <code java> | + | |
- | private Operator matchOp(Fix fix, int prec) { | + | |
- | | + | |
- | | + | |
- | | + | |
- | } | + | |
- | } | + | |
- | + | ||
- | return null; | + | |
} | } | ||
</ | </ | ||
- | Okay, we're all set for the main event! | + | Finally, we need a helper |
- | Here is how we modify '' | + | |
- | You can see a strong resemblance to the infix operator parsing code given in the book (new lines highlighted): | + | |
- | <code java [highlight_lines_extra=" | + | |
- | private Expr operatorExpression(int prec) { | + | |
- | if (prec == 16) return primary(); | + | |
- | Operator op; | + | <code java> |
- | + | | |
- | Expr expr = operatorExpression(prec + 1); | + | |
- | while ((op = matchOp(INFIX, prec)) != null) { | + | |
- | Token operator = previous(); | + | |
- | Expr right = operatorExpression(op.highPrec + 1); | + | |
- | expr = new Expr.Binary(expr, operator, | + | |
- | } | + | |
- | + | ||
- | return expr; | + | |
} | } | ||
</ | </ | ||
- | We use Java's combined conditional-assignment atop the '' | + | Now add these checks |
- | The interior of the '' | + | Here' |
- | It takes a bit of thinking to understand why this works for parsing expressions according to the precedence rules we want, but it does. | + | <code java [highlight_lines_extra=" |
- | Take a minute to ponder it. | + | |
- | If you still don't get it, wait until we have a fully-functional expression parser then play around with this line to see how it changes the behavior. | + | |
- | + | | |
- | Our code implements precedence ranges, but assumes all infix operators are associative. | + | |
- | We need to modify the loop to return immediately if the infix operator is not associative: | + | |
- | <code java [highlight_lines_extra=" | + | |
- | while ((op = matchOp(INFIX, | + | |
- | | + | |
- | Expr right = operatorExpression(op.highPrec + 1); | + | |
- | | + | |
- | | + | |
- | } | + | |
</ | </ | ||
- | + | Logical not: | |
- | And that's how we parse infix operators! | + | <code java [highlight_lines_extra=" |
- | That was the most complicated case, so let's move on to prefix operators. | + | case NOT: |
- | Again our code resembles the prefix operator parsing logic given in the book. | + | |
- | Add this snippet near the top of '' | + | return |
- | + | ||
- | <code java [highlight_lines_extra=" | + | |
- | | + | |
- | | + | |
- | + | ||
- | Operator op; | + | |
- | if ((op = matchOp(PREFIX, | + | |
- | Token opToken = previous(); | + | |
- | Expr expr = operatorExpression( | + | |
- | op.assoc ? op.lowPrec : op.highPrec + 1); | + | |
- | return | + | |
- | } | + | |
- | + | ||
- | Expr expr = operatorExpression(prec + 1); | + | |
</ | </ | ||
- | + | Enabled: | |
- | Of note is the expression '' | + | <code java [highlight_lines_extra=" |
- | To understand this expression, it is helpful to consider an example. | + | case ENABLED: |
- | The negative prefix operator '' | + | |
- | In order to do that after consuming the first '' | + | |
- | Then we will consume the second '' | + | |
- | In contrast, the prefix operator '' | + | |
- | In that case we want to reject the expression '' | + | |
- | Thus the second '' | + | |
- | + | ||
- | All that remains is to parse postfix operators. | + | |
- | These are not covered in the book, but they pretty much resemble infix operators without matching an expression on the right-hand side of the operator. | + | |
- | Add the highlighted code below the '' | + | |
- | + | ||
- | <code java [highlight_lines_extra=" | + | |
- | } | + | |
- | + | ||
- | | + | |
- | Token opToken = previous(); | + | |
- | | + | |
- | | + | |
- | } | + | |
- | + | ||
- | return expr | + | |
- | } | + | |
</ | </ | ||
- | + | Subtraction: | |
- | And that completes our operator parsing logic! | + | <code java [highlight_lines_extra=" |
- | All that remains is our '' | + | case MINUS: |
- | It is fairly similar to that given in the book, with some omissions since our minimal TLA⁺ subset does not contain strings or null values. | + | |
- | Add this code after '' | + | return (int)left - (int)right; |
- | + | ||
- | <code java> | + | |
- | | + | |
- | | + | |
- | if (match(TRUE)) | + | |
- | + | ||
- | if (match(NUMBER)) { | + | |
- | return new Expr.Literal(previous().literal); | + | |
- | } | + | |
- | + | ||
- | if (match(LEFT_PAREN)) { | + | |
- | Expr expr = expression(); | + | |
- | consume(RIGHT_PAREN, | + | |
- | return new Expr.Grouping(expr); | + | |
- | } | + | |
- | } | + | |
</ | </ | ||
- | + | Addition: | |
- | We have two final additions to '' | + | <code java [highlight_lines_extra=" |
- | Here's how we parse '' | + | case PLUS: |
- | + | checkNumberOperands(expr.operator, left, right); | |
- | <code java [highlight_lines_extra=" | + | return (int)left + (int)right; |
- | return | + | </code> |
- | } | + | Less than: |
- | + | <code java [highlight_lines_extra=" | |
- | | + | case LESS_THAN: |
- | | + | checkNumberOperands(expr.operator, left, right); |
- | Expr condition | + | |
- | | + | </code> |
- | Expr yes = expression(); | + | The '' |
- | | + | <code java [highlight_lines_extra=" |
- | | + | case DOT_DOT: |
- | | + | checkNumberOperands(expr.operator, left, right); |
- | } | + | Set< |
- | } | + | </ |
+ | Set membership: | ||
+ | <code java [highlight_lines_extra=" | ||
+ | | ||
+ | checkSetOperand(expr.operator, | ||
+ | | ||
+ | </ | ||
+ | Disjunction: | ||
+ | <code java [highlight_lines_extra=" | ||
+ | case OR: | ||
+ | checkBooleanOperands(expr.operator, | ||
+ | return | ||
+ | </ | ||
+ | Conjunction: | ||
+ | <code java [highlight_lines_extra=" | ||
+ | | ||
+ | checkBooleanOperand(expr.operator, left); | ||
+ | if (!(boolean)left) return false; | ||
+ | | ||
+ | | ||
+ | | ||
+ | </ | ||
+ | Finally, '' | ||
+ | <code java [highlight_lines_extra="3" | ||
+ | | ||
+ | Object conditional | ||
+ | | ||
+ | | ||
+ | | ||
</ | </ | ||
- | And here's how we parse the set construction operator. | + | ====== Section 7.4: Hooking Up the Interpreter ====== |
- | Again add the highlighted code to the bottom of '' | + | |
- | <code java [highlight_lines_extra=" | + | We're very close! |
- | | + | In [[https:// |
- | | + | First, add this public '' |
- | + | <code java [highlight_lines_extra=" | |
- | if (match(LEFT_BRACE)) | + | void interpret(Expr expression) { |
- | | + | |
- | | + | |
- | if (RIGHT_BRACE != peek().type) { | + | |
- | do { | + | } catch (RuntimeError error) { |
- | elements.add(expression()); | + | |
- | } while (match(COMMA)); | + | |
- | | + | |
- | consume(RIGHT_BRACE, | + | |
- | return new Expr.Variadic(operator, elements); | + | |
} | } | ||
} | } | ||
</ | </ | ||
- | This will handle expressions like '' | + | In contrast to the book, our '' |
- | + | ||
- | The '' | + | |
- | + | ||
- | ===== Section 6.3: Syntax Errors ===== | + | |
- | + | ||
- | We don't need to modify most of the error reporting code given in [[https:// | + | |
- | Here it is; add the '' | + | |
<code java> | <code java> | ||
- | private | + | private |
- | | + | return |
- | + | ||
- | throw error(peek(), | + | |
} | } | ||
</ | </ | ||
- | Then add the '' | + | Add a '' |
<code java> | <code java> | ||
- | | + | static void runtimeError(RuntimeError |
- | Lox.error(token, | + | |
- | return new ParseError(); | + | " |
- | } | + | |
- | </ | + | |
- | + | ||
- | In the '' | + | |
- | + | ||
- | <code java> | + | |
- | | + | |
- | | + | |
- | report(token.line, " at end", message); | + | |
- | } else { | + | |
- | report(token.line, " at '" + token.lexeme | + | |
- | | + | |
} | } | ||
</ | </ | ||
- | Add the '' | + | Then add a static |
<code java [highlight_lines_extra=" | <code java [highlight_lines_extra=" | ||
- | class Parser { | + | static boolean hadError = false; |
- | | + | static |
- | | + | |
</ | </ | ||
- | One piece of code we //do// need to modify is the '' | + | And exit from the '' |
- | TLA⁺ doesn' | + | |
- | <code java> | + | <code java [highlight_lines_extra=" |
- | private void synchronize() { | + | |
- | | + | |
- | + | ||
- | while(!isAtEnd()) { | + | |
- | if (previous().type == EQUAL_EQUAL) return; | + | |
- | advance(); | + | // Indicate an error in the exit code. |
- | | + | if (hadError) System.exit(65); |
+ | | ||
} | } | ||
</ | </ | ||
- | Fully-featured TLA⁺ parsers generally look ahead to identify the start of a new operator definition (not trivial!) and insert a synthetic zero-width token for the parser to consume. | + | Finally, create |
- | For an example, see SANY's very complicated | + | |
- | We won't be doing that here, but it's a good technique to know about; looking ahead then inserting synthetic tokens to disambiguate syntax is a common method when parsing complicated & ambiguous languages like TLA⁺. | + | |
- | ===== Section 6.4: Wiring up the Parser ===== | + | <code java [highlight_lines_extra=" |
+ | public class TlaPlus { | ||
+ | private static final Interpreter interpreter | ||
+ | static boolean hadError | ||
+ | </ | ||
- | In [[https:// | + | Then finish it off by actually interpreting |
- | In the '' | + | |
- | + | ||
- | <code java [highlight_lines_extra=" | + | |
- | List< | + | |
- | + | ||
- | Parser parser = new Parser(tokens); | + | |
- | Expr expression = parser.parse(); | + | |
+ | <code java [highlight_lines_extra=" | ||
// Stop if there was a syntax error. | // Stop if there was a syntax error. | ||
if (hadError) return; | if (hadError) return; | ||
- | | + | |
} | } | ||
</ | </ | ||
- | Fire up the interpreter and parse a TLA⁺ expression! | + | Voila! |
+ | Your program will now interpret any constant | ||
+ | Try it out: | ||
< | < | ||
- | > {1 + 2, IF TRUE THEN 3 ELSE 4, {}} | + | > {0 .. 2, IF TRUE THEN 1 ELSE 2, {}} |
- | ({ (+ 1 2) (IF true 3 4) ({)) | + | [[], 1, [0, 1, 2]] |
</ | </ | ||
- | If you got out of sync, you can find a snapshot of the expected state of the code in [[https:// | + | |
- | Next tutorial: [[https:// | + | If you got out of sync, you can find a snapshot of the expected state of the code in [[https:// |
+ | Next tutorial: [[https:// | ||
====== Challenges ====== | ====== Challenges ====== | ||
Here are some optional challenges to flesh out your TLA⁺ interpreter, | Here are some optional challenges to flesh out your TLA⁺ interpreter, | ||
+ | You should save a copy of your code before attempting these. | ||
+ | - TLC evaluates cross-type equality comparison as a runtime error. For example, '' | ||
+ | - TLC requires set elements to all be of the same type. Trying to construct the set '' | ||
- | [[https:// | + | [[https:// |