程序设计语言构造的语法可以使用 上下文无关文法 或者 BNF (巴库斯-瑙尔范式) 表示法来描述，文法为语言设计者和编译器编写者提供了很大便利: 文法给出了一个程序设计语言的精确易懂的语法归约 对于某些类型的文法，我们可以自动构造出高效的语法分析器，它能够确定一个源程序的语法结构。同时，语法分析器的构造过程可以揭示出语法的二义性，同时还可能发现一些容易在语言的初始设计阶段被忽略的问题 一个正确设计的文法给出了一个语言的结构，该结构有助于把源程序翻译为正确的目标代码，也有助于检测错误 一个文法支持逐步加入可以完成新任务的新语言构造，从而迭代地演化和开发程序语言。如果对语言的实现遵循语言的文法结构，那么在实现中加入这些新构造的工作就会变得更加容易 语法分析器从词法分析器获得一个词法单元组成的串，并验证这个串可以由源语言的文法生成，我们期望语法分析器能够以易于理解的方式报告语法错误，并能够从常见的错误中恢复并继续处理程序的其余部分。从概念上来说，对于良构的程序，语法分析器构造出一棵 语法分析树，并把它传递给编译器的其他部分进一步处理。我们并不需要显式地构造出语法分析树，对于源程序的检查和翻译工作可以和语法分析过程交替完成，因此语法分析器和其他部分可以用一个模块实现。 错误处理程序检测出错误后，必须报告在源程序的什么位置检测到错误，程序可能有不同层次的错误 词法错误 包括标识符、关键字或运算符拼写错误，或没有在n字符串文本上正确的添加引号 语法错误 包括分号、花括号的多余、缺失等，或 if-else 语句不匹配等 语义错误 包括运算符和运算分量之间的类型不匹配 逻辑错误 因程序员的错误推理而引起的任何错误，包括良构程序但结果不符合预期 语法分析器在检测出错误后，一般将自己恢复到某个状态，且有理由预期从那里开始输入将提供有意义的诊断信息，通常也会发现更多的错误，而不是检测到一个错误就退出程序，当然如果错误过多最好让编译器在达到某个错误数量上限后退出 panic 的恢复 语法分析器一旦发现错误就不断丢弃输入的符号，直到找到同步词法单元 (synchronizing token) 为止，同步词法单元通常是界限符 (如 ; 或 })，它们在源程序中清晰、无二义性。panic 的错误纠正方法常常会跳过大量输入，不检查跳过部分可能包含的错误，但是实现足够简单且不会让语法分析陷入死循环 短语层次的恢复 当发现错误时，语法分析器可以在余下的输入上进行局部性纠正，即将余下输入的某个前缀替换为另一个串，使语法分析器可以继续分析。这个方法难以处理实际错误发生在检测位置之前的情况 错误产生式 通过预测可能遇到的常见错误，在当前语言的文法中加入特殊的产生式，这些产生式可以生产含有错误的构造，语法分析器就能检测到一个预期的错误，生成适当的错误诊断信息 全局纠正 处理一个错误的输入串时通过最少的改动将其转换为语法正确的串 上下文无关文法一个上下文无关文法由 终结符、非终结符、一个 开始符号 和一组 产生式 组成 终结符：组成串的基本符号，与术语 词法单元名 为同义词，如 if-else 结构中的 if 和 else 非终结符：表示串的集合的语法变量，它们表示的串集合用于定义由文法生成的语言 开始符号：某个非终结符号，这个符号表示的串集合就是这个文法生成的语言 产生式：将终结符和非终结符组合为串的方法，每个产生式由以下元素组成 一个被成为产生式头或左部的非终结符，头代表串的集合 符号 \(\rightarrow\)，有时也使用 ::= 来表示 一个由零或多个终结符与非终结符组成的体或右部，体代表头所对应的串的某种构造方法 例如有一组生成式它们的头都是 E，我们可以将其组合在一起成 E \(\rightarrow\) E + T | E - T | T 这种形式 \[\begin{aligned} E &\rightarrow E + T\\ E &\rightarrow E - T \\ E &\rightarrow T \end{aligned}\]

