2

我正在尝试使用 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 解析器示例。

4

1 回答 1

4

您的语言几乎太简单以至于不需要解析器生成器。同时，它不是上下文无关的，这使得使用解析器生成器变得很困难。因此，Nearly 解析器很可能不是最适合您的工具，尽管它可能会通过一些黑客技术使其工作。

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

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

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

问题是您定义string为sstrchar:*，如果我们查看sstrcharin的定义string.ne，我们会看到（忽略不相关的后处理操作）：

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

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

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

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

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

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

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

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

Nearly macro 将其扩展到

 "[" [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})\].*?\[\/\1\]/gmi

您可以使用Regex 101在线玩它

于 2021-03-09T03:49:06.923 回答