c++ - 使用 BNF 语法提取信息

Question

我想从文本正文中提取信息并能够对其进行查询。

此文本主体的结构将由 BNF 语法(或变体)指定，要提取的信息将在运行时指定(此时查询的语法无关紧要)。

所以要求很简单，真的:

• 接收一些结构化的文本
• 使用语法以可利用的形式加载它以对其进行解析
• 运行查询以选择它的某些部分

举例说明，假设我们有这样的文法(自定义的BNF格式):

<digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<id> ::= 15 * digit

<hex> ::= 10 * (<digit> | a | b | c | d | e | f)

<anything> ::= <digit> | .... (all characters)

<match> ::= <id> (" " <hex>)*

<nomatch> ::= "." <anything>*

<line> ::= (<match> | <nomatch> | "") [<CR>] <LF>

<text> ::= <line>+

这样的文本将符合:

012345678901234
012345678901234 abcdef0123

Nor the previous line nor this one would match

然后我想列出规则中出现的所有标签，例如使用类似 XPath 的语法:

match//id

这将返回一个列表。

---

这听起来相对容易，除了我有两个很大的限制:

• 应在运行时读取 BNF 语法(从类似字符串/vector 的结构)
• 查询也会在运行时被读取

一些精度:

• 语法预计不会经常更改，因此生成内存结构的“编译”步骤是可以接受的(并且可能是实现良好速度所必需的)
• 速度至关重要，即时收集所需部分的奖励积分
• 可能有回调来消除歧义的加分(例如，有时必要的消除歧义信息可能需要数据库访问)
• 多部分语法的奖励点(有利于语法元素的模块化和重用)

例如，我知道 lex/yacc 和 flex/bison，但是它们似乎只创建要编译的 C/C++ 代码，这不是我所关注的。

Do you know of a robust library (preferably free and open-source) that can transform a BNF grammar into a parser "on-the-fly" and produce a structured in-memory output from a body of text using this parser ?

编辑:我对替代方案持开放态度。目前，想法是也许正则表达式可以允许这种提取，但是考虑到所涉及语法的复杂性，这可能很快就会变得丑陋，因此维护正则表达式将是一项非常可怕的任务。此外，通过分离语法和提取，我希望能够针对不同的提取需求重用相同的语法，而不是每次都使用略有不同的正则表达式。

Answer 1

我有一个专有的解决方案，可以将语法源转换为内存中的表示形式。结果是一个纯数据结构。任何代码都可以使用它。我还有实际实现解析器的 C++ 类。规则处理程序作为虚拟方法实现。

我们的解决方案与 YACC/Bison 之间的主要区别是不生成 C/C++ 代码。这意味着无需重新编译应用程序即可重新加载语法。语法可以用规则处理程序代码中使用的应用程序 ID 进行注释。