Parser

The Alpaca parser transforms a List[Lexeme] into a typed result by matching token sequences against grammar rules. You define rules using pattern matching, and the macro builds an LALR(1) parse table at compile time.

Under the hood: compile-time table generation

When you define object MyParser extends Parser, the Alpaca macro:

Reads every Rule val declaration
Builds an LALR(1) parse table (states, transitions, actions)
Compiles semantic actions (your case bodies) into the action table
Reports grammar conflicts (shift/reduce, reduce/reduce) as compile errors

At runtime, parse() executes the precomputed table. No grammar analysis happens during parsing.

Defining a Parser

Extend Parser for a stateless parser, or Parser[Ctx] to carry custom state through reductions. The required entry point is val root: Rule[R] -- the macro uses this as the start symbol.

import halotukozak.alpaca.*

val BrainLexer = lexer:
  case ">" => Token["next"]
  case "<" => Token["prev"]
  case "\\+" => Token["inc"]
  case "-" => Token["dec"]
  case "\\." => Token["print"]
  case "," => Token["read"]
  case "\\[" => Token["jumpForward"]
  case "\\]" => Token["jumpBack"]
  case "." => Token.Ignored
  case "\n" => Token.Ignored

enum BrainAST:
  case Root(ops: List[BrainAST])
  case While(ops: List[BrainAST])
  case Next, Prev, Inc, Dec, Print, Read
import halotukozak.alpaca.*

object BrainParser extends Parser:
  val root: Rule[BrainAST] = rule:
    case Operation.List(stmts) => BrainAST.Root(stmts)

  val While: Rule[BrainAST] = rule:
    case (BrainLexer.jumpForward(_), Operation.List(stmts), BrainLexer.jumpBack(_)) =>
      BrainAST.While(stmts)

  val Operation: Rule[BrainAST] = rule(
    { case BrainLexer.next(_) => BrainAST.Next },
    { case BrainLexer.prev(_) => BrainAST.Prev },
    { case BrainLexer.inc(_) => BrainAST.Inc },
    { case BrainLexer.dec(_) => BrainAST.Dec },
    { case BrainLexer.print(_) => BrainAST.Print },
    { case BrainLexer.read(_) => BrainAST.Read },
    { case While(whl) => whl },
  )

brain-parser

Declare every rule with val. A def rule is a compile error; see Common Problems for this and other errors you are likely to hit.

Rules and Productions

A Rule[R] is a named non-terminal that produces values of type R. Use rule to define one or more productions.

Single production -- colon syntax:

import halotukozak.alpaca.*

val BrainLexer = lexer:
  case ">" => Token["next"]
  case "<" => Token["prev"]
  case "\\+" => Token["inc"]
  case "-" => Token["dec"]
  case "\\." => Token["print"]
  case "," => Token["read"]
  case "\\[" => Token["jumpForward"]
  case "\\]" => Token["jumpBack"]
  case "." => Token.Ignored
  case "\n" => Token.Ignored

enum BrainAST:
  case Root(ops: List[BrainAST])
  case While(ops: List[BrainAST])
  case Next, Prev, Inc, Dec, Print, Read
object SingleProductionParser extends Parser:
  val root: Rule[BrainAST] = rule:
    case Operation.List(stmts) => BrainAST.Root(stmts)

  val Operation: Rule[BrainAST] = rule:
    case BrainLexer.inc(_) => BrainAST.Inc

Multiple productions -- argument list:

import halotukozak.alpaca.*

val BrainLexer = lexer:
  case ">" => Token["next"]
  case "<" => Token["prev"]
  case "\\+" => Token["inc"]
  case "-" => Token["dec"]
  case "\\." => Token["print"]
  case "," => Token["read"]
  case "\\[" => Token["jumpForward"]
  case "\\]" => Token["jumpBack"]
  case "." => Token.Ignored
  case "\n" => Token.Ignored

enum BrainAST:
  case Root(ops: List[BrainAST])
  case While(ops: List[BrainAST])
  case Next, Prev, Inc, Dec, Print, Read
object MultipleProductionsParser extends Parser:
  val root: Rule[BrainAST] = rule:
    case Operation.List(stmts) => BrainAST.Root(stmts)

  val While: Rule[BrainAST] = rule:
    case (BrainLexer.jumpForward(_), Operation.List(stmts), BrainLexer.jumpBack(_)) =>
      BrainAST.While(stmts)

  val Operation: Rule[BrainAST] = rule(
    { case BrainLexer.inc(_) => BrainAST.Inc },     // single-symbol: direct match
    { case BrainLexer.dec(_) => BrainAST.Dec },
    { case While(whl) => whl },                      // non-terminal reference
  )

