使用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语法(从字符串/矢量类结构)
• 查询也将在运行时读取

一些准确性:

• 语法预计不会经常改变,因此产生内存结构的"编译"步骤是可以接受的(并且可能是实现良好速度所必需的)
• 速度是最重要的,即想要的部分的即时收集的奖励点
• 可以使回调消除歧义的奖励积分(例如,有时必要的消歧信息可能需要DB访问)
• 多部分语法的奖励积分(有利于模块化和语法元素的重用)

我知道lex/yacc和flex/bison,但是它们似乎只创建了要编译的C/C++代码,这不是我所追求的.

你知道一个健壮的库(最好是免费的和开源的),它可以将"BNF语法"转换为"即时"解析器,并使用这个解析器从文本体中生成结构化的内存输出吗？

编辑:我对替代品持开放态度.目前,这个想法可能是正则表达式可以允许这种提取,但是考虑到所涉及的语法的复杂性,这可能会很快变得难看,因此保持正则表达式将是一项非常可怕的任务.此外,通过分离语法和提取,我希望能够为不同的提取需求重用相同的语法,而不是每次都有略微不同的正则表达式.

Answer 1

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

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