首页 文章

上下文敏感度与歧义

提问于
浏览 次
14

我对上下文敏感度和模糊性如何相互影响感到困惑 .

我认为是正确的是：

歧义：

模糊语法导致使用左或右派生构造多个解析树 . 所有可能的语法都含糊不清的语言是一种含糊不清的语言 .

例如，C是一种含糊不清的语言，因为x * y总是意味着两种不同的东西，如：Why can't C++ be parsed with a LR(1) parser?中所述 .

上下文灵敏度：

上下文敏感语法具有规则，其中这些规则的左侧可以包含（非）终端符号，除了在不同类型语法的所有规则的lhs内所需的一个非终结符号之外 . 这意味着您不能在降序时替换非终结符 . 相反，你必须先看看周围的非终结者 .

现在困扰我的是那些或多或少说上下文敏感的解析器可以解析像x * y这样的歧义的语句 . 例如，在上面的链接问题中，声明"... a parser that does [decorating a syntax tree while creating it] isn't context free, and LR parsers (the pure ones) are context free."在我看来，这意味着上下文敏感的解析器（与无上下文解析器相反？）可以做到这一点 . 另一个例子是Is any part of C++ syntax context sensitive?，其中这个问题用"Yes ..."回答 . 同样在这里：what is an ambiguous context free grammar?

我不明白这个C歧义与上下文敏感性有什么关系 . 我不认为有任何上下文敏感的语法可以处理这种歧义 . 例如，如果你采用像Typedef，<other> ，PointerDeclaration - > Ident“”Ident这样的虚构规则

然后你仍然无法确定（使用纯解析）在Typedef期间是否使用了具体的第一个Ident（例如“x”）（例如typedef double x;） .

因此，可能在链接的问题中使用术语“上下文敏感性”，尽管意味着像上下文依赖一样简单（例如，需要比简单解析器提供的更多信息） . 或者“真实的”上下文敏感性“与歧义之间是否有任何联系 .

Edit 更具体的问题：在无上下文语法中是否存在任何可以通过使用上下文相关语法处理的歧义 . 这个问题发生在我身上，因为在链接的问题中，它听起来像C模糊性有时被称为上下文敏感性问题 .

Edit2 附加信息：第346页上的书Computer Systems指出，具有相同数量的实际和形式参数的要求可以由上下文相关语法表达 . 但这非常麻烦，因为你需要很多复杂的规则 . 但也许这也适用于前面提到的C模糊性 . 所以我们有像这样的规则

“Typedef double x”，<other> ，PointerDeclaration - >“x”“”Ident

当然，这些规则将非常有限，你需要大量的表达每种可能性 . 至少这可能是问题答案的一种方法，如果（理论上）无上下文的自由模糊可以用上下文敏感规则的使用来代替

c++ grammar ambiguity

3 回答

  • 5

    上下文敏感性和模糊性完全正交 . 存在模糊的无上下文语言和明确的上下文敏感语言 .

    context-sensitive language 是一种可以通过上下文相关语法（CSG）解析的形式语言 . 每个 context-free language 也是一种上下文敏感语言，因为无上下文语法是简化的上下文相关语言 . 不是每种形式语言都是上下文敏感的;有些语言甚至连CSG也无法描述 .

    回复于
  • 0

    如果要使用无上下文解析器解析上下文相关语言，可以定义一个无上下文语法，该语法接受上下文相关语言的超集（因为它们功能较弱） . 因为您接受超集，所以可能会出现歧义或误报结果，必须在解析后解决 .

    Example One: a XML-like language ，允许任何标签名称 . 因为无上下文语法不能解析由两个重复单词w = {a，b}组成的句子ww，所以它也无法解析ID相等的 <ID></ID> . 因此，定义了一个接受超集的无上下文语法：

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

    这显然解析了一个人不想要的句子，因此必须在 open 和 close 中对等效ID进行额外检查 .

    Example Two: C-like Typedef 用一种非常简单的语言 . 想象一下只包含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 . 您可以为一般情况编写上下文敏感语法（即使它必须绝对不直观），但您不能编写无上下文语法 .

    Regarding your Edit 1: 我希望上一个例子回答这个问题 .

    Regarding your Edit 2: 还有另外一些技巧如何表达，所以规则不是那么有限，但它们通常令人兴奋和IMO这就是没有人使用CSG形式主义的原因 .

    注意：上下文敏感语法相当于线性有界自动机，无上下文语法相当于下推自动机 . 说上下文无关的解析器与上下文相关的解析器相反是不对的 .

    回复于
  • 4

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

    回复于

相关问题