是D的语法真的上下文无关吗？ [英] Is D's grammar really context-free?

问题描述

我已经在几个月前在D新闻组发布了这个消息，但由于某种原因，答案从来没有说服我，所以我想我会在这里问。

---

D的语法显然无上下文/ a>。

然而，C ++的语法不是（即使没有宏）。（请仔细阅读）

em>现在批准，我什么也不知道（正式）关于编译器，词法分析器和解析器。所有我知道的是从我在网络上学到的。

这里是什么（我相信）我已经理解上下文，在不那么技术lingo：

语言的语法是无上下文的如果且只有，你总是可以理解的意思

或者，甚至在更少的地方严格：

语法不能是上下文无关的，如果我需要我不能告诉一个表达式的类型只是因此，例如，C ++失败了无上下文的测试，因为意思的意思是

confusing< sizeof（x）> :: q< 3> （2） 取决于 q 的值。

到目前为止，这么好。

现在我的问题是：同样可以说D吗？

在D中，散列表可以通过 Value [Key] 声明创建，例如

  int [string] peoplesAges; //将名称映射到年龄
  

静态数组可以用类似的语法定义：

  int [3] ages; // 3个元素的数组
  

并且模板可以使他们感到困惑：

 模板Test1（T ...）
 {
 alias int [T [0] 
} 
 
模板Test2（U ...）
 {
 alias int [U] Test2; // LGTM 
} 
 
 Test1！（5）foo; 
 Test1！（int）bar; 
 Test2！（int）baz; // 你猜怎么了？它是无效的代码。 
  

这意味着我不能说出 T [0 ] 或 U 只是通过查看（即它可以是一个数字，它可以是一种数据类型，是上帝知道的一个元组 - 什么）。我甚至不能告诉表达式是否语法有效（因为 int [U] 当然不是 - 你不能有一个hashtable元组作为键或值）。

我尝试对 Test 进行的任何解析树将会失败 （因为它需要知道节点是否包含数据类型与文字或标识符），除非它延迟结果，直到 T



鉴于此，D实际上是上下文无关的，还是我误解了这个概念？

为什么/为什么不？

---

：

我只是想我会评论：看到答案真的很有趣，因为：

• 有些答案声称C ++和D不能无上下文。


• 有些答案声称C ++和D都是


• 有些答案支持C ++对上下文敏感， C ++是上下文无关的，而D是上下文相关的： - ）

我不知道我是学习还是得到更困惑，但无论哪种方式，我很高兴我问这个...感谢你花时间回答，大家！

解决方案

无上下文是第一个生成语法的属性。这意味着非终端可以产生什么将不依赖于非终端出现的上下文（在非上下文无关的生成语法中，由给定非终端生成的字符串的概念通常是困难的界定）。这不妨碍由两个非终端生成相同的符号串（因此，相同的符号串出现在具有不同含义的两个不同的上下文中），并且与类型检查无关。

如果至少有一个上下文无关语法描述它，通常通过说一种语言是上下文无关的，从语法扩展到语言。

在实践中，没有编程语言是上下文无关的，因为像一个变量必须在使用之前必须声明这样的东西不能通过上下文无关的语法来检查（他们可以由一些其他种类的语法检查）。这是不错的，实际上要检查的规则分为两部分：那些你想检查的语法和那些你检查在语义通过（这个部门还允许更好的错误报告和恢复，所以你有时想要接受更多的语法，而不是为了给您的用户更好的诊断）。

人们通过说明C ++不是上下文无关的是以不方便的方式（以方便包括作为标准接近官方语言描述和我的解析器生成器工具支持那种分区）;允许语法是不明确的和语义检查要解决的歧义是一个相对容易的方法来做C ++和遵循C ++标准，但它是不方便的，当你依赖于不允许不明确的语法的工具，当你有这样的工具，它是方便的）。

我不知道足够D知道是否有一个方便的语言规则剪切上下文无关的语法与语义检查，但你显示的远不是证明的情况下没有。

I've posted this on the D newsgroup some months ago, but for some reason, the answer never really convinced me, so I thought I'd ask it here.

---

The grammar of D is apparently context-free.

The grammar of C++, however, isn't (even without macros). (Please read this carefully!)

Now granted, I know nothing (officially) about compilers, lexers, and parsers. All I know is from what I've learned on the web.
And here is what (I believe) I have understood regarding context, in not-so-technical lingo:

The grammar of a language is context-free if and only if you can always understand the meaning (though not necessarily the exact behavior) of a given piece of its code without needing to "look" anywhere else.

Or, in even less rigor:

The grammar cannot be context-free if I need I can't tell the type of an expression just by looking at it.

So, for example, C++ fails the context-free test because the meaning of confusing<sizeof(x)>::q < 3 > (2) depends on the value of q.

So far, so good.

Now my question is: Can the same thing be said of D?

In D, hashtables can be created through a Value[Key] declaration, for example

int[string] peoplesAges;   // Maps names to ages

Static arrays can be defined in a similar syntax:

int[3] ages;   // Array of 3 elements

And templates can be used to make them confusing:

template Test1(T...)
{
    alias int[T[0]] Test;
}

template Test2(U...)
{
    alias int[U] Test2;  // LGTM
}

Test1!(5) foo;
Test1!(int) bar;
Test2!(int) baz;  // Guess what? It's invalid code.

This means that I cannot tell the meaning of T[0] or U just by looking at it (i.e. it could be a number, it could be a data type, or it could be a tuple of God-knows-what). I can't even tell if the expression is grammatically valid (since int[U] certainly isn't -- you can't have a hashtable with tuples as keys or values).

Any parsing tree that I attempt to make for Test would fail to make any sense (since it would need to know whether the node contains a data type versus a literal or an identifier) unless it delays the result until the value of T is known (making it context-dependent).

Given this, is D actually context-free, or am I misunderstanding the concept?

Why/why not?

---

Update:

I just thought I'd comment: It's really interesting to see the answers, since:

• Some answers claim that C++ and D can't be context-free
• Some answers claim that C++ and D are both context-free
• Some answers support the claim that C++ is context-sensitive while D isn't
• No one has yet claimed that C++ is context-free while D is context-sensitive :-)

