问题标签 [compiler-theory]

出于好奇，我想知道解析 C++ 的一些“理论”结果是什么。

让 n 是我的项目的大小（例如，在 LOC 中，但由于我们将处理 big-O，所以它不是很重要）

• C++ 是否在 O(n) 中解析？如果不是，那么复杂性是多少？
• C（或 Java 或其语法意义上的任何更简单的语言）是否在 O(n) 中解析？
• C++1x 会引入更难解析的新特性吗？

参考将不胜感激！

是否有任何编程语言允许名称包含空格？（按名称，我指的是变量、方法、字段等）

澄清

当我提到交叉编译时，我的意思是从一种语言到另一种语言（想想 GWT），而不是从主机平台到目标平台。

背景

我正在开发一种交叉编译为 Java 的阿拉伯语编程语言，这为我节省了特定于平台的麻烦。现在我不得不搁置它并出于各种原因转向交叉编译到C。

我想开发一个单独的库，在编译时将其替换为运行它的系统的等效库。

例如，如果程序员用阿拉伯语编程语言编写一个GUI绘图函数并编译，在Windows下编译会交叉编译成win32代码，在Gnome下编译GTK+，在KDE下编译Qt等。图书馆也是如此。

问题

是否值得通过所有这些麻烦来结束编译的可执行文件，或者我最好使用虚拟机方法？选择其中一个的优点和缺点（从语言开发人员的角度而不是使用该语言的程序员的角度）？还有其他我需要考虑的因素吗？

任何进一步阅读的参考链接将不胜感激:)

在大学时我主修编译器理论和语法，因此在这方面有很好的背景（虽然很久以前），并且知道创建编译器是一项艰巨的任务，至少对于像 C++ 这样的语言来说是这样。

因此，我对似乎由个人而不是在公司工作的大量人员创建的大量编程语言感到困惑。例如 Ruby，根据维基百科，它是由一个人创建的——我不知道这种语言也许它非常简单，但我的观点是那里有大量的自创语言。

那么，作为一个个体，如何去创造自己的语言（这不是太简单以至于毫无用处）而不是花费一生来做这件事呢？

有没有关于这个主题的好书（不是关于编译器和一般的规范）？

我有一个问题，我似乎无法解决它，所以我希望这里的某个人能够帮助我。

我正在为 miniGLSL 编写一个编译器，到目前为止一切都很好。我现在需要输出到 ARB 片段程序，但问题是，我必须定位的 ARB 不支持分支。（支持指令的完整列表可在此处找到http://petewarden.com/notes/archives/2005/05/fragment_progra_2.html）。

为了模拟 if/else，我一直在使用 CMP 程序，如下所示（假设 0 或更大 = true，否则为 false。// 表示注释，因为 # 导致此处格式错误）：

进入 ARB 片段：

这是关于在我意识到我的代码将开始变得非常丑陋之前我得到的地方。每个级别的 if/else 都将引入不断堆叠的比较，此外，最后一个 else 要求我重新评估 cond2，或使用另一个寄存器。我知道我可能在这里做错了什么，但我不确定是什么。我尝试过使用计数器，尝试添加 if/else 块、anding、oring 等先前阶段的结果，但我找不到如何将 if/else 块转换为 ARB 片段程序集的好的解决方案。 t 真的在越来越多的 CMP 声明堆栈上。有谁知道如何使这更简单，以便我的编译器可以以编程方式输出？在这一点上，我不太担心优化，我只是想让它发挥作用。

谢谢

有谁知道任何讨论内联算法的论文？和密切相关的是，父子图与调用图的关系。

背景：我编写了一个编译器，Ocaml其中积极地内联函数，主要是由于这个和其他一些优化，它为我的编程语言在许多情况下（包括甚至C）生成比大多数其他语言更快的代码。

问题 #1：该算法在递归方面存在问题。为此，我的规则只是将孩子内联到父母中，以防止无限递归，但这排除了兄弟函数相互内联一次。

