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

我正在用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)

回答:

您拥有的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),否则会出现无限循环。它将始终尝试查看它是否可以匹配另一个字符串AB该字符串的末尾,然后匹配另一个字符串,从而导致永无止境的递归。

以上是 简洁的语法来解析诸如“ abab”或“ baba”之类的交替字符的字符串 的全部内容, 来源链接: utcz.com/qa/417941.html

回到顶部