问题标签 [compiler-theory]

我们正在为 Al Aho 的编译器类编写一个编译器，并且我们正在考虑使用以下代码来生成我们的 AST。这里有一些背景。我们希望将范围规则实现为 name-id 映射堆栈，并且我们希望在进入并生成声明的节点之前将一组映射推送到堆栈上。

那么，这是我的问题。这是如何运作的？这段代码什么时候执行？当解析器减少这个产生时它会被执行吗？哪一部分发生在什么时候？我应该去办公时间看看吗？

我一直在上编译器和工具课程（本学期）。我已经阅读了中间代码生成，并且还看到了 DAG 表示以获得最优性。编译器清楚的一点是，无论生成什么中间代码，它都必须映射到系统的指令集，这样我们才能运行我们的程序。

假设我为特定架构（比如 A）编写了一个编译器，其中两个数字之间的加法是ADD R1、R2、R3（来自 A 的指令集），其中 R1-是目标，R2、R3 是来源。我已经映射了这些指令，也就是说，当我想添加中间代码中表示的两个数字（无论其类型如何，为简单起见）时，我将运行ADD操作码！。

假设新架构已经上市，其中两个数字相加具有不同的指令集，例如AD R1,R2,R3。现在显然我的编译器不会添加数字！

现在我的问题是，当我为我的编程语言编写编译器时，我必须将所有架构与它们的指令集一起添加，以便我的编译器正确地完成它需要做的事情？如果是这样，有什么方法可以优化这个效果？因为添加所有指令集几乎会降低我的性能。

纠正如果我错了！

定义问题是数据流分析中最基本的问题之一。给定一个包含变量定义和用途的控制流图，问题导致计算哪些变量定义可以达到特定用途。

例如考虑流程图：

块 3 中变量 x 的使用可以通过块 1 或块 2 中的定义来实现。

计算哪些定义可以使用的算法是经典的数据流问题。使用龙编译器书（新版）中的符号，到达定义数据流问题如下：

域：定义集（例如 {x <- .., ...}）
方向：前向
传递函数：fb(x) = gen(B) U (x - kill(B)) 其中 gen(B) 是块 B 生成的定义集并 kill(B) 块 B 杀死
的
定义集流向块是前代块定义的联合。
方程：OUT[B] = fb(IN[B]), IN[B] = U(P in pred)OUT[P]
初始化：OUT[B] = {}

但是，并非所有定义都相同。例如，块 1 中的定义可能永远无法在块 3 中使用，因为它可能会被块 2 中的定义杀死。另一方面，块 2 中的定义如果被执行，将保留其值直到它在块中使用3.

我想找到从定义到用法的任何路径上都没有杀死定义的用法的到达定义。我的问题是是否存在类似的数据流问题（可能是传播等）。在数据流分析方面如何解决。

我确实有一个可能的解决方案，但如果解决方案已经存在，我不想重新发明轮子。

我正在准备关于语言、语法、解析和编译器的考试。这不是我真正喜欢的茶，我发现大多数资源都使用数学语言来定义不同的交易术语并解释我需要了解的不同概念，而不是坚持使用我非常喜欢的英语或法语。因此，我在寻找继续学习的动力和简单地理解理论方面都遇到了一些麻烦。所以这是我的问题：你们中有人知道我在哪里可以找到一种“有趣”的方式来学习这一切吗？或者至少，也许是一种更“具体”、更少“数学”的方式来处理这个主题。

我需要涵盖以下内容，因此欢迎任何关于这些主题的内容！

• 解析（LR，LL，...）
• 语法（上下文无关，确定性，...）
• 语法分析 静态流分析
• 关于软件维护和对用户界面的依赖性的影响分析
• 动态分析

这里有一些资源可以被认为是“有趣”（强调引号）的学习技术主题的方法，只是为了了解我在寻找什么。

• 为什么是 Ruby 的辛酸指南
• 试试 MongoDB（输入Help + Enter）

