本文是北航《操作系统》课程预习教程的一部分。此版本由本人编写。 2024 年课程实验环境由 GXemul 更换为 QEMU，为了方便同学适应新的实验环境，在预习教程中特地新增《GDB：程序的解剖术》和《QEMU 模拟器介绍》两篇文章。 回想起刚刚踏入编程世界的时候，大概每个人都有这样的经历：仔细编写的程序总是得不到正确的结果，即便将代码从头到尾检查几遍，依旧找不出隐藏其中的错误。虽然我们对自己所写的代码了如指掌，但是代码终究是静态的，无法反映真实的运行情况；虽然各种各样的测试样例可以让我们发现错误，但是程序终归是只有输入输出的黑箱，其中的运行机理让我们束手无策。 为了解决这样的困境你肯定试过很多办法，比如说大名鼎鼎的 “printf” 大法。但是在原有的逻辑中插入没有意义的输出反而会使代码的结构更加混乱，过量的输出同样更加可能掩盖错误的真相，最终离发现错误的目标越来越远。我们需要采用另一种方法，能够在不侵入代码原有逻辑的前提下，追踪程序的运行情况，从而发现程序运行中出现的错误。 GDB 简介 能够实现追踪并控制程序运行功能的程序称为 Debugger，中文称其为调试器。不同语言有着不同的调试器，如 Python 的 PDB、Java 的 JDB。而我们在本篇文章中介绍的则为 GDB，全称为 “GNU Debugger“。 GDB 的吉祥物，一条 “射水鱼”。擅长射出水柱击落岸边植物上的昆虫（Bug）。 GDB 是一个功能十分强大的调试器，它适用于 C、C++、Go、Rust 等多种语言。GDB 最初由 GNU 项目的创始人理查德·马修·斯托曼（Richard Matthew Stallman）编写，并作为 GNU 项目的一部分。根据 GDB 官网的描述，GDB 的主要功能包括： 启动程序并指定可能影响其行为的任何内容。 使程序在指定条件下停止。 当程序停止时，检查发生了什么。 更改程序中的内容，以便可以尝试纠正一个错误的影响，并继续了解另一个错误。 接下来我们会逐步介绍上述功能。看看 GDB 是如何像手术刀一样解剖程序运行的机理，发现病灶所在的。 准备工作 在开始之前需要说明两点： 接下来的内容我们将在 Ubuntu 中进行，这与本课程的实验环境保持一致。同时建议同学们尽量在学习和开发时多多使用 Linux 环境，因为许多项目都只支持 Linux 平台，或只提供 Linux 下的教程和文档。 为了更好地理解 GDB 的指令操作，同学们最好在阅读教程的同时同步进行操作。 实验所提供的跳板机上会安装好所有需要的环境，因此同学们也可以使用跳板机完成本文操作。但是跳板机中会出现由于无法关闭 address space randomization 导致无法设置断点的问题。这一问题可以通过在 GDB 界面中输入 set disable-randomization off 指令解决。...

一、前言 因而，每一生物的有机形体都是一个神圣的机器，或一台无限地优越于任何人造的自动机器的自然的自动机器（automata）。因为人的技艺所制造的机器的每一部分并非机器。……而自然的机器，即有机体，在其无限小的部分仍是机器。 —— 戈特弗里德·威廉·莱布尼茨《单子论》第 64 节 本章将从词法分析所用的 3 型文法入手，引入自动机的概念，并详细介绍有穷自动机的原理及实现。最终实现编译程序的词法分析模块。 二、正则文法的解析过程 在第 1 章的最后我们介绍了 3 型文法。3 型文法也称正则文法，特征是对于文法中的每一条规则，其右侧要么是一个终结符，要么是一个终结符加上一个非终结符，且非终结符只位于终结符的一侧。根据非终结符位置的不同分为左线性和右线性。 或许有些人会这样讲：“左线性是终结符在右侧；右线性是终结符在左侧”。但是这样实在太别扭了。应该说 “左线性是非终结符在左侧；右线性是非终结符在右侧”。 为什么通过这一约束，3 型文法就能区别于 2 型文法了呢？我们可以通过正则文法的解析过程来理解。 现在有一左线性正则文法 $G_1[Z]$： $$ \begin{align*} Z & \rightarrow A1 \\ A & \rightarrow B1 | 1 \\ B & \rightarrow A0 \end{align*} $$ 现在可能不太能看得出来，但是 $G_1[Z]$ 能够接受符号串 $101011$。我们可以画出此符号串对应的文法树。 通过文法树我们可以看出，对于左线性正则文法 $G_1[Z]$，其文法树只向左增长。当然这一点从规则中也可以看出，只不过不那么直观罢了。 可为什么具有这样特性的文法就特殊了呢？接下来我们根据文法树，以归约的视角看待符号串 $101011$ 的解析过程： 读入 1，1 归约得到 A； 读入 0，A0 归约得到 B； 读入 1，B1 归约得到 A； …… 以此类推，我们就可以发现其中的规律。对于这样的文法，读入一次即归约一次。因为文法中最多只有两个符号，所以一旦读入了一个新的符号，则必定进行一次归约。 同理的，我们考虑右线性正则文法 $G_2[S]$： $$ \begin{align*} S & \rightarrow 1A \\ A & \rightarrow 0B | 1 \\ B & \rightarrow 1A \end{align*} $$ $101011$ 也能被 $G_2[S]$ 接受。其文法树如下，对于右线性正则文法 $G_2[Z]$，其文法树只向右增长...

