16

我对上下文敏感性和歧义如何相互影响感到困惑。

我认为正确的是：

歧义：

模棱两可的文法会导致使用左派生或右派生构造多个分析树。所有可能的语法都是模棱两可的语言是模棱两可的语言。

例如，C++ 是一种模棱两可的语言，因为 x * y 总是可以表示两种不同的东西，如下所述：为什么不能用 LR(1) 解析器解析 C++？.

上下文敏感性：

上下文相关文法具有规则，其中这些规则的左侧可能包含（非）终结符号，除了在不同类型文法的所有规则中所需的一个非终结符之外。这意味着您不能在下降时仅替换非终结符。相反，您必须先查看周围的非终结符。

现在困扰我的是或多或少说上下文敏感的解析器可以解析像 x * y 这样的歧义的语句。例如，在上面链接的问题中，声明“......一个 [在创建语法树时装饰语法树] 的解析器不是上下文无关的，而 LR 解析器（纯解析器）是上下文无关的。” 在我看来，这意味着上下文敏感的解析器（与上下文无关的解析器相反？）可以做到这一点。另一个例子是 C++ 语法是否对上下文敏感？这个问题的答案是“是的......”。同样在这里：什么是模棱两可的上下文无关语法？

我看不出这种 C++ 歧义与上下文敏感性有什么关系。我认为没有任何上下文相关的语法可以处理这种歧义。例如，如果您采用 Typedef、<other>*、PointerDeclaration -> Ident "*" Ident 之类的虚构规则

那么您仍然无法确定（通过纯解析）在 Typedef 期间是否使用了具体的第一个 Ident（例如“x”）（例如 typedef double x;）。

因此，是否有可能在链接的问题中使用术语“上下文敏感性”，尽管其含义很简单，例如上下文相关性（例如，需要比简单解析器提供的更多信息）。或者“真实的”上下文敏感性”和歧义之间是否存在任何联系。

编辑更具体的问题：上下文无关语法中是否存在任何可以通过使用上下文相关语法来处理的歧义。这个问题出现在我身上是因为在链接的问题中，听起来 C++ 的歧义有时被称为上下文敏感问题。

Edit2附加信息：《计算机系统》一书在第 346 页上指出，诸如具有相同数量的实际参数和形式参数之类的要求可以通过上下文相关的语法来表达。但这非常麻烦，因为您需要很多复杂的规则。但也许这也适用于前面提到的 C++ 歧义。所以我们有这样的规则

"Typedef double x", <other>*, PointerDeclaration -> "x" "*" Ident

当然，这样的规则是非常有限的，你需要大量的资金来表达每一种可能性。如果（理论上）上下文无关的歧义可以用上下文相关规则的使用来代替，至少这可能是解决问题的一种方法

4

3 回答 3

5

上下文敏感性和歧义是完全正交的。存在歧义的上下文无关语言和明确的上下文敏感语言。

上下文相关语言是一种可以由上下文相关文法 (CSG) 解析的形式语言。每个上下文无关语言也是上下文相关语言，因为上下文无关语法是简化的上下文相关语言。不过，并非每种形式语言都是上下文相关的。有些语言连 CSG 都无法描述。

于 2011-05-22T13:07:27.153 回答
4

如果你想用上下文无关的解析器来解析上下文相关的语言，你可以定义一个上下文无关的语法，它接受上下文相关语言的超集（因为它们的功能不那么强大）。因为您接受超集，您可能会得到歧义或误报结果，必须在解析后解决。

示例一：一种类似 XML 的语言，允许使用任何标签名称。因为上下文无关文法无法解析包含两个重复单词w = {a,b}+ 的句子ww，所以它也无法解析ID 相等的地方。因此，定义了一个接受超集的上下文无关文法：<ID></ID>

start -> elem
elem  -> open elem* close
open  -> '<' ID '>'
close -> '</' ID '>'
ID    -> ('a' / 'b')+

这显然会解析不需要的句子，因此必须额外检查等效的openID close。

示例二：一种非常简单的语言的类 C 类型定义。想象一种只包含 typedef、指针和乘法的语言。它只有两个 ID，a并且b. 这种语言的一个例子：

typedef a;
b * a;                    // multiplication
a * b;                    // b is pointer to type a

上下文无关语法如下：

start                     -> typedef multiplication-or-pointer+
typedef                   -> 'typedef' ID ';'
multiplication-or-pointer -> ID '*' ID ';'
ID                        -> 'a'
ID                        -> 'b'

该文法不接受超集，但它不知道看到的是乘法还是指针，因此它是模棱两可的。因此，必须检查结果并决定是乘法还是指针，这取决于 typedef 中定义的类型。

使用上下文相关的语法可以做更多的事情。非常粗略（且不精确）：

start                                     -> typedef multiplication-or-pointer+
typedef                                   -> 'typedef' ID ';'
multiplication-or-pointer                 -> pointer / multiplication
'typedef' 'a' ';' WHATEVER pointer        -> 'a' '*' ID   
'typedef' 'b' ';' WHATEVER pointer        -> 'b' '*' ID   
'typedef' 'b' ';' WHATEVER multiplication -> 'a' '*' ID
'typedef' 'a' ';' WHATEVER multiplication -> 'b' '*' ID
ID                                        -> 'a'
ID                                        -> 'b'

请注意，我在这里显示的内容并不准确，因为我限制了 ID 的数量。通常，可以有无限数量的 ID。您可以为一般情况编写上下文相关的语法（即使它必须绝对不直观），但您不能编写上下文无关的语法。

关于您的编辑 1：我希望前面的示例能回答这个问题。

关于您的编辑 2：还有其他技巧如何表达，因此规则不受限制，但它们通常令人兴奋，IMO 这就是没有人使用 CSG 形式主义的原因。

注意：上下文相关文法等价于线性有界自动机，上下文无关文法等价于下推自动机。说上下文无关解析器是上下文敏感解析器的对立面是不对的。

于 2014-06-10T11:15:28.887 回答
0

编译器不使用“纯”（无论这可能意味着什么）语法进行解析——它们是真实世界的程序，做所有真实世界程序所做的事情——在某些情况下应用启发式。这就是为什么不使用编译器生成器生成 C++ 编译器（以及大多数其他语言的编译器，除了本科生练习）。

于 2011-05-22T16:32:38.020 回答