Alpaca

A type-safe lexer and parser library for Scala 3, featuring compile-time validation and a pattern-matching DSL.

Features

• Type-safe lexer and parser — catch errors at compile time with Scala 3's type system
• Pattern-matching DSL — define lexers and parsers using intuitive case syntax
• Compile-time validation — regex patterns and grammar rules are checked during compilation
• Macro-based code generation — Scala 3 macros generate efficient tokenizers and parse tables
• Context-aware — lexical and parsing contexts with type-safe state management
• LALR(1) parsing — automatic parse table generation with conflict detection
• Cross-platform — runs on the JVM, Scala.js, and Scala Native

Installation

Mill

Add Alpaca as a dependency in your build.mill:

//| mill-version: 1.3.1
//| mill-jvm-version: 21

import mill._
import mill.scalalib._

object myproject extends ScalaModule {
  def scalaVersion = "3.9.0"

  def scalacOptions = Seq("-Yretain-trees")

  def mvnDeps = Seq(
    mvn"com.halotukozak::alpaca::1.0.0-RC5"
  )
}

SBT

Add Alpaca to your build.sbt:

libraryDependencies += "com.halotukozak" %% "alpaca" % "1.0.0-RC5"

Make sure you're using Scala 3.9.0 or later and enable the required compiler flag (Alpaca 0.3.2 and earlier also need -experimental):

scalaVersion := "3.9.0"
scalacOptions ++= Seq("-Yretain-trees")

Scala CLI

Use Alpaca directly in your Scala CLI scripts:

//> using scala "3.9.0"
//> using dep "com.halotukozak::alpaca:1.0.0-RC5"
//> using options "-Yretain-trees"

import halotukozak.alpaca.*

// Your code here

Scala.js and Scala Native

Alpaca is also published for Scala.js 1 and Scala Native 0.5 (built with Scala.js 1.22.0 and Scala Native 0.5.12). The same dependency works there, with %%% in sbt:

libraryDependencies += "com.halotukozak" %%% "alpaca" % "1.0.0-RC5"

In Mill, the mvn"com.halotukozak::alpaca::1.0.0-RC5" line above picks the right artifact in a ScalaJSModule or ScalaNativeModule. In Scala CLI, add //> using platform js (or native) and write the dependency with two colons before the version: //> using dep "com.halotukozak::alpaca::1.0.0-RC5". The -Yretain-trees flag is needed on every platform.

Quick Start

Creating a Lexer

Define a lexer using pattern matching with regex patterns:

import halotukozak.alpaca.*

val MyLexer = lexer:
  case num @ "[0-9]+" => Token["NUM"](num.toDouble)
  case "\\+" => Token["PLUS"]
  case "-" => Token["MINUS"]
  case "\\*" => Token["STAR"]
  case "/" => Token["SLASH"]
  case "\\(" => Token["LP"]
  case "\\)" => Token["RP"]
  case "\\s+" => Token.Ignored

Creating a Parser

Define a parser by extending the Parser class and defining grammar rules:

import halotukozak.alpaca.*

object MyParser extends Parser:
  val root: Rule[Double] = rule:
    case Expr(e) => e

  val Expr: Rule[Double] = rule(
    { case (Expr(l), MyLexer.PLUS(_), Term(r)) => l + r },
    { case (Expr(l), MyLexer.MINUS(_), Term(r)) => l - r },
    { case Term(t) => t },
  )

  val Term: Rule[Double] = rule(
    { case (Term(l), MyLexer.STAR(_), Factor(r)) => l * r },
    { case (Term(l), MyLexer.SLASH(_), Factor(r)) => l / r },
    { case Factor(f) => f },
  )

  val Factor: Rule[Double] = rule(
    { case MyLexer.NUM(n) => n.value },
    { case (MyLexer.LP(_), Expr(e), MyLexer.RP(_)) => e },
  )

Parsing Input

import halotukozak.alpaca.*

val input = "2 + 3 * 4"
val lexemes = MyLexer.tokenize(input).getOrThrow
val result = MyParser.parse(lexemes).getOrThrow
println(result) // 14.0

What's Next

The full documentation is at alpaca.halotukozak.com.

• Getting Started — build a BrainFuck interpreter step by step
• Lexer — the full lexer DSL reference
• Parser — grammar rules, EBNF operators, conflict resolution
• Tooling — debug output and the IntelliJ plugin
• Cookbook — complete examples: an expression evaluator, a JSON parser, contextual lexing
• Theory — formal foundations: finite automata, LR parsing, parse tables

Benchmarks

Runtime benchmarks are not run automatically in CI on push or pull requests. They can be triggered manually:

• GitHub Actions — go to Actions > Runtime Benchmark > Run workflow and select the branch.

• Locally — run all benchmarks (JMH + Python) from the repository root:

  ./mill benchmarks.runAll
  

  Or run individual JMH suites directly:

  ./mill benchmarks.alpaca.runJmh
  ./mill benchmarks.fastparse.runJmh
  

  Results are written to benchmarks/outputs/.

Building from Source

Prerequisites

• JDK 21 or later
• Mill 1.1.10 or later

Build Commands

The build defines separate jvm, js, and native modules; commands below target jvm (swap in js/native to build for those platforms):

# Compile the project
./mill jvm.compile

# Run tests
./mill jvm.test

# Generate documentation
./mill jvm.docJar

# Run test coverage
./mill jvm.scoverage.htmlReport

Thesis

This project was developed as a Bachelor's Thesis. The full text is available in the thesis.pdf file. The LaTeX source files are on the thesis branch. The thesis is written in Polish and does not represent the current state of the project.

Contributing

Contributions are welcome. Please feel free to submit a Pull Request.

internal is part of the binary contract

The halotukozak.alpaca.internal package is not user API, but it is part of the binary contract. The lexer and parser macros expand into code that lives in users' binaries and calls internal symbols directly:

• the Lexer constructor (the class every generated lexer extends), DefinedToken/IgnoredToken, TokenInfo and Printable.apply;
• Production, NEL and the grammar symbols, ParseAction, the ParseTable encoding, ActionTable, RevertedArray, the ParserExtractors actions and the Parser constructor;
• every @publicInBinary member.

A MiMa or TASTy-MiMa report on an internal class is therefore a real break for already-compiled users, not a false positive. Don't filter it out. Changing these symbols incompatibly needs a major version.

Authors

Created by halotukozak and Corvette653

---

Made with ❤️ and coffee