Multi-symbol productions match a tuple; single-symbol productions match directly (no parentheses). Each { case ... } block must contain exactly one alternative.

Multiline Actions

Rule bodies can span multiple statements. Use intermediate variables and return the final value:

import halotukozak.alpaca.*

val BrainLexer = lexer:
  case "\\+" => Token["inc"]
  case "-" => Token["dec"]
  case name @ "[A-Za-z]+" => Token["functionName"](name)
  case "\\(" => Token["functionOpen"]
  case "\\)" => Token["functionClose"]
  case "!" => Token["functionCall"]
  case "\\s+" => Token.Ignored

enum BrainAST:
  case Root(ops: List[BrainAST])
  case FunctionDef(name: String, ops: List[BrainAST])
  case FunctionCall(name: String)
  case Inc, Dec

case class BrainParserCtx(
  functions: Set[String] = Set.empty,
) extends ParserCtx
object FunctionDefParser extends Parser[BrainParserCtx]:
  val root: Rule[BrainAST] = rule:
    case Operation.List(stmts) => BrainAST.Root(stmts)

  val FunctionDef: Rule[BrainAST] = rule:
    case (BrainLexer.functionName(name), BrainLexer.functionOpen(_),
          Operation.List(ops), BrainLexer.functionClose(_)) =>
      val funcName = name.value
      require(!ctx.functions(funcName), s"Function $funcName already defined")
      ctx.functions += funcName
      BrainAST.FunctionDef(funcName, ops)

  val Operation: Rule[BrainAST] = rule(
    { case BrainLexer.inc(_) => BrainAST.Inc },
    { case FunctionDef(fdef) => fdef },
  )

Named Productions with Special Characters

Production names can contain hyphens, dots, spaces, or any other character that is not a valid Scala identifier. Access them with backtick quoting in resolutions:

import halotukozak.alpaca.*

val MyLexer = lexer:
  case "\\+" => Token["PLUS"]
  case "<<" => Token["SHL"]
  case "if" => Token["IF"]
  case "then" => Token["THEN"]
  case x @ "[0-9]+" => Token["NUM"](x.toInt)
  case "\\s+" => Token.Ignored
object MyParser extends Parser:
  val root: Rule[Int] = rule:
    case Expr(e) => e

  val Expr: Rule[Int] = rule(
    "left-add" { case (Expr(a), MyLexer.PLUS(_), Expr(b)) => a + b },
    "shift.left" { case (Expr(a), MyLexer.SHL(_), Expr(b)) => a << b },
    "if then" { case (MyLexer.IF(_), Expr(c), MyLexer.THEN(_), Expr(t)) => if c != 0 then t else 0 },
    { case MyLexer.NUM(n) => n.value },
  )

given Resolutions[MyParser.type] = resolutions(
  production.`left-add`.before(MyLexer.PLUS, MyLexer.SHL, MyLexer.THEN),
  production.`shift.left`.before(MyLexer.PLUS, MyLexer.SHL, MyLexer.THEN),
  production.`if then`.before(MyLexer.PLUS, MyLexer.SHL, MyLexer.THEN),
)

Matching Symbols

The left side of => is a pattern made of extractors:

BrainLexer.inc(lexeme) matches a terminal and binds its Lexeme (read the value with lexeme.value);
While(whl) matches a non-terminal and binds the value its rule produced;
.List, .Option and .SeparatedBy[Separator] match a symbol zero or more times, optionally, or delimited by a separator, without hand-written recursion.

Extractors covers every form, with their binding types.

Parsing Input

Call parse(lexemes) where lexemes comes from tokenize():

import halotukozak.alpaca.*

val BrainLexer = lexer:
  case ">" => Token["next"]
  case "<" => Token["prev"]
  case "\\+" => Token["inc"]
  case "-" => Token["dec"]
  case "\\." => Token["print"]
  case "," => Token["read"]
  case "\\[" => Token["jumpForward"]
  case "\\]" => Token["jumpBack"]
  case "." => Token.Ignored
  case "\n" => Token.Ignored

