D语言的语法真的是上下文无关的吗?

64

我几个月前在D的新闻组上发布了这篇文章,但出于某种原因,答案从未真正让我信服,所以我想在这里问一下。


D语言的语法显然是无环境限制的

然而,C++的语法不是(即使没有宏)。 (请仔细阅读!)

现在承认,我对编译器、词法分析器和解析器一无所知(官方)。所有我知道的都是从网上学到的。
这里是我理解的关于上下文的不太技术性的语言:

如果且仅当您在不需要“查看”任何其他地方的情况下就能理解给定代码片段的含义(但不一定是确切的行为),则该语言的语法是无环境限制的。

或者,更简略:

如果我不能仅通过查看它来告诉表达式的类型,则语法不能是无环境限制的。

例如,C++未通过无环境限制测试,因为confusing<sizeof(x)>::q < 3 > (2)含义取决于q的值

到目前为止,一切正常。

现在我的问题是:D语言是否也是如此?

在D中,哈希表可以通过Value[Key]声明创建,例如

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

静态数组可以使用类似的语法进行定义:

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

模板可以用来使它们变得混淆:

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.

这意味着我无法仅凭外观(即它可能是一个数字,它可能是一个数据类型,或者它可能是一个神知道什么的元组)来确定 T[0]U 的含义。我甚至无法确定表达式是否语法有效(因为int[U] 明显无效 - 你不能使用元组作为键或值的哈希表)。任何我尝试为 Test 制作的解析树都将无法有意义(因为它需要知道节点包含数据类型还是文字或标识符),除非它延迟结果直到了解 T 的值(使其依赖于上下文)。鉴于此,D 是否真的是上下文无关的,或者我对概念存在误解?为什么/为什么不?更新:我只是想评论一下:看到答案真的很有趣,因为:一些答案声称 C++ 和 D 不能是上下文无关的;一些答案声称 C++ 和 D 都是上下文无关的;一些答案支持 C++ 是上下文敏感的,而 D 不是;没有人声称 C++ 是上下文无关的,而 D 是上下文敏感的 :-) 我不知道自己是在学习还是变得更加困惑,但无论如何,我很高兴问了这个问题...感谢大家抽出时间来回答!

4
@VJo:它在将D语言的语法与C++进行比较(无上下文 vs. 有上下文)。我标记了C++而不是其他语言,因为D语言的网站将其与C++进行了比较。 - user541686
5
我们谈论的是模板还是语法本身?我认为 D 既有指针又有乘法,那么 a * b 是什么意思? - Bo Persson
3
好的,所以语法是上下文无关的,只是从语法中无法看出来?我能理解为什么会有人问这个问题。 :-) - Bo Persson
7
有趣的是,每个人都在这里提出自己对计算机科学的理论。我渴望知道谁是正确的,但我完全不知道。我最好不要猜测。 - Johannes Schaub - litb
4
我们需要让沃尔特回答这个问题。 - Arlen
显示剩余17条评论
7个回答

49

“无上下文”首先是生成语法的属性。这意味着非终止符可以生成的内容不会取决于非终止符所处的上下文(在非无上下文生成语法中,“给定非终止符生成的字符串”的概念通常很难定义)。这并不防止两个非终止符生成相同的符号串(因此,相同符号串可以出现在两个不同的上下文中,并具有不同的含义),与类型检查无关。

通常将无上下文的定义从语法扩展到语言,规定如果至少有一个无上下文语法描述该语言,则该语言为无上下文语言。

实际上,没有一种编程语言是无上下文的,因为像“必须在使用之前声明变量”这样的事情无法通过无上下文语法进行检查(它们可以通过其他类型的语法进行检查)。这并不是坏事,实际上要检查的规则分为两类:您想用语法检查的规则和您在语义处理中检查的规则(这种划分还允许更好的错误报告和恢复,所以您有时要接受比语法可能更多的内容,以便为用户提供更好的诊断)。

人们说C++不是无上下文的意思是在方便的情况下无法进行此划分(“方便”包括标准语言描述“遵循”,“我的解析器生成工具支持这种划分”等标准;允许语法模糊性并且语义检查可以解决歧义是在C++中进行划分并遵循C++标准的一种相对容易的方法,但是当您依赖不允许有歧义语法的工具时,这种方法不方便,如果您有这样的工具,则很方便)。

我不了解D足够,无法知道是否存在一种方便的方式将语言规则划分为带有语义检查的无上下文语法,但是您展示的远未证明不存在这种情况。


