问题标签 [compiler-theory]

我正在寻找能够从编程语言中的输入程序创建 Win32 程序的编译器的源代码（哪个没关系，也许越简单越好）

然而我找不到任何适合我的东西，像 GCC 这样的大型编译器让我非常困惑，因为它们有很多功能，我不知道从哪里开始。

• 是否有针对某些编程语言的 OpenSource Win32 微编译器，我可以看看吗？

编译器如何跨翻译单元检测重复定义。假设头文件中有一个 extern const 变量声明。
如果在多个翻译单元中使用此头文件 - 每个翻译单元都有单独的定义 - 每个 TU 对象创建都会成功，但是在创建最终可执行文件时会引发错误。

在链接每个 TU 时（在创建可执行文件期间）是否创建了一个参考表来说明这些重复？

有关此主题的任何链接都会有所帮助。

提前感谢您的解释。

我正在使用 flex、byacc（用于词法和解析）和 C++ 开发类似 Python 的小型语言，但我对范围控制有一些疑问。

就像python一样，它使用空格（或制表符）进行缩进，不仅如此，我还想实现索引中断，例如，如果你在另一个while循环内的while循环内键入“break 2”，它不仅会从最后一个，但也从第一个循环开始（因此中断后的数字为 2）等等。

例子：

但由于我没有“反”制表符来检查作用域何时结束（例如 C，我只会使用 '}' 字符）我想知道这种方法是否是最好的：

我会在我的 yacc 文件上定义一个全局变量，例如“int tabIndex”，我将使用 extern 在我的 lex 文件中访问它。然后每次我在我的 lex 文件中找到一个制表符时，我都会将该变量增加 1。在解析我的 yacc 文件时，如果我找到一个“break”关键字，我会减少从 tabIndex 变量中键入的数量，当我在编译后到达和 EOF，我得到一个 tabIndex ！= 0 我会输出编译错误。

现在的问题是，查看缩进是否减少的最佳方法是什么，我应该从 lex 读取 \b （退格）字符，然后减少 tabIndex 变量（当用户不使用 break 时）？

另一种方法来实现这一点？

也只是另一个小问题，我希望每个可执行文件都有一个名为 start() 的函数的起点，我应该将它硬编码到我的 yacc 文件中吗？

很抱歉这个问题很长，非常感谢任何帮助。另外，如果有人可以为 python 提供一个 yacc 文件作为指导（尝试在 Google 上查找但没有运气）。

提前致谢。

想象一下，我有一种基于堆栈的玩具语言，它带有 Push、Pop、Jump 和 If 操作。

我有一个程序，它的输入是玩具语言。例如我得到序列

在这种情况下，最大堆栈将为 2。更复杂的示例将使用分支。

在这种情况下，最大堆栈将为 3。但是，如本例所示，通过从上到下遍历是不可能获得最大堆栈的，因为它实际上会导致堆栈下溢错误。

CFG 可以帮助您构建图表并遍历您拥有的基本块的每条可能路径。然而，由于路径的数量对于 n 个顶点可以快速增长，因此您得到 (n-1)！可能的路径。

我目前的方法是尽可能简化图表并减少可能的路径。这行得通，但我认为它很难看。有没有更好（阅读：更快）的方法来解决这个问题？如果算法产生的堆栈深度不是最优的，我很好。如果正确的堆栈大小是 m，那么我唯一的限制是结果 n 是 n >= m。是否有可用的贪心算法可以在这里产生良好的结果？

更新：我知道循环和所有控制流合并具有相同堆栈深度的不变量。我想我写下一个简单的玩具般的语言来说明这个问题。基本上我有一个确定性的基于堆栈的语言（JVM 字节码），所以每个操作都有一个已知的堆栈增量。

请注意，对于这个问题，我确实有一个可行的解决方案，可以产生良好的结果（简化的 cfg），但我正在寻找一种更好/更快的方法。

正如删除左递归中所解释的，有两种方法可以删除左递归。

• 使用一些过程修改原始语法以删除左递归
• 原来写的文法没有左递归

人们通常使用 ANTLR 删除（没有）左递归的方法是什么？我使用 flex/bison 作为解析器，但我需要使用 ANTLR。我唯一担心使用 ANTLR（或一般的 LL 解析器）是左递归删除。

• 实际上，在 ANTLR 中去除左递归有多严重？这是使用 ANTLR 的亮点吗？或者，在 ANTLR 社区中没有人关心它？
• 我喜欢 AST 生成 ANTLR 的想法。在快速简便地获得 AST 方面，哪种方法（在 2 种删除左递归方法中）更可取？

