Posts

之前使用 Matplotlib 画图的时候发现不能正常显示中文。在解决问题的过程中了解了一下字体显示的一些知识，在这里记录一下。 一、编码与字体 我们知道，为了让字符能够存储在计算机中，我们为每个字符分配对应的数码。这种人为约定称为字符编码。常见的编码包括 ASCII、GBK、Unicode 等等。字符编码是字符的数据表示。 然而，仅有编码依然不能在计算机中显示字符。因为符号是一种图形，若我们不能确定字符所对应的图形的样式，那么我们就无法在屏幕中看到字符。同样的，这种字符到对应图形的约定称为字形，字形的集合即字体。字体是字符的图像表示。 于是，这里我们就有了两种不同的映射关系。一种是字符到字符编码的映射关系，这一关系确定了字符的存储方式；另一种是字符到字体的映射关系，这一关系确定了字符的显示方式。 因此，简单来说，计算机显示字符的过程就是将编码数据转换为字形图像的过程。 二、编码的分裂和统一 然而这一过程并不真的那么简单。原因之一便是从计算机技术早期遗留下来的一系列互不兼容的编码方式。 在互联网还未诞生的时候，各个国家和地区为了在计算机中显示自己的文字，各自开发出自己的字符编码方式，例如简体中文的 GB2312、繁体中文的 Big5、日文的 Shift_JIS 等等。然而在互联网的国际化场景下，不同的编码方式带来了交流上的困难。 所以这时候 Unicode 标准应运而生。Unicode 由统一码联盟推动，旨在使用 Unicode 取代现存的字符编码。该标准整理并编码了世界上大部分的文字系统，使得电脑能以通用划一的字符集来处理和显示文字。 然而 windows 下的默认编码方式还是 gbk。 Unicode 编码空间区间为 $[0, 17 \times 2^{16})$，但目前只使用了其中很少一部分。该编码空间被划分为了 17 个平面，其中 4-13 号均未使用。其他平面的主要内容为： 0 号平面（0x0000-0x​FFFF）称为基本多文种平面，包含了几乎所有现代语言的字符。 1 号平面（0x10000-0x1FFFF）称为多文种补充平面，包括了绝大多数古代文字，现时已不再使用或很少使用的符号等。 2、3 号平面（0x20000-0x​2FFFF、0x30000-0x​3FFFF）称为补充表意文字平面，用于中日韩统一表意文字中未被包含在早期编码标准中的文字。 14 号平面（0xE0000-0xEFFFF）为特别用途补充平面。 15、16 号平面（0xF0000-0x​10FFFF）为私人使用平面。（例如苹果公司的图标字符） Unicode 虽然制定了统一的字符编码方式，但是直接使用 Unicode 编码进行存储的效率并不高。因此需要对 Unicode 进行进一步编码，这就带来了 UTF（Unicode Transformation Format），包括 UTF-32、UTF-16 和 UTF-8。 UTF-32 使用定长的 32 位对 Unicode 进行编码。根据 Unicode 的编码空间我们知道，最多只需要 21 位即可表示所有编码。因此 UTF-32 中的 11 位始终为 0。这使得 UTF-32 的空间效率很低。所以这种编码方式主要用在系统的内部 API 中。...

