Contextual Lexing
This recipe makes BrainFuck> point at its own mistakes. The lexer tracks bracket depth and source positions, the parser keeps a registry of defined functions, and a call to an undefined function is reported with the line and column where it appears.
What you'll learn: how lexer context, the lexemes it produces, and parser context work together. Each piece has a reference page, linked as we go.
The Lexer
The lexer context counts open parentheses and tracks line and column (see Lexer Context for custom contexts and the built-in tracking fields):
import halotukozak.alpaca.*
case class BrainLexContext(
brackets: Int = 0,
line: Line = Line.Start,
column: Column = Column.Start,
) extends LexerCtx
val BrainLexer = lexer[BrainLexContext]:
case "\\+" => Token["inc"]
case "-" => Token["dec"]
case name @ "[A-Za-z]+" => Token["functionName"](name)
case "\\(" =>
ctx.brackets += 1
Token["functionOpen"]
case "\\)" =>
require(ctx.brackets > 0, "Mismatched brackets")
ctx.brackets -= 1
Token["functionClose"]
case "!" => Token["functionCall"]
case "\\s+" => Token.Ignored
brackets changes only where a rule body assigns it. line and column advance on their own after every match, and each lexeme records where its token starts.
The Parser
The parser context collects defined function names and the errors found so far (see Parser Context). The position of an error comes from the lexeme the rule binds, not from the parser context (see Lexeme Bindings):
import halotukozak.alpaca.*
case class BrainLexContext(
brackets: Int = 0,
line: Line = Line.Start,
column: Column = Column.Start,
) extends LexerCtx
val BrainLexer = lexer[BrainLexContext]:
case "\\+" => Token["inc"]
case "-" => Token["dec"]
case name @ "[A-Za-z]+" => Token["functionName"](name)
case "\\(" =>
ctx.brackets += 1
Token["functionOpen"]
case "\\)" =>
require(ctx.brackets > 0, "Mismatched brackets")
ctx.brackets -= 1
Token["functionClose"]
case "!" => Token["functionCall"]
case "\\s+" => Token.Ignored
import halotukozak.alpaca.*
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,
errors: List[String] = Nil,
) extends ParserCtx
object BrainParser extends Parser[BrainParserCtx]:
val root: Rule[BrainAST] = rule:
case Operation.List(ops) => BrainAST.Root(ops)
val Operation: Rule[BrainAST] = rule(
{ case BrainLexer.inc(_) => BrainAST.Inc },
{ case BrainLexer.dec(_) => BrainAST.Dec },
{ case FunctionDef(fdef) => fdef },
{ case FunctionCall(call) => call },
)
val FunctionDef: Rule[BrainAST] = rule:
case (BrainLexer.functionName(name), BrainLexer.functionOpen(_),
Operation.List(ops), BrainLexer.functionClose(_)) =>
if ctx.functions(name.value) then
ctx.errors :+= s"${name.line}:${name.column}: function ${name.value} is already defined"
ctx.functions += name.value
BrainAST.FunctionDef(name.value, ops)
val FunctionCall: Rule[BrainAST] = rule:
case (BrainLexer.functionName(name), BrainLexer.functionCall(_)) =>
if !ctx.functions.contains(name.value) then
ctx.errors :+= s"${name.line}:${name.column}: function ${name.value} is not defined"
BrainAST.FunctionCall(name.value)
Collecting errors instead of throwing lets one run report all of them. The parser reports syntax errors in its Result.Failure on its own; errors is only for the checks the rules make. Each :+= and += is rewritten into a copy of the context, so the reductions that follow see the new value.
Running It
Check the final lexer context once the whole input is consumed, then read the errors from the final parser context:
import halotukozak.alpaca.*
case class BrainLexContext(
brackets: Int = 0,
line: Line = Line.Start,
column: Column = Column.Start,
) extends LexerCtx
val BrainLexer = lexer[BrainLexContext]:
case "\\+" => Token["inc"]
case "-" => Token["dec"]
case name @ "[A-Za-z]+" => Token["functionName"](name)
case "\\(" =>
ctx.brackets += 1
Token["functionOpen"]
case "\\)" =>
require(ctx.brackets > 0, "Mismatched brackets")
ctx.brackets -= 1
Token["functionClose"]
case "!" => Token["functionCall"]
case "\\s+" => Token.Ignored
import halotukozak.alpaca.*
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,
errors: List[String] = Nil,
) extends ParserCtx
object BrainParser extends Parser[BrainParserCtx]:
val root: Rule[BrainAST] = rule:
case Operation.List(ops) => BrainAST.Root(ops)
val Operation: Rule[BrainAST] = rule(
{ case BrainLexer.inc(_) => BrainAST.Inc },
{ case BrainLexer.dec(_) => BrainAST.Dec },
{ case FunctionDef(fdef) => fdef },
{ case FunctionCall(call) => call },
)
val FunctionDef: Rule[BrainAST] = rule:
case (BrainLexer.functionName(name), BrainLexer.functionOpen(_),
Operation.List(ops), BrainLexer.functionClose(_)) =>
if ctx.functions(name.value) then
ctx.errors :+= s"${name.line}:${name.column}: function ${name.value} is already defined"
ctx.functions += name.value
BrainAST.FunctionDef(name.value, ops)
val FunctionCall: Rule[BrainAST] = rule:
case (BrainLexer.functionName(name), BrainLexer.functionCall(_)) =>
if !ctx.functions.contains(name.value) then
ctx.errors :+= s"${name.line}:${name.column}: function ${name.value} is not defined"
BrainAST.FunctionCall(name.value)
val program =
"""foo(++)
|foo!
| bar!""".stripMargin
val lexed = BrainLexer.tokenize(program)
require(lexed.ctx.brackets == 0, "Mismatched brackets")
val parsed = BrainParser.parse(lexed.getOrThrow)
parsed.ctx.errors.foreach(println)
// 3:3: function bar is not defined
Going Further
- Add your own tracked field, such as an indentation level: Lexer Context.
- Skip input no pattern matches instead of stopping: Lexer Error Recovery.
- Recover from syntax errors in the parser: Error Recovery.
- Follow the data from input to parse result: Between Stages.