Lexer

The Alpaca lexer transforms raw text into a stream of structured tokens. You define lexical rules as regex patterns paired with token constructors, and the macro generates a tokenizer at compile time.

import halotukozak.alpaca.*

Defining a Lexer

A lexer is defined with the lexer block. Each case branch maps a regex pattern to a token constructor. At each position the lexer takes the longest match; when several patterns match equally long text, the one declared first wins (see How a Token Is Chosen).

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

The result is a Lexer[LexerCtx.Default], the type to use when a lexer appears in your own signatures. It can tokenize input strings and provides typed accessors for each defined token (e.g., BrainLexer.inc).

This is the BrainFuck lexer from Getting Started, reduced to the eight standard commands; everything else is a comment, which the "." catch-all ignores. Later pages extend it with custom context (bracket counting) and error recovery.

How a Token Is Chosen

A lexer block looks like a Scala match, but it does not pick the first case that fits. At each position in the input:

1. every pattern is tried against the remaining input,
2. the pattern that matches the longest text wins (longest match, also called maximal munch),
3. only when several patterns match text of the same length does declaration order decide: the case declared first wins.

This is the rule used by flex, JFlex and ocamllex (which, like Alpaca, writes its rules in match-like syntax).

import halotukozak.alpaca.*

val MyLexer = lexer:
  case "=" => Token["ASSIGN"]
  case "==" => Token["EQ"]
  case "if" => Token["IF"]
  case id @ "[a-z]+" => Token["ID"](id)
  case "\\s+" => Token.Ignored

println(MyLexer.tokenize("== = if iffy").getOrThrow.map(_.name)) // List(EQ, ASSIGN, IF, ID)

"==" beats the earlier "=" because it is longer. if is matched equally long by IF and ID, so the earlier IF wins the tie. iffy is longer only for ID, so it stays a single identifier instead of splitting into if + fy.

In practice this means:

• Patterns that extend each other can go in any order. "=" and "==", or "[0-9]+" and "[0-9]+\\.[0-9]+", work either way round.
• Keywords go before the identifier pattern. That order only decides the exact tie. The other order is a compile-time error, because the keyword could never win (see Shadowed Patterns).
• Ignored patterns compete too. A comment pattern "//[^\n]*" beats a "/" operator wherever both match, because it is longer.

Longest match decides one token at a time, so it has some consequences that surprise people coming from match:

• It does not look at what comes next. With "-?[0-9]+" for numbers and "-" for minus, 1-2 lexes as 1 followed by -2, because -2 is longer than -. Handle the sign in the parser instead of in the number pattern.
• It never backtracks. With "a", "ab" and "bc", the input abc fails at c. The lexer commits to the longest ab and does not go back to try a + bc.
• A single pattern takes as much as it can. "/\\*.*\\*/" reads /* a */ x /* b */ as one comment. Exclude the closing delimiter from the body instead, since lazy quantifiers are not supported:

import halotukozak.alpaca.*

val MyLexer = lexer:
  case "/\\*([^*]|\\*+[^*/])*\\*+/" => Token.Ignored
  case id @ "[a-z]+" => Token["ID"](id)
  case "\\s+" => Token.Ignored

println(MyLexer.tokenize("/* a */ x /* b */").getOrThrow.map(_.name)) // List(ID)

Regular Expressions

Patterns use Java-style regex syntax and are validated at compile time by Alpaca's own regex library (a few Java constructs -- lookbehind, lazy and possessive quantifiers -- are not supported; see Invalid Regex). Backslashes must be doubled inside Scala string literals: "\\+" matches a literal +, and "\\d+" matches one or more digits.

import halotukozak.alpaca.*

val MyLexer = lexer:
  // Literals that are regex metacharacters need escaping
  case "\\+" => Token["inc"]         // literal +
  case "\\." => Token["print"]       // literal .
  case "\\[" => Token["jumpForward"] // literal [

  // Non-metacharacters need no escaping
  case ">" => Token["next"]          // literal >
  case "-" => Token["dec"]           // literal -
  case "," => Token["read"]          // literal ,

  // Character classes and quantifiers
  case "[0-9]+" => Token["NUM"]      // one or more digits
  case "[a-zA-Z_][a-zA-Z0-9_]*" => Token["ID"] // identifier
  case "\\s+" => Token.Ignored        // whitespace; `line` counts the newlines in it

An invalid regex (unmatched parentheses, bad quantifiers) produces a compile-time error, and so does a pattern that can match the empty string, like "a*": every token must consume at least one character. A pattern that can never win -- because an earlier one always matches the same text at least as long -- produces a compile-time shadowing error; see Shadowed Patterns.

Tokens

Tokens come in three forms.

Named Tokens

Token["NAME"] creates a token with a Unit value. The token name becomes both the lexeme's .name field and the accessor on the lexer object. To access the matched text, use lexeme.text.

import halotukozak.alpaca.*

val BrainLexer = lexer:
  case ">" => Token["next"]
  case "<" => Token["prev"]
  case "\\+" => Token["inc"]
  case "\\s+" => Token.Ignored

val lexemes = BrainLexer.tokenize("> < +").getOrThrow
// lexemes: next, prev, inc

Value-Bearing Tokens

Token["NAME"](value) attaches a computed value. Bind the matched text with @ and transform it:

import halotukozak.alpaca.*

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

val lexemes = BrainLexer.tokenize("foo!").getOrThrow
// lexemes: functionName("foo"), functionCall

The type system tracks the value type: BrainLexer.functionName has type Token["functionName", ..., String].

Ignored Tokens

Token.Ignored matches text but excludes it from the token stream. Use it for whitespace, comments, and anything syntactically irrelevant.

