编译原理


  • 编译:将高级语言 翻译 成汇编语言或机器语言的过程。
  • 编译器结构:
    • 词法分析,扫描识别源程序,得到词法单元 token 序列。
    • 语法分析,构造语法分析树。
    • 语义分析,收集标识符的属性信息,语义检查。
    • 中间代码生成,三地址码,语法树等结构
    • 机器无关代码优化
    • 目标代码生成
    • 机器相关代码优化

一、语言&文法&词法分析

1.0 基本概念

  • 基本符号
    • Σ:字母表,形式符号的集合
    • ε:空串
    • |w|:字符串w的长度
  • 基本运算
    • 连接,如 x, y 为串,xy 表连接
    • 幂运算,即对串的重复
    • * 闭包,同正则表达式中 *,可重复0~∞次
    • + 闭包,同正则表达式中 +,可重复1~∞次

  • 文法,$G=(V_T, V_N, P, S)$
    • $V_T$:终结符集合
    • $V_N$:非终结符集合,非终结符是用来表示语法成分的符号,有时也称为“语法变量
      • $V_T \cap V_N = \varnothing$
      • $V_T \cup V_N$:文法符号集
    • $P$:产生式集合
    • $S$:开始符号
  • 文法的通常 符号表示
    • 终结符:a, b, c
    • 非终结符:A, B, C
    • 文法符号:X, Y, Z
    • 终结符号串:u, v…z
    • 文法符号串:$\alpha$, $\beta$, $\gamma$

  • 推导
    • 用产生式的右部替换产生式的左部
    • $\alpha _0 \Rightarrow ^n \alpha _n$,表示 n 步推导
  • 归约
    • 用产生式的左部替换产生式的右部

文法 G 生成的 语言:由文法 G 的开始符号 S 推导出的所有句子构成的集合,记为 $L(G)$

$$L(G)=\{ w| S\Rightarrow ^* w,w\in V_T^* \}$$

  • 语言上的运算:
    • 并,$L \cup M=\{ w|w\in L \lor x\in M \}$
    • 连接,$LM = \{ w_1w_2|w_1\in L \land w_2 \in M\}$
    • *闭包,$L^* = L^0 \cup L^1 \cup L^2…$

  • 句型
    • 如果 $S \Rightarrow ^* \alpha$,$\alpha \in (V_N \cup V_T)^*$,则称 $\alpha$ 为 G 的一个句型。
  • 句子
    • 如果 $S \Rightarrow ^* w$,$w \in V_T^*$,则称 w 为 G 的一个句子。
    • 句子是不包含非终结符的句型

1.1 Chomsky 文法分类

  • 0 型文法,无规则文法
    • $\forall \alpha \rightarrow \beta \in P$,$\alpha$ 中至少包含一个非终结符
  • 1 型文法,上下文有关文法,Content-Sensitive Grammar
    • $\forall \alpha \rightarrow \beta \in P$,$|\alpha| \le |\beta|$
    • CSG 中不包含 ε-产生式
  • 2 型文法,上下文无关文法,Content-Free Grammar
    • $\forall \alpha \rightarrow \beta \in P$,$\alpha \in V_N$
    • 即每个产生式左部为非终结符
  • 3 型文法,正则文法,Regular Grammar
    • 右线性文法,$A\rightarrow wB$ 或 $A\rightarrow w$
    • 左线性文法,$A\rightarrow Bw$ 或 $A\rightarrow w$

1.2 CFG 的分析树

  • 根节点,标号为文法开始符号
  • 内部节点表示对一个产生式的应用
  • 叶节点的标号既可以是非终结符,也可以是终结符
    • 从左到右排列叶节点得到的符号串,称为这棵树的产出或边缘

给定一个句型,其分析树中每一棵 子树 的边缘称为该句型的一个 短语

如果子树只有父子两代节点,那么这棵子树的边缘称为该句型的一个 直接短语
$\Rightarrow$ 直接短语一定是某产生式的右部
$\Rightarrow$ 产生式的右部不一定是 给定句型 的直接短语

二义性文法:如果一个文法可以为某个句子生成多棵分析树,则称这个文法是二义性的。

对于任意一个上下文无关文法,不存在一个算法,判定它是无二义性的;
但能给出一组充分条件,满足这组充分条件的文法是无二义性的。

语法分析的前提:CFG无二义性

1.3 正则表达式

描述正则语言的形式工具:

  • 3型(正则)文法
  • 有限自动机
  • 正则表达式

