6

是否有一个编程语言在语法和语义方面的复杂性的客观衡量标准，而不是该语言的使用复杂程度？

我读过很多主观评论，但很少有严谨的分析。

4

11 回答 11

10

语言的BNF是一个粗略的衡量标准 - 只是为了品尝 :-)

举几个例子，

于 2009-07-22T21:41:48.210 回答
6

我不清楚复杂性在应用于编程语言时甚至是一个定义明确的术语。

如果“客观”是指“定量”，您可以提出以下问题

  • 明确的语法有多大？

  • 一个有效的 yacc 语法有多大？

由于几乎没有一种语言具有正式的语义，因此很难进行任何定量研究。但你可以问

  • 相对于使用相同元语言（编写解释器的语言）的其他语言的解释器，该语言的最简单解释器有多大？该度量与 Kolmogorov 复杂性有些相关。

除了出于好奇之外，我不清楚这个问题是否值得问——很难想象有用的答案。

于 2009-07-22T21:34:13.030 回答
4

看看指称语义和操作语义：

指称语义是一种通过构建描述语言表达式含义的数学对象（称为指称）来形式化编程语言含义的方法。

编程语言的操作语义描述了有效程序如何被解释为计算步骤的序列。这些序列就是程序的含义。在函数式程序的上下文中，终止序列的最后一步返回程序的值。（一般来说，单个程序可以有许多返回值，因为该程序可能是不确定的，即使对于确定性程序，也可能有许多计算序列，因为语义可能无法准确指定达到该值的操作序列。）

于 2009-07-22T22:08:33.053 回答
3

我见过的语言最好的衡量标准是随机字符串成为有效程序的概率。Perl 是一门在这个规模上排名很高的语言，Ada 排名相当低。

这个指标的含义完全是另一个问题。

于 2009-07-22T21:31:07.840 回答
3

作为一般规则，语法或语义或实现越动态和抽象，语言就越复杂（不要像你所说的那样使用）。

因此，Java 是一种比 C 更复杂的语言，因为：

  1. C 的作用域规则简单，而 Java 的规则相对复杂
  2. 类型更复杂，方法解析和重载
  3. 继承、参数枚举和检查、方法重载等事情使编译过程更加复杂。

在此基础上，我认为 Python 比 Java 更简单，因为它的对象模型虽然复杂，但在简化为更简单的形式方面很简单。从时间和计算的角度来看，将给定语法转换为更简单形式的难易程度也可能是一个角度。

另一方面，像lisp这样的语言，有些人会认为使用起来很复杂，但非常简单。像 Haskell 这样的东西也是如此。

您可以通过以下方式之一测量复杂性，但不完整：

  1. 一个简单问题的关键字数量、代码行数和语义复杂性（如标识符解析）。斐波那契计算可能就是其中之一。比较常见算法的令人满意的有效实现。
  2. 什么时候发生？名称是在运行时后期绑定的，还是在编译时解析的？
  3. 如果没有给出标识符、类型和外部代码的所有事实，是否可以用一种以上的方式理解给定的代码片段？

有很多方法。您可以测量给定语法的编译过程的计算复杂度。

并非所有这些例子都是正确的。一些对象模型非常复杂，但速度非常快，因为它们使用了快速基础。自我可能就是一个例子。

于 2009-07-22T21:35:03.743 回答
1

我认为，如果您查看正确性证明领域，您会发现对语义复杂性的更详细分析。像 CSP（以及较小程度上的 Lambda 演算）这样的系统旨在通过分析易于处理。语言越接近底层形式系统的表达，从语义的角度来看，它就越简单。

反例类似于 C 编程语言。如果不知道它将在什么操作系统和硬件上运行，就不可能弄清楚 C 程序实际上做了什么。

于 2009-07-22T22:09:34.237 回答
1

I love Project Euler for evaluating this. :)

于 2009-07-22T21:49:09.003 回答
1

最简单的两件完全客观的事情是语言定义符号和关键字/保留词的数量，以及其 BNF 中产生的数量。

对于那些拥有它们的语言，您可以查看的另一件事是其标准文档的相对大小。不过，有些人会争辩说，并非所有标准文档都是在同一级别编写的。

于 2009-07-22T22:04:44.870 回答
1

正如其他用户发布的那样，关键字是衡量编程语言复杂程度的客观指标。语法/句法将描述代码结构的复杂程度（允许的关键字组合）。有一些与软件质量相关的代码指标来衡量一段代码的复杂程度。

在我看来，语义复杂性更难衡量。它与表达能力有关（编程语言级别越高，表达能力越强）。我认为尝试比较以不同语言实现的不同解决方案以衡量它们的表达能力是没有意义的（即使用欧拉项目问题实现 = 解决方案）。问题本身和每种编程语言范式都会使比较产生偏差。

在高级编程语言的情况下，我假设特定问题的可能实现的数量（从抽象的角度来看）是语义复杂性的一个很好的衡量标准。

对于低级编程语言，看看规范语言如何生成代码可能会很有趣（找到一个实现=给定问题的解决方案）。尽管如此，由于抽象有限，该度量似乎与软件质量代码度量密切相关。

如您所见，抽象和语义复杂性更难自动化（根据规范生成实现 = 解决方案）。这就是程序员的知识、智力和心理发挥作用的地方（人工智能还没有达到这一点）。

于 2016-04-19T19:01:47.523 回答
0

语言的使用有多复杂在某种程度上是主观的。

另一方面，可以回答有关语言语义有多复杂的问题，但只能与其他语言进行比较。然而，这些不一定有用。例如，我会给 Smalltalk 的语义复杂度为 1，而 C++ 的复杂度为 9。但是，我敢打赌，您正在阅读的浏览器是用 C++ 编写的，而不是 Smalltalk。

于 2009-07-22T21:24:33.047 回答
0

如果有这样一个客观的衡量标准，它对于评估为特定目的使用给定语言的效用或成本可能几乎没有用处。它可以帮助您排除空格或脑残，但这可以很容易地完成，而无需将资源花费在这样一个客观的衡量标准上——通过主观地观察源代码并意识到您永远不想认真地处理它。

大多数语言都会有很多积极和消极的一面，你需要权衡你想要实现的目标和需要满足的条件。

于 2009-07-22T21:25:09.660 回答