简洁的语法来解析诸如“ abab”或“ baba”之类的交替字符的字符串

Question

我正在用golang开发玩具解析器，只是为了学习语言。我添加了一个包含语法的测试案例，涉及以下案例：

Valid:
a, ab, aba, ababababababa, ababababab
b, ba, bab, babababababab, bababababa

Invalid:
abb, baa

a总是紧随其后，b反之亦然。

现在解析器中的语法看起来像这样（为了简洁起见，我省略了周围的代码）：

    "expr": Or(Ref("A"), Ref("B")),
    "A": And(
        a,
        Optional(
            And(
                b,
                Optional(Ref("A"))))),
    "B": And(
        b,
        Optional(Ref("A")))

哪里

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

我想这不是描述这种语法的最简洁的方法。如何使其更紧凑？

有关：

• 为什么递归下降解析器不能处理左递归

编辑：

Filip的BNF答案可以用我的语法写成：

    "expr": Or(Ref("A"), Ref("B")),
    "A":    Or(And(a, Ref("B")), a),
    "B":    Or(And(b, Ref("A")), b)

Answer 1

您拥有的BNF语法是这样的：

expr ::= A | B
A ::= "a" B | "a"
B ::= "b" A | "b"

我认为可以使用您的语法将此翻译为：

"expr": Or(Ref("A"), Ref("B")),
"A": And(
    a,
    Optional(Ref("B"))),
"B": And(
    b,
    Optional(Ref("A")))

请注意，在非端子（）之前检查端子（"a"，"b"）很重要Ref(x)，否则会出现无限循环。它将始终尝试查看它是否可以匹配另一个字符串A或B该字符串的末尾，然后匹配另一个字符串，从而导致永无止境的递归。