Создаёшь func FuzzParse(f *testing.F), добавляешь примеры f.Add("valid input"), f.Add(""). Потом f.Fuzz(func(t *testing.T, s string) { result, err := Parse(s); if err != nil { return }; /* проверяй инварианты */ }). Не проверяй конкретные значения — проверяй что нет паники, что результат валиден, что encode(decode(x)) == x.