主要是借着记笔记 预习 巩固一下记忆

1. 处理器

1.1. 处理器与寄存器

1. 处理器

根据维基百科的定义, 处理器的主要功能是解释计算机指令以及处理计算机软件中的数据. 更加具体地说, 处理器负责管理、调度和分配计算机系统的重要资源，并控制程序执行.

​ 上图给出了一个 CPU 的简单示意图.

2. 寄存器

​ 总的来说, 处理器中的寄存器包括三大类

用户程序可见寄存器

​ 用户程序可见寄存器可以使程序员减少访问主存储器的次数，提高指令执行的效率. 这些寄存器在所有程序 (包括应用程序和系统程序) 中均可使用, 包括:

• 数据(通用)寄存器: AX、BX、CX、DX等
• 地址寄存器: 索引(SI、DI)、栈指针(SP、BP)、段地址(CS、DS、SS、ES)、页表寄存器等

控制和状态寄存器

​ 控制和状态寄存器用于控制处理器的操作，主要是被具有特权的操作系统程序使用，以控制程序的执行

• 程序计数器PC：存储将取指令的地址
• 指令寄存器IR：存储最近使用的指令
• 条件码CC：CPU为指令操作结果设置的位，标志正/负/零/溢出等结果
• 标志位：中断位、中断允许位、中断屏蔽位、 处理器模式位、内存保护位、…，等

**程序状态字 (PSW) **

​ 严格来说, Program State Word 可能并不是一个或一种寄存器. 实际上, 程序运行时,其状态不断动态地变化, 如当前处于用户态还是内核态, 下一条要执行的指令位置是什么, 等等. 操作系统将程序运行时的一组动态信息汇集在一起,称为程序状态字 (PSW), 并存放在处理器的一组特殊寄存器里, 以方便系统的控制和管理.

​ 但是实际上为了方便, 我们可以设置一组控制和状态寄存器来存储PSW, 也可以专门设置一个 PSW 寄存器.

1.2. 指令与处理器模式

2. 中断管理

2.1. 中断与中断源

1. 中断, 异常与系统异常

操作系统是 “中断驱动” 的, 即中断是激活操作系统的唯一方式.

广义上, 我们称中断是一种执行过程, 即指程序执行过程中，遇到急需处理的事件时，暂时中止CPU上现行程序的运行, 转去执行相应的事件处理程序, 待处理完成 后再返回原程序被中断处或调度其他程序执行.

狭义上, 我们认为中断是广义中断的一个子集, 也就是指来源于处理器之外的中断事件 (与当前运行指令无关的中断事件), 如I/O中断、时钟中断、外部信号中断等.

狭义的中断概念引出了异常的概念: 与中断相对应地, 异常指当前运行指令引起的中断事件，如地址异常、算术异常、处理器硬件故障等.

一种特殊的异常是系统异常: 指执行 trap 指令而触发系统调用引起的中断事件，如请求设备、请求I/O、创建进程等

中断对于操作系统具有非常重要的作用. 甚至可以说, 操作系统就是中断驱动的.

2. 中断源

处理器硬件故障中断事件: 由处理器、内存储器、总线等硬件故障引起的中断事件. 也就是坏了

程序性中断事件: 由处理器执行机器指令引起的中断事件. 算术异常(除数为零、操作数溢出), 指令异常(非法指令、用户态使用特权指令、地址越界、非法存取等)：终止进程, etc.

自愿性中断事件: 由处理器执行陷入指令请求OS服务引起的中断事件. 在操作系统中又被称作系统调用.

I/O中断事件: 由外围设备报告I/O状态引起的中断事件

外部中断事件: 由外围设备发出的信号引起的中断事件

2.2. 中断系统

中断系统是计算机系统中响应和处理中断的系统，包括硬件子系统和软件子系统两部分

• 中断响应由硬件子系统完成
• 中断处理由软件子系统完成

1. 中断的响应

响应中断的设计是, 在指令执行周期最后增加一个微操作. 示意图如下:

具体来说, 中断响应的具体步骤如下:

• 发现中断源，提出中断请求: 发现中断寄存器中记录的中断 $\to$ 决定这些中断是否应该屏蔽 $\to$ 当有多个要响应的中断源时，根据规定的优先级选择一个.

• 中断当前程序的执行: 保存当前程序的 PSW/PC 到核心栈

• 转向操作系统的中断处理程序

2. 中断的处理

Trivially, 处理中断的程序叫做中断处理程序. 蚌

具体来说, 处理中断的过程如下 (如上图):

• 保护未被硬件保护的处理器状态
• 识别中断源 (通过分析被中断进程的PSW中断码字段)
• 分别处理发生的中断事件
• 恢复正常操作: 对于某些中断, 在处理完毕后, 直接返回刚刚被中断的进程; 对于其他一些中断, 需要中断当前进程的运行, 调整进程队列, 启动进程调度, 选择下一个执行的进程并恢复其执行.

2.3. 多中断的响应与处理

有了中断的概念之后, 我们很自然地需要几个新的概念来组织中断的进行.

• 中断优先级: 当计算机同时检测到多个中断时, 中断装置必须按照某个顺序响应中断. 表征这个顺序的单位就是中断优先级.
• 中断屏蔽: 当计算机检测到中断时, 中断装置通过中断屏蔽位决定是否响应已发生的中断. 也就是说, 中断装置可以选择拒绝中断.
• 中断的嵌套: 当计算机响应中断后, 在中断处理过程中, 可以再响应其他中断. 也就是说, 中断也可以有中断.

但是实际上, 操作系统的性能攸关程序系统，且中断响应处理有硬件要求, 综合考虑到系统效率和实现代价的问题, 中断的嵌套处理应限制在一定层数内, 如3层

中断的嵌套处理机制改变了中断处理次序, 先响应的有可能后处理.

总的来说, 决定中断处理次序的因素有如下几个:

• 中断屏蔽可以使中断装置不响应某些中断
• 中断优先级决定了中断装置响应中断的次序
• 中断可以嵌套处理, 但嵌套的层数应有限制
• 中断的嵌套处理改变了中断处理的次序

3. 进程管理

3.1. 进程及其状态

1. 进程 (process)

操作系统必须全方位地管理计算机系统中运行的程序, 因此, 操作系统为正在运行的程序抽象出了一个管理实体——进程. 也就是说, 进程是为了管理程序运行所抽象出来的概念.

进程是操作系统进行资源分配和调度的一个独立单位. (比方说在内存管理中, 每个进程拥有一个LDT)

Physically, 一个进程包括五个实体部分:

• (OS管理运行程序的) 数据结构 $P$
• (运行程序的) 内存代码 $C$
• (运行程序的) 内存数据 $D$
• (运行程序的) 通用寄存器信息 $R$
• (OS控制程序执行的) 程序状态字信息 $PSW$

2. 进程的关系

无关进程: 不同代码在不同数据集上运行

交往进程: 不同代码在相同数据集上运行

无关进程: 相同代码在不同数据集上运行

3. 进程的状态

jyy: “程序是状态机.”

一般来说, 在操作系统中, 进程的状态模型通常包括以下几种状态：

• 就绪 (Ready) 状态：表示进程已经准备好了运行，并在等待CPU资源分配。
• 运行 (Running) 状态：表示正在执行的进程，其占用了CPU资源。
• 阻塞 (Blocked) 状态：表示进程因为等待某些事件的发生而被暂停，此时它不会占用CPU资源。
• 创建 (New) 状态：表示操作系统已经创建了一个新的进程，但尚未分配任何资源给它。
• 终止 (Terminated) 状态：表示进程已经执行完毕或被终止，此时释放了所有的资源。

但是实际上, 不同的操作系统可能会对这些状态进行微调和补充, 以满足具体的需求. 例如Windows中还有一个挂起 (Suspended) 状态，表示进程被暂停, 并且其状态信息已经保存在硬盘上, 等待恢复; 而在Unix/Linux系统中, 则将就绪和运行两个状态合并为执行 (Running) 状态, 并引入了僵尸 (Zombie) 状态, 表示进程已经完成了执行, 但其父进程还没有回收其资源.

那么在愚蠢的NJUSE@OS课件上, 我们给出了如下常见的进程状态模型 (进程三态模型):

(1) 运行态 $\to$ 等待态: 等待资源、I/O、信号

(2) 等待态 $\to$ 就绪态: 资源满足、I/O结束、 信号完成

(3) 就绪态 $\to$ 运行态: 处理器空闲时选择更高优先权进程抢占

