As for how I got around Perl's unhappiness here, I rolled my own solution:

m{
  A
  (?:
    (?>[^AB]*)  # match non-A's and non-B's WITHOUT BACKTRACKING
    (?:
      [AB]      # match A or B next...
      |         # ...or...
      (?<=.)    # ...if there was a character before
    )
    B           # match B
  )*            # 0 or more times
  [^AB]*        # you know the rest
  A
}x
[download]

Ick. Why should I have to do that work?

$_="goto+F.print+chop;\n=yhpaj";F1:eval