🥮 mooncakes.io

    moonearley

    Runtime token CFG parsing with ambiguity-preserving packed forests and bounded queries.

    earley
    cfg
    parser
    ambiguity
    sppf
    Download zip
    Version
    0.1.1
    License
    MIT
    Repository
    Last updated
    4 days ago
    Downloads
    41

    No dependencies

    #MoonEarley

    MoonBit 运行时 CFG 解析基础库：接收调用者提供的 token，支持左递归、可空规则和歧义， 将推导保存在可查询的共享 packed forest 中，而不是提前选择一棵树。

    模块：LuoYunze-nuist/moonearley@0.1.1。许可证：MIT。

    #安装和最小调用

    环境要求：MoonBit 编译器 moonc >= 0.10.16 和 Python 3。当前验证使用官方 moon 0.1.20261028 / moonc v0.10.18+6c83a7f62，支持 JS、wasm、wasm-gc 和 native。 Native 另需本机 C 编译器、链接器和平台 SDK；Windows 本地未具备时由 Linux CI 验证。

    moon add LuoYunze-nuist/moonearley@0.1.1

    在消费者 moon.pkg 中加入：

    import { "LuoYunze-nuist/moonearley" }

    let grammar = @moonearley.parse_grammar("S -> 'name' '=' 'number';").unwrap()
    let report = @moonearley.parse(grammar, [
      @moonearley.token("name", "answer", 0, 6),
      @moonearley.token("=", "=", 7, 8),
      @moonearley.token("number", "42", 9, 11),
    ]).unwrap()
    assert_true(report.accepted())
    assert_eq(report.forest().count().unwrap(), @moonearley.Finite(1))

    parse 返回 Result[Report, Problem]。语法不接受是 Ok(report) 且 accepted=false； 非法输入或预算耗尽是 Err。accepted prefix 仍可有 expected terminals。 请避免在生产应用直接 unwrap 不可信输入。

    #数据模型和 API

    • Symbol::{Terminal,Nonterminal}：名称精确、区分两种 namespace。
    • Rule {lhs,rhs,label}：label 必须唯一；重复 rhs 不同 label 是不同推导。
    • Grammar::new 复制输入；analyze、sets、lint 提供可空/可生成/可达、FIRST/FOLLOW、递归诊断。
    • Token {kind,text,start,end}：只按 kind 匹配；text 原样保留。start/end 是调用者源坐标， 非负单调不重叠；空跨度及间隔合法。
    • Report：accepted、expected、furthest、statistics、diagnostic、context、forest。
    • Forest：symbol/intermediate/token 节点，families 是有序 AND 子节点的 OR 备选。 root/node/rule_at/token_at 均只读快照；可变数组查询返回副本。
    • count(cap?,work_limit?)：Finite(n)、AtLeast(cap) 或 Infinite。 恰好等于 cap 保持 Finite；只对生产性且从根可达的循环判 Infinite。
    • extract_trees(limits?)：Intermediate 被展开为真实 AST 的有序 children；检查 truncated() 和 status 的 tree/depth/work/cycle 标志，不能把部分结果当全集。 对循环仅给 cycle-free 有限代表，不枚举任意循环次数的有限树。
    • reachable_nodes / productive_nodes / ambiguity_nodes / span queries / to_dot。 ambiguity 是至少两个生产性 families 的局部歧义，可以位于 Intermediate。
    • Session::new、push、push_all、fork、report：保留已完成 chart，支持 append-only 前缀解析，失败事务回滚。为所有权安全深拷贝，不宣称常数时间增量。

    forest/tree 区间是半开 token-index 区间，与 Token 的源坐标不同。 完整可见 API：pkg.generated.mbti；算法约束：docs/architecture/design.md。

    #文法前端

    @start E;
E -> ['add'] E '+' E | ['number'] 'n' | ['empty'] ;

    start directive 可省略（第一条 lhs 为 start）；空分支为 epsilon。 裸非终结符是 ASCII identifier，任意名称可双引号；terminal 和 label 单引号。 支持 # 行注释和引号/Unicode 转义。错误 offset 是零基 UTF-16 单位。 默认 65536 source units、4096 rules、16384 RHS symbols；export_grammar 保留规则顺序与标签。 不是 Lark grammar syntax，不会把裸 epsilon 自动当成空分支。

    #三个可运行下游场景

    moon run examples/expression --target js --deny-warn