问题 #2：我不知道优化内联操作的简单方法。我的算法对于函数体的可变表示是必不可少的，因为似乎根本不可能做出有效的函数内联算法。如果调用图是一棵树，很明显自下而上的内联是最佳的。

技术信息：内联由许多内联步骤组成。问题是步骤的顺序。

每个步骤的工作原理如下：

• 我们通过用实参替换类型参数和值参数来制作要内联和 beta-reduce 的函数的副本。
• 然后，我们将 return 语句替换为对新变量的赋值，然后跳转到函数体的末尾。
• 然后，对该函数的原始调用将被此主体替换。
• 然而我们还没有完成。我们还必须克隆该函数的所有子函数，同时对它们进行 beta 缩减，并将克隆重新作为调用函数的父级。

克隆操作使得内联递归函数变得极其困难。保留已在进行中的内容的列表并仅检查我们是否已经在处理此调用的常用技巧在幼稚的形式中不起作用，因为递归调用现在被移动到被填充到调用中的 beta-reduced 代码函数，并且递归目标可能已更改为克隆的孩子。然而，在调用父级时，子级仍在调用调用其子级的原始父级，现在递归的展开不会停止。如前所述，我打破了这种回归，只允许内联对孩子的递归调用，防止兄弟递归被内联。

由于需要garbage collect未使用的函数，内联的成本变得更加复杂。由于内联可能是指数级的，因此这是必不可少的。如果对一个函数的所有调用都是内联的，如果该函数还没有被内联，我们应该删除它，否则我们将浪费时间内联到一个不再使用的函数。实际上跟踪谁调用了什么是极其困难的，因为当内联时，我们不是在使用实际的函数表示，而是一个“未分解”的表示：例如，指令列表正在按顺序处理并建立一个新列表，并且在任何一个时间点都可能没有一个连贯的指令列表。

在他的 ML 编译器中，Steven Weeks 选择使用一些重复应用的小优化，因为这使得优化易于编写和控制，但不幸的是，与递归算法相比，这错过了很多优化机会。

问题 #3：什么时候内联函数调用是安全的？

笼统地解释这个问题：在惰性函数式语言中，参数被包装在闭包中，然后我们可以内联应用程序；这是 Haskell 的标准模型。然而，它也解释了为什么Haskell这么慢。如果参数已知，则不需要闭包，则可以直接将参数替换为其参数 where is 出现（这是正常顺序beta-reduction）。

但是，如果已知参数评估不是非终止的，则可以使用急切评估：为参数分配一次表达式的值，然后重用。这两种技术的混合是使用闭包，但将结果缓存在闭包对象中。尽管如此，GHC 还没有成功地生成非常高效的代码：这显然非常困难，尤其是在您进行单独编译的情况下。

在菲利克斯，我采取了相反的方法。我不是通过证明优化保留语义来要求正确性并逐渐提高效率，而是要求优化定义语义。这保证了优化器的正确操作，但代价是某些代码将如何表现的不确定性。这个想法是为程序员提供方法来强制优化器在默认优化策略过于激进的情况下符合预期的语义。

例如，默认的参数传递模式允许编译器选择是否将参数包装在闭包中，用参数替换参数，或者将参数分配给参数。如果程序员想要强制闭包，他们可以传入一个闭包。如果程序员想要强制进行急切评估，他们会标记参数var。

这里的复杂性远大于函数式编程语言：Felix 是一种带有变量和指针的过程语言。它也有 Haskell 风格的类型类。这使得内联例程极其复杂，例如，类型类实例尽可能替换抽象函数（由于调用多态函数时的类型特化，可能在内联时找到实例，所以现在我们有了一个新函数可以内联）。

为了清楚起见，我必须添加更多注释。

内联和其他一些优化，例如用户定义的术语减少、类型类实例化、用于变量消除的线性数据流检查、尾部记录优化，都是在给定函数上一次性完成的。

排序问题不是应用不同优化的顺序，问题是对函数进行排序。

