135 GrammarTile
135 : GrammarTile
- Author: Plawan Rath
- Description: Byte-level pushdown-automaton coprocessor with a baked JSON grammar
- GitHub repository
- Open in 3D viewer
- Clock: 50000000 Hz
hidden: true title: "GrammarTile — byte-PDA coprocessor"
How it works
GrammarTile is a small synthesizable accelerator that implements the inner per-byte kernel of a byte-level NFA + bounded pushdown automaton.
A host streams candidate byte sequences in over SPI. For each one it can:
- Load the chip with a starting PDA state (
LOAD_STATE). - Stream the candidate bytes one at a time (
ADVANCE). - Read back a single accept/reject bit (
QUERY_ACCEPT). - (Optionally) checkpoint and restore the active PDA state (
CHECKPOINT,RESTORE) so a single starting state can be tested against many candidate sequences without reloading.
Internally the chip classifies each input byte into one of 29 character
classes via a small combinational encoder, advances a 64-bit one-hot
bit-parallel Glushkov NFA, pushes or pops a 16-deep × 4-bit context stack as
the edge action requires, and recomputes the accept signal as
nfa_accept & stack_empty.
The full block diagram and pin assignments live in
architecture.md. The grammar that V1 bakes into the NFA
transition matrix is documented in grammar-v1.md.
How to test
The chip exposes two host interfaces:
-
SPI mode (
mode_sel = 0, default): standard mode-3 SPI onui_in[3:0] = {SCK, MOSI, CS_N, mode_sel}. Command set:Opcode Name Payload (MOSI) Reply (MISO) 0x00RESETnone none 0x01LOAD_STATE17 bytes (8 NFA + 1 sp + 8 stack) none 0x02ADVANCE1 byte input character none (status on uo[1])0x03QUERY_ACCEPT1 dummy byte 1 byte: {6'b0,err,acc}0x04CHECKPOINTnone none 0x05RESTOREnone none -
Parallel-byte fast path (
mode_sel = 1): drive a byte onuio[7:0]and pulseui_in[4](par_strobe) for one clock to advance. Intended for bench/FPGA-emulation use where you have a dedicated 8-bit harness instead of RP2040 SPI.
Status outputs are continuously visible:
uo_out[1]—accept(combinational):nfa_accept & stack_empty.uo_out[2]—ready: 1 when the engine is idle and can accept the next command.uo_out[3]—error: latched on stack overflow/underflow or invalid-byte.uo_out[7:4]— bottom 4 bits of the NFA state vector (silicon-bring-up visibility).
A self-checking cocotb test runs in CI on every push (.github/workflows/test.yaml)
and exercises a JSON corpus.
External hardware
- Tiny Tapeout demo board (RP2040 → SPI on
ui_in[3:0],uo_out[0]MISO). - Optional: 8-bit DIP switch + button on
uio[7:0]andui_in[4]for manual byte streaming inmode_sel=1.
IO
| # | Input | Output | Bidirectional |
|---|---|---|---|
| 0 | SPI SCK | SPI MISO (status byte readback) | parallel byte-in[0] / QSPI IO0 (future) |
| 1 | SPI MOSI | accept (combinational, low-latency) | parallel byte-in[1] / QSPI IO1 (future) |
| 2 | SPI CS_N (active low) | ready (engine idle, ok to issue next command) | parallel byte-in[2] / QSPI IO2 (future) |
| 3 | mode_sel (0=SPI, 1=parallel byte-in fast path) | error (stack overflow / underflow / invalid byte) | parallel byte-in[3] / QSPI IO3 (future) |
| 4 | par_strobe (parallel byte-in latch, mode_sel=1) | dbg NFA state[0] | parallel byte-in[4] / QSPI SCK (future) |
| 5 | reserved | dbg NFA state[1] | parallel byte-in[5] / QSPI CS_N (future) |
| 6 | reserved | dbg NFA state[2] | parallel byte-in[6] / reserved |
| 7 | reserved | dbg NFA state[3] | parallel byte-in[7] / reserved |