编译原理

编译原理学习笔记。

绪论

什么是编译

程序设计语言

  • 机器语言:可以被计算机直接理解
  • 汇编语言:引入助记符
    • 依赖于特定机器,非计算机专业人员使用受限制
    • 编写效率依然很低
  • 高级语言:类似于数学定义或自然语言的简洁形式
    • 接近人类表达习惯
    • 不依赖于特定机器
    • 编写效率高
1
2
3
C706 0000 00002  //机器语言
MOV X, 2 //汇编语言
x = 2 //高级语言

编译:

  • 高级语言->汇编语言
  • 讲高级语言(源语言)翻译成汇编语言或机器语言(目标语言)的过程

源文件到目标机器码的过程:

预处理器:

  • 负责把存储在不同文件中的源程序聚合在一起
  • 把被称为宏的缩写语言装换为原始语句
    编译器
  • 将源代码编译成汇编代码
    汇编器:
  • 将汇编代码编译成可重定位的机器代码
  • 可重定位:表示在内存中存放的起始位置L不是固定的
    加载器:
  • 修改可重定位地址:将修改后的指令和数据放到内存中适当的位置
  • 起始地址+相对地址=绝对地址
    链接器:
  • 大型程序经常被分割成多个部门被编译,所以可重定位的机器代码可以与其他可重定位目标程序或库文件进行链接生成可执行代码
  • 解决外部内存地址问题

编译系统结构

编译器的输入是高级语言程序,输出是汇编语言程序/机器语言程序。

分析部分:与源语言相关

  • 词法分析:确定各个单词的词性或词类

  • 语法分析:识别句子中的各类短语,从而确定句子结构

  • 语义分析:根据句子结构分析出各个短语在句子中充当什么成分,从而确定各个名字性成分同谓语动词之间的关系

  • 中间代码生成:语义分析的结果通常直接当做中间代码生成的结果,这两个阶段通常一起实现。

综合部门:与目标语言相关

  • 目标代码生成:

  • 代码优化:

语法制导翻译:这种情况下,语法分析,语义分析和中间代码生成放在一起实现。

词法分析

从左向右逐行扫描源程序的字符,识别出各个单词,确定单词的类型。将识别出的单词转换成统一的机内表示——词法单元(token)形式。token是一个二元组,<种别码,属性值>

种别码:

  • 关键字:if,else。一词一码

  • 标识符:变量名,数组名,函数名。多词一码

  • 常量:整形,浮点型,字符型,布尔型。一型一码
  • 运算符:算术,关系,逻辑。一词一码或一型一码
  • 界限符:括号,分号。一词一码

对于多词一码或者一型一码,通过属性值来区别。

语法分析

从词法分析输出的token序列中识别出各类短语,并构造语法分析树。语法分析树描述了句子的语法结构。

  • 赋值语句的分析树
1
2
position       =    initial        +   rate      *       60   ;
<id, position> <=> <id, initial> <+> <id,rate> <*> <num,60><;>

  • 变量声明语句的分析树

语义分析

主要任务:

  • 收集标识符的属性信息

    • 种属:简单变量,复合变量(数组),过程
    • 类型:字符型,整型
    • 存储位置、长度
    • 变量的值
    • 变量的作用域
    • 参数和返回值信息:对于过程(函数),参数个数等

    标识符属性存储在符号表中,每个标识符对应符号表中的一行,每一列对应标识符的属性。

字符串表用来存储标识符和字符常量。Name字段被分割成两个部分,第一个部分用来存储字符串的其实位置,第二个部分用来存储字符串的长度。

  • 语义检查

    • 变量或过程未经声明就使用

    • 变量或过程名重复声明

    • 运算分量类型不匹配

    • 操作符与操作数之间的类型不匹配,比如

      • 数组下标不是整数
      • 对非数组变量使用数组访问操作符
      • 对非过程名使用过程调用操作符
      • 过程调用的参数类型或数目不匹配
      • 函数返回类型有误

中间代码生成

中间表示形式:

  • 三地址码
    • 三地址码由类似于汇编的指令序列组成
    • 每个指令最多有三个操作数
    • 三地址指令序列唯一确定了运算完成的顺序
    • 三地址指令的表示
      • 四元式: (op,y,z,x),op表示操作符,x表示目标数,y,z表示操作数
      • 三元式
      • 间接三元式
  • 语法结构树/语法树

目标代码生成

目标代码生成以源程序的中间表示形式作为输入,并把它映射到目标语言。

目标代码生成的一个重要任务是为程序使用的变量合理分配寄存器。

代码优化

为改进代码所进行的等级程序变换,使其运行得更快一些,占用空间更少一些,或者二者兼顾。

代码优化分为:

  • 机器无关代码优化:中间代码层面优化
  • 机器相关代码优化:目标代码层面优化

优化的方面:

  • 自动识别代码中的重复运算或冗余运算,并删除
  • 将代价较高的运算替换成代价较少的运算

语言及其文法

基本概念

字母表

是一个有穷符号集合。

符号:包括字母,数字,标点符号等

字母表上的运算:

  • 乘积
  • n次幂
  • 正闭包
  • 克林闭包:正闭包加上空串

串是字母表中符号的一个有穷序列。

串s的长度,通常记作|s|,指s中符号的个数。比如|abc|=3

空串的长度为0的串,用$\epsilon$表示,$|\epsilon|=0$

串上的运算:

  • 连接

x和y是串,x和y的连接,是把y附加到x后面而形成的串,记作xy