enum BrainAST:
  case Root(ops: List[BrainAST])
  case While(ops: List[BrainAST])
  case Next, Prev, Inc, Dec, Print, Read
import halotukozak.alpaca.*

object BrainParser extends Parser:
  val root: Rule[BrainAST] = rule:
    case Operation.List(stmts) => BrainAST.Root(stmts)

  val While: Rule[BrainAST] = rule:
    case (BrainLexer.jumpForward(_), Operation.List(stmts), BrainLexer.jumpBack(_)) =>
      BrainAST.While(stmts)

  val Operation: Rule[BrainAST] = rule(
    { case BrainLexer.next(_) => BrainAST.Next },
    { case BrainLexer.prev(_) => BrainAST.Prev },
    { case BrainLexer.inc(_) => BrainAST.Inc },
    { case BrainLexer.dec(_) => BrainAST.Dec },
    { case BrainLexer.print(_) => BrainAST.Print },
    { case BrainLexer.read(_) => BrainAST.Read },
    { case While(whl) => whl },
  )
class Memory(
  val cells: Array[Int] = new Array(256),
  var pointer: Int = 0,
)

extension (ast: BrainAST)
  def eval(mem: Memory): Unit = ast match
    case BrainAST.Root(ops)  => ops.foreach(_.eval(mem))
    case BrainAST.Next       => mem.pointer = (mem.pointer + 1) & 0xff
    case BrainAST.Prev       => mem.pointer = (mem.pointer - 1) & 0xff
    case BrainAST.Inc        => mem.cells(mem.pointer) = (mem.cells(mem.pointer) + 1) & 0xff
    case BrainAST.Dec        => mem.cells(mem.pointer) = (mem.cells(mem.pointer) - 1) & 0xff
    case BrainAST.Print      => print(mem.cells(mem.pointer).toChar)
    case BrainAST.Read       => mem.cells(mem.pointer) = scala.io.StdIn.readChar() & 0xff
    case BrainAST.While(ops) => while mem.cells(mem.pointer) != 0 do ops.foreach(_.eval(mem))
val lexemes = BrainLexer.tokenize("++[>+<-]").getOrThrow
val parsed = BrainParser.parse(lexemes)
// parsed: Result[ParserCtx.Empty, BrainAST, BrainLexer.ParserError]

brain-tokenize

parse() does not throw when the input does not match the grammar. It returns a Result -- the same type tokenize returns -- which is one of two cases, both carrying the parser context (ctx) as it was when parsing ended:

Result.Success(ctx, value) -- the input matched, and value is what the root rule produced (a BrainAST here);
Result.Failure(ctx, recovered, errors) -- the input did not match; errors is a non-empty list of ParserErrors. recovered is the value produced anyway when the parser's error-handling strategy skipped past the errors and parsing still reached the end (see Error Recovery), and None when parsing stopped before producing a value -- at the first error by default, or at a later error that was not skipped.

Match on it to handle both outcomes:

import halotukozak.alpaca.*

val BrainLexer = lexer:
  case ">" => Token["next"]
  case "<" => Token["prev"]
  case "\\+" => Token["inc"]
  case "-" => Token["dec"]
  case "\\." => Token["print"]
  case "," => Token["read"]
  case "\\[" => Token["jumpForward"]
  case "\\]" => Token["jumpBack"]
  case "." => Token.Ignored
  case "\n" => Token.Ignored

enum BrainAST:
  case Root(ops: List[BrainAST])
  case While(ops: List[BrainAST])
  case Next, Prev, Inc, Dec, Print, Read
import halotukozak.alpaca.*

object BrainParser extends Parser:
  val root: Rule[BrainAST] = rule:
    case Operation.List(stmts) => BrainAST.Root(stmts)

  val While: Rule[BrainAST] = rule:
    case (BrainLexer.jumpForward(_), Operation.List(stmts), BrainLexer.jumpBack(_)) =>
      BrainAST.While(stmts)

  val Operation: Rule[BrainAST] = rule(
    { case BrainLexer.next(_) => BrainAST.Next },
    { case BrainLexer.prev(_) => BrainAST.Prev },
    { case BrainLexer.inc(_) => BrainAST.Inc },
    { case BrainLexer.dec(_) => BrainAST.Dec },
    { case BrainLexer.print(_) => BrainAST.Print },
    { case BrainLexer.read(_) => BrainAST.Read },
    { case While(whl) => whl },
  )
class Memory(
  val cells: Array[Int] = new Array(256),
  var pointer: Int = 0,
)

