简洁的语法来解析诸如“ 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" 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 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 | 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
该字符串的末尾,然后匹配另一个字符串,从而导致永无止境的递归。
以上是 简洁的语法来解析诸如“ abab”或“ baba”之类的交替字符的字符串 的全部内容, 来源链接: utcz.com/qa/417941.html