NFA的重要状态如果一个 NFA 状态有一个标号非 \(\varepsilon\) 的离开转换，那么我们称这个状态为 重要状态 (important state)。子集构造法在计算 \(\varepsilon-closure(move(T，a))\) 的时候，它只使用了集合T中的重要状态，也就是说只有当状态s是重要的，状态集合 \(move(s,a)\) 才可能是非空的。在子集构造法的应用过程中，两个NFA状态集合可以被认为是一致的条件是 具有相同的重要状态，且 要么都包含接受状态，要么都不包含接受状态 如果 NFA 是使用 McMaughton-Yamada-Thompson 算法根据一个正则表达式生成的，那么我们可以获得更多重要状态的性质 重要状态只包括在基础规则部分为正则表达式中某个特定符号位置引入的初始状态，即每个重要状态对应于正则表达式中的某个运算分量 NFA 只有一个接受状态，但该接受状态不是重要状态。我们可以在正则表达式r的右端连接一个独特的结束标记符 #，使得r的接收状态增加一个在 # 上的转换，使其成为 (r)# 的NFA的重要状态 NFA 的重要状态直接对应于正则表达式中存放了字母表中符号的位置，使用抽象语法树来表示扩展的正则表达式是非常有用的 抽象语法树抽象语法树的叶子结点对应于运算分量，内部结点表示运算符。标号为 连接运算符 (\(\circ\)) 的内部结点被称为 cat结点，并运算符 (\(|\)) 的内部结点被称为 or结点，= 星号运算符= (\(*\)) 的内部结点被称为 star结点，我们构建正则表达式 \((a|b)^{*}abb\#\) 的抽象语法树。 抽象语法树的叶子结点可以标号为 \(\varepsilon\)，也可以用字母表中的符号作为标号，对于每个标号不为 \(\varepsilon\) 的叶子结点，我们赋予一个独立的整数，我们将这个整数称作叶子结点的 位置，同时也表示和它对应的符号的位置，当然一个符号可以有多个位置。抽象语法树中的这些位置对应构造出的 NFA 中的重要状态。 计算函数要从一个正则表达式直接构造出 DFA，我们要先构造出它的抽象语法树，然后计算如下四个函数：nullable、firstpos、lastpos 和 followpos，且这四个函数都用到了扩展正则表达式 (r)# 的抽象语法树。 nullable(n) 当且仅当此结点代表的子表达式的语言中包含空串 \(\varepsilon\) 时抽象语法树结点n为真，即：这个子表达式可以生成空串或本身就是空串，即使它也可能表示其他串 firstpos(n) 定义了以结点n为根的子树中的位置集合，这些位置对应于以n为根的子表达式的语言中某个串的 第一个符号 lastpos(n) 定义了以结点n为根的子树中的位置集合，这些位置对应于以n为根的子表达式的语言中某个串的 最后一个符号 followpos(p) 定义了一个和位置p相关的、抽象语法树中的某些位置的集合。当且仅当存在 L((r)#) 中的某个串 \(x=a_{1}a_{2}\cdots a_{n}\)，使得我们在解释为什么x属于 L((r)#) 时，可以将x中的某个 \(a_{i}\) 和抽象语法树中的位置p匹配，且将位置 \(a_{i+1}\) 和位置q 匹配，那么位置q在 \(followpos(p)\) 中。简单地说，该函数计算出位置n之后可以跟随的其他位置 在计算函数时，我们先给出较为简单的 nullable 、 firstpos 和 lastpos 的计算方式，可以使用一个对树的高度直接进行递归的过程来计算它们，计算方式如下。

个人使用的是腾讯云的轻量服务器，系统镜像选择的是 Debian 11，搭建的服务有 博客 HUGO 、私有网盘 Nextcloud 以及 Git服务器 GitLab 目前使用的是 Debian GNU/Linux 11 (bullseye) 搭建服务器，当然用的是 fish 作为 shell 1 2 3 4 5 6 7 8 9 10 11 12 bash -c "cat <<- EOF | sudo tee /etc/apt/sources.list deb https://mirrors.ustc.edu.cn/debian/ bullseye main contrib non-free deb https://mirrors.ustc.edu.cn/debian/ bullseye-updates main contrib non-free deb https://mirrors.ustc.edu.cn/debian/ bullseye-backports main contrib non-free deb https://mirrors.ustc.edu.cn/debian-security bullseye-security main contrib non-free # deb-src https://mirrors.ustc.edu.cn/debian/ bullseye main contrib non-free # deb-src https://mirrors.

词法分析是编译器的第一阶段，主要负责读取源程序的输入字符，将它们组成 词素，生成并输出一个词法单元序列，每个词法单元对应一个词素，这个词法单元序列将被语法分析器进行语法分析。除此之外，词法分析器还会过滤源程序中的注释和空白，生成错误信息与源程序的位置关联起来，有时还会进行宏扩展。 学习词法分析时，需要分清以下三个相关但有区别的术语 词法单元 由一个词法单元名和一个可选的属性值组成，词法单元名是一个表示某种词法单位的抽象符号，比如关键字，或标识符的输入字符序列 词素 源程序中的字符序列，它和某一词法单元的模式匹配，并被词法分析器识别为该词法单元的一个实例 模式 描述了一个词法单元的词素可能具有的形式。对于关键词它是组成关键字的字符序列；对于标识符和其他词法单元，模式是一个更加复杂的结构，可以和很多符号串匹配 比如 printf("Total=%d\n"，source); 中，printf 和 source 都是和词法单元 id 的模式匹配的词素，而字符串则是一个和 literal 匹配的词素，以下表格为词法单元的示例 词法单元 非正式描述 词素示例 if 关键字，字符 i/f if else 关键字，字符 e/l/s/e else comparison 比较运算符 <，<= id 普通标识符 pi，D2，source number 数字常量 3.1415926，1024 literal 字符串常量 “hello world!” 词法单元的规约 串和语言字母表 (alphabet) 是一个有限的符号集合，符号的典型示例是包括字母、数字和标点符号，常见的字母表如 ASCII 和 Unicode。 串 (string) 是某个字母表中符号的一个有穷序列，串 s 的长度，表示 s 中符号出现的次数，记作 \(|s|\)，长度为 0 的串被称为空串，记作 \(\varepsilon\)。 语言 (language) 是某个给定字母表上一个任意的可数的串的集合，此外空集 \(\varnothing\) 和 仅包含空串的集合都是语言。 词法分析中，最重要的语言上的运算是 并、连接 和 闭包。连接是将一个串附加到另一个串的后面形成新串，例如 \(x=dog, y=house\)，那么 x、y 的连接 \(xy=doghouse\) ；空串是连接运算的 单位元，即对于任意串 \(s\varepsilon = \varepsilon s = s\)。两个串的连接可以被看作乘积，那么可以定义串的指数运算： \(s^0=\varepsilon，s^i = s^{i-1}s(i > 0)\) 。Kleene 闭包 (closure)，记作 \(L^{*}\)，即将 L 连接 0 次或多次后得到的串集；正闭包 与闭包基本相同，但不包括 \(L^0\)，也就是说，除非 \(\varepsilon\) 属于 L，否则 \(\varepsilon \notin L\)。