extension (ast: BrainAST)
  def eval(mem: Memory): Unit = ast match
    case BrainAST.Root(ops)  => ops.foreach(_.eval(mem))
    case BrainAST.Next       => mem.pointer = (mem.pointer + 1) & 0xff
    case BrainAST.Prev       => mem.pointer = (mem.pointer - 1) & 0xff
    case BrainAST.Inc        => mem.cells(mem.pointer) = (mem.cells(mem.pointer) + 1) & 0xff
    case BrainAST.Dec        => mem.cells(mem.pointer) = (mem.cells(mem.pointer) - 1) & 0xff
    case BrainAST.Print      => print(mem.cells(mem.pointer).toChar)
    case BrainAST.Read       => mem.cells(mem.pointer) = scala.io.StdIn.readChar() & 0xff
    case BrainAST.While(ops) => while mem.cells(mem.pointer) != 0 do ops.foreach(_.eval(mem))
val lexemes = BrainLexer.tokenize("++[>+<-]").getOrThrow
val parsed = BrainParser.parse(lexemes)
// parsed: Result[ParserCtx.Empty, BrainAST, BrainLexer.ParserError]
parsed match
  case Result.Success(_, ast) => ast.eval(Memory())
  case Result.Failure(_, _, errors) => errors.foreach(error => println(error.message))

When failing is not an option you want to handle at that point, getOrThrow returns the value or throws a ParserException holding the errors, and toOption / toEither convert the result:

import halotukozak.alpaca.*

val BrainLexer = lexer:
  case ">" => Token["next"]
  case "<" => Token["prev"]
  case "\\+" => Token["inc"]
  case "-" => Token["dec"]
  case "\\." => Token["print"]
  case "," => Token["read"]
  case "\\[" => Token["jumpForward"]
  case "\\]" => Token["jumpBack"]
  case "." => Token.Ignored
  case "\n" => Token.Ignored

enum BrainAST:
  case Root(ops: List[BrainAST])
  case While(ops: List[BrainAST])
  case Next, Prev, Inc, Dec, Print, Read
import halotukozak.alpaca.*

object BrainParser extends Parser:
  val root: Rule[BrainAST] = rule:
    case Operation.List(stmts) => BrainAST.Root(stmts)

  val While: Rule[BrainAST] = rule:
    case (BrainLexer.jumpForward(_), Operation.List(stmts), BrainLexer.jumpBack(_)) =>
      BrainAST.While(stmts)

  val Operation: Rule[BrainAST] = rule(
    { case BrainLexer.next(_) => BrainAST.Next },
    { case BrainLexer.prev(_) => BrainAST.Prev },
    { case BrainLexer.inc(_) => BrainAST.Inc },
    { case BrainLexer.dec(_) => BrainAST.Dec },
    { case BrainLexer.print(_) => BrainAST.Print },
    { case BrainLexer.read(_) => BrainAST.Read },
    { case While(whl) => whl },
  )
class Memory(
  val cells: Array[Int] = new Array(256),
  var pointer: Int = 0,
)

extension (ast: BrainAST)
  def eval(mem: Memory): Unit = ast match
    case BrainAST.Root(ops)  => ops.foreach(_.eval(mem))
    case BrainAST.Next       => mem.pointer = (mem.pointer + 1) & 0xff
    case BrainAST.Prev       => mem.pointer = (mem.pointer - 1) & 0xff
    case BrainAST.Inc        => mem.cells(mem.pointer) = (mem.cells(mem.pointer) + 1) & 0xff
    case BrainAST.Dec        => mem.cells(mem.pointer) = (mem.cells(mem.pointer) - 1) & 0xff
    case BrainAST.Print      => print(mem.cells(mem.pointer).toChar)
    case BrainAST.Read       => mem.cells(mem.pointer) = scala.io.StdIn.readChar() & 0xff
    case BrainAST.While(ops) => while mem.cells(mem.pointer) != 0 do ops.foreach(_.eval(mem))
val lexemes = BrainLexer.tokenize("++[>+<-]").getOrThrow
val parsed = BrainParser.parse(lexemes)
// parsed: Result[ParserCtx.Empty, BrainAST, BrainLexer.ParserError]
parsed.getOrThrow.eval(Memory())  // the AST, or throws a ParserException
parsed.toOption                   // Some(ast), or None
parsed.toEither                   // Right(ast), or Left(errors)