例如x=dog, y = house,那么xy=doghouse

空串是单元位。

  • $s^1= s^0 s = \epsilon s= s, s^2 = ss$

文法定义

文法的形式化定义:$G=(V_T,V_N,P,S)$

$V_T$:终结符集合

终结符:是文法所定义的语言的基本符号,有时也称token。

例如:$V_T={apple,boy,eat,little }$

$V_N$:非终结符集合

非终结符:是用来表示语法成分的符号,有时也称为“语法变量”

例如:$V_N={<句子>,<名词短语>,<动词短语>,<名词> …}$

注意:

  • 终结符集合和非终结符集合是不相交的
  • 终结符集合和非终结符集合并集为文法符号集

$P$:产生式集合

产生式:描述了将终结符和非终结符组合成串的方法,产生式的一般形式为:$\alpha \Rightarrow \beta$

读作:$\alpha$定义为$\beta$

$S$:开始符号

$S \in V_N$。开始符号:表示的是该文法中最大的语法成分。

例如:$S=<句子>$

产生式的简写:

对于有相同左部的$\alpha$的产生式:
$$
\alpha \Rightarrow \beta_1 \space\space \alpha \Rightarrow \beta_2 \space…\space \alpha \Rightarrow \beta_n
$$
可以简记为:
$$
\alpha \Rightarrow \beta_1 | \beta_2 | …|\beta_n
$$
例如:

符号约定:

总结:

语言的定义

推导

直接推导就是用产生式的右部替换产生式的左部。

比如:
$$
\alpha \Rightarrow \beta \
\gamma \alpha \delta \Rightarrow \gamma \beta \delta
$$
间接推导

比如:
$$
\alpha_0 \Rightarrow \alpha_1 \space \alpha_1 \Rightarrow \alpha_2 \space …. \space \alpha_{n-1} \Rightarrow \alpha_n \
\alpha_0 \Rightarrow^{n} \alpha_n
$$

规约

规约是推导的逆过程。

例如:

有了文法(语言规则),如何判断某一词串是否是该语言的句子:

  • 句子的推导:是否能够从文法推导出句子
  • 句子的规约:从该句子是否可以规约到文法的开始符号

句型和句子

如果$S \Rightarrow^ \alpha, \alpha \in (V_T \cup V_N)^$,则称$\alpha$是$G$的一个句型。$S$是句子的开始符号。

一个句型中既可以包含终结符,也可以包含非终结符,也可能是空串。

如果$S \Rightarrow^ w, w \in V_T^$,则称$w$是$G$的一个句子。

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

语言

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

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

例如:

其他S表示字母数字串,即有字母开头的,字母和数字组成的字符串。即变成语言中的标识符。

语言上的运算

例如:

令$L={A,B…,Z,a,b,..,z},D={0,1,…,9}$。则$L(L \cup D)^$表示的语言是标识符。注意,$$表示生成的串。$*$表示闭包运算。

文法分类

Chomsky文法分类体系:

  • 0型文法

    • 无限制文法/短语结构文法
    • $\forall \alpha \Rightarrow \beta \in P$,$\alpha$中至少包含1个非终结符
    • 由0型文法$G$生成的语言$L(G)$是0型语言
  • 1型文法

    • 又称上下文有关文法(CSG)
    • 满足0型文法的基础上,$\forall \alpha \Rightarrow \beta \in P$,$|\alpha| \leq |\beta|$
    • 产生式的一般形式:$\alpha_1 A \alpha_2 \Rightarrow \alpha_1 \beta \alpha_2, (\beta \neq \epsilon)$
    • CSG中不包含空产生式,即$ \epsilon $。证明:如果$\beta=\epsilon$,即$|\beta| =0$,而$\alpha$必须包含一个非终结符,所以$|\alpha| \geq 1$,与$|\beta|=0$矛盾。
    • 由上下文有关文法产生的语言称为上下文有关语言(1型语言)。
  • 2型文法

    • 上下文无关文法(CFG)
    • $\forall \alpha \Rightarrow \beta \in P$,$\alpha \in V_N$
    • 产生式的一般形式:$A \Rightarrow \beta$,$A$表示非终结符,即生成式的左部是一个非终结符,如下就是一个上下文无关文法的例子:

    image-20200508164608087

  • 3型文法

    • 又称正则文法(RG)
      • 右线性文法:$A \Rightarrow wB 或 A \Rightarrow w$,$A$表示非终结符,$w$表示终结符
      • 左线性文法:$A \Rightarrow Bw 或 A \Rightarrow w$
      • 左线性文法和右线性文法都称为正则文法
    • 由正则文法$G$生成的语言称为正则语言
    • 正则文法能描述程序设计语言的多数单词

四种文法的关系:

  • 逐级限制
  • 逐级包含

3型文法,一定是2型文法;2型文法,一定是1型文法;1型文法,一定是0型文法。反过来则不成立。

CFG(上下文无关文法)的分析树

正则文法可以描述程序语言中大多数单词,但是其生成能力有限, 它几乎描述不了程序设计语言中的句子构造。而上下文无关文法可以描述大部分程序设计语言中的语法构造,也是被研究得最多的一种文法。

分析树的定义:

  • 根节点的标号为文法开始符号
  • 内部节点表示对一个产生式$A \Rightarrow \beta$的应用,该节点的标号是此产生式左部$A$.该节点的子节点的标号从左到右构成了产生式的右部$\beta$
  • 叶节点的标号既可以是非终结符,也可以是终结符。从左到右排列叶节点得到的符号串是这颗树的产出或边缘。