正则表达式是用来描述正则语言的更紧凑的表示方法。

1.4 有限自动机

一个 非确定有限状态自动机 NFA (nondeterministic finite automata)是一个五元组:
$$ M = (S, \Sigma, \delta, s_0 , F)$$

与 DFA 唯一不同之处:$\delta:S \times \Sigma \rightarrow 2^S$,即状态的转移结果是一个集合


一个 确定的有限状态自动机 DFA (deterministic finite automata) 是一个五元组:
$$ M = (S, \Sigma, \delta, s_0 , F)$$

$S$:有限状态集
$\Sigma$:有限输入符号集
$\delta$:转移函数
$s_0$:开始状态,$s_0 \in S$
$F$:接受状态(或终止状态)集合

  • 表示方式:
    • 转移图
      • 非空有限状态,用圆圈表示
      • 终态,双圆圈表示
      • 开始状态,start箭头标出
      • 转移函数,用带箭头圆弧表示
      • 非空的有限输入符号,标在圆弧旁边
    • 转移表
  • 定理:L是某个 DFA 的语言,当且仅当L也是某个 NFA 的语言。

一些图例:


1.5 练习

构造产生如下语言的上下文无关语法:
(1)$\{uawb | u,w \in \{a, b\}^*\ ∧ |u| = |w| \}$
     $S → Ab$
     $A → BAB | a$
     $B → a | b$

二、自顶向下语法分析

2.0 概述

自顶向下的分析,可以看成是从文法开始符号 S 推导出词串 w 的过程。

最左推导,总是选择每个句型的最左非终结符进行替换

最右推导,总是选择每个句型的最右非终结符进行替换

在自底向上的分析中,总是采用最左归约的方式,因此把最左归约称为 规范归约,而最右推导相应地称为 规范推导


  • 递归下降分析(自顶向下语法分析的通用形式)
    • 由一组过程组成,每个过程对应一个非终结符
    • 同一非终结符的多个候选式存在共同前缀,将导致回溯现象,由此引出以下的分析
  • 预测分析
    • 是递归下降分析的一个特例,通过输入中向前看固定个数(通常为1)符号来选择正确的 A-产生式
    • 可以对某些文法构造出向前看 k 个输入符号的预测分析器,该类文法有时也称为 LL(k)文法类
    • 预测分析不需要回溯,是一种确定的自顶向下分析方法
void A(){
  选择一个 A 产生式
  for(i to k){
    if (xi 是一个非终结符)
      调用过程 xi
    else if (xi 为当前的输入符号 a)
      读入下一个输入符号
    else 
      发生错误
  }
}

  • 含有 $A\rightarrow A\alpha$ 形式的文法称为是 直接左递归
  • 如果一个文法中有一个非终结符 A 使得对某个串 $\alpha$ 存在一个推导 $A \Rightarrow ^+ A\alpha$,那么这个文法就是 左递归
    • 左递归文法会使递归下降分析器陷入无限循环
  • 经过两步或两步以上推导产生的左递归称为是间接左递归的

消除左递归:引进一些非终结符和 $\epsilon$_产生式

2.1 LL(1)分析