(4) 运行态 $\to$ 就绪态: 运行时间片到、 有更高优先权进程

Physically, OS无法预期进程的数目与资源需求，计算机系统在运行过程中可能出现资源不足的情况. 因此我们引入了挂起的概念. 运行资源不足表现为性能低和死锁两种情况, 因此我们必须要采取包括如下的措施来缓解这样的情况: 剥夺某些进程的内存及其他资源, 调入OS管理的对换区, 不参加进程调度, 待适当时候再调入内存、恢复资源、参与运行. 这就是进程挂起. 加入挂起的概念之后, 我们的进程状态模型如下图所示:

3.2. 进程的数据描述

1. 进程控制块

为了描述进程的相关信息, 我们需要引入一个概念叫做进程控制块 (Process Control Block, PCB). Trivially, PCB is what describes the state and the environment information of a process. PCB 的简图如下:

借助PCB，OS可 以全面管理进程的物理实体, 刻画进程的执行现状, 控制进程的执行

PCB 结构每个部分的相关内容与表示都可以在官网的Manual上看到, 其中在 Linux 下的 ps 指令就可以展示部分进程信息. pstree 可以展示出进程的父进程和子进程.

2. 进程映像

进程映像是某一时刻进程的内容及其执行状态集合. 随着进程数量的增多, 对进程的管理/进程间的通讯变得非常复杂, 我们需要一个叫做进程映像的中间层来解决这样的问题. 进程映像是操作系统管理进程和实现进程间通信的一个重要机制，其作用包括以下几个方面：

• 进程的创建和复制：当操作系统需要创建一个新进程时，会先将其对应的可执行文件读取到内存中，然后根据其映像信息来初始化进程的各种资源和状态；而当进程需要复制自身时（如fork操作），则可以通过复制进程映像来创建新的进程。
• 进程的调度和切换：当一个进程被挂起或者等待某些条件时，操作系统可以将其进程映像保存到交换空间（swap space）中，以释放内存资源；而当该进程再次被激活时，可以重新加载其进程映像，并恢复其原来的执行状态。
• 进程间通信：进程映像可以作为一种进程间通信的手段，通过共享内存、消息队列、管道等方式来传递数据和信息。在这种情况下，不同进程可以访问同一份进程映像，并在其中写入或读取所需的数据，以实现有效的进程协作。
• 进程的调试和分析：进程映像可以帮助我们理解、调试和分析进程的运行情况。通过读取进程映像中的代码、数据和堆栈信息等，我们可以了解进程的执行状态、调用关系、内存使用情况等，并通过相应的工具进行跟踪和分析。

进程1

进程2

... ...

进程n

3. 进程上下文

进程的执行需要环境支持，包括CPU现场和Cache中的执行信息. 我们将这样的环境与进程物理实体和称为进程上下文 (Process Context), 用来刻画进程的执行情况. 具体来说, 进程上下文包括如下的几种:

• 用户级上下文：用户程序块/用户数据区/ 用户栈/用户共享内存
• 寄存器上下文：PSW/栈指针/通用寄存器
• 系统级上下文：PCB/内存区表/核心栈

3.3. 进程管理的实现

Trivially, 进程管理就是如何管理操作系统的进程, 包括操作系统对进程的创建、调度、同步、通信、终止等活动进行有效地管理和协调. 具体来说, 操作系统的进程管理包括以下几个主要部分：

进程创建

• 操作系统初始启动时会创建承担系统资源分配和控制管理的一些系统进程，同时会创建一个所有用户进程的祖先，其他用户进程实在用户程序被提价与选中运行时被创建的.
• 操作系统通常将创建关系通过父子进程的关系来表示。
• 创建原语：进程表加一项、申请PCB(进程控制块)并初始化、生成唯一进程标识、建立进程映像、分配各种资源、移入就绪队列、通知操作系统某些模块

进程撤销

• 完成特定工作或出现严重错误后需要撤销，分为正常撤销和非正常撤销。
• 产生原因：运行结束、执行非法指令、用户态执行特权指令、时间配额到、等待时间超时、越界错误、共享内存区非法使用、程序性故障等。
• 撤销原语：从队列中移除、归还资源、撤销标识、回收PCB、移除进程表项

进程阻塞

• 使得进程让出处理器转而等待一个事件，比如等待资源等，阻塞是同步时间.
• 阻塞原语：保存现场信息、修改PCB、移入等待队列、调度其他进程执行

进程唤醒

• 等待时间完成时产生一个中断，激活操作系统，在系统的控制下将被阻塞进程唤醒
• 唤醒原语：等待队列中移出、修改PCB、移入就绪队列(该进程优先级高于运行进程触发抢占)

进程挂起

• 出现引起挂起的事件时，系统或进程会利用挂起原语把指定进程或处于等待态的进程挂起。
• 挂起原语：修改状态并出入相关队列、收回内存等资源送至对换区。
• 挂起原语可以由进程自己或其他进程调起。

进程激活

• 当系统资源尤其是内存资源充裕或请求激活进程时，系统或相关进程会调用激活原语将指定进车行激活。
• 激活原语：分配内存，修改状态并出入相关队列。
• 激活原语只能由其他进程调用。

其他

• 如修改进程特权，以上是一个进程控制的流程

4. 多线程技术

4.1. 多线程环境概述

4.2. 多线程的实现技术

5. 处理器调度

5.1. 处理器调度的层次

5.2. 处理器调度算法

这篇文章讲的很好

为什么在linux中 pstree 的根节点不是init

在现代Linux系统中，根节点通常是systemd（或者systemd的一个子进程），而不是传统的init进程。这是因为systemd是一种新的初始化系统，旨在取代传统的SysVinit和Upstart等系统。相比于传统的init系统，systemd具有更快的启动速度、更好的并行处理能力、更多的可管理性和更强的安全性等优点。在systemd初始化系统中，它会作为第一个进程启动，并负责启动所有其他系统服务和进程。因此，它成为了整个系统进程树的根节点。与传统的init进程类似，systemd也可以监控所有进程的状态，以确保系统各个方面都正常运行。但是，相比于init，systemd提供了更加全面和强大的服务管理功能，包括自动化启动、停止和重启服务、资源限制、日志记录、进程监控等等。

1. 抢占式(剥夺式)调度：当前正在运行的进程可能被操作系统中断，并转移到就绪态。处理器剥夺原则：
   1. 高优先级进程/线程可剥夺低优先级进程/线程。
   2. 运行进程/线程时间片用完后被剥夺。
2. 非抢占式(非剥夺式)调度：一个进程一旦处于运行态，它就不断执行直到终止，或者为等待I/O或请求某些操作系统服务而阻塞自己。
3. 与非抢占式调度相比，抢占式调度可能会导致较大的开销，但是可能对所有进程提供更好的服务，可以避免任何一个进程独占处理器太长时间

主要查看了 CSAPP

从 C 程序到可执行文件, 总共经过了这样几个部分:

1. Preprocess

在C语言中，预处理器 (C PreProcessor)是一种特殊的程序，用于在编译过程之前对源代码进行处理。预处理器会根据以 # 开头的预处理指令对源代码进行不同形式的转换，例如宏替换、文件包含等操作。

当我们使用C语言编写程序时，源代码通常包含三个部分：头文件（Header File）、函数定义和主函数。预处理器的作用就是将这些源代码文件合并起来，并生成一份纯C文件，也称为翻译单元（Translation Unit）。纯C文件中只包含了最终要编译的源代码，而没有任何预处理指令和注释。

生成纯C文件的过程，通常可以通过命令行工具 gcc -E 来执行，其中 -E 参数表示只进行预处理，不进行编译和链接。例如，假设我们有一个名为 test.c 的源文件，可以使用以下命令将其转换为纯C文件：

复制代码gcc -E test.c -o test.i

其中，-o 参数指定了输出文件的名称为 test.i(也可以是.c格式的)，该文件即为生成的纯C文件。

生成纯C文件的主要目的是方便调试和分析源代码。由于纯C文件已经去除了预处理指令和注释，因此可以更加方便地查看和分析源代码中真正要编译的部分。此外，生成纯C文件还可以帮助我们理解预处理器的工作原理，并调试和优化预处理器宏和指令。

上图是对 hello.c 程序进行操作, 生成的纯C中间文件居然多达550行

.i 格式 和 .c 格式有什么区别

.i 格式和 .c 格式都是C语言的源文件格式，它们之间的区别在于：

