README
¶
racc — go-ruby-racc
A pure-Go (no cgo) reimplementation of the runtime at the heart of Ruby's
Racc — the table-driven LALR(1) parse engine
(Racc::Parser) that every racc-generated parser drives via include Racc::Parser. It is a faithful port of MRI 4.0.5's Ruby runtime core
(lib/racc/parser.rb: _racc_do_parse_rb / _racc_yyparse_rb / _racc_evalact
/ _racc_do_reduce), so that — given the same parse tables — it walks the
same shift/reduce/accept/error trajectory and returns the same result as
MRI, without any Ruby runtime.
This is the runtime only, not the racc generator tool. A racc-generated
parser file embeds a Racc_arg table constant plus generated _reduce_N action
methods and a next_token lexer; at parse time MRI's runtime interprets those
tables. This package reproduces that interpreter so racc-generated gem parsers can
run on go-embedded-ruby. It is a
standalone, reusable module — a sibling of
go-ruby-marshal,
go-ruby-regexp,
go-ruby-erb, and
go-ruby-pstore.
What it is — and isn't. The parse automaton — read the action table for the current state and lookahead, shift / reduce / accept / recover, drive the goto tables, run the error-recovery state machine — is fully deterministic and needs no interpreter, so it lives here as pure Go over a
Tablesvalue (the raccRacc_arg). The grammar-specific halves are the seams the host injects: the lexer (next_token), the reduce actions (_reduce_N), and the error handler (on_error). rbgo wires these to the user's Ruby parser; the tests wire small Go closures, so the whole suite is deterministic and Ruby-free.
How a generated parser's tables drive the engine
A racc-generated parser carries a Racc_arg array. Its 14 elements map
field-for-field onto Tables:
Racc_arg index |
Tables field |
role |
|---|---|---|
| 0–3 | ActionTable / ActionCheck / ActionDefault / ActionPointer |
compressed action table (shift / reduce / accept / error per state × lookahead) |
| 4–7 | GotoTable / GotoCheck / GotoDefault / GotoPointer |
compressed goto table (state after a reduction) |
| 8 | NtBase |
first nonterminal id (reduce_to − NtBase indexes the goto tables) |
| 9 | ReduceTable |
flat (len, reduce_to, method_id) triples per rule |
| 10 | TokenTable |
external token symbol → internal id (EOF ⇒ 0) |
| 11–12 | ShiftN / ReduceN |
the action-code band boundaries |
| 13 | UseResult |
whether reduce actions take the extra result argument |
nil cells in the pointer / value tables are encoded with the package sentinels
ptrNil / nilCell. The engine consumes this Tables value exactly as MRI's
runtime consumes Racc_arg, so transcribing a generated parser's constants (or
emitting them from a code generator) is all that is needed to run that grammar.
The seams
type Parser struct {
Tables *Tables
NextToken func() (sym any, val any) // the lexer (next_token); nil sym == EOF
Reduce func(methodID int, values []any, result any) any // the _reduce_N dispatch
OnError func(tok int, val any, valueStack []any) error // on_error; nil enters recovery
}
func (p *Parser) DoParse() (result any, err error) // do_parse
func (p *Parser) Yyparse(iter func(yield func(sym, val any))) (result any, err error) // yyparse(recv, mid)
func (p *Parser) Yyerror() // throw :racc_jump, 1 — from a Reduce action
func (p *Parser) Yyaccept() // throw :racc_jump, 2 — from a Reduce action
func (p *Parser) Yyerrok() // leave error-recovery mode
NextTokenis the lexer seam used byDoParse(MRI'snext_token). It returns[sym, val]; a nilsymis EOF (MRI's[false, false]). An unknown non-nil symbol maps to the error token (internal id 1).Reduceis the reduce-action seam (MRI's__send__(method_id, val, …), i.e. the generated_reduce_N). It receives the rule'smethod_idand the popped symbol values and returns the produced nonterminal's value.OnErroris the parse-error seam (MRI'son_error). It fires the first time an error action is taken; returningnilenters racc's error-recovery mode, returning an error aborts the parse with it. When unset, the engine raises a*ParseErrorwith MRI's exact message —parse error on value <inspect> (<tok>).
Yyparse swaps the pull lexer for an iterator seam: the iter closure is called
once and must yield(sym, val) per token, mirroring yyparse(recv, mid) where
recv.mid yields the tokens.
Usage
p := &racc.Parser{Tables: calcTables} // calcTables transcribes the grammar's Racc_arg
p.NextToken = lexer.Next // the host lexer
p.Reduce = func(methodID int, val []any, result any) any {
switch methodID { // the generated _reduce_N bodies
case 2: // exp: exp '+' exp
return val[0].(int) + val[2].(int)
case 5: // exp: NUMBER
return val[0]
// …
}
return result
}
result, err := p.DoParse()
MRI parse-trajectory parity
The headline guarantee is same tables ⇒ same parse. The differential oracle
(oracle_test.go) installs the calc grammar's Racc_arg into
MRI's own Racc::Parser (the Ruby core, forced via Racc_No_Extensions) and
into this engine, runs the identical token streams through both, and asserts the
reduce trajectory and the final result/error match byte-for-byte — including
operator-grouping decisions driven by racc's conflict resolution and the exact
default error-message text. A second grammar with an error rule exercises the
error-recovery path; building it caught a real divergence (MRI renders a character
terminal's token_to_str as the double-quoted "+", not '+').
Tests & coverage
Deterministic, ruby-free tests drive the engine over fixed parse tables (calc and a
statement grammar with error recovery) and hold coverage at 100% on their own,
so the qemu cross-arch and Windows lanes pass the gate. The MRI oracle runs on the
Linux/macOS lanes where ruby (≥ 4.0) is installed and skips itself on Windows /
when ruby is absent.
COVERPKG=$(go list ./... | paste -sd, -)
go test -race -coverpkg="$COVERPKG" -coverprofile=cover.out ./...
go tool cover -func=cover.out | tail -1 # 100.0%
CGO-free, gofmt + go vet clean, and green across the six 64-bit Go targets
(amd64, arm64, riscv64, loong64, ppc64le, s390x) and three OSes (Linux, macOS,
Windows).
What rbgo binds
rbgo (go-embedded-ruby) binds the three seams to the user's Ruby parser object: the
generated next_token method (the user's lexer) → NextToken; the generated
_reduce_N methods dispatched by method_id → Reduce; and the parser's
on_error (default or overridden) → OnError. The Racc_arg constant emitted by
racc into the parser becomes a Tables, and do_parse / yyparse map to
DoParse / Yyparse. That makes racc-generated gem parsers run on the pure-Go,
CGO-free runtime with no Ruby interpreter underneath.
License
BSD-3-Clause — see LICENSE. Copyright the go-ruby-racc/racc authors.
WebAssembly
Being pure Go (CGO=0), this library also compiles to WebAssembly — both
GOOS=js GOARCH=wasm (browser / Node.js) and GOOS=wasip1 GOARCH=wasm (WASI).
CI builds both targets on every push, alongside the six 64-bit native/qemu arches.
GOOS=js GOARCH=wasm go build ./... # browser / Node
GOOS=wasip1 GOARCH=wasm go build ./... # WASI (wasmtime, wasmer, wasmedge, …)
Documentation
¶
Overview ¶
Package racc is a pure-Go (CGO=0) port of MRI's Racc::Parser runtime — the table-driven LALR(1) parse engine that every racc-generated Ruby parser drives via `include Racc::Parser`.
This is the RUNTIME only, not the racc generator. A racc-generated parser file embeds a constant `Racc_arg` (the parse tables: action/goto/reduce tables, the token-value table, the shift/reduce counts, …) plus the generated reduce-action methods (`_reduce_N`) and a `next_token` lexer. At parse time, MRI's `_racc_do_parse_rb` / `_racc_yyparse_rb` interpret those tables, calling back into the lexer and the reduce actions. This package reproduces that interpreter byte-for-byte on the parse trajectory: given the same tables and the same token stream, it performs the same shift/reduce/accept/error sequence and returns the same result as MRI running its Ruby runtime core.
The engine is pure compute. The host (e.g. rbgo) injects three SEAMS that, in a generated parser, are the user's Ruby code:
- NextToken: the lexer (`next_token` / the iterator yielded by yyparse). It returns the next [tokenSymbol, value] pair; symbol == nil signals EOF, which MRI spells `[false, false]`.
- Reduce: the reduce-action dispatch (`__send__(method_id, val, vstack[, result])`), i.e. the generated `_reduce_N` callbacks. Given the rule index (the racc `method_id`) and the slice of popped symbol values, it returns the value of the produced nonterminal.
- OnError: the parse-error handler (`on_error`). It is called the first time an error action fires; returning normally enters racc's error-recovery mode, and returning an error aborts the parse with that error. The default handler (Parser.OnError unset) raises a ParseError, matching MRI.
The Tables layout mirrors MRI's `Racc_arg` array exactly so a generated parser's tables drive this engine unchanged; see Tables for the index mapping.
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type ParseError ¶
type ParseError struct {
// Tok is the internal token id of the token that caused the error
// (MRI's ERROR_TOKEN_ID).
Tok int
// Val is the value of the offending token (MRI's ERROR_VALUE).
Val any
// Msg is the rendered message, matching MRI's
// "parse error on value <val.inspect> (<token_to_str or '?'>)".
Msg string
}
ParseError is the error MRI's Racc::Parser raises (and rescues) on a parse error. It corresponds to Ruby's `Racc::ParseError < StandardError`.
func (*ParseError) Error ¶
func (e *ParseError) Error() string
type Parser ¶
type Parser struct {
// Tables are the racc-generated parse tables driving the automaton.
Tables *Tables
// NextToken is the lexer seam, used by DoParse. It returns the next token's
// internal-or-external symbol and value. A nil symbol means EOF (MRI's
// `[false, false]`). The returned symbol is looked up in Tables.TokenTable;
// an unknown non-nil symbol maps to the error token (internal id 1).
NextToken func() (sym any, val any)
// Reduce is the reduce-action dispatch seam (the generated `_reduce_N`). It is
// called with the racc rule's method_id and the slice of popped symbol values
// (MRI's `val`), and returns the value of the produced nonterminal. When
// Tables.UseResult is true the action conventionally starts from values[0]
// (MRI passes `tmp_v[0]` as the initial `result`); that initial value is also
// provided here as result for parity with the generated `def _reduce_N(val, _values, result)`.
Reduce func(methodID int, values []any, result any) any
// OnError is the parse-error seam (MRI's `on_error`). It is called the first
// time an error action fires, with the offending token id/value and a snapshot
// of the value stack (callers must not mutate it). Returning nil enters racc's
// error-recovery mode; returning a non-nil error aborts the parse with that
// error. When nil, the engine raises a ParseError, matching MRI's default.
OnError func(tok int, val any, valueStack []any) error
// contains filtered or unexported fields
}
Parser is the table-driven LALR(1) parse engine. Construct it with a Tables and the host seams, then call Parser.DoParse or Parser.Yyparse.
A zero Parser is not usable; Tables and NextToken (for DoParse) / the iterator (for Yyparse) plus Reduce must be set.
func (*Parser) DoParse ¶
DoParse runs the parser using the NextToken lexer seam. It is the Go counterpart of Racc::Parser#do_parse → _racc_do_parse_rb. It returns the accepted result (MRI's Symbol_Value_Stack[0]) or a *ParseError (or the error returned by a custom OnError) on failure.
func (*Parser) Yyaccept ¶
func (p *Parser) Yyaccept()
Yyaccept exits the parser from inside a reduce action, like MRI's Racc::Parser#yyaccept (`throw :racc_jump, 2`). Call it only from within a Reduce callback.
func (*Parser) Yyerrok ¶
func (p *Parser) Yyerrok()
Yyerrok leaves error-recovery mode, like MRI's Racc::Parser#yyerrok. Call it from within a Reduce/OnError seam.
func (*Parser) Yyerror ¶
func (p *Parser) Yyerror()
Yyerror enters error-recovery mode from inside a reduce action, like MRI's Racc::Parser#yyerror (`throw :racc_jump, 1`). Call it only from within a Reduce callback; it unwinds to the reduce dispatcher.
func (*Parser) Yyparse ¶
Yyparse runs the parser using a pull-style iterator seam instead of NextToken, mirroring Racc::Parser#yyparse → _racc_yyparse_rb. The yield function passed to iter must be called once per token with (sym, val) (nil sym == EOF), exactly as MRI's RECEIVER#METHOD_ID yields [tok, val]. It returns the accepted result or an error, like DoParse.
In a generated parser, `yyparse(recv, mid)` drives the automaton from tokens that recv.mid yields; here the caller supplies that iterator directly as iter.
type Symbol ¶
type Symbol string
Symbol is the Go representation of a Ruby Symbol token (e.g. :NUMBER). A racc token table keys terminals by their grammar symbol; for named tokens MRI uses a Ruby Symbol and for character literals a String. Use Symbol so the two are distinct map keys in Tables.TokenTable, matching MRI where :foo and "foo" differ.
type Tables ¶
type Tables struct {
ActionTable []int // [0] compressed action table (negative=reduce, positive=shift, shift_n=accept)
ActionCheck []int // [1] validity check parallel to ActionTable
ActionDefault []int // [2] default action per state
ActionPointer []int // [3] per-state base offset into ActionTable (nil ⇒ use default)
GotoTable []int // [4] compressed goto table
GotoCheck []int // [5] validity check parallel to GotoTable
GotoDefault []int // [6] default goto per produced nonterminal
GotoPointer []int // [7] per-state base offset into GotoTable (nil ⇒ use default)
NtBase int // [8] first nonterminal id; reduce_to-NtBase indexes the goto tables
ReduceTable []int // [9] flat triples (len, reduce_to, method_id) indexed by act*-3
TokenTable map[any]int // [10] maps an external token symbol to its internal id (EOF symbol ⇒ 0)
ShiftN int // [11] boundary: 0<act<ShiftN ⇒ shift; act==ShiftN ⇒ accept
ReduceN int // [12] boundary: 0>act>-ReduceN ⇒ reduce; act==-ReduceN ⇒ error
UseResult bool // [13] whether reduce actions take the extra `result` argument
// TokenToS optionally maps an internal token id to its display string
// (MRI's Racc_token_to_s_table), used by [Tables.TokenToStr] and in the
// default parse-error message. It is not part of Racc_arg.
TokenToS []string
}
Tables holds a racc-generated parser's parse tables. The field order and semantics mirror MRI's `Racc_arg` array element-for-element (the comment after each field is the `Racc_arg` index), so the constants emitted by `racc` map directly onto this struct:
Racc_arg = [ action_table, action_check, action_default, action_pointer, # 0..3 goto_table, goto_check, goto_default, goto_pointer, # 4..7 nt_base, reduce_table, token_table, shift_n, # 8..11 reduce_n, use_result_var [, ...] ] # 12..13
The action/goto tables use racc's compressed double-array layout: an entry at pointer+input is valid only when the parallel *_check array equals the current state (resp. nonterminal index), otherwise the *_default for that state is used.
func (*Tables) TokenToStr ¶
TokenToStr returns the display string for an internal token id, mirroring MRI's Racc::Parser#token_to_str (returns "" when there is no mapping, where MRI returns nil). It is exposed because OnError handlers commonly want it.
Source Files