Grammar compile¶

A policy starts as a line of text such as test(ping) ; act(ack) ("when ping happens, propose ack") and has to become a state machine the runtime can step through, one event at a time. This page is for contributors changing the policy language or its compiler. It follows the text through each stage: parsing into a tree, the star-height limit, a nondeterministic automaton (Thompson construction), a deterministic one (subset construction), and finally a statechart with states named s0, s1, ....

text or Python builders → Expr tree → star height ≤ 3 → Thompson NFA → subset DFA → statechart

After reading it you should be able to take test(ping) ; act(ack), draw the four NFA states, fill the subset table, and predict that dfa.step(start, "ping") lands on a state marked ack (tests/test_grammar.py::test_compile_and_step). The resulting machine puts its outputs (proposed actions) on states, not on transitions, so it is a Moore machine. Terms such as star height and statechart are in the glossary.

Why Lark is not the kernel¶

Two layers share the grammar/ package and they are easy to smash together.

Lark is text → Expr only. grammar.parse.parse loads policy.lark, runs an LALR parser with a contextual lexer, and a PolicyTransformer returns a frozen dataclass tree. That is the whole job. Lark does not know star-height. It does not build automata. It does not decide what an unknown event does at runtime.

After parsing, everything works on the tree. height.py measures the tree you wrote. dfa.py builds a Thompson \(\varepsilon\)-NFA and determinizes it. Complement is a Boolean operation on the event language: it does not add 1 to height, and it drops action markings. None of this depends on Lark; it would behave the same if the Expr came from Python builders and nobody called parse.

The cap of 3 comes from the companion math catalog (result 134), which claims that every regular language has generalized star height at most 3. In the wider literature, the generalized star-height problem is open; see Policies that stay simple for both statements. The code does not depend on that claim being true: it simply refuses policies whose written tree nests * more than Limits.max_star_height deep.

The split is deliberate. A general context-free control language would need a different certificate. Policies stay in this algebra so the star-height channel still means something. Wider DSL coverage (comments, quoted names, eps, real error positions) belongs on the front-end. Wider language coverage would be a different library.

You can see the split in the constructors. The DSL keyword is test(name). The Python constructor is evt(name), because pytest collects functions named test. Both produce Test. The kernel never sees which front-end you used.

from grounded_decision import act, evt, parse, seq, star_height

assert parse("test(ping) ; act(ack)") == seq(evt("ping"), act("ack"))
assert star_height(parse("not((test(a))*)")) == 1

The AST the kernel actually compiles¶

Frozen dataclasses in grammar.ast:

Node	Meaning
`Epsilon`	Empty sequence. DSL `eps`.
`Test(name)`	Consume one named event. DSL `test(...)`.
`Act(name)`	Terminal marking: propose this action. Not a letter.
`Seq(parts)`	Sequence. DSL `;`. At least one part.
`Union(parts)`	Choice. DSL `\\|`. At least one part.
`Star(inner)`	Kleene star. DSL postfix `*`.
`Complement(inner)`	Boolean complement of the event language. DSL `not(...)`.

alphabet(expr) is the set of test names. Act contributes nothing. That is the Moore invariant: actions live on states, tests are the input alphabet. If you ever find yourself adding ack to the alphabet because the policy contains act(ack), you have broken the kernel.

Helpers seq, union, star, evt, act, complement fold single-child Seq/Union so seq(evt("a")) is just Test("a").

Full EBNF (`policy.lark`)¶

The file next to parse.py is the source of truth for the text language. It is packaged as a resource (files("grounded_decision.grammar") / "policy.lark") and loaded at parser construction. Tests assert the resource contains ?start: union.

// Policy DSL. LALR grammar consumed by grounded_decision.grammar.parse.
// This is text → Expr only. Star-height, NFA, and DFA are the kernel, not Lark.

?start: union

union: seq ("|" seq)*
seq: starred (";" starred)*
starred: atom STAR*

atom: "test" "(" name ")"   -> test
    | "act" "(" name ")"    -> act
    | "not" "(" union ")"   -> complement
    | "eps"                 -> epsilon
    | "(" union ")"         -> parens

