文章
26
标签
22
分类
17
Home
Archives
Tags
Categories
Link
About
List
目录
  1. 1. 绪论
    1. 1.1. 课件PPT
    2. 1.2. 什么是编译
    3. 1.3. 编译系统的结构
    4. 1.4. 词法分析概述
    5. 1.5. 语法分析概述
    6. 1.6. 语义分析概述
    7. 1.7. 中间代码生成及编译器后端概述
  2. 2. 语言及其文法
    1. 2.1. 基本概念
      1. 2.1.1. 字母表
      2. 2.1.2. 字母表上的运算
      3. 2.1.3. 符号串
      4. 2.1.4. 串上的运算
    2. 2.2. 文法的定义
      1. 2.2.1. 文法的形式化定义
      2. 2.2.2. 产生式的简写
      3. 2.2.3. 符号的约定
    3. 2.3. 语言的定义
      1. 2.3.1. 推导与规约
      2. 2.3.2. 句型和句子
      3. 2.3.3. 语言的形式化定义
      4. 2.3.4. 语言上的运算
    4. 2.4. 文法的分类
      1. 2.4.1. 0型文法，无限制文法，短语结构文法
      2. 2.4.2. 1型文法，上下文有关文法(CSG)
      3. 2.4.3. 2型文法，上下文无关文法(CFG)
      4. 2.4.4. 3型文法，正规文法，正则文法(RG)
      5. 2.4.5. 四种文法之间的关系
    5. 2.5. 上下文无关文法的分析树
      1. 2.5.1. CFG分析树定义
      2. 2.5.2. 分析树是推导的图形化表示
      3. 2.5.3. 句型的短语
      4. 2.5.4. 二义性文法
      5. 2.5.5. 二义性文法的判定
  3. 3. 词法分析
    1. 3.1. 正则表达式（RE）
      1. 3.1.1. 正则表达式的定义
      2. 3.1.2. 正则表达式的代数定律
    2. 3.2. 正则定义
      1. 3.2.1. 例1：C语言的标识符
      2. 3.2.2. 例2：无符号数
    3. 3.3. 有穷自动机（FA）
      1. 3.3.1. FA 的典型例子
      2. 3.3.2. FA 模型
      3. 3.3.3. 状态图
      4. 3.3.4. FA定义（接受）的语言
      5. 3.3.5. 最长子串匹配原则
    4. 3.4. 有穷自动机的分类
      1. 3.4.1. 确定的有穷自动机 (DFA)
      2. 3.4.2. 非确定的FA (NFA)
      3. 3.4.3. DFA和NFA的等价性(重点考点)
    5. 3.5. 正则表达式和有穷自动机之间的转换
      1. 3.5.1. 从RE到NFA
    6. 3.6. 从NFA到DFA的转换
      1. 3.6.1. 举例
      2. 3.6.2. 子集构造法
      3. 3.6.3. 计算 ε-closure 空闭包函数
    7. 3.7. 识别单词的DFA
      1. 3.7.1. 识别标识符的 DFA
      2. 3.7.2. 识别无符号数的 DFA
      3. 3.7.3. 识别各进制无符号整数的 DFA
      4. 3.7.4. 识别注释的 DFA
      5. 3.7.5. 识别 token 的 DFA
    8. 3.8. 词法分析阶段的错误处理
      1. 3.8.1. 词法分析阶段可检测错误的类型
      2. 3.8.2. 错误处理程序
      3. 3.8.3. 错误恢复策略
  4. 4. 语法分析
    1. 4.1. 自顶向下分析概述
      1. 4.1.1. 最左推导和最右推导
      2. 4.1.2. 自顶向下的语法分析采用最左推导方式
      3. 4.1.3. 自顶向下语法分析的通用形式
      4. 4.1.4. 预测分析(Predictive Parsing)
    2. 4.2. 文法转化
    3. 4.3. LL(1)文法
  5. 5. 语法制导翻译
    1. 5.1. 语法制导翻译概述
    2. 5.2. 语法制导定义(SDD)
      1. 5.2.1. 综合属性和继承属性
      2. 5.2.2. SDD的求值顺序
      3. 5.2.3. S-属性定义与L-属性定义
    3. 5.3. 语法制导翻译方案
      1. 5.3.1. S-SDD转换为SDT
      2. 5.3.2. L-SDD转换为SDT
      3. 5.3.3. 在非递归的预测分析过程中进行语义翻译
      4. 5.3.4. 在递归的预测分析过程中进行语义翻译
      5. 5.3.5. 在LR分析过程中进行语义翻译
  6. 6. 中间代码的生成
    1. 6.1. 课件PPT
      1. 6.1.1. 中间语言
      2. 6.1.2. 说明语句的翻译
      3. 6.1.3. 赋值语句的翻译
      4. 6.1.4. 布尔表达式的翻译
      5. 6.1.5. 控制语句的翻译
      6. 6.1.6. 过程调用的处理
    2. 6.2. 控制流语句及STD
  7. 7. 课堂笔记
    1. 7.1. 11.07
    2. 7.2. 11.28
    3. 7.3. 12.05
      1. 7.3.1. 控制语句的翻译
    4. 7.4. 12.12
    5. 7.5. 12.19
      1. 7.5.1. 局部优化
      2. 7.5.2. 目标代码生成——最后一章
        1. 7.5.2.1. 代码生成算法
  8. 8. 作业习题
  9. 9. 考试
编译原理
|课程
字数总计: 12k|阅读时长: 37 分钟|阅读量:

复习要求：翻看笔记+高珍老师PPT，然后挑重点理解，要记得刷题

  • 绪论
  • 高级语言及其文法
  • 词法分析
  • 语法分析
  • 语法制导翻译
  • 中间代码生成
  • 优化

视频：

  • 绪论 1-6
  • 语言及其文法 2.5完整看完
  • 你
  • chapter 9

考点用重点考点进行标识

需要补充的地方[?]

参考网址：编译原理MOOC笔记

绪论

课件PPT

image-20191212212425319

什么是编译

