问题标签 [context-sensitive-grammar]

据我了解，大多数语言都是上下文无关的，但也有一些例外。例如，在 C++ 中a * b可能代表或乘法。type * pointer_declaration哪个发生取决于上下文，第一个标识符的含义。另一个例子是name用 VHDL 制作

您会看到语法形式是不同的，但如果省略可选参数，它们可以匹配，例如f，它是否代表 func_call、physical_literal，例如隐含可选量为 1 的 1 米或 enum_literal。

在与 Scala 插件设计人员交谈时，我了解到您构建 AST 是为了在依赖关系发生变化时重新评估它。如果您有 AST，则无需重新解析文件。AST 也值得显示文件内容。但是，如果语法是上下文相关的（假设这f是一个函数，在另一个文件中定义，但后来用户将其重新限定为枚举文字或未定义），则 AST 无效。在这种情况下，AST 会发生变化。每当您更改依赖项时，AST 都会更改。我要求评估并让我知道如何制作的另一种选择是构建一个模棱两可的 AST。

据我所知，解析器组合器是PEG 类型的。他们通过返回第一个匹配的产品来隐藏歧义，并且f会匹配一个函数调用，因为它是我语法中的第一个替代方案。我要求一个组合器，它不会退回到第一次成功，而是继续下一个替代方案。最后，它会返回给我一个所有匹配选项的列表。它会让我感到模棱两可。

我不知道您将如何向用户显示不明确的文件内容树，但它会消除重新解析依赖文件的需要。我也很高兴知道现代语言设计如何解决这个问题。

一旦解析了不明确的节点并返回了不明确的结果，我希望解析器收敛，因为我想继续解析，name并且我不想在每个歧义之后解析到文件末尾。这种情况因诸如 之类的情况而变得复杂f(10)，它可以是带有单个参数的函数调用，也可以是返回一个数组的空函数调用，该数组随后被索引。因此，f(10) 可以通过两种方式匹配名称，func_call直接匹配或递归匹配arr_indexing -> name ~ (expr)。因此，它不会像几个并行规则那样模棱两可，例如fcall | literal. 在重新收敛之前，某些分支可能比 1 个解析器长，例如fcall ~ (expr) | fcall.

你将如何解决它？是否可以将歧义组合器添加到 PEG？

在我的一个 cs 课程中，他们提到上下文无关语法和上下文相关语法之间的区别在于，在 CSG 中，生产规则的左侧必须小于或等于右侧。

所以，他们给出的一个例子是上下文相关的语法不能有一个空字符串，因为那样第一条规则就不会被满足。

但是，我了解到，常规语法包含在上下文无关中，上下文无关包含在上下文相关中，上下文相关包含在递归可枚举语法中。

因此，例如，如果一个文法是递归可枚举的，那么它也属于上下文相关、上下文无关和常规类型。

问题是，如果发生这种情况，那么如果我有一个包含空字符串的上下文无关语法，那么它将不满足被视为上下文相关的规则，但随后会发生矛盾，因为每个上下文相关是上下文无关的。

我正在使用 Xtext，需要对以下两个问题提出建议。

问题 #1

假设我有三个规则a，b和c。我想允许这些规则的任何序列，除了 b 和 c 应该只出现一次。如何最好地写出这样的语法？

这是我想出的：

有没有更好的方法来编写根语法？b 和 c 仍然必须按严格的顺序排列，这并不理想。

问题 #2

看看这个语法：

使用这种语法，我希望能够编写如下语言：

但是，由于节点“y”出现在“c”下，我收到错误消息。这是为什么？是不是因为现在“y”已经在其中一个规则中用作终端，它不能出现在语法的其他任何地方？

如何修正这个语法？

相关问题/材料：

• 我们如何将 a^nb^n 与 Java 正则表达式匹配？

• 如何确定一个数字是否是正则表达式的素数？（它处理一元素数匹配，而我正在寻找基数≥2；不过，这是一个不错的技巧，是什么让我想到了这个）

• http://nikic.github.io/2012/06/15/The-true-power-of-regular-expressions.html

众所周知，各种编程语言支持的“正则表达式”生成的语言在形式上是非常规的，并且如上述材料所示，能够识别至少一些上下文敏感的语言。

语言 L = {x | x 是以 10 为底的素数} 是一种上下文相关的语言，因为素性可以通过线性有界自动机测试（但它不是通过泵引理参数的上下文无关语言）。

那么，是否可以编写一个 Perl 或 Java 正则表达式来精确接受所有以 10 为底的素数？如果感觉更容易，请随意替换任何其他基数≥ 2 或准确识别所有合数。

例如，使用转义符运行任意 Perl 代码被视为作弊。重复替换（这很容易图灵完备）也超出了范围；整个工作应该在正则表达式中完成。这个问题更多的是关于正则表达式实际上有多强大的界限。

正如我所说的，第一个生产规则是无上下文的（因为左侧小于右侧），但对于第二个生产规则，它不是（因为左侧长度等于右侧）。

好吧，我们可以在这个陈述中对这个语法说些什么。它是否与上下文无关？

请解释如何设计上述语言的上下文相关语法。我是上下文敏感语法的新手。

我想编写一个匹配字符串的表达式语法，如下所示：

然而，问题是部分A可以包含来自部分B的关键字“ONE”或“ANOTHER” ，因此只有最后一次出现的选择关键字应该与部分B匹配。这里有一个例子：字符串

应该被解析成字段

pyparsing我尝试了表达式的“ ” -stopOn关键字：OneorMore

但这不起作用。对于示例字符串，我得到ParseException：

这是有道理的，因为在第一次出现而不是最后一次stopOn出现时停止。如何编写一个在最后一次出现时停止的语法？也许我需要求助于上下文相关的语法？choice

我正在尝试定义可用于描述以下类型表的语法：

**co1.......**col2......**col3......

价值.......价值.......价值

价值.......价值.......价值

价值.......价值.......价值

价值.......价值.......价值

......

**col1 和 **col2 是列名。该格式可以选择具有附加的预定义列（例如，假设 **col4 和 **col5 也可以包括在内）。我想编写一个输出这种格式的解析器。这种类型的表可以用 BNF 或 EBNF 来描述吗？

从我目前所读的内容来看，这是一个上下文相关的语法，因此不能用 BNF 或 EBNF 来描述（我认为这是因为如果 x-1 也这样做，行 x 将只包含 **col4）。这个对吗？是否有任何替代方法来描述上面的表格格式？

我对生成乔姆斯基所描述的上下文相关语言的元素感兴趣，如乔姆斯基语法分类中 “类型 - 1 语法”一节中所述。

（基本上，类似于标准的上下文无关语法，但允许在生产规则的左侧使用多个符号，包括终端）。

我知道 Prolog 中的确定子句语法，但我看不到这些语法与乔姆斯基的上下文相关语言之间的明显映射。是否有一种“通用”的方式来使用 DCG 框架来描述左侧带有多个符号的生产规则，或者我是否需要针对每种单独的语言使用一种特别的方法？

如果我有类似的东西var string = "var";，那么在第一个双引号之后规则会发生变化，并且与var文本开头的含义不同。在第二个双引号之后，事情又恢复了正常。怎么不考虑上下文？

（请不要在答案中使用这些箭头，而是尝试使用自然语言！）