哈工大慕课《编译原理》笔记

第一讲 绪论

语义分析

语句主要分为：声明语句（数据对象和过程）、可执行语句

语义分析的主要任务

第二讲 语言及其文法 2020-4-14

2.1 基本概念

字母表

字母表 ∑是一个有穷符号集合；

符号：字 母、数、标点符号、 …

字母表上的运算

串

串的运算

2.2 文法定义

文法的形式化定义

北航文法：|、（、[、{

或、限定范围、可选、闭包

如果不会引起误解，产生式就可以代表一种语言

产生式的简写<!>

符号约定

2.3 语言的定义

有了规则，怎么识别是否是这种语言？

推导与规约

句型和句子

语言的形式化定义

必须是句子，只有终结符

语言的运算

不是很理解，这里的运算是指语言的吗？

举例：把集合看成一种语言，字母、数字的集合，看作是语言；然后语言运算，就是标识符了

(这么看也没错，语言本就是一个集合)

2.4 文法的分类

0型文法

1型文法

2型文法

3型文法

关系

2.5 CFG的语法分析树

短语和直接短语

句柄：最左直接短语

二义性文法

第三讲 词法分析 2020-4-14

3.1 正则表达式

正则表达式(Regular Expression，RE)是一种用来描述正则语言的更紧凑的表示方法

正则表达式可以由较小的正则表达式按照特定规则递归地构建。每个正则表达式r定义（表示）一个语言，记为L(r )。这个语言也是根据r的子表达式所表示的语言递归定义的

正则表达式的定义

空串是RE，表达的语言也是空串

字母表上的任何一个符号，表示的语言只包含它本身

集中运算：

• 连接：
• 或：|
• 克林闭包：语言的克林闭包

• 括号可以消去

  正规式简化

  正闭包

  r+ = rr = r\r，r*= r+|ε

  +与*具有相同的运算优先级和结合性

  可选符

  r?=r |ε

  字符组

  字符组是或关系的缩写形式，它把所有存在或关系的字符集中在[ ]里面

  枚举方式: 如[abc]，它等价于a|b|c
  分段方式: 如[0-9a-z]，它等价于[0123456789abcdefghijklmnopqrstuvwxyz]
  17

  非字符组

  若Σ={a,b,c,d,e,f,g}，则L([ ^abc ]) = { d, e, f, g }。

  串

  引入串的表示可以避免与正规式中运算符的冲突。例如：”a|b”=a”|”b≠a|b。

  正规式简化2

  转义符\，用于将特殊符号的含义取消
  {m,n} 匹配其前面的字符至少出现m次，最多出现n次
  {n} 匹配其前面的字符恰好出现n次
  {n,}匹配其前面的字符出现不小于n次
  首符号‘^’
  尾符号‘$’
  .匹配除了换行符外任意一个字符

举例

正则语言

可以用RE定义的语言叫做正则语言(regular language)或正则集合(regular set)

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

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

RE的代数定律

3.2 正则定义

举例

3.3 有穷自动机

FA的表示

转换图

结点：FA的状态

初始状态（开始状态）：只有一个，由start箭头指向

终止状态（接收状态）：可以有多个，用双圈表示

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

FA定义（接收）的语言

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

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

最长子串匹配原则(LongestString MatchingPrinciple)

匹配到 < 之后，只要还有符号，就继续匹配；即使到达某个终态

++ 可以也匹配+；但我们把他看作是++

3.4 有穷自动机的分类

1、确定的有穷自动机(DFA)

对应一个输入字母，只有一种转换

2、非确定的有穷自动机(NFA)

从状态出发，沿着标记出发，能到达的状态是个集合

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

DFA和NFA的等价性

• 对任何非确定的有穷自动机N ，存在定义同一语言的确定的有穷自动机D

• 对任何确定的有穷自动机D ，存在定义同一语言的非确定的有穷自动机N

3、带有“ε-边”的NFA

不是相同状态，例如有些东西不再接收

带有和不带有“ε-边”的NFA 的等价性

4、DFA的算法实现 <<!!!>>

NFA直观；但DFA实现简单

louden 书的实现

和博客类似

3.5 从正则表达式到有穷自动机

识别单词>> 正则表达式 ，因为直接从正则表达式到 DFA比较难；所以先到 NFA，再到DFA

根据RE 构造NFA

3.6 从NFA到DFA的转换

从NFA到DFA的转换

从带有ε-边的NFA到DFA的转换

子集构造法（subset construction）

从初始状态求闭包开始（就是空转换能到达的状态集合）

Dstates ： DFA 的 状态集合；一开始只有初始闭包；

之后对每一个输入符号，状态转换，再求闭包；这是一个新状态；

注意标记问题；就像dfs，visited数组一样

似乎没有最小化DFA

3.7 识别单词的DFA

DFA举例

1、识别标识符的DFA

慕课提示：识别关键字和标识符是一样的；有一个关键字的表

2、识别无符号数的DFA

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

4、识别注释的DFA

5、识别Token

词法分析阶段的错误处理<<!!!>>

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

• 单词拼写错误
• 非法字符

词法错误检测

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

错误处理

不是很理解他说的

第四讲 语法分析1 2020-4-3

4.1 自顶向下分析概述

4.2 文法转换

1、消除直接左递归

事实上，这种消除过程就是把左递归转换成了右递归

举例：

2、消除间接左递归

消除左递归算法：

3、提取左公因子算法

应该是解决有多个候选式导致的回溯问题

总结

没有矩阵消除左递归方法

但没有曾老师讲的详细：

情况1：同一非终结符有多个候选式

情况2： e和可能句型片断的后续符号相同

但注意到，内容可能放在后面，如FIRST集合

4.3 LL(1)文法

S_文法

要求相当严格

（有空产生式）什么时候使用ε产生式？

如果当前某非终结符A与当前输入符a不匹配时，若存在A→ε，可以通过检查a是否可以出现在A的后面，来决定是否使用产生式A→ε（若文法中无A→ε ，则应报错）

所以就有了下面的FOLLOW集合：

非终结符A的后继符号集 FOLLOW

可能在某个句型中紧跟在A后边的终结符a的集合，记为FOLLOW(A)

当A选择空语句的时候，接下来的终结符可能是什么

产生式的可选集 SELECT

确定下一个字符是什么的时候可以选择

产生式A→β的可选集是指可以选用该产生式进行推导时对应的输入符号的集合，记为SELECT( A→β )

虽然可以空串，但仍然要终结符开始：

串首终结符集 FIRST

给定一个文法符号串α， α的串首终结符集FIRST(α)被定义为可以从α推导出的所有串首终结符构成的集合。如果α * ε，那么ε也在FIRST(α)中

很好理解，符号串可以推出的第一个终结符

没空串，可选集就是串首；有，就要加上Follow减去空

LL(1)文法

和曾老师讲的内容一样，即：

（1）不考虑ε-产生式的情况

根据产生式的首字符进行判断，首字符不能相同

（2）含ε-产生式的情况

在使用ε-产生式推导时，需考虑非终结符的后续符号串的首字符；不能相同

4.4 FIRST集和FOLLOW集的计算

FIRST集合

以下是符号X的集合计算：

注意：第二步，需要直到yk都能推出空串，才能加入空串到集合中；前面能推出空串，吧yi+1的first加入集合中

符号串的集合计算，如下图所示：

非终结符的Follow集计算

不断应用下列规则，直到没有新的终结符可以被加入到任何FOLLOW集合中为止：

• 将$放入FOLLOW( S )中，其中S是开始符号，$是输入右端的结束标记

即开始的符号，有$ 符号/初始化

逐个产生式分析；每个产生的右部逐个非终结符分析

• 如果存在一个产生式A→αBβ，那么FIRST ( β )中除ε 之外的所有符号都在FOLLOW( B )中
• 如果存在一个产生式A→αB，或存在产生式A→αBβ且FIRST ( β ) 包含ε，那么FOLLOW( A )中的所有符号都在FOLLOW( B )中

哈工大课程里面说要不断重试，直到不刷新

但曾老师好像先看右部有几个符号，把相同的符号一次看完

SELECT 集合计算

对于表达式而言

似乎可以根据 同一非终结符 的select集合是否相交推出是否 是LL(1)文法

曾老师的课:first+集合和select差不多；根据是否相交判断文法

第五讲 语法分析2 2020-4-3

4.5 递归的预测分析法

有伪代码例子

取下一个token来分析，

4.6 非递归的预测分析法

下推自动机，栈的思想

下推自动机比有穷自动机的识别能力更强，有穷自动机的识别能力不强是因为它的记忆功能不强

举例

非递归的预测分析不需要为每个非终结符编写递归下降过程，而是根据预测分析表构造一个自动机，也叫表驱动的预测分析

对比

4.7 预测分析中的错误处理

两种错误：

• 栈顶的终结符和当前输入符号不匹配
• 栈顶非终结符与当前输入符号在预测分析表对应项中的信息为空

恐慌模式

• 忽略输入中的一些符号，直到输入中出现由设计者选定的同步词法单元(synchronizing token)集合中的某个词法单元

例如可以把FOLLOW(A)中的所有终结符放入非终结符A的同步记号集合

• 如果终结符在栈顶而不能匹配，一个简单的办法就是弹出此终结符

第六讲 语法分析3 2020-4-10

4-8 自底向上的语法分析

• 从分析树的底部(叶节点)向顶部(根节点)方向构造分析树

• 可以看成是将输入串w归约为文法开始符号S的过程

• 自顶向下的语法分析采用最左推导方式
  自底向上的语法分析采用最左归约方式（反向构造最右推导）

• 自底向上语法分析的通用框架：移入-归约分析(Shift-Reduce Parsing)

移入-归约分析器

移入-归约分析中存在的问题

• 错误地识别了句柄

4-9 LR 分析法概述

L: 对输入进行从左到右的扫描
R: 反向构造出一个最右推导序列

• LR(k)分析
  需要向前查看k个输入符号的LR分析

k = 0 和k = 1 这两种情况具有实践意义
当省略(k)时，表示k =1

LR 分析法的基本原理

• 自底向上分析的关键问题是什么？

如何正确地识别句柄

• 句柄是逐步形成的，用“状态”表示句柄识别的进展程度

LR 分析器（自动机）的总体结构

LR 分析表的结构

注意：

• 规约的时候 当前状态出栈、符号出栈、新符号入栈；接下来要根据新的状态栈顶状态goto新状态；

• 似乎一个符号都会对应一个状态，规约的时候出去几个符号，就出去几个状态

LR 分析器的工作过程

LR 分析算法

算法简单、主要是构建分析表复杂

4-10 LR(0)分析

LR(0) 项目

右部某位置标有圆点的产生式称为相应文法的一个LR(0)项目（简称为项目）

增广文法

如果G 是一个以S为开始符号的文法，则G的增广文法G’ 就是在G中加上新开始符号S’ 和产生式S’ → S而得到的文法

引入这个新的开始产生式的目的是使得文法开始符号仅出现在一个产生式的左边，从而使得分析器只有一个接受状态

文法中的项目

后继项目

同属于一个产生式的项目，但圆点的位置只相差一个符号，则称后者是前者的后继项目

A→α· Xβ的后继项目是A→αX·β

可以把等价的项目组成一个项目集( I ) ，称为项目集闭包(Closure of Item Sets)，每个项目集闭包对应着自动机的一个状态

举例：构造LR(0)自动机

4-11 LR(0)分析表的构造

CLOSURE( )函数

很好理解：期待B，那么B的产生式就进来，（点在前面

求等价状态的集合

GOTO ( )函数

返回项目集I对应于文法符号X的后继项目集闭包

X的后继项目 集合；再求闭包

也就是在求后继项目集合，然后还需要求闭包

规范LR(0) 项集族

这样就出来了很多个项目集，就是不同的状态集

LR(0)分析表构造算法

先求出项集族；然后再填表：action；goto；规约；acc

LR(0) 分析过程中的冲突

• 移进/归约冲突

即有移进又有规约

• 归约/归约冲突

多种规约

接下来的算法解决这些问题

第七讲 语法分析4 2020-4-11

4-12 SLR分析

归根结底，正确识别句柄

SLR分析法的基本思想

也叫SLR(1)；因为1可以省略，也叫SLR

多看一个符号，根据下一个符号，仅用FOLLOW集合就可以判断是否规约

SLR分析表

有点不同，黄色行，本来LR(0)是全r的，规约；现在有的要继续移入

移入的地方变成规约；规约主要是由空产生式规约

SLR 分析表构造算法

也就是看下一个字符是否规约；因为如果规约，下个字符那么必在follow集合中；否则不在

SLR 分析中的冲突

4-13 LR(1)分析

LR(1)分析法的提出

SLR分析存在的问题

SLR只是简单地考察下一个输入符号b是否属于与归约项目A→α相关联的FOLLOW(A)，但b∈FOLLOW(A)只是归约α的一个必要条件，而非充分条件

对于产生式A→α的归约，在不同使用位置，A会要求不同的后继符号

在特定位置，A的后继符集合是FOLLOW(A)的子集

规范LR(1)项目

将一般形式为[A→α·β, a]的项称为LR(1) 项，其中A→αβ 是一个产生式，a 是一个终结符(这里将$视为一个特殊的终结符)它表示在当前状态下，A后面必须紧跟的终结符，称为该项的展望符(lookahead)

• LR(1) 中的1指的是项的第二个分量的长度

LR(k)向前展望k个符号

• 在形如[A→α·β, a]且β ≠ ε的项中，展望符a没有任何作用

移入项目、待约项目是没有任何作用的

• 但是一个形如[A→α·, a]的项在只有在下一个输入符号等于a时才可以按照A→α 进行归约

这样的a的集合总是FOLLOW(A)的子集，而且它通常是一个真子集

等价LR(1)项目

也就是说 ，有非终结符 就要加入等价项目

举例

有些状态有相同的项目，但是状态中的语句数目等不同、展望符不同，不是同一个状态，如10、8

LR(0)：规约状态就规约

SLR：下一个字符在FOLLOW集才能规约

LR(1)：与展望符相同才能规约，Follow集的子集

CLOSURE、goto函数变化

强调：对于展望符，可以理解为规约时的条件，即，下个字符是什么；只有对规约项目有意义

LR分析表构造算法

4-14 LALR分析

第八讲 语法制导翻译1 2020-4-23

5-1 语法制导翻译概述

什么是语法制导翻译

语法制导翻译的基本思想

为CFG中的文法符号设置语义属性，用来表示语法成分对应的语义信息

文法符号的语义属性值是用与文法符号所在产生式（语法规则）相关联的语义规则来计算的

对于给定的输入串x ，构建x的语法分析树，并利用与产生式（语法规则）相关联的语义规则来计算分析树中各结点对应的语义属性值

两个概念

将语义规则同语法规则（产生式）联系起来要涉及两个概念

• 语法制导定义(Syntax-Directed Definitions, SDD )

• 语法制导翻译方案(Syntax-Directed Translation Scheme , SDT )

语法制导定义(SDD)

SDD是对CFG的推广

• 将每个文法符号和一个语义属性集合相关联

• 将每个产生式和一组语义规则相关联，这些规则用于计算该产生式中各文法符号的属性值

例：如果X是一个文法符号，a是X的一个属性，则用X.a表示属性a在某个标号为X的分析树结点上的值

语法制导翻译方案(SDT)

SDT是在产生式右部嵌入了程序片段的CFG，这些程序片段称为语义动作。

按照惯例，语义动作放在花括号内

5-2 语法制导定义SDD

综合属性(synthesized attribute)

继承属性(inherited attribute)

举例

算术表达式

声明语句

属性文法(Attribute Grammar)

没有副作用的？

5-3 SDD的求值顺序

SDD为CFG中的文法符号设置语义属性。对于给定的输入串x，应用语义规则计算分析树中各结点对应的属性值

依赖图(Dependency Graph)

综合属性在右边，继承属性在左边

虚节点：

属性值的计算顺序

排序不止一种

对于只具有综合属性的SDD ，可以按照任何自底向上的顺序计算它们的值

对于同时具有继承属性和综合属性的SDD，不能保证存在一个顺序来对各个节点上的属性进行求值

这里的前两点 不是很懂，但似乎不影响

期望的是自顶向下的实现

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

S-属性定义

LR？

L-属性定义

S-SDD只有综合属性，L-SDD没有限制综合属性

依赖的只有三种：

父亲的继承属性、左边的属性、本身的属性

A为什么不能是综合属性？

会造成循环依赖

第九讲 语法制导翻译2 2020-4-23

5-5 语法制导翻译方案SDT

将S-SDD转换为SDT

子节点都是综合属性，所以要放在最后

当规约发生的时候，执行语法动作

需要扩展分析栈

将L-SDD转换为SDT

L-属性定义的SDT 实现

可以通过三种方式实现：

前两种都是LL分析类型，LL文法

最后是LR分析过程中翻译

5-6 在非递归的预测分析过程中进行翻译

L-SDD 的非递归实现，是自顶向下的方法

例子：待续

第十讲 语法制导翻译3 2020-4-23

5-7 在递归的预测分析过程进行翻译

非终结符的过程进行扩展，与递归下降分析法对于

算法：

5-8 L-属性定义的自底向上翻译

毫无疑问：S-SDD 可以直接自底向上

给定一个以LL文法为基础的L-SDD，可以修改这个文法，并在LR语法分析过程中计算这个新文法之上的SDD

也就是说LL文法，通过LR语法分析来建立SDD

方法：就是替换；空产生式；

我们会发现用到的属性不在产生式中，但LR用的是栈，可以找到

举例：带续：

第十一讲 中间代码生成1