计算机程序语言可以自顶向下可以分为高级语言、汇编语言和机器语言三种，其中开发程序员最长接触的为高级语言，如JAVA，高级语言经过编译就会生成汇编语言或机器语言，具体关系如下图：

image-20191127165753230

编译的过程就是将高级语言翻译成汇编语言或机器语言的过程 ，即将源语言转化为目标语言的过程。

编译器在语言处理系统中的位置如下图所示：

image-20191127165935095

  • 可重定位(Relocatable)： 在内存中存放的起始位置L不是固定的

  • 加载器：修改可重定位地址；将修改后的指令和数据放到内存中适当的位置

    起始位置+相对地址=绝对地址

  • 链接器的作用：

    1. 将多个可重定位的机器代码文件（包括库文件）
    2. 连接到一起解决外部内存地址问题

编译系统的结构

在有了高级语言程序之后（如一段C语言代码），编译器应该怎么翻译成汇编语言程序或机器语言程序呢？

我们先来看一下人工英汉怎么进行翻译的，编译器所做的工作有类似之处。

image-20191127170344850

首先我们分析源语言，即英文，先拆分名词、动词等，然后组成短语，最终才能组合成句。即一段语言的分析理解包括了3个基本的小部分,最终才能连接成为一个完整的句子

  1. 词法分析（Lexical Analysis）
  2. 语法分析（Syntax Analysis）
  3. 语义分析（Semantic Analysis）

那么一个完整的编译器结构如下图所示：

image-20191127170550711

词法分析概述

词法分析顾名思义就是通过扫描源程序，识别出每一个单词，确定单词类型，然后转化为统一的机内表示——词法单元（token）形式。

token：< 种别码，属性值>

例如if、else对应唯一的表示形式。具体的表示形式如下表所示：

image-20191127170722792

例如有一句代码为：

while(value!=100){num++;}

则经过词法分析后如下所示，其中每句后的<-,->表示每个单词的含义。

while      < WHILE ,    -  >  // 关键词，一词一码
(          <SLP    ,    -  >  // 界限符，一词一码
value      <IDN    ,  value>  // 标识符，多词一码，< 种别码，属性值value>
!=         <NE     ,    -  >  // 运算符，一词一码
100        <CONST,100> 				// 常 量，一型一码
)          <SRP,->            // 界限符，一词一码
{          <LP,->             // 界限符，一词一码
num        <IDN,num>          // 标识符，多词一码，< 种别码，属性值value>
++         <INC,->            // 运算符，一词一码
;          <SEMI,->           // 界限符，一词一码
}          <RP,->             // 界限符，一词一码

语法分析概述

语法分析器(parser)从词法分析器输出的token序列中识别出各类短语，并构造语法分析树(parsetree)。简而言之就是将词法分析后识别出来的单词构成短语，将短语整合成一个完整的句子。

语法分析树描述了句子的语法结构。如下是赋值语句的语法分析树：

   position      =      initial      +    rate      *    60     ;  
<id，position>  <=>   <id,initial>  <+> <id, rate> <*> <num,60> <;>

image-20191127180738395

例如我们需要得到变量声明的分析树，变量声明可以是int a；也可以是int a,b,c；抽象成文法（变量声明的规则）和分析树为：

image-20191127181449598

语义分析概述

语义分析的主要任务是收集标识符的属性信息，其中包括种属（简单变量、复合变量···）、类型（整型、实型···）、存储位置、长度等；除此之外语义分析还要进行语义检查，其中包括变量是否是没有声明就使用了。

中间代码生成及编译器后端概述

常见的中间表示形式为：

  • 三地址码(Three-address Code)：三地址码由类似于汇编语言的指令序列组成， 每个指令最多有三个操作数(operand)。

  • 语法结构树/语法树(Syntax Trees)

常见的为三地址形式，其中表示方法为四元式(Quadruples)：(op, y, z, x)。

image-20191127182026339

中间代码生成的案例为：

[!!!重点题]先画出语法分析树，然后再进行分析

image-20191127182553003

语言及其文法

基本概念

正如英语是由句子组成的集合，而句子又是由单词和标点符号组成的序列那样。程序设计语言 C 语言，是由 C 程序所组成的集合，而程序是由类似 if , begin, end 的符号，字母和数字这样一些基本符号所组成。

从字面上看，每个程序都是一个“基本符号”串，设有一基本符号串，那么 C 语言可看成是在这个基本符号集上定义的，按一定规则构成的一切基本符号串组成的集合。

字母表

字母表$$\sum$$是一个有穷的符号集合，其中符号包括字母、数字和标点符号等

如:

  • 二进制字母表：{ 0,1 } ；

  • ASCII字符集 ；

  • Unicode字符。

字母表上的运算

字母表 $\sum_1$ 和 $\sum_2$ 的乘积( product)

image-20191127203325412

字母表 $\sum$ 的n次幂( power)：长度为n的符号串构成的集合

image-20191127203359267

字母表 $\sum$ 的正闭包( positive closure)：长度为正数的符号串构成的集合

image-20191127203508021

