I am working on a toy parser in golang just to learn the language. I added a test case with grammar covering the following cases:
Valid:
a, ab, aba, ababababababa, ababababab
b, ba, bab, babababababab, bababababa
Invalid:
abb, baa
a
is always followed by b
and vice versa.
Now the grammar in my parser looks like that (I omit the surrounding code for sake of brevity):
"expr": Or(Ref("A"), Ref("B")),
"A": And(
a,
Optional(
And(
b,
Optional(Ref("A"))))),
"B": And(
b,
Optional(Ref("A")))
Where
a - exact match for "a" character
b - exact match for "b" character
"A", "B", "expr" - names of the parts of the grammar that can be referred
later with Ref("A")
And - consume sequence of expressions
Or - consume any of the expressions
Ref - refer to other expression (allows recursion)
Optional - make the expression non-obligatory
I guess it is not the most succinct way to describe this grammar. How to make it more compact?
Related:
EDIT:
The BNF answer from Filip can be written in my syntax as:
"expr": Or(Ref("A"), Ref("B")),
"A": Or(And(a, Ref("B")), a),
"B": Or(And(b, Ref("A")), b)