I've been writing acceptance tests in Given-When-Then since 2009 and I've never written a feature file by choice. So when someone asks whether you can do BDD without Gherkin, my answer is that I've never done it any other way.
Cucumber has been the default for long enough that the two have merged in people's heads. They shouldn't have. BDD is a way of specifying behaviour. Gherkin is a file format one family of tools uses to do it.
I've been writing acceptance tests on the JVM since 2009. Concordion first, then Cucumber on the teams around me, then Yatspec, and eventually I wrote my own.
Yatspec's trick was that it read the test method itself. You wrote:
given(orchestration.sends(anOrder));
and the report showed:
Given orchestration sends an order
No feature file, no step definitions, no glue. The test was the sentence.
That's the idea I've been chasing ever since, and it's why I wrote Kensa. So this is a biased guide. It's also a short one.