import halotukozak.alpaca.*

val BrainLexer = lexer:
  case "\\+" => Token["inc"]
  case "." => Token.Ignored   // any non-command character
  case "\n" => Token.Ignored  // newlines

val lexemes = BrainLexer.tokenize("+ hello +\n+").getOrThrow
// lexemes: inc, inc, inc (everything else is ignored)

Variable Binding

The @ syntax binds the matched text to a variable, giving you a String to transform before passing to the token constructor.

import halotukozak.alpaca.*

val MyLexer = lexer:
  case num @ "[0-9]+" => Token["NUM"](num.toInt)
  case name @ "[A-Za-z]+" => Token["functionName"](name)
  case "\\s+" => Token.Ignored

Without @, the rule body can't see the matched text; the lexeme still has it as lexeme.text.

Token Naming Rules

The Pipeline

1. You write Token["NAME"] or Token[variable.type] in the lexer definition
2. The string inside the type parameter becomes the token name
3. To access the token on the lexer object (e.g., in parser rules), Scala's standard name encoding applies
4. If the name is a Scala keyword or isn't a valid Scala identifier (like \\+ or (), use backticks: BrainLexer.`\\+`

Dynamic Token Names

When several patterns share the same structure, use alternation with variable.type to create one token per alternative:

import halotukozak.alpaca.*

val MyLexer = lexer:
  case keyword @ ("if" | "else" | "while") => Token[keyword.type]
  case op @ ("\\+" | "-" | "\\*") => Token[op.type]
  case id @ "[a-zA-Z_][a-zA-Z0-9_]*" => Token["ID"](id)
  case "\\s+" => Token.Ignored

// Each alternative becomes a separate token, named by its path:
// MyLexer.`if`, MyLexer.`else`, MyLexer.`while`, MyLexer.`\\+`, MyLexer.-, MyLexer.`\\*`

Keywords like if always need backticks. - is a valid Scala identifier and does not.

Tokenization

Call tokenize() on your lexer with an input string:

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
val lexed = BrainLexer.tokenize("++[>+<-].")
val lexemes = lexed.getOrThrow

The method returns a Result -- the same type parse returns (see Parsing Input):

• ctx -- the final lexer context after processing all input. With LexerCtx.Default, this includes column and line: the position after the last match.
• getOrThrow -- the lexemes: matched tokens with Token.Ignored entries removed. Each Lexeme carries the token name, extracted value, and a snapshot of context fields at match time.

If the input contains a character that matches no pattern, tokenize does not throw: it returns a Result.Failure listing LexerErrors, and getOrThrow throws them as a LexerException. An exception thrown by a rule body, such as a failed require, is different: it propagates out of tokenize. See Runtime Error Handling for how to handle the errors, or skip unmatched input instead of stopping.

Tokenizing Files with LazyReader

For large files, use LazyReader instead of loading the entire file into a String. It reads characters on demand from the underlying file:

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
import java.nio.file.Path

val reader = LazyReader.from(Path.of("program.bf"))
val lexemes =
  try BrainLexer.tokenize(reader).getOrThrow
  finally reader.close()

LazyReader.from(path) accepts an optional Charset parameter (defaults to UTF-8). It reads the file with java.nio.file, which Scala Native provides but Scala.js does not, so on Scala.js read the input into a String yourself. Always close the reader in a finally block (or use scala.util.Using.resource) so the file handle is released even if tokenization throws.

tokenize reads the file in chunks, so memory does not grow with the file size. Like the Reader it wraps, a LazyReader is consumed as it is read, so create a new one per run.

Token Value Types

The value type depends on how the token is defined:

The Lexeme Structure

Every non-ignored match produces a Lexeme. This is the one place that describes it; the other pages link here. A lexeme has:

• name -- the token name as a string literal type (e.g., "inc", "functionName")
• value -- the extracted value (Unit for Token["NAME"], or the computed type for Token["NAME"](expr))
• text -- the matched string, not the remaining input
• the lexer context's fields -- column and line with LexerCtx.Default, or your own fields with a custom context, read by name with their types

The context fields are a snapshot taken right after the rule body ran, with one exception: fields with a given Tracking (such as Line and Column) keep their values from before the match, even if the rule body assigned them, so line and column point at the start of the token. Snapshots are independent: later changes to the context don't reach lexemes already produced. Reading a field the context doesn't have (e.g., .indent with LexerCtx.Default) is a compile error.

import halotukozak.alpaca.*

val MyLexer = lexer:
  case num @ "[0-9]+" => Token["NUM"](num.toInt)
  case "\\s+" => Token.Ignored

val lexemes = MyLexer.tokenize("42 13").getOrThrow
lexemes(0).column    // 1: Int (where the token starts)
lexemes(1).column    // 4: Int
lexemes(0).line      // 1: Int
lexemes(0).text      // "42": String

Lexemes compare by value: two are equal when their name, value, text and context fields are. They print the same way, e.g. Lexeme(NUM, 42, "42", column = 1, line = 1).

Naming the Types

Every lexer has type members for its lexemes and errors, to use in your own signatures:

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
def describe(lexeme: BrainLexer.Lexeme): String =
  s"${lexeme.name} at ${lexeme.line}:${lexeme.column}"

def describe(error: BrainLexer.LexerError): String =
  s"${error.message} at ${error.line}:${error.column}"

val lexemes: List[BrainLexer.Lexeme] = BrainLexer.tokenize("+>").getOrThrow

The plain Lexeme, LexerError and ParserError types compile too, but they don't carry the context fields, so lexeme.line doesn't compile on them.