一、前言 本质是存在的真理，是自己过去了的或内在的存在。 —— 格奥尔格·威廉·弗里德里希·黑格尔《小逻辑》第二篇 本质论 §112 本篇文章是一个间章。旨在衔接文法理论与编译过程，从架构上概述整个编译程序。文法理论旨在解释自然语言，而编译过程却要创造新的语言。编译程序通过将文法规则机械化，创造出易于理解的高级语言，实现了计算的高级抽象。 二、何为 “编译” 为了理解何为 “编译”，我们可以从一个具体的编译器开始。这里我们以 C 语言的编译过程为例： 现在有一个简单的由 C 语言文法写成的文本文件 test.c // test.c #include <stdio.h> int main() { printf("hello, world.\n"); return 0; } 想要将其编译为可执行文件，当然可以使用 gcc test.c -o test 或 clang test.c -o test，但是这样就不能反映编译的具体过程了。所以这里我编写了一个 Makefile，用来指明 gcc 编译时所经历的具体步骤。 # Makefile srcname = test cc = gcc # Default target all: $(srcname) @echo "Finish!" # Linking stage $(srcname): $(srcname).o @echo "Linking stage: Creating executable '$(srcname)'" $(cc) $(srcname).o -o $(srcname) # Assembly stage $(srcname)....

一、前言 一个人进行推理时…… 这种过程如果是用语词进行的，他便是在心中把各部分的名词序列连成一个整体的名词或从整体及一个部分的名词求得另一个部分的名词。 —— 托马斯·霍布斯《利维坦》第一部分 论人类 第五章 论推理与学术 当霍布斯将他的机械唯物主义运用于人的思想时，语言便成为了人脑的齿轮。人的精神当然并非机械，可这种认识却也敏锐地察觉到了语言的一些本质，那就是语言是一些规则，通过这些规则的拼凑，我们得以表述我们的思想。如今，这种规则我们称之为文法。 语言学家的一部分工作是从现有的自然语言中总结文法，让语言成为机械。但是这并不是我们的重点，我们所要探索的是一个更加年轻的领域，这个领域的研究从机械出发，却要去创造千变万化的语言，让机械成为语言。 二、自然语言的文法：一个例子 但是要开始我们的旅程，还需要从自然语言开始。当我们听别人说话，或者阅读一段句子的时候，我们究竟在理解什么？比如说，现在有这样一句话，你知道我的叉子被放在哪里吗。让我们尝试理解这个句子。 这部分默认各位已有了对词性的基本认识，至少知道名词、形容词、动词、副词等等的大致含义。否则的话，这部分内容实难描述。 另外注意对于自然语言的相关表述可能并不完全符合人的认知的真实情况，这一部分只是为了方便理解。 首先需要明确一点，抛开我们所有的经验来看，语言就是符号的序列。也就是说语言是在时间上存在先后顺序的许多符号。这意味着我们的理解过程必定是从前到后的。对于上述句子来说，我们先读到 你，之后才能读到 知，再之后 道、我 等等。 另外，在这样不断读到一个个符号的时候，我们也并非单纯的按照字母或音节分别认识，而是首先明确哪些音节或符号共同组成相同含义，并将其作为一个单词来识别。在自然语言处理领域，这称为“分词”；而对于编译来说，这称为“词法分析”。 我们理解这个句子的过程可能是这样的： 读到 你，这指代一个事物，为名词 读到 知道，这指代一个行为，为动词 读到 我的，这描述了事物的属性，为形容词 读到 叉子，这指代了另一个事物，为名词 形容词 我的 和名词 叉子 组成 我的叉子，也是个名词 读到 被放，这是动词。 读到 在，这表达了一个关系，为介词 读到 哪里，这是名词 介词 在 和 名词 哪里 组成 在哪里，用于描述行为，为副词 动词 被放 和副词 在哪里 组成 被放在哪里，也是个动词。 名词 我的叉子 和动词 被放在哪里 组成 我的叉子被放在哪里，用于陈述一个事实，称为陈述句 名词 你、动词 知道 和句子 我的叉子被放在哪里 组成了 你知道我的叉子被放在哪里，是另一个陈述句。 读到 吗，这是一个疑问语气词，用于表达疑问。 句子 你知道我的叉子被放在哪里 和疑问语气词 吗 组成 你知道我的叉子被放在哪里吗，表达对被陈述的事情真实性的询问，是疑问句。 读完了所有的单词，最后得到的疑问句就是整个句子。 在上述过程中，我们不断将小的句子成分归纳为大的句子成分，在这样归纳的过程中，我们将句子中的每个单词相互关联起来，最终理解句子表达的含义。从中我们可以知道这是一个疑问，想要得到的回答是“你”与“我的叉子被放”两个事物间是否存在“知道”的关系等等。（这样说话好别扭。）...

