编译原理

第一章 引论

两种主要策略

  • 编译器(Compiler)：主要目的是将便于人编写、阅读、维护的高级语言的代码翻译为计算机能解读、运行的机器码。/C++
  • 解释器(Intercepter)：是一种直接执行高级语言代码的计算机程序，而无需将代码编译成机器码。/Python

编译器比解释器做了更多的预处理

Java 两者都使用

语言处理步骤

源程序 -> 预处理器(Processs 生成修改后的源代码) - 编译器(Compiler 生成编译程序) - 汇编器(Assembler 生成可定位机器码) - 连接器(目标机器码)

编译器的七个阶段

  1. 词法分析(Lexical analyzer)：将连续的字符串变成有意义的单元(token)
  2. 语法分析(Syntax analyzer)：决定程序的结构，生成分析树 or 抽象语法树。
  3. 语义分析(Semantic Analyzer)：静态语义分析：
  4. 中间代码生成(Intermediate code generator)：三地址码，类似汇编语言的指令，每个指令最多有三个运算分量、一个运算符。
  5. 机器无关代码优化(Machine-independent code optimizer)
  6. 目标代码生成(Code generator)
  7. 机器相关代码优化(Machine-dependent Code Optimizer)

编译器的分类

  • 前端：和源代码有关
  • 后端：和目标代码有关

pass: 一般来说编译的一个阶段叫做一个pass(即从头到尾遍历一次源代码)，但有些编译器会把某些阶段合并，比如词法语法放在一个pass中。

词法分析(Lexical Analyzer)

作用：从源代码中读取字符，并形成最小逻辑单元(Token/词法单元)。

Token：词法单元，由一个词法单元名和一个可选的属性值组成。如 <id,2> <number,整数100> <add_op>

Pattern：模式，描述一个词法单元可能具有的形式，可以匹配一个或多个符号串。如“所有整型”模式。

Lexeme：词素，源程序中的一个字符序列，与某个模式匹配。/ 能够被模式匹配到的字符串。

词法单元的说明

正规表达式

正规表达式展示了字符串的匹配模式。

正规表达式操作符：

  • Choice among alternative 选择 |
  • Concatenation 连接
  • Repeat 重复 *

优先级： a* > ab > a|b

二意性(Ambiguity)

二意性：一个字符串可以被多个模式匹配。

如if可以是一个标志符也可以是一个关键字，关键字解释优先。

如>=可以是单个词法单元也可以是一串词法单元，单个词法单元优先。(最长字串原则)

单个字符向前看(single-character lookahead)：通过往前后多看一个符号，知道单词结束。

多个字符向前看(multi-character lookahead)：通过往前后多看多个符号，知道单词结束。

分割符(Delimiters)：完全没有二意性，知道它不属于单词。

词法单元识别

状态转换图：描述状态之间的转换关系。

开始状态：识别处理的开始
结束状态：双圈表示，代表识别过程的结束，加一个*表示最后那个单词不要。

有限状态自动机(Finite State Machines)

用数学的方法表达某种算法。

  • 非确定有限状态自动机(NFA Nondeterministic Finite AutoMata)

    • 一个输入状态可能会到多个状态
    • 从一个状态转换到后一个状态，不需要输入
    • NFA能接受的语言就是所有从开始到结束状态所组成的字符

  • 确定有限状态自动机(DFA Deterministic Finite AutoMata)

    • 一个输入只会到一个状态
    • 每一个状态都需要输入

从正规表达式到DFA

正规表达式 -> NFA -> DFA -> Program

从正规表达式到NFA

  • NFA of rs:

  • NFA of r|s:

  • NFA of r*:

NFA -> DFA

  • 伊普西隆-闭包(S)：状态S通过0个或多个伊普西隆-转换可以到达的状态合集。

  • 伊普西隆-闭包(T)：可由0次或多次伊普西隆-转换从T中的状态到达的所有合集的集合。

示例：

  • move[T, a]：是一个状态集，它是所有可以从T的某一个状态出发，经过一条a边（跳过之前任意条的伊普西隆边）所能到达的状态组成的集合。

示例：

  • Dtran[T, a] = 伊普西隆-闭包(move[T, a])

示例：

