解析“ababa”或“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

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

Answer 1

您拥有的 BNF 语法是这样的：expr ::= A | BA ::= "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字符串的末尾，然后是另一个，然后是另一个，从而导致永无止境的递归。