1. 后缀不同：.i 是纯C文件的后缀，而 .c 是包含了所有源代码和预处理指令的源文件的后缀。
2. 是否经过预处理：.i 文件是经过预处理器预处理后的纯C文件，而 .c 文件则包含了所有的源代码和预处理指令。在生成 *.i 文件时，预处理器会对源代码中的预处理指令进行展开并替换为相应的代码，同时还会去除注释和空行等无用信息，最终得到一个只包含有效C代码的文件。
3. 用途不同：.c 文件是编译器直接使用的源文件，其中包含了所有需要编译的代码和预处理指令。而 .i 文件通常用于调试和分析源代码，它已经去除了预处理指令和无用信息，方便用户查看和分析纯C代码。

总之，.i 和 .c 文件都是C语言的源文件格式，但 .i 文件是经过预处理器处理后的纯C文件，只包含有效的C代码，而 .c 文件则包含了所有的源代码和预处理指令。.i 文件一般用于调试和分析源代码，而 .c 文件是编译器直接使用的源文件。

2. Compile

3.

链接

在计算机科学中，链接（Linking）是将多个目标文件（Object File）或库文件（Library）组合成一个可执行文件的过程。在程序开发过程中，通常会将程序代码分为多个源文件进行编写和管理，每个源文件经过编译后都会生成目标文件。然后，这些目标文件需要被链接起来才能生成最终的可执行文件。

在链接的过程中，链接器会将不同的目标文件中定义的函数、变量等符号连接起来，以便程序正确地执行。具体来说，链接器会完成以下几个主要任务：

1. 符号解析（Symbol Resolution）：将目标文件中使用到的未定义符号与其他目标文件中定义的符号进行匹配，并将它们连接起来。
2. 重定位（Relocation）：由于目标文件中的地址空间与最终可执行文件中的地址空间可能会不同，因此链接器需要对目标文件中的一些地址进行修正，以便使它们在最终可执行文件中能够正确地访问目标对象。
3. 优化（Optimization）：链接器还可以对目标文件中的代码进行优化，以提高最终程序的性能和效率。

在不同的操作系统和编程语言中，链接的方式和实现都可能会有所不同。在C语言中，静态链接和动态链接是两种常见的链接方式，它们使用的链接器也不同。

链接分为静态链接和动态链接两种类型。

静态链接

静态链接是指将所有目标文件和库文件直接链接到最终生成的可执行文件中的过程。在静态链接期间，编译器将目标文件中使用到的库文件中的函数和变量 直接复制 到最终生成的可执行文件中，这使得最终的可执行文件中包含了所有需要的代码和数据，可以独立地运行于系统环境中。

具体来说做了两件事:

• 空间和地址分配
• 符号解析与重定位

优点：

• 可以在不安装任何其他软件的情况下，将可执行文件直接复制到其他计算机上运行。
• 执行速度相对较快，因为所有代码和数据都已经被复制到同一个文件中。

缺点：

• 可执行文件比较大，包含了所有需要的库代码和数据，因此占用的存储空间较大。
• 如果多个程序使用同一份库文件，则会出现代码重复的情况，浪费存储空间。
• 如果库文件更新了，需要重新链接并重新编译整个程序。

动态链接

动态链接是指在程序运行时才从共享库文件 (Shared Library) 中加载所需的函数和数据的链接方式。在动态链接期间，编译器只将程序中使用到的库函数的名称记录在可执行文件中，并不将函数的实现代码复制到可执行文件中。当程序运行时，操作系统会根据程序需要从共享库文件中动态加载所需的函数和数据。

具体来说有四个步骤:

• 动态链接器自举
• 装载共享对象
• 重定位与初始化
• 转交控制权

优点：

• 可执行文件相对较小，因为它只包含了函数名等链接信息，而没有库代码和数据。
• 不同的程序可以共享同一份库文件，节省存储空间。
• 如果库文件更新了，不需要重新编译整个程序，只需要替换共享库文件即可。

缺点：

• 程序在运行时需要加载共享库文件，会增加启动时间和内存使用量。
• 执行速度相对静态链接较慢，因为需要从共享库中加载函数和数据。

总之，静态链接适合独立部署的应用程序，而动态链接适合需要共享库文件的应用程序。

非常大程度上参考了这篇文章, 但是我的建议是 RTFM.

众所周知, 笔者的操作系统课烂得无法让人忍受, 并且笔者使用的是M1芯片的MacOS, 如果没有 LLDB, 笔者将难以进行这类底层代码的debug. 是时候学习一些 LLDB 的操作了.

1. Clang

Clang 是一个C、C++、Objective-C和Objective-C++编程语言的编译器前端。它采用了LLVM作为其后端，由LLVM2.6开始，一起发布新版本。它的目标是提供一个GCC (GNU Compiler Collection) 的替代品，支持了GNU编译器大多数的编译设置以及非官方语言的扩展。作者是Chris Lattner，在苹果公司的赞助支持下进行开发，而源代码许可是使用类BSD的伊利诺伊大学厄巴纳-香槟分校开源码许可.

Clang 项目包括 Clang 前端和 Clang 静态分析器等.

在Mac上, 编译运行 C 语言的指令是

$ clang <NAME>.c # 默认得到a.out文件
$ ./a.out

在这样的情况下生成的 a.out 文件, lldb a.out也会正常启动，但是无法顺利断点. 执行lldb a.out并顺利打断点需要使用clang的-g flag

clang -g main.c

此时会生成一个名为a.out.dSYM，此后就能顺利执行lldb a.out (注意不是 lldb a.out.dSYM)了

2. Run

在输入 lldb a.out 之后, 会进入lldb的调试界面. 如下:

此时输入 r 或者 run, 程序可以开始运行 (直到遇到错误或者断点处停下).

2.1. 设置断点

(lldb) breakpoint set -f <NAME>.c -l <LINE_NUM> 
# 或者是
(lldb) br s -f <NAME>.c -l <LINE_NUM> 
# 或者是
(lldb) b <NAME>.c: <LINE_NUM> 
# 或者是
(lldb) b <NAME>.c: <LINE_NUM> 

## 或者是
(lldb) br <FUNC_NAME> # 这一指令会将断点设在函数体内第一行.

这里 <NAME>.c 表示 C 文件的名字(注意不是 a.out), <LINE_NUM> 表示想要将断点设在 C 文件的第几行

如果编译时没有加上 -g flag, 此时将遇到这样的报错

2.2. 删除断点

(lldb) br list #这条指令将会按照顺序展示所有的断点
(lldb) br del <BREAKPOINT_NUM> #这条指令将会删去第 <BREAKPOINT_NUM> 条断点

3. Control Flow

只有三种平凡的用法

(lldb) s(tep) # 单步执行, 如果遇到函数则会进入函数体
(lldb) n(ext) # 下一步, 如果遇到函数则跳过, 不会进入函数体内
(lldb) c(ontinue) # 直接运行到下一个断点处

4. Variables

打印出某个变量的值

(lldb) p <VAR_NAME>

考虑到作用域, 在一个 C 项目中很可能出现同名的变量, 这个时候需要选择好帧栈.

(lldb) bt # 展示所有的栈

(lldb) frame select <FRAME_NAME> #选择特定的帧栈
# 或者是
(lldb) fr s <FRAME_NAME> #选择特定的帧栈

(lldb) frame variable # 展示当前帧栈内所有的变量
# 或者是
(lldb) fr variable

5. Watch Point

watchpoint 与breakpoint有类似之处但是也有区别, watchpoint 是当监视的变量被修改时, 则停止运行. breakpoint 是当程序运行到特定的位置时, 则停止运行.

当开始 run 之后, 进行如下的输入.

(lldb)watchpoint set variable <GLOBAL_VAR> 
# 或者是
(lldb)w s v <GLOBAL_VAR> 

此时 continue, 可以继续执行.

(lldb)watchpoint list
# 或者是
(lldb)w list

这样的指令可以监视所有的watchpoint

6. Kill

直接输入 kill 会杀死当前的进程 (每个 run 对应一个进程).

首次接触 $\LaTeX$ 还是一年之前敲数据科学和离散数学笔记的时候. 那个时候把关于概率论/离散数学的符号搞的透熟, 后来才发现有截图识别这种东西.

长久以来一直没有掌握 $\LaTeX$ 的正经使用, 是时候了.

本文主要参考:

• overleaf官网的doc
• nybgg的博客

1. Writing your first piece of $\LaTeX$

The first step is to create a new LATEX project. You can do this on your own computer by creating a new .tex file; alternatively, you can start a new project in Overleaf.