I can't tell if I'm learning or getting more confused, but either way, I'm kind of glad I asked this... thanks for taking the time to answer, everyone!

解决方案

Being context free is first a property of generative grammars. It means that what a non-terminal can generate will not depend on the context in which the non-terminal appears (in non context-free generative grammar, the very notion of "string generated by a given non-terminal" is in general difficult to define). This doesn't prevent the same string of symbols to be generated by two non-terminals (so for the same strings of symbols to appear in two different contexts with a different meaning) and has nothing to do with type checking.

It is common to extend the context-free definition from grammars to language by stating that a language is context-free if there is at least one context free grammar describing it.

In practice, no programming language is context-free because things like "a variable must be declared before it is used" can't be checked by a context-free grammar (they can be checked by some other kinds of grammars). This isn't bad, in practice the rules to be checked are divided in two: those you want to check with the grammar and those you check in a semantic pass (and this division also allows for better error reporting and recovery, so you sometimes want to accept more in the grammar than what would be possible in order to give your users better diagnostics).

What people means by stating that C++ isn't context-free is that doing this division isn't possible in a convenient way (with convenient including as criteria "follows nearly the official language description" and "my parser generator tool support that kind of division"; allowing the grammar to be ambiguous and the ambiguity to be resolved by the semantic check is an relatively easy way to do the cut for C++ and follow quite will the C++ standard, but it is inconvenient when you are relying on tools which don't allow ambiguous grammars, when you have such tools, it is convenient).

I don't know enough about D to know if there is or not a convenient cut of the language rules in a context-free grammar with semantic checks, but what you show is far from proving the case there isn't.

这篇关于是D的语法真的上下文无关吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！