最近这段时间文章似乎写得不太多，但是这个小小博客并非就此死掉了。为了一些可能并不存在的关注者，同时也为了我自己，先在这里发一篇短文。 现在的我处于这样的一个阶段，不再满足于罗列刚刚学到的知识，希望在文章中加上自己的思考；但同时自己却也没有经年的储备，稍有新意的认识只能慢慢积累。这就导致了一部分内容不必写；而另一部分内容又还不能写。有时我也想稍稍水一些字数，把那些不必写的内容写一写，可近期的学业又没有留给我那么多可浪费的时间。对这一点，我要向我的博客道歉。 可道歉归道歉，我并没有忘记写文章这件事。自我上一篇文章完成已有一个半月的时间，在这期间我也构思了许久自己要做些什么。就在今天，我从考试中解放出来，接下来的计划也早就在我脑中成熟了。 操作系统实验的笔记是本博客阅读量较多的一系列文章，接下来我希望以类似的形式写一系列编译技术的文章。从编译的理论知识出发，辅以相应代码，逐渐编写一个简单的编译器。这也是我对自己的编译技术课程的总结。 说出去的话就不能反悔了。本文也是对我自己的鞭策。

一、总览 如果你想要了解 LLVM，那么有几种可能呢？你或许是想要创造一门新的编程语言的技术爱好者；或是陷入编译课的泥沼不能自拔的大学生，但不管怎么样，你都只希望使用 LLVM 做一件事：生成目标代码。 但是这一过程并不容易。你大概率经过了编译前端的艰辛历程，但是现在在你面前的是另一座大山，LLVM IR。在最开始就看到什么基本块、虚拟寄存器、phi 节点之类的概念使你心烦意乱；各种各样的代码示例中充满了和重点并不相关的细节。这些都使你无从下手…… 或许一个更好的学习方式是将 LLVM IR 视为一种特殊的编程语言，而非编译器的 “中间表示”。这种语言站在了高级与低级语言之间，既具备了一定的抽象能力，又反映了底层汇编的工作原理。 本篇文章，就将以编程语言的视角粗略介绍 LLVM IR。通过直接手写 LLVM IR，逐步分析其特点和原理。希望能够有所帮助。 （1）准备工作 LLVM IR 虽然是中间代码，但是 LLVM 也提供了 lli 工具用于解释/即时编译执行 LLVM IR 文件。这样 LLVM IR 又与 Java 字节码有了一些相似之处。使用 lli 可以直接运行我们手写的中间代码，很是方便。使用 lli 这需要安装 LLVM。 sudo apt-get install llvm 另外，LLVM 中是没有内建输入输出的，因为 LLVM 的工作在操作系统之下。这就导致了一个问题，我们不能得知程序的执行结果。一种方法是可以用函数的返回值来输出，但是这样输出只能是单个数值。为了方便起见，可以先用 c 语言编写一个输出库。并使用 clang 将其编译成 LLVM IR。为此需要安装 clang sudo apt-get install clang 对于输出库，这里只简单定义 putint 函数。 // lib.c #include <stdio.h> void putint(int i) { printf("%d\n", i); } 使用 clang 将其翻译成中间代码。不要担心，我们并不需要关心生成的 lib....