5
对于将纯语法检查和语义检查区分开来这一点的赞同,我认为这是一个相当主观的选择。 - BCS
很抱歉,我不知道“终端”和“生成式”的含义。 但无论如何,你的说法让我非常困惑:“实际上,没有一种编程语言是上下文无关的,因为像‘必须在使用之前声明变量’这样的事情无法通过上下文无关文法进行检查。”这难道不是语义问题(未解决的引用)而不是句法问题(“我无法弄清楚这是试图将两个东西相乘,尽管其中一个不存在”)吗? - user541686
11
语法是描述终结符串集合的一种方式(终结符集合为字母表)。生成式语法是你熟悉的语法类型。我的一个观点是,词汇、句法和语义之间的区分在很大程度上是任意的,并且主要是由于描述难度和工具可用性而驱动的。我的第二个主要观点是,无上下文语法有一个形式化的语法定义,如果没有明确说明在词汇和语义阶段要推进什么,你就处于“你知道我的意思”领域中。 - AProgrammer
不是我想要的答案,但看起来是目前最好的,+1。 - user541686
4
虽然这个答案是正确的,但有些人可能会感到困惑,因为AProgrammer使用了Chomsky的语言,其中一个语法“生成”一个字符串(字符串是由语法产生的),而不是更自然的解析的概念:在编译器中,我们不关心生成字符串,我们只关心解释字符串的反向过程。 - Qwertie

23

“被上下文无关所描述的特性是一个非常正式的概念;你可以在这里找到一个定义。请注意,它适用于语法:如果至少有一个上下文无关语法能够识别一个语言,则该语言被称为上下文无关语言。请注意,可能存在其他语法,可能是非上下文无关的语法,能够识别相同的语言。

基本上它意味着语言元素的定义不会因其周围的元素而改变。通过语言元素,我指的是像表达式标识符这样的概念,并不是程序中这些概念的具体实例,例如a + bcount

让我们尝试构建一个具体的例子。考虑这个简单的COBOL语句:

   01 my-field PICTURE 9.9 VALUE 9.9.

这里我定义了一个字段,即一个变量,它被定义为可以容纳一个整数位、一个小数点和一个小数位,并且其初始值为9.9。这个字段的非常简略的语法可能是:

field-declaration ::= level-number identifier 'PICTURE' expression 'VALUE' expression '.'
expression ::= digit+ ( '.' digit+ )

很不幸,可以跟在PICTURE后面的有效表达式与可以跟在VALUE后面的有效表达式不同。我可以将文法中第二个产生式改写为:

'PICTURE' expression ::= digit+ ( '.' digit+ ) | 'A'+ | 'X'+
'VALUE' expression ::= digit+ ( '.' digit+ )

如果这么做,我文法就变成了上下文有关文法,因为根据'PICTURE'或者'VALUE'后面是否出现,expression的语义会不同。然而,正如已经指出的那样,这并没有说明底层语言的任何信息。更好的替代方案是:

field-declaration ::= level-number identifier 'PICTURE' format 'VALUE' expression '.'
format ::= digit+ ( '.' digit+ ) | 'A'+ | 'X'+
expression ::= digit+ ( '.' digit+ )

这是一个无上下文限制的语法。

正如您所看到的,这与您的理解非常不同。考虑:

a = b + c;

如果没有查看a、b和c的声明,很难对这个语句做出太多评论。对于任何语言而言,只要这是一个有效的语句,那么这个语句本身并不意味着这些语言不是上下文无关的。可能让你感到困惑的是,上下文无关性与歧义性是不同的概念。以下是你的C++示例的简化版本:

a < b > (c)

这段代码含糊不清,仅凭它本身你无法确定它是一个函数模板调用还是一个布尔表达式。而前一个例子则不含糊; 从语法的角度来看,它只能被解释为:

identifier assignment identifier binary-operator identifier semi-colon

在某些情况下,您可以通过在语法层面引入上下文敏感性来解决歧义。我不认为以上模糊的示例是这种情况:在这种情况下,除非知道a是模板还是其他类型,否则无法消除歧义。请注意,当此类信息不可用时,例如当它取决于特定模板专业化时,语言提供了解决歧义的方法:这就是为什么有时必须使用typename来引用模板内的某些类型或在调用成员函数模板时使用template的原因。


