3.3. A concrete Decimal trace
Consider one valid input:
Decimal ::= Sign Natural "." Fraction
Sign ::= sign
Natural ::= digit+
Fraction ::= digit{1,4}
input: -12.34
3.3.1. Decoder: build the choices first
The decoder represents a partial match as a pair containing the captures found so far and the unconsumed remainder. It explores the input from left to right:
-
Signconsumes-. Its absent alternative cannot continue becauseNaturalrequires a digit. -
Naturalcan initially consume1or12. The1branch leaves2.34, so the following dot fails. The12branch reaches the dot. -
Fractioncan consume3, leaving4, or consume34, leaving nothing.
The following checked equation exposes the two candidates that reach the root:
example :
decimalRootCandidates "-12.34" =
[([("Sign", "-"),
("Natural", "12"),
("Fraction", "3")],
"4"),
([("Sign", "-"),
("Natural", "12"),
("Fraction", "34")],
"")] := ⊢ decimalRootCandidates "-12.34" =
[([("Sign", "-"), ("Natural", "12"), ("Fraction", "3")], "4"),
([("Sign", "-"), ("Natural", "12"), ("Fraction", "34")], "")]
All goals completed! 🐙
Triptych.decode constructs this candidate list, keeps only entries with an empty
remainder, and returns the first one. The first candidate above is discarded; the second yields
the captures Sign = "-", Natural = "12", and Fraction = "34".
3.3.2. Scanner: ask the rest immediately
The complete scanner does not first construct that list. Whenever it finds a possible prefix, it immediately calls the continuation for the rest of the grammar:
Natural = "1" -> try "." next -> fail immediately Natural = "12" -> try "." next -> continue Fraction = "3" -> root sees remainder "4" -> fail immediately Fraction = "34" -> root sees no remainder -> return success
This is the same ordered search, but failed choices are discarded as soon as their continuation fails, and the successful choice stops the search.
Decimal also passes Triptych.Grammar.staticUnique, so its normal runtime path is even
more direct. The scanner sees that Natural is followed by the literal dot, consumes the
digit run up to that dot, and then consumes the final fraction to the end of the input. It obtains
the successful captures without complete-candidate backtracking.
The two implementations therefore return exactly the same observable result:
example :
decode Decimal.grammar "-12.34" =
some
[("Sign", "-"),
("Natural", "12"),
("Fraction", "34")] ∧
scan Decimal.grammar "-12.34" =
some
[("Sign", "-"),
("Natural", "12"),
("Fraction", "34")] := ⊢ decode Decimal.grammar "-12.34" = some [("Sign", "-"), ("Natural", "12"), ("Fraction", "34")] ∧
scan Decimal.grammar "-12.34" = some [("Sign", "-"), ("Natural", "12"), ("Fraction", "34")]
All goals completed! 🐙
The generated parser then checks the constraints and computes the value from this one capture map. Neither the decoder nor the scanner itself decides what the Decimal value means.