通常如何添加错误产生？我遇到了我的错误产生太浅的问题：当解析器开始弹出语句中的错误状态时，它会弹出，直到它遇到它所在部分的错误产生，并打印出无效错误信息。

为每个非终端添加一些描述性错误产生是个好主意吗？

我编写了一个变体类，它将用作动态语言中的主要类型，最终将允许 256 种不同类型的值（标头是无符号字节，实际只使用了 20 种）。我现在想实现类型之间的转换/转换。

我最初的想法是一个查找表，但所需的内存量使其实现起来不切实际。

有哪些替代方案？现在，我正在考虑其他三种研究方法和其他人的建议：

1. 将类型分组为更大的子集，例如数字或集合或其他。
2. 创建一个具有 CanCast(from, to) 和 Cast(Variant) 方法的转换接口，并允许将实现该接口的类添加到列表中，然后可以检查该列表是否有任何转换类可以进行转换。
3. 与 (1) 类似，但要制作几个主类型，并且铸造是从原始类型到主类型然后再到最终类型的两步过程。

什么是最好的系统？

编辑：我已经添加了赏金，因为我仍然不确定最好的系统，当前的答案非常好，并且肯定得到了我的 +1，但肯定有人这样做并且可以说出最好的方法是什么。

我目前正在寻找实现动态调度的各种方法。

据我所知，有两种“简单”的方法可以实现这一点：

• 虚函数表，如 C++ 中的
• Message Dispatcher，就像在 SmallTalk 中一样（这有点类似于 Python 将方法存储为属性的想法__dict__）

我会注意到，据我所知，选择 VFT 是因为它们执行合理且易于实现（也因为它们非常适合 C++ 单独编译模型），而不是因为它们是最快的方法。

我已经阅读了几篇文章和出版物，但是大多数都是“旧的”（我读到的最后一篇文章（*）提到了使用 Pentium 200MHz ...嗯），所以我怀疑它们是否代表了最先进的技术除非研究陷入僵局。

我对感兴趣：

• 动态调度策略，如果它们支持多方法就更好了。
• 各种策略的基准

我对最近的文章和不寻常的策略特别感兴趣（即使它们没有被证明是有效的）。

欢迎出版物，如果它们可以免费获得会更好，否则对所呈现的技术和结果的总结会很棒。

也欢迎真正编译器实现的技术文章。

(*)这篇关于 Eiffel 的文章说明了整个程序分析如何帮助删除虚拟呼叫站点。

编译器将源代码作为字符串处理，因此在 C++ 中，例如，当它鼓励像它从必须在和之间的范围内unsigned char x = 150;的类型限制中知道的语句一样时。unsigned char0255

我的问题是，虽然数字150仍然是字符串，但算法编译器使用什么算法编译器来比较数字序列 -150在这种情况下 - 与类型限制？

我为十进制、八进制、十六进制和小端二进制的“int”类型做了一个简单的算法，但我不认为编译器会做这样的事情来检测数字溢出。

我制作的算法是用 C++ 编码的：

该算法可以优化为适用于所有整数类型，但对于浮点，我必须制作新的算法才能使用 IEEE 浮点表示。

我认为编译器使用有效的算法来检测我以外的溢出，不是吗？

假设我的 CFG（以及其他）中有两个基本块 A 和 B，边缘从 A 到 B。我需要执行以下操作：

• 在该边缘上获取一组有效值（它可能是一个过度近似，即它可能包含不再有效的值）
• 将它们中的每一个映射到另一个值（S->S'）
• 用映射值 (S') 替换 - 在 B 及其后继者中 - S 中的所有值的使用

LLVM 是否提供了一种简单的方法来完成第一点和第三点（因为我似乎无法找到它）？如果没有，您对如何做有什么建议吗？

注意：交叉发布在 LLVM 邮件列表中

我彻底阅读了这个问题，然后构建一个 IDE 的想法让我印象深刻。

我是一名应届毕业生，想知道在构建 IDE 时要采取的概念和实际步骤。

在发布这个问题之前我没有做任何功课，但我相信我能在这里得到一个有效的答案。