moon run examples/language_service --target js --deny-warn
moon run examples/grammar_qa --target js --deny-warn

    1. DSL 解释器：1+2*3 外部 token → 两种完整推导 → 下游求值输出 7 和 9， 由解释器决定优先级；库没有丢弃替代解释。
    2. 语言服务：声明前缀 → retained chart 和 expected = → fork 试输错误 kind 得到源 offset 11 的诊断；原会话继续至接受，旧 report 不变化。
    3. 文法 QA：包含可空 unit cycle 及不可达 production 的 CFG → lint、Infinite 推导计数、带 cycle_truncated 的有限见证及可视化 AND/OR DOT 图。

    #验证

    python scripts/check_toolchain.py
moon info && moon fmt
moon fmt --check
moon check --target wasm-gc --deny-warn
moon build --target wasm-gc --deny-warn
moon test --target wasm-gc --deny-warn
python scripts/audit_sources.py --require-production 1500
python scripts/audit_history.py --minimum-nonempty 20

    本地 Windows / moon 0.1.20261028 / moonc v0.10.18+6c83a7f62： 102 个命名测试在 wasm-gc、wasm、JS 各全通过；三个示例各目标运行。 独立 span-oracle 992 识别用例；固定 Lark SHA 的 252 接受性与推导数对照在 JS、wasm-gc 一致。 不是性能比较。Native 本机缺少完整 C 工具链与 SDK，不宣称本地已执行；CI 含 native job。 CI 各后端及 Lark 对照任务都会在检查前强制验证编译器版本下限。 当前版本测试结果与 CI 链接见仓库 Actions，实质规模和方法见 docs/verification.md。

    外部对照（先检出固定上游，不依赖 PyPI 浮动版本）：

    git clone https://github.com/lark-parser/lark ../lark-reference