name: NAME
    | ESCAPED_STRING

STAR: "*"
NAME: /[A-Za-z_][A-Za-z0-9_]*/

COMMENT: /#[^\n]*/

%import common.ESCAPED_STRING
%import common.WS
%ignore WS
%ignore COMMENT

Read it as a precedence ladder, lowest to highest:

Union — A | B | C becomes Union((A, B, C)) if there are two or more alternatives. A lone seq is not wrapped.
Sequence — A ; B ; C becomes Seq((A, B, C)). Same folding.
Star — atom STAR*, so test(a)** is Star(Star(Test("a"))). Height is the nesting depth of those stars, not the number of * tokens on the page in some other grouping.
Atoms — test, act, not(...), eps, parenthesized union.

Names. Unquoted names match [A-Za-z_][A-Za-z0-9_]*. Quoted names are Lark ESCAPED_STRING (double quotes, Python-style escapes). The transformer runs ast.literal_eval on the token, so test("low-risk") and test("a b") become Test("low-risk") and Test("a b"). Hyphens and spaces are why quotes exist; they are illegal in NAME.

Epsilon. eps is a keyword atom, not a name. test(eps) is a test whose event is the string eps. Bare eps is Epsilon().

Comments. # to end of line, including a comment-only line. They are %ignored, same as whitespace. A file that is only comments is empty after ignore, and parse rejects empty input before Lark runs:

if not source or not source.strip():
    raise ParseError("empty policy")

Parser construction. LALR, contextual lexer, transformer attached, maybe_placeholders=False, propagate_positions=True, cache=False. Positions are how ParseError prints line N col M plus Lark's context snippet. UnexpectedInput is wrapped; you never see a raw Lark exception from parse.

The transformer is small on purpose. union / seq fold length-1. starred wraps once per extra STAR token. ESCAPED_STRING is the only token that is interpreted rather than passed through as text.

Illegal input is an error with a location¶

Every character must belong to a token. A stray character is a ParseError with line, column, the expected tokens (sorted, as the literal symbols) and a caret under the problem:

>>> parse("test(a) $ act(b)")
ParseError: line 1 col 9: unexpected '$'; expected one of: ')', '*', ';', '|'
test(a) $ act(b)
        ^

tests/test_grammar.py::test_parse_rejects_garbage_the_old_tokenizer_skipped pins this. Do not replace Lark with a regex tokenizer that skips characters it does not recognise: a skipped character silently turns one policy into a different one. (The project once had such a tokenizer; the changelog records the fix.)

Empty and whitespace-only strings are a dedicated error ("empty policy"), not a Lark unexpected-token at column 1 of nothing.

Star-height is on the tree you wrote¶

Epsilon, Test, Act          →  0
Seq, Union                  →  max of children
Complement                  →  height of inner     (does not add 1)
Star                        →  1 + height of inner

check_star_height raises StarHeightError if that number exceeds Limits.max_star_height (default 3). compile_expr and Module.from_expr both go through the gate. A fourth nested star is rejected at compile, not at decide.

The kernel does not rewrite an arbitrary regular language down to height 3. ((((test(a))*)*)*)* is height 4 and fails even though the language is \(\{a\}^*\), which has height 1. The limit is a check on the expression you ship, not a minimisation pass. See Policies that stay simple.

workflow_liveness ships a legal height-1 loop:

(test(submit) ; (test(approve) ; act(provision) | test(reject) ; act(close)))*

Thompson construction, node by node¶

_compile_nfa(expr, nfa) returns (start, accept) of a fragment with a unique accept state. All fragments are glued with \(\varepsilon\)-edges (letter is None in the NFA). The NFA is one shared _NFA: a list of dict[str | None, set[int]], a parallel actions list, a start index, and an accept set (filled after the walk).

nfa.add_state(action=None) appends an empty outgoing map and an action slot. nfa.link(src, letter, dst) adds dst to the set for that letter (or \(\varepsilon\)).

NFA size is capped by Limits.max_nfa_states after the walk, before subset construction.

`Epsilon`¶