image-20200508170439014

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

给定一个推导$S \Rightarrow \alpha_1 \Rightarrow \alpha_2 …\Rightarrow \alpha_n$,对于推导过程中得到的每一个句型$\alpha_i$都可以构造出一个边缘为$a_i$的分析树。

image-20200508172924163

(句型的)短语

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

如果子树只有父子两代结点,那么这颗子树的边缘称为该句型的一个直接短语(高度为2的子树的边缘)。

image-20200508193632350

直接短语一定是某个产生式的右部。

但产生式的右部不一定是给定句型的直接短语。

二义性文法

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

编译器希望不要遇到二义性,不然就无法执行。

image-20200508194456469

上面的句型可以通过文法可以表示成两棵分析树。这是由于else可以跟第一个if匹配,也可以跟第二if匹配。

所以消除二义性的规则是:每个else和最近的尚未匹配的if匹配。如果有了这条规定,上面句型的分析树就是唯一的了。

image-20200508194714825

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

满足:肯定无二义性

不满足:也未必就是有二义性。

词法分析

正则表达式

语言$L={a}{a,b}^({\epsilon} \cup ({.,}{a,b} {a,b}^))$

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

例如:$r=a(a|b)^(\epsilon | (.|-)(a|b)(a|b)^)$

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

定义

$\epsilon$是一个RE,$L(\epsilon) = {\epsilon }$

如果$\alpha \in \sum$,则$\alpha$是一个RE,$L(\alpha) = {\alpha}$

如果$r$和$s$都是RE,表示的语言分别是$L(r)$和$L(s)$,则:

  • $r|s$是一个RE,$L(r|s)=L(r) \cup L(s)$
  • $rs$是一个RE,$L(rs) = L(r)L(s)$
  • $r^$是一个RE,$L(r^)=(L(r))^*$
  • $(r)$是一个RE,$L((r))=L(r)$

运算优先级:$*$、连接,|

例子:

image-20200508204704315

例子:

C语言中无符号整数的RE:

十进制整数的RE:$(0|…|9)(0|…|9)^*|0$

八进制整数的RE:$0(1|…|7)(0|…|7)^*$

正则语言

可以用RE定义的语言,叫做正则语言或正则集合。

RE满足的代数定律:

image-20200508205232765

正则文法和正则表达式等级:

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

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

正则

正则定义具有如下形式的定义序列:

image-20200508211147930

其中:

  • 每个$d_i$都是一个新符号,它们都不在序列字母表$\sum$中,而且各不相同
  • 每个$r_i$是字母表$\sum \cup {d_1,d_2,…,d_{i-1}}$上的正则表达式

例子:

image-20200508210838380

image-20200508210850892

有穷自动机(FA)

有穷自动机有两位神经物理学家于1948年首先提出,是对一类处理系统简历的数学模式。

这类系统具有一系列离散的输入输出信息和有穷数目的内部状态(状态:概况了对过去输入信息处理的状况)。

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

FA的典型例子:

电梯控制装置:

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

FA模型

image-20200509125120172

FA由三部分组成:

  • 输入带:用来存储输入符号串
  • 读头:从做向右逐个读取输入符号,不能修改(只读),不能往返移动
  • 有穷控制器:具有有穷个状态数,根据当前的状态和当前输入符号控制转入下一个状态

FA表示

转换图:

  • 结点:FA的状态
    • 初始状态(开始状态):只有一个,有start箭头指向
    • 终止状态(接收状态):可以有多个,用双圈表示
  • 带有标记的有向边:如果对于输入a,存在一个从状态p到状态q的转换,就在p、q之间画一条有向边,并标记上a

image-20200509130042710

FA定义(接收)的语言

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

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

image-20200509150955233

最长子串匹配原则

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

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

image-20200509151248177

所以如果遇到<=符号,就会匹配成小于等于;如果遇到++符号,就会匹配成自增符号。

FA分类

  • 确定的FA(DFA)

  • 非确定的FA(NFA)

确定的有穷自动机(DFA)

$$
M = (S, \sum, \delta, s_0, F)
$$

$S$:有穷状态集

$\sum$ :输入字母表,即输入符号集合,假设$\epsilon$不是$\sum$中的元素

$\delta$:将$S \times \sum$映射到$S$的转换函数。$\forall s \in S, a \in \sum, \delta(s,a)$表示从状态$s$出发,沿着表示$a$的边所能到达的状态。

$s_0$:开始(或初始)状态,$s_0 \in S$

$F$:接受状态(或终止状态)集合,$F \subset S$

例子:

image-20200509152425899

$S = {0,1,2,3}$

$\sum = {a,b}$

$F={3}$

$s_0 = 0$

$\delta$可以用转换表表示

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

$$
M = (S, \sum, \delta, s_0, F)
$$

$S$:有穷状态集

$\sum$ :输入字母表,即输入符号集合,假设$\epsilon$不是$\sum$中的元素

$\delta$:将$S \times \sum$映射到$2^S$的转换函数。$\forall s \in S, a \in \sum, \delta(s,a)$表示从状态$s$出发,沿着表示$a$的边所能到达的状态集合

$s_0$:开始(或初始)状态,$s_0 \in S$

$F$:接受状态(或终止状态)集合,$F \subset

例子:

image-20200509152904280

$s_0 = 0$

$S= {0,1,2,3}$

$F={3}$

$\sum = {a, b}$

DFS和NFA的等价性

对于任何NFA,存在识别同一语言的DFA。

