手动解析一个简单的语法

Question

我需要实现一个简单的解析器来解析以下字符串： a[b[c,d],e],f[g,h[i],j[k,l]],...

在上面的示例中，有一个由一个或多个 OBJECTS 组成的 GROUP。每个对象都有嵌套的 OBJECTS(b in a AND h,j in f) 加上嵌套的 VALUES(c,d,e,g,i,k,l)。

所以，它是这样的：

GROUP : OBJECT (,OBJECT)*
OBJECT: NAME '[' OBJECTorVALUE (OBJECTorVALUE)* ']'
OBJECTorVALUE: OBJECT | VALUE
VALUE : NAME

手动解析此类语法的最简单方法是什么？

我试着用递归下降解析器解析它，它是可行的，但看起来很奇怪，因为你必须解析 OBJECTorVALUE 的产生式：

OBJECTorVALUE: NAME '[' blabla ']'
OBJECTorVALUE: NAME

因此，要使其成为 LL 文法（由 rec-descent 解析），我们应该将其解析为

OBJECTorVALUE: NAME Z
Z: eps | '[' blabla ']'

现在 rec-desc 解析器变得有些不必要的复杂性并且感觉不自然，所以我必须引入一种 rec-desc 方法来在名称后查找 Z。所以，而不是简单的方法

parseGroup -> parseObjects 
parseObj -> parseName consume[ parseObjectValueGroup consume ]
parseObjectValueGroup -> parseObjectValues
parseObjectValue -> look('[') -> parseObj OR parseValue

我也一样，但最后的语句变成了

parseObjectValue -> parseName parseZ
parseZ -> look('[') -> parseObjWithoutName OR return empty
parseObjWithoutName -> ...

我觉得这看起来很乱，所以我们可以在这里使用更简单的东西吗？我的意思是它是该死的简单语法，甚至可以通过字符串拆分来解析，而且看起来非常简单。也许简单 LR 解析器 (SLR) 在这种情况下会更具可读性？

Answer 1

我实际上认为尝试解析这种自上而下的方法并不会那么糟糕。如果你试着把它写成正式语法，它看起来比实际情况要糟糕得多。例如，伪代码可能如下所示：

ParseGroup():
    result = empty list
    while true:
        read token 'next'; it's some identifier.
        if (there's no next token) {
           append 'next' to result.
           break;
        }
        else if (the next token is '[') {
           let inner = ParseGroup();
           read token; it's a ']';
           append 'next[inner]' to result.
        } else {
           append 'next' to result.
        }
        read token; it's a comma.
        append ',' to result.
    }
}

这基本上是为修改后的语法略作修改的 LL(1) 解析器。

Answer 2

这真是一个非常简单的语法。你的语法不完整，因为 NAME 没有定义。 ABNF (RFC 5234) 语法中定义的语法是这样的（假设是 NAME 规则）：

group   = element *("," WS element)
element = name WS ["[" WS group "]" WS]
name    = 1*(%x61-7A / %x41-5A)
WS      = *(%x20 / %x9 / %xA / %xD)

你可以理解为：一组由逗号分隔的元素组成。每个元素都有一个名称，并且在它之后可能在乡绅括号中有一个子元素组。 'name' 是一个或多个英文字母字符。在语法的每个部分之间，允许使用白色 space（零个或多个）：space（20 十六进制）、制表符（9 十六进制）、换行符（A 十六进制）或回车 return（D 十六进制）。如果你不想要白色space，完全删除WS规则即可。

这是语法，但还有语义：如果 element 只有名称，那么它是 value，否则它是 object。这是一个简单的消歧，你应该在解析完成后做。

如果语法这么简单，你不想自己写代码，我做了一个工具（Tunnel Grammar Studio）可以用C++代码为你生成这个语法。语法很简单，所以工具的演示应该足够了。您也可以在线运行语法。 TGS 生成迭代解析器，这意味着如果您的组 ps 嵌套太多，您不必担心堆栈溢出问题。

ps。除了十六进制值，您还可以编写 1*('a'-'z' / 'A'-'Z')，因为 TGS 具有 ABNF 语法的扩展，可以轻松编写语法。

手动解析一个简单的语法

Manually parsing a simple grammar

grammar

parsing

text-parsing

context-free-grammar