一、前言 我语言的局限，即是我世界的局限 —— 路德维希·约瑟夫·约翰·维特根斯坦 二、从文法树到语义 经过语法分析阶段的处理，我们将词序列组织成了一棵文法树。而在语义分析阶段，我们的目标就是理解该文法树的含义，并按其含义将该文法树翻译含义等价的另一种语言。 上面的表述十分宽泛。这是因为语义分析阶段不像前两个阶段有着明确的输入输出和确定的算法，根据使用场景的不同采用各自的处理方法。 举个例子，对比 C 语言和 SQL 语言，虽然它们都会采用编译技术进行语句的处理，但是 C 语言的语义分析产物是类似汇编的中间代码；而 SQL 语言的语义分析的结果则是对数据库中数据的处理操作。 因此，语义分析并没有通用的算法，就算同样是编程语言，面向过程、面向对象、函数式等不同的语言类别在语义分析上也有许多不同的处理。所以在本篇文章中，我们只会介绍最为简单和普遍的一种语义分析方法，那就是语法制导翻译。 三、语法制导翻译 （1）属性翻译文法 通过前面的文章，我们知道文法树表达了句子的结构。这种结构从语义上来说有两种含义： 一是指整体由部分组成。这反映了文法树中父节点的含义。例如对于表达式会 $1 + 2$，表达式本身是文法树中的父节点，而 $1$ $+$ 和 $2$ 则是子节点。 二是指部分处于整体之中。这反映了文法树中子节点的含义。 在使用语法制导翻译进行语义分析时，这两种含义我们称为属性。第一种属性由 “父” 传递到 “子”，称之为继承属性；第二种属性由 “子” 传递到 “父”，称之为综合属性。 （2）符号表管理 四、中间代码

一、前言 从这个精神王国的圣餐杯里， 他的无限性给他翻涌起泡沫。 —— 格奥尔格·威廉·弗里德里希·黑格尔《精神现象学》下卷 第八章 绝对知识 二、从正则文法到上下文无关文法 词法分析阶段，我们可以使用正则文法描述词的定义，这是因为词的结构是无嵌套的。也就是说，词只会由例如前缀、后缀以及结构的顺序重复等概念描述，不可能出现需要前后匹配的地方。举个例子，正则文法不能定义形如 $12344321$ 的回文数；或形如 $(()(()))$ 的括号结构。 然而，所有的高级语言却都是嵌套的。通过嵌套，高级语言能够表示更加复杂的结构，实现控制流、子程序、作用域、类等等高级概念。因此，正则文法并不能描述高级语言的语法，我们需要使用 2 型文法，也即上下文无关文法描述高级语言。2 型文法区别于 3 型文法就在于其嵌套性。 举个例子，我们可以将上述括号结构用如下 2 型文法定义： $$ S \rightarrow (S)S | \epsilon $$ 其中规则 $S \rightarrow S(S)$ 中左括号和右括号同时出现，这样就保证了对于一个左括号，必定有一个右括号与其匹配。因而我们说上面的文法具有嵌套性。 而 3 型文法则不同。由于左线性和右线性的约束，3 型文法中不可能出现一条规则中右侧有多个终结符的情况。 不过虽然 2 型文法相较于 3 型文法具有更强的表达能力，但是这也为其解析提供了一定的困难。我们可以选择用前面定义的文法给出 $(()(()))$ 的文法树： 可以看出，相较于 3 型文法的文法树，2 型文法的文法树更像是树：并不是只向一侧增长，而是在任意地方都可能产生子树。因此，2 型文法的推导或归约过程不再能看作状态的转移，我们需要用有穷自动机之外的另一种模型描述，该模型应当具有接受嵌套结构的能力。这就是下推自动机。 三、下推自动机 （1）例子：判断有效括号问题 初学编程的时候各位应该都做过类似的题目，那就是判断有效括号。实际上这是一个编译问题。我们可以使用编译理论的语言将该问题表述为：对于符号集 $\Sigma = \{`(`, `)`, `[`, `]`, `\{`, `\}`\}$，对给定的括号文法 $G$，对于任意 $s \in \Sigma^*$，给出一个算法，判断是否有 $s \in L(G)$（即 $s$ 是否被文法 $G$ 接受）。...