flowchart LR
    s((s)) -->|ε| t((t))

Two fresh states, one \(\varepsilon\)-edge. Language: \(\{\varepsilon\}\).

`Test(name)`¶

flowchart LR
    s((s)) -->|name| t((t))

Two fresh states, one labeled edge. This is the only construct that introduces an alphabet letter. Language: \(\{\texttt{name}\}\).

`Act(name)`¶

flowchart LR
    s((s)) -->|ε| t((t*))

Two fresh states, one \(\varepsilon\)-edge, and actions[t] = name. The accept state of the fragment is marked. There is no letter. After determinization, a DFA state whose subset contains t will propose name.

This is the whole Moore encoding. If actions were letters, the environment would have to "send" ack for the machine to fire ack. They are not. The policy consumes ping and marks ack.

`Seq(parts)`¶

Compile the first part to \((s, p)\). For each subsequent part, compile to \((a, b)\) and \(\varepsilon\)-link \(p \rightarrow a\), then set \(p \leftarrow b\). Return \((s, p)\).

flowchart LR
    Astart((A.s)) --> Aacc((A.t))
    Aacc -->|ε| Bstart((B.s))
    Bstart --> Bacc((B.t))

For two parts this is A ; B. For more, the unique accept of each fragment is glued to the start of the next. There is no extra wrapper state around the whole sequence.

`Union(parts)`¶

Fresh start \(s\), fresh accept \(t\). For each part, compile to \((a, b)\), link \(s \xrightarrow{\varepsilon} a\) and \(b \xrightarrow{\varepsilon} t\).

flowchart LR
    s((s)) -->|ε| As((A.s))
    s -->|ε| Bs((B.s))
    As --> At((A.t))
    Bs --> Bt((B.t))
    At -->|ε| t((t))
    Bt -->|ε| t

Standard Thompson choice. The unique-accept invariant is why the extra \(t\) exists: each part has its own accept, and they must join.

`Star(inner)`¶

Fresh start \(s\), fresh accept \(t\). Compile inner to \((a, b)\). Four \(\varepsilon\)-edges:

\(s \rightarrow a\) — enter the body
\(s \rightarrow t\) — skip (zero times)
\(b \rightarrow a\) — loop
\(b \rightarrow t\) — exit

flowchart LR
    s((s)) -->|ε| a((inner.s))
    s -->|ε| t((t))
    a --> b((inner.t))
    b -->|ε| a
    b -->|ε| t

This is the construction in _compile_nfa, not a "plus" and not a skip-only star. Zero or more copies of the inner language.

`Complement(inner)`¶