构造DFA

  1. 构建转换表

    1. 确定表头：表列数 = 字符数 + 1
    2. 填表：第一行第一列元素为T = 起始点闭包，然后求Dtran(T, a) Dtran(T, b)
    3. 填表：检查Dtran[T, a]和Dtran[T, b]是否在第1列出现过，把凡是没有出现过的Dtran[t, a]和Dtran[T, b]分别填在后面的空行的第1列上，分别又求出相应的Dtran[T, a]和Dtran[T, b]，直到所有Dtran[T, a]和Dtran[T, b]都在第1列出现过为止。

  2. 把上述的转换表看作是DFA D的状态转换表，并把每行每列的子集都作为状态重新编号：把第一行第一列的子集作为初态，编号为1，凡含有原终态的状态子集作为初态，其余为非初非终态。

  3. 根据转换表画出状态转换图

DFA化简

DFA化简

语法分析

介绍

语法分析器的作用：将一系列的词法单元处理为语法树。

语法分析器的位置：

三种生成方式

  • Universal 通用的
  • Top-down 自顶向下
  • Bottom-up 自底向上

错误类型

  • 词法错误：拼写错误
  • 语法错误：不符合语法结构，如：括号不匹配、分毫位置错误、缺少语法单位，等。
  • 语义错误：类型不匹配等
  • 逻辑错误：逻辑结果错

错误恢复策略

  • 恐慌模式(panic-mode)恢复：发现错误后，丢弃后面的输入符号直到找到同步词法单元（界符;{}()等）
  • 短语层次(phrase-level)恢复：在发现的错误后面进行局部性纠正，将余下输入的某个前缀替换为可能正确的另一个串
  • 错误产生式：构造可能的错误语句对应的产生式，如果某个语句符合这个产生式，则进行相应的错误处理
  • 全局纠正：通过一个最小的改动序列，得到开销最低的全局性纠正方法

CFG - 上下文无关文法

定义

CFG：描述一个编译语言的语法结构，与RE类似。

例如：
exp -> exp op exp | (exp) | number
op -> + | - | *

  • Non-terminals 非终结符号
    • 一个非终结符号描述一个程序的结构，代表一个结构还能由更小的结构组成
    • 通常写为大写字母(A, B, C等)，或者小写、斜体的名字(exp, stmt)等
  • Start symbol 开始符号
    • 一般放在语法规则的第一位
    • 是特殊的非终结符号，通常是S
  • Terminals 终结符号
    • 代表一个结构不能由更小的结构组成。
    • 通常写为小写字母、运算符、界符、数字、黑体字符串id、if等。
  • Production 产生式：产生式决定了程序合法的语法结构，每一行（exp -> exp op exp | (exp) | number）就是一个产生式。

消除左递归

立即左递归：对Aa|b替换为非左递归的产生式：

A -> bA'

A -> aA' | `空`

Derivations 推导

一个推导从一个单结构名称开始，以一串词法单元字符串结束。

  • 最右推导：每步推导总是用产生式右部符号串替换句型最右边的非终结符号；
  • 最左推导：每步推导总是用产生式右部符号串替换句型最左边的非终结符号；

CFG v.s. Regular expression

每个可以使用正规式描述的构造都可以使用上下文无关文法来描述；反之不成立。

构造正规式对应的上下文无关文法

先根据正规式构造对应的NFA，再构造相应的上下文无关文法。步骤：

  • 对于NFA的每个状态i，创建一个非终结符号Ai
  • 若状态i输入a后进入状态j，则有产生式Ai->aAj;若状态i输入空后进入状态j，则有Ai->Aj
  • 若状态i是结束状态，则有产生式Ai->空
  • 若状态i是开始状态，则Ai是开始符号

Ambiguity二义性

判断二义性

给一个字符串：

  • 存在两种最左推导
  • 存在两种最右推导
  • 存在两种解析树

消除二义性

  • Precedence优先级
  • Associativity结合方向
  • Most closely nested rule最近嵌套

优先级低的算符放在离开始符号近的产生式中（即解析树中，优先级低的算符离根节点更近）

自顶向下的语法分析

自顶向下的语法分析可以被看作是为输入串构造语法分析树的问题。（从根开始，深度优先）创建这棵语法分析树的各个结点。

  • 递归下降分析
  • LL(1)分析

递归下降分析