A ParserError is plain data: it carries the lexeme the parser could not accept (unexpected, None when the input ended too early), what the grammar would have accepted there (expected, token names and ParserError.EndOfInput), and, at the end of the input, the last lexeme before it (last, otherwise None). The errors parse returns have a Fields type member, the lexer context's fields that the lexemes carry (in a signature, write their type as BrainLexer.ParserError; see Naming the Types), so the error's position is in the lexer context's fields: error.unexpected.map(_.line) and error.unexpected.map(_.column) with LexerCtx.Default, a compile error when the context has no such field. At the end of the input, read the position from error.last instead. Its message names the lexemes but no position, e.g. for 1 + + 2 in a grammar of numbers and +:

Unexpected PLUS "+". Expected one of: NUMBER

import halotukozak.alpaca.*

val BrainLexer = lexer:
  case ">" => Token["next"]
  case "<" => Token["prev"]
  case "\\+" => Token["inc"]
  case "-" => Token["dec"]
  case "\\." => Token["print"]
  case "," => Token["read"]
  case "\\[" => Token["jumpForward"]
  case "\\]" => Token["jumpBack"]
  case "." => Token.Ignored
  case "\n" => Token.Ignored

enum BrainAST:
  case Root(ops: List[BrainAST])
  case While(ops: List[BrainAST])
  case Next, Prev, Inc, Dec, Print, Read
import halotukozak.alpaca.*

object BrainParser extends Parser:
  val root: Rule[BrainAST] = rule:
    case Operation.List(stmts) => BrainAST.Root(stmts)

  val While: Rule[BrainAST] = rule:
    case (BrainLexer.jumpForward(_), Operation.List(stmts), BrainLexer.jumpBack(_)) =>
      BrainAST.While(stmts)

  val Operation: Rule[BrainAST] = rule(
    { case BrainLexer.next(_) => BrainAST.Next },
    { case BrainLexer.prev(_) => BrainAST.Prev },
    { case BrainLexer.inc(_) => BrainAST.Inc },
    { case BrainLexer.dec(_) => BrainAST.Dec },
    { case BrainLexer.print(_) => BrainAST.Print },
    { case BrainLexer.read(_) => BrainAST.Read },
    { case While(whl) => whl },
  )
class Memory(
  val cells: Array[Int] = new Array(256),
  var pointer: Int = 0,
)

extension (ast: BrainAST)
  def eval(mem: Memory): Unit = ast match
    case BrainAST.Root(ops)  => ops.foreach(_.eval(mem))
    case BrainAST.Next       => mem.pointer = (mem.pointer + 1) & 0xff
    case BrainAST.Prev       => mem.pointer = (mem.pointer - 1) & 0xff
    case BrainAST.Inc        => mem.cells(mem.pointer) = (mem.cells(mem.pointer) + 1) & 0xff
    case BrainAST.Dec        => mem.cells(mem.pointer) = (mem.cells(mem.pointer) - 1) & 0xff
    case BrainAST.Print      => print(mem.cells(mem.pointer).toChar)
    case BrainAST.Read       => mem.cells(mem.pointer) = scala.io.StdIn.readChar() & 0xff
    case BrainAST.While(ops) => while mem.cells(mem.pointer) != 0 do ops.foreach(_.eval(mem))
val lexemes = BrainLexer.tokenize("++[>+<-]").getOrThrow
val parsed = BrainParser.parse(lexemes)
// parsed: Result[ParserCtx.Empty, BrainAST, BrainLexer.ParserError]
BrainParser.parse(BrainLexer.tokenize("[+").getOrThrow) match
  case Result.Failure(_, _, errors) =>
    println(errors.head.message)    // Unexpected end of input after inc "+". Expected one of: dec, inc, jumpBack, jumpForward, next, prev, print, read
    println(errors.head.last.map(last => (last.line, last.column))) // Some((1,2))
    println(errors.head.expected)   // List(dec, inc, jumpBack, jumpForward, next, prev, print, read)
  case Result.Success(_, _) => ()

Error Recovery

By default the parser stops at the first error, so errors has one element. An ErrorHandling[Ctx] for your parser context, built with ErrorHandling.forParser, can tell it to skip the unexpected input and go on instead -- as a lexer's is built with ErrorHandling.forLexer (see Error Recovery). Every skip is still reported as a ParserError, and if parsing then reaches the end, its value is the failure's recovered:

import halotukozak.alpaca.*

val BrainLexer = lexer:
  case ">" => Token["next"]
  case "<" => Token["prev"]
  case "\\+" => Token["inc"]
  case "-" => Token["dec"]
  case "\\." => Token["print"]
  case "," => Token["read"]
  case "\\[" => Token["jumpForward"]
  case "\\]" => Token["jumpBack"]
  case "." => Token.Ignored
  case "\n" => Token.Ignored

enum BrainAST:
  case Root(ops: List[BrainAST])
  case While(ops: List[BrainAST])
  case Next, Prev, Inc, Dec, Print, Read
import halotukozak.alpaca.*

object BrainParser extends Parser:
  val root: Rule[BrainAST] = rule:
    case Operation.List(stmts) => BrainAST.Root(stmts)

  val While: Rule[BrainAST] = rule:
    case (BrainLexer.jumpForward(_), Operation.List(stmts), BrainLexer.jumpBack(_)) =>
      BrainAST.While(stmts)

  val Operation: Rule[BrainAST] = rule(
    { case BrainLexer.next(_) => BrainAST.Next },
    { case BrainLexer.prev(_) => BrainAST.Prev },
    { case BrainLexer.inc(_) => BrainAST.Inc },
    { case BrainLexer.dec(_) => BrainAST.Dec },
    { case BrainLexer.print(_) => BrainAST.Print },
    { case BrainLexer.read(_) => BrainAST.Read },
    { case While(whl) => whl },
  )
class Memory(
  val cells: Array[Int] = new Array(256),
  var pointer: Int = 0,
)

extension (ast: BrainAST)
  def eval(mem: Memory): Unit = ast match
    case BrainAST.Root(ops)  => ops.foreach(_.eval(mem))
    case BrainAST.Next       => mem.pointer = (mem.pointer + 1) & 0xff
    case BrainAST.Prev       => mem.pointer = (mem.pointer - 1) & 0xff
    case BrainAST.Inc        => mem.cells(mem.pointer) = (mem.cells(mem.pointer) + 1) & 0xff
    case BrainAST.Dec        => mem.cells(mem.pointer) = (mem.cells(mem.pointer) - 1) & 0xff
    case BrainAST.Print      => print(mem.cells(mem.pointer).toChar)
    case BrainAST.Read       => mem.cells(mem.pointer) = scala.io.StdIn.readChar() & 0xff
    case BrainAST.While(ops) => while mem.cells(mem.pointer) != 0 do ops.foreach(_.eval(mem))
val lexemes = BrainLexer.tokenize("++[>+<-]").getOrThrow
val parsed = BrainParser.parse(lexemes)
// parsed: Result[ParserCtx.Empty, BrainAST, BrainLexer.ParserError]
case class RecoveringCtx() extends ParserCtx

given ErrorHandling[RecoveringCtx] = ErrorHandling.forParser(_ => ErrorHandling.Strategy.SkipOne)

object RecoveringParser extends Parser[RecoveringCtx]:
  val root: Rule[Int] = rule:
    case BrainLexer.inc.List(incs) => incs.size

RecoveringParser.parse(BrainLexer.tokenize("++>+").getOrThrow) match
  case Result.Failure(_, recovered, errors) =>
    println(recovered)                     // Some(3)
    println(errors.flatMap(_.unexpected).map(_.text)) // List(>)
  case Result.Success(_, _) => ()

Strategy	Behavior
`Stop` (default)	Stop at the error; the failure has no `recovered` value
`SkipOne`	Skip the unexpected lexeme and go on
`SkipToNextMatch`	Skip ahead to the next lexeme the parser can accept at that point and go on; one `ParserError` covers the whole skipped run

The end of the input cannot be skipped, so an error there stops the parser whatever the strategy.

The handler is given the ParserError, so it can decide per error -- for example skip stray separators but stop on anything else. Define the given where the parser is defined, or in the context's companion object.

In the handler, ctx works as in the parser's actions: assigning a field changes the context the parser goes on with.

import halotukozak.alpaca.*

val BrainLexer = lexer:
  case ">" => Token["next"]
  case "<" => Token["prev"]
  case "\\+" => Token["inc"]
  case "-" => Token["dec"]
  case "\\." => Token["print"]
  case "," => Token["read"]
  case "\\[" => Token["jumpForward"]
  case "\\]" => Token["jumpBack"]
  case "." => Token.Ignored
  case "\n" => Token.Ignored