$LL(1)$分析(自顶向下预测分析)

  • First 集合
    • 一个句型 $\alpha$ 若可以推导出另一个以终结符 $a$ 开头的句型,那么 $a$ 属于 $First(\alpha$);若 $\alpha$ 可以推导出 ε,那么 ε 属于 $First(\alpha)$
    • 即可推导的前缀(所有串首终结符)的集合
  • Follow 集合
    • 可能在某个句型中紧跟在 A 后面的终结符 a 的集合。若G 中存在一个以 $X$ 结尾的句型,那么 # 属于 $Follow(X)$
    • 算法:
      • 初始时,置 $Follow(S)=\{\#\}$;对其它 $X\in V_N$,置 $Follow(X)=\varnothing$
      • 依次考虑每一个右端含有非终结符的产生式
        • 在末情况下,follow1 = follow1 ∪ follow2
        • 不在末,follow1 = follow1 ∪ (first2 - {ε})
  • Select 集合
    • 产生式 $A\rightarrow \beta$ 的可选集是指可以选用该产生式进行推导时对应的输入符号的集合,记为 $SELECT(A \rightarrow \beta)$
    • 即可选用该产生式进行推导时,对应的终结符集合
  1. $$SELECT(A \rightarrow a\beta) = \{ a\}$$

  2. $$SELECT(A \rightarrow \epsilon) = FOLLOW(A)$$

  3. $$如果 \epsilon \notin FIRST(\alpha), 那么SELECT(A\rightarrow \alpha)=FIRST(\alpha)$$

  4. $$如果 \epsilon \in FIRST(\alpha), 那么SELECT(A\rightarrow \alpha)=(FIRST(\alpha)-\{\epsilon \})\cup FOLLOW(A)$$



注意:三个集合的计算

注意:证明 $LL(1)$ 文法,即选择候选式时不会冲突

由各产生式的 select 集引出预测分析表,

三、自底向上语法分析

3.0 概述

自底向上的分析,可以看成是将输入串 w 归约为文法开始符号 S 的过程。

  • 采用最左归约
  • 移入-归约分析
    • 根据剩余输入,不可归约时移入栈顶,可归约时将栈的元素替换,或接收、报错
  • 栈内符号串 + 剩余输入 = “规范句型”

句柄:右句型的一个直接短语

移进−归约冲突是指到达一个不能确定下一步应该移进还是应该归约的状态。

归约−归约冲突是指到达一个可以对多个短语进行归约的状态。

SLR(1)分析,向前查看一个符号可解决冲突

二义文法在LR分析中的应用

  • LR 分析中的出错处理
    • LR 分析表的空表项对应一个出错位置
    • 可根据相应的堆栈终结和输入符号设置报错信息,进行简单的恢复工作

3.1 LR分析

  • LR 分析表
    • $s_n$, 将符号a、状态n压入栈
    • $r_n$, 用第 n 个产生式进行归约

四、语法制导得语义计算基础

4.0 概述

语法制导翻译:语法分析 -> 语义分析 -> 中间代码生成

语义翻译:语义分析 -> 中间代码生成

语法制导翻译使用上下文无关文法 CFG 来引导对语言的单一,是一种面向文法的翻译技术

  • 语义分析要解决的问题
    • 如何表示语义信息
      • 文法符号(语法信息)->(设置) 语义属性
    • 如何计算语义信息(语义属性)
      • 产生式(语法规则)->(关联) 语义规则
  • 语义属性
    • 综合属性
      • 非终结符,由子节点或本身的属性计算
      • 终结符,词法值
    • 继承属性
      • 非终结符,由子节点或本身的属性计算
      • 终结符,没有继承属性

4.1 属性文法

4.2 语义计算

五、代码优化和目标代码生成

5.0 概述

  • 输入:某一种中间代码以及符号表等信息
  • 输出:特定目标机或虚拟机的目标代码

如不特别说明,本章的中间代码形式均为三地址码(简称TAC)

  • 基本块
    • 程序中一个顺序执行的语句序列
  • 流图
    • CFG _Control-Flow Graph_,是个有向图
  • 循环
    • 支配节点集,如果从流图的首结点出发,到达 n 的的任意通路都要经过 m, 则称 m 支配 n, 或 m 是 n 的支配结点。
  • 数据流分析基础
  • 局部优化技术
  • 目标代码生成技术
  • 代码优化技术

5.1 目标代码生成技术

这是最后一次课内容

  • 指令选择
  • 寄存器分配
  • 指令调度
  • 代码优化

作业:第六题

六、实验课

1.词法分析器自动构造工具JFLEX,S1词法分析器自动构造
2.词法分析器自动构造工具YACC,S1词法分析器自动构造
3.基础实验项目:表达式计算器Jflex/Yacc实现
4.J1_指令
5.实验项目PA1:Step1 S1编译器Jflex/Yacc实现
6.实验项目PA2:Step2 S2编译器实现
7.实验项目PA3:Step3 S3编译器实现;Step4 S4编译器实现

说明:汇编语言 J1,编译器 S1


jflex 是一个 词法分析 的生成器,生成 Java 写的词法分析器,文件扩展名为 .l

yacc 是 Unix 系统上的一个 $LALR(1)$ 语法分析 生成器。yet another compiler compiler,文件扩展名为 .y

yacc -J S1ly.y  
jflex S1l.l
javac Parser.java
javac Yylex.java
java Parser S1
a S1.a

other

参考资料:


分数:

  • 平时(40%)
    • 书面作业(10%)
    • 上机作业+出勤(15%)
    • 实验大作业(15%)
  • 期末(60%)

文章作者: ╯晓~
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 ╯晓~ !
评论
  目录