对于任何DFA,存在识别同一语言的NFA。

image-20200510095240335

带有$\epsilon$边的NFA

image-20200510100652361

带有和不带有”$\epsilon$-边”的 NFA的等价性:

image-20200510100741694

DFA算法实现

NFA比DFA更直观,但是DFA更容易实现。

输入:以文件结束符eof结尾的字符串x,DF的开始状态$s_0$,接受状态F,转换函数move

输出:如果D接受x,则回答“yes”,否则回答“No”

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

image-20200510101135283

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

image-20200510101814026

因为NFA比较直观,所以根据RE构建NFA比较容易。

又因为NFA和DFA等价,所以再根据NFA构造DFA。

先将RE转换成NFA,然后再从NFA转成DFA。

根据RE构造NFA:
image-20200510104154071

image-20200510104207824

例子:$r=(a|b)^*abb$对应的NFA

image-20200510104259359

从NFA到DFA

例子:

image-20200510104810148

image-20200510105240112

子集构造法

输入:NFA
输出:接收相同语言的DFA

方法:

image-20200510114605955

image-20200510115300043

识别单词的DFA

标识符的DFA

image-20200510115550338

无符号数的DFA

image-20200510115650316

因为NFA存在空边”$\epsilon $”,所以将NFA转换成DFA:

image-20200510120629577

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

image-20200510120727145

识别注释的DFA

image-20200510142715112

识别Token的DFA

识别各类符号。

image-20200510142819794

词法分析阶段的错误处理

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

  • 单词拼写错误:int i = 0x3G;
  • 非法字符:~@

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

错误处理:

  • 查找已扫描字符串中最后一个车对应于某终态的字符
    • 如果找到了,将该字符与前面的字符识别成一个单词。然后将输入指针退回到该字符,扫描器重新回到初始状态,继续识别下一个单词
    • 如果没找到,则确定出错,采用错误恢复策略

错误恢复策略:

最简单的错误恢复策略:恐慌模式恢复

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

语法分析

自顶向下分析概述

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

可以看成是从文法开始符号$S$推导出词串$w$的过程:

image-20200510143819079

每一步推导中,都需要做两个选择:

  • 替换当前句型中的哪个非终结符
  • 用该非终结符的哪个候选式进行替换

最左推导

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

image-20200510144156287

如果$S \Rightarrow^*_{lm} \alpha$,则称$\alpha$是当前文法的最左句型。

最右推导

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

image-20200510144343503

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

最左推导和最右推导的唯一性

给定分析树,推导可能不是唯一的,因为我们选择中间任意一个非终结符进行替换。但是每棵分析树对应的最左推导和最右推导是唯一的。

image-20200510144826925

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

由于分析器都是从左到右的扫描字符串,所以自动向下的语法分析采用最左推导的方式。

  • 总是选择每个句型的最左非终结符进行替换
  • 根据输入流中的下一个终结符,选择最左非终结符的一个候选式

例子:

image-20200510145052277

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

递归下降分析:

  • 由一组过程组成,每个过程对应一个非终结符
  • 从文法开始符号$S$对应的过程开始,其中递归调用文法中其他非终结符对应的过程。如果$S$对应的过程体恰好扫面了整个输入串,则更成功完成语法分析。

image-20200510145346504

需要回溯的分析器,称为不确定分析器。

如果在分析的过程中,预测出正确的产生式,就不需要回溯,这种分析叫做预测分析。

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

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

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

文法转换

存在的问题

  • 同一非终结符的多个候选式存在相同前缀,将导致回溯现象。

比如:$S \Rightarrow aAd | aBe$

  • 左递归文法会使递归下降分析器陷入无限循环

image-20200510150629931

消除直接左递归

image-20200510151001684

$A \rightarrow A\alpha$是一个左递归文法,由于其对应的正则表示为$r= \beta \alpha^*$,所以可以转换成对应的非递归文法:
$$
A \rightarrow \beta A^\prime \
A^\prime \rightarrow \alpha A^\prime | \epsilon
$$
事实上,这种消除的过程就是吧左递归转换成了右递归。

例子:

image-20200510151651151

一般形式:

image-20200510151633396

消除左递归是要付出代价的——引进一些非终结符和$\epsilon$_产生式

消除间接左递归

image-20200510151805416

具体算法:

输入:不含循环推导和$\epsilon-$产生式的文法$G$

输出:等价的无左递归文法

方法:

image-20200510152057713

提取左公因子

对于存在公共前缀的产生式:

image-20200510152324062

提取左公因子算法:

输入:文法$G$

输出:等价的提取了左公因子的文法

方法:

image-20200510152409034

LL(1)文法

递归下降分析,可能遇到回溯,回溯会影响分析器的效率。如果每步可以预测出正确的选择,就不需要回溯,这种分析称为预测分析。

什么样的文法可以采用预测分析呢?就是下面介绍的LL(1)文法。

S_文法

预测分析发的工作郭广昌:

  • 从文法开始符号出发,在每一步推导过程中根据当前句型的最左非终结符$A$和当前输入符号$\alpha$,选择正确的$A$-产生式。为保证分析的确定性,选出的候选式必须是唯一的。

S_文法(简单的确定性文法)满足:

  • 每个产生式的右部都以终结符开始
  • 同一非终结符的各个候选式的首终符都不同

S_文法中不包含$\epsilon$产生式

例子:对于包含$\epsilon$产生式的文法

image-20200510155556458

什么时候使用$\epsilon$产生式?

