creating:expressions

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revision Previous revision
Next revision		 Previous revision
creating:expressions [2025/04/11 20:24] – Completed chapter 6 tutorial ahelwercreating:expressions [2025/05/13 15:58] (current) – Fixed lookahead in set literal parsing ahelwer
Line 1: Line 1:
-======= Handling Constant TLA⁺ Expressions =======+======= Parsing Constant TLA⁺ Expressions =======
  
-This tutorial page covers the next three chapters in //Crafting Interpreters//:+This tutorial page covers the next two chapters in //Crafting Interpreters//:
   - [[https://craftinginterpreters.com/representing-code.html|Chapter 5: Representing Code]]   - [[https://craftinginterpreters.com/representing-code.html|Chapter 5: Representing Code]]
   - [[https://craftinginterpreters.com/parsing-expressions.html|Chapter 6: Parsing Expressions]]   - [[https://craftinginterpreters.com/parsing-expressions.html|Chapter 6: Parsing Expressions]]
-  - [[https://craftinginterpreters.com/evaluating-expressions.html|Chapter 7: Evaluating Expressions]] 
  
 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! 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!
Line 38: Line 37:
 ternary        → "IF" expression "THEN" expression "ELSE" expression; ternary        → "IF" expression "THEN" expression "ELSE" expression;
 variadic       → "{" ( expression ( "," expression )* )? "}" variadic       → "{" ( expression ( "," expression )* )? "}"
-operator       → "=" | "+" | "-" | ".." | "/\" | "\/" | "<"  | "\in" ;+operator       → "=" | "+" | "-" | ".." | "<"  | "\in" ;
 </code> </code>
 There are a few interesting differences. There are a few interesting differences.
Line 51: Line 50:
 The only difference between ''{1, 2, 3}'' and an operator like ''constructSet(1, 2, 3)'' is syntactic sugar. The only difference between ''{1, 2, 3}'' and an operator like ''constructSet(1, 2, 3)'' is syntactic sugar.
 This is the perspective of a language implementer. This is the perspective of a language implementer.
-Later on we will extend the definition of ''variadic'' to include vertically-aligned conjunction & disjunction lists.+ 
 +Note that we //could// also include the conjunction ''/\'' and disjunction ''\/'' infix operators here but they have odd parsing interactions with vertically-aligned conjunction & disjunction lists, so we will handle them in a later chapter dedicated to that topic.
  
 ===== Section 5.2: Implementing Syntax Trees ===== ===== Section 5.2: Implementing Syntax Trees =====
Line 59: Line 59:
  
 <code java [highlight_lines_extra="19,20,21"]> <code java [highlight_lines_extra="19,20,21"]>
-package com.craftinginterpreters.tool;+package tool;
  
 import java.io.IOException; import java.io.IOException;
Line 94: Line 94:
     PrintWriter writer = new PrintWriter(path, "UTF-8");     PrintWriter writer = new PrintWriter(path, "UTF-8");
  
-    writer.println("package com.craftinginterpreters.tla;");+    writer.println("package tla;");
     writer.println();     writer.println();
     writer.println("import java.util.List;");     writer.println("import java.util.List;");
Line 207: Line 207:
  
 <code java [highlight_lines_extra="1"]> <code java [highlight_lines_extra="1"]>
-package com.craftinginterpreters.tla;+package tla;
  
 class AstPrinter implements Expr.Visitor<String> { class AstPrinter implements Expr.Visitor<String> {
Line 277: Line 277:
 In [[https://craftinginterpreters.com/parsing-expressions.html|Chapter 6]], we finally build a parse tree out of our tokens! In [[https://craftinginterpreters.com/parsing-expressions.html|Chapter 6]], we finally build a parse tree out of our tokens!
  
-===== Chapter 6.1: Ambiguity and the Parsing Game =====+===== Section 6.1: Ambiguity and the Parsing Game =====
  
 First, as in [[https://craftinginterpreters.com/parsing-expressions.html#ambiguity-and-the-parsing-game|section 6.1 of the book]], we have to disambiguate our grammar. First, as in [[https://craftinginterpreters.com/parsing-expressions.html#ambiguity-and-the-parsing-game|section 6.1 of the book]], we have to disambiguate our grammar.
Line 299: Line 299:
 Worry not, it can still be made terse and understandable! Worry not, it can still be made terse and understandable!
  
-===== Chapter 6.2: Recursive Descent Parsing =====+===== Section 6.2: Recursive Descent Parsing =====
  
 [[https://craftinginterpreters.com/parsing-expressions.html#recursive-descent-parsing|Section 6.2]] is where we start writing our parser in the recursive descent style. [[https://craftinginterpreters.com/parsing-expressions.html#recursive-descent-parsing|Section 6.2]] is where we start writing our parser in the recursive descent style.
Line 310: Line 310:
  
 <code java [highlight_lines_extra="1,4,6"]> <code java [highlight_lines_extra="1,4,6"]>
-package com.craftinginterpreters.tla;+package tla;
  
 import java.util.List; import java.util.List;
 import java.util.ArrayList; import java.util.ArrayList;
  
-import static com.craftinginterpreters.tla.TokenType.*;+import static tla.TokenType.*;
  
 class Parser { class Parser {
Line 398: Line 398:
  
 Now we have to define a table of operators with their details. Now we have to define a table of operators with their details.
-For this, create a new file ''Operator.java'' containing a class recording operator fix type, token type, associativity, and precedence range:+First use the handy Java 17 [[https://openjdk.org/jeps/395|records]] feature to quickly define a new ''Operator'' dataclass; this will hold the attributes of the operators we want to parse. 
 +Put it at the top of the ''Parser'' class:
  
-<code java> +<code java [highlight_lines_extra="2,3,4"]> 
-package com.craftinginterpreters.tla;+class Parser { 
 +  private static enum Fix { PREFIX, INFIX, POSTFIX } 
 +  private static record Operator(Fix fix, TokenType token, 
 +      boolean assoc, int lowPrec, int highPrec) {}
  
-enum Fix { +  private final List<Token> tokens;
-  PREFIX, INFIX, POSTFIX +
-} +
- +
-class Operator { +
-  final Fix fix; +
-  final TokenType token; +
-  final boolean assoc; +
-  final int lowPrec; +
-  final int highPrec; +
- +
-  public Operator(Fix fix, TokenType token, boolean assoc, +
-                  int lowPrec, int highPrec) { +
-    this.fix = fix; +
-    this.token = token; +
-    this.assoc = assoc; +
-    this.lowPrec = lowPrec; +
-    this.highPrec = highPrec; +
-  } +
-}+
 </code> </code>
- 
-For convenience, import the ''Fix'' enum values in ''Parser.java'' so they can be referenced directly: 
- 
-<code java [highlight_lines_extra="7"]> 
-package com.craftinginterpreters.tla; 
- 
-import java.util.List; 
-import java.util.ArrayList; 
- 
-import static com.craftinginterpreters.tla.TokenType.*; 
-import static com.craftinginterpreters.tla.Fix.*; 
- 
-class Parser { 
-</code> 
- 
  
 You can find operator attributes on page 271 of //[[https://lamport.azurewebsites.net/tla/book.html|Specifying Systems]]// by Leslie Lamport, or [[https://github.com/tlaplus/tlaplus/blob/13e5a39b5368a6da4906b8ed1c2c1114d2e7de15/tlatools/org.lamport.tlatools/src/tla2sany/parser/Operators.java#L130-L234|this TLA⁺ tools source file]]. You can find operator attributes on page 271 of //[[https://lamport.azurewebsites.net/tla/book.html|Specifying Systems]]// by Leslie Lamport, or [[https://github.com/tlaplus/tlaplus/blob/13e5a39b5368a6da4906b8ed1c2c1114d2e7de15/tlatools/org.lamport.tlatools/src/tla2sany/parser/Operators.java#L130-L234|this TLA⁺ tools source file]].
Line 446: Line 416:
 <code java> <code java>
   private static final Operator[] operators = new Operator[] {   private static final Operator[] operators = new Operator[] {
-    new Operator(PREFIX,  NEGATION,   true,   4,  4 ), +    new Operator(Fix.PREFIX,  NOT,        true,   4,  4 ), 
-    new Operator(PREFIX,  ENABLED,    false,  4,  15), +    new Operator(Fix.PREFIX,  ENABLED,    false,  4,  15), 
-    new Operator(PREFIX,  MINUS,      true,   12, 12), +    new Operator(Fix.PREFIX,  MINUS,      true,   12, 12), 
-    new Operator(INFIX,   AND,        true,   3,  3 ), +    new Operator(Fix.INFIX,   IN,         false,  5,  5 ), 
-    new Operator(INFIX,   OR,         true,   3,  3 ), +    new Operator(Fix.INFIX,   EQUAL,      false,  5,  5 ), 
-    new Operator(INFIX,   IN,         false,  5,  5 ), +    new Operator(Fix.INFIX,   LESS_THAN,  false,  5,  5 ), 
-    new Operator(INFIX,   EQUAL,      false,  5,  5 ), +    new Operator(Fix.INFIX,   DOT_DOT,    false,  9,  9 ), 
-    new Operator(INFIX,   LESS_THAN,  false,  5,  5 ), +    new Operator(Fix.INFIX,   PLUS,       true,   10, 10), 
-    new Operator(INFIX,   DOT_DOT,    false,  9,  9 ), +    new Operator(Fix.INFIX,   MINUS,      true,   11, 11), 
-    new Operator(INFIX,   PLUS,       true,   10, 10), +    new Operator(Fix.POSTFIX, PRIME,      false,  15, 15),
-    new Operator(INFIX,   MINUS,      true,   11, 11), +
-    new Operator(POSTFIX, PRIME,      false,  15, 15),+
   };   };
 </code> </code>
Line 491: Line 459:
  
     Operator op;     Operator op;
- +
     Expr expr = operatorExpression(prec + 1);     Expr expr = operatorExpression(prec + 1);
-    while ((op = matchOp(INFIX, prec)) != null) {+    while ((op = matchOp(Fix.INFIX, prec)) != null) {
       Token operator = previous();       Token operator = previous();
       Expr right = operatorExpression(op.highPrec + 1);       Expr right = operatorExpression(op.highPrec + 1);
       expr = new Expr.Binary(expr, operator, right);       expr = new Expr.Binary(expr, operator, right);
     }     }
- +
     return expr;     return expr;
   }   }
Line 512: Line 480:
 We need to modify the loop to return immediately if the infix operator is not associative: We need to modify the loop to return immediately if the infix operator is not associative:
 <code java [highlight_lines_extra="5"]> <code java [highlight_lines_extra="5"]>
-    while ((op = matchOp(INFIX, prec)) != null) {+    while ((op = matchOp(Fix.INFIX, prec)) != null) {
       Token operator = previous();       Token operator = previous();
       Expr right = operatorExpression(op.highPrec + 1);       Expr right = operatorExpression(op.highPrec + 1);
Line 530: Line 498:
  
     Operator op;     Operator op;
-    if ((op = matchOp(PREFIX, prec)) != null) {+    if ((op = matchOp(Fix.PREFIX, prec)) != null) {
       Token opToken = previous();       Token opToken = previous();
       Expr expr = operatorExpression(       Expr expr = operatorExpression(
Line 556: Line 524:
     }     }
  
-    while ((op = matchOp(POSTFIX, prec)) != null) {+    while ((op = matchOp(Fix.POSTFIX, prec)) != null) {
       Token opToken = previous();       Token opToken = previous();
       expr = new Expr.Unary(opToken, expr);       expr = new Expr.Unary(opToken, expr);
Line 616: Line 584:
     if (match(LEFT_BRACE)) {     if (match(LEFT_BRACE)) {
       Token operator = previous();       Token operator = previous();
-      List<Expr> elements = new ArrayList<Expr>(); +      List<Expr> elements = new ArrayList<>(); 
-      if (RIGHT_BRACE != peek().type) {+      if (!check(RIGHT_BRACE)) {
         do {         do {
           elements.add(expression());           elements.add(expression());
Line 668: Line 636:
 Add the ''ParseError'' class definition at the top of the ''Parser'' class: Add the ''ParseError'' class definition at the top of the ''Parser'' class:
  
-<code java [highlight_lines_extra="2"]>+<code java [highlight_lines_extra="5"]>
 class Parser { class Parser {
 +  private static enum Fix { PREFIX, INFIX, POSTFIX }
 +  private static record Operator(Fix fix, TokenType token,
 +      boolean assoc, int lowPrec, int highPrec) {}
   private static class ParseError extends RuntimeException {}   private static class ParseError extends RuntimeException {}
  
Line 681: Line 652:
   private void synchronize() {   private void synchronize() {
     advance();     advance();
-    +
     while(!isAtEnd()) {     while(!isAtEnd()) {
       if (previous().type == EQUAL_EQUAL) return;       if (previous().type == EQUAL_EQUAL) return;
-      +
       advance();       advance();
     }     }
Line 717: Line 688:
 ({ (+ 1 2) (IF true 3 4) ({)) ({ (+ 1 2) (IF true 3 4) ({))
 </code> </code>
 +If you got out of sync, you can find a snapshot of the expected state of the code in [[https://github.com/tlaplus/devkit/tree/main/3-expressions|this repo directory]].
 +Next tutorial: [[creating:evaluation|Evaluating Constant TLA⁺ Expressions]]!
 +
 +====== Challenges ======
 +
 +Here are some optional challenges to flesh out your TLA⁺ interpreter, roughly ranked from simplest to most difficult.
 +
 +[[creating:scanning|< Previous Page]] | [[creating:start#table_of_contents|Table of Contents]] | [[creating:evaluation|Next Page >]]
  
  • creating/expressions.1744403081.txt.gz
  • Last modified: 2025/04/11 20:24
  • by ahelwer