[Nearley]：如何解析匹配的开始和结束标签

Question

我正在尝试使用 nearley 解析一种非常简单的语言：您可以在匹配的开始和结束标签之间放置一个字符串，并且您可以链接一些标签。它看起来像一种 XML，但是用 [ 而不是 < ，标签总是 2 个字符长，并且没有嵌套。

[aa]My text[/aa][ab]Another Text[/ab]

但我似乎无法正确解析这一点，因为我一有多个标签就得到 the grammar should be unambiguous。

我现在掌握的语法：

@builtin "string.ne"
@builtin "whitespace.ne"

openAndCloseTag[X] -> "[" $X "]" string  "[/" $X "]"

languages -> openAndCloseTag[[a-zA-Z] [a-zA-Z]] (_ openAndCloseTag[[a-zA-Z] [a-zA-Z]]):*

string -> sstrchar:* {% (d) => d[0].join("") %}

与此相关，理想情况下我希望标签不区分大小写（例如 [bc]TESt[/BC] 有效）

有人知道我们该怎么做吗？我找不到近距离的 XML 解析器示例。

Answer 1

您的语言几乎太简单了，不需要解析器生成器。同时，它不是上下文无关的，这使得使用解析器生成器变得困难。因此，Nearly 解析器很可能不是您的最佳工具，尽管它可能需要一些 hackery 才能工作。

要事第一。您实际上并没有为您的语言提供明确的定义，这就是您的解析器报告歧义的原因。要查看歧义，请考虑输入

[aa]My text[/ab][ab]Another Text[/aa]

这与您的测试输入非常相似；我所做的只是交换一对字母。现在，问题来了：这是一个由单个 aa 标签组成的有效输入吗？还是语法错误？（这是一个严肃的问题。像这样的标签系统的一些定义认为标签只能由匹配的关闭标签关闭，因此看起来像不同标签的东西被认为是纯文本。这样的系统会接受输入作为单个标记值。）

问题是您将 string 定义为 sstrchar:*，如果我们查看 string.ne 中 sstrchar 的定义，我们会看到（忽略后处理无关紧要的动作）：

sstrchar -> [^\'\n]
    | "\" strescape
    | "\'"

现在，第一种可能性是“除反斜杠、单引号或换行符以外的任何字符”，很容易看出 [/ab] 中的所有字符都在 sstrchar 中. （我不清楚你为什么选择 sstrchar；单引号在你的语言中似乎并不特殊。或者你可能只是没有提到它们的重要性。）所以 string 可以向上延伸到输入结束。当然，语法需要一个结束标记，Nearley 解析器会确定是否找到匹配项（如果有）。但是，实际上，有两个。所以解析器声明了一个歧义，因为它没有任何标准可以在两个关闭标签之间进行选择。

这就是我们遇到的问题，即您的语言不是上下文无关的。（实际上，它在某种技术意义上是上下文无关的，因为“只有”676 个两个字母的不区分大小写的标签，理论上可以列出所有 676 种可能性。但我猜你不想做到这一点。）

上下文无关文法不能表达坚持两个非终结符展开为同一个字符串的语言。这就是上下文无关的定义：如果一个非终端只能匹配与前一个非终端相同的输入，那么第二个非终端匹配取决于上下文，特别是第一个非终端产生的匹配。在上下文无关文法中，非终结符扩展为同一事物，而不管文本的其余部分如何。不允许出现非终结符的上下文影响展开。

现在，您很可能期望您的宏定义：

openAndCloseTag[X] -> "[" $X "]" string  "[/" $X "]"

正在通过重复 $X 宏参数来表示上下文相关的匹配。但 Nearley 文档将此构造描述为宏并非偶然。 X 这里指的就是宏调用中使用的字符串。所以当你说：

openAndCloseTag[[a-zA-Z] [a-zA-Z]]

Nearly 宏将其扩展为

 "[" [a-zA-Z] [a-zA-Z] "]" string  "[/" [a-zA-Z] [a-zA-Z] "]"

这就是它将用作语法生成的内容。请注意，两个 $X 宏参数已扩展为相同的参数，但这并不意味着它们将匹配相同的输入文本。这些子模式中的每一个都将独立匹配任何两个字母字符。上下文无关。

正如我之前提到的，您可以使用这个宏来写出 676 种可能的标记模式：

tag -> openAndCloseTag["aa"i]
     | openAndCloseTag["ab"i]
     | openAndCloseTag["ac"i]
     | ...
     | openAndCloseTag["zz"i]

如果你这样做了（并且你设法正确列出了所有的可能性）那么解析器就不会抱怨歧义只要你从不在同一个输入中使用同一个标签两次。因此，您的原始输入和我更改后的输入都可以（只要您接受我的输入是单个标记对象的解释）。但它仍然会报告以下内容不明确：

[aa]My text[/aa][aa]Another Text[/aa]

这是不明确的，因为语法允许它是单个 aa 标记字符串（其文本包含看起来像关闭和打开标记的字符）或两个连续的 aa 标记字符串。

为了消除歧义，您必须以不允许内部标记的方式编写 string 模式，就像 sstrchar 不允许内部单引号一样。当然，除了匹配不包含模式的字符串远没有匹配不包含单个字符的字符串那么简单。它可以使用 Nearley 来完成，但我真的不认为这是你想要的。

最好的选择可能是使用本机 Javascript 正则表达式来匹配标记的字符串。这将证明更简单，因为 Javascript 正则表达式比数学正则表达式更强大，甚至允许匹配（某些）上下文相关结构的可能性。例如，您可以将 Javascript 正则表达式与 Moo 词法分析器一起使用，它很好地集成到 Nearley 中。或者您可以直接使用正则表达式，因为一旦您匹配了标记的文本，您就不需要做太多其他事情了。

为了帮助您开始，这里有一个简单的 Javascript 正则表达式，它匹配带有匹配的不区分大小写标签的标记字符串（末尾的 i 标志）：

/\[([a-zA-Z]{2})\].*?\[\/\]/gmi

您可以使用 Regex 101

在线玩它

[Nearley]：如何解析匹配的开始和结束标签

[Nearley]: how to parse matching opening and closing tag

javascript

parsing

nearley