字母表 $\sum$ 的克林闭包(Kleene closure)：任意符号串(跟正闭包相比长度可以为零）构成的集合

image-20191127203705801

符号串

由字母表中的符号组成的任何有穷序列称为符号串。

串 s 的长度，通常记作 |s| ，是指 s 中符号的个数。例：|aab|=3。

空串是长度为 0 的串，用 ε 表示，|ε|=0。

串上的运算

串的连接

如果 x 和 y 是串，那么 x 和 y 的连接，是把 y 附加到 x 后面而形成的串，记作 xy。

例如，如果 x=dog 且 y=house，那么 xy=doghouse。

空串是连接运算的单位元，即，对于任何串 s 都有， εs=sε=s。

串的幂运算：将 n 个 串连接起来。

image-20191127204538740

文法的定义

自然语言中句子的构成规则为：句子由名词短语构和动词短语成，名词短语由形容词和名词短语构成···，直到最终特定的名词、动词、形容词等。

分析一个自然语言的例子，得出句子的构成规则。

image-20191127201802385

文法的形式化定义

$$
G = (V_T , V_N , P , S )
$$

  • G：表示文法，文法由一个四元组定义

  • 终结符集合和非终结符集合都是字母表

  • 终结符集合与非终结符集合是不相交的 -> $V_T∩V_N=Φ$

  • 终结符集合与非终结符集合的并集是文法符号集 -> $V_T∪V_N$：文法符号集

  • $V_T$：

    image-20191127210706311

  • $V_N$：因为从它们可以推出其他的语法成分，所以被称为非终结符

    image-20191127210747647

  • P：产生式集合，注意左部和右部的取值，左部是正闭包，右部是克林闭包

    例： P = <句子> → <名词短语><动词短语>, <名词短语> → <形容词><名词短语>

    image-20191127211430931

  • S：开始符号

    $S∈V_N$，开始符号(start symbol)表示的是该文法中最大的语法成分。例：S = <句子>

    image-20191127212009896

    例：image-20191127212046791

产生式的简写

image-20191127212509659

符号的约定

  • 终结符

    image-20191127213016136

  • 非终结符

image-20191127213110142

  • 其他

    image-20191127213523082

语言的定义

推导与规约

假设自然语言的文法可以表示为

image-20191127213748634

单词串：little boy eats apple

有了文法（语言规则），如何判定一个单词串是否是满足文法的句子？

答案是：推导和规约。

$ a_0$ 经过 n 步推导出$ a_n$ ，可简记为：$ a_0 -> a_n$

image-20191127215130972

image-20191127215144948

例：

由上而下为推导，即具体化的过程——-从生成语言的角度

由下而上为规约，即抽象化的过程——从识别语言的角度

image-20191127214236911

句型和句子

句型：

image-20191127214426061

句子：句子是不包含非终结符的句型

image-20191127214450796

例：

image-20191127214531118

语言的形式化定义

由文法 G 的开始符号 S 推导出的所有句子构成的集合称为文法G生成的语言，记作 L(G)，即：`

image-20191127215520196

例1：

$E->E+E | E * E | (E) | id$ 生成的语言中包含多少个句子

答案是无数个，文法解决了无穷语言的有穷表示问题

例2：

我们现在拥有的文法 G 如下所示，其生成的语言标识符，即以字母开头的字符串。因为S定义为一个字母或以字母开头的字母数字串，即用于表示标识符。

image-20191127215638460

语言上的运算

image-20191127220637268

文法的分类

0型文法，无限制文法，短语结构文法

  • α中至少包含1个非终结符

image-20191127221027086

1型文法，上下文有关文法(CSG)

  • 产生式左部符号的个数不能多于右部

  • CSG不包含 $\varepsilon$ 产生式，即产生式右部是空串的产生式，因为左部至少包含一个非终结符，左部长度至少为1，如果右部是 $\varepsilon$ ，右部长度为1，与CGS定义不符合。

image-20191127221328301

2型文法，上下文无关文法(CFG)

  • 左边是一个非终结符，将其替换不需要考虑其上下文
  • 所举的例子即2型文法

image-20191127221344869

3型文法，正规文法，正则文法(RG)

  • 3型文法分为2种文法
  • 产生式右部最多只有一个非终结符，且只能在一侧
  • 例子中的两个文法都是指标识符，即一个字母或以字母开头的字母数字串
  • 程序语言中的多数单词都能用正则文法表示

image-20191127222052426

四种文法之间的关系

image-20191127222635614

上下文无关文法的分析树

程序语言中的多数单词都能用正则文法表示，但正则文法生成能力有限，句子构造则需要用上下文无关文法进行描述。

CFG分析树定义

例：图中跟节点表示的是对第三个式子的应用

image-20191127222833264

分析树是推导的图形化表示

推导过程中产生许多句型,最终推导出分析树的边缘

image-20191127223759244

句型的短语

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

如果子树只有父子两代节点，那么这课子树的边缘称为该句型的一个直接短语。

直接短语一定是产生式的右部，但产生式的右部不一定是给定句型的直接短语，但可能是其他句型的直接短语

image-20191127224229562

例：人民、生活、水平是该句子的直接短语，而高人、民生、活水虽然也是第5个产生式的右部，但是在这棵分析树中，它们不是直接短语。

image-20191127225119891

二义性文法

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

下面这个例子产生二义的原因是else可以跟第一个if条件语句和第二个if条件语句相配。

消歧规则：每个else和最近的尚未匹配的if进行匹配，所以只有第一个分析树

image-20191127225609332

二义性文法的判定

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

  • 满足，肯定无二义性
  • 不满足，也未必就是有二义性的

词法分析

词法分析这一章从正则表达式到有穷自动机，讲述了如何利用确定性的有穷自动机来进行单词的识别。其中正则表达式和有穷自动机之间也有相应的转化关系。

本文内容：介绍正则定义，正则表达式，有穷自动机（确定的有穷自动机 DFA，不确定的有穷自动机 NFA），NFA 转换为等价的 DFA，DFA 的化简，识别单词的 DFA ，典型例题及详细解答。

在前面我们说过，程序设计语言中的大多数单词都可以用正则文法来描述，在这一章中我们将介绍描述正则语言的更紧凑的方法——正则表达式。

正则表达式（RE）

语言是一个集合，因此我们可以在语言上进行多种集合运算。比如说并运算，乘积运算（即连接运算），闭包运算等等。

正则表达式示例

接下来我们看一个语言的例子，如下图所示：

image-20191127234530543

这个语言的字首是字母 a，接下来连接一个任意长度的 a,b 串，再接下来连接一个空串。连接一个空串就代表句子已经结束了。除此之外，我们还可以连接一个点号（.）或者下划线（_）或者一个长度大于等于1 的 a,b串。

这个式子写起来比较复杂，因此我们要介绍正则表达式。

正则表达式（Regular Expression，RE）是一种用来描述正则语言的更紧凑的表达方式。

例如上面的语言可以用正则表达式来表示，如上图所示。

这个正则表达式表示，句子的第一个符号是字母 a ，接下来连接一个任意长度的 a,b串，再接下来连接一个空串。连接一个空串就代表句子已经结束了。除此之外，我们还可以连接一个点号（.）或者下划线（_）或者一个长度大于等于1 的 a,b 串。

从这个例子中，我们可以看出，正则表达式可以用较小的正则表达式根据特定规则来递归构建。

每个正则表达式 r 定义（表示）一个语言，记为 $L(r)$。这个语言也是根据 r 的子表达式所表示的语言递归定义的。

正则表达式的定义

  • 空串是一个正则表达式，那么它所表达的语言也只包括空串。
  • 字母表上的任何一个符号都是一个正则表达式，那么它所表示的语言只包含它本身。
  • 假设 r 和 s 都是正则表达式，它们表示的语言分别是 $L(r)$ 和 $L(s)$ ，则:
    • $r|s$ （r 或 s）也是一个正则表达式，它表示的语言是 $L(r|s) = L(r) ∪ L(s)$
    • rs（r 和 s 的连接）也是一个正则表达式，它表示的语言是 $L(rs) = L(r)L(s)$
    • $r^$（r 的克林闭包）也是一个正则表达式，它表示的语言是也 $L(r^) = (L(r))^*$
    • $(r)$ 是一个正则表达式，它表示的语言就是 $L(r)$，即 $L((r))=L(r)$

image-20191127234942937

例：

假设符号表中有 a,b。则 a 是一个正则表达式，b 也是一个正则表达式。可以推导出以下的正则表达式：

image-20191127235851699

例：

描述 C 语言中无符号整数的正则表达式

  • 十进制整数的正则表达式：第一个符号是19中的一个数字，接下来连接若干个 09 的数字，或者连接符号 0。
  • 八进制整数的正则表达式：第一个符号是数字0，第二个符号是17中的一个数字，接下来连接若干个 07 中的数字。
  • 十六进制整数的正则表达式：第一个符号是0，第二个符号是 x，第三个符号是 1～f 中的符号，接下来连接若干个 0～f 中的符号。

image-20191128000002054

正则表达式的代数定律

正则语言：可以用正则表达式定义的语言叫做正则语言或正则集合。

正则表达式也遵循一些代数定律，如下图所示：

image-20191128000355664

正则文法与正则表达式等价：

  • 对于任何一个正则文法 G，存在定义同一语言的正则表达式 r。

  • 对任何正则表达式 r，存在生成同一语言的正则文法 G。

  • 总之，有 G 就有 r ，有 r 就有 G 。

正则定义

为了方便起见，我们可以给某些正则表达式命名，像使用字母表中的符号一样，使用这些名字来构造正则表达式。（这就是正则定义提出的定义和基本思想）

正则定义就是给正则表达式命名，右侧是字母表与已定义的正则定义的并集

image-20191128000623988

例1：C语言的标识符

C语言中标识符的正则定义：

  • 第一个正则表达式，表示0~9中的某个数字，我们给它取一个名字，digit

  • 第二个正则表示式，表示一个字母（小写字母或大写字母）和一个下划线。我们给它取一个名字，letter_

  • 接下来我们用起好的这两个名字，来构造第三个正则表达式。

  • 第三个正则表示式，首先是一个 letter_，接下来连接一个 letter _ 或 digit 构成的字符串。这个表达式表示的是字母打头的字符数字串。（正是标识符的定义）

image-20191128001129801

例2：无符号数

（整型或浮点数）无符号数的正则定义：

  • digit，还是表示一个数字

  • digits，digit 连接上一个 digit 的克林闭包，表示的是一个长度>=1 的数字串。

  • optionalFraction，点号（.）后面连接一个 digits 或 这个表达式是一个空串。（这个符号表示的是一个小数部分，或一个空串）代表可选的小数部分。

  • optionalExponent，大写字母 E 后面连接一个 + （正号）或 一个 -（负号）或直接连接一个长度大于等于1 的数字串（digits），或者这个表达式为空串。可选的指数部分。

  • number，长度大于等于1 的数字串，连接一个可选的小数部分，连接一个可选的指数部分。

    • 当可选的小数部分为空串时，这个表达式为一个整数的若干次幂，如 2E-3
      若可选的指数部分为空串时，这个正则表达式为小数。比如说 2.15

    • 若可选的小数部分和可选的指数部分都为空串时，这个正则表达式为整数。比如说 2

    • 若可选的小数部分和可选的指数部分都不为空串时，这个正则表达式为指数形式的浮点数。比如说 2.15E+3, 2.15E-3。
      当指数为正号时，指数是可以省略的，如 2.15E3

image-20191128001235949

有穷自动机（FA）

有穷自动机（Finite Automata，FA）由两位神经物理学家Meculoch 和 Pitts 于 1948年提出，是对一类处理系统建立的数学模型。

重要的理论基础

这类系统具有一系列离散的输入输出信息和有穷数目的内部状态。

系统只需要根据当前所处的状态和当前面临的输入信息，就可以决定系统的后继行为。每当系统处理了当前的输入后，系统的内部状态也将发生改变。

FA 的典型例子

电梯控制装置

  • 输入：顾客的乘梯需求（所要到达的层号）
  • 状态：电梯所处的层数+运动方向
  • 电梯控制装置并不需要记住先前全部的服务要求，只需要知道电梯当前所处的状态以及还没有满足的所有服务请求。

FA 模型

FA模型由以下三部分组成：

  • 输入带：用来存放输入符号串

  • 读头：从左向右逐个读取输入符号，不能修改（只读），不能往返移动

  • 有穷控制器：具有有穷个状态数，根据当前的状态 + 当前输入符号控制转入下一状态。

image-20191128002151798

状态图

有穷自动机可以用转换图来表示。

结点：FA 的状态

  • 初始状态（开始状态）：只有一个，由 start 箭头指向
  • 终止状态：可以由多个，用双圈表示（下例中的 3）

带标记的有向边：如果对于输入 a ，存在一个从状态 p 到状态 q 的转换，就在 p、q 之间画一条有向边，并标记上 a。

image-20191128002520110

在这个图中，一共有4个状态，分别为状态0，状态1，状态2，状态3。状态0为初始状态，由start箭头指向，状态3为终止状态，用双圈表示。

FA定义（接受）的语言

给定输入串 x，如果存在一个对应于串 x 的从初始状态到某个终止状态的转换序列，则称 串 x 被该 FA 接受。

由一个有穷自动机 M 接受的所有串构成的集合称为是该 FA定义（或接收）的语言，记为 $ L(M)$。

image-20191128002951076

对于 abbaabb来说，我们可以判断是否为这个 FA 所接受。能。

接受第一个 a后，由初始状态0转换到状态 0，再遇到两个 b 后，依然保持状态 0，遇到下个 a 时，还保持状态 0，再遇到一个 a 时，转换到状态1，接下来两个 b，分别转换到状态2，和最终状态3。

最长子串匹配原则

当输入串的多个前缀与一个或多个模式匹配时，我们总是选择最长的前缀进行匹配。

image-20191128003035729

对于上图来说，当遇到 < 号时，转换到状态1，当遇到 < = 号时，转换到状态2。

即：在到达某个终态之后，只要输入带上还有符号，DFA 就继续前进，以便找到尽可能长的匹配。

有穷自动机的分类

  • 确定的有穷自动机（DFA）
  • 不确定的有穷自动机（NFA）

确定的有穷自动机 (DFA)

  • DFA定义为一个五元组

  • 假设字母表中没有 $\varepsilon$

image-20191128003106533

例：

在这个有穷自动机DFA 中，

状态集S 包含4个状态。分别是：状态0， 状态1， 状态2， 状态3。

输入字母表Σ 中包含的元素是：符号a，符号b。

转换函数 δ ，我们用一个转换表来表示。

例：状态0 遇到符号 a 时，变成状态1，状态0 遇到 符号 b 时，依旧是状态 0。以此类推，完成转换表(重点考点)。

  • 3是终止态，用 * 标识。

DFA可以用状态图或转换表两种等价方式来表示。

image-20191128003129846

DFA 的算法实现

  • 输入：以文件结束符 eof 结尾的字符串 x，DFA 的开始状态为 s0，接受状态集 F，转换函数 move

  • 输出：如果 D 接受 x，则回答“yes”，否则回答“no”

  • 方法：将下述算法应用于输入串 x

    image-20191128173024112

s=s0;
c=nextChar();    //返回输入串x的下一个符号
while(c!=eof)
{
    s=move(s,c); //从状态s出发，沿着标记为c的边所能到达的状态
    c=nextChar();
}
if(s在F中)
    return "yes";
else
    return "no";

非确定的FA (NFA)

  • DFA定义为一个五元组

  • 同样假设字母表中没有 $\varepsilon$

  • NFA 与 DFA 唯一的区别是：从状态 s 出发，能到达的状态可能有多个。（并不是唯一确定的）

    因此，转换函数为集合，而不是元素。

image-20191128011646974

例：

在这个例子中，在初始状态0，遇到符号 a 的时候，它进入的状态包含状态0和状态1 ，两个元素。在状态0 时，遇到符号 b 时，它进入的状态只有 状态 0，因此集合中只有状态 0 一个元素。

如果转换函数 没有给出对应于状态-输入对的信息，就把空集放入到相应的表项中。

image-20191128011817554

带有 ε边 的 NFA

在状态 a，不需要遇到任何符号，即可进入状态 b，在状态 b，不需要任何符号，即可进入状态 c。

一旦进入状态 b，就不再接受符号 0，同理，一旦进入状态 c，就不在接受符号 1。

这个带有 空边 的NFA 接受的语言是 由若干个 0 连接 若干个 1 再连接上 若干个 2。（r=0 * 1 * 2*）

image-20191128011907201

带有 ε边 和 不带有 ε边 的 NFA的等价性

  • 不带空边的状态 A：由若干个 0 构成
  • 不带空边的状态 B：由若干个 0 连接若干个 1 构成
  • 不带空边的状态 C：由若干个 0 连接 若干个 1 连接 若干个 2 构成

但是状态A,B,C 都可以概括为若干个 0 连接 若干个 1 再连接上 若干个 2 构成。

image-20191128012012232

DFA和NFA的等价性(重点考点)

对任何非确定的有穷自动机 NFA，存在定义同一语言的确定的有穷自动机 DFA。

对任何确定的有穷自动机 DFA，存在定义同一语言的非确定的有穷自动机 NFA。

DFA 和 NFA 可以识别相同的语言

这两个 DFA 和 NFA 都识别的是以 abb结尾 的 a,b 串。

image-20191128163557050

等价性(重点考点)

  1. (重点考点)：正则文法(即3型文法，a->b形式) = 正则表达式(大概是字符串，正则表达式是正则语言更紧凑的表达方式) = 有穷自动机

  2. 给定正则文法，可以构造等价的有穷自动机，给定有穷自动机，能够构造出相应的正则文法。

  3. (重点)：DFA和NFA都可以识别同一种语言，但就在表现形式而言，NFA比DFA更加直观，就计算机实现而言，NFA比DFA更难实现。

  4. 从正则表达式构造NFA比较简单，然后再将NFA转换成DFA

  5. 带有 ε边 和 不带有 ε边 的 NFA也具有等价性

正则表达式和有穷自动机之间的转换

(重点考点)

记住几个常见的，然后把RE不停分解即可

正则表达式是采用符号序列的模式，它可以很直观的描述单词的构成。但在构造分析器时，我们真正实现和模拟的是 DFA。因此这涉及到从正则表达式到有穷自动机的转换。

从正则表达式到 DFA 的转换是比较困难的。所以我们通常是 将正则表达式 转换成 NFA ，再将 NFA 转换 成 DFA。

即：RE -> NFA -> DFA

image-20191128163642655

从RE到NFA

image-20191128214119559

正则表达式经过运算，仍然是正则表达式

image-20191128214307836

不停的分解子表达式，即可求得最终的 NFA。

例：

将正则表达式 r=（a|b）*abb 对应的 NFA，不断地进行分解。

首先将 （a|b)* abb 分解成 4 个子表达式连接的形式。再将 （a|b）* 继续进行分解，最终得到最后结果。

image-20191128214509128

从NFA到DFA的转换

(重点考点)

举例

例1:

image-20191128214827894

NFA转换表 -> 根据表新的状态

从 NFA 转换到 DFA 时，我们要构造新的状态。

比如说，在初始状态 a ，遇到符号 a 时，可能继续保持 状态 a，也有可能转换到 状态 b。因此构造新的状态 a,b。

验证NFA和DFA是否等价：表达的正则表达式一样

DFA 的每个状态都是由 NFA 中的状态构成的集合，即 NFA 状态集合的一个子集。

例2：带有 ε 边 的 NFA 到 DFA 的转换

==注意转换表的生成==，A遇到0可以到状态ABC，遇到1可以到状态BC,遇到2可以到状态C.

转换表中有几个非空集合，最后DFA就有几条状态转移线->这是错误的结论，应该跟着它的思路去推导出来，这种题要重新自己做一遍

因为 状态 A 不需要任何输入，即可转换成状态 B，状态 C。所有在遇到输入 0时，它既可以是状态 A，也可以是 状态 B，状态 C。后面同理，即可得状态表。

![image-20191128215348210](/Users/hamster/Library/Application Support/typora-user-images/image-20191128215348210.png)

把ABC组合起来构成start，同时也是终结态。注意跟着这个表达式的结构画出NFA和DFA

子集构造法

这个MOOC讲的比较模糊，建议结合课堂例题再看一下，感觉期末肯定会考

DFA的每个状态都是一个由 NFA中的状态构成的集合,即 NFA状态集合的一个子集：

image-20191128215642257

计算 ε-closure 空闭包函数

image-20191128220820422

识别单词的DFA

过程总结：先写出正则定义，再写出NFA，最后把NFA转化成DFA

识别标识符的 DFA

下面图中识别标识符的 DFA，第一部分识别字母和下划线，第二部分识别字母和下换线和数字组成的串。

因为这个 NFA 就是 DFA，因此不需要进行转换。

image-20191128220851091

识别无符号数的 DFA

第一部分是长度大于等于1的数字串，第二部分是可选的小数部分（两个子表达式进行或运算得到的），第三部分是可选的指数部分（两个子表达式进行或运算得到的）。

image-20191128220929335

再将 NFA 转换成 DFA，如下图所示：

自己推导一遍

image-20191128221020821

识别各进制无符号整数的 DFA

image-20191128221044975

识别注释的 DFA

image-20191128221107888

识别 token 的 DFA

识别关键字时把IDN与关键字表对照查询

image-20191128221135193

词法分析阶段的错误处理

词法分析阶段可检测错误的类型

  1. 单词拼写错误

    例：int i=0x3G,float j=1.05e

  2. 非法字符

    例：~@
    词法错误检测
    如果当前状态与当前输入符号在转换表对应项中的信息为空，而当前状态又不是终止状态，则调用错误处理程序。

错误处理程序

根据最长子串匹配原则，查找已扫描字符串中最后一个对应于某终态的字符

  • 如果找到了，将该字符与其前面的字符识别成一个单词。然后将输入指针退回到该字符，扫描器重新回到初始状态，继续识别下一个单词
  • 如果没找到，则确定出错，采用错误恢复策略。

错误恢复策略

最简单的错误恢复策略：“恐慌模式”恢复

从剩余的输入中不断删除字符，直到词法分析器能够在剩余输入的开头发现一个正确的字符为止。

语法分析

语法分析的任务是根据给定的文法，识别数据中的各类短语，并构造语法分析树。如果输入串的各个单词恰好自左至右地站在分析树的各个节点上，则该词串就是该语言的一个句子。

构造的方法主要分为2类，包括自顶向下分析和自底向上分析。

自顶向下分析概述

自顶向下的分析是指从分析树的顶部（根节点）向底部（叶节点）方向构造分析树，可以看做是从文法开始符号S推导出单词串w的过程，例如：

image-20191130114221614

输入为id+(id+id)，可以理解为通过语法分析树可以最终得到id+(id+id)，即将叶子节点连接起来就可以构成id+(id+id)。

每次推导中都要作两个选择：

  • 替换哪一个非终结符
  • 用哪个候选式来替换非终结符

最左推导和最右推导

最左推导

在最左推导中，从文法的开始符号起，总是选择每个句型的最左非终结符进行替换，得到的句型称 为当前文法的最左句型(left-sentential form)

最右推导与最左规约

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

image-20191130114317278

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

从右边开始推导比较规范

自底向上：最左规约

自顶向下：最左推导

最左推导和最右推导具有唯一性。

自顶向下的语法分析采用最左推导方式

image-20191201002921672

自顶向下的语法分析采用最左推 导方式，总是选择每个句型的最左非终结符进行替换 ，根据输入流中的下一个终结符，选择最左非终结符的一个候选式。

试着写一下下面的题，用最左推导

image-20191130114354939

当非终结符的选择不止一种的时候，叶子节点是什么要参考当前的输入指针是什么。当前指针指向的符号已经使用则进行后移。如指针指向+号表示：此次要选择以+号开头的非终结符。

自顶向下语法分析的通用形式

递归下降分析(Recursive-Descent Parsing)，由一组过程组成，每个过程对应一个非终结符 。

从文法开始符号S对应的过程开始，其中递归调用文法中其它非终结符对应 的过程。如果S对应的过程体恰好扫描了整个输入串，则成功完成语法分析。

void A( ) { 
1)	选择一个A产生式，A →X1X2… Xk； 
2)	for( i = 1 to k) { 
3)		if( Xi是一个非终结符号) 
4)			调用过程Xi ( ) ; 
5)		else  if ( Xi等于当前的输入符号a)       
6)			读入下一个输入符号; 
7)		else /* 发生了一个错误*/ ; 
	}
}

但可能需要回溯，从而导致效率比较低。需要回溯的分析器叫做不确定的分析器。

预测分析(Predictive Parsing)

预测分析是递归下降分析技术的一个特例，通过在输入中向前看固定个数（通常是一个）符号来选 择正确的A-产生式。

可以对某些文法构造出向前看k个输入符号的预测分析器，该类文法有时也称为LL(k) 文法类

预测分析不需要回溯，是一种确定的自顶向下分析方法
。

文法转化

并不是所有的文法都适合自顶向下的分析。

同一非终结符的多个候选式存在共同前缀，将导致回溯现象，例如：

问题1:此时就会在a的时候产生歧义。

image-20191201004042231

问题2:左递归文法会使递归下降分析器陷入无限循环

含有A→Aα形式产生式的文法称为是直接左递归的 (immediate left recursive)

如果一个文法中有一个非终结符 A 使得对某个串α存 在一个推导A⇒+AαA\Rightarrow ^+AαA⇒
+
Aα ，那么这个文法就是左递归的。

经过两步或两步以上推导产生的左递归称为是间接左递归的。

image-20191201004426055

LL(1)文法

语法制导翻译

语法制导翻译概述

将语义分析和中间代码生成统称为语义翻译，而语义翻译和语法分析统称为语法制导翻译，边分析语法，边完成制导翻译的过程

image-20191128110328713

语法制导定义(SDD)

综合属性和继承属性

SDD的求值顺序

S-属性定义与L-属性定义

语法制导翻译方案

语法制导翻译方案(SDT)是在产生式右部中嵌入了程序片段(称为语义动作)的CFG。SDT可以看作是SDD的具体实施方案，本节主要关注如何使用SDT来实现两类重要的SDD， 因为在这两种情况下，SDT可在语法分析过程中实现 ：

  • 基本文法可以使用LR分析技术，且SDD是S属性的
  • 基本文法可以使用LL分析技术，且SDD是L属性的

S-SDD转换为SDT

将一个S-SDD转换为SDT的方法：将每个语义动作 都放在产生式的最后。例如：

image-20191128104350111

L-SDD转换为SDT

在非递归的预测分析过程中进行语义翻译

在递归的预测分析过程中进行语义翻译

在LR分析过程中进行语义翻译

中间代码的生成

课件PPT

中间语言

?这个四元表达式之前有MOOC讲解的知识点，后期记得补上

  1. 中间语言（复杂性界于源语言和目标语言之间） 的好处：

中间代码也叫中间语言（Intermediate code /language）是：源程序的一种内部表示，不依赖目标机的结构，复杂性介于源语言和机器语言之间。

image-20191212214030712

  1. 常用中间语言，重点讲了三地址代码的四元式，==给一个语句要求写出四元式==

image-20191212215641717

  1. 四元式例题

  1. 三地址语句的种类，?有些种类的不是到怎么写四元式

image-20191212214431636

说明语句的翻译

?PPT没有内容,要掌握吗

赋值语句的翻译

  1. 赋值语句的基本文法

    赋值语句翻译的主要任务是生成对表达式求值的三地址码

    例题，根据表达式写出三地址码和四元式 ->

    image-20191212215432319

  2. 赋值语句对应的语法制导翻译SDT

    赋值语句翻译的主要任务是生成对表达式求值的三地址码，因此为基本文法中的非终结符S和E分别设置了综合属性code，用来表示这两个文法符号对应的三地址码，另外E还有一个综合属性addr，用来表示表达式的值的存放地址

几个其中函数：

  • lookup(name)：查询符号表 返回name对应的记录；
  • gen(code)：生成三地址指令code；
  • newtemp( )：生成一个新的临时变量t， 返回t的地址addr。

布尔表达式的翻译

控制语句的翻译

过程调用的处理

dfsagg

控制流语句及STD

先分析控制流语句的代码结构，定义文法符号的属性

其中包含的继承属性为：

S.next：是一个地址，该地址中存放了紧跟在S代码之后的指令 (S的后继指令)的标号

B.true：是一个地址，该地址中 存放了当B为真时控制流转向的 指令的标号

B.false：是一个地址，该地址 中存放了当B为假时控制流转向 的指令的标号

用指令的标号标识一条三地址指令

image-20191212092405477

然后编写控制流语句的基本文法及STD

newlabel( ): 生成一个地址；

label(L): 将下一条 三地址指令的标号赋给L

1.P->S

image-20191212092630864

课堂笔记

11.07

1.概念：算符(要相邻)，素短语，算符优先关系

2.例题：书本P89
3.判断是否为算法优先文法，算符之间只能有一个关系
4.算符优先关系表
5.FIRSTVT和LASTVT，可以用来构造优先关系表
6.PPT41页例题和书本P91笔记
7.根据PPT41写出PPT44例题
8.PPT46的素短语和最左素短语
9.PPT47的规约过程
10.PPT51页例题
11.规约准确率高，算符优先法速度快

11.14
一、复习
1.规约：找句柄
2.算符优先文法：找最左素短语，i直接返回为最顶端的N，有算符才能规约，否则都是占位符，一定要包含算符。速度快但有时不准确，前提是符合算符优先文法才能用。很多都不适用
3.另一种：LR分析法

二、LR分析法：
1.从左到右扫描符号串，用最左规约，最右推导。能解决大部分语法规则，但二义文法，需要处理才能用。
2.LR(1)分析表，算FIRST和FELLOW，有多个候选式。而LR分析法我们用的是LR分析法，有很多能自动构造LR分析表。
3.课本P101例题，状态栈和符号栈，遇到s5:状态转为5，移入i，指针后移；r2：用(2)表达式进行规约右侧符号，消除此时状态，写入规约后符号，查询Goto表更新状态。栈顶的状态显示了分析的历史信息/进度。
4.根据有限状态自动机DFA，LR(0)item组成的集合

11.28

一、书本125，二义文法不能用LR分析法，图5.11和表5.7的第7行，对于二义文法进行人为选择优先级以规避冲突

二、进入第六章

  • 综合属性、继承属性
  • 终结符只有综合属性，比如digit
  • S-属性定义属于L-属性定义
  • L-属性需要综合属性时可能尚未计算结束，需要多扫描几遍才行，参考其他文件的从左到右计算
  • PPT第22页例题，10进制实数

三、进入第7章

  1. 语义分析和中间代码的生成

  2. 本章目录，这些翻译在参考资料里好像没有

    image-20191128112512716

  3. 常见的中间语言，用的比较多的是三地址代码，四元式表达

    image-20191128110501843

  4. 本书涉及的三地址语句类型

    布尔表达式和控制流语句，两种方法，一种按部就班，一种进行优化，一真一假的话短路掉部分计算

12.05

  1. 条件为真/假的时候，出口不一样，还要加上一个GOTO语句
  2. 如果边分析边生成的话，会比较难一遍扫描完成-》回填机制
  3. 引入ture\false\next三个属性

image-20191205101010915

循环体也要有一个GOTO,为S增加begin属性

顺序执行，保留S.next的原因，因为S可能是条件/循环语句等，

image-20191205101347847

布尔表达式两种翻译方式：

  • 两遍扫描：为给定的输入串构造一棵语法树；对语法树进行深度优先遍历，进行语义规则中规定的翻译。
  • 一遍扫描

分析语法都用LR分析法

一遍扫描的困难：

如If-then-else，在这个语句中，if会有两个jump（j, ， ,跳转地址），插入GOTO语句，用M来用链条连起来，用回填语句M整个扫描完后要规约为一个S;但是扫描到if的时候还不知道入口的跳转地址，定义一个M,示例PPT36页，

emit是要增加一条中间代码

merge合成一个

backpatch是用于回填，先用指针指向

老师上课重点讲了这两个的作用，为了一遍扫描生成中间码

M的作用：用M.quad回填E.turelist，用于记录S1和S2的入口地址，两个backpatch回填

N的作用：对于if-then，完成之后要跳出这个条件语句,强制跳转语句

M与N都是空字

这个语句知道E的真和假，E的假不用执行了，真需要回填

总共三个跳转：只回填真语句的回填，N的回填，假的回填不用

把不知道的地方放到S的属性，S.nextlist=merge(),不知道的先merge到S.nextlist上去，指针附在nextlist后面，什么时候回填还不知道，需要回填的时候在进行回填

边扫描边生成代码：不知道的全部空着，然后用链条把这个放到上一级S的属性，等到知道入口在哪里再进行回填

image-20191205102810201

当E1为假才去看E2，用M记录入口地址

image-20191205104225017

一条中间代码都没有产生。由于不知道E1和E2的真出口，所以要用第2句把E1和E2链接到E上，AorB都是假的话需要一个假出口，那么跳出，所以E2E2的假出口也是E的假出口，这时整个AorB都是假。

merge是链表的合并

image-20191205104611691

AND

E1的真出口是E2的入口地址

E2的真出口是E的真出口

E2、E1的假出口都是E的假出口

image-20191205105832546NOT ()

image-20191205105903510

OR AND NOT （）都没有中间代码的生成，只有涉及到id的时候才产生中间代码。

中间代码：如果满足relop.op操作，操作数满足该关系，就往这个真出口出去，为假的话就强制执行假出口；所以这里总共有2个出口。

中间代码也有需要回填，所以要把真假出口挂到E的链条上

如果回填了的话nextquad会发生改变

image-20191205110007147

举例：E(C)的假出口需要往105回填为106，不知道怎么回填的出口还是挂到上一级。8条代码里3个地址确定，不确定的其他传到E上

image-20191205110523628

两种方法，以上一种(画图、生成中间代码)，以下方法：PPT28页

优先级：先做and后做or，图中标出了两个真出口和两个假出口

image-20191205111639649

控制语句的翻译

while要跳回头部判断，S1.begin

对E的真出口进行回填，假出口要挂在S上，S.nexilist也要回填！！！

image-20191205113019738

例题，包含了布尔、控制、赋值语句

a<b的假出口为S.next，不要随意写跳到107

image-20191205113230955

12.12

控制语句的翻译

begin不见了，用M1代替

image-20191212101929099

[？？？？]

S->begin L end

S->A 【S定义为一个语句】

{S.nextList:=makelist()}

A如果是一个赋值语句，因为要用S来表示它，A要规约为S，

为了和其他while等保持一致，留一个接口，但是直接给个空就行

L->S

{L.nextlist:=S.nextlist}

向前转移和向后转移

image-20191212103511132

L已经定义为了变量而不是标号或者还没定义，报错

L:

image-20191212103721251

case语句，也有叫做switch

两种翻译法生成语义的方法是一样的，但是第一种比较方便优化

把L都标出来，最后统一做判断

过程调用的处理

我们只讲转地址，不讨论传参数

过程调用的翻译子程序

？？？ 没听懂

把MOOC看了

优化

符号表和内存，跳过

==先讲了循环优化啥的再讲的基本块==

单一入口没有入口和goto跳转，顺序执行的

循环是优化的重点

image-20191212112633270

12.19

局部优化

什么是基本块、怎么划分、

image-20191219101408869

image-20191219101658878

划分基本块，课堂详讲的练习，讲了2次

image-20191219101826384

在一个基本块内进行优化

基本块用DAG表示

叶子结点是标识符或常数，然后添加到上级结点(附加操作符)

常见DAG：

基本块的DAG构造算法：举例课本P284，看！！！

image-20191219103216509

合并已知量：如果来两个都是常数，则删除，参考步骤b，还有其他规则。。。。建议看MOOC

DAG图的优化：

image-20191219104454583)image-20191219105123608

最后简化为4个运算，公共变量用S代替

目标代码生成——最后一章

四元式有一个优化，最后代码也有一个优化

==第一个操作数==

了解一个简单的代码生成器

附加在四元式的待用/活跃信息表

每一个变量是否会在后面被引用

比如第一个表：T=A-B,T在第3个被引用，A在第2个引用，B在右操作数被引用

image-20191219111824648

代码生成算法

作业习题

作业，P306 3(B2)

考试

选A卷

判断题10分，

目标码

前3重中之重

做过的题一定会做

词法分析

优化放在B卷考

词法、语法、中间代码。 伪代码，目标有一点

概念性的东西

2*5，2题，每题5分 判断

3*8 选

22*3 大题

词法分析 语法分析（分析器要会） 中间码生成（子程序提供，要用过程）蓝色基本上可以忽略

文章作者: 桔子邮差
文章链接: http://yoursite.com/2019/11/27/%E7%BC%96%E8%AF%91%E5%8E%9F%E7%90%86/
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 微木斋！
编译原理
打赏
  • 微信
  • 支付寶
评论
繁