Lzh's blog

编译原理复习-1

  • 2023年 04月19日

第一次小测为1-4章, 主打一个开卷, 所以没有必要记录杂七杂八的细枝末节. 主打一个脉络和算法理解.

Chapter-1: Intro

狭义地讲, 编译器的工作是将程序翻译成能被计算机执行的形式.

1.1 一个编译器的结构

  • 分析(analysis):
    • 将源程序拆分成多个要素, 在其上加上一些语法结构, 并最后生成中间表示;
  • 综合(synthesis):
    • 根据中间表示和符号表信息来构造出目标程序

分析部分常被成为前端, 综合部份称为后端

1.2 更细分的步骤

  1. 词法分析
    • 拆分词素为<token_name, attribute_value>
    • 构建符号表
  2. 语法分析
    • 创建树形表示AST
  3. 语义分析
    • 遍历树检查一致性
  4. 中间代码生成
    • 其实AST也可以视作中间代码的一种形式
    • 编译器运行过程中可能会有多种中间表示过程, 一般来说是用三地址码作为最终表示
  5. 代码生成
    • 结合中间表示形式和目标架构, 生成机器码

1.3 习题

  • 有人把程序设计语言分为编译型和解释型两类，例如 C 是编译型，Python 是解释型。这个分类是否合理？能否构建 C 语言的解释器，或者 Python 的静态编译器？谈谈你的看法？

编译和解释是语言实现，和语言设计本身应该分离。可以实现 C 的解释器，但完整的 Python 的静态编译器不太容易实现，主要是因为语言的动态特性太过灵活（如内置函数 eval），静态编译可能要把很大一部分解释器功能链接进去。

Chapter-2: A simple SDT

这一章相对于后续章节的简介和索引, 但其安排格式很奇怪, 是从语法制导翻译开始的. 虽然采用了实际的Java代码, 但由于顺序缘故, 这样讲不容易理解, 而且很丑陋, 所以重新排了顺序.

2.1 词法分析

对于词法分析比较完整的表述为:

  • 从输入中读取字符, 并将它们组成”词法单元对象”.

构成一个词法单元的输入字符序列称为词素, 比如if之于$\mathbf{if}$, int xx,yy等变量名. 此外, 一个词法单元对象还包含一些附加信息, 这些信息以属性值的形式出现, 随后会在语法制导翻译中大显身手.

一些基本的要求如下:

  • 剔除空白注释, 记录行号等
  • 预读以保证”>=”等符号的识别不出错
  • 通过生成式, 识别关键字和标识符

2.2 语法分析

语法分析是决定如何使用一个文法生成一个终结符号串的过程. 更直观的, 我们在寻找一颗语法分析树.

比较直观的想法有自顶向下方法, 这里介绍一种简单的预测分析法.

预测分析法需要非终结符的FIRST集合无交集, 从而可以根据Lookahead符号无二义的确定其生成式.

但其可能产生左递归式的无穷循环, 从而需要对文法做一些消除左递归的操作.

2.3 符号表

符号表是一种供编译器用于保存有关源程序构造的各种信息的数据结构.

在分析阶段由词法分析器, 语法分析器和语义分析器创建并使用的.

2.4 语法制导翻译

语法制导翻译是通过向一个文法的产生式附加一些规则或程序片段得到的.

这是相当关键的一步, 因为编译本身可以理解成一种语法制导翻译.

  • 语法制导定义(SDD)

也就是附加一些规则, 在文法符号和属性集合相关联时, 构建AST中各结点的属性计算方式即可.

  • 语法翻译方案

附加一些称为语义动作的程序片段, 可以达到和SDD相同的效果.

2.5 中间代码生成

这里的中间代码生成多指”三地址代码”, 这种非结构化的中间表达, 而不是语法树那样的结构化表达, 对于这种非结构化的表达, 寻找相关并优化会更加方便一些.

三地址代码的生成可以通过语法制导实现. 留到后面再说吧.

3 词法分析

词法分析器就是将输入代码流转换为词法单元的序列.

需要说明的是, 实际过程中并不是词法分析器扫一遍, 然后语法分析器再扫一遍, 没必要. 通常是协同工作, 语法分析器调用词法分析器读入, 并获得相应序列.

3.1 概念

词法分析器本身并不算困难, 不过先要分清楚几个概念:

  • 词法单元由一个词法单元名和一个可选的属性值组成.
  • 模式描述了一个词素可能具有的形式
  • 词素是源程序中的一个字符序列

针对这个属性, 比如说0/1不仅要返回一个$\mathbf{number}$的的名字, 还要返回一个number.value = 0/1才有效.

3.2 如何识别词素

在大部分语言标准中, 没有太多是允许无限长变量名的, 所以实际上DFA也就绰绰有余了, 不需要用到更复杂的CFG.

而关键字的识别也可以使用自动机实现, 其中保留字的设计则比较多样, 比如在运行最初直接加入符号表, 防止第二种出现, 也有通过匹配额外处理的. 倒也没必要学那么清除, 毕竟研究生也不想做那玩意.

3.3 如何处理错误

词法分析阶段就能处理的错误并不多见, 比如7zx这种变量名在C中是不允许的. 这种是能直接得到的.

剩下的比如误写int mian()这种, 是真不好说, 词法肯定不管你, 这就是语言标准的问题, 必须有个main()

3.4 习题

  • 将下列代码划分成词素序列:
int find(int x)
   /* haha */
   return x==Fa[x]?x:Fa[x]=find(Fa[x]);

<int>
<id, "find">
<(>
<id, "x">
<)>
<{>
<float>
<id, "x">
<return>
<id, "x">
<op, "==">
<id, "Fa">
<op, "[">
<id, "x">
<op, "]">
<op, "?">
<id, "x">
<op, ":">
<id, "Fa">
<op, "[">
<id, "x">
<op, "]">
<op, "=">
<id, "find">
<(>
<id, "Fa">
<op, "[">
<id, "x">
<op, "]">
<)>
<}>
// id后的名字为指向符号表中对应符号的指针
搜索