Complement is not a local Thompson gadget. The inner expression is compiled all the way to a DFA (compile_expr(inner, limits), under the caller's Limits), then embedded back into the current NFA by _nfa_from_complemented_dfa.

Copy every DFA state into the NFA with add_state() — no action argument, so markings are dropped.
Fresh fragment start \(s\) and accept \(t\).
\(\varepsilon\) from \(s\) to the copied DFA start.
For each DFA letter, copy the deterministic transition as a labeled NFA edge.
For each copied DFA state that is not accepting, \(\varepsilon\) to \(t\).

Flipping accepting bits is how complement is implemented: the fragment accept \(t\) is reachable exactly from the rejecting DFA states (plus \(\varepsilon\)-closure). That is a language operation on the event alphabet. Action markings on the inner DFA are discarded because "the complement of a machine with outputs" is not something this compiler defines. If you needed the complement of a control language and still wanted actions, you would mark them outside not(...).

The recursive compile_expr(inner, limits) re-checks star height and the size caps under the same Limits as the outer policy (tests/test_grammar.py::test_complement_respects_caller_limits), and builds a DFA that already treated missing letters as self-loops. Those self-loops are copied, so the complement sees a total function on the inner alphabet.

Subset construction¶

After _compile_nfa returns, nfa.start and nfa.accept = {accept} are set. Letters are tuple(sorted(alphabet(expr))) — deterministic column order.

\(\varepsilon\)-closure is a DFS from a seed set along letter is None edges.

Subset construction:

Start subset = \(\varepsilon\text{-close}(\{\texttt{start}\})\), id 0.
Queue of unprocessed subsets.
For each subset \(S\) and each letter \(\ell\), let \(N = \bigcup_{v \in S} \delta(v, \ell)\), then \(S' = \varepsilon\text{-close}(N)\) if \(N\) is nonempty, else \(\emptyset\).
Assign \(S'\) an id if new; enqueue it. Cap: Limits.max_dfa_states.
Record trans_map[id(S)][ℓ] = id(S').

A DFA row is then filled in letter order. If a letter is missing from trans_map (should not happen when the alphabet is nonempty, because the loop visits every letter), the fallback is "stay" when there are no letters, otherwise _sink_id (the empty subset if it exists).

A second pass replaces any negative sentinel with a self-loop. The empty subset, if it was reached, is the DFA's dead state: every letter loops on it, and nothing after it can ever be accepted. DFA.dead records its id (None if the policy never reaches it). It stays in the DFA, because complement needs it, but dfa_to_statechart leaves it out of the chart (below).

Action of a DFA state. Collect the distinct nfa.actions[v] for \(v\) in the subset that are not None, sorted. No marking: the DFA state has no action. One marking: that is its action. Two or more: the policy is ambiguous, because one event (or the start) can lead to two different actions, and compile_expr raises CompileError naming the event, the state and the actions. For example, test(eligible) ; (act(approve) | act(deny)) raises:

Policy is ambiguous: after event 'eligible' (state s1) it could propose 'approve' or 'deny'; give each action its own event, for example test(ok) ; act(approve) | test(bad) ; act(deny).

The message says at the start instead of after event ... when the start state itself is ambiguous, and act(a) ; act(b) after one event is caught the same way. Write each action after its own event instead: test(eligible) ; act(approve) | test(ineligible) ; act(decline). The check is skipped when compiling the operand of not(...), because complement drops actions anyway (below).

Accepting. The DFA state is accepting if the subset meets nfa.accept or carries an action marking. The or is why act(ack) is visible as a control state even if you only look at accepting. dfa_to_statechart uses the action first anyway.

DFA.step(state, name) looks the name up in the alphabet. If the name is not a letter, it returns state unchanged. If it is a letter, it follows trans. So:

alphabet letter: deterministic row
any other string: self-loop at the DFA layer

The statechart compiled from the DFA only has transitions for alphabet letters, and none into the dead state. Statechart.step on an unknown name, or on a letter the current state does not continue with, returns None, and Module.decide stays and sets proposed_action = None with the reason event '…' is not handled in state '…'; nothing proposed.

DFA → statechart¶

dfa_to_statechart(name, dfa) in statechart/machine.py:

One chart state per DFA state except the dead state, named s{i} (s0, s1, …; the numbers are the DFA's, so the dead state's number is simply missing).
s{dfa.start} is initial (always s0, because subset construction numbers the start subset 0).
If the DFA state has an action: verdict=ACT, that action.
Else if it is accepting: verdict=ABSTAIN, no action.
Else: verdict=None, no action.
Priority is 2 (even) on states that propose an action and on final states (no outgoing transition in the chart), and 1 (odd) on every other state. Under the max-parity rule the solver uses (the largest priority seen infinitely often decides), the progress check then passes exactly when, from the start, the policy can keep reaching action states or reach a final state. (test(ping))* fails it. Payoff is 0 everywhere. To set priorities, payoffs or environment-owned states yourself, build a Statechart by hand; Games and solvers explains what the check can and cannot detect.
One transition per alphabet letter whose target is not the dead state: s{i} -letter-> s{trans[i][j]}. Transition action/payoff/priority stay at defaults (None / 0 / 0). The proposed action at decide-time comes from trans.action or chart.action_of(new_state), so the state marking is what fires.

Module.from_expr is exactly: check via compile_expr, then this function, then Module(...) which validates and solves the game.

Editing a policy renumbers its states

State names come from the order subset construction discovers subsets, and letters are visited in sorted order. Adding a branch can shift every name. test(b) ; act(x) compiles to s1 = x; test(a) ; act(y) | test(b) ; act(x) compiles to s1 = y, s2 = x. A state saved under the first policy would silently mean something else under the second. Services must store a policy fingerprint next to each saved state and refuse mismatches; see State and policy versions.

Worked example: `test(ping) ; act(ack)`¶

This is the whole pipeline on the string the tests use.

Parse¶

test(ping) ; act(ack)

test(ping) → Test("ping")
act(ack) → Act("ack")
; → Seq((Test("ping"), Act("ack")))

Star-height 0. Alphabet {ping}, sorted as ("ping",).

Thompson NFA¶

Test("ping") allocates states 0, 1:

0 --ping--> 1

Act("ack") allocates states 2, 3 with actions[3] = "ack":

2 --ε--> 3*

Seq \(\varepsilon\)-links the accept of the first fragment to the start of the second: 1 --ε--> 2. Fragment (start, accept) = (0, 3).

NFA states:
  0  --ping-->  {1}          action None     ← start
  1  --ε----->  {2}          action None
  2  --ε----->  {3}          action None
  3  (no edges)              action "ack"    ← unique accept

\(\varepsilon\)-close(\(\{0\}\)) \(= \{0\}\) (no \(\varepsilon\) out of the start). \(\varepsilon\)-close(\(\{1\}\)) \(= \{1,2,3\}\).

Subset DFA¶

Start subset \(S_0 = \{0\}\), DFA state 0.

Letter ping from \(S_0\): move to \(\{1\}\), close to \(\{1,2,3\}\). New subset \(S_1\), DFA state 1.

Letter ping from \(S_1\): none of 1, 2, 3 has a ping edge. Move set empty → empty subset \(S_2\), DFA state 2.

Letter ping from \(S_2\): empty stays empty. Self-loop on 2. State 2 is the dead state (dfa.dead == 2).

Actions and accepting:

DFA	NFA subset	action	accepting	`ping`
0	\(\{0\}\)	`None`	no	1
1	\(\{1,2,3\}\)	`"ack"` (state 3)	yes (accept 3 and marking)	2
2	\(\emptyset\)	`None`	no	2

DFA:
  0 --ping--> 1 --ping--> 2 --ping--> 2
              *
            action ack

dfa.step(0, "ping") is 1, dfa.action_at(1) is "ack". dfa.step(0, "other") is 0: "other" is not in the alphabet.

Statechart¶

s0  initial, verdict None,  action None,  priority 1
s1  verdict ACT,            action ack,   priority 2

s0 -ping-> s1

The dead state 2 is left out, and with it the arrows s1 -ping-> s2 and s2 -ping-> s2. s1 has no outgoing arrow, so it is final.

Module.from_expr("pingack", parse("test(ping) ; act(ack)")) then compiles a game with a _final self-loop on s1 and solves it: the only play is s0, s1, s1, …, the largest priority seen forever is 2, so the progress check passes. decide(Event("ping"), well_corroborated_evidence()) steps s0 → s1 and, if every evidence check passes, returns verdict=act, action=ack.

A second ping without reset() is not handled in s1: the entity stays in s1, nothing is proposed, and the record is abstain with reason "event 'ping' is not handled in state 's1'; nothing proposed". The reason "no action marked on current state" is reserved for moving into a state that proposes nothing, as workflow_liveness does after test(submit) and before act(provision).

What this page is not¶

It is not a tutorial on context-free grammars, and Lark plays no part in the star-height limit. The check is star_height(expr) <= 3 on the tree, plus an automaton small enough to fit under Limits. If you need a different text language, change policy.lark and the transformer, and keep the Thompson / subset / complement-via-DFA kernel intact.

Grammar compile¶

Why Lark is not the kernel¶

The AST the kernel actually compiles¶

Full EBNF (policy.lark)¶

Illegal input is an error with a location¶

Star-height is on the tree you wrote¶

Thompson construction, node by node¶

Epsilon¶

Test(name)¶

Act(name)¶

Seq(parts)¶

Union(parts)¶

Star(inner)¶

Complement(inner)¶