git -C ../lark-reference checkout 9a4fb9c7458e8155636773a3cded0016d52516da
python scripts/reference_check.py --lark-source ../lark-reference --target js

    #功能边界和来源

    参考 MIT Python Lark 的 Earley/packed forest 核心并独立 MoonBit 重写，不是完整 Lark 移植。 没有 lexer/dynamic lexing、ANTLR/LR codegen、错误恢复、semantic-action 引擎、Leo 优化， 不处理任意位置编辑，也不声称优于确定性解析器的性能。输入规模、文字长度及进程资源 需要调用者控制，详见 SECURITY.md。

    完整上游版权、参考与独立测试来源：THIRD_PARTY_NOTICES.md、licenses/Lark-MIT.txt。 AI 辅助范围：AI_USAGE.md。查重记录：docs/competition/duplicate-check.md。 有限结论：在已记录检索范围内未发现成熟直接替代，不声称绝对不存在。

    DerivationCount

    source
    pub(all) enum DerivationCount {
      Finite(Int)
      AtLeast(Int)
      Infinite
    } derive(Eq, 
    Debug    )

    Counts distinguish exact equality to the cap from actual saturation. Infinite means arbitrarily many finite derivation trees, not an infinite tree.

    DerivationCount::equal

    source

    DerivationCount::not_equal

    source
    fn DerivationCount::not_equal(x : DerivationCount, y : DerivationCount) -> Bool

    DerivationCount::to_repr

    source

    Engine

    source
    type Engine

    Family

    source
    pub(all) struct Family {
      rule : Int
      children : Array[Int]
    } derive(Eq, 
    Debug    )

    A family is an AND-edge; a node's families are OR-alternatives.

    Family::equal

    source
    fn Family::equal(Family, Family) -> Bool

    Family::not_equal

    source
    fn Family::not_equal(x : Family, y : Family) -> Bool

    Family::to_repr

    source

    FirstSet

    source
    pub struct FirstSet {
      kinds : Array[String]
      empty : Bool
    } derive(Eq, 
    Debug    )

    FIRST has terminal kinds plus a separate epsilon bit, never a magic token.

    FirstSet::equal

    source
    fn FirstSet::equal(FirstSet, FirstSet) -> Bool

    FirstSet::is_nullable

    source
    fn FirstSet::is_nullable(self : FirstSet) -> Bool

    FirstSet::not_equal

    source
    fn FirstSet::not_equal(x : FirstSet, y : FirstSet) -> Bool

    FirstSet::terminals

    source
    fn FirstSet::terminals(self : FirstSet) -> Array[String]

    FirstSet::to_repr

    source

    FollowSet

    source
    pub struct FollowSet {
      kinds : Array[String]
      eof : Bool
    } derive(Eq, 
    Debug    )

    FOLLOW distinguishes end of input from every possible caller token kind.

    FollowSet::equal

    source
    fn FollowSet::equal(FollowSet, FollowSet) -> Bool

    FollowSet::includes_eof

    source
    fn FollowSet::includes_eof(self : FollowSet) -> Bool

    FollowSet::not_equal

    source
    fn FollowSet::not_equal(x : FollowSet, y : FollowSet) -> Bool

    FollowSet::terminals

    source
    fn FollowSet::terminals(self : FollowSet) -> Array[String]

    FollowSet::to_repr

    source

    Forest

    source
    pub struct Forest {
      nodes : Array[Node]
      tokens : Array[Token]
      rules : Array[Rule]
      root : Int?
    }

    Forest IDs are local to this snapshot; spans here are token-index intervals.

    Forest::ambiguity_nodes

    source
    fn Forest::ambiguity_nodes(self : Forest, reachable_only? : Bool, work_limit? : Int) -> Result[Array[Int], Problem]

    Local ambiguity means at least two productive packed families at a node. Parents with only one family are not listed merely because a child is ambiguous. By default consider only viable root-reachable nodes; false includes disconnected productive nodes. Token leaves are never ambiguous.

    Forest::count

    source
    fn Forest::count(self : Forest, cap? : Int, work_limit? : Int) -> Result[DerivationCount, Problem]

    Counts all labeled derivations represented by the accepted root. A rejected forest or nonproductive root has zero, not Infinite. Both limits must be positive Int values; arithmetic remains safe even at Int's maximum cap. Work charges node visits, family checks and child edges across every pass; exhausted budgets are errors, never partial counts.

    Forest::extract_trees

    source
    fn Forest::extract_trees(self : Forest, limits? : TreeLimits) -> Result[TreeExtraction, Problem]

    Forest::node

    source
    fn Forest::node(self : Forest, id : Int) -> Result[NodeInfo, Problem]

    Forest::node_count

    source
    fn Forest::node_count(self : Forest) -> Int

    Forest::nodes_at_span

    source
    fn Forest::nodes_at_span(self : Forest, start : Int, end : Int) -> Result[Array[Int], Problem]

    Exact half-open token interval, not the tokens' caller-defined source offsets. Zero-width intervals are valid, including at the end of input.

    Forest::nodes_of_kind

    source
    fn Forest::nodes_of_kind(self : Forest, kind : NodeKind) -> Array[Int]

    All matching IDs in allocation order; namespaces remain distinct.

    Forest::productive_nodes

    source
    fn Forest::productive_nodes(self : Forest, work_limit? : Int) -> Result[Array[Int], Problem]

    Finite-proof productivity over every node, independent of root reachability.

    Forest::reachable_from

    source
    fn Forest::reachable_from(self : Forest, id : Int, work_limit? : Int) -> Result[Array[Int], Problem]

    Useful for chart fragments and rejected reports that have no accepted root.

    Forest::reachable_nodes

    source
    fn Forest::reachable_nodes(self : Forest, work_limit? : Int) -> Result[Array[Int], Problem]

    Follow all stored families from the accepted root, cycle-safely. A rejected forest has no root and therefore no root-reachable IDs.

    Forest::root

    source
    fn Forest::root(self : Forest) -> Int?

    Forest::rule_at

    source
    fn Forest::rule_at(self : Forest, id : Int) -> Result[Rule, Problem]

    Forest::rule_count

    source
    fn Forest::rule_count(self : Forest) -> Int

    Forest::symbol_nodes

    source
    fn Forest::symbol_nodes(self : Forest, name : String) -> Array[Int]

    Search every stored symbol node, including disconnected chart material.

    Forest::symbol_nodes_at

    source
    fn Forest::symbol_nodes_at(self : Forest, name : String, start : Int, end : Int) -> Result[Array[Int], Problem]

    Forest::to_dot

    source
    fn Forest::to_dot(self : Forest, reachable_only? : Bool, work_limit? : Int) -> Result[String, Problem]

    Deterministic DOT encodes AND/OR structure with a separate box per family. Ordered child edges keep their positions, including repeated child IDs. Empty families remain visible. Cycles are exported without tree expansion. Default output covers all structural root-reachable families; false includes the entire chart snapshot. Work also charges every escaped label character.

    Forest::token_at

    source
    fn Forest::token_at(self : Forest, id : Int) -> Result[Token, Problem]

    Forest::token_count

    source
    fn Forest::token_count(self : Forest) -> Int

    Total tokens includes unmatched input; forest leaves contain only scanned tokens.

    FrontendLimits

    source
    pub(all) struct FrontendLimits {
      max_chars : Int
      max_rules : Int
      max_symbols : Int
    } derive(Eq, 
    Debug    )

    Budgets count UTF-16 source units, productions, and total RHS symbols. All limits must be positive and at most ten million. Comments count as source.

    FrontendLimits::equal

    source

    FrontendLimits::not_equal

    source
    fn FrontendLimits::not_equal(x : FrontendLimits, y : FrontendLimits) -> Bool

    FrontendLimits::to_repr

    source

    FrontendLimits::validate

    source
    fn FrontendLimits::validate(self : FrontendLimits) -> Result[Unit, Problem]

    Grammar

    source
    pub struct Grammar {
      start : String
      rules : Array[Rule]
    }

    A validated, owned snapshot of a token-kind context-free grammar. Fields are private outside this package; the parser can read them directly.

    Grammar::analyze

    source
    fn Grammar::analyze(self : Grammar) -> GrammarAnalysis

    Compute independent finite fixed points and per-expansion facts once.

    Grammar::first

    source
    fn Grammar::first(self : Grammar, name : String) -> Result[FirstSet, Problem]

    Convenience one-shot query. Reuse sets() when querying many symbols.

    Grammar::first_sequence

    source
    fn Grammar::first_sequence(self : Grammar, symbols : Array[Symbol]) -> Result[FirstSet, Problem]

    Grammar::follow

    source
    fn Grammar::follow(self : Grammar, name : String) -> Result[FollowSet, Problem]

    Grammar::lint

    source
    fn Grammar::lint(self : Grammar) -> Array[GrammarDiagnostic]

    Return warnings sorted by original rule index, then declared kind order. Reachability is syntactic; productivity is checked per RHS, not per LHS. Cycles are reported once per component per kind, including disconnected components. Earley parsing supports these grammars: nothing is rejected.

    Grammar::new

    source
    fn Grammar::new(start : String, rules : Array[Rule]) -> Result[Grammar, Problem]

    Construct a grammar without retaining any caller-owned arrays. Empty expansions and repeated expansions with distinct labels are legal. Names are exact strings: whitespace is meaningful, not silently trimmed.

    Grammar::nonterminals

    source
    fn Grammar::nonterminals(self : Grammar) -> Array[String]

    All defined nonterminals, including disconnected and nonproductive ones.

    Grammar::nullable

    source
    fn Grammar::nullable(self : Grammar) -> Array[String]

    Grammar::productive

    source
    fn Grammar::productive(self : Grammar) -> Array[String]

    Grammar::reachable

    source
    fn Grammar::reachable(self : Grammar) -> Array[String]

    Grammar::rule_count

    source
    fn Grammar::rule_count(self : Grammar) -> Int

    Includes epsilon rules and distinct labels sharing an expansion.

    Grammar::rules

    source
    fn Grammar::rules(self : Grammar) -> Array[Rule]

    Return an independent outer array AND independent expansion arrays. Rule ordering is retained because rule indices identify parser alternatives.

    Grammar::sets

    source
    fn Grammar::sets(self : Grammar) -> GrammarSets

    FOLLOW obeys the equations for ALL rules, not only reachable productions. Only the distinguished start is initially seeded with end of input.

    Grammar::start

    source
    fn Grammar::start(self : Grammar) -> String

    The distinguished nonterminal, unchanged from construction.

    Grammar::terminals

    source
    fn Grammar::terminals(self : Grammar) -> Array[String]

    Distinct token kinds, sorted independently of production ordering.

    GrammarAnalysis

    source
    pub struct GrammarAnalysis {
      nullable_names : Map[String, Bool]
      productive_names : Map[String, Bool]
      reachable_names : Map[String, Bool]
      nullable_rules : Array[Bool]
      productive_rules : Array[Bool]
      reachable_rules : Array[Bool]
    }

    Reusable fixed-point results. No mutable collections escape this value.

    GrammarAnalysis::is_nullable

    source
    fn GrammarAnalysis::is_nullable(self : GrammarAnalysis, name : String) -> Bool

    Unknown names return false rather than introducing implicit definitions.

    GrammarAnalysis::is_productive

    source
    fn GrammarAnalysis::is_productive(self : GrammarAnalysis, name : String) -> Bool

    GrammarAnalysis::is_reachable

    source
    fn GrammarAnalysis::is_reachable(self : GrammarAnalysis, name : String) -> Bool

    GrammarAnalysis::nullable

    source
    fn GrammarAnalysis::nullable(self : GrammarAnalysis) -> Array[String]

    GrammarAnalysis::productive

    source
    fn GrammarAnalysis::productive(self : GrammarAnalysis) -> Array[String]

    GrammarAnalysis::reachable

    source
    fn GrammarAnalysis::reachable(self : GrammarAnalysis) -> Array[String]

    GrammarAnalysis::rule_is_nullable

    source
    fn GrammarAnalysis::rule_is_nullable(self : GrammarAnalysis, index : Int) -> Bool?

    Safe index queries distinguish a negative/out-of-range index from false.

    GrammarAnalysis::rule_is_productive

    source
    fn GrammarAnalysis::rule_is_productive(self : GrammarAnalysis, index : Int) -> Bool?

    GrammarAnalysis::rule_is_reachable

    source
    fn GrammarAnalysis::rule_is_reachable(self : GrammarAnalysis, index : Int) -> Bool?

    GrammarDiagnostic

    source
    pub(all) struct GrammarDiagnostic {
      kind : GrammarLintKind
      rule_index : Int
      rule_label : String
      related_rules : Array[Int]
      nonterminals : Array[String]
      message : String
    } derive(Eq, 
    Debug    )

    Indices refer to the original grammar order. For a cyclic component, related_rules lists every production contributing an internal graph edge; rule_index/label identify its earliest production. Names are lexical. For a duplicate, related_rules contains the first matching expansion.

    GrammarDiagnostic::equal

    source

    GrammarDiagnostic::not_equal

    source
    fn GrammarDiagnostic::not_equal(x : GrammarDiagnostic, y : GrammarDiagnostic) -> Bool

    GrammarDiagnostic::to_repr

    source

    GrammarLintKind

    source
    pub(all) enum GrammarLintKind {
      UnreachableRule
      NonproductiveRule
      DuplicateExpansion
      NullableCycle
      LeftRecursion
    } derive(Eq, 
    Debug    )

    Advisory findings never change grammar validity or parser acceptance.

    GrammarLintKind::equal

    source

    GrammarLintKind::not_equal

    source
    fn GrammarLintKind::not_equal(x : GrammarLintKind, y : GrammarLintKind) -> Bool

    GrammarLintKind::to_repr

    source

    GrammarSets

    source
    pub struct GrammarSets {
      names : Array[String]
      nullable : Map[String, Bool]
      first : Map[String, Map[String, Bool]]
      follow : Map[String, Map[String, Bool]]
      end_of_input : Map[String, Bool]
    }

    Immutable-by-API, reusable set tables for all defined nonterminals.

    GrammarSets::first

    source
    fn GrammarSets::first(self : GrammarSets, name : String) -> Result[FirstSet, Problem]

    Reject unknown names rather than returning a misleading empty FIRST row.

    GrammarSets::first_sequence

    source
    fn GrammarSets::first_sequence(self : GrammarSets, symbols : Array[Symbol]) -> Result[FirstSet, Problem]

    A sequence may contain new nonempty terminal kinds, but every nonterminal must be defined. Validate even the suffix behind a nonnullable prefix.

    GrammarSets::follow

    source
    fn GrammarSets::follow(self : GrammarSets, name : String) -> Result[FollowSet, Problem]

    GrammarSets::nonterminals

    source
    fn GrammarSets::nonterminals(self : GrammarSets) -> Array[String]

    Limits

    source
    pub(all) struct Limits {
      tokens : Int
      items : Int
      nodes : Int
      families : Int
      work : Int
    } derive(Eq, 
    Debug    )

    All counters are cumulative for one parse/session, not reset per token.

    Limits::equal

    source
    fn Limits::equal(Limits, Limits) -> Bool

    Limits::not_equal

    source
    fn Limits::not_equal(x : Limits, y : Limits) -> Bool

    Limits::to_repr

    source

    Limits::validate

    source
    fn Limits::validate(self : Limits) -> Result[Unit, Problem]

    Bound configuration arithmetic before any allocation or chart work.

    Node

    source
    type Node

    NodeInfo

    source
    pub(all) struct NodeInfo {
      kind : NodeKind
      start : Int
      end : Int
      alternatives : Array[Family]
    } derive(Eq, 
    Debug    )

    Read-only snapshot view. Mutating its arrays cannot mutate the forest.

    NodeInfo::equal

    source
    fn NodeInfo::equal(NodeInfo, NodeInfo) -> Bool

    NodeInfo::not_equal

    source
    fn NodeInfo::not_equal(x : NodeInfo, y : NodeInfo) -> Bool

    NodeInfo::to_repr

    source

    NodeKind

    source
    pub(all) enum NodeKind {
      TokenLeaf(Int)
      SymbolNode(String)
      Intermediate(Int, Int)
    } derive(Eq, 
    Debug    )

    Intermediate nodes encode one prefix of a production, not an AST node.

    NodeKind::equal

    source
    fn NodeKind::equal(NodeKind, NodeKind) -> Bool

    NodeKind::not_equal

    source
    fn NodeKind::not_equal(x : NodeKind, y : NodeKind) -> Bool

    NodeKind::to_repr

    source

    ParseDiagnostic

    source
    pub(all) struct ParseDiagnostic {
      token_index : Int
      char_start : Int
      char_end : Int
      actual_kind : String?
      expected_kinds : Array[String]
      at_eof : Bool
    } derive(Eq, 
    Debug    )

    Structured rejection diagnostics; token indices and character offsets are distinct.

    ParseDiagnostic::equal

    source

    ParseDiagnostic::not_equal

    source
    fn ParseDiagnostic::not_equal(x : ParseDiagnostic, y : ParseDiagnostic) -> Bool

    ParseDiagnostic::to_repr

    source

    Problem

    source
    pub(all) enum Problem {
      InvalidGrammar(String)
      InvalidToken(Int, String)
      Limit(String, Int)
      InvalidNode(Int)
      InvalidLimit(String)
      Syntax(Int, String)
    } derive(Eq, 
    Debug    )

    An input or budget failure. Results never silently report budget exhaustion as rejection.

    Problem::equal

    source
    fn Problem::equal(Problem, Problem) -> Bool

    Problem::not_equal

    source
    fn Problem::not_equal(x : Problem, y : Problem) -> Bool

    Problem::to_repr

    source

    Report

    source
    pub struct Report {
      forest : Forest
      expected : Array[String]
      furthest : Int
      stats : Statistics
    }

    A parse report is an immutable snapshot, including when a session later advances.

    Report::accepted

    source
    fn Report::accepted(self : Report) -> Bool

    Report::context

    source
    fn Report::context(self : Report, radius : Int) -> Result[Array[Token], Problem]

    A bounded token window around the failure, or the end for an accepted report.

    Report::diagnostic

    source
    fn Report::diagnostic(self : Report) -> ParseDiagnostic?

    Accepted prefixes have no failure, even when further tokens could be accepted.

    Report::expected

    source
    fn Report::expected(self : Report) -> Array[String]

    Report::forest

    source
    fn Report::forest(self : Report) -> Forest

    Report::furthest

    source
    fn Report::furthest(self : Report) -> Int

    Furthest chart with at least one state, in token indices rather than source offsets.

    Report::statistics

    source
    fn Report::statistics(self : Report) -> Statistics

    Rule

    source
    pub(all) struct Rule {
      lhs : String
      rhs : Array[Symbol]
      label : String
    } derive(Eq, 
    Debug    )

    Rule labels identify alternatives independently of their symbol sequences.

    Rule::equal

    source
    fn Rule::equal(Rule, Rule) -> Bool

    Rule::not_equal

    source
    fn Rule::not_equal(x : Rule, y : Rule) -> Bool

    Rule::to_repr

    source

    RuleTree

    source
    pub(all) struct RuleTree {
      label : String
      rule : Int
      span : TreeSpan
      children : Array[Tree]
    } derive(Eq, 
    Debug    )

    A real grammar production. Intermediate forest prefixes never become this node.

    RuleTree::equal

    source
    fn RuleTree::equal(RuleTree, RuleTree) -> Bool

    RuleTree::not_equal

    source
    fn RuleTree::not_equal(x : RuleTree, y : RuleTree) -> Bool

    RuleTree::to_repr

    source

    Session

    source
    pub struct Session {
      engines : Array[Engine]
    }

    A session owns a persistent chart; each successful push only adds a new chart.

    Session::fork

    source
    fn Session::fork(self : Session) -> Session

    Snapshots and forked sessions have no shared mutable chart or family arrays.

    Session::new

    source
    fn Session::new(grammar : Grammar, limits? : Limits) -> Result[Session, Problem]

    Opening a session can fail during nullable closure before the first token.

    Session::push

    source
    fn Session::push(self : Session, token : Token) -> Result[Report, Problem]

    Validate and append one token atomically; failed appends leave statistics unchanged.

    Session::push_all

    source
    fn Session::push_all(self : Session, tokens : Array[Token]) -> Result[Report, Problem]

    Append a batch atomically. Input can start at any later character offset.

    Session::report

    source
    fn Session::report(self : Session) -> Report

    Reports copy the packed forest and remain valid after future appends.

    Statistics

    source
    pub(all) struct Statistics {
      tokens : Int
      items : Int
      nodes : Int
      families : Int
      work : Int
    } derive(Eq, 
    Debug    )

    Stable counters describe allocated states, not derivation counts.

    Statistics::equal

    source
    fn Statistics::equal(Statistics, Statistics) -> Bool

    Statistics::not_equal

    source
    fn Statistics::not_equal(x : Statistics, y : Statistics) -> Bool

    Statistics::to_repr

    source

    Symbol

    source
    pub(all) enum Symbol {
      Terminal(String)
      Nonterminal(String)
    } derive(Eq, 
    Debug    )

    CFG symbols are names, never regular expressions or literal text matchers.

    Symbol::equal

    source
    fn Symbol::equal(Symbol, Symbol) -> Bool

    Symbol::not_equal

    source
    fn Symbol::not_equal(x : Symbol, y : Symbol) -> Bool

    Symbol::to_repr

    source

    Token

    source
    pub(all) struct Token {
      kind : String
      text : String
      start : Int
      end : Int
    } derive(Eq, 
    Debug    )

    Span units belong to the caller (typically UTF-16 or byte offsets).

    Token::equal

    source
    fn Token::equal(Token, Token) -> Bool

    Token::not_equal

    source
    fn Token::not_equal(x : Token, y : Token) -> Bool

    Token::to_repr

    source

    TokenTree

    source
    pub(all) struct TokenTree {
      token : Token
      span : TreeSpan
    } derive(Eq, 
    Debug    )

    The original immutable token plus its interval in the parser token sequence.

    TokenTree::equal

    source
    fn TokenTree::equal(TokenTree, TokenTree) -> Bool

    TokenTree::not_equal

    source
    fn TokenTree::not_equal(x : TokenTree, y : TokenTree) -> Bool

    TokenTree::to_repr

    source

    Tree

    source
    pub(all) enum Tree {
      RuleNode(RuleTree)
      TokenNode(TokenTree)
    } derive(Eq, 
    Debug    )

    A finite AST. Caller-constructed trees must be acyclic for traversal tools. Arrays are caller-owned; extraction reports expose independently copied trees.

    Tree::copy

    source
    fn Tree::copy(self : Tree) -> Tree

    Deep-copy every child array, including arrays shared by separate branches. The iterative rebuild never borrows caller arrays in the returned tree.

    Tree::depth

    source
    fn Tree::depth(self : Tree) -> Int

    Tree::equal

    source
    fn Tree::equal(Tree, Tree) -> Bool

    Tree::metrics

    source
    fn Tree::metrics(self : Tree) -> TreeMetrics

    Size counts rules AND tokens; epsilon has size/depth one. Root depth is one. Explicit traversal stacks also support deep caller-created finite trees.

    Tree::not_equal

    source
    fn Tree::not_equal(x : Tree, y : Tree) -> Bool

    Tree::rule_labels

    source
    fn Tree::rule_labels(self : Tree) -> Array[String]

    Production labels in left-to-right preorder, including repeated labels.

    Tree::size

    source
    fn Tree::size(self : Tree) -> Int

    Tree::span

    source
    fn Tree::span(self : Tree) -> TreeSpan

    Tree::to_repr

    source

    Tree::tokens

    source
    fn Tree::tokens(self : Tree) -> Array[Token]

    Leaves retain text, kind and caller source offsets; no retokenization occurs.

    TreeExtraction

    source
    pub struct TreeExtraction {
      trees : Array[Tree]
      status : TreeExtractionStatus
      work : Int
    }

    Owned results. Getters copy all mutable tree arrays, including shared children.

    TreeExtraction::status

    source

    TreeExtraction::tree_count

    source
    fn TreeExtraction::tree_count(self : TreeExtraction) -> Int

    TreeExtraction::trees

    source
    fn TreeExtraction::trees(self : TreeExtraction) -> Array[Tree]

    TreeExtraction::truncated

    source
    fn TreeExtraction::truncated(self : TreeExtraction) -> Bool

    TreeExtraction::work

    source
    fn TreeExtraction::work(self : TreeExtraction) -> Int

    Charged task steps, path comparisons, branch copies, child scheduling/merging.

    TreeExtractionStatus

    source
    pub(all) struct TreeExtractionStatus {
      tree_limit : Bool
      depth_limit : Bool
      work_limit : Bool
      cycle_truncated : Bool
    } derive(Eq, 
    Debug    )

    Flags are independent: a cyclic forest can still yield finite trees. A tree-limit flag means an additional complete tree was actually discovered. Cycle/depth flags mean branches were skipped, not that they lack derivations.

    TreeExtractionStatus::equal

    source

    TreeExtractionStatus::not_equal

    source

    TreeExtractionStatus::to_repr

    source

    TreeExtractionStatus::truncated

    source
    fn TreeExtractionStatus::truncated(self : TreeExtractionStatus) -> Bool

    TreeLimits

    source
    pub(all) struct TreeLimits {
      max_trees : Int
      max_depth : Int
      work_budget : Int
    } derive(Eq, 
    Debug    )

    Extraction budgets are independent of the parser's chart budgets. Depth counts AST rules/tokens, never Intermediate prefix nodes.

    TreeLimits::equal

    source
    fn TreeLimits::equal(TreeLimits, TreeLimits) -> Bool

    TreeLimits::not_equal

    source
    fn TreeLimits::not_equal(x : TreeLimits, y : TreeLimits) -> Bool

    TreeLimits::to_repr

    source

    TreeLimits::validate

    source
    fn TreeLimits::validate(self : TreeLimits) -> Result[Unit, Problem]

    A hard depth ceiling remains useful even though extraction itself is iterative.

    TreeMetrics

    source
    pub(all) struct TreeMetrics {
      size : Int
      depth : Int
      tokens : Int
    } derive(Eq, 
    Debug    )

    TreeMetrics::equal

    source
    fn TreeMetrics::equal(TreeMetrics, TreeMetrics) -> Bool

    TreeMetrics::not_equal

    source
    fn TreeMetrics::not_equal(x : TreeMetrics, y : TreeMetrics) -> Bool

    TreeMetrics::to_repr

    source

    TreeSpan

    source
    pub(all) struct TreeSpan {
      start : Int
      end : Int
    } derive(Eq, 
    Debug    )

    Half-open token-index interval, not the caller's Token.start/end units.

    TreeSpan::equal

    source
    fn TreeSpan::equal(TreeSpan, TreeSpan) -> Bool

    TreeSpan::not_equal

    source
    fn TreeSpan::not_equal(x : TreeSpan, y : TreeSpan) -> Bool

    TreeSpan::to_repr

    source

    default_frontend_limits

    source
    fn default_frontend_limits() -> FrontendLimits

    Defaults bound both lexer storage and the grammar passed to validation.

    default_limits

    source
    fn default_limits() -> Limits

    Conservative defaults for small/medium runtime grammars; not performance guarantees.

    default_tree_limits

    source
    fn default_tree_limits() -> TreeLimits

    export_grammar

    source
    fn export_grammar(grammar : Grammar) -> String

    Canonical human CFG: explicit start, one production per line, all labels explicit, every nonterminal double quoted, and a final newline. Rule and RHS order are preserved, not sorted: they identify parser alternatives. Exporting is read-only and returns the same string on every call for the same grammar. Import using parse_grammar with sufficient FrontendLimits for this output; export is not restricted to the importer's default budgets. No Lark claim.

    extract_trees

    source
    fn extract_trees(forest : Forest, limits? : TreeLimits) -> Result[TreeExtraction, Problem]

    Extract finite cycle-free derivations, not a promise to enumerate cyclic trees. Repeated IDs on one path skip only that branch and set cycle_truncated; other finite alternatives remain eligible, including productive unit/epsilon cycles. max_trees is inclusive: after filling it, search for one extra finite tree to determine truncation. Work/depth exhaustion is explicit even with zero trees. A rejected forest (no root) has an empty, complete result. Invalid limits or inconsistent internal forest references are Err; ordinary truncation is Ok.

    parse

    source
    fn parse(grammar : Grammar, tokens : Array[Token], limits? : Limits) -> Result[Report, Problem]

    Recognize and preserve all derivations. Rejection is Ok(report); failure is Err(problem).

    parse_grammar

    source
    fn parse_grammar(source : String, limits? : FrontendLimits) -> Result[Grammar, Problem]

    A small token-kind CFG language, not Lark syntax or a text-tokenizing lexer. Syntax: optional initial @start Name;, then Name -> ['label'] symbols | ;. Each alternative may have one label; an empty alternative means epsilon. Bare names match [A-Za-z_][A-Za-z0-9_]*; double quotes allow arbitrary names. Single quotes denote terminal kinds or bracketed labels. Both quotes accept escaped backslash/quotes, n/r/t and uXXXX (paired for supplementary Unicode). Space, tab, CR/LF and # line comments are ignored outside quoted strings. Default start is the first lhs. Missing labels get collision-free rule:N names. Syntax offsets are zero-based UTF-16 units, including the EOF offset. Lexical/syntax failures precede semantic validation; exhaustion is never rejection.

    token

    source
    fn token(kind : String, text : String, start : Int, end : Int) -> Token

    Snapshot a token, preventing accidental dependence on caller arrays.

    validate_tokens

    source
    fn validate_tokens(tokens : Array[Token]) -> Result[Unit, Problem]

    Validate monotonic nonoverlapping spans; zero-width tokens are permitted.

    Source Files

    Powered by MoonBit

    Site sourceReport issueModulesSkillsCLIBuild queueStatistics

    © 2026 mooncakes.io