编译器编译器是一个 程序，它可以阅读以某一 源语言 编写的程序，并把该程序翻译成一个 等价的、用 目标语言 编写的程序; 解释器是另一种语言处理器，它直接利用用户提供的输入执行源程序中指定的操作。 编译器产生的机器语言目标程序通常比一个解释器 快 得多，但是解释器的 错误诊断效果 比编译器更好，因为解释器是逐个语句地执行源程序。 基本组成编译器是由 预处理器 (preprocessor)、编译器 (compiler)、汇编器 (assembler)、链接器 (linker) 这几大主要部分组成，最后生成一个可执行程序 (executable)。 预处理器：主要负责文本替换或巨集展开 编译器：可能产生一个汇编语言的中间代码作为其输出，因为汇编语言比较容易 输出 和 调试 汇编器：将编译器产生的中间结果生成 可重新定位的 机器代码 链接器：将一个或多个由编译器或汇编器生成的目标文件外加库，链接为一个可执行文件 现代编译器中，基本可以分步骤调用编译器的各个部分，生成所需要的阶段输出，以 gcc 和 clang 为例 预处理 (-E)：输出文件经过预处理器生成的源代码，一般以 .i 作为文件扩展名 编译 (-S)：将源代码或预处理文件编译生成汇编代码，汇编代码后缀名 .s 汇编 (-c)：将源代码或之前步骤生成的中间代码汇编生成可重新定位的机器码，文件后缀名为 .o 链接：将源文件或之前步骤生成的中间代码链接生成可执行程序 结构编译器由两部分组成，分析 部分和 综合 部分 分析：将源程序分解成为多个组成元素，并在要素之上加上语法结构。分析部分被称为编译器的 前端 综合：根据中间表示和符号表中的信息来构造用户期待的目标程序。综合部分被称为编译器的 后端 现代编译器，比如 LLVM 以设计精良的 IR 作为中端输出，语言只需要实现前端和中端，最终由 LLVM 实现 IR 到二进制的转换，可以做到只优化 LLVM 就完成对其上所有语言的优化。 词法分析 (lexical analysis) 词法分析器读入组成源程序的字符流，并将它们组成成为有意义的 词素 (lexeme) 的序列。对于每个词素，词法分析器产生如下形式的 词法单元 (token) 作为输出 <token-name，attribute-value> 语法分析 (syntax analysis) 语法分析器使用由词法分析器生成的各个词法单元的第一个分量来创建树形的中间表示，该中间表示给出了词法分析产生的词法单元流的语法结构。常用表示方法为 语法树 (syntax tree)，树中的每个内部接点表示一个运算，而该结点的子结点表示该运算的分量 语义分析 (semantic analysis) 使用语法树和符号表中的信息来检查源程序是否和语言定义的语义一致。同时也会收集类型信息，并把这些信息存放在语法树或符号表中 中间代码生成 编译器一般在语法分析、语义分析结束之后，会生成一个明确的低级的或类机器语言的中间表示，该中间表示应该 易于生成、且可以被 轻松翻译 为目标机器语言 代码优化 机器无关的代码优化步骤试图改进中间代码，以便生成 更好 的目标代码 代码生成 以源程序的中间表示形式作为输入，并把它映射到目标语言，代码生成必须要 合理分配寄存器 符号表管理 记录源程序中使用的变量名称，并收集和每个名字的各种属性有关的信息，这些属性一般包含 存储分配、类型、作用域 等 构造工具除通用软件开发工具外，编译器的实现一般需要专业的工具来实现，这些专用工具使用专用的语言来 描述 和 实现 特定的组件，这些生成器会隐藏相当复杂的生成算法细节，并生成易于与其他部分集成的组件