我使用一种脑死亡算法来检测递归：我建立一个每个函数直接使用的所有内容的列表，找到闭包，然后检查函数是否在结果中。请注意，在优化过程中会多次建立使用集，这是一个严重的瓶颈。

不幸的是，函数是否递归可能会发生变化。递归函数可能在尾部记录优化后变为非递归函数。但是有一个更难的情况：实例化一个类型类的“虚拟”函数可以使看起来是非递归的递归。

至于兄弟调用，问题是给定 f 和 g 其中 f 调用 g 和 g 调用 f 我实际上想将 f 内联到 g 中，并将 g 内联到 f .. 一次。我的无限回归停止规则是，如果 f 是 g 的孩子，则只允许将 f 内联到 g 中，这不包括内联兄弟。

基本上我想“尽可能地”“扁平化”所有代码。

我提供了一些包含已知分隔数量的文本块的输入集。

我想制作一个自动生成 1 个或多个正则表达式的程序，每个正则表达式都匹配输入集中的每个文本块。

我看到了一些相对简单的方法来实现蛮力搜索。但我不是编译器理论方面的专家。这就是为什么我很好奇：

1）这个问题可以解决吗？还是有一些原则上不可能做出这样的算法？

2）是否有可能实现该算法的多项式复杂度并避免暴力破解？

假设你有这样的语法：

S→A

A→ E“=”E

在此示例中，S 派生序列 ( E"=" E)。然而，与此相反的是什么？也就是说，填空的合适词是什么：

“序列（E“=” E）_ __ _ __ S。

如果我们借用微积分的反义词，可以说 ( E"=" E)积分 S，但这似乎不对。

我想在 C++ 中生成具有唯一确定性名称的各种数据类型。例如：

目前我的编译器使用计数器合成名称，这意味着在不同翻译单元中编译相同数据类型时名称不一致。

这是行不通的：

1. 使用 ABI mangled_name 函数。因为它已经依赖于具有唯一名称的结构。通过假装结构是匿名的，可以在符合 C++11 的 ABI 中工作吗？

2. 模板，例如 struct2，因为模板不适用于递归类型。

3. 一个完整的修改。因为它给出的名字太长了（数百个字符！）

除了全局注册表（YUK！）之外，我唯一能想到的就是首先创建一个独特的长名称，然后使用摘要或散列函数来缩短它（希望没有冲突）。

实际问题：生成可以在类型为匿名的情况下调用的库，例如元组、求和类型、函数类型。

还有其他想法吗？

编辑：递归类型问题的补充说明。考虑定义这样的链表：

这实际上是需要的。它不起作用有两个原因：首先，您不能对 typedef 进行模板化。[不，您不能使用带有 typedef 的模板类，它不起作用] 其次，您不能将 list* 作为参数传递，因为它尚未定义。在没有多态性的 C 中，您可以这样做：

有几种解决方法。对于这个特定的问题，您可以使用 Barton-Nackman 技巧的变体，但它并不能一概而论。

有一个通用的解决方法，首先由 Gabrielle des Rois 向我展示，使用具有开放递归的模板，然后使用部分特化来关闭它。但这非常难以生成，即使我能弄清楚如何做到这一点，也可能无法阅读。

正确地做变体还有另一个问题，但这不是直接相关的（更糟糕的是，因为对声明具有可构造类型的联合的愚蠢限制）。

因此，我的编译器只是使用普通的 C 类型。无论如何，它必须处理多态性：编写它的原因之一是绕过包括模板在内的 C++ 类型系统的问题。这会导致命名问题。

我想为自定义标记语言编写一个编译器，我想获得最佳性能，我还想有一个良好的可扩展设计。

多范式编程语言 (C++) 更适合实现现代设计模式，但我认为这会稍微降低性能（例如考虑RTTI），这或多或少可能会使 C 成为更好的选择。

我想知道如果有人想创建一个快速、高效且设计良好的现代编译器（在作为软件符合现代软件工程原则的意义上），最好的语言是什么（C、C++ 甚至是客观的 C）。