本文是北航《操作系统》课程预习教程的一部分。此版本由本人编写。 2024 年课程实验环境由 GXemul 更换为 QEMU，为了方便同学适应新的实验环境，在预习教程中特地新增《GDB：程序的解剖术》和《QEMU 模拟器介绍》两篇文章。 操作系统是直接运行在计算机硬件之上，向下管理硬件资源，对上为软件提供统一服务的一类程序。在本课程的实验中，为了开发和运行我们的 MOS 操作系统，我们必须具备一套支持操作系统运行的硬件系统，其中包括处理器、内存、外部设备（如磁盘）等多个组成部分。 然而，为每位同学都准备一套硬件设备是不切实际的。相较之下，使用模拟器则是一个更好的选择。模拟器能够模拟计算机硬件的行为和特性，使开发者可以在模拟的环境中运行和测试软件，而无需实际的物理硬件设备。 本实验所采用的模拟器为 QEMU，接下来我们就会对这一模拟器进行介绍。 什么是 QEMU QEMU（Quick Emulator）是一个通用的开源的机器仿真和虚拟化工具，由传奇程序员布里斯·贝拉（Fabrice Bellard）编写。QEMU 能够提供跨体系结构的硬件模拟，支持 x86、ARM、MIPS、RISC-V 等多种架构。 布里斯·贝拉 是 QEMU、FFmpeg 等著名项目的创始人。他的工作涉足操作系统（QEMU）、编译器（Tiny C Compiler）、图形学（TinyGL）、通信技术（Amarisoft）、数学（Bellard’s formula）、音视频（FFmpeg）、人工智能（NNCP）等众多领域，并都做出过许多突出的贡献。是一位近乎全才的人物。 QEMU 拥有多种不同的使用方式，而在实验中我们所使用的主要是 QEMU 的系统仿真模式。在此模式中，QEMU 能够模拟处理器的执行过程以及各种硬件设备的行为，从而提供包括处理器、内存和外部设备在内的整机虚拟模型。在此模型之上，我们能够运行一个完整的操作系统，而不需要任何额外硬件的支持。 QEMU 提供了高度定制化的硬件模拟能力，使得搭建指定硬件平台的运行环境十分容易。并且 QEMU 也提供了使用 GDB 进行调试的原生支持，使程序的开发更加便捷。正因如此，QEMU 成为了底层开发领域十分重要的工具。 QEMU 的工作原理 这部分并不是本课程要求掌握的内容。各位可以按兴趣阅读。 在正式谈论 QEMU 的工作原理前，我们需要先了解一下虚拟化（Virtualization）技术。这里的虚拟化特指硬件虚拟化，是指隐藏真实的物理硬件，而由软件模拟出特定的硬件环境，在此环境中运行的操作系统就好像运行在实际的物理机器上一样。在此过程中，通过模拟产生的硬件环境称为虚拟机（Virtual Machine），实现虚拟化的程序称为虚拟机管理程序（Hypervisor）。本质上，虚拟机管理程序是一种中间件。 通过虚拟化技术，我们可以屏蔽底层硬件的差别，从而在单台物理设备上运行许多不同的操作系统环境，充分利用硬件资源。虚拟化产生的硬件环境也很容易在不同设备间迁移，这也利于系统的管理和维护。 根据虚拟化实现方式的不同，虚拟机管理程序分为第一类虚拟机管理程序（Type 1 Hypervisor）和第二类虚拟机管理程序（Type 2 Hypervisor）。 第一类虚拟机管理程序直接运行在硬件之上，如下图 (a) 所示。此时虚拟机管理程序实际上占据了类似操作系统的位置，整个物理机被其分割为多个虚拟机。 而第二类虚拟机管理程序则运行在操作系统之上，是操作系统中的应用程序，如下图 (b) 所示。其中称运行该虚拟机管理程序的操作系统所处的机器为宿主机（Host），而管理程序中的虚拟机则为客户机（Guest）。由于第二类虚拟机管理程序采取了软件模拟处理器、解释执行机器码的方式，所以也被称为模拟器（Simulator）。 第一类虚拟机管理程序主要在企业数据中心或服务器中使用。常见的产品包括 KVM、VMWare ESXi 等等。而第二类虚拟机管理程序则通常在个人计算机上使用，以便能在运行虚拟机的同时执行其他进程。常见的产品包括 VMware Workstation、Oracle VirtualBox 等等，其中也包括 QEMU。 图片来自 Andrew S....

本文是北航《操作系统》课程预习教程的一部分。此版本由本人编写。 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]$，其文法树只向右增长...