如果当前某非终结符$A$与当前的输入符$a$不匹配时,若存在$A \rightarrow \epsilon$,可以通过检查$a$是否可以出现在$A$的后面,来决定是否使用产生式$A \rightarrow \epsilon$。(若文法中无$A \rightarrow \epsilon$,则应报错)。

非终结符的后继符号集

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

可能在某个句型中紧跟在$A$后边的终结符$a$的集合,记为$FOLLOW(A), FOLLOW(A) = {a|S \Rightarrow^ aAa\beta, a \in V_T, a,\beta \in (V_T \cup V_N)^ }$

如果$A$是某个句型的最右符号,则将结束符添加到$FOLLOW(A)$中

image-20200510160542843

产生式可选集

产生式$A \rightarrow \beta$的可选集是指可以选用该产生式进行推导时对应的输入符号的集合,记为$SELECT(A \rightarrow \beta)$

  • $SELECT(A \rightarrow \alpha \beta) = {\alpha}$
  • $SELECT(A \rightarrow \epsilon) = FOLLOW(A)$

q_文法:

  • 每个产生式的右部或为$\epsilon$,或以终结符开始
  • 具有相同左部的产生式有不相交的可选集

q_文法不含右部以非终结符打头的产生式

串首终结符集

串首终结符:串首第一个符号,并且是终结符。简称首终结符。

给定一个文法符号串$\alpha$,$\alpha$串首终结符集$FIRST(\alpha)$被定义为可以从$\alpha$推导出的所有串首终结符构成的集合。如果$\alpha \Rightarrow^* \epsilon$,那么$\epsilon$也在$FRRST(\alpha)$中。

  • 对于$\forall \alpha \in (V_T \cup V_N)^+, FIRST(\alpha) = {\alpha | \alpha \Rightarrow \alpha \beta, \alpha \in V_T, \beta \in (V_T \cup V_N)^*}$;
  • 如果$\alpha \Rightarrow \epsilon$,那么$\epsilon \in FIRST(\alpha)$

产生式$A \rightarrow \alpha$的可选集$SELECT$

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

注意:$\Rightarrow ^*$表示通过$n >= 0$步推导;$\Rightarrow ^ +$表示通过$n>0$推导

LL(1)文法

文法$G$是$LL(1)$的,当且仅当$G$的任意两个具有相同左部的产生式$A \rightarrow \alpha | \beta$满足下面的条件:

  • 如果$\alpha$和$\beta$均不能推导出$\epsilon$,则$FIRST(\alpha) \cup FIRST(\beta) = \Phi$
  • $\alpha$和$\beta$至多有一个能推导出$\epsilon$
  • 如果$\beta \Rightarrow ^ * \epsilon$,则$FIRST(\alpha) \cup FOLLOW(A) = \Phi$
  • 如果$\alpha \Rightarrow ^ * \epsilon$,则$FIRST(\beta) \cap FOLLOW(A) = \Phi$

最后两个条件,可以保证同一非终结符的各个产生式的可选集互不相交。

因此,可以为$LL(1)$文法构造预测分析器。

第一个$L$表示从左向右扫描输入

第二个$L$表示产生最左推导

$1$表示在每一步中只需要向前看一个输入符号来决定语法分析动作

FIRST集和FOLLOW集的计算

FIRST计算

$FIRST(X)$:可以从$X$推导出的所有串首终结符所构成的集合。

如果$X \Rightarrow ^* \epsilon$,那么$\epsilon \in FIRST(X)$

例子:

image-20200511100600620

算法:

image-20200511100739781

计算串$X_1 X_2 … X_n$的$FIRST$集合

image-20200511101005809

FOLLOW集计算

$FOLLOW(A)$:可能在某个句型中紧跟在$A$后面的终结符$a$的集合。$FOLLOW(A = {a | S \Rightarrow ^ \alpha A \alpha \beta, \alpha \in V_T, \alpha, \beta \in (V_T \cup V_N)^})$

如果$A$是某个句型的最右符号,则将结束符添加到$FOLLOW(a)$中

例子:

image-20200511102001166

算法:

image-20200511102635190

例子:表达式文法各产生式的$SELECT$集

image-20200511103023304

因为所有具有相同左部的产生式的$SELECT$集不相交,则该表示文法是$LL(1)$文法。

根据$SELECT$集得到的预测分析表:

image-20200511104328127

$LL(1)$文法的分析方法:

  • 递归的预测分析发
  • 非递归的预测分析法

递归预测分析法

递归的预测分析法是指:在递归下降分析中,编写每一个非终结符对应的过程时,根据预测分析表进行产生式的选择。

根据每个非终结符的产生式和$LL(1)$文法的预测分析表,为每个非终结符编写对应的过程:

image-20200511125006810

非递归预测分析法

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

image-20200511131205695

例子:

$L={a^n b^n | n >=1}$

首先遇到遇到$a$,直接将$a$压入栈中。直到遇到$b$开始,就从栈中弹出$a$,每来一个$b$就弹出一个$a$,直到栈为空,此时就会满足$a$的个数和$b$的个数相同。

image-20200511131651613

首先栈初始化为开始符号,根据栈顶符号和输入符号的开始符号,以及预测分析表,我们将$E$弹出栈,将$TE^ \prime$压入栈中。

然后,栈顶元素为$T$,并且输入开始符号为$id$, 因此将$T$弹出栈,将$FT^\prime$压入栈中。

其次,根据栈顶元素$F$和输入的开始符号为$id$,因此将$F$弹出栈,将$id$压入栈中。