1
我不明白你的COBOL代码中有什么不是上下文无关的(PICTURE后面跟着一个图片子句,VALUE后面跟着一个算术表达式,但它们之间的关系并不远到不能在上下文无关语法中实现)。另一方面,a<b>(c)的解析树取决于a的声明,这种情况很痛苦,因为它可能需要放在上下文无关语法中。 - AProgrammer
2
你的COBOL示例是错误的。在无上下文语法中,这是完全合法的。仅仅因为一个句法元素可以有多种解释,并不意味着该语言是上下文敏感的。查阅定义或阅读其他答案以获取更多详细信息。 - hammar
1
@Mehrdad:意义(又称语义)与语言的上下文敏感性无关,这是一个纯语法概念。 - hammar
3
@Mehrdad: 一种无上下文语法确实可能存在歧义,例如像int[T[0]]这样的字符串可以有多种解析方式。您可以在不考虑上下文的情况下确定其为有效的语法,但不能确定其含义。在一个有上下文语境的语言中,即使是这样一个句法元素的有效性也取决于其上下文。 - hammar
@Mehrdad 让我们在聊天室里继续这个讨论 - hammar
显示剩余9条评论

15

已经有很多好的回答了,但是由于您对语法、解析器和编译器等方面不太了解,让我通过一个例子来演示一下。

首先,语法的概念相当直观。想象一组规则:

S -> a T
T -> b G t
T -> Y d
b G -> a Y b
Y -> c
Y -> lambda (nothing)

假设你从S开始。大写字母代表非终结符,小写字母代表终结符。这意味着如果你得到一个由所有终结符组成的句子,你可以说语法生成了该句子作为语言中的“单词”。想象一下使用上述语法进行这样的替换(*短语*之间的短语是被替换的短语):

*S* -> a *T* -> a *b G* t -> a a *Y* b t -> a a b t

那么,我可以用这个语法来创建 aabt

好的,回到主线。

让我们假设有一种简单的语言。您有数字、两种类型(int和string)和变量。您可以在整数上进行乘法,在字符串上进行加法,但不能反过来进行操作。

首先需要的是一个词法分析器。通常这是一个正则文法(或等同于它的DFA,或者等同于正则表达式),用于匹配程序中的令牌。通常使用正则表达式来表示它们。在我们的示例中:

(我随意编写了这些语法)

number: [1-9][0-9]*    // One digit from 1 to 9, followed by any number
                       // of digits from 0-9
variable: [a-zA-Z_][a-zA-Z_0-9]*  // You get the idea. First a-z or A-Z or _
                                  // then as many a-z or A-Z or _ or 0-9
                                  // this is similar to C
int: 'i' 'n' 't'
string: 's' 't' 'r' 'i' 'n' 'g'
equal: '='
plus: '+'
multiply: '*'

whitespace: (' ' or '\n' or '\t' or '\r')*   // to ignore this type of token

现在,您已经拥有了一个常规的语法,可以对输入进行分词,但它并不理解其结构。

然后您需要一个解析器。解析器通常是上下文无关文法。上下文无关文法意味着,在文法中,您只有单个非终结符出现在文法规则的左侧。在本答案开头的示例中,规则如下:

b G -> a Y b

这使得语法上下文变得敏感,因为左侧有b G而不仅仅是G。这是什么意思呢?

当你编写语法时,每个非终结符都有一个含义。让我们为我们的示例编写一个上下文无关文法(|表示或。就像在同一行中编写多个规则):

program -> statement program | lambda
statement -> declaration | executable
declaration -> int variable | string variable
executable -> variable equal expression
expression -> integer_type | string_type
integer_type -> variable multiply variable |
                variable multiply number |
                number multiply variable |
                number multiply number
string_type -> variable plus variable

现在这个语法可以接受这段代码:
x = 1*y
int x
string y
z = x+y

从语法上讲,这段代码是正确的。那么,让我们回到什么是无上下文语法的意思。正如你在上面的例子中看到的,当你展开executable时,你会生成一个形式为variable = operand operator operand的语句,而不考虑你所在代码的哪个部分。无论是开始还是中间,无论变量是否被定义,或者类型是否匹配,你都不知道也不关心。

接下来,你需要语义。这就是上下文敏感语法发挥作用的地方。首先,让我告诉你,在现实中,没有人真正编写上下文敏感语法(因为解析它太困难了),而是编写解析输入时解析器调用的一些代码片段(称为动作例程,虽然这不是唯一的方法)。然而,从形式上讲,你可以定义所有你需要的。例如,为了确保在使用变量之前定义它,而不是这样

executable -> variable equal expression

你需要有类似于以下的东西:

你必须拥有类似于以下的东西:

