简洁的语法来解析诸如"abab"之类的交替字符的字符串或"baba" [英] Succinct grammar to parse strings of alternating characters like "ababa" or "baba"

问题描述

我正在研究解析器. en.wikipedia.org/wiki/Go_(programming_language)"rel =" nofollow noreferrer> golang 只是为了学习该语言.我添加了一个包含语法的测试案例，涵盖以下案例:

I am working on a toy parser in golang just to learn the language. I added a test case with grammar covering the following cases:

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

Invalid:
abb, baa

a后面总是b，反之亦然.

a is always followed by b and vice versa.

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

Now the grammar in my parser looks like that (I omit the surrounding code for sake of brevity):

    "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

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

I guess it is not the most succinct way to describe this grammar. How to make it more compact?

相关:

• 为什么不能返回递归下降解析器句柄递归

来自Filip的BNF 答案可以用我的语法写成:

The BNF answer from Filip can be written in my syntax as:

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

推荐答案

您拥有的BNF语法是:

The BNF grammar you have is this:

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

我认为使用您的语法可以将其翻译为:

which I think translates to this using your syntax:

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

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

Note that it is important to check terminals ("a", "b") before non-terminals (Ref(x)), or you'll get an infinite loop. It would always try to see if it could match another A or B to the end of the string, and then another, and another, causing a never ending recursion.

这篇关于简洁的语法来解析诸如"abab"之类的交替字符的字符串或"baba"的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！