上下文敏感性与模糊度 [英] Context-sensitivity vs Ambiguity
问题描述
我认为正确的是：
歧义：
一个模糊的语法导致使用左或右导出构造多个解析树。
例如，C ++是一个模糊的语言，因为x * y总是意味着两个不同的东西，如下所述： a href =http://stackoverflow.com/questions/243383/why-c-cannot-be-parsed-with-a-lr1-parser>为什么C ++不能用LR（1）解析器解析？。
上下文敏感性：
上下文相关语法有规则，这些规则可以包含除了在不同种类的语法的所有规则的lhs内所需的一个非终结符之外的（非）终端符号。这意味着你不能只是在降序时替换非终结符。
现在让我烦恼的是那些或多或少说的上下文敏感解析器可以解析模糊性，如x * y。例如，在上述链接的问题中，声明... [在创建语法树时装饰语法树]的解析器不是上下文无关的，并且LR解析器（纯粹的）是上下文无关的。在我看来这意味着上下文敏感的解析器（与上下文无关的解析器相反）可以做到这一点。另一个示例是 C ++语法的任何部分是否对上下文敏感？这个问题回答是...。相同：什么是模糊的上下文无关语法？
我看不到这个C ++歧义与上下文相关。我不认为有任何上下文敏感的语法，可以处理这种歧义。例如，如果你使用虚拟规则像
Typedef，< other> *，PointerDeclaration - > Ident*Ident
，那么你还是不会能够确定（使用纯解析）在Typedef期间是否使用了具体的第一个Ident（例如x）（例如typedef double x;）。
所以有可能在链接的问题中使用术语上下文敏感性，尽管意味着简单的上下文依赖性（例如比简单解析器提供更多的信息）。
编辑更多指定问题：是否有任何种类的上下文敏感性这个问题发生在我身上，因为在链接的问题中，听起来像C ++歧义有时被称为上下文敏感性问题。
Edit2 附加信息：计算机系统说明了诸如具有相同数量的实际和形式参数的需求可以由上下文敏感的语法表示，但是这是非常繁琐的，因为你需要很多复杂的规则，但也许这也可能适用于前面提到的C ++歧义。所以我们有规则像
typedef double x，< other> *，PointerDeclaration - >x*Ident
当然，这样的规则将非常有限，表达一切可能性。至少这可能是一个解决问题的方法，如果（理论上）上下文无关的歧义可以用上下文相关规则的使用替换
上下文敏感性和歧义完全正交。存在歧义的上下文无关语言和无歧义的上下文敏感语言。
上下文敏感语言是一种可以解析的形式语言上下文敏感语法（context-sensitive grammar，CSG）。每个上下文无关语言也是一种上下文敏感语言，因为上下文无关语法是简化的上下文相关语言。不是每种形式语言都是上下文相关的;有甚至一个CSG不能描述的语言。
I'm confused about how context-sensitivity and ambiguity influence each other.
What i think is correct is:
Ambiguity:
An ambiguous grammar leads to the construction of more than one parse-tree using either left or right derivation. A language where all possible grammars are ambiguous is an ambiguous language.
For instance C++ is an ambiguous language because x * y always can mean two different things as discussed in: Why C++ cannot be parsed with a LR(1) parser?.
Context-sensitivity:
A context-sensitive grammar has rules where the left hand side of these rules may contain (non)terminal symbols additional to the one nonterminal required within the lhs of all rules of different kinds of grammars. Which means that you cannot just replace a nonterminal while descending. Instead you have to look at the surrounding nonterminals first.
Now what bothers me are statements that more or less say that context-sensitive parsers can parse ambiguities like x * y. For instance in the above linked question it is stated that "... a parser that does [decorating a syntax tree while creating it] isn't context free, and LR parsers (the pure ones) are context free." In my opinion this implies that context-sensitive parsers (the opposite of context-free parsers?) can do this. Another example would be Is any part of C++ syntax context sensitive? where this question is answered with "Yes ...". Same here: what is an ambiguous context free grammar?
I don't see what this C++ ambiguity has to do with context-sensitivity. I don't think that there is any context-sensitive grammar that can deal with this ambiguity. For instance if you take a fictional rule like Typedef, <other>*, PointerDeclaration -> Ident "*" Ident
then you still would not be able to determine (with pure parsing) whether the concrete first Ident (e.g. "x") was used during the Typedef (e.g. typedef double x;).
So is it possible that the term "context-sensitivity" is used within the linked questions although meaning something simple like context-dependency (e.g. more information needed than provided by a simple parser). Or is there any kind of connection between "real" context-sensitivity" and ambiguities.
Edit More specified question: Is there any kind of ambiguities within context-free grammars that can be dealt with by using context-sensitive grammars. This question occurs to me because in the linked questions it sounds like the C++ ambiguity is sometimes referred to as an context-sensitivity problem.
Edit2 Additional Info: The book Computer Systems states on page 346 that requirements such as having the same amount of actual and formal parameters can be expressed by context-sensitive grammars. But this is very cumbersome because you would need lots of complexe rules. But maybe this could also apply to the C++ ambiguity mentioned earlier. So that we have rules like
"Typedef double x", <other>*, PointerDeclaration -> "x" "*" Ident
Of course such rules would be very limited and you would need a huge amount to express every possibility. At least this could be an approach to the answer of the question if (theoratically) context-free free ambiguities can be replaced with the usage of context-sensitive rules
Context-sensitivity and ambiguity are entirely orthogonal. There exist ambiguous context-free languages and unambiguous context-sensitive languages.
A context-sensitive language is a formal language that can be parsed by a context-sensitive grammar (CSG). Every context-free language is also a context-sensitive language since context-free grammars are simplified context-sensitive languages. Not every formal language is context-sensitive though; there are languages that even a CSG cannot describe.
这篇关于上下文敏感性与模糊度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