对于每一个非终结符号A都有一个过程：

  1. 选择A的一个产生式(比如A -> A|B，选择A还是B)
  2. 产生式中的一个终结符对应一个匹配操作(Match)
  3. 产生式的非终结符对应一个对其过程的调用

First 和 Follow 集

编译原理之First集和Follow集

  • FIRST 可以由α推导得到的串的首符号的集合，其中α是任意的文法符号串。

    1. 若X是一个终结符号，那么FIRST(X) = X;
    2. 如果X是非终结符号，且有产生式形如X → a…，则FIRST( X ) = { a };
    3. 如果X是非终结符，且有产生式形如X → A|B ，则FIRST( X ) = { FIRST(A),FIRST(B)};
    4. 如果X是非终结符，且有产生式形如X → AB
      • 当ε不属于First(A)时，则FIRST( X ) = { FIRST(A) }
      • 当ε属于First(A)时，则FIRST( X ) = { FIRST(A)，FIRST(B) }
      • 当ε属于FIRST(A)、FIRST(B) 时，将空字符加入FIRST( X )

  • FOLLOW的计算

    1. 对于文法的开始符号S，置$于FOLLOW(S)中;
    2. 若A->aBb是一个产生式，则把FIRST(b)中除了e之外的所有符号都放在FOLLOW(B)中;
    3. 如果存在一个产生式A->aB，或存在产生式A->aBb且FIRST(b)包含e，那么把FOLLOW(A)中的所有符号加入FOLLOW(B) // 如果B有可能是最后一个符号，则把FOLLOW(A)加入FOLLOW(B)中，否则把FIRST(B)-{e}加至FOLLOW(B)中。

      注意：在FOLLOW集中没有ε。

LL(1)

判断是否为LL(1)文法

构造LL(1)

自底向上的语法分析

句柄(handle)

分析树中最左边具有父子两代的子树的树叶结点自左至右排列而成。

LR(0)

  • 项：一个文法G的一个LR(0)项（简称为项）是G的一个产生式再加上一个位于它的体中某处的点·。如A->XYZ 产生了四个项：
    1
    2
    3
    4
    A->·XYZ
    A->X·YZ
    A->XY·Z
    A->XYZ·

产生式 A->ε 只生成一个项 A-> ·

  • 闭包：如果I是文法G的一个项集，那么CLOSURE(I)就是根据下面的两个规则从I构造得到的项集：
    1) 一开始，将I中的各个项加入到CLOSURE(I)中。
    2) 如果A->a·Bb在CLOSURE(I)中，B->r是一个产生式，并且B->·r不在CLOSURE(I)中，就将这个项计入其中。不断应用这个规则，直到没有新项可以加入到CLOSURE(I)中为止。

  • GOTO函数：GOTO(I, X) 其中I是一个项集而X是一个文法符号。GOTO(I, X)被定义为I中所有形如[A->a·Xb]的项所对应的项[A->aX·b]的集合的闭包。

  • 构造LR(0)分析表：
    1. 构造增广文法的LR(0)项目集族的DFA。
    2. 根据各状态中的项目填写分析表：
      • 如果从状态i到状态j有一个基于符号X的转换：
        • X属于终结符号T时，则Action[i, X] = sj;
        • X属于非终结符号N时，则GOTO[i, X] = j;
      • 如果状态i中有完整项目[A->r·]，且A不等于S‘，则对所有X属于T，Action[i, X] = r(A->r);
      • 如果状态i中有完整项目[S’->S·]，则Action[i, X] = acc;

  • LR分析过程：

SLR(1)

与LR(1)的差别：使用非终结符号的Follow集来决定是否使用规约操作。

  • 构造SLR(1)分析表：
    1. 构造增广文法的LR(0)项目集族的DFA。
    2. 根据各状态中的项目填写分析表：
      • 如果从状态i到状态j有一个基于符号X的转换：
        • X属于终结符号T时，则Action[i, X] = sj;
        • X属于非终结符号N时，则GOTO[i, X] = j;
      • 如果状态i中有完整项目[A->r·]，且A不等于S‘，则对所有a属于Follow(A)，Action[i, a] = r(A->r);
      • 如果状态i中有完整项目[S’->S·]，则Action[i, X] = acc;

判断是否是SLR(1)文法