declaration some_code executable -> declaration some_code variable equal expression

虽然更加复杂,但要确保声明中的变量与正在计算的变量匹配。

总之,我只是想给你一个想法。所以,所有这些都是上下文敏感的:

  • 类型检查
  • 函数参数的数量
  • 函数的默认值
  • 如果代码中obj.member中存在memberobj
  • 几乎所有不像:缺少;}

我希望你知道它们之间的区别(如果你不知道,我很愿意解释)。

所以总结一下:

  • 词法分析器使用正则语法对输入进行标记化
  • 解析器使用上下文无关文法来确保程序处于正确的结构中
  • 语义分析器使用上下文相关文法进行类型检查、参数匹配等等

然而,并不总是这样。这只是向你展示了每个级别需要变得更强大才能做更多事情。然而,上述每个编译器级别实际上都可以更强大。

例如,我不记得的一种语言,使用括号进行数组订阅和函数调用,因此需要解析器查找变量的类型(上下文相关的相关内容)并确定要采取哪个规则(function_call或array_substitution)。

如果您设计一个具有重叠的正则表达式的词法分析器,则还需要查找上下文以确定正在匹配哪种类型的标记。

回答您的问题!通过您提到的示例,很明显c++语法不是上下文无关的。至于D语言,我完全不知道,但现在你应该能够理性思考了。这样想:在上下文无关文法中,非终结符可以扩展而不考虑任何东西,但只考虑语言的结构。就像你说的那样,它会扩展,而不“看”其他地方。

一个熟悉的例子是自然语言。例如,在英语中,你会说:

sentence -> subject verb object clause
clause -> .... | lambda

好的,这里的非终结符是sentenceclause。使用这个语法,你可以创建这些句子:

I go there because I want to

或者

I jump you that I is air

如您所见,第二个句子有正确的结构,但是没有意义。就上下文无关语法而言,意义并不重要。它只是将verb扩展为任何动词,而不“查看”其余部分的句子。
因此,如果您认为D必须在某个时候检查其他地方的定义方式,仅仅为了说程序在结构上是正确的,那么它的语法就不是上下文无关的。如果您隔离代码的任何部分,它仍然可以说它在结构上是正确的,那么它就是上下文无关的。

展示上下文无关文法和上下文有关文法的区别只需要三行 :D。为创造一堵文字墙而努力的人点赞。"上下文有关文法是将特定的终端/非终端组合扩展到另一个序列,而上下文无关文法只是将一个非终端扩展到一个序列" - CoffeDeveloper
3
@Dariooo,即使你用数学方式写出1行代码,但大多数人仍需要解释才能理解。;) 感谢你的点赞。 - Shahbaz

10

D语言的词法分析器中存在一个结构体:

string ::= q" Delim1 Chars newline Delim2 "

其中Delim1和Delim2是匹配标识符,而Chars不包含换行符Delim2。

这个结构是上下文敏感的,因此D的词法语法是上下文敏感的。

我已经有几年没有太多接触D的语法了,所以我无法立即记住所有的问题点,甚至不确定它们是否使D的解析器语法上下文敏感,但我认为它们不会。从回忆中,我会说D的语法是上下文无关的,不是任何k的LL(k),并且它有一个非常混乱的模棱两可的数量。


1
我记得语言理论中的一个事实是,一般来说,标识符stuff sameidentifier不是上下文无关的。在发布之前,我通过泵引理将上述产生式规则运行了一遍,以确保其正确性。 - Ellery Newcomer
1
投票支持,因为这是唯一真正尝试回答问题的回复。 - johncip

8
如果我需要,我无法仅凭观察就能确定表达式的类型,那么语法就不能是上下文无关的。
不,这完全是错误的。如果你无法仅凭观察和解析器的当前状态(我在函数中,在命名空间中等)来确定它是否是一个表达式,那么语法就不能是上下文无关的。
然而,表达式的类型是一种语义含义,而不是句法含义,解析器和语法对类型、语义有效性以及您是否可以将元组作为哈希映射中的值或键,以及是否在使用之前定义了该标识符并不关心。
语法不关心它的含义,或者它是否有意义。它只关心它“是什么”。

