How to properly test many methods when main logic is in private method [duplicate]

Question

This is a little bit of follow up question to How to test private methods. I totally agree (and experienced what happens when you try) that we should not test private methods. Sometimes though it leads to duplication.

This question is also not about If one test - one assert breaks DRY principle as suggested. The question remains despite of using single or many assert per test.

Let's make a simplified example with two public methods (example in PHP):

class Parser {
   public function parse_class() {
      return $this->parse("Class"); 
   }
   public function parse_methods() {
      return $this->parse("Methods");
   }
   private function parse($what) {
      // make proper regexp to find class name or methods name
      return $results
   }
   }

If the code war refactored this way, to remove duplication - we have a choice to have duplication in tests:

function test_parse_class_gives_empty_array_when_no_classes() {
  $parser = new Parser("Foo");
  $this->assertEmpty($parser->parse_class());
}
function test_parse_method_gives_empty_array_when_no_methods() {
  $parser = new Parser("Bar");
  $this->assertEmpty($parser->parse_methods());
}

or to introduce some logic in test, to reduce this duplication:

/**
* @dataProvider [ ['class', 'no class definition here'],['methods', 'foo bar baz']]
*/
function test_parse_methods_return_empty_arrays_when_nothind_found($suffix, $str){
  $methodName = "parse_" . $suffux;
  $parser = new Parser($str);
  $this->assertEmpty($parser->$methodName());
}

The first approach is easier to read, but burden to write and maintain (and the amount of tests increase by two for each edge case). If it's refactored as in 2nd example - it's easier to maintain, but harder to read and comprehend. Additionally: should it be tested as well?

Third option would be to maybe assume that the provate method is a responsibility in itself and extract to yet another class. parse method would be public and it would be easier to test. But then most probably the original code will become too fragmented (like: nothing is happening anywhere anymore)?

What kind of approach works best with such situation? Maybe it's a pattern I fail to recognize?