发现栈顶元素和输入的开始符号相等,所以将id淡出栈,并将输入指针向后移动。

一直重复以上步骤。得到上图的右侧分析。

输出的序列就是一个最左推导。

表驱动的预测分析法:

输入:一个串$w$和文法$G$的 分析表$M$

输出:如果$w$在$L(G)$中,输出$w$的最左推导;否则给出错误提示

方法:最初,语法分析器的格局如下:输入缓冲区中是w$,$G$的开始符号位于栈顶,其下面是$。下面的程序使用预测分析表$M$生成了处理这个输入的预测分析过程:

image-20200511132902835

递归预测分析法和非递归预测分析法的区别:

image-20200511133109864

预测分析法的实现步骤:

  • 构造文法
  • 改造文法:消除二义性,消除左递归,消除回溯
  • 求每个变量的$FIRST$和$SELECT$集,从而求得每个候选式的$sELECT$集
  • 检查是不是$LL(1)$文法,若是,构造预测分析表
  • 对于递归的预测分析,根据预测分析表为每一个非终结符编写一个过程;对于非递归的预测分析,实现表驱动的预测分析算法。

预测分析中的错误检测

两种情况下可以检测到错误:

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

预测分析中的错误恢复:

恐慌模式:

  • 忽略输入中的一些符号,直到输入中出现由设计者选定的同步词法单元集合中的某个词法单元
    • 其效果依赖于同步集合的选取。集合的选取应该使得语法分析器能从实际遇到的错误中快速恢复
    • 例如可以把$FOLLOW(A)$中的所有终结符放入非终结符$A$的同步记号集合
  • 如果终结符在栈顶而不能匹配,一个简单的办法就是弹出此终结符

image-20200511143057864

分析表的使用方法:

  • 如果$M[A,a]$是空,表示检测到错误,根据恐慌模式,忽略输入符号$a$
  • 如果$M[A, a]$是$synch$,则弹出栈顶的非终结符$A$,试图继续分析后面的语法成分
  • 如果栈顶的终结符和输入符号不匹配,则弹出栈顶的终结符

image-20200511143323782

自底向上分析概述

  • 分析树的底部(叶结点)向顶部(根结点)方向构造分析树
  • 可以看成将输入串$w$规约为文法开始符号$S$的过程
  • 自顶向下的语法分析采用最左推导方式
  • 自底向上的语法分析采用最右规约的方式(反向构造最右推导)
  • 自底向上语法分析的通用看人家
    • 移入-规约分析

例子:移入-规约分析

image-20200511143939647

image-20200511144340728

移入-规约分析的工作过程:

  • 对输入串的一次从左到右的扫描过程中,语法分析器将零个或多个输入符号移入到栈的顶端,直到它可以对栈顶的一个文法符号串$\beta$进行规约为止
  • 然后,它将$\beta$规约为某个产生式的左部
  • 语法分析器不断地重复这个循环,直到它检测到一个语法错误,或者栈中包含了开始符号且输入缓冲区为空为止。

移入-规约分析器可采用的4种动作:

  • 移入
  • 规约
  • 接受:宣布语法分析过程成功完成
  • 报错:发现一个语法错误,并调用错误恢复子程序

移入-规约分析器存在的问题:

image-20200511145557054

上图中的红线,应该被识别为一个整体,并规约为$$。而上图中却将$i_B$识别为一个字符串,并规约为$$。

错误的原因:错误地识别了句柄

句柄:句型的最左直接短语

image-20200511145911875

LR分析法概述

LR文法是最大的、可以构造出相应移入-规约语法分析器的文法类:

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

$LR(k)$分析:

需要向前查看$k$个输入符号的$LR$分析。

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

基本原理

自底向上分析的关键问题是:如何正确识别句柄。

句柄是逐步形成的,用”状态”表示矩形识别exe进展程度。

image-20200511152217270

$LR$分析器基于这样一些状态来构造自动机进行句柄识别。

$LR$自动机总体结构:
image-20200511152339433

例子:

image-20200511152852447

LR分析器的工作过程

初始化:

image-20200511161018159

一般情况下:

image-20200511161037267

  • 如果$ACTION[s_m, a_i] = sx$,那么格局变为:

image-20200511161120275

  • 如果$ACTION[s_m, a_i] = rx$表示用第$x$个产生式$A \rightarrow X_{m-(k-1)}… X_m$进行规约,那么格局变为:

image-20200511161238525

  • 如果$GOTO[s_{m-k}, A] = y$,那么格局变为:

image-20200511161331126

  • 如果$ACTION[s_m, a_i] = acc$,那么分析成功
  • 如果$ACTION[s_m, a_i] = err$,那么出现语法错误

LR分析算法:

输入:串$w$和LR语法分析表,该表描述了文法$G$的ACTION函数和GOTO函数

输出:如果$w$在$L(G)$中,则输出$w$的自底向上语法分析过程中的规约步骤;否则给出一个错误指示

方法:初始时,语法分析器中的内容为初始状态$s_0$,输入缓冲区的内容为:$w$$,然后,语法分析器执行下面的程序:

image-20200511153452496

构造$LR$分析表的方法:

  • LR(0)分析
  • SLR分析
  • LR(1)分析
  • LALR分析

LR(0)分析

LR(0)项目:右部某位置有圆点的产生式称为相应文法的一个$LR(0)$项目(简称项目)
$$
A \rightarrow a_1 . a_2
$$
image-20200511162316794

