I just fed it this:

---

Here is a grammar for a made up language:

sentence = "sob" subject (verb "ob" object | verb "ad" sentence | "ploj").
verb = "ab" | "pom"
object = "foo" | "bar"

Construct a few sentences, and show the sentence so far, and which rule and step of the rule you are currently applying. E.g. sentence= ""; rule=sentence; step="sob".

---

Notice I did not explain the BNF syntax, which is reasonable as it'll have plenty of that in its training data. Notice that I also "forgot" to give it a production for the "subject" rule - leaving it with two choices: It can give up and tell me off, or it can do as best it can and let me know it's had to improvise.

Here's the first sentence construction:

---

First Sentence Construction:

sentence = "";

Rule: sentence; Step: "sob".
sentence = "sob";

Rule: subject; Step: (choosing object as a subject for simplicity) "foo".
sentence = "sob foo";

Rule: verb; Step: "ab".
sentence = "sob foo ab";

Rule: (verb "ob" object | verb "ad" sentence | "ploj"); Step: "ob".
sentence = "sob foo ab ob";

Rule: object; Step: "bar".
sentence = "sob foo ab ob bar"; (Complete Sentence)

---

It has correctly applied the rules I did give, and opted to "fill in" "object" as a replacement for my missing "subject" rule. There are few enough rules this could be a fluke, but it's a better choice to guess at that substitution than verb or sentence, though hardly takes a genius.

Second:

---

Second Sentence Construction:

sentence = "";

Rule: sentence; Step: "sob".
sentence = "sob";

Rule: subject; Step: "bar".
sentence = "sob bar";

Rule: verb; Step: "pom".
sentence = "sob bar pom";

Rule: (verb "ob" object | verb "ad" sentence | "ploj"); Step: "ad".
sentence = "sob bar pom ad";

Rule: sentence; Step: "sob" (this starts a nested sentence).
sentence = "sob bar pom ad sob";

Rule: subject; Step: "foo".
sentence = "sob bar pom ad sob foo";

Rule: verb; Step: "ab".
sentence = "sob bar pom ad sob foo ab";

Rule: (verb "ob" object | verb "ad" sentence | "ploj"); Step: "ob".
sentence = "sob bar pom ad sob foo ab ob";

Rule: object; Step: "foo".
sentence = "sob bar pom ad sob foo ab ob foo"; (Complete Sentence)

---

This is also correct, and it correctly points out that the arm it picked triggered a nested application of the `sentence` rule.

It stumbled on the third attempt:

---

Third Sentence Construction:

sentence = "";

Rule: sentence; Step: "sob".
sentence = "sob";

Rule: subject; Step: "foo".
sentence = "sob foo";

Rule: verb; Step: "pom".
sentence = "sob foo pom";

Rule: (verb "ob" object | verb "ad" sentence | "ploj"); Step: "ploj".
sentence = "sob foo pom ploj"; (Complete Sentence)

---

Note that there is a possible interpretation of the "|" operator which would make its sentence valid, so "technically" it could be, but it would involve (ver "ob" object | verb "ad" sentence | "ploj") to be interpreted as (verb (("ob object)|("ad" sentence)|"ploj")) and that's contrived.

So to answer you: It can, and it does, but not always consistently. One can choose to be disappointed it's not perfect, but for just handing it a grammar and asking it to reason about it with no example text or chances to "practice" whatsoever, I think it's doing quite well.

I've interviewed many software developers who'd struggle with a task like this.

When prodded about the third example, it picks a more reasonable interpretation of the "|", though it's explanation starts out with an error, but then given a correct explanation:

---

Q: How do you figure this? The full rule is "sob" subject (verb "ob" object | verb "ad" sentence | "ploj"). How do you figure the verb is allowed without being followed by either "ad" or "ob"?

A: Upon closer examination, you are correct to point out that the structure following "sob" subject must indeed involve a verb according to the rule provided. The full rule:

"sob" subject (verb "ob" object | verb "ad" sentence | "ploj").
indicates that the sentence must start with "sob", followed by a subject, and then either:

a verb followed by "ob" and an object,

a verb followed by "ad" and another sentence,

or the standalone term "ploj".

---

It goes on to give two correct alternatives to the erroneous one:

---

* "sob foo ploj" — where "ploj" follows directly after the subject without a verb, or
* "sob foo ab ob bar" — where "ab" is the verb followed by "ob" and "bar" as the object.

---

While it's not perfect, it can very clearly "learn and reproduce multistep algorithms" to some extent. It also clearly needs to get better at it.