Let’s start with the simplest working example, which can be opened directly in Overleaf:

\documentclass{article}
\begin{document}
First document. This is a simple example, with no 
extra parameters or packages included.
\end{document}

[ Open this example in Overleaf.](https://www.overleaf.com/docs?engine=pdflatex&snip_name=Simplest+working+example+LaTeX+document&snip=\documentclass{article} \begin{document} First+document.+This+is+a+simple+example%2C+with+no+ extra+parameters+or+packages+included. \end{document}) This example produces the following output.

$\large\text{to-be-continued}$.

大创的中期答辩马上就要到了, 为了 省事 做出好看的效果, 在 GitHub 上发现了这样一个宝藏.

效果倒是和著名的 reveal.js 还有衍生物 reveal-md.js 差不多, 但是比 reveal.js 简单, 比 reveal-md 内容丰富.

这里是官网. 废话不多说, 直接上成果.

主要参考了这篇博客.

1. 文件系统

维基百科对于文件系统给出了如下的定义和解释:

​ 计算机的文件系统是一种存储和组织计算机数据的方法，它使得对其访问和查找变得容易，文件系统使用文件和树形目录的抽象逻辑概念代替了硬盘和光盘等物理设备使用数据块的概念，用户使用文件系统来保存数据不必关心数据实际保存在硬盘（或者光盘）的地址为多少的数据块上，只需要记住这个文件的所属目录和文件名。在写入新数据之前，用户不必关心硬盘上的那个块地址没有被使用，硬盘上的存储空间管理（分配和释放）功能由文件系统自动完成，用户只需要记住数据被写入到了哪个文件中。

​ 文件系统通常使用硬盘和光盘这样的存储设备，并维护文件在设备中的物理位置。但是，实际上文件系统也可能仅仅是一种访问资料的界面而已，实际的数据可能是通过网络协议（如NFS、SMB、9P等）提供的或者暂存于内存上，甚至可能根本没有对应的文件（如proc文件系统）。

​ 严格地说，文件系统是一套实现了数据的存储、分级组织、访问和获取等操作的抽象数据类型（Abstract data type）。

2. FAT

​ FAT (File Allocation Table, 文件分配表) 是一种由微软发明并拥有部分专利的文件系统，供MS-DOS使用，也是所有非NT核心的Windows系统使用的文件系统。

​ FAT文件系统考虑当时电脑性能有限，所以未被复杂化，因此几乎所有个人电脑的操作系统都支持。这特性使它成为理想的软盘和存储卡文件系统，也适合用作不同操作系统中的资料交流。

​ 但FAT有一个严重的缺点：当文件删除后写入新资料，FAT不会将文件整理成完整片段再写入，长期使用后会使文件资料变得逐渐分散，而减慢了读写速度。碎片整理是一种解决方法，但必须经常磁盘碎片整理来保持FAT文件系统的效率。

3. FAT12

​ 初期的FAT就是现在俗称的FAT12。作为软盘的文件系统，它有几项限制：

• 不支持分层性结构
• 簇寻址只有12位（这使得控制FAT有些棘手）
• 而且只支持最多32M的分区.

​ 当时入门级的磁盘是5.25"、单面、40磁道、每个磁道8个扇区、容量略少于160KB。上面的限制超过了这个容量一个或几个数量级，同时允许将所有的控制结构放在第一个磁道，这样在读写操作时移动磁头。这些限制在随后的几年时间里被逐步增大。

​ 由于唯一的根目录也必须放在第一个磁道，能够存放的文件个数就限制在几十个。

FAT12的基本组织单位

• byte: 基本数据单位——在FAT12中, 没有比byte更小单位的数据
• sector: 磁盘中的最小数据单元——磁盘的读写最小只能以一个sector为一个单位
• cluster: 一个cluster是一个或多个扇区

FAT12 文件系统的组成

FAT12 Boot Sector

主引导区的大小为512个字节, 主引导区的构成如下表

根目录区的目录项

根目录区由若干个目录项构成, 每个目录项的大小是32个byte

我真的很讨厌 markdown 的表格

FAT

FAT是FAT12的数据组织核心

在 FAT12 文件系统中, 包括两个 FAT (File Allocation Table): FAT1 和 FAT2, 两者是相互备份的关系 ，数据内容完全一致.

从数据结构的角度看, FAT表是一个有向关系图, 这个图记录了文件先后关系.

FAT表包括若干个紧密分布的表项 (FATEntry), 每个表项占用12bit (也就是说3个表项占用2个字节), 每个表项都与数据区中的一个簇相对应，而且表项的序号也是与簇号一一对应的. 当然, 也有一些特例

• FATEntry的值 $\geq$ 0xFF8，表示当前簇已经是本文件的最后一个簇
• FATEntry的值为 0xFF7, 表示它是一个坏簇

在1.44M软盘上，FAT前三个字节 (即前两个FATEntry) 的值是固定的: 0xF0、0xFF、0xFF, 用于表示这是一个应用在1.44M 软盘上的FAT12 文件系统。本来序号为 0和1的FAT表项应该对应于簇0和簇1，但是由于这两个表项被设置成了固定值，Cluster0 和 Cluster1就没有存在的意义了，所以数据区就起始于 Cluster2.

FAT 表以一种非常优雅的方式规范了文件数据的先后关系. 假设 $DIR\_FstClus$ 表示文件第 $0$ 簇 (扇区) 的位置, 第 $i$ 个表项 $vec[i]$ 表示文件数据的实际位置, 则文件第一扇区的位置为 $vec[DIR\_FstClus]$ , 且迭代地有, 第 $i+ 1$ 个表项的实际位置为

这一节讲的很迷幻, 哥们记完了笔记但还是不怎么懂

1. $\small \text{Symbol Table}$

$def$: 符号表 ($\text{Symbol Table}$) 是用于保存各种信息的数据结构.

$\text{DSL}$ (领域特定语言): 通常只有单作用域 (全局作用域), e.g. $\text{SQL}$, $\text{MATLAB}$

$\text{GPL}$ (通用程序设计语言): 通常需要嵌套作用域, e.g. $\text{Python}$, $\text{Java}$

在 SysY 语言中, 我们结合 Symbol / Scope / Type 等抽象的概念开展了如下的设计.

2. $\small\text{Attribute Grammar}$

对于已经涉及到的几个概念, 可以有对应的文法 $G$ 来刻画.

• $\text{Lexical Analysis}$: $\text{Regular Expression}$
• $\text{Syntactic Analysis}$: $\text{Context-free Grammar}$
• $\text{Semantic Analysis}$: $\textcolor\red{\text{Attribute Grammar}}$

$Knuth$ 在他的论文中提到了两种属性:

• $\text{synthesized attributes}$
• $\text{inherited attributes}$

针对这两种属性, 一般地, 有两种计算属性值的方法:

• Offline: 已经有了语法分析树, 按照从左到右的深度优先顺序遍历语法分析树, 计算属性值. 关键: 在合适的时机执行合适的动作，计算相应的属性值
• Online: 在语法分析过程中实现属性文法. 基本思想: 一个动作在它左边的所有文法符号都处理过之后立刻执行.$B\to X\{a\}Y$ (其中 $\{a\}$ 表示 action)

在这里, 我们主要考虑 Online 方法

2.1. $\small\text{Syntax-Directed Definition}$

$def:$ 语法制导($\text{SDD}$) 是一个**上下文无关文法和属性及规则的结合. $\text{SDD}$ 唯一确定了语法分析树上每个非终结符节点的属性值**.

与 $\text{SDD}$ 相对应的, 我们可以将语法树扩充为注释 (annotated) 语法分析树: 显示了各个属性值的语法分析树. e.g.

2.2. $\small\text{Synthesized Attribute}$

$def:$ 节点 $N$ 上的综合属性只能通过 $N$ 的子节点或 $N$ 本身的属性来定义.

2.3. $\small{S \text{-Attributed Definition}}$

$def:$ 特别地, 如果一个 $\text{SDD}$ 的每个属性都是综合属性, 则它是 $S$ 属性定义.

为了描述 $S$ 属性定义, 我们借助一个叫做依赖图的新概念. 依赖图用于确定一棵给定的语法分析树中各个属性实例之间的依赖关系. 下图是依赖图的一个例子.

更加具体地, $S$ 属性定义的依赖图刻画了属性实例之间自底向上的信息流动. $S$ 属性定义的一个依赖图如下.

此类属性值的计算可以在自顶向下的 $LL$ Syntactic Analysis过程中实现: 在 $LL$ 语法分析器中, 递归下降函数 $A$ 返回时, 计算相应节点 $A$ 的综合属性值.

2.4. $\small\text{Inherited Attribute}$

节点 $N$ 上的继承属性只能通过 $N$ 的父节点、$N$ 本身和 $N$ 的兄弟节点 (可以是左兄弟或者是右兄弟) 上的属性来定义.

信息流向: 先从左向右、从上到下传递信息, 再从下到上传递信息. 同样, 可以通过依赖图来可视化这样的信息传递流向.

2.5. $\small{L\text{-Attributed Definition}}$

$def$: 如果一个 $\text{SDD}$ 的每个属性都满足如下的条件, 则它是 $L$ 属性定义.

        $(1)$ 要么是综合属性

        $(2)$ 要么是继承属性, 但是它的规则满足这样的限制: 对于产生式 $A \to X_1X_2 ...X_n$ 及其对应规则定义的继承属性 $X_i .a$, 这个规则只能使用:

                ($\text{a}$) 和**产生式头 $A$** 关联的继承属性.

                ($\text{b}$) 位于**$X_i$ 左边的文法符号实例 $X_1, X_2, ..., X_{i−1}$ 相关的继承属性或综合属性**.

                ($\text{c}$) 与这个 $X_i$ 的实例本身相关的继承属性或综合属性, 但是在由这个 $X_i$ 的全部属性组成的依赖图中不存在环.

一个自然的想法是, 将 $L$ 属性定义和 $LL$ 文法结合起来 (毕竟 Online 模式的属性定义就是要在文法分析的时候加进来)

对于递归下降的子过程 $A \to X_1...Xi...X_n$

• 在调用 $X_i$ 子过程之前, 计算 $X_i$ 的继承属性
• 以 $X_i$ 的继承属性为参数调用 $X_i$ 子过程
• 在 $X_i$ 子过程返回之前, 计算 $X_i$ 的综合属性
• 在 $X_i$ 子过程结束时返回 $X_i$ 的综合属性

$\small{\text{S-AD} \ \ V.S.\ \ \text{L-AD}}$

对于表达式 $XY^*$ 我们分别给出 (左递归的) $S$ 属性定义和 (右递归的) $L$ 属性定义如下:

2.6. $\small\text{Postfix Notation}$

$def$: 后缀表示 ($\text{Postfix Notation}$) 的递归定义如下:

        $(1)$ 如果 $E$ 是一个 变量或常量, 则 $E$ 的后缀表示是 $E$ 本身.

        $(2)$ 如果 $E$ 是形如 $E_1\ op\ E_2$ 的表达式, 则 $E$ 的后缀表示是 $E^′_1E^′_2\ op$, 这里 $E^′_1$ 和 $E^′_2$ 分别是 $E_1$ 与 $E_2$ 的后缀表达式.

        $(3)$ 如果 $E$ 是形如 $(E_1)$ 的表达式, 则 $E$ 的后缀表示是 $E_1$ 的后缀表示.

2.7. $\small\text{Syntax-Directed Translation Scheme}$

$def$: 语法制导的翻译方案 ($\text{SDT}$) 是在其产生式体中嵌入语义动作的上下文无关文法.

一个自然的想法是, 如何将带有语义规则的 $\text{SDD}$ 转换为带有语义动作的 $\text{SDT}$: 使用**后缀翻译方案**, $i.e.$ 所有动作都在产生式的最后.

这一部分知识的直观感受: 新的定义巨多无比但是内容却又都很 trivial. 需要对定义相当熟悉.

“根据定义.” ——张运清教授.

1. Parser 介绍

1.1. Parser 的功能

Parser 接受经过 Lexer 解析之后产生的符号流, 生成一个语法树

1.2. Parser 的三种设计方法

难度递增

• Parser Generator (e.g. ANTLR4)
• Handwritten Lexer (由于难度太大而直接跳过)
• Automated Lexer

2. Parser Generator —— ANTLR4

文法 (grammar), 词法 (lexical) 和语法 (syntax) 的区别

这一部分的具体代码可以查看蚂蚁老师的视频

2.1. ANTLR4消除文法二义性

编程语言的文法不能是二义性的. 下面介绍几种经典的二义性文法.

1. 悬空的ELSE

一个经典的二义性的例子是如下的文法 (悬空的else):

如果给出如下的语句, 显然会产生有歧义的解释:

if a then if b then c else d

为了消除程序语言解释的二义性, 我们可以将上面的文法改造成没有二义性的写法如下:

但是这样的写法不够好, 因为文法变得非常的复杂.

不过, ANTLR4有自动消除文法二义性的功能, 即: 只需要给出第一种写法, ANTLR4能自动解析出和第二种写法相同的效果. ANTLR4消除二义性的方式是, 对于可能有多种解释方式的语句, 写在前面的解释方式具有更高的优先级, 可以优先被解释.

2. 运算符结合性导致的二义性

结合性，就是当一个表达式中出现多个优先级相同的运算符时，先执行哪个运算符：先执行左边的叫左结合性，先执行右边的叫右结合性.

对于如下的文法:

如果给出如下的简单语句:

1 - 2 - 3

可能会解析成两种结果

• 左结合: (1 - 2) - 3
• 右结合: 1 - (2 - 3)

同样, ANTLR4也可以消除这样的二义性, 其做法是: 对于没有明确规定是左结合还是右结合的运算符, 默认是左结合. 对于想要明确指出是右结合的运算符, 可以用如下的写法:

3. 运算符优先级导致的二义性

同样, ANTLR4 认为写在前面的运算符具有更高的优先级. 如上的语句不需要进行任何的修改, 就可以被 ANTLR4 无歧义地识别. 但是值得注意的是, 一些 上古时期的 语法分析器生成器并不能正确地处理优先级.

理论上, 我们还是可以把这种写法改成无歧义的写法, 一种方法是写成 左递归(左结合) 的形式:

之所以说这是左递归的写法, 因为运算符左侧递归调用了 expr (而在原本的写法中, 运算符左侧和右侧都递归调用了 expr, 因此既可以用左结合的方法来解释, 也可以用右结合的方法来解释)

另一种改造方法是改造成 右递归(右结合) 的形式 (which is not trivial):

不难发现, 虽然这样也能算出正确的结果, 但是副作用是把减号和乘号变成了右结合运算符

2.2. ANTLR4 如何处理节点事件

ANTLR4考虑了两种处理节点事件的设计模式: Listener模式 和 Visitor模式. 同时, ANTLR4 将“语法树的构建”和“语法树节点事件的处理”有意地分离开来, 使得程序员处理节点事件的难度和复杂度大大降低.

3. CFG

3.1. CFG 的定义

$def:$ 上下文无关文法 (Context-Free Grammar) $G$ 是一个四元组:

其中:

$(1)$ $T$ 是是终结符号 ($\textbf{Terminal}$) 集合, 对应于词法分析器产生的词法单元.

$(2)$ $N$ 是非终结符号 ($\textbf {Non}\mbox-\textbf{terminal}$) 集合.

$(3)$ $P$ 是产生式 ($\textbf {Production}$) 集合.

​ $(3.1)$ 头部/左部 ($\textbf {Head}$) $A$: 单个非终结符. (这正是 CFG 区别于 CSG 的地方)

​ $(3.2)$ 体部/右部 ($\textbf {Body}$) $\alpha$: 终结符与非终结符构成的串, 也可以是空串 $\epsilon$.

$(4)$ $S$ 为开始 ($\textbf {Start}$) 符号。要求 $S \in N$ 且唯一.

这里维基百科说得更清楚

与 CFG 相对的概念是 CSG (Context-Sensitive Grammar, 上下文相关文法). 下图给出了一个上下文相关文法的例子

3.2. CFG 的语义

上下文无关文法 $G$ 定义了一个语言 $L(G)$

0. Derivation

推导 (derivation) 指的就是将某个产生式的左边替换成它的右边. 推导时需要考虑两个平凡的问题:

• 每一步推导需要选择替换哪个非终结符号
• 每一步推导需要使用哪个产生式

关于推导, 有一些形式化表述:

• $A\Rightarrow \alpha$ : $A$ 经过一步推导得出 $\alpha$
• $A \overset +\Rightarrow \alpha$ : $A$ 经过过一步或多步推导得出 $\alpha$
• $A\overset *{\Rightarrow} \alpha$ : $A$ 经过零步或多步推导得出 $\alpha$

1. Sentential Form

$def: $ 如果 $S \stackrel{*}{\Rightarrow} \alpha$ , 且 $\alpha \in (T\cup N)^*$, $S$ 为开始符号, 则称 $\alpha$ 是文法 $G$ 的一个句型 (Sentential Form)

2. Sentence

$def: $ 如果 $S \overset * \Rightarrow \omega$, 且 $\omega \in T^*$, $S$ 为开始符号, 则称 $\omega$ 是文法 $G$ 的一个句子 (Sentence)

3. Language of Grammar

$def: $ 文法 $G$ 的语言 (Language) $L(G)$ 是它能推导出的所有句子构成的集合

其中 $S$ 为开始符号.

3.3. $\text{Chomsky}$ 谱系

语言学家Chomsky在这篇论文中提出了Chomsky谱系, 刻画了不同文法的表达能力.

为什么不使用 强大又优雅 的正则表达式来描述程序设计语言的语法: 可以证明, 正则表达式的表达能力严格弱于上下文无关文法 (实际上这很符合直观感受)

• 每个正则表达式 $r$ 对应的语言 $L(r)$ 都可以使用上下文无关文法来描述
• 存在某种语言, 能用上下文无关文法描述, 但是不能用正则表达式描述 (详见下面的Pumping Lemma)

实际上, Chomsky将文法分成四类, 这四种文法的形式化定义都和上面的CFG类似, 唯一不同的地方就是产生式的规则. 四者的产生式规则区别如下:

Pumping Lemma for Regular Languages

$Thm:$ $L=\{a^nb^n|n\geq 0\}$ 无法用正则表达式描述. 证明如下:

假设存在正则表达式 $r$ $s.t.$ $L(r)=L$ , 则存在有限状态自动机 $D(r): L(D(r))=L$ , 假设其状态数是 $k$ , 如果输入 $a^m\ (m> k)$ , 根据如下的图示:

$D(r)$ 也能接受 $a^ib^{i+j}$, 矛盾.

Pumping Lemma for Context-free Languages

$Thm$: $L=\{a^nb^nc^n|n\geq 0\}$ 无法用上下文无关文法描述. 证明 不会 略去.

4. 递归下降的 $LL$ 语法分析器

在无二义性的文法中, 每个句子对应唯一的一棵语法分析树. 有如下常见的文法:

值得注意的是, 无论是常见的 $LL$ 还是 $LR$ 算法, 都无法处理二义性文法. 要处理二义性文法, 需要借助 $LL(*)/\text{ALLStar}$ 算法.

$\textcolor\red LL(1)$ : 从左向右 ($\text{left to right}$) 读入词法单元

$L\textcolor \red L(1)$ : 构建最左推导 ($\text {leftmost}$) (总是选择最左边的非终结符进行展开)

$LL(\textcolor \red 1)$ : 只需向前看一个输入符号便可确定使用哪条产生式

而 $LL(1)$ 语法分析器具有如下的四个特点:

• 自顶向下
• 递归下降
• 基于预测分析表
• 适用于 $LL(1)$ 文法

4.1. 自顶向下构建语法分析树

• 根节点是文法的起始符号 $S$
• 每个中间节点表示对某个非终结符应用某个产生式进行推导: 需要考虑
  • 选择哪个非终结符: $LL(1)$ 总是选择最左边的非终结符进行展开.
  • 选择哪个产生式: 在 $LL(1)$ 文法中, 只会出现一种选择.
• 叶节点是词法单元流 $\omega\$$: 仅包含终结符号与特殊的文件结束符 $\$$ ($\text {EOF}$)

4.2. 递归下降的实现

递归下降可以这样实现: 为每个非终结符写一个递归函数 内部按需调用其它非终结符对应的递归函数, 下降一层 .

4.3. 预测分析表

预测分析表指明了每个**非终结符在面对不同的词法单元或文件结束符时, 该选择哪个产生式** (按编号进行索引) 或者报错 (空单元格)

4.4. $LL(1)$ 文法

$def:$ 如果文法 $G$ 的预测分析表是无冲突的, 则 $G$ 是 $LL(1)$ 文法.

其中, 无冲突指的是每个单元格里只有一个生成式 (编号). 对于当前选择的非终结符, 仅根据输入中当前的词法单元 (即 $LL(1)$ ) 即可确定需要使用哪条产生式. 这里需要介绍两个概念:

• $\text F\small \text{IRST}\normalsize(\alpha)$ 集合
• $\text F\small \text{OLLOW}\normalsize(A)$ 集合

1. $\text F\small \text{IRST}\normalsize(\alpha)$ 集合

$\text{F}\small \text{IRST}\normalsize (α)$ 是可从 $α$ 推导得到的句型的首个终结符号的集合. 形式化地, $\text F\small\text{IRST}\normalsize(α)$ 有定义如下.

$def: $ $\forall \alpha \in (T\cup N)^*$ ( $\alpha$ 是产生式的右部):

其中 $\beta \in (T\cup N)^*$.

考虑非终结符 $A$ 的所有产生式 $A → α_1, A → α_2, . . . , A → α_m$, 如果它们对应的 $\text F\small\text {IRST}\normalsize(α_i)$ 集合互不相交, 则只需查看当前输入词法单元, 即可确定选择哪个产生式 (或报错).

为了计算 $\text{F}\small\text{IRST}\normalsize(\alpha)$ , 先计算 $\alpha$ 中每个符号 $X$ 的 $\text F\small \text{IRST}\normalsize(X)$ 集合

不断应用上面的规则, 直到每个 $\text F\small \text{IRST}\normalsize(X)$ 都不再变化. 再计算每个符号串 $\alpha$ 的 $\text F\small \text{IRST}\normalsize(\alpha)$ 集合. 首先将 $\alpha$ 中的第一个符号 $X$ 取出来, 则:

此时有:

最后, 如果 $\epsilon \in L(\alpha)$ , 则将 $\epsilon$ 加入 $\text F\small \text{IRST}\normalsize(\alpha)$.

下面给出计算 $\text F\small \text{IRST}$ 集合的一个例子. 要特别注意什么时候要加入 $\epsilon$ 而什么时候不要.

2. $\text F\small \text{OLLOW}\normalsize(A)$ 集合

$\text F\small\text{OLLOW}\normalsize(A)$是可能在某些句型中紧跟在非终结符 $A$ 右边的终结符的集合. 形式化地, $\text F \small\text{OLLOW}\normalsize(A)$ 有定义如下.

$def:$ 对于任意的 (产生式的左部) 非终结符 $A \in N$ :

其中 $\beta, \gamma\in (T\cup N)^*$.

考虑产生式 $A \to \alpha$. 特别地, 如果从 $\alpha$ 可能推导出空串 $(\textcolor \red { \alpha \overset * \Rightarrow \epsilon})$, 则只有当当前词法单元 $t \in \text F \small\text{OLLOW}\normalsize(A)$ , 才可以选择该产生式.

为了给每个非终结符 $X$ 计算 $\text F\small \text{OLLOW}\normalsize(X)$ 集合, 需要考虑如下的算法:

不断应用上面的规则, 直到每个 $\text F\small \text{OLLOW}\normalsize(X)$ 都不再变化.

下面给出构建 $\text F\small \text{OLLOW}$ 集合的一个例子.

4.5. 计算预测分析表

现在我们已经有了 $LL(1)$ 文法的 $\text F \small \text {IRST}$ 与 $\text F \small\text{OLLOW}$ 集合, 那么如何根据 $\text F \small \text {IRST}$ 与 $\text F \small\text{OLLOW}$ 集合计算给定文法 $G$ 的预测分析表 ?

对于每条产生式 $A \to \alpha$ 与终结符 $t$, 如果:

则在表格 $[A,t]$ 中填入 $A \to \alpha$ (的编号).

让我们重新审视 $LL(1)$ 文法的定义.

$def:$ 如果文法 $G$ 的预测分析表是无冲突的, 则 $G$ 是 $LL(1)$ 文法.

4.6. $LL(0)$

$LL(0)$ 是非递归的预测分析算法.

4.7. 处理非 $LL(1)$ 文法

如果文法 $G$ 不是 $LL(1)$ 文法, 但仍然想使用 $LL(1)$ 语法分析器来处理. 我们没有好的办法, 只能将该文法转换成 $LL(1)$ 文法. 有两种常见的方法:

• 消除左递归
• 提取左公因子

以表达式的文法为例:

1. 消除左递归

左递归包括直接左递归 (Direct Left Recursion) 和间接左递归 (Indirect Left Recursion)

一个例子

在 2.2 中, 我们讲到了将上述文法改成如下的文法, 可以消除二义性, 但是不能改变左递归性.

$LL(1)$ 不能处理左递归的文法, 因为 $E$ 在不消耗任何词法单元的情况下, 直接递归调用 $E$ 本身, 造成了死循环. 一个可能的解决方法是, 将上述的文法改成右递归, 如下:

并且在此基础上构建其预测分析表:

但是这样改造的代价是, 文法变得非常复杂, 而且失去了原本直观的含义.

消除直接左递归

对于这样直接左递归 $A\to A\alpha\ |\ \beta$ , 可以改成这样的右递归:

更加一般地, 行如下的左递归 (其中, $\beta_i$ $(1\leq i \leq n)$ 不以 $A$ 开头) :

可以统一地构造出这样的右递归写法:

消除间接左递归

算法的成立条件是:

• 文法中不存在环 (形如 $A \overset * \Rightarrow A$ 的推导)
• 文法中不存在 $\epsilon$ 产生式 (形如 $A \to \epsilon$ 的产生式)

2. 提取左公因子 (Left-Factoring)

在 2.2 中, 我们讲到了提取左公因子无助于消除文法二义性. 但是 ANTLR4 可以处理有左公因子的文法. (开挂属于是)

5. Adaptive $\small LL(*)$ 语法分析算法

可以从这篇论文中了解到 $\text{Adaptive}\ LL(*)$ 设计的更多细节, 但是这片论文运用了大量的形式化方法, 我看不懂 目前还看不懂.

这一算法又被缩写成 $ALLStar$ 算法

两个主题:

• 掌握: 处理表达式优先级
• 了解: 处理语法错误

5.1. $ALL(*)$ 处理表达式优先级

ANTLR4 ( 使用了 $ALL(*)$ 算法的分析器) 的四个优势:

$ALL(*)$ 根据 g4 文件中定义的优先级, 将文法大致改写成如下的形式 (经简化):

expr[int _p]: 
			 (
			 		<NON-LEFT-RECURSIVE-TERMINAL_1>
			 	| <NON-LEFT-RECURSIVE-TERMINAL_2>
			 	| ...
			 	| <NON-LEFT-RECURSIVE-TERMINAL_m>
			 )
			 (
			 		{$_op <= <PRIORITY_1>}? <LEFT-RECURSIVE-TERMINAL_1> expr[<PRIORITY_1> + 1/0]
			 		{$_op <= <PRIORITY_2>}? <LEFT-RECURSIVE-TERMINAL_2> expr[<PRIORITY_2> + 1/0]
			 		...
			 		{$_op <= <PRIORITY_{n-m}>}? <LEFT-RECURSIVE-TERMINAL_{n-m}> expr[<PRIORITY_{n-m}> + 1/0]
			 )*

• 想要该运算符实现左结合, 则右侧递归时选择优先级上升: <PRIORITY_1> + 1
• 想要实现右结合, 则优先级不变

5.2. $ALL(*)$ 处理错误

6. 不断规约的 $LR$ 语法分析器

这篇文章介绍了关于LR的基本知识

自底向上的、 不断归约的、 基于句柄识别自动机的、 适用于$LR$ 文法的、 $LR$ 语法分析器

• $LL(k)$ 的弱点: 在仅看到右部的前 k 个词法单元时就必须预测要使用哪条产生式

• $LR(k)$ 的优点: 看到与正在考虑的这个产生式的整个右部对应的词法单元之后再决定

自底向上构建语法分析树

• 根节点是文法的起始符号 $S$
• 每个中间非终结符节点表示使用它的某条产生式进行归约
• 叶节点是词法单元流 $w$$ 仅包含终结符号与特殊的文件结束符 $

这里实在是难以记录, 只能意会. 不妨查看蚂蚁老师的视频.

1. Lexer介绍

1.1. Lexer的功能

ANTLR4中的g4文件和ANTLR3中的g文件, 都是词法单元的规约

1.2. 词法分析器的三种设计方法

难度递增

• Lexer Generator (e.g. ANTLR4)
• Handwritten Lexer
• Automated Lexer

生产环境下的编译器 (如 gcc) 通常选择手写词法分析器

2. 词法单元的规约

词法单元的规约需要 形式化 定义

2.1. 非形式化的定义

1. id: 以字母开头的字母/数字串
2. Language: id 所构成的集合
3. Definition of Language: 给定 Alphabet $\Sigma$ 上一个任意的可数的 String 集合

(3) Alphabet: 字母与数字等符号的集合

• $def$: Alphabet $\Sigma$ 是一个有限的符号集合.

(4) String: 语言中的每一个元素(即一个id)称为串

• $def$: Alphabet $\Sigma$ 上的 String (s) 是由 $\Sigma$ 中符号构成的一个有穷序列.

• 特殊地, 空串 $\epsilon$ 是满足 $|\epsilon|=0$ 的串

String 上定义了两种运算

• 连接运算: 如果 $x$ 和 $y$ 都是一个 String, 则

• 指数运算: 如果$s$ 是一个 String, 则

根据上述的四个定义, 我们不难发现: 语言是串的集合

2.2. 形式化的定义

语言形式化的定义, 我们借助了集合的概念. 对于集合的运算, 我们首先需要回顾闭包的概念, 闭包允许我们通过有限集构造出无限集

正闭包与Kleene闭包

这里的连接应该是一种类似于 Descartes积的东西

我们发现, 如果 $\mathbf L := \{A, B, . . . , Z, a, b, . . . , z\},\mathbf D:=\{= 0, 1, . . . , 9\} $, 那么根据集合运算的定义, id 可以形式化地定义为:

接下来要引入 (简洁、优雅、强大的) 正则表达式.

2.3. 正则表达式的形式化定义

每个正则表达式 $r$ 对应着一个正则语言, 记作 $L(r)$. 给定字母表 $\Sigma$, $\Sigma$ 上的正则表达式以及对应的正则语言由且仅由如下的4条规则定义:

1. $\epsilon$ 是正则表达式:

2. $\forall a\in \Sigma$, $a$ 是正则表达式:

3. 如果 $r$ 是正则表达式, 则 $(r)$ 也是正则表达式:

4. 如果 $r$ 与 $s$ 是正则表达式, 则 $r|s$, $rs$, $r^*$ 也是正则表达式:

其中, 运算优先级满足

3. Lexer Generator—— ANTLR4

3.1. ANTLR4中的冲突解决规则

这篇文章介绍了贪婪匹配和非贪婪匹配的区别

• 最前优先匹配
• 最长优先匹配
  • 1.23不会被匹配成1, ., 23
  • >=不会被匹配成 > 和 =
• 非贪婪匹配
• 在默认情况下的量词匹配都是贪婪匹配, 只需要在量词后加上?, 就会转变为非贪婪匹配
• ANTLR4采用这样的非贪婪匹配

4. Automated Lexer

4.1. Definitions

自动机(Automaton; Automata) 的两大要素: 状态集 $S$ 和状态转移函数 $\delta$

在自动机理论中, 根据表达/计算能力的强弱, 自动机可以分为不同层次.

在接下来的全部内容中, 我们将试图生成一个正则表达式的词法分析器 (也就是说, 下面的定义可能有其狭义之处).

NFA

$def$: 非确定性有穷自动机 (Nondeteministic Finite Automaton) $\mathcal A$ 是一个五元组:

where:

(1) $\Sigma$ 是字母表 ($\epsilon \not \in \Sigma$)

(2) $S$ 是有穷的状态集合

(3) $s_0$ 是唯一的初始状态, $s_0 \in S$

(4) $\delta$ 是状态转移函数:

(5) $F$ 是接受状态的集合, $F\subseteq S$

约定: 所有没有对应出边的字符默认指向一个默认不存在的 “空状态” $∅$

(非确定性) 有穷自动机是一类极其简单的计算装置 它可以识别 (接受/拒绝) $\Sigma$ 上的字符串

Accept

$def$: NFA $\mathcal A $ 接受String $x$, 当且仅当存在一条从开始状态 $s_0$ 到某个接受状态 $f\in F$, 标号为 $x$ 的路径.

根据这样的定义, $\mathcal A$ 定义了一种语言 $L(\mathcal A)$: 即所有能被 $\mathcal A$ 接受的字符串所构成的集合

在上面的例子中, $\mathcal A$ 的语言 $L(\mathcal A)$ 就是如下的正则表达式定义的正则语言:

DFA

$def$: 确定性有穷自动机 (Deteministic Finite Automaton) $\mathcal A$ 是一个五元组:

其中:

(1) $\Sigma$ 是字母表 ($\epsilon \not \in \Sigma$)

(2) $S$ 是有穷的状态集合

(3) $s_0$ 是唯一的初始状态, $s_0 \in S$

(4) $\delta$ 是状态转移函数:

(5) $F$ 是接受状态的集合, $F\subseteq S$

约定: 所有没有对应出边的字符默认指向一个 “死状态”

直觉上, DFA 和 NFA 的区别在于, DFA 的每一个节点的出边都是确定的, 不会存在对于一个节点, 给定一个输入, 但是进入到两个不同状态的情况

相比之下 NFA 更加简洁, 适合用来描述语言 $L(\mathcal A)$

DFA 更加易于判断 $x\in L(\mathcal A)$, 适合产生词法分析器

所以我们的思路是: 用 NFA 描述语言, 用 DFA 实现词法分析器, $i.e.$

4.2. $\small \text{RE} \Rightarrow \text{NFA}:$ Thompson 构造法

即对于给定的正则表达式 $r$, 要将其转化为对应的 NFA $N(r)$, 且满足 $L(r)=L(N(r))$

Thompson构造法的基本思想

Thompson构造法的基本思想是: 按照结构归纳

根据上面给出的正则表达式的形式化定义, 将 NFA 的规则分成基本规则和归纳规则两种, 基本规则处理不包含运算符的子表达式, 归纳规则根据一个给定表达式的直接子表达式的 NFA 构造出这个表达式的 NFA

$(1)$ 基本规则 —— $\epsilon$ 是正则表达式:

$(2)$ 基本规则 —— $\forall a\in \Sigma$, $a$ 是正则表达式:

$(3)$ 基本规则 —— 如果 $r$ 是正则表达式, 则 $(r)$ 也是正则表达式:

$(4)$ 归纳假设 —— 如果 $r$ 与 $s$ 是正则表达式, 则 $r|s$, $rs$, $r^*$ 也是正则表达式:

这里设计了$\epsilon$ 转移

一种扩展的NFA是NFA-λ（也叫做NFA-ε或有ε移动的NFA），它允许到新状态的变换不消耗任何输入符号。例如，如果它处于状态1，下一个输入符号是a，它可以移动到状态2而不消耗任何输入符号，因此就有了歧义：在消耗字母a之前系统是处于状态1还是状态2呢?由于这种歧义性，可以更加方便的谈论系统可以处在的可能状态的集合。因此在消耗字母a之前，NFA-ε可以处于集合{1,2}内的状态中的任何一个。等价的说，你可以想象这个NFA同时处于状态1和状态2:这给出了对幂集构造的非正式提示：等价于这个NFA的DFA被定义为此时处于状态q={1,2}中。不消耗输入符号的到新状态的变换叫做λ转移或ε转移。它们通常标记着希腊字母λ或ε。

我们首先假设正则表达式 $r$ 与 $s$ 的 NFA 分别为 $N(r)$ 和 $N(s)$, 那么根据假设, 它们必须满足 NFA 的递归定义.

$(4.1)$ 如果 $r$ 与 $s$ 是正则表达式, 则 $r|s$ 也是正则表达式:

$(4.2)$ 如果 $r$ 与 $s$ 是正则表达式, 则 $rs$ 也是正则表达式:

$(4.3)$ 如果 $r$ 与 $s$ 是正则表达式, 则 $r^*$ 也是正则表达式:

下面给出一个完整的例子. 对于正则表达式 $r=(a|b)^*abb$, 可以根据 Thompson构造法进行这样的构造

$N(r)$ 的性质和 Thompson 构造法的复杂度分析

1. $N(r)$ 的开始状态和结束状态均唯一
2. $N(r)$ 的开始状态没有入边, 结束状态没有出边
3. $N(r)$ 的状态数 $|S|\leq 2\times |r|$ (其中 $|r|$ 为 $r$ 中运算符和运算分量的总和)
4. 每个状态最多有两个 $\epsilon$-入边和两个 $\epsilon$-出边
5. $\forall a\in \Sigma$, 每个状态最多有一个 $a$-入边和 $a$-出边

4.3. $\small \text{NFA} \Rightarrow \text{DFA}:$ 子集构造法

子集构造法的整体思想是, 用 DFA 模拟 NFA.

下面给出一个用 $\text{DFA}$ 来模拟 $\text{NFA}$ 的例子. 对于左边的 $\text{NFA}$, 可以使用如右图的 $\text{DFA}$ 来模拟.

NFA

DFA

并且其关键步骤给出如下:

为了展示子集构造法, 我们必须先阐述几个定义

$\epsilon\text{-closure}(s)$: 也就是状态 $s$ 的 $\epsilon\text{-}$闭包, 是只通过 $\epsilon\text{-}$转移就可达的状态集合. 形式化地定义如下:

其中, 形式化地, 闭包 $f\text{-closure}(T)$ 的代数含义如下:

称为函数 $f$ 在 $T$ 上的闭包. 在此基础上, 再提出状态集的 $\epsilon\text{-}$闭包和状态集的转移函数的概念. 形式化地定义如下:

在此基础上, 我们给出子集构造法的形式化表述.:

如果 $\text{NFA}$ $N$ 和 $\text{DFA}$ $D$ 的形式化定义如下:

一些比较关键的关系如下

1. $\Sigma_D = \Sigma_N$

2. $\forall s_D\in S_D:s_D\subseteq S_N$, 也就是说:

2. 初始状态 $d_0=\epsilon\text{-closure}(n_0)$
3. 转移函数 $\forall a\in \Sigma_D:\delta_D(s_D,a)=\epsilon\text{-closure}(\text{move}(s_D, a))$
4. 接受状态集 $F_D=\{s_D\in S_D|\exists f\in F_N:f\in s_D\}$

子集构造法的复杂度分析:

$(|S_N | = n)$

$ |S_D| = \text{Θ}(2^n )$

最坏情况下, $|S_D| = Ω(2^n )$

4.4. $\small \text{NFA} \Rightarrow \text{DFA}:\text{DFA}$ 最小化

上个阶段构建出来的 DFA 也确实已经是能拿来使用了. 但是不够简介. 我们将继续完善我们的 DFA, 来使它成为一个最简洁的 DFA. 最小化 DFA 的基本思想是: 划分而非合并 (合并在理论上只是下面这个逻辑式取反而已, 但是在计算上更加复杂.)

$def:$ 如果分别从 $s$ 与 $t$ 出发, 沿着标号为 $x$ 的路径到达的两个状态中只有一 个是接受状态, 则称 $x$ 区分了状态 $s$ 与 $t$.

$def:$ 如果存在某个能区分状态 $s$ 与 $t$ 的字符串, 则称 $s$ 与 $t$ 是可区分的.

4.5. $\small \text{DFA} \Rightarrow \text{RE}$

没错我懒得打了

数据库概述

1. 数据库的基本概念

数据库（Database，简称DB）是长期储存在计算机内、 有组织的、可共享的大量数据的集合

1.1. 数据库管理系统(DataBase Management System)

1. DBMS 是DB的管理软件，是一种软件产品，将一个企业的数据以记录的形式在计算机中保存起来。

1.2. 数据库(DataBase)

1. 为同一个目的而保存起来的所有数据的集合称为数据库

2. 数据库用户

1. 最终用户(交互式用户)
2. 临时用户(用SQL语句访问DBMS的用户)
3. 缺乏经验的用户(通过菜单访问DBMS的用户)
4. 应用管理员(编写菜单程序的程序员)
5. 数据库管理员(DBA):在数据库系统中，负责数据库的设计、建立、日常管理和运行维护的人员。

3. 数据模型

3.1. Hierarchical：层次数据模型

3.2. Network：网状数据模型

3.3. Relational：关系模型

3.4. Object-Oriented：面向对象模型

计算、数据与数据管理

人工管理的特点

• 数据的管理者：用户（程序员），数据不保存
• 数据面向的对象：某一应用程序
• 数据的共享程度：无共享、冗余度极大
• 数据的独立性：不独立，完全依赖于程序
• 数据的结构化：无结构
• 数据控制能力：应用程序自己控制

文件系统管理的特点:

• 数据的管理者：文件系统，数据可长期保存
• 数据面向的对象：某一应用
• 数据的共享程度：共享性差、冗余度大
• 数据的结构化：记录内有结构，整体无结构
• 数据的独立性：独立性差
• 数据控制能力：应用程序自己控制

数据库管理的特点