增广文法:如果$G$是一个以$S$为开始符号的文法,则$G$的增广文法$G ^\prime$就是在$G$中加上新开始符号$S^\prime$和产生式$S^\prime \rightarrow S$而得到的文法。

例如:

image-20200511162703912

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

文法中的项目:

image-20200511162806324

开始的项目是初始项目,最终的项目是规约项目

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

$A \rightarrow \alpha . X\beta$的后继项目是$A \rightarrow \alpha X .\beta$

每一个项目对应着句柄识别的一个状态,把所有项目作为自动机的状态的话,会导致自动机的状态过于庞大。

那么这些项目中是否存在一些等价的呢?

上面的(0)和(2)等价,(3)(7)和(11)等价,(5)和(13)等价。

当项目中圆点后面是一个非终结符的时候,就存在等价项目。

可以把等价的项目组成一个项目集($I$),称为项目集闭包,每个项目集闭包对应这自动机的一个状态。

例子:LR(0)自动机

image-20200511163607090

首先把初始项目放入初始状态($I_0$)中,并且四个构造一个项目集闭包。

然后计算后继项目。状态$I_1$已经是规约状态,所以不会有后继状态。状态$I_2,I_4, I_3$都是中间项目,继续计算后继项目。一直重复直到所有状态到达规约状态。

根据左侧转换图来构造分析表。

sn:n表示状态,即$I$的下标

rm:m表示所用的生成式,即文法中()中的数字

LR(0)分析表构造算法

CLOSURE()函数:计算给定项目集$I$的闭包

image-20200512090031072

GOTO()函数:计算项目集$I$对应文法符号$X$的后继项目集闭包。

image-20200512090042758

构造$LR(0)$自动机的状态集:

image-20200512090217925

$LR(0)$分析表构造算法:

image-20200512090743083

$LR(0)$自动机的形式化定义

文法:$G=(V_N, V_T, P, S)$

$LR(0)$自动机:$M=(C, V_N \cup V_T, GOTO, I_), F$

image-20200512091024575

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

image-20200512091057805

状态$I_2$存在冲突。$E \rightarrow T.$表示进行规约操作,而$T \rightarrow T . F$表示进行移入操作,将$$移入栈中。所以存在移入/规约冲突

状态$I_9$类似。

image-20200512091514495

还有一种规约/归约冲突

例子:移入/规约冲突和归约/归约冲突

image-20200512091819178

SLR分析

例子:$LR(0)$分析过程中的冲突

image-20200512091057805

$LR(0)$没有向前查看符号,没有考虑文法符号的上下文环境。

SLR分析基本思想:

image-20200514143755112

也称为$SLR(1)$方法,因为向前查看了一个符号,但是之前提到过如果等于1,可以省略,S表示简单simple,通过$FOLLOW$集就可以解决冲突,后面会讲解有些冲突需要更复杂的方式化简。

开始例子的SLR分析表:

image-20200514144217756

SLR分析表构造算法:

image-20200514144406272

与$LR(0)$分析算法类似,唯一的不同就是对规约项目的处理上。

如果给定文法的$SLR$分析表中不存在有冲突的动作,那么该文法称为$SLR$文法

$SLR$分析中的冲突:

image-20200514144558923

对于状态$I_2$,第一个项目表示,如果下一个符号是$=$,移入动作,将等号移入栈中,进行状态6.

而第二项目表示,遇到$R$的$FOLLOR$集的时候,将栈顶的$L$规约为$R$。

所以遇到等号时,会存在移入\规约冲突。

LR(1)分析

$SLR$分析存在的问题:

$SLR$只是简单地考察下一个输入符号$b$是否属于与规约项目$A \rightarrow \alpha$相关联的$FOLLOW(A)$,但$b \in FOLLOW(A)$只是规约$\alpha$的一个必要条件,而非充分条件。

对于产生式$A \rightarrow \alpha$的规约,在不同使用位置,$A$会要求不同使用位置,$A$会要求不同的后继符号。

image-20200514152143495

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

规范$LR(1)$项目:

将一般形式为$[A \rightarrow \alpha . \beta, a ]$的项称为$LR(1)$项,其中$A \rightarrow \alpha\beta$是一个产生式,$a$是一个终结符(这里将$视为一个特殊的终结符),他表示在当前状态下,A后面必须紧跟的终结符,称为该项的展望符。

  • LR(1)中的1指的是项的第二分量的长度
  • 在形如$[A \rightarrow \alpha . \beta, a]$且$\beta \neq \epsilon$的项中,展望符$a$没有任何作用
  • 但是一个形如$[A \rightarrow \alpha ., a]$的项只有在下一个输入符号等于$a$时才能以按照$A \rightarrow \alpha$进行规约
    • 这样的$a$的集合总是$FOLLOW(A)$的子集,而且他通常是一个真子集

LR(1)的等价项目:

image-20200514161142318

例子:LR(1)

转换图:

image-20200514153425448

分析表:

image-20200514153806088

如果除展望符外,两个$LR(1)$项目集是相同的,则称这两个$LR(a)$项目集是同心的

LALR分析法

$LR(1)$自动机中存在一些同心项目集,$LR(1)$根据展望符的不同,将原始的$LR(0)$项目进行分裂。这样就使得$LR(1)$中的状态数较$LR(0)$多了很多。比如C语言的语法,$LR(0)$分析表只有几百个状态,而$LR(1)$分析表则有上千个状态。

为了使$LR(1)$技术实用化,就需要需要想办法减少状态数。

LALR(lookahead-LR)分析的基本思想