@Hans:我很确定context只包括“到目前为止已经声明了哪些标识符?”这样的内容。LALR语法是上下文无关的,但它们仍然使用解析器状态来确定含义。 - Puppy
没有任何东西可以阻止一个字符串被两个不同的非终结符在 CFG 中生成。因此,仅仅查看该字符串并不能表明它是由哪个非终结符生成的。你需要一些上下文。但是,在 CFG 中需要考虑的上下文比更强大的语法更加局部化。 - AProgrammer
@DeadMG: “语法并不关心它的意思,或者是否有意义。它只关心它是什么。” --> 我有点困惑。所以你的意思是 omg(!) 符合 D 语法吗?那个字符串中的所有内容看起来都没问题,除了感叹号既不是标识符也不是数字…… - user541686
我对D语言的语法不够了解,无法确定给定字符串的情况。 - Puppy

6

要回答编程语言是否是上下文无关的问题,首先必须确定在语法和语义之间划分的界限。以C语言为极端例子,程序在某些整数类型溢出后使用其值是非法的。显然,这不能在编译时检查,更不用说解析时了:

void Fn() {
  int i = INT_MAX;
  FnThatMightNotReturn();  // halting problem?
  i++;
  if(Test(i)) printf("Weeee!\n");
}

作为其他人指出的一个不太极端的例子,使用规则前的减速不能在上下文无关语法中强制执行,因此如果您希望保持语法的上下文无关,则必须将其推迟到下一步。
作为实际定义,我会从这个问题开始:您是否可以正确和明确地确定所有正确程序的解析树,并且对于所有不正确的程序(语言要求拒绝),要么将它们拒绝为语法无效,要么生成可以被后续处理识别为无效并拒绝的解析树? 考虑到 D 语法的最正确规范是一个解析器(我记得是一个 LL 解析器),我强烈怀疑它实际上符合我提出的定义的上下文无关性。
注意:以上内容并未说明语言文档或特定解析器使用的语法,只说明上下文无关语法是否存在。此外,关于 D 语言的唯一完整文档是编译器 DMD 的源代码。

+1关于语法和语义的有趣观点。然而:“您能够使用上下文无关文法正确且明确地确定所有正确程序的解析树吗?”-->由于关联数组和静态大小数组不属于同一解析树(它们使用不同的语法进行定义),因此在模板中使用时,根据上下文需要进行潜在的转换。当然,编译器会正确编译所有内容,但初始解析树并不正确。这是上下文无关的吗?对我来说不是,但我不确定。 - user541686
关于我的溢出示例;我得检查一下,即使其结果从未被使用,允许溢出甚至可能是非法的。另一方面,这并不改变示例的重点。 - BCS
@Mehrdad:这仅意味着文档语法(已知错误:例如,a*b=c;在该语法中是模棱两可的,但由DMD无歧义地解析)不是上下文自由的。通过对语法进行一些微不足道的调整,您可以合并产生式,使其变得无歧义。您不一定会知道[]中的内容是什么,但您将正确地解析它。 - BCS
在D语言中,a*b=c;是将变量b声明为指向a的指针,并用表达式c进行初始化。这是根据定义的规定;如果a不能解析为某种类型,则程序是非法的,即使a * b作为乘法表达式返回可以分配给c的值。对于已分配的乘法表达式,您需要使用括号。也许这仍然不是上下文无关的,但a*b=c;不是一个悬而未决的语句。 - Bolpat
@Bolpat 如果我没记错的话,当我发表那个评论大约9年前,文档中的语法技术上允许 MulExp = Exp; 的解析。但是就编译器的解释而言,您是正确的;它是无歧义的。这实际上是我的观点;文档中的语法和源代码中的语法并不相同。 - BCS

4

这些答案让我感到头疼。

首先,低级语言的复杂性以及确定它们是否为上下文自由语言的困难之处在于,你所编写的语言通常需要经过多个步骤处理。

在C++中(顺序可能错乱,但不应该影响我的观点):

  1. 它必须处理宏和其他预处理器内容
  2. 它必须解释模板
  3. 最后它才会解释你的代码。

因为第一步可以改变第二步的上下文,第二步可以改变第三步的上下文,所以你编写的语言(包括所有这些步骤)是上下文敏感的。

人们试图捍卫一种语言(声称它是上下文自由的)的原因是,因为唯一存在上下文的例外是可追踪的预处理器语句和模板调用。你只需要遵循两个受限制的例外规则来假装该语言是上下文自由的。

大多数语言总体上都是上下文敏感的,但大多数语言仅有这些微小的例外,可以被视为上下文自由的。


我希望在学完编译器等相关课程三年前看到这个问题。我记得在学校理解这些东西很好,但由于没有对编译器产生浓厚的兴趣,恐怕已经多年没有学习了。 - Sophie McCarrell

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接