Add Rust implementation of SCFG decoder

Rust port of the Ruby prototype decoder with performance
optimizations for real Hiero-style grammars:

- Rule indexing by first terminal/NT symbol for fast lookup
- Chart symbol interning (u16 IDs) instead of string hashing
- Passive chart index by (symbol, left) for direct right-endpoint lookup
- Items store rule index instead of cloned rule data

Includes CKY+ parser, chart-to-hypergraph conversion, Viterbi
decoding, derivation extraction, and JSON hypergraph I/O.

Self-filling step in parse uses grammar lookup (not just
remaining active items) to handle rules that were consumed
during the parse loop or skipped by the has_any_at optimization.

Produces identical output to the Ruby prototype on all test examples.

Co-Authored-By: Claude Opus 4.6 <noreply@anthropic.com>

1 files changed, 39 insertions, 0 deletions

diff --git a/rs/src/semiring.rs b/rs/src/semiring.rs
new file mode 100644
index 0000000..9a8fe3e
--- /dev/null
+++ b/rs/src/semiring.rs
@@ -0,0 +1,39 @@
+pub trait Semiring {
+    fn one() -> f64;
+    fn null() -> f64;
+    fn add(a: f64, b: f64) -> f64;
+    fn multiply(a: f64, b: f64) -> f64;
+}
+
+pub struct ViterbiSemiring;
+
+impl Semiring for ViterbiSemiring {
+    fn one() -> f64 {
+        1.0
+    }
+
+    fn null() -> f64 {
+        0.0
+    }
+
+    fn add(a: f64, b: f64) -> f64 {
+        a.max(b)
+    }
+
+    fn multiply(a: f64, b: f64) -> f64 {
+        a * b
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    #[test]
+    fn test_viterbi() {
+        assert_eq!(ViterbiSemiring::one(), 1.0);
+        assert_eq!(ViterbiSemiring::null(), 0.0);
+        assert_eq!(ViterbiSemiring::add(0.3, 0.7), 0.7);
+        assert_eq!(ViterbiSemiring::multiply(0.5, 0.6), 0.3);
+    }
+}