Parser.pudu

Pudu304 lines11.9 KB

Copy pathGitHub ↗

1/** @Log.Expressions.Parser.Grammar — tokens into an expression tree */2module PuduLangLog.Expressions.Parser34import Std.Decimal as Decimal5import Std.List as List6import Std.Set as Set7import PuduLangLog.Expressions.Lexer as Lexer8import PuduLangLog.Expressions.Syntax as Syntax9import PuduLangLog as Log1011/// The comparison operators.12const COMPARISONS: Set[Str] = setOf(["=", "<>", "<", "<=", ">", ">="])1314/// Hexadecimal digits by value.15const HEX: Str = "0123456789abcdef"1617/** @Log.Expressions.Parser.Step — a parsed part and the index after it */18type Step = Result[(Syntax.Expression, Int), Str]1920/// The expression the whole text denotes, or where and why it could not be read.21export fn parse(text: Str) -> Result[Syntax.Expression, Str] {22  let found = Lexer.tokens(text) ?23  let (expression, next) = expressionAt(&found, 0) ?24  if found[next].kind != Lexer.End { return Err(unexpected(&found[next])) }25  Ok(expression)26}2728/// The expression starting at a token, and the index after it; used by templates to read holes.29export fn expressionAt(found: &Array[Lexer.Token], start: Int) -> Step {30  if isKeyword(found, start, "if") {31    let (condition, afterCondition) = expressionAt(found, start + 1) ?32    let afterThen = expect(found, afterCondition, "then") ?33    let (then, afterValue) = expressionAt(found, afterThen) ?34    let afterElse = expect(found, afterValue, "else") ?35    let (otherwise, end) = expressionAt(found, afterElse) ?36    return Ok((Syntax.Conditional(condition, then, otherwise), end))37  }38  either(found, start)39}4041/// A chain of `or`.42fn either(found: &Array[Lexer.Token], start: Int) -> Step {43  var (left, next) = both(found, start) ?44  while isKeyword(found, next, "or") {45    let (right, after) = both(found, next + 1) ?46    left = Syntax.Binary("or", left, right, false)47    next = after48  }49  Ok((left, next))50}5152/// A chain of `and`.53fn both(found: &Array[Lexer.Token], start: Int) -> Step {54  var (left, next) = negation(found, start) ?55  while isKeyword(found, next, "and") {56    let (right, after) = negation(found, next + 1) ?57    left = Syntax.Binary("and", left, right, false)58    next = after59  }60  Ok((left, next))61}6263/// `not` applied to a comparison, any number of times.64fn negation(found: &Array[Lexer.Token], start: Int) -> Step {65  if isKeyword(found, start, "not") {66    let (operand, next) = negation(found, start + 1) ?67    return Ok((Syntax.Unary("not", operand), next))68  }69  comparison(found, start)70}7172/// An additive expression, optionally compared, matched with `like`, tested with `in`, or checked73/// with `is null`; `ci` after the right side makes text comparisons ignore case.74fn comparison(found: &Array[Lexer.Token], start: Int) -> Step {75  let (left, next) = additive(found, start) ?76  let token = found[next]77  if token.kind == Lexer.Symbol && Set.contains(&COMPARISONS, token.text) { return compared(found, next + 1, token.text, left) }78  if isKeyword(found, next, "like") || isKeyword(found, next, "in") { return compared(found, next + 1, token.text, left) }79  if isKeyword(found, next, "not") && (isKeyword(found, next + 1, "like") || isKeyword(found, next + 1, "in")) {80    let (inner, after) = compared(found, next + 2, found[next + 1].text, left) ?81    return Ok((Syntax.Unary("not", inner), after))82  }83  if isKeyword(found, next, "is") {84    let negated = isKeyword(found, next + 1, "not")85    let at = if negated { next + 2 } else { next + 1 }86    let after = expect(found, at, "null") ?87    let test = Syntax.Binary("is null", left, Syntax.Constant(Log.Scalar(Log.Null)), false)88    return Ok((if negated { Syntax.Unary("not", test) } else { test }, after))89  }90  Ok((left, next))91}9293/// The right side of a binary comparison and an optional `ci`.94fn compared(found: &Array[Lexer.Token], start: Int, operator: Str, left: Syntax.Expression) -> Step {95  let (right, next) = additive(found, start) ?96  let ignoring = isKeyword(found, next, "ci")97  Ok((Syntax.Binary(operator, left, right, ignoring), if ignoring { next + 1 } else { next }))98}99100/// A chain of `+` and `-`.101fn additive(found: &Array[Lexer.Token], start: Int) -> Step {102  var (left, next) = multiplicative(found, start) ?103  while isSymbol(found, next, "+") || isSymbol(found, next, "-") {104    let operator = found[next].text105    let (right, after) = multiplicative(found, next + 1) ?106    left = Syntax.Binary(operator, left, right, false)107    next = after108  }109  Ok((left, next))110}111112/// A chain of `*`, `/`, and `%`.113fn multiplicative(found: &Array[Lexer.Token], start: Int) -> Step {114  var (left, next) = power(found, start) ?115  while isSymbol(found, next, "*") || isSymbol(found, next, "/") || isSymbol(found, next, "%") {116    let operator = found[next].text117    let (right, after) = power(found, next + 1) ?118    left = Syntax.Binary(operator, left, right, false)119    next = after120  }121  Ok((left, next))122}123124/// A power, grouping to the right.125fn power(found: &Array[Lexer.Token], start: Int) -> Step {126  let (base, next) = negative(found, start) ?127  if !isSymbol(found, next, "^") { return Ok((base, next)) }128  let (exponent, after) = power(found, next + 1) ?129  Ok((Syntax.Binary("^", base, exponent, false), after))130}131132/// A unary minus, any number of times.133fn negative(found: &Array[Lexer.Token], start: Int) -> Step {134  if isSymbol(found, start, "-") {135    let (operand, next) = negative(found, start + 1) ?136    return Ok((Syntax.Unary("-", operand), next))137  }138  postfix(found, start)139}140141/// A primary followed by member accesses and indexers.142fn postfix(found: &Array[Lexer.Token], start: Int) -> Step {143  var (target, next) = primary(found, start) ?144  loop {145    if isSymbol(found, next, ".") && found[next + 1].kind == Lexer.Identifier {146      target = Syntax.Member(target, found[next + 1].text)147      next = next + 2148    } else if isSymbol(found, next, "[") {149      if (isSymbol(found, next + 1, "?") || isSymbol(found, next + 1, "*")) && isSymbol(found, next + 2, "]") {150        target = Syntax.Wildcard(target, if found[next + 1].text == "?" { Syntax.AnyOf } else { Syntax.AllOf })151        next = next + 3152      } else {153        let (key, after) = expressionAt(found, next + 1) ?154        next = expectSymbol(found, after, "]") ?155        target = Syntax.Index(target, key)156      }157    } else {158      return Ok((target, next))159    }160  }161}162163/// A literal, a name, a function call, a parenthesized expression, an array, or an object.164fn primary(found: &Array[Lexer.Token], start: Int) -> Step {165  let token = found[start]166  match token.kind {167    case Lexer.Number => Ok((Syntax.Constant(Log.Scalar(numberOf(token.text))), start + 1))168    case Lexer.Text => Ok((Syntax.Constant(Log.Scalar(Log.Text(token.text))), start + 1))169    case Lexer.BuiltIn => Ok((Syntax.Name(token.text), start + 1))170    case Lexer.Keyword => keywordValue(&token, start)171    case Lexer.Identifier => {172      if !isSymbol(found, start + 1, "(") { return Ok((Syntax.Name(token.text), start + 1)) }173      let (arguments, next) = argumentsAt(found, start + 2) ?174      let ignoring = isKeyword(found, next, "ci")175      Ok((Syntax.Call(token.text.toLower(), arguments, ignoring), if ignoring { next + 1 } else { next }))176    }177    case Lexer.Symbol => {178      if token.text == "(" {179        let (inner, next) = expressionAt(found, start + 1) ?180        return Ok((inner, expectSymbol(found, next, ")") ?))181      }182      if token.text == "[" { return arrayAt(found, start + 1) }183      if token.text == "\{" { return objectAt(found, start + 1) }184      Err(unexpected(&token))185    }186    case Lexer.End => Err("the expression ends too soon")187  }188}189190/// `true`, `false`, or `null`.191fn keywordValue(token: &Lexer.Token, start: Int) -> Step {192  match token.text {193    case "true" => Ok((Syntax.Constant(Log.Scalar(Log.Boolean(true))), start + 1))194    case "false" => Ok((Syntax.Constant(Log.Scalar(Log.Boolean(false))), start + 1))195    case "null" => Ok((Syntax.Constant(Log.Scalar(Log.Null)), start + 1))196    case _ => Err(unexpected(token))197  }198}199200/// Call arguments up to the closing parenthesis, and the index after it.201fn argumentsAt(found: &Array[Lexer.Token], start: Int) -> Result[(Array[Syntax.Expression], Int), Str] {202  var arguments: Array[Syntax.Expression] = []203  if isSymbol(found, start, ")") { return Ok((arguments, start + 1)) }204  var next = start205  loop {206    let (argument, after) = expressionAt(found, next) ?207    arguments = arguments.push(argument)208    if isSymbol(found, after, ")") { return Ok((arguments, after + 1)) }209    next = expectSymbol(found, after, ",") ?210  }211}212213/// An array literal after its `[`, with `..` spreading another array.214fn arrayAt(found: &Array[Lexer.Token], start: Int) -> Step {215  var elements: Array[Syntax.Element] = []216  if isSymbol(found, start, "]") { return Ok((Syntax.ArrayOf(elements), start + 1)) }217  var next = start218  loop {219    let spread = isSymbol(found, next, "..")220    let (item, after) = expressionAt(found, if spread { next + 1 } else { next }) ?221    elements = elements.push(if spread { Syntax.SpreadItems(item) } else { Syntax.Item(item) })222    if isSymbol(found, after, "]") { return Ok((Syntax.ArrayOf(elements), after + 1)) }223    next = expectSymbol(found, after, ",") ?224  }225}226227/// An object literal after its `{`: `name: value`, `'quoted name': value`, a bare name standing for228/// the property of that name, and `..` spreading another object.229fn objectAt(found: &Array[Lexer.Token], start: Int) -> Step {230  var fields: Array[Syntax.Field] = []231  if isSymbol(found, start, "\}") { return Ok((Syntax.ObjectOf(fields), start + 1)) }232  var next = start233  loop {234    let token = found[next]235    var after = next236    if isSymbol(found, next, "..") {237      let (members, end) = expressionAt(found, next + 1) ?238      fields = fields.push(Syntax.SpreadMembers(members))239      after = end240    } else if token.kind == Lexer.Identifier || token.kind == Lexer.Text {241      if isSymbol(found, next + 1, ":") {242        let (held, end) = expressionAt(found, next + 2) ?243        fields = fields.push(Syntax.Pair(token.text, held))244        after = end245      } else {246        fields = fields.push(Syntax.Pair(token.text, Syntax.Name(token.text)))247        after = next + 1248      }249    } else {250      return Err(unexpected(&token))251    }252    if isSymbol(found, after, "\}") { return Ok((Syntax.ObjectOf(fields), after + 1)) }253    next = expectSymbol(found, after, ",") ?254  }255}256257/// A number literal: an integer, a decimal, or hexadecimal after `0x`.258fn numberOf(text: Str) -> Log.Scalar {259  if text.startsWith("0x") {260    var value = Decimal.zero()261    for character in text.drop(2).toLower().chars() { value = value * Decimal.fromInt(16) + Decimal.fromInt(HEX.indexOf(character.toText())) }262    return match Decimal.toInt(value) {263      case Some(whole) => Log.Integer(whole)264      case None => Log.Exact(value)265    }266  }267  if text.contains(".") { return Log.Exact(Decimal.parseOr(text, Decimal.zero())) }268  match text.toInt() {269    case Some(value) => Log.Integer(value)270    case None => Log.Exact(Decimal.parseOr(text, Decimal.zero()))271  }272}273274/// Whether the token at an index is a keyword.275fn isKeyword(found: &Array[Lexer.Token], index: Int, word: Str) -> Bool {276  match List.get(found, index) {277    case Some(token) => token.kind == Lexer.Keyword && token.text == word278    case None => false279  }280}281282/// Whether the token at an index is a symbol.283fn isSymbol(found: &Array[Lexer.Token], index: Int, symbol: Str) -> Bool {284  match List.get(found, index) {285    case Some(token) => token.kind == Lexer.Symbol && token.text == symbol286    case None => false287  }288}289290/// The index after a required keyword.291fn expect(found: &Array[Lexer.Token], index: Int, word: Str) -> Result[Int, Str] {292  if isKeyword(found, index, word) { Ok(index + 1) } else { Err("expected `" + word + "` at " + show(found[index].position)) }293}294295/// The index after a required symbol.296fn expectSymbol(found: &Array[Lexer.Token], index: Int, symbol: Str) -> Result[Int, Str] {297  if isSymbol(found, index, symbol) { Ok(index + 1) } else { Err("expected `" + symbol + "` at " + show(found[index].position)) }298}299300/// A description of an unexpected token.301fn unexpected(token: &Lexer.Token) -> Str {302  if token.kind == Lexer.End { "the expression ends too soon" } else { "unexpected `" + token.text + "` at " + show(token.position) }303}304