添加

我对以下语法做了一些实验。

左递归删除后，我得到以下一个

我可以提出以下 ANTLR 表示。尽管它相对简单明了，但似乎没有左递归的语法应该是更好的方法。

正如在删除 ANTLR 中的左递归中询问和回答的那样，我可以删除左递归

左递归删除后，我得到以下一个

那么，如何用修改后的语法进行树构造呢？输入1+2，我想要一棵树

我看到以下模式经常发生：

请注意，文字字符串被使用了两次。提取物来自 nginx 源代码库。

当在编译单元中遇到这些文字时，编译器应该能够合并这些文字。

我的问题是：

1. 在编译单元中遇到商业级编译器（VC++、GCC、LLVM/Clang）是否会消除这种冗余？
2. （静态）链接器在链接目标文件时是否删除了此类冗余。
3. 如果 2 适用，这种优化会在动态链接期间发生吗？
4. 如果 1 和 2 适用，它们是否适用于所有文字。

这些问题很重要，因为它允许程序员在不损失效率的情况下变得冗长——例如，考虑将大量静态数据模型硬连接到程序中（例如，在某些低级场景中使用的决策支持系统的规则） .

编辑

2 点/说明

1. 上面的代码是由公认的“大师”程序员编写的。那家伙单枪匹马写了nginx。

2. 我没有问过哪种可能的文字硬编码机制更好。因此，不要跑题。

编辑 2

我最初的例子是相当做作和限制性的。以下代码段显示了嵌入到内部硬编码知识中的字符串文字的用法。第一个片段用于配置解析器，告诉它要为哪个字符串设置哪些枚举值，第二个片段更普遍地用作程序中的字符串。只要编译器使用字符串文字的一份副本，我个人对此感到满意，并且由于元素是静态的，它们不会进入全局符号表。

紧随其后的是：

对于那些留在主题上的人，太棒了！

对于我们的编译器理论课，我们的任务是为我们自己设计的编程语言创建一个简单的解释器。我正在使用 jflex 和 cup 作为我的生成器，但我对什么是词法错误有点困惑。另外，是否建议我使用 jflex 的状态功能？感觉不对，因为解析器似乎更适合处理该方面。您是否推荐任何其他工具来创建该语言。对不起，如果我不耐烦，但它是在星期二到期。

我为大学项目编写编译器，我想将我的抽象语法树转换为控制流图（CFG）。

我认为VCFG 中的节点（）应该是来自 AST 的节点。我从算法上知道如何构造边缘集（G=(V,E)），但我很难更正式地编写这个过程

我创建了这个 scala 样式模式匹配（伪）：

哪个应该匹配 AST 结构，例如：

并提供一个边缘集，如：

点Src

有人对如何比scala“伪代码”更正式地执行此操作有任何提示吗？

我在想一些归纳的东西，比如：

（上面只会给出一棵树而不是一个图。例如，从分支的边缘到下一条语句没有边缘）

编辑：

我一直在阅读kiama 和scala 的数据流，我喜欢他们使用的“succ”和“following”方法。然而，我很难将其归结为更正式的描述，主要是因为漂亮的childAttr，s.next它隐藏了一些当我尝试正式指定它时变得丑陋的细节。

编辑2：

我已经阅读了 Dragon Book 和“现代编译器在 ML 中的实现”以及学习编写编译器的其他一些材料，并且一些/大部分提到了数据流和控制流，但从未涉及如何创建CFG 以任何正式的方式。

编辑3：

通过Kiama的作者、副教授 Tony Sloane 博士，我收到了一些额外的参考书目来查找。

据我所见，这些书籍的“方法”是基于程序的“每个语句”而不是基于 AST，并且基于基本块。尽管如此，伟大的投入！

我刚开始阅读《龙之书》，我发现难以理解一些陈述。

它说：“词法分析器为源程序中的每个词位生成标记序列”。你能帮我理解上面的行吗？我知道标记和词位，但是为每个词位生成多个标记意味着什么……AFAIK LEXEME 本身会损害单个标记。

完整报价如下：

“作为编译器的第一阶段，词法分析器的主要任务是读取源程序的输入字符，将它们分组为词位，并为源程序中的每个词位生成一个标记序列作为输出。”

上面的引用来自第 3 章..第 3.1 节标题“词法分析器的角色”页码是 109