use*_*754 14 c++ grammar ambiguity
我对上下文敏感度和模糊性如何相互影响感到困惑.
我认为是正确的是:
歧义:
模糊语法导致使用左或右派生构造多个解析树.所有可能的语法都含糊不清的语言是一种含糊不清的语言.
例如,C++是一种含糊不清的语言,因为x*y总是意味着两种不同的东西,如下所述:为什么不能用LR(1)解析器解析C++？.
上下文灵敏度:
上下文敏感语法具有规则,其中这些规则的左侧可以包含(非)终端符号,除了在不同类型语法的所有规则的lhs内所需的一个非终结符号之外.这意味着您不能在降序时替换非终结符.相反,你必须先看看周围的非终结者.
现在困扰我的是那些或多或少说上下文敏感的解析器可以解析像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
当然,这些规则将非常有限,你需要大量的表达每种可能性.至少这可能是问题答案的一种方法,如果(理论上)无上下文的自由模糊可以用上下文敏感规则的使用来代替
上下文敏感性和模糊性完全正交.存在模糊的无上下文语言和明确的上下文敏感语言.
甲上下文有关语言是可以通过一个上下文有关文法(CSG)进行解析的正式语言.每种无上下文的语言也是一种上下文敏感语言,因为无上下文语法是简化的上下文敏感语言.不是每种形式语言都是上下文敏感的; 有些语言甚至连CSG也无法描述.