Appearance
| 1 | namespace Syntax.Parsers.Expressions is | |
| 2 | use System.Exception; | |
| 3 | ||
| 4 | use IO.Std; | |
| 5 | ||
| 6 | use Logging; | |
| 7 | use Source; | |
| 8 | ||
| 9 | enum PRECEDENCE is | |
| 10 | NONE = 0, | |
| 11 | MIN = 10, | |
| 12 | YIELD = 20, // reserved for `||` generator yield infix | |
| 13 | UNDEFINED = 30, | |
| 14 | USER_1 = 40, | |
| 15 | BOOLEAN = 50, | |
| 16 | USER_2 = 60, | |
| 17 | RELATIONAL = 70, | |
| 18 | USER_3 = 80, | |
| 19 | RANGE = 90, | |
| 20 | USER_4 = 100, | |
| 21 | SHIFT = 110, | |
| 22 | USER_5 = 120, | |
| 23 | BITWISE = 130, | |
| 24 | USER_6 = 140, | |
| 25 | ADDITION = 150, | |
| 26 | USER_7 = 160, | |
| 27 | MULTIPLICATION = 170, | |
| 28 | USER_8 = 180, | |
| 29 | MEMBER = 190, | |
| 30 | PRIMARY = 200 | |
| 31 | si | |
| 32 | ||
| 33 | enum ASSOCIATIVITY is | |
| 34 | LEFT, | |
| 35 | RIGHT | |
| 36 | si | |
| 37 | ||
| 38 | class EXPRESSION( | |
| 39 | expression_tertiary_parser: Parser[Trees.Expressions.Expression], | |
| 40 | precedence: Collections.MutableMap[string,PRECEDENCE] | |
| 41 | ): Base[Trees.Expressions.Expression] is | |
| 42 | _precedence: Collections.MutableMap[string,PRECEDENCE]; | |
| 43 | _real_operation: Collections.MAP[string,string]; | |
| 44 | ||
| 45 | super(); | |
| 46 | ||
| 47 | init(..) is | |
| 48 | _precedence = precedence; | |
| 49 | ||
| 50 | _precedence["*"] = PRECEDENCE.MULTIPLICATION; | |
| 51 | _precedence["✕"] = PRECEDENCE.MULTIPLICATION; | |
| 52 | _precedence["×"] = PRECEDENCE.MULTIPLICATION; | |
| 53 | _precedence["/"] = PRECEDENCE.MULTIPLICATION; | |
| 54 | _precedence["%"] = PRECEDENCE.MULTIPLICATION; | |
| 55 | _precedence["÷"] = PRECEDENCE.MULTIPLICATION; | |
| 56 | _precedence["+"] = PRECEDENCE.ADDITION; | |
| 57 | _precedence["-"] = PRECEDENCE.ADDITION; | |
| 58 | _precedence["&"] = PRECEDENCE.BITWISE; | |
| 59 | _precedence["|"] = PRECEDENCE.BITWISE; | |
| 60 | _precedence["¦"] = PRECEDENCE.BITWISE; | |
| 61 | _precedence["^"] = PRECEDENCE.BITWISE; | |
| 62 | _precedence["∩"] = PRECEDENCE.BITWISE; | |
| 63 | _precedence["∪"] = PRECEDENCE.BITWISE; | |
| 64 | _precedence[".."] = PRECEDENCE.RANGE; | |
| 65 | _precedence["::"] = PRECEDENCE.RANGE; | |
| 66 | _precedence["<<"] = PRECEDENCE.SHIFT; | |
| 67 | _precedence[">>"] = PRECEDENCE.SHIFT; | |
| 68 | _precedence["≈"] = PRECEDENCE.RELATIONAL; | |
| 69 | _precedence["≡"] = PRECEDENCE.RELATIONAL; | |
| 70 | _precedence["=="] = PRECEDENCE.RELATIONAL; | |
| 71 | _precedence["!="] = PRECEDENCE.RELATIONAL; | |
| 72 | _precedence["=~"] = PRECEDENCE.RELATIONAL; | |
| 73 | _precedence["!~"] = PRECEDENCE.RELATIONAL; | |
| 74 | _precedence["<"] = PRECEDENCE.RELATIONAL; | |
| 75 | _precedence[">"] = PRECEDENCE.RELATIONAL; | |
| 76 | _precedence[">="] = PRECEDENCE.RELATIONAL; | |
| 77 | _precedence["<="] = PRECEDENCE.RELATIONAL; | |
| 78 | _precedence["/\\"] = PRECEDENCE.BOOLEAN; | |
| 79 | _precedence["\\/"] = PRECEDENCE.BOOLEAN; | |
| 80 | _precedence["∧"] = PRECEDENCE.BOOLEAN; | |
| 81 | _precedence["∨"] = PRECEDENCE.BOOLEAN; | |
| 82 | _precedence["||"] = PRECEDENCE.YIELD; | |
| 83 | _precedence["??"] = PRECEDENCE.USER_1; | |
| 84 | ||
| 85 | _real_operation = Collections.MAP[string,string](); | |
| 86 | ||
| 87 | _real_operation["!~"] = "=~"; | |
| 88 | _real_operation["=~"] = "=~"; | |
| 89 | _real_operation["!="] = "=="; | |
| 90 | _real_operation["=="] = "=="; | |
| 91 | _real_operation["<"] = "<>"; | |
| 92 | _real_operation["<="] = "<>"; | |
| 93 | _real_operation[">"] = "<>"; | |
| 94 | _real_operation[">="] = "<>"; | |
| 95 | si | |
| 96 | ||
| 97 | description: string => "expression"; | |
| 98 | ||
| 99 | precedence(context: CONTEXT) -> PRECEDENCE is | |
| 100 | if context.current.token != Lexical.TOKEN.OPERATOR then | |
| 101 | return PRECEDENCE.NONE; | |
| 102 | fi | |
| 103 | ||
| 104 | let op = context.current.value_string; | |
| 105 | ||
| 106 | let known: PRECEDENCE mut = _; | |
| 107 | if _precedence.try_get_value(op, known ref) then | |
| 108 | return known; | |
| 109 | fi | |
| 110 | ||
| 111 | let auto = auto_precedence_for(op); | |
| 112 | _precedence[op] = auto; | |
| 113 | ||
| 114 | return auto; | |
| 115 | si | |
| 116 | ||
| 117 | // First-character-based precedence heuristic for user-defined | |
| 118 | // operators. Modelled on OCaml/F#. Every built-in operator in the | |
| 119 | // _precedence table matches what this would compute, so the table | |
| 120 | // is purely an optimisation and a hook point for explicit overrides | |
| 121 | // via @precedence. | |
| 122 | auto_precedence_for(op: string) -> PRECEDENCE static is | |
| 123 | if op =~ "/\\" \/ op =~ "\\/" then | |
| 124 | return PRECEDENCE.BOOLEAN; | |
| 125 | fi | |
| 126 | if op =~ ".." \/ op =~ "::" then | |
| 127 | return PRECEDENCE.RANGE; | |
| 128 | fi | |
| 129 | ||
| 130 | let first = op.get_chars(0); | |
| 131 | ||
| 132 | if first == '*' \/ first == '/' \/ first == '%' \/ | |
| 133 | first == '×' \/ first == '÷' \/ first == '✕' | |
| 134 | then | |
| 135 | return PRECEDENCE.MULTIPLICATION; | |
| 136 | fi | |
| 137 | if first == '+' \/ first == '-' then | |
| 138 | return PRECEDENCE.ADDITION; | |
| 139 | fi | |
| 140 | if first == '<' \/ first == '>' then | |
| 141 | if op.length >= 2 /\ op.get_chars(1) == first then | |
| 142 | return PRECEDENCE.SHIFT; | |
| 143 | else | |
| 144 | return PRECEDENCE.RELATIONAL; | |
| 145 | fi | |
| 146 | fi | |
| 147 | if first == '=' \/ first == '!' \/ first == '~' \/ | |
| 148 | first == '≈' \/ first == '≡' | |
| 149 | then | |
| 150 | return PRECEDENCE.RELATIONAL; | |
| 151 | fi | |
| 152 | if first == '&' \/ first == '∩' then | |
| 153 | return PRECEDENCE.BITWISE; | |
| 154 | fi | |
| 155 | if first == '|' \/ first == '¦' \/ first == '∪' then | |
| 156 | return PRECEDENCE.BITWISE; | |
| 157 | fi | |
| 158 | if first == '^' then | |
| 159 | return PRECEDENCE.BITWISE; | |
| 160 | fi | |
| 161 | if first == '∧' \/ first == '∨' then | |
| 162 | return PRECEDENCE.BOOLEAN; | |
| 163 | fi | |
| 164 | if first == '?' then | |
| 165 | return PRECEDENCE.USER_1; | |
| 166 | fi | |
| 167 | ||
| 168 | return PRECEDENCE.USER_5; | |
| 169 | si | |
| 170 | ||
| 171 | // First-character associativity heuristic. Default is left; | |
| 172 | // `?`-prefixed operators are right-associative so that `a ?? b ?? c` | |
| 173 | // parses as `a ?? (b ?? c)` — each intermediate result stays | |
| 174 | // optional rather than being closed off by the inner operator. | |
| 175 | auto_associativity_for(op: string) -> ASSOCIATIVITY static is | |
| 176 | if op.get_chars(0) == '?' then | |
| 177 | return ASSOCIATIVITY.RIGHT; | |
| 178 | fi | |
| 179 | return ASSOCIATIVITY.LEFT; | |
| 180 | si | |
| 181 | ||
| 182 | parse(context: CONTEXT) -> Trees.Expressions.Expression is | |
| 183 | try | |
| 184 | return parse(context, expression_tertiary_parser.parse(context)!, PRECEDENCE.MIN); | |
| 185 | catch ue: UnwindException | |
| 186 | throw ue; | |
| 187 | ||
| 188 | catch e: Exception | |
| 189 | IoC.CONTAINER.instance.logger.exception(context.current.location, e, "parse exception: {e.message}"); | |
| 190 | ||
| 191 | return Trees.Expressions.Literals.NONE(context.location); | |
| 192 | yrt | |
| 193 | si | |
| 194 | ||
| 195 | // precedence climbing expression parser: | |
| 196 | parse(context: CONTEXT, left: Trees.Expressions.Expression mut, min_precedence: PRECEDENCE) -> Trees.Expressions.Expression is | |
| 197 | let last_was_yield_infix mut = false; | |
| 198 | ||
| 199 | do | |
| 200 | let left_precedence = precedence(context); | |
| 201 | ||
| 202 | if cast int(left_precedence) < cast int(min_precedence) then | |
| 203 | break; | |
| 204 | fi | |
| 205 | ||
| 206 | let apparent_op = context.current.value_string; | |
| 207 | ||
| 208 | let real_op mut = apparent_op; | |
| 209 | ||
| 210 | if _real_operation.contains_key(apparent_op) then | |
| 211 | real_op = _real_operation[apparent_op]; | |
| 212 | fi | |
| 213 | ||
| 214 | let op = Trees.Identifiers.Identifier(context.location, real_op); | |
| 215 | ||
| 216 | let op_location = context.location; | |
| 217 | ||
| 218 | let associativity = auto_associativity_for(apparent_op); | |
| 219 | ||
| 220 | context.next_token(); | |
| 221 | ||
| 222 | let right: Trees.Expressions.Expression mut = expression_tertiary_parser.parse(context)!; | |
| 223 | ||
| 224 | assert right? else "parse right failed"; | |
| 225 | ||
| 226 | do | |
| 227 | let right_precedence = precedence(context); | |
| 228 | ||
| 229 | if associativity == ASSOCIATIVITY.RIGHT then | |
| 230 | if cast int(right_precedence) < cast int(left_precedence) then | |
| 231 | break; | |
| 232 | fi | |
| 233 | else | |
| 234 | if cast int(right_precedence) <= cast int(left_precedence) then | |
| 235 | break; | |
| 236 | fi | |
| 237 | fi | |
| 238 | ||
| 239 | right = parse(context, right, right_precedence); | |
| 240 | od | |
| 241 | ||
| 242 | if apparent_op =~ "||" then | |
| 243 | if last_was_yield_infix then | |
| 244 | IoC.CONTAINER.instance.logger.error( | |
| 245 | op_location, | |
| 246 | "yield infix '||' does not chain" | |
| 247 | ); | |
| 248 | fi | |
| 249 | left = lower_yield_infix(left, right); | |
| 250 | last_was_yield_infix = true; | |
| 251 | else | |
| 252 | left = Trees.Expressions.BINARY(left.location::right.location, op, apparent_op, left, right); | |
| 253 | last_was_yield_infix = false; | |
| 254 | fi | |
| 255 | od | |
| 256 | ||
| 257 | return left; | |
| 258 | si | |
| 259 | ||
| 260 | // Desugar `value || next_state` into a call to the stream-step | |
| 261 | // YIELD variant: `Ghul.Pipes.STREAM.YIELD(value, next_state)`. | |
| 262 | // The right operand is the next state for the consuming | |
| 263 | // `STREAM_PIPE` to feed into the next `advance(state)` call — | |
| 264 | // not a deferred thunk, since laziness comes from the consumer | |
| 265 | // invoking `advance` once per `move_next`. | |
| 266 | lower_yield_infix( | |
| 267 | left: Trees.Expressions.Expression, | |
| 268 | right: Trees.Expressions.Expression | |
| 269 | ) -> Trees.Expressions.Expression static is | |
| 270 | let location = left.location::right.location; | |
| 271 | ||
| 272 | let ghul = Trees.Identifiers.Identifier(location, "Ghul"); | |
| 273 | let pipes = Trees.Identifiers.QUALIFIED(location, ghul, "Pipes", location, location); | |
| 274 | let stream = Trees.Identifiers.QUALIFIED(location, pipes, "STREAM", location, location); | |
| 275 | let yield_member = Trees.Identifiers.QUALIFIED(location, stream, "YIELD", location, location); | |
| 276 | ||
| 277 | let yield_function = Trees.Expressions.IDENTIFIER(location, yield_member); | |
| 278 | ||
| 279 | let call_arguments = Trees.Expressions.LIST( | |
| 280 | location, | |
| 281 | [left, right]: Trees.Expressions.Expression | |
| 282 | ); | |
| 283 | ||
| 284 | return Trees.Expressions.CALL(location, yield_function, call_arguments); | |
| 285 | si | |
| 286 | si | |
| 287 | si |