解析“ababa”或“baba”等​​交替字符字符串的简洁语法

Question

我正在用golang开发一个玩具解析器，只是为了学习这门语言。我添加了一个测试用例，其语法涵盖以下情况：Valid:a, ab, aba, ababababababa, abababababb, ba, bab, babababababab, bababababaInvalid:abb, baaa总是跟在后面，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" characterb - 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 expressionsOr       - consume any of the expressionsRef      - refer to other expression (allows recursion)Optional - make the expression non-obligatory我想这不是描述这种语法的最简洁的方式。如何让它更紧凑？

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字符串的末尾，然后是另一个，然后是另一个，从而导致永无止境的递归。