在将给定源语言的一个程序翻译成特定机器代码的过程中，一个编译器可能构造出一系列中间表示。高层的中间表示接近源语言，而底层的表示接近目标语言。语法树是高层表示，它刻画了源程序的自然层次性结构，且适用于静态类型检查。低层表示适用于机器相关处理，如寄存器分配、指令选择等。
语法树的变体语法树中的各个结点代表了源程序的构造，一个结点的所有子结点反映了该结点对应构造的有意义的组成成分。为表达式构建的有向无环图 (Directed Acyclic Graph, DAG) 指出了表达式中的公共子表达式。
与语法分析树有些不同的是，DAG 的结点可能有多个父结点，也就是说这个结点是个公共子结点。比如表达式 \(a + a * (b - c) + (b - c) * d\)
SDD 既可以构造语法树，也可以构造 DAG，在构造 DAG 结点时每次构造之前都会检查是否已存在这样的结点。如果已存在结点，就返回已有结点，否则构建新结点。
编号 产生式 语义规则 1 \(E\rightarrow{}E_{1}+T\) \(E.node=\textbf{new}\ Node(’+’,E_{1}.node,T.node)\) 2 \(E\rightarrow{}E_{1}-T\) \(E.node=\textbf{new}\ Node(’-’,E_{1}.node,T.node)\) 3 \(\begin{aligned}E&\rightarrow{}T\\T&\rightarrow{}T_{1}*F\end{aligned}\) \(\begin{aligned}E.node&=T.node\\T.node&=\textbf{new}\ Node(’*’,T_{1}.node,F.node)\end{aligned}\) 4 \(T\rightarrow{}(E)\) \(T.node=E.node\) 5 \(T\rightarrow{}\textbf{id}\) \(T.node=\textbf{new}\ Leaf(\textbf{id},\textbf{id}.entry)\) 6 \(T\rightarrow{}\textbf{num}\) \(T.node=\textbf{new}\ Leaf(\textbf{num},\textbf{num}.entry)\) 通常语法树或 DAG 的结点存放在记录数组中，每个记录第一个字段是运算符代码，也是该结点的标号；叶结点可能有一个存放词法值的字段，而内部结点可能有两个指向其左右运算数的字段。
在这样的一个数组中，我们只需要给定结点对应的整数下标就可以引用该结点了。而这个下标被称为表达式的值编码 (value number)。通常为了防止结点太多所造成的巨大的搜索开销，可以用 Hash 的方法实现，加快创建结点时的搜索。
三地址码三地址码中一条指令的右侧最多有一个运算符，因此 \(x+y*z\) 这样的代码可能被翻译成 \[\begin{aligned} t_{1} &= y * z\\ t_{2} &= x + t_{1} \end{aligned}\]
最通用的语法制导翻译的方法是先通过构造一棵语法分析树，然后通过访问这棵树的各个结点来计算结点的属性值。在很多情况下，翻译可以在语法扫描分析期间完成，不需要构造出明确的语法分析树。语法制导翻译主要有两类：
L 属性翻译 (从左到右)，可以在语法分析过程中完成的翻译方案 S 属性翻译 (综合)，可以很容易与自底向上语法分析过程联系起来 语法制导定义语法制导定义 (Syntax-Directed Definition, SDD) 是一个上下文无关文法 (Context-Free Grammar, CFG) 和属性及规则的结合，属性和文法符号相关联，而规则和产生式相关联。如果 X 是一个符号而 a 是 X 的一个属性，那么我们用 X.a 表示 a 在某个标号为 X 的分析树结点上的值。
继承属性与综合属性处理非终结符的两种属性：
综合属性 (synthesized attribute) 在分析树结点 N 上的非终结符 A 的综合属性是由 N 上的产生式所关联的语义规则来定义的。这个产生式的头部一定是 A，结点 N 上的综合属性只能通过 N 的子结点或 N 本身的属性值来定义。 继承属性 (inherited attribute) 在分析树结点 N 上的非终结符 B 的继承属性是由 N 的父结点上的产生式所关联的语义规则来定义的。这个产生式的体中必然包含符号 B，结点 N 上的继承属性只能通过 N 的父结点、N 本身和 N 的兄弟结点上的属性来定义。 虽然不允许结点 N 的继承属性通过子结点上的属性来定义，但可以通过结点本身的继承属性定义综合属性。另外，终结符可以由综合属性，但不能有继承属性，它的属性值是由词法分析器提供的词法值，SDD 中没有计算终结符的属性值的语义规则。
比如有一个简单的加乘计算器。
编号 产生式 语义规则 1 \(L\rightarrow{}E\textbf{n}\) \(L.
正正规规地开始写实现一个编译器感觉压力还是蛮大的。初步选型是
基础工具 Git CMake gcc 编译器生成工具 Flex GNU Bison 其他工具 Clang Format CppLint EditConfig C++ 支持 17 简直太棒了！！！还不知道毕昇杯能不能用 CMake 去构建。
由于是多人合作项目，代码风格暂时定的是 Google，估计啥都不知道。想想到时候 review 代码就头大。
这篇主要是记录下从 info (Emacs 看 info 真方便) 中学习的 Flex 和 GNU Bison 相关用法。
TL;DR. main 函数示例 或 北大编译实践
FlexFlex 可以理解为词法分析器生成工具 Lex 的开源版本，意为 fast lexical analyzer generator。根据描述的正则表达式与 C 代码 (这些被称为 规则)，来生成对应的分析器代码 (文件名默认为 lex.yy.c)，其中定义了接口 yylex() 用来启动分析器，函数原型如下
1 int yylex(void); Flex 默认会生成标准的 C99 代码，而非 K&R 风格代码。在调用 yylex 时，它会持续从全局输入文件 yyin 中扫描 token，直到遇到 EOF 或 action 执行返回语句。如果 yylex 因 return 停止扫描，可以再次调用扫描器，从中断处继续扫描。当扫描到 EOF 时，只有 yywrap() 返回 0 才继续读取其他文件，返回非零时扫描器会终止并返回 0。如果你不实现 yywrap(),需要使用 %option noyywrap 或链接 -lfl 使用总返回 1 的默认版本。
一个自底向上的语法分析过程对应于为输入字符串构造语法分析树的过程，它从叶节点开始开始逐渐向上构造。虽然大部分编译器前端不会显示构造语法分析树，而是直接翻译，但自底向上构建有些像构建语法分析树。
移入归约语法分析是自底向上语法分析的通用框架。LR 文法就是采用移入-归约语法分析的文法。
移入-归约 归约将语法分析过程，看作输入串 w 归约 (reduction) 为文法开始符号的过程， 在归约步骤中，一个与某产生式体相匹配的特定子串被替换为该产生式头部的非终结符。
自底向上语法分析过程中，最关键的是何时进行归约，以及应用哪个产生式进行归约。
当然归约是推导步骤的反向操作，不过可以是 最右 推导。
句柄剪枝对输入进行从左向右扫描，并在扫描过程中进行自底向上语法分析，就可以反向构造出最右推导。简单地说，句柄 是和某个产生式体匹配的子串，对它的归约代表了相应最右推导中的一个反向步骤。
如果有 \(\textit{S}\xRightarrow[rm]{*}\alpha\textit{A}w\xRightarrow[rm]{}\alpha\beta{}w\)，那么紧跟 \(\alpha\) 的产生式 \(\textit{A}\rightarrow\beta\) 是 \(\alpha\beta{}w\) 的一个 句柄 (handle)。换句话说，最右句型 \(\gamma\) 的一个句柄是满足以下条件的产生式 \(\textit{A}\rightarrow\beta\) 及串 \(\beta\) 在 \(\gamma\) 中出现的位置：将这个位置上的 \(\beta\) 替换为 A 之后得到的串是 \(\gamma\) 的某个最右推导序列中出现在位于 \(\gamma\) 之前的最右句型。
句柄右边的串 w 一定只包含终结符，即产生式体 \(\beta\) 称为一个句柄 (而不是 \(\textit{A}\rightarrow\beta\))，如果文法有二义性时可能存在多个最右推导，但无二义性的文法有且仅有一个句柄。通过句柄剪枝可以得到一个反向的最右推导。
移入-规约语法分析技术该语法分析使用栈来保存符号，并用一个输入缓冲区来存放将要进行语法分析的其余符号。句柄在被识别之前，总是出现在栈顶的。
在栈中依然用 \(\$\) 标记栈底位置，在从左到右扫描输入串时，语法分析器将零个或多个输入符号移动到栈顶，直到对栈顶的一个文法符号串 \(\beta\) 进行归约为止。语法分析器将不断重复这个过程，直到检测到错误，或栈中包含了开始符号且输入缓冲区为空为止。此时宣告语法分析完成。
语法分析器主要由四个动作构成
移入 (shift) 将下一个输入符号移到栈顶 归约 (reduce) 被归约的符号串的右端必然是栈顶，语法分析器在栈中确定这个栈的左端，并决定用哪个非终结符来替换这个串 接受 (accept) 语法分析完成 报错 (error) 发现一个语法错误，调用错误恢复过程 使用栈主要是因为在语法分析过程中有个重要的性质：句柄总出现在栈顶，绝不会出现在栈中。
移入-归约语法分析中的冲突某些上下文无关文法无法使用移入-归约语法分析技术，对于这样的文法可能出现如下 configuration：虽然知道栈中的所有内容以及接下来的 k 个输入符号，
自顶向下语法可以被看作输入串构造语法分析树的问题，从语法分析树的根结点开始，深度优先创建这棵树的各个结点。
对于输入 id + id * id，可以根据最左推导序列产生语法分析树序列： \[\begin{aligned} E &\rightarrow TE^{’}\\ E^{’} &\rightarrow +\ T\ E^{’}\,|\,\varepsilon\\ T &\rightarrow FT^{’}\\ T^{’} &\rightarrow *\ F\ T^{’}\,|\,\varepsilon\\ F &\rightarrow (\ E\ )\,|\,\textbf{id}\\ \end{aligned}\]
根据左推导有如下自顶向下分析过程
递归下降的语法分析递归下降的语法分析由一组过程组成，每个非终结符有一个对应的过程，程序的执行从开始符号对应的过程开始，如果这个过程扫描了整个输入串，就停止执行并宣布语法分析完成。
通用递归下降分析技术可能需要回溯，即重复扫描输入串。在 PL 构造进行语法分析时很少回溯，因此需要回溯的语法分析器并不常见。自然语言分析的场合，回溯也不高效，因此更加倾向基于表格的语法分析方法，如 DP 或 Earley 方法。
一个简单的示例考虑文法 \[\begin{aligned} S &\rightarrow c\,A\,d\\ A &\rightarrow a\,b \ |\ a\\ \end{aligned}\] 自顶向下构造串 \(w=cad\)，初始结点指向 w 的第一个字符，即标号为 S 的结点指向 c，将会得到图 1 (a) 中的树，字符c 匹配。
Figure 1: 自顶向下语法分析器过程
将 A 用 \(\textit{A} \rightarrow ab\) 展开得到图 1 (b) 的树，第二个字符 a 匹配，此时指针推进到第三个字符 d。由于 b 与 d 不匹配，将报告失败，并回到 A 开始尝试之前未进行的且有可能匹配的其他产生式，图 1 (c) 所示。
信息 本篇是基于 tecosaur 的 Emacs 配置 大幅缩减版本，如果你对 Org Mode 感兴趣可以看他制作的 This Month in Org。
本篇标题和副标题均采用原标题的中译
Title: Doom Emacs Configuration Subtitle: The Methods, Management, and Menagerie of Madness — in meticulous detail 让我们改变对程序构建的传统态度：与其想象我们的主要任务是指导计算机做什么，不如专注于向人们解释我们想让计算机做什么。 — 高德纳
引言与其说不喜欢 IDE，倒不如说现在太菜了用不上 IDE，况且 Linux 下除了 JetBrains 家的也没其他能用的了。
不过这都是后话了，最初用的是 Dev-C++ 和 VS 2017 ，说实话 VS 好看但太大了，对我这种写 Hello World 的人来说太浪费了。其实简单说就是，VS 太大不会用，JetBrains 太贵买不起，虽然是学生可以申请免费全家桶，但 CLion 不像 Intellij IDEA 或者 PyCharm 它没免费版啊。也就尝试着 Notepad++ 了，当时并没什么政治倾向。也就当一个自带高亮的记事本， Dev-C++ 改用还得用啊。
在用编辑器时听闻了 Vim 、 Linux 等软件，爷投 *nix 了！所以 Notepad++ 也用不上了，选来选去选了个 Emacs ，多少开始离谱起来了，因为我觉得 Vim 的且模式好麻烦。不过好在这种玩意一招鲜吃遍天，你可以为其添加任意语言的支持，什么 Intellij IDEA 、 PyCharm 还要分，太麻烦了，就问你能加 Erlang 、 Elixir 、 Haskell 等支持吗 (这不巧了吗，还都能加)。况且用 shell 时默认的快捷键也是和 Emacs 一致的。
正好家里买了打印机，HP 4800 系列，耗材是真便宜，喷墨是真慢啊。不过正好记录一下 Linux 下的 HP 打印机配置过程。
另外 HP 对开源的态度真不错，估计也是因为自家是开源大厂的缘故吧。
信息 本文主要是 openSUSE 配置 HP 打印机的过程 安装驱动Linux 下有 HP 官方的打印机驱动，称为 HPLIP (HP’s Linux Imaging and Printing software)，可以查看 HPLIP 文档 或者 下载。
对于 HPLIP 可以在以下 Linux 发行版进行自动安装
SUSE Linux (13.2, 42.1, 42.2, 42.3, 15.0, 15.1, 15.2, 15.3) Fedora (22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35) Linux Mint (18, 18.1, 18.2, 18.3, 19, 19.1, 19.2, 19.
在客户端阻塞在 read 等待用户输入时，服务器关闭会导致向客户端发送 FIN，这是客户端的另一个输入。但由于客户端阻塞在 read 从而无法立即接受这个输入，直到从套接字读入为止。这就需要进程提前告知内核，使得内核在进程指定的输入准备好后，或可以输出后，立即通知进程，这个能力被称为 I/O 复用 (I/O multiplexing)。
I/O 复用有多个 syscall 可以实现，Unix 古老的函数 select 与 poll，POSIX 有一个比较新的变种为 pselect，而 Linux 与 freeBSD 独立发展出了 epoll 与 kqueue。
I/O 复用典型适用于以下场合：
当客户处理多个描述符时 客户同时处理多个套接字时，不过这种场景比较少见 如果 TCP 服务器既要监听套接字，又要处理已连接的套接字 如果一个服务器既要处理 TCP 又要处理 UDP，或同时处理多个不同协议，或多个服务 需要注意的是，并非只有网络编程需要用到 I/O 复用，I/O 复用是对文件描述符状态的监听，因此其他场景下也有其适用的空间。
I/O 模型在 Unix 系统上，一个输入操作通常包含两个不同的阶段
数据准备完成 从内核向进程复制数据 在等待数据准备到复制数据的过程，根据行为的不同，I/O 模型主要分为以下几种
blocking I/O (阻塞式 I/O)
阻塞式 I/O 模型是最常见、最简单、最好理解的 I/O 模型，目前为止所有的套接字函数都是阻塞式 I/O，另外 C 标准库所提供的 I/O 也是阻塞式 I/O，这样的模型符合初学函数时提及的运行流程。
在 recvfrom 这个示例中，只有数据报到达且复制到进程缓冲区中或错误发生才返回，而这段时间内进程是被阻塞的，不再向下运行代码。
nonblocking I/O (非阻塞式 I/O)
基本 TCP 套接字函数 socket 函数在网络编程中第一步往往调用 socket 函数，以指定通讯协议的详情。
1 2 3 // sys/socket.h int socket(int domain, int type, int protocol); // return socket fd, or -1 and set errno on error domain 指协议族，type 是套接字类型，protocol 参数应该设置为某个协议类型常量，或者为 0 表示对 domain 与 type 的系统默认值。
domain AF_INET: IPv4 协议 AF_INET6: IPv6 协议 AF_UNIX or AF_LOCAL: Unix Domain Socket AF_ROUTE: 路由套接字 AF_KEY: 密钥套接字 type SOCK_STREAM: 字节流套接字 SOCK_DGRAM: 数据报套接字 SOCK_SEQPACKET: 有序分组套接字 SOCK_RAW: 原始套接字 protocol (for IPv4 and IPv6) IPPROTO_TCP IPPROTO_UDP IPPROTO_SCTP 需要注意的是，不是所有的组合都是有效的，下表总结了有效的 socket 函数参数组合，空白意味着无效。
套接字地址数据结构套接字函数基本都需要一个指向套接字地址结构的指针作为参数，每个协议族都有自己的套接字定义，均以 sockaddr_ 开头，并有协议族的唯一后缀。
IPv4 套接字地址结构IPv4 套接字地址结构通常称之为 互联网套接字结构 (Internet socket address structure)，结构体 sockaddr_in，定义于 <netinet/in.h> 中 (POSIX)。
1 2 3 4 5 6 7 8 9 10 struct in_addr { in_addr_t s_addr; // 32 bit IPv4 地址 (网络序) }; struct sockaddr_in { uint8_t sin_len; // 结构体大小 sa_family_t sin_family; // AF_INET in_port_t sin_port; // 16 bit 传输层端口号 (网络序) struct in_addr sin_addr; char sin_zero[8]; // unused }; 需要注意几点：
长度字段 sin_len 是为了增加对 OSI 协议的支持而在 4.
本次介绍 mod 配置 Tropical Experience | The Volcano Biome (热带冒险 | 火山生态群)，版本 v2.70，这也就是常说的 3 合 1
三合一是将单机版 DLC 巨人国、船难和哈姆雷特合并在一张地图上的 mod，大型但兼容性较差，请谨慎添加 mod。
Kind of World (世界类型)：世界生成需要三合一还是单一世界
custom 表示三合一地图，这也是默认选项 shipwrecked 表示仅海难 hamlet 表示仅哈姆雷特 Sea World 表示世界都是海，仅出生点一点点陆地 for hamlet world (哈姆雷特世界设置)
Hamlet Caves (哈姆雷特洞穴): 是否启用 Hamlet 世界的 Hamlet 洞穴，需要开启世界洞穴设置 Together Caves (巨人国洞穴): 是否启用 Hamlet 世界的巨人国洞穴，需要开启世界洞穴设置 Hamlet Clouds: 是否采用 Hamlet 边界云质地 Continent Size (大陆大小) Compact 袖珍 Default 默认 Bigger 巨大 Filling the Biomes: 生物密度 Compact Pig Ruins: 是否袖珍遗迹 for shipwrecked world (船难世界设置)
Lua 是一个动态弱类型脚本语言，核心由 C 语言实现，执行效率高，可直接做 C / C++ 扩展。另外 Lua 另一个主流实现 Lua JIT 主要研究针对 Lua 的即时编译系统。
而 Lua 由于其高性能、小巧、简单、与 C 结合性好等特点，大量运用于游戏领域，而饥荒的实现以及扩展也基本使用 Lua 完成。
本章主要描述 Lua 中的词法、语法和语义，语言结构将使用通常的扩展 BNF 表示，比如 {a} 表示 0 或 多个 a， [a] 表示一个可选的 a。而关键字用黑体表示 (e.g. kword)，其他终结符使用反引号表示 (e.g. `=`)
而 Lua 学习主要以 Lua 5.1 的 官方文档 为对象。
词法介绍在 Lua 中标识符可以是任意字母、数字、下划线所组成的字符串 (不能以数字开头)，而标识符可以用作变量的名称和表字段名。但是在标识符命名时不能使用以下名称，因为它们是关键字。
关键字 and break do else elseif end false for function if in local nil not or repeat return then true until while Lua 是一个大小写敏感的语言，因此 And 与 AND 是完全不同的两个标识符。一般约定，由一个下划线开头并跟随大写字母的标识符 (e.