enum BrainAST:
  case Root(ops: List[BrainAST])
  case While(ops: List[BrainAST])
  case Next, Prev, Inc, Dec, Print, Read
import halotukozak.alpaca.*

object BrainParser extends Parser:
  val root: Rule[BrainAST] = rule:
    case Operation.List(stmts) => BrainAST.Root(stmts)

  val While: Rule[BrainAST] = rule:
    case (BrainLexer.jumpForward(_), Operation.List(stmts), BrainLexer.jumpBack(_)) =>
      BrainAST.While(stmts)

  val Operation: Rule[BrainAST] = rule(
    { case BrainLexer.next(_) => BrainAST.Next },
    { case BrainLexer.prev(_) => BrainAST.Prev },
    { case BrainLexer.inc(_) => BrainAST.Inc },
    { case BrainLexer.dec(_) => BrainAST.Dec },
    { case BrainLexer.print(_) => BrainAST.Print },
    { case BrainLexer.read(_) => BrainAST.Read },
    { case While(whl) => whl },
  )
class Memory(
  val cells: Array[Int] = new Array(256),
  var pointer: Int = 0,
)

extension (ast: BrainAST)
  def eval(mem: Memory): Unit = ast match
    case BrainAST.Root(ops)  => ops.foreach(_.eval(mem))
    case BrainAST.Next       => mem.pointer = (mem.pointer + 1) & 0xff
    case BrainAST.Prev       => mem.pointer = (mem.pointer - 1) & 0xff
    case BrainAST.Inc        => mem.cells(mem.pointer) = (mem.cells(mem.pointer) + 1) & 0xff
    case BrainAST.Dec        => mem.cells(mem.pointer) = (mem.cells(mem.pointer) - 1) & 0xff
    case BrainAST.Print      => print(mem.cells(mem.pointer).toChar)
    case BrainAST.Read       => mem.cells(mem.pointer) = scala.io.StdIn.readChar() & 0xff
    case BrainAST.While(ops) => while mem.cells(mem.pointer) != 0 do ops.foreach(_.eval(mem))
val lexemes = BrainLexer.tokenize("++[>+<-]").getOrThrow
val parsed = BrainParser.parse(lexemes)
// parsed: Result[ParserCtx.Empty, BrainAST, BrainLexer.ParserError]
case class BudgetCtx(skipsLeft: Int = 1) extends ParserCtx

given ErrorHandling[BudgetCtx] = ErrorHandling.forParser: _ =>
  if ctx.skipsLeft == 0 then ErrorHandling.Strategy.Stop
  else
    ctx.skipsLeft -= 1
    ErrorHandling.Strategy.SkipOne

object BudgetParser extends Parser[BudgetCtx]:
  val root: Rule[Int] = rule:
    case BrainLexer.inc.List(incs) => incs.size

BudgetParser.parse(BrainLexer.tokenize("+>+<+").getOrThrow) match
  case Result.Failure(ctx, recovered, errors) =>
    println(ctx.skipsLeft)                             // 0
    println(recovered)                                 // None: the second skip was refused
    println(errors.flatMap(_.unexpected).map(_.text))  // List(>, <)
  case Result.Success(_, _) => ()

Conflict Resolution

Ambiguous grammars produce compile-time errors. The BrainFuck grammar has no conflicts (all tokens are unambiguous), but arithmetic grammars do. See Conflict Resolution for the full before/after DSL.

Quick example:

import halotukozak.alpaca.*

val CalcLexer = lexer:
  case "\\+" => Token["PLUS"]
  case x @ "[0-9]+" => Token["NUMBER"](x.toInt)
  case "\\s+" => Token.Ignored
object CalcParser extends Parser:
  val Expr: Rule[Double] = rule(
    "plus" { case (Expr(a), CalcLexer.PLUS(_), Expr(b)) => a + b },
    { case CalcLexer.NUMBER(n) => n.value.toDouble },
  )
  val root = rule:
    case Expr(e) => e

given Resolutions[CalcParser.type] = resolutions(
  production.plus.before(CalcLexer.PLUS),  // left-associative
)

Resolutions is a type class: declare the given next to the parser object (before or after it), or inside it. See Where resolutions Live for the details.

See Parser Context for custom state, Extractors for all pattern forms, and Debug Settings for compile-time debugging.

In this article

Generated with

made with ❤️ and coffee