寻找具有相同核心的$LR(a)$项集,并将这些项集并为一个项目集。所谓项集的核心就是其第一分量的集合。

然后根据合并后得到的项集族构造语法分析表

如果分析表中没有语法分析动作冲突,给定的文法就称为$LALR(1)$文法,就可以根据该分析表进行语法分析。

合并同心项集:

image-20200518100542173

image-20200518100655214

合并同心项集时产生规约-规约冲突的例子:

image-20200518100916852

合并同心项集不会产生移进-规约冲突,这是因为合并同心集,实际上合并的是对应项的展望符,而展望符只在规约的时候起作用,对于移进的时候不起作用的。

合并同心项集后,虽然不产生冲突,但可能会推迟错误的发现:

image-20200518101430032

状态$I_4$和状态$I_9$是同心的,因此可以合并。

但是如果输入是一个d$,而在会出现错误,只是推迟了两步。

LALR的特点

形式上与$LR(1)$相同

大小上与$LR(0)$和$SLR$相当的

分析能力介于$SLR$和$LR(1)$二者之间

合并后的展望符集合仍为$FOLLOW$集的子集

二义性文法的LR分析

二义性文法的特点:

  • 每个二义性文法都不是LR的
  • 某些类型的二义性文法在语言的描述和实现中很有用
    • 二义性文法比非二义性文法更简短,更自然

image-20200518103311338

应该保守地使用二义性文法,并且必须在严格控制之下使用,因为稍有不慎机会导致语法分析器识别的语言出现偏差。

LR分析中的错误处理

语法错误的检测:当LR分析器在查询分析表并发现一个报错条目时,就检测到了一个语法错误

错误恢复策略:

  • 恐慌模式错误恢复
  • 短语层次错误恢复

恐慌模式错误恢复:

image-20200518110525787

短语层次错误恢复:

  • 检查LR分析表中的每一条报错条目,并根据语言的使用方法来决定程序员所犯的何种错误最右可能引起这个语法错误
  • 然后构造出适当的恢复过程

语法制导翻译概述

image-20200518110742089

语法制导翻译的基本思想:

如何表示语义信息?

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

如何计算语义属性?

  • 文法符号的语义属性值是用文法符号所在产生式(语法规则)相关联的语义规则来计算的。
  • 对于给定的输入串x,构造x的语法分析树,并利用与产生式(语法规则)相关联的语义规则来计算分析树中各结点对应的语义属性值

将语义规则同语法规则(产生式)联系起来要设计两个概念:

  • 语法制导定义(SDD)
  • 语法制导翻译方案(SDT)

语法制导定义(SDD):

SDD是对CGF(上下文无关文法)的推广

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

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

例如:

image-20200518133849440

语法制导翻译方案(SDT):

SDT是在产生式右部嵌入了程序片段的CFG,这些程序片段称为语义动作。按照惯例,语义动作放在花括号内:

image-20200518134001088

一个语义动作在产生式中的位置决定了这个动作的执行时间。

SDD与SDT的区别:

  • SDD
    • 是关于语言翻译的高层次规格说明
    • 隐蔽了许多具体实现细节,使用户不必显式地说明翻译发生的顺序
  • SDT
    • 可以看作是对SDD的一种补充,是SDD的具体实施方案
    • 显式地指明了语义规则的计算顺序,以便说明某些实现细节

语法制导定义SDD

文法符号的属性:

  • 综合属性
  • 继承属性

综合属性

在分析树结点N上的非终结符A的综合属性只能通过N的子结点或N本身的属性值来定义。

image-20200521102004908

终结符可以具有综合属性。终结符的综合属性值是由词法分析器提供的词法值,因此在SDD中没有计算终结符属性值的语义规则。

继承属性

在分析树结点N上的非终结符A的继承属性只能通过N的父结点,N的兄弟结点或N本身的属性值来定义。

image-20200521102350471

终结符没有继承属性。终结符从词法分析器处获得的属性值被归为综合属性值。

例子:带有综合属性的SDD

例子:带有继承属性L.inh的SDD

image-20200521102915480

比如int a, b, c,通过这个分析树,就可以得到a,b,c的类型都为int

属性文法

一个没有副作用的SDD有时也称为属性文法。

属性文法的规则仅仅通过其他属性值和常量来定义一个属性值。

例如:

image-20200521104402066

SDD的求值顺序

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

按照什么顺序计算属性值?

语义规则建立了属性之间的依赖关系,在对语法分析树结点的一个属性求值之前,必须首先求出这个属性值所依赖的所有属性值。

所有属性的依赖关系由依赖图描述。

依赖图

  • 依赖图是一个描述了分析树中结点属性间依赖关系的有向图
  • 分析树中每个标号为X的结点的每个属性a都对应着依赖图中的一个结点
  • 如果属性X.a的值依赖于属性Y.b的值,则依赖图中有一条从Y.b的结点指向X.a的结点的有向边

例子:

image-20200521142101208

综合属性type放在结点的右侧,继承属性in放在结点的左侧。

属性值的计算顺序:

可行的求值顺序是满足下列条件的结点序列$N_1,N_2, …, N_k$:如果依赖图中有一条从结点$N_i$到$N_j$的边($N_i \rightarrow N_j$),那么$i < j$(即:在结点序列中,$N_i$排在$N_j$前面)。

这样的排序将一个有向图边变成了一个线性排序,这个排序称为这个图的拓扑排序

例子:

image-20200521142610030

zxp wechat
欢迎关注微信公众号!