编译原理-笔记

Posted on | In , | Visitors:

编译原理 笔记

引言

语言

分类

  • 面向机器
    • 机器语言：最基本的计算机语言
    • 汇编语言：用符号表示的指令的集合
  • 面向人类
    • 通用程序设计语言
      • 演变：过程->模块（抽象数据类型、ADT）->类
      • 共同特点：声明+操作
        • 声明：提供所操作对象的性质，生成相应的环境，一般是配置存储空间
        • 操作：确定操作的计算次序【过程头+过程体】，生成可执行的代码序列
    • 数据查询语言
    • 形式化描述语言E:E'+'E|E'*'E|id，核心部分是基于数学基础的产生式，例如：YACC

按照范型划分的程序设计语言

  • 过程式语言、面向对象语言
  • 函数语言：递归特性，如Lisp
  • 说明性、非算法式语言：浓厚的数学特征，如：LEX/YACC、SQL
  • 脚本式语言：仅是一种安排，没有复杂的逻辑关系，如：shell语言

语言之间的翻译

汇编语言->机器语言：汇编（如果是A2到M1这种叫交叉汇编）

程序设计语言->汇编语言或机器指令：编译（或解释）

高级语言之间：转换（或预编译）

逆向：反汇编、反编译

编译器与解释器

编译器：

解释器：

特点

编译器：

  • 工作效率高（目标程序运行效率高），即时间快，空间省
  • 交互性与动态性差、可移植性差

解释器：

  • 工作效率低，即时间慢（但是执行时间快，总时间慢）、空间费
  • 交互性与动态性好、可移植性好
    • 数据对象的类型可以动态改变，并允许用户对源程序进行修改，且提供较好的出错诊断，从而为用户提供了交互式的跟踪调试功能【数据库中的动态查询语句】
    • 解释器也是用某种程序语言编写的，因此，只要对解释器进行重新编译，就可使解释器执行在不同环境中，如Java虚拟机

主要区别：

运行目标程序时的控制权在解释器而不在目标程序

工作过程

词法分析

输入是源程序，输出是记号流

根据词法规则识别出源程序中的各个记号；每个记号代表一个单词；线性

  • 关键字/保留字
  • 标识符：即类型名、变量名、过程名、常量名等
  • 字面量
    • 数字字面量
    • 字符串字面量
  • 特殊符号
    • 运算符
    • 分隔符，", '

语法分析

输入是词法器返回的记号流，输出语法树

根据语法规则识别出记号流中的结构，并构造出一颗能够正确反映该结构的语法树（一般采用二叉树）

语义分析

根据语法分析器构造的语法树，进行适当的语义处理

例如：类型检查和转换等，其目的在于保证语法正确的结构在语义上也是合法的

声明性语句：将相应的环境信息记录在符号表中

操作性语句：提供符号表中的信息判断各操作数是否合法

中间代码生成（可选）

对语法树进行遍历，并生成可以顺序执行的中间代码序列

最常用的形式是四元式(序号)(op操作符/算符, arg1左操作数, arg2右操作数, result结果)，也是三地址码

操作数：算子

在此之前，解释器和编译器仍然是相同的

中间代码优化（可选）

局部优化、循环优化、全局优化等；

等价变换：变换前后的指令序列完成同样的功能，但在占用的空间上和程序执行的时间上都更省、更有效

目标代码生成

不同形式：汇编语言形式（还需要再进行一次汇编）、可重定位二进制代码形式【相对寻址】、内存形式（Load-and-Go，编译后马上运行，运行一次就需要编译一次）;

符号表管理

甚至要保留到程序的运行阶段

出错处理

动态错误：逻辑错误/动态语义错误，如除以0，数组下标越界等

静态错误：又分为语法错误和静态语义错误

​ 语法错误：语言结构上的错误，如单词拼错、缺少操作数，begin和end不匹配等

​ 静态语义错误：语言意义上的错误，如前后类型不一致，参数不匹配

工作模式

前端：语言结构和意义的分析，输出与机器无关

后端：综合；语言意义处理

中间代码：前端与后端的分界

划分有利于编译器的开发、维护与移植

扫描

每个阶段将程序完整分析一遍的工作模式称为一遍扫描

原理上希望扫描的遍数越少越好，则需要

  • 编译器具有足够大的空间
  • 语言的设计上和编译技术上提供支持

词法分析

编译器中唯一与源程序打交道的部分；规定所有合法输入+识别合法输入

任务：

  1. 滤掉源程序中的无用成分，如注释、空格、回车等
  2. 处理与具体平台有关的输入，如文件结束符的不同表示等
  3. 根据模式识别记号，并交给语法分析器【主要任务】
  4. 调用符号表管理器或出错处理器，进行相关处理

工作方式：

  1. 单独一遍扫描，输出记号流
  2. 作为语法分析器的子程序，通过词法分析器的调用，然后返回记号
  3. 与语法分析器并行工作的模式，以生产/消费的形式并行工作，通过队列存放已生产的“记号”

词法

词法的双重含义：

  • 规定单词形成的规则，也被称为构词规则或词法规则
    • 作用相当于立法，规定什么样的输入序列是语言所允许的合法单词
  • 根据构词规则识别输入序列，也被称为词法序列
    • 作用相当于执法，根据规则识别出合法的单词和指出非法的输入序列

模式pattern：产生和识别元素的规则

记号token：按照某个模式（或规则）识别出的元素（一组），包含记号的类别和记号的值

单词lexeme：被识别出的元素自身的值（一个），也称为词值

字典：预先定义且内容不变的记号表

基本分类

  • 关键字/保留字kw(key word/reserved word)
  • 标识符id(identifier)
  • 字面量literal
    • 常数字面量
      • 整型、实型、枚举
    • 字符串字面量
  • 特殊符号ks(key symbol/special symbol)
    • 运算符
    • 分隔符，例如"，'

模式的形式化描述

语言L是有限字母表∑上有限长度字符串的集合

字符串

基本概念：

表示/术语 意义
$\ S\ $ 字符串的长度
$ε$ $\ ε\ =0$
S1S2 字符串的连接
$S^n$ 连续n个S的连接
S的前缀X “abc”的前缀可以是：$ε, a, ab, abc$
S的后缀X “abc”的后缀可以是：$ε, c, bc, abc$
S的子串X “abc”的子串可以是：$ε, a, b, c, …$
S的真前缀 X是S的前缀，并且具有性质：$X!=S\ and\ \ X\ >0$
S的真后缀 X是S的后缀，并且具有性质：$X!=S\ and\ \ X\ >0$
S的真子串 X是S的真子串，并且具有性质：$X!=S\ and\ \ X\ >0$
S的子序列X S中去掉0或若干个不一定连续的字符后形成的字符串

集合操作：

表示、术语 意义
$\phi$ 空集合，即元素个数为0的集合
$\{ε\}$ 空串作为唯一元素的集合
$X=L∪M$ X是集合L和M的并: $X={s\ s∈L or s∈M }$
$X=L∩M$ X是集合L和M的交: $X={s\ s∈L and s∈M}$
$X=LM$ X是集合L和M的连接: $X={st\ s∈L and t∈M}$
$X=L-M$ X是集合L和M的差: $X={s\ s∈L and s not∈ M}$
$X=L^*$ X是集合L和M的(星)闭包: $X=L^0∪L^1∪L^2∪…$，其中$L^0=\{ε\}​$
$X=L^+$ X是集合L和M的正闭包: $X=L^1∪L^2∪L^3∪…$

正规式

$记号=正规式$，读作：记号定义为正规式或者记号是正规式

令Σ是一个有限字母表，则Σ上的正规式及其表示的集合递归定义如下:

  1. ε是正规式，它表示集合$L(ε)={ε}$
  4. 若a是Σ上的字符，则a是正规式，它表示集合L(a)=${a}$
  5. 若正规式r和s分别表示集合L(r)和L(s)，则

（a） $r|s$是正规式，表示集合$L(r)∪L(s)$

（b） $rs$是正规式，表示集合$L(r)L(s)$

（c） $r^$是正规式，表示集合$(L(r))^$，

（d）$(r)$是正规式，表示的集合仍然是$L(r)$【加括弧改变优先级、结合性】

可用正规式描述的语言称为正规语言或正规集

优先级：（从高到低顺序排列为）闭包运算、连接运算、或运算

结合性：三种运算均具有左结合性质

正规集是一个集合，而正规式是表示正规集的一种方法

不同正规式也可以表示同一个正规集，即正规式与正规集之间是多对一的关系

若正规式P和Q表示了同一个正规集，则称P和Q是等价的，记为P=Q

代数性质：

$r s=s r$ $(rs)t=r(st)$
$r (s t)=(r s) t$ $εr=rε=r$
$r(s t)=rs rt$ $r^*=(r^+ ε)$
$(s t)r=sr tr$ $r^{*}=r^$

其它：

  • 可缺省，$r?=r|ε​$，因为ε不可以用键盘直接键入，？与*具有相同的运算优先级
  • 字符组[r]，有两种形式
    • 枚举，如$[abc]=a|b|c$
    • 分段，如$[0-9a-z]$，注意左边界小于右边界
  • 非字符组$[$^$r]=\sum-L(r)$
  • 串，”r”，用来避免与正规式中运算符的冲突
  • 辅助定义式：名字=正规式，是为复杂的或重复出现的正规式命名，并在以后的使用中用名字代替正规式

char = [a-zA-Z]

digit =[0-9]
digits =$digit^+$

optional_fraction =(.digits)?

optional_exponent =(E(+|-)?digits)?

id =char(char|digit)*

num =digits optional_fraction optional_exponent

有限自动机

所谓有限，是指自动机的状态数是有限的

NFA

NFA: Nondeterministic Finite Automaton不确定的有限自动机

NFA是一个五元组（5-tuple）：
M =（S，∑，move，$s_0$，F），其中
（1） S是有限个状态（state）的集合；
（2） ∑是有限个输入字符（包括ε）的集合；
（3） move是一个状态转移函数，move($s_i$，ch)=$s_j$表示，当前状态$s_i$下若遇到输入字符ch，则转移到状态$s_j$；
（4）$s_0$是唯一的初态（也称开始状态）；
（5） F是终态集（也称接受状态集），它是S的子集，包含了所有的终态

表示方式
状态转换图

用一个有向图来直观表示NFA

  • NFA中的每个状态，对应转换图中的一个节点
  • NFA中的每个move(si, a)=sj，对应转换图中的一条有向边
  • 需满足最长匹配原则

初态：除去环后没有前驱的节点

状态转换矩阵

用一个矩阵来直观表示NFA

矩阵中，状态对应行，字符对应列

一般矩阵第一行所对应的状态为初态，而终态需要特别指出

识别记号的特点

具有不确定性，即在当前状态下对同一字符有多于一个的下一状态转移

具体体现：

  • （定义）move函数是1对多的
  • （状态转移图）同一状态有多于一条边标记相同字符转移到不同的状态
  • （状态转移矩阵）M[si, a]是一个状态的集合
方法与问题

方法：反复试探所有路径，直到到达终态，或者到达不了终态

问题：

  1. 只有尝试了全部可能的路径，才能确定一个输入序列不被接受，而这些路径的条数随着路径长度的增长成指数增长
  2. 识别过程中需要大量回溯，时间复杂度升高且算法趋于复杂

DFA

DFA: Deterministic Finite Automaton确定的有限自动机

DFA是NFA的一个特例，其中：
（1）没有状态具有ε状态转移(ε_transition)，即状态转换图中没有标记ε的边；
（2）对每个状态s和每个字符a，最多有一个下一状态。

识别记号的特点

具有确定性，即在当前状态下对同一字符最多只有一个的下一状态转移

具体体现：

  • （定义）move函数是1对1的
  • （状态转移图）从一个节点出发的边上标记均不相同
  • （状态转移矩阵）M[si, a]是一个状态
  • 且字母表不包括$\varepsilon$

将在DFA上识别输入序列的过程形式化为算法，该算法被称为模拟器（模拟DFA的行为）或驱动器（用DFA的数据驱动分析动作）;
算法与DFA一起，即构成识别记号的词法分析器的核心。它的最大特点是算法与模式无关，仅DFA与模式相关。

有限自动机的等价

若有限自动机M和M’识别同一正规集，则称M和M’是等价的，记为M=M’。

模拟DFA

1
2
3
4
5
6
7
8
s:=s0； ch:=nextchar； 	 -- 初值
while  ch≠eof		 -- 循环
	loop s:=move(s,ch);  
	ch:=nextchar;
end loop;
if s is in F then return “yes”;	 -- 返回
else return “no”;
end if;

NFA与DFA

NFA：与正规式有对应关系，易于构造，状态数少

DFA：确定性便于记号识别，不易构造，状态数可能多

对于任何一个NFA，均可以找到一个与它等价的DFA

*词法分析器的构造

方法和步骤

正规式－NFA－DFA－最小化DFA－词法分析器

  1. 用正规式描述模式（为记号设计正规式）
  2. 为每个正规式构造一个NFA，它识别正规式所表示的正规集
  3. 将构造的NFA转换成等价的DFA，这一过程也被称为确定化
  4. 优化DFA，使其状态数最少，这一过程也被称为最小化
  5. 根据优化后的DFA构造词法分析器

由正规式构造NFA而不是DFA的原因是正规式到NFA有规范的一对一的构造算法

由DFA而不是由NFA构造词法分析器的原因是DFA识别记号的方法优于NFA识别记号的方法

词法分析器返回的完整记号包括属性和类别

从正规式到NFA

首先有个箭头然后一个0，同时注意*，所存在经过ε的边

Thompson算法

输入：字母表∑上的正规式r
输出：接受L(r)的NFA N
方法：首先分解r，然后根据下述步骤构造NFA：

然后看Thompson算法中，对于第三种，(a)分类的时候会有两个分开的ε，然后合上的ε，(c)星闭包的时候，起始和中间，中间和最后，起始和最后，中间和中间都有ε；(b)的意思是，P的终态和Q的初态进行合并

从NFA到DFA

注意从这里开始都是smove，因为算的都是集合(set)的了

“并行”模拟NFA

<1> 消除ε 状态转移：$ε_闭包(T)$
<2> 消除多于一个的下一状态转移：smove(S, a)

用状态集代替状态

状态集T的ε_闭包(T)是一个状态集，且满足：
（1） T中所有状态属于ε_闭包(T)；
（2） 任何smove(ε_闭包(T)，ε)属于ε_闭包(T)；
（3） 再无其他状态属于ε_闭包(T)。

求ε_闭包

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function ε_闭包(T) is
begin
  for T中每个状态t 
  	loop 加入t到U; push(t);
  end loop;
  while  栈不空
  	loop pop(t); 
    	for 每个u=move(t, ε)
    	loop 
    		if u不在U中 then 加入u到U; push(u); end if; 
  		end loop;
  	end loop; 
  return U;
end ε_闭包;

模拟NFA

1
2
3
4
5
6
7
8
9
S := ε_闭包({s0});         -- 所有可能初态的集合
ch := nextchar;
while  ch ≠ eof loop 
	 S:= ε_闭包(smove(S，ch))； 
	 ch:= nextchar;
end loop;
if  S∩F≠Φ then return “yes”;  
else return “no”; 
end if;

缺点：每次动态计算下一状态转移集合，效率低

“子集法”构造DFA

将NFA的下一状态集合合并为一个状态

与模拟DFA相比，记录了所有状态与状态转移

但是在最坏的情况下，等价的DFA的状态数可能是$o(2^n)$级的，需要很大的存储空间，这时候往往采用模拟NFA

我的感觉就是模拟DFA是像解释器一样的，每一个序列都要按NFA走一次，重新计算集合；而子集法就是像编译器一样的，首先把所有情况都考虑到，只需要将序列根据新生成的状态生成图走一遍，看是否到了终态即可

首先要写个$ε_闭包({0})$，同时记为A，然后再算，每一个出现的都要对每个字符再算，每一个的格式是$ε_闭包(smove(A,a))$

子集法

1
2
3
4
5
6
7
8
9
10
11
12
13
ε_闭包({s0})是Dstates仅有的状态，且尚未标记;
while Dstates有尚未标记的状态T 
loop  标记T;
      for  每一个字符a   -- T中向外转移边的标记
      loop	U := ε_闭包(smove(T，a));
        if U非空 
        then Dtran[T，a] := U; 	--Dtran是一个状态转换矩阵
             if   U不在Dstates中 
             then U作为尚未标记的状态加入Dstates;
             end if;
        end if;
      end loop;
end loop;

优点：

  1. 消除了不确定性
  2. 无需动态计算状态集合（针对模拟NFA的算法）

对于任何两个状态t和s，若从一状态出发接受输入字符串ω，而从另一状态出发不接受ω，或者从t出发和从s出发到达不同的接受状态，则称ω对状态t和s是可区分的

若任何输入序列$ω$对s和t均是不可区分的，则说明从s出发和从t出发，分析任何输入序列$ω$均得到相同结果；因此，s和t可以合并成一个状态

最小化DFA

将一个DFA等价变换为另一个状态数最少的DFA的过程被称为最小化DFA，相应的DFA称为最小DFA

首先可以通过划分组，看是否是最简的

  1. 初始划分：终态与非终态
  2. 利用可区分的概念，反复分裂划分中的组Gi，直到不可再分裂
    如果某一个组经过一个字符串达到的组和其它的都不一样，则它可以分割出来
  3. 由最终划分构造D’，关键是选代表和修改状态转移
  4. 消除可能的死状态（不是终态，且所有输入的字符均转向其自身）和（从初态）不可（到）达（的）状态
由DFA构造词法分析器

需满足最长匹配原则

表驱动型的词法分析器

数据与操作分离的工作模式

转换矩阵是分析器的分析表，模拟DFA算法是分析器的驱动器

DFA是被动的，需要一个驱动器（如LEX）来模拟DFA的行为，以实现对输入序列的分析

直接编码的词法分析器

将DFA和DFA识别输入序列的过程合并在一起，直接用程序代码模拟DFA识别输入序列的过程

适合转换图，适合词法比较简单的情况，可以直接根据正规式/转换图进行编码，而无需一步一步按上述方法来

① 初态→程序的开始
② 终态→程序的结束（不同终态return不同记号）；
③ 状态转移→分情况或者条件语句（case/if）
④ 环→循环语句（loop）
⑤ return满足最长匹配原则

同时实际的词法分析器不但接受合法输入，也应指出非法输入

两者的比较
表驱动 直接编码
分析器的速度 慢 快
程序与模式的关系 无关 有关
分析器的规模 较大 较小
适合的编写方法 工具生成 手工编写

练习题

  1. 识别abb和abab，同时构造$(a|b)^*abb$的DFA，并且简化DFA，最后设计“直接编码的词法分析器”

    用Thompson算法构造正规式r=(a|b)*abb的NFA N(r)

    首先分解正规式，然后自下而上构造NFA

    然后如果用模拟NFA法的话

    每次根据输入序列，确定下一个状态

    如果用子集法的话

    简化DFA


    可以看到ABCD通过b得到的分别是CDCE，而唯有E不在ABCD组，所以只可以划分出D

    直接编码的词法分析器

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    void main(){ 	char buf[]="abba#", *ptr=buf;
      while (*ptr!='#' ){
    l0: while (*ptr=='b') ptr++;			// state 0
        switch(*ptr)
        { case 'a': ptr++; 
    l1:             while (*ptr=='a') ptr++;	// state 1
                    switch (*ptr)
                    { case 'b': ptr++;
    	                     switch (*ptr)	// state 2
    		              { case 'a': ptr++; goto l1;
    		                case 'b': ptr++;
    			                   switch (*ptr)	// state3
    				            { case 'a': ptr++; goto l1;
    				              case 'b': ptr++; goto l0;
    				              case '#': cout<<"yes\n";
    				 	                 return;
    				              default:  goto le;						     }
    		                default: goto le;
    		              }
                      default: goto le;
                    }
           default: goto le;
        }
      }
    le: cout << "no\n" << endl;
    } // 看实例运行

  2. 写出每个a后必跟b的ab串

    $(b|(ab)^)^$

  3. 不含011的01串

    $1^(01|0)^$

语法分析

词法分析：字母是元素，组成字符串，记号的集合，线性结构，以字符流为输入
语法分析：记号是元素，组成句子， 句子的集合，树结构，以记号流为输入

语法的双重含意：

  1. 语法规则：上下文无关文法（子集－LL文法或LR文法）
  2. 语法分析：下推自动机（LL或LR分析器），自上而下和自下而上分析 （这两种都只能处理上下文无关文法的子类）

语法分析器

语法分析器是编译器前端的重要组成部分，中心部件

语法分析器的两个重要作用：

  1. 根据词法分析器提供的记号流，为语法正确的输入构造分析树（或语法树）
  2. 检查输入中的语法（可能包括词法）错误，并调用出错处理器进行适当处理

语法错误的处理原则

源程序中可能出现的错误：

  • 语法（包括词法）错误
    • 词法错误如非法字符或拼写错关键字、标识符等
    • 语法错误是指语法结构出错，如少分号、begin/end不配对等
  • 语义错误
    • 静态语义错误（涉及的是编译时可检查出来的错误）：如类型不一致、参数不匹配等
    • 动态语义错误（程序运行时的逻辑错误）：如死循环、变量为零时作除数等

目标：

  • 清楚而准确地报告错误的出现（地点正确，不漏报、不错报也不多报
  • 迅速从每个错误中恢复过来（以便分析继续进行）
  • 不应对语法正确源程序的分析速度降低太多

基本恢复策略

  1. 紧急方式恢复：抛弃若干输入，直到遇到某个指定的合法记号（称为同步记号）集合为止同步记号一般是定界符，如分号或end等【最简单，但最容易造成错报、漏报和多报语法错误的现象】
  2. 短语级恢复：采用串替换的方式对剩余输入进行局部纠正（抛弃+插入）
  3. 出错产生式：用出错产生式捕捉错误（预测错误），预置型的短语级恢复方式（YACC采用的方式）
  4. 全局纠正：对错误输入序列x，找相近序列y，使得x变换成y所需的修改、插入、删除次数最少【代价太大】

上下文无关文法CFG

CFG：Context Free Grammar

CFG是一个四元组G =（N，T，P，S），其中
（1） N是非终结符（Nonterminals）的有限集合；
（2） T是终结符（Terminals）的有限集合，且N∩T=Φ；
（3） P是产生式（Productions）的有限集合，
A→α，其中A∈N（左部），α∈(N∪T)（右部），
若α=ε，则称A→ε为空产生式（也可以记为A →）；
（4） S是非终结符，称为文法的*开始符号（Start symbol）

可以将产生式中的记号→读作“定义为”或者“可导出”，如：“E → E + E”可用自然语言表述为“算术表达式定义为两个算术表达式相加”， 或者“一个算术表达式加上另一个算术表达式，仍然是一个算术表达式”

文法开始符号S是第一个产生式的左部；N是可以出现在产生式左边符号的集合；T是绝不出现在产生式左边符号的集合（记号）【所以T不一定是一个句子的那种终结符，也可以是一个短语的终结符，如+、-、(、)等等

CFG的产生式表示也被称为巴克斯范式BNF，规范的BNF中，->用::=来表示

约定：大写英文字母A、B、C表示非终结符；小写英文字母a、b、c表示终结符；小写希腊字母α、β、δ表示任意文法符号序列

产生式中，用“|”连接的每个右部称为一个候选项，具有平等的权利

CFG产生语言的基本方法——推导

推导：产生式产生语言的过程是从开始符号S开始，对产生式左部的非终结符反复地使用产生式：将产生式左部的非终结符替换为右部的文法符号序列(展开产生式，用标记=>表示)，直到得到一个终结符序列

利用产生式产生句子的过程中，将产生式A→γ的右部代替文法符号序列αAβ中的A得到αγβ的过程，称αAβ直接推导出αγβ，记作：αAβ=>αγβ

若对于任意文法符号序列α1，α2，…αn，均α1=>α2=>…=>αn，则称此过程为零步或多步推导，记为：$α1=^>αn$，其中α1=αn的情况为零步推导；若α1≠αn，即推导过程中至少使用一次产生式，则称此过程为*至少一步推导，记为：$α1=^+>αn$

对于所有α，有$α=^>α$，即推导具有自反性
若$α=^>β$，$β=^>γ$，则$α=^>γ$，即推导具有传递性

CFL上下文无关语言

由CFG G所产生的语言L(G)被定义为:
$L(G)=\{\omega|S=^+>\omega\ and\ \omega\in T^*\}$

L(G)称为上下文无关语言(Context Free Language, CFL)，ω称为句子，若S=*>α，α∈(N∪T)*，则称α为G的一个句型

第一个是文法开始符号，最后一个是句子，其他的都是句型，但广义来说，第一个和最后一个也是句型

在推导过程中，若每次直接推导均替换句型中最左边的非终结符，则称为最左推导，由最左推导产生的句型被称为左句型；

类似的可以定义最右推导与右句型，最右推导也被称为规范推导

分析树

分析树是推导的图形表示，直观并且同时反映语言结构的实质和推导过程

对CFG G的句型，分析树被定义为具有下述性质的一棵树。
（1） 根由开始符号所标记
（2） 每个叶子由一个终结符、非终结符、或ε标记
（3） 每个内部结点由一个非终结符标记
（4） 若A是某内部节点的标记，且X1，X2，…，Xn是该节点从左到右所有孩子的标记，则A→X1X2…Xn是一个产生式。若A→ε，则标记为A的结点可以仅有一个标记为ε的孩子

分析树与语言和文法的关系：

  1. 每一直接推导(每个产生式)，对应一棵仅有父子关系的子树，即产生式左部非终结符“长出”右部的孩子
  2. 分析树的叶子，从左到右构成G的一个句型；若叶子仅由终结符标记，则构成一个句子

语法树

为了仅关注句型，并且忽略推导过程，产生了语法树：

对CFG G的句型，表达式的语法树被定义为具有下述性质的一棵树:
（1） 根与内部节点由表达式中的操作符标记；
（2） 叶子由表达式中的操作数标记；
（3）用于改变运算优先级和结合性的括弧，被隐含在语法树的结构中

分析树和语法树又被称为具体语法树和抽象语法树AST

二义性与二义性的消除

若文法G对同一句子产生不止一棵分析树，则称G是二义的

产生原因：在产生句子的过程中某些直接推导有多于一种选择；文法中缺少对文法符号优先级和结合性的规定；一个句子有多于一颗分析树，仅与文法和句子有关，与采用的推导方法无关（对于某些文法和句型，无论采用最左推导还是最右推导都会有歧义的）

文法二义性不能说明程序设计语言是二义的；程序设计语言不能二义；只有当产生一个语言的所有文法都是二义的时，这个语言才被认为是二义的

二义文法不是CFG

消除文法二义的两种方法：

  1. 改写二义文法为非二义文法
  2. 规定二义文法中符号的优先级和结合性，使仅产生一颗分析树

现给出一个二义文法：

1
2
3
4
5
E→E+E 
 | E*E
 |（E） 
 | -E
 | id
改写二义文法为非二义文法

对于上述二义文法进行改写：

1
2
3
E → E + T  | T			
T → T * F  | F 
F →（E）    | -F | id

改写二义文法的方法：

通过引入非终结符，使原来分辨不清的结构受到约束，从而使得对任何一个句子，仅能构造一颗分析树

一些结论：

  1. 新引入的非终结符，限制了每一步直接推导均有唯一选择
  2. 最终分析树的形状，仅与文法有关，而与推导方法无关
  3. 非终结符的引入，增加了推导步骤（分析树增高），从而分析树效率降低
  4. 越接近S的文法符号的优先级越低（如E→E+T）
  5. 对于A→αAβ，若$a\in\beta$（A在a的左边），则a具有左结合性质；若$a\in\alpha$（A在a的右边），则a具有右结合性质【如E->E+T，则+具有左结合性，E->T+E，则+具有右结合性】

关键步骤：

  1. 引入一个新的非终结符，增加一个子结构并提高一级优先级
  2. 递归非终结符在终结符左边，运算具有左结合性，否则具有右结合性

我的想法是先列出优先级，比如这里我可以说从低到高是[+] [\] [(), -, id]；然后列出结合性：左结合+,*；右结合-；无结合id；因为有三个层次，所以需要再引入两个新变量，首先是优先级最低的，然后是次之，最后是最高的；在每一个产生式中，又要根据结合性，如果是左结合的则右边应该含有终结符的标号，否则相反，就可以写出来了；当然要注意可以不含有+的问题，所以有个|T的存在*

对于“悬空”问题（即else和最近还是最远if匹配）

我们来讨论一下，首先这里没有优先级区分，但是结合性应该是右结合，即else与其左边最靠近的then结合，那么只需改写如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
原来的：
S → if C then S
   | if C then S else S
   | id := E     
C → E=E | E<E | E>E
E → E+E | -E | id | n
改写之后的（MS是完全匹配的意思，即含有if then else；UMS不完全匹配，即含有if then，至于then中是否嵌套，则看如下表示）：
S  → MS 			   
    | UMS			   
MS → if C then MS else MS  
    | id := E		   
UMS→ if C then S		    
    | if C then MS else UMS  
C → E=E | E<E | E>E
E → E + T  | T			
T →（E）    | -T | id | n

然后根据一一比对，比如对于if x<3 then if x>0 then x:=5 else x:=-5

比如对于和最远的if匹配的话，我们首先将S展开，如果是MS，则展开为第一种，但是MS展不开了（这里应该是if x>0 then x:=5这句话）；如果是UMS，则展开为第二种，但是MS也展不开了，所以这种匹配不可行；而和最近的if匹配的话，是可行的，且唯一确定，首先展开成UMS，S再展开成MS的第一种

规定二义文法中符号的优先级和结合性

但是二义文法具有如下优点：

  1. 比非二义文法容易理解
  2. 分析效率高，分析树低，直接推导步骤少

通过为二义文法规定优先级和结合性（YACC的方法）

修改语言的语法（表现形式被改变）
  1. 明确给出结束标志，如end if
  2. 给表达式加括号

正规式与CFG

正规式到CFG的转换

正规式所描述的语言结构均可用CFG描述，反之不一定

识别正规语言的自动机是有限自动机，它们的特征是没有记忆功能

识别CFL的自动机是下推自动机，在有限自动机的基础上增加了一个下推栈，具有简单的记忆功能

从正规式到CFG的对应关系：

  1. 构造正规式的NFA
  2. 若0为初态，则$A_0$为开始符号
  3. 对于move(i,a)=j，引入产生式$A_i$→$aA_j$
  4. 对于move(i,ε)=j，引入产生式 $A_i→A_j$
  5. 若i是终态，则引入产生式$A_i →ε$

为什么用正规式而不用CFG描述词法：

  1. 词法规则简单，用正规式描述已足够
  2. 正规式的表示比CFG更直观、简洁、易于理解
  3. 有限自动机的构造比下推自动机简单，且分析效率高
  4. 区分词法和语法，为编译器前端的模块划分提供方便
  • 正规式适合描述线性结构，如标识符、关键字、注释等
  • CFG适合描述具有嵌套（层次）性质的非线性结构，如不同结构的句子if-then-else、while-do等

上下文有关语言CSL

变量的声明与引用、过程调用时形参与实参的一致性检查等无法用CFG描述，所以产生了CSL（Context Sensitive Language)

CFG到CSL的文法所表示的意思都变了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
CFG无法表示:
L1={ωcω|ω∈(a|b)*}	(标识符声明与引用一致性的抽象)
L2={a^n b^m c^n d^m|n≥1和m≥1}	(形参ab与实参cd一致性的抽象)
L3={a^nb^nc^n|n≥1} 		(输入n个字符，回退n个字符，加n个底线，计数问题的抽象)
对文法稍加修改，得到相近的CFL：
【ω^r是ω的逆序】
L1'={ωcω^r|ω∈(a|b)*}			（S→aSa|bSb|c）
L2'={a^n b^m c^m d^n|n≥1, m≥1}	  （S→aSd|aAd    A→bAc|bc）
L2''={a^n b^n c^m d^m|n≥1, m≥1}   （S→AB  A→aAb|ab  B→cBd|cd）
L3'={a^m b^m c^n|m, n≥1}		  （S→AC  A→aAb|ab   C→cC|c）
正规式：
L3''={a^k b^m c^n|k,m,n>=1} 		a^+ b^+ c^+

命题：L3’不是正规集，因为构造不出可以识别L3’的DFA
证明：（反证）
假设L3’是正规集，则可构造n个状态的DFA D，它接受L3’；
考察D读完$ε，a，aa，…，a^n$，分别到达$S0，S1，…，Sn$，共有$n+1$个状态。
根据鸽巢原理，序列中至少有两个状态相同，设$S_i=S_j（j>i）$，因为$a^ib^ic^k∈L3’$，所以存在路径​$a^ib^ic^k$，但是D中也有路径$a^jb^ic^k$，矛盾；故L3’不是正规集

形式语言与自动机

若文法$G=(N，T，P，S)$的每个产生式$α→β$中，均有$α∈(N∪T)^$，且至少含有一个非终结符，$β∈(N∪T)^$，则称G为0型文法【任何0型语言都是递归可枚举的；反之，递归可枚举集必定是一个0型语言】

对0型文法施加以下第i条限制，即得到i型文法。

  1. G的任何产生式α→β（S→ε除外）满足|α|≤|β|
  2. G的任何产生式形如A→β，其中A∈N，$β∈(N∪T)^*$【对于$\alpha A\beta\to\alpha \gamma\beta$，则A只有在左边是$\alpha$，右边是$\beta$这样的上下文才可能替换成$\gamma$
  3. G的任何产生式形如A→a或者A→aB(或者A→Ba)，其中A和B∈N，a∈T
文法 语言 自动机
短语文法（0型） 短语结构语言 图灵机
CSG （1型） CSL 线性界线自动机
CFG （2型） CFL 下推自动机
正规文法（3型） 正规集 有限自动机

CSG、CFG、正规式能力递减，但是能力越强的文法，其文法的设计和自动机的构造越苦难

自上而下分析

自上而下分析是一种试探的过程，是反复使用不同产生式谋求与输入序列匹配的过程

当既有左递归又有左因子的时候，先消除左递归

消除左递归

避免陷入死循环

消除直接左递归

若文法G中的非终结符A，对某个文法符号序列α存在推导$A=^+>Aα$，则称G是左递归的。若G中有形如A→Aα的产生式，则称该产生式对A直接左递归

1
2
3
4
5
首先，整理A产生式为如下形式:
	A→ Aα1|Aα2|...|Aαm|β1|β2|...|βn
其中αi非空[若αi为空，则形成一个有环的A产生式]，βj均不以A开始。然后用下述产生式代替A产生式：
	A → β1 A' |β2 A' | ...|βn A'   
	A'→ α1 A' | α2 A' | ... | αm A' |ε

消除文法左递归

核心思想：将不是直接左递归的非终结符右部展开到其他产生式中

但是若G产生句子的过程中出现$A=^+>A$的推导，则无法消除左递归

合理排序非终结符：A1，A2，…，An;【通过两层for循环检验】
然后用用$Aj→δ1|δ2|…|δk$右部替换$Ai→Ajγ$中的Aj得到$Ai→δ1γ|δ2γ|…|δkγ$;再消除Ai产生式中的直接左递归;

如S→Aa|b A→Ac|Sd|ε

将S的右部展开在A中，得到：A→Ac|Aad|bd|ε

消除新产生式中的直接左递归，得到：

S→ Aa | b A→ bdA' | A' A'→ cA' | adA' | ε

提取左因子

避免回溯

将：A → αβ1|αβ2，替换为：A →αA' A'→β1|β2

递归下降分析

  1. 直接以程序的方式模拟产生式产生语言的过程
  2. 每个产生式对应一个子程序，产生式右边的非终结符对应子程序调用，终结符则与输入序列匹配
  3. 它对文法的限制是不能有公共左因子和左递归；
  4. 它是一种非形式化的方法，只要能写出子程序，用什么样的方法和步骤均可

优点：简单灵活、容易构造

缺点：程序与文法直接相关，对文法的任何改变均需对程序进行相应的修改

适合规模比较小的语言

稳妥的笨方法：

  1. 构造文法的状态转换图并且化简

    • 标记为A的边可等价为标记ε的边转向A转换图的初态
    • $ε$边连接的两个状态可以合并
    • 标记相同的路径可以合并
    • 不可区分的状态可以合并

  2. 将转换图转化为EBNF表示

    EBNF：扩展BNF（和正规式一样，为了表示方便加入的+、？、[]等等）

    ①${ }​$：重复0或若干次（while）
    ② [ ]：可选择（if或while）
    ③ |：括弧( )之内的或关系（case）
    ④ ( )：改变运算的优先级和结合性

  3. 从EBNF构造子程序

构造递归下降字程序：

首先设计两个变量lookahead（当前的下一输入的终结符）和eof（输入结束标志）

另外设计一个函数match(t)，进行终结符匹配

预测分析器

预测分析器是下推自动机的一个具体实现

栈中的内容是符号；而在移进-归约分析器的栈中内容是状态

预测分析表

M[A, a]的内容：若当前栈顶是非终结符A，下一输入终结符是a，则M[A, a]指示下一步动作；其中A为行下标，a为列下标

格局：格局是一个三元组
（栈内容，当前剩余输入，改变格局的动作）
$^top$ $^ip$

改变格局的动作：
① 匹配终结符：若\^top=^ip(但≠#)，则pop且next(ip)
② 展开非终结符：
若^top= X且M[X,^ip]=α(X→α)，则pop且push(α)
③ 报告分析成功：若^top=^ip=#，则分析成功并结束
④ 报告出错：其它情况，调用错误恢复例程

构造预测分析表
  1. 首先构造FIRST集合与FOLLOW集合
  2. 然后根据两个集合构造预测分析表

文法符号序列α的FIRST集合为:
$FIRST(α)=\{a|α=^>a…，a∈T\}$，
若$α=^>ε$，则$ε∈FIRST(α)$

非终结符A的FOLLOW集合如下:
$FOLLOW（A） = \{ a |S=^*>…Aa…，a∈T\}$，
若A是某句型的最右符号，则$#∈FOLLOW（A）$

通俗地讲，α的FIRST集合就是从α开始可以导出的所有以终结符开头的序列中的开头终结符；而A的FOLLOW集合，就是从开始符号可以导出的所有含A的文法符号序列中紧跟A之后的终结符

FIRST集合计算

自下而上计算FIRST

  1. 若X∈T，则$FIRST(X)={X}$；
  2. 若X是非终结符且有X→ε，则加入ε到FIRST(X)；
  3. 若X是非终结符且有X→Y1Y2…Yk，并设Y0=ε，Yk+1=ε。那么对所有从0开始的j(0≤j≤k)，若a∈FIRST(Yj+1)且ε∈FIRST(Y1~Yj)【这里表示1到j都有ε】，则加入a到FIRST(X)。

FIRST(X1X2…Xn)是所有FIRST(Xi)(i=1,2,..,k)的并集，其中k为第一个具有性质ε不属于FIRST（Xk）或k>n的文法符号

First集合里的符号一定是终结符，ε不是终结符，也不是非终结符，只是一个表示空的标志而已

T->array[num] of int中array, [, num, ], of, int都是终结符

FOLLOW集合计算

自上而下计算FOLLOW

  1. 加入#到FOLLOW(S)，其中S是开始符号，#是输入结束标记

  2. 若有产生式A→αBβ，则除ε外，FIRST(β)的全体加入到FOLLOW(B)

  3. 若有产生式A→αB或A→αBβ且ε∈FIRST(β)，则FOLLOW(A)的全体加入到FOLLOW(B)

    若 $S =^*>δAa$ a紧跟A之后
    则 $=>δαBa$ a也紧跟B之后（A→αB）

    或者 $=>δαBβa =^*>δαBa$ （A→αBβ）
    因为 ε∈FIRST(β) 使得B成为A产生式右部最右的文法符号
    即 对任何a∈FOLLOW(A)，均有a∈FOLLOW(B)

构造预测分析表：

预测分析表的列都是终结符

  1. 对文法的每个产生式A→α，执行2和3

  2. 对FIRST(α)的每个终结符a，加入α到M[A，a]

    若当前栈顶为A，当前输入为a，则规则2表示下一步动作是展开A→α，因为a∈FIRST(α)，所以展开后下一次正好匹配a【这里α是aB…这样的表示，因为FIRST(α)里有a】

  3. 若$ε∈FIRST(α)$，则对FOLLOW(A)的每个终结符b(包括#)加入α到M[A，b]

    若当前栈顶为A，当前输入为b且b∈FOLLOW(A)，则规则3表示下一步动作是展开A→ε，即栈顶弹出A，继续分析A之后的部分，因为b∈FOLLOW(A)，所以弹出A后下一次正好匹配A的后继b

  4. M中其它没有定义的条目均是error

驱动器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
初始格局为: （#S，ω#，分析器的第一个动作）[其中ω是输入序列]
令ip指向ω#中的第一个终结符，top指向S;
  loop x:=top^; a:=ip^;
	if x ∈ T
	then  	if x=a 
			then pop(x); next(ip); -- 匹配终结符
      		else error(1);     -- 出错：栈顶终结符不是a
      		end if;
	else  	if   M[x, a] = X→Y1Y2...Yk
			then pop(X); push(YkYk-1...Y2Y1);--展开产生式
      		else error(2);     -- 出错：产生式不匹配
      		end if;
	end if;
	exit when x=# and a=#;           -- 分析成功
  end loop;

LL(1)文法

文法G被称为是LL(1)文法，当且仅当为它构造的预测分析表中不含多重定义的条目；由此分析表所组成的分析器被称为LL(1)分析器，它所分析的语言被称为LL(1)语言；第一个L代表从左到右扫描输入序列，第二个L表示产生最左推导，1表示在确定分析器的每一步动作时向前看一个终结符

任何二义文法都不是LL(1)文法

证明是LL(1)文法

G是LL(1)的，当且仅当G的任何两个产生式A→α|β满足:

  1. 对任何终结符a，α和β不能同时推导出以a开始的串

向前看一个就不够了，M[A，a]中有多重定义A→α和A→β

  1. α和β最多有一个可以推导出ε

向前看一个就不够了，任何属于FOLLOW（A）的终结符b(包括#)，M[A，b]中有多重定义A→α和A→β

  1. 若β=*>ε,则α不能导出以FOLLOW(A)中终结符开始的任何串

若条件3不满足，即存在终结符b，它既在FOLLOW(A)中，又在FIRST(α)中，则步骤2把条目A→α加入到M[A，b]中，而步骤3又把条目A→β加入到M[A，b]中，即M[A，b] 中有多重定义A→α和A→β

所以LL(1)文法既无左递归也无左因子

缺点：

  1. 文法难写，难懂
  2. 适应范围有限，往往写不出有些语言的LL(1)文法

实际编译器中使用更多的是一类LL(1)文法的真超集——LR(1)文法

自下而上分析

从句子ω开始，从左到右扫描ω，反复用产生式的左部替换产生式的右部（句型中的句柄）、谋求对ω的匹配，最终得到文法的开始符号，或者发现一个错误：规范归约—剪句柄—移进/归约分析—SLR(1)分析器

规范规约

设αβδ是文法G的一个句型，
若 存在S =>αAδ，A =+>β，
则 称β是句型αβδ相对于A的短语，
特别的，若 有A→β，则 称β是句型αβδ相对于产生式A→β的直接短语
一个句型的最左直接短语被称为*句柄

如：句型：id1+id2*id3，短语：id1+id2*id3、id2*id3、id1、id2、id3，直接短语：id1、id2、id3，句柄：id1

句型：存在的一个子树；短语：以非终结符为根子树中所有从左到右的叶子；直接短语：只有父子关系的树中所有从左到右排列的叶子（树高为2）；句柄：最左边父子关系树中所有从左到右排列的叶子（句柄是唯一的）

最左规约

若 α是文法G的句子且满足下述条件，则 称序列αn，αn-1，…，α0是α的一个最左归约。

1. $α_n=α$
2. $α_0=S$（S是G 的开始符号）
3. 对任何i(0<i<=n)，$α_{i-1}$是将$α_i$中**句柄**替换为相应产生式左部非终结符得到的

最左归约的逆过程是一个最右推导，分别称最右推导和最左归约为规范推导和规范归约

推导=>；归约<=（剪句柄的过程）

移进-归约分析器

也有驱动器指向输入记号流的向上的箭头的！！！

格局：（#栈中内容，当前剩余输入#，改变格局的动作）
改变格局的动作：
移进(shift)：输入序列中的终结符进栈。(匹配终结符)
归约(reduce)：将栈顶句柄替换为对应非终结符(最左归约)
接受(accept)：宣告分析成功
报错(error)：发现语法错误，调用错误恢复例程

  1. 句柄总是在栈顶形成(最左归约)
  2. 栈中保留的总是一个右句型的前缀(加上若干终结符形成句型)，称为活前缀
  3. 最左归约是逻辑上从下到上构造一棵分析树，或从下到上为分析树剪句柄

LR分析

特点：

  1. 采用最一般的无回溯移进-归约方法
  2. 可分析的文法是LL文法的真超集
  3. 能够及时发现错误，快到从左到右扫描输入序列的最大可能；
  4. 分析表较复杂，难以手工构造
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
初始格局为：（#0，ω#， 移进），其中0是初态
ip指向ω#中的第一个终结符，top指向栈顶初始状态；
loop  s:=top^; a:=ip^;
   case action[s，a] is
	 shift s': push(a); push(s'); next(ip); -- 移进
	 reduce by A→β:
		pop(2*|β|);	 -- 弹出句柄和相应状态
		s' := top^;  	 -- 暴露出当前栈顶状态s'
		push(A);     	 -- 产生式左部符号进栈
		push(goto(s'，A)); -- 新栈顶状态进栈
		write(A→β);      -- 完成归约，跟踪分析轨迹
	 accept:  return; 		-- 成功返回
	 others:  error;  		-- 出错处理
   end case;
end loop;

LR分析表

与预测分析表不同的是LR分析表的列既有终结符也有非终结符的部分

动作表

action[s, a]确定改变格局的动作

转移表

goto[s, A]指示非终结符的状态转移

若为文法G构造的移进-归约分析表中不含多重定义的条目，则称G为LR(k)文法，分析器被称为是LR(k)分析器，它所识别的语言被称为LR(k)语言。L表示从左到右扫描输入序列，R表示逆序的最右推导

k表示为确定下一动作向前看的终结符个数，一般情况下k<=1。当k=1时，简称LR

有LR(0)、SLR(1)、LALR(1)和LR(1)分析器，它们功能的强弱和构造的难度依次递增；当k>1后，分析器的构造趋于复杂，一般情况下并不构造k>1的LR(k)分析器

SLR(1)分析器

SLR(1)，即简单LR(1)

首先构造一个可以识别文法G中所有活前缀的DFA，然后根据DFA和简单的向前看信息构造SLR分析表

出现在移进-归约分析器栈中的右句型的前缀，被称为文法G的活前缀（viable prefix）

活前缀＋若干剩余输入（不在栈中）＝>右句型

在移进-归约分析中，只要保证已扫描过的输入序列可以归约为一个活前缀，则分析到目前为止没有错误

一个LR(0)项目(简称项目)是这样一个产生式，在它右部的某个位置有一个点“.”。对于A→ε，它仅有一个项目A→.

一个产生式右部若有n个文法符号，则该产生式有n+1个LR(0)项目

每个产生式是一个识别活前缀的NFA；每个项目是NFA的一个状态

项目A→α.β显示了分析过程中看到(移进)了产生式的多少；β不为空的项目称为可移进项目，β为空的项目称为可归约项目

拓广文法

拓广文法$G’ = G∪{S’→S}$

写拓广文法的时候，每一个一行，然后要写(i)，对于同一个非终结符展开成多个用|连接的时候，每一种选择也必须分行写

其中：S'→.S是识别S的初态，
S'→S.是识别S的终态。
目的是使最终构造的DFA状态集中具有唯一的初态和终态

从NFA到DFA

NFA（项目）→DFA（项目集）

词法分析器－“子集法” ：
① ε_闭包(I)：从状态集I不经任何字符能到达的状态全体
② smove（I，a）：所有从I经字符a能直接到达的状态全体

类似的两个过程：
① closure(I)：从项目集I不经任何文法符号到达的项目全体
② goto(I，x)：所有从I经文法符号x能直接到达的项目全体

项目集I的闭包closure(I)是这样一个项目集

1. I中的所有项目属于closure(I)；
2. 若A→α.Bβ属于closure(I)，则所有**形如B→.γ的项目**属于closure(I)；
3. 其它任何项目不属于closure(I)

即若.后面是一个非终结符B，则需要将B展开成B→.γ的形式

closure(I)的计算

1
2
3
4
5
6
7
8
9
10
11
function closure（I） is
begin   J := I；
    for J中每个项目[A→α.Bβ]和G中每个产生式B→γ
    loop 
        if   B→.γ不在J中  
        then 加入[B→.γ]到J;
        end  if；
        exit when 再没有项目可以被加入到J中；
    end loop；    
    return（J）；
end closure；

对所有属于项目集I、且形如[A→α.Xβ]的项目（X∈N∪T），goto(I，X)是所有形如[A→αX.β]的项目

设J=goto(I，X)，K=closure(J)，K中项目A→α.β分为两类：

1. J：   α非空，因为至少有一个X；**均是核心项目**
2. K-J：  α=ε，即 "."在产生式右部最左边（想到新增加的都是`B→.γ`这类）；可由某个J计算而来（K-J=closure(J)-J）；**均是非核心项目**

项目[S’→.S]和所有“.”不在产生式右部最左边的项目称为核心项目(kernel items)，其它“.”在产生式右部最左边的项目(不包括[S’→.S])称为非核心项目(nonkernel items)

比较：项目A→α.β显示了分析过程中看到(移进)了产生式的多少；β不为空的项目称为可移进项目，β为空的项目称为可归约项目

识别活前缀的DFA：

1
2
3
4
5
6
7
8
9
10
11
12
13
构造文法G的、基于LR(0)项目的、识别活前缀的DFA
加入closure(S’→.S)到C中，作为唯一未标记状态; -- 初态
while C中还有未标记状态I   -- 考察所有未标记状态
loop 标记I;
	for I状态下的每个文法符号x   -- 考察所有x
	loop if J:=closure(goto(I,x))非空  --有下一状态
		 then 	Dtran[I,x]:= J;  -- 记录下一状态转移
			if J不在C中	           -- 新状态待考察
			then 不标记加入J到C；
			end if;
		  end if;
	end loop;
end loop;

例子如下：大概就是每次加入一个新的文法符号X的时候，如果到达新的状态，则转移过去，并且如果.之后的是非终结符的时候，需要继续找到从项目集I不经任何文法符号到达的项目全体（即计算closure(I)）

%E5%88%86%E6%9E%90%E5%99%A8.png)

活前缀与项目

若存在最右推导S’=*>αAω=>αβ1β2ω，则称项目[A→β1.β2] 对活前缀αβ1有效

项目A→β1.β2对活前缀αβ1有效，具有两层含意：

  1. 从文法开始符号，经αβ1可到达该项目(项目所在状态)
  2. 在当前活前缀的情况下，该项目可指导下一步分析动作(αAω=>αβ1β2ω)

活前缀与项目的关系

① 一个项目可能对若干个活前缀有效，项目A→β1.β2对所有从初态出发可以到达此项目的路径上的标记均有效（一个路径标记是一个活前缀）
② 若干个项目可能对同一个活前缀有效，项目集中的所有项目对同一活前缀均有效

​ 综合①②可知：
​ 同一项目集中的所有项目，对此项目集的所有活前缀均有效，即项目集中的每个项目均有同等权利指导下一步动作（即一个对某活前缀有效，则整个项目集对他都有效）

这里的活前缀的DFA也要每一种可能分行写，而且不可以用|连接，对于.后面的非终结符，展开要完全，比如项目集中已经存在部分，也要补全，然后每个还要标序号，为了清晰可见，可以不连接到，而只是箭头和标号，同时注意如果给出的不是拓广文法，要先变成拓广文法，然后给出识别活前缀的DFA

③ 有效项目的意义

​ 1.到目前为止分析是正确的；
​ 2.指导下一步的分析：
​ A→β1.β2（可移进项）：移进β2中第一个终结符
​ B→β.（可归约项）：按产生式B→β归约

④ 项目集中的冲突和解决冲突的简单方法：SLR(1)
当一个项目集中同时存在：
A→β1.β2和B→β1.：既可移进又可归约，移进/归约冲突
A→α.和B→α.：均可指导下一步分析，归约/归约冲突
解决方法：简单向前看一个终结符：
移进/归约冲突：若FIRST(β2)∩FOLLOW(B)=Φ，冲突可解决
归约/归约冲突：若FOLLOW(A)∩FOLLOW(B)=Φ，冲突可解决

证明是SLR(1)文法

若冲突可以解决，则称文法为SLR(1)文法，构造的分析表为SLR(1)分析表

在写原因的时候，需要给出每一个FIRST和FOLLOW，算计算FIRST和FOLLOW的过程，因为是自下而上和自上而下的

证明是LR(0)文法

若上述构造的DFA中没有冲突，则文法是LR(0)的（可以说某某项目集既有可移进项目又有可归约项目，产生了移进/归约冲突，所以该文法不是LR(0)文法）

例如上图中，I1、I2、I9均有移进/归约冲突

1
2
3
4
5
6
7
8
9
FIRST(F) = {-, id}
FIRST(T) = {-, id}
FIRST(E) = {-, id}
FIRST(E')= {-, id}
FOLLOW(E')= {#}
FOLLOW(E) = {-, #}
FOLLOW(T) = {*, -, #}
FOLLOW(F) = {*, -, #}

但是FIRST(-T)∩FOLLOW(E')=Φ FIRST(*F)∩FOLLOW(E)=Φ，所以此文法是SLR(1)文法

构造SLR分析表

输入: 基于G的LR(0)项目集的、识别活前缀的DFA=(C, Dtran)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
if   DFA中有不能解决的移进/归约和归约/归约冲突
then error;
else for 每个状态转移Dtran[i,x]=j
	   loop if x∈T 
            then action[i,x]:=Sj; 
            else goto[i,x]:=j; 
            end if;
       end loop;
       for  状态i的每个可归约项A→α.
       loop  if   S'→ S. 
             then action[i, #]:=acc;
             else for 每个a∈FOLLOW(A) 
                  loop action[i,a]:=Rk; end loop; --k代表当时给表达式的标号
             end if;
       end loop;
   end if;
2. DFA的初态（S'→.S所在的状态），是分析表的开始状态

例如，上述例子可构造分析表如下：

非SLR(1)文法

二义文法不是SLR(1)文法

所以非SLR(1)文法分为两类

  • 非二义文法：可以增加向前看终结符个数解决冲突
  • 二义文法：无论向前看多少个终结符，也无法解决二义性

练习题

  1. 根据给出的文法，首先消除二义性，接着消除左递归

    1
    2
    3
    4
    5
    E→E+E 
     | E*E
     |（E） 
     | -E
     | id

首先消除二义性：

先看优先级：[+] [] [(), -, id]，再结合性，左结合：+ ()；右结合：-；无结合id

1
2
3
E->E+T|T
T->T*F|F
F->(E)|-F|id

再消除左递归：

根据算法A->Aα|β变成A->βA' A'->αA'|ε

1
2
3
4
5
E->TE'
E'->+TE'|ε
T->FT'
T'->*FT'|ε
F->(E)|-F|id

  1. 根据给出的文法，消除左递归，编写状态转换图，并化简，写出递归下降子程序；编写预测表，并通过驱动器算法来预测分析句子id+id*id;#是否被接受

    1
    2
    3
    4
    L→E;L|ε
         E→E+T|E-T|T
         T→T*F|T/F|T mod F|F
         F→(E)|id|num
1
2
3
4
5
6
7
消除左递归后的等价文法:
  L →E;L|ε
  E →TE'
  E'→+TE'|-TE'|ε
  T →FT'
  T'→*FT'|/FT'| mod FT'|ε
  F →(E)|id|num

转换图及其化简：

递归下降子程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
procedure L is
begin
   lookahead := lexan； --调用词法分析器，返回一个终结符
   while (lookahead/=eof)loop E; match(';'); end loop;
end L;
procedure E is
begin
  T;
  while lookahead∈(+|-)
  loop 
  	   match(lookahead);
       T;
  end loop;
end E;
procedure T is
begin
  F;
  while lookahead∈(*|/|mod)
  loop 
  		match(lookahead);
       	F;
  end loop;
end T;
procedure F is
begin
   case lookahead is
    '(' : match('('); E; match(')');
    id  : match(id);
    num : match(num);
    others : error("syntax error2");
   end case;
end F;

自下而上计算FIRST

1
2
3
4
5
6
7
8
9
10
11
FIRST(F)={(, id, num}
FIRST(T')={ε, *, /, mod}
FIRST(T)=FIRST(F)={(, id, num}
FIRST(E')={+, -, ε}
FIRST(E)=FIRST(T)={(, id, num}
FIRST(L)=FIRST(E)+ε={(, id, num, ε}

自上而下计算FOLLOW

1
2
3
4
5
6
7
8
9
10
11
FOLLOW(L)={#}
FOLLOW(E)={), ;}
FOLLOW(E')=FOLLOW(E)={), ;}
FOLLOW(T)=FIRST(E')+FOLLOW(E)={+, -, ), ;}
FOLLOW(T')=FOLLOW(T)={+, -, ), ;}
FOLLOW(F)=FOLLOW(T)+FOLLOW(T')+[FIRST(T')-ε]={+, -, ), ;, *, /, mod}

对文法的每个产生式A→α：

对FIRST(α)的每个终结符a，加入α到M[A，a]

若ε∈FIRST(α)，则对FOLLOW(A)的每个终结符b(包括#)加入α到M[A，b]

  1. 已知文法：(1) S→aABe (2) A→b (3) A→Abc (4) B→d，求对句子：abbcde的最左归约；并用移进-归约方法分析abbcde

    abbcde <= aAbcde <= aAde <= aABe <= S

    a4 a3 a2 a1 a0

    移进-归约方法：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    栈	剩余输入  改变格局的动作
    #	abbcde#  移进
    #a	 bbcde#  移进
    #ab	  bcde#  归约，(2)A→b
    #aA	  bcde#  移进
    #aAb   cde#  移进
    #aAbc   de#  归约，(3)A→Abc
    #aA     de#  移进
    #aAd     e#  归约，(4)B→d
    #aAB     e#  移进
    #aABe 	  # 归约，(1)S→aABe 
    #S		  # 接受

  2. 已知文法如下，求id--id*id#是否被接受

    1
    2
    3
    4
    5
    6
    E → E-T	（1） 
       | T	（2）
    T → T*F	（3）
       | F	（4）
    F → -F	（5）
       | id （6）

 首先我们再来回顾一下规则

1
2
3
4
5
6
7
8
shift s': 
  push(a); push(s'); next(ip); 
reduce by A→β:
  pop(2*|β|);
  s':=top^;
  push(A);  push(goto(s'，A));
  write(A→β);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
栈	      剩余输入	  	动作
#0	    id--id*id# 		s4
#0id4	  --id*id# 		r6(F→id)
这里来说明一下归约的步骤，首先弹出两个id的大小，现在的栈是#0，然后修改栈指针，压入F，同时压入goto(0, F)，即3
#0F3	  --id*id# 		r4(T→F)
#0T2	  --id*id# 		r2(E→T)
#0E1	  --id*id#  	s6
#0E1-6     -id*id#  	s5
#0E1-6-5    id*id#  	s4
#0E1-6-5id4   *id#  	r6(F→id)
#0E1-6-5F8    *id#  	r5(F→-F)
这里来说明一下归约的步骤，首先弹出两个-F的大小，即4个，现在的栈是#0E1-6，然后修改栈指针，压入F，同时压入goto(6, F)，即3
#0E1-6F3      *id# 		r4(T→F)
#0E1-6T9      *id#  	s7
#0E1-6T9*7     id#  	s4
#0E1-6T9*7id4    #  	r6(F→id)
#0E1-6T9*7F10    #  	r3(T→T*F)
#0E1-6T9         #		r1(E→E-T)
#0E1             #		acc

静态语义分析

语法制导翻译是处理语义的基本方法，它以语法分析为基础，在语法分析得到语言结构的结果时，处理附着于此结构上的语义，如计算表达式的值、生成中间代码等

语法与语义

语法是指语言结构，即语言的“样子”；语义是附着于语言结构上的实际含义，即语言的“意义”

语义分析的作用：

  • 检查是否结构正确的句子所表示的意思也合法
  • 执行规定的语义动作，如：
    • 表达式求值
    • 符号表填写
    • 中间代码生成等

方法：语法制导翻译

语法制导翻译

基本思想：将语言结构的语义以属性的形式赋予代表此结构的文法符号，而属性的计算以语义规则的形式赋予由文法符号组成的产生式。在语法分析推导或规约的每一步骤中，通过语义规则实现对属性的计算，以达到对语义的处理

具体方法：

  • 将文法符号所代表的语言结构的意思，用附着于该文法符号的属性表示
  • 用语义规则规定产生式所代表的语言结构之间的关系（即属性之间的关系），即用语义规则实现属性计算

语义规则

两种形式：

  • 语法制导定义（算法）
    用抽象的属性和运算表示的语义规则 (公式，做什么)
  • 翻译方案（程序实现，方法不唯一）
    用具体的属性和运算表示的语义规则 (程序段，如何做)
    语义规则也被习惯上称为语义动作
    忽略实现细节，二者作用等价（设计与实现）

属性

对于产生式A→α，其中α是由文法符号X1X2…Xn组成的序列，它的语义规则可以表示为(4.1)所示关于属性的函数：
b := f(c1, c2, …, ck) (4.1)
语义规则中的属性存在下述性质与关系。
(1) 若b是A的属性，c1, c2, …, ck是α中文法符号的属性，或者A的其它属性，则称b是A的综合属性。
(2) 若b是α中某文法符号Xi的属性，c1, c2, …, ck是A的属性，或者是α中其它文法符号的属性，则称b是Xi的继承属性。
(3) 称(4.1)中属性b依赖于属性c1, c2, …, ck。
(4) 若语义规则的形式如下，则可将其想像为产生式左部文法符号A的一个虚拟属性。属性之间的依赖关系，在虚拟属性上依然存在。
f(c1, c2, …, ck)

属性之间的计算构成了语义规则，计算的先后次序被称为属性的依赖关系

例如：E→E1+E2 E.val:=E1.val+E2.val，则表明：E的属性.val由E1和E2的相应属性计算而来，E的属性依赖于E1和E2的属性

注释分析树

将属性附着在分析树对应文法符号上，形成注释分析树；类似的，将属性附着在语法树对应文法符号上，形成语法分析树

注释分析树直观地反映属性的性质和属性之间的关系，所以画树还要标属性，对于S标nc，对于M标stat，对于E标tc和fc

继承属性：自上而下计算的，从前辈和兄弟的属性计算得到，即“自上而下，包括兄弟”

综合属性：自下而上计算的，从子孙和自身的其他属性计算得到，即“自下而上，包括自身”

LR分析翻译方案的设计

LR分析中的语法制导翻译实质上是对LR语法分析的扩充：

  1. 扩充LR分析器的功能：当执行归约产生式的动作时，也执行产生式对应的语义动作。由于是归约时执行语义动作，因此限制语义动作仅能放在产生式右部的最右边
  2. 扩充分析栈：增加一个与分析栈并列的语义栈，用于存放分析栈中文法符号所对应的属性值

递归下降分析翻译方案的设计

在产生式右部任何位置都可以嵌入语义动作；（与LR分析只能在最右边进行比较）

在函数返回值、参数、变量等设计存储空间

中间代码

  • 要求中间代码具有如下特性，以便于编译器的开发移植和代码的优化（优点）
    • 便于语法制导翻译
    • 既与机器指令的结构相近，又与具体机器无关。
  • 中间代码的主要形式：树、后缀式、三地址码等

后缀式

也被称为逆波兰表示，操作数在前，操作符紧随其后，无需用括号限制运算的优先级和结合性

表示并不惟一

1
2
3
4
5
6
7
8
9
x := first_token;
while  not end_of_exp 
loop    if   x in operands
        then push x;          -- 操作数进栈
        else pop(operands);  -- 算符，弹出操作数
             push(evaluate);  -- 计算，并将结果进栈
        end  if;
     	next(x);
end loop;

后缀式并不局限于二元运算的表达式，可以推广到任何语句，只要遵守操作数在前，操作符紧跟其后的原则即可

三地址码

形式接近机器指令，且具有便于优化的特征

顾名思义，是由不超过三个地址组成的一个运算

题目中的三地址码序列需要像这样：

1
2
3
4
5
6
7
(1) if a < b goto (3)
(2) goto (8)
(3) if c < d goto(5)
(4) goto (8)
(5) t1:= a + c
(6) x:=t1
(7) goto -

语法：

result := arg1 op arg2结果存放在result中的二元运算arg1 op arg2

或result := op arg1结果存放在result中一元运算op arg1

或 op arg1一元运算op arg1

或result := arg1直接拷贝

三元式

(i)(op, arg1, arg2)

序号(i)是它们在三元式表中的位置

序号的双重含义：既代表此三元式，又代表三元式存放的结果
存放方式：数组结构，三元式在数组中的位置由下标决定
弱点：给代码的优化带来困难
因为代码优化常使用的方法是删除某些代码或移动某些代码位置，而一旦进行了代码的删除或移动，则表示某三元式的序号会发生变化，从而使得其他三元式中对原序号的引用无效

语法制导翻译
  1. 属性 .code：三元式代码，指示标识符的存储单元或三元式表中的序号
  2. 属性 .name：标识符的名字
  3. 函数trip( op，arg1，arg2 )：生成一个三元式，返回三元式的序号
  4. 函数 entry(id.name)：返回标识符在符号表中的位置或存储位置 
1
2
3
4
5
6
7
产生式：					语义规则：
(1) A→id:=E	{A.code:=trip(:=,entry(id.name),E.code)}
(2) E→E1+E2	{E.code:=trip(+,E1.code，E2.code)}
(3) E→E1*E2 {E.code:=trip(*,E1.code，E2.code)}
(4) E→(E1)  {E.code:=E1.code}
(5) E→-E1	{E.code:=trip(@，E1.code, )}
(6) E→id	{E.code:=entry(id.name)}

四元式

  1. 四元式与三元式的唯一区别是将由序号所表示的运算结果改为了由临时变量来表示

  2. 此改变使得四元式具有了运算结果与四元式在四元式序列中的位置无关的特点，它为代码的优化提供了极大方便，因为这样可以删除或移动四元式而不会影响运算结果【避免了三元式的值与三元式在三元式组中的位置相关的弱点】

  3. 三地址码与四元式形式的一致性

    ​ 四元式 三地址码
    (op，arg1，arg2，result) result := arg1 op arg2

    result的表示方法通常是给出一个临时名字，用它来存放运算的结果，被称为临时变量（语法制导翻译时可以随意引入临时变量，若干临时变量可以共用同一个存储空间）

语法制导翻译
  1. 属性.code： 表示存放运算结果的变量
  2. 函数newtemp：返回一个新的临时变量，如T1，T2，…等
  3. 过程emit( op，arg1，arg2, result)：生成一个四元式，若为一元运算，则arg2可空
1
2
3
4
5
6
7
产生式：					语义规则：
1)A→id:=E	{A.code:=newtemp; emit(:=, entry(id.name), E.code, A.code)}
(2)E→E1+E2	{E.code:=newtemp; emit(+，E1.code,E2.code,E.code)}
(3)E→E1*E2	{E.code:=newtemp; emit(*，E1.code,E2.code,E.code)}
(4)E→(E1)	{E.code:=E1.code}
(5)E→-E1	{E.code:=newtemp; emit(@,E1.code, , E.code)}
(6)E→id		{E.code:=entry(id.name)}

图形表示

树作为中间代码，语法树真实反映句子结构，对语法树稍加修改（加入语义信息），即可以作为中间代码的一种形式(注释语法树)

树语法制导翻译
  1. 属性.nptr：指向树节点的指针
  2. 函数mknode(op，nptr1，nptr2)： 生成一个根或内部节点，节点数据是op， nptr1和nptr2分别指向的左右孩子的子树。若仅有一个孩子，则nptr2为空
  3. 函数mkleaf(node)： 生成一个叶子节点
1
2
3
4
5
6
7
产生式：					语义规则：
(1) A → id := E {A.nptr:= mknode(:=,mkleaf(entry(id.name)),E.nptr)}
(2) E → E1 + E2	{E.nptr:=mknode(+,E1.nptr,E2.nptr)}
(3) E → E1 * E2 {E.nptr:=mknode(*,E1.nptr,E2.nptr)}
(4) E → ( E1 )  {E.nptr:=E1.nptr}
(5) E → - E1	{E.nptr:=mknode(@,E1.nptr, )}
(6) E → id		{E.nptr:=mkleaf(entry((id.name))}
树的优化表示DAG

​ 如果树上若干个节点有完全相同的孩子，则这些节点可以指向同一个孩子，形成一个有向无环图(Directed Acyclic Graph, DAG)
​ DAG与树的唯一区别是多个父亲可以共享同一个孩子，从而达到资源（运算、代码等）共享的目的

​ 仅需要在mknode和mkleaf中增加相应的查询功能
​ 首先查看所要构造的节点是否已经存在，若存在则无需构造新的节点，直接返回指向已存在节点的指针即可

树与其他中间代码的关系

  1. 树表示的中间代码与后缀式和三地址码之间有内在联系
  2. 对树进行深度优先后序遍历，得到的线性序列就是后缀式，或者说后缀式是树的一个线性化序列
  3. 树的每个内部节点和它的孩子对应一个三元式或四元式

符号表

符号表的作用：连接声明与引用的桥梁，记住每个符号的相关信息，如作用域和绑定等，帮助编译的各个阶段正确有效地工作

符号表的空间存储应该是可以动态扩充的

符号表设计的基本要求：目标是合理存放信息和快速准确查找

  • 正确存储各类信息
  • 适应不同阶段的需求
  • 便于有效地进行查找、插入、删除和修改等操作；
  • 空间可以动态扩充

逻辑上讲：每个声明的名字在符号表中占据一栏，称为一个条目，用于存放名字的相关信息
符号表中的内容：保留字、标识符、特殊符号（包括算符、分隔符等）等等
多个子表：不同类别的符号可以存放在不同的子表中，如变量名表、过程名表、保留字表等
存放方式：关键字＋属性

组合关键字至少应该包括三项：名字＋作用域＋类型

构成名字的字符串的存储：

  • 定长数据/直接存放
    • 名字：直接存储名字
  • 变长数据（名字长度变化范围很大）/间接存放
    • 名字，起始地址；名字间可以用特殊符号隔开，也可以在名字中添加长度

名字的作用域

<1> 静态作用域规则（static-scope rule）：

​ 编译时就可以确定名字的作用域，也可以说，仅从静态读程序就可确定名字的作用域。

<2> 最近嵌套规则（most closely nested）：
以程序块为例，也适用于过程

  1. 程序块B中声明的作用域包括B；
  2. 如果名字x不在B中声明，那么B中x的出现是在外围程序块B’的x声明的作用域中，使得
    • B’有x的声明，并且
    • B’比其它任何含x声明的程序块更接近被嵌套的B

线性表

线性表应是一个栈（后进先出），以正确反映名字的作用域，即符号的加入和删除，均在线性表的一端进行

查找：从表头(栈顶)开始，遇到的第一个名字；
插入：先查找，再插入在表头；

删除：
(a) 暂时：将在同一作用域的名字同时摘走，适当保存
(b) 永久：将在同一作用域的名字同时摘走，不再保存
修改：与查找类似，修改第一个遇到的名字的信息；修改可以用删除＋插入代替

效率（n个条目）：

  • 一个名字的查找
    • 成功查找(平均)：(n+1)/2
    • 不成功查找：n+1
  • 建立n个条目的符号表(最坏)：$\displaystyle\sum^n_{i=1}i$ = (n+1)(n+2)/2

散列表

将线性表分成m个小表，构造hash函数，使名字均匀散布在m个子表中；若散列均匀，则时间复杂度会降到原线性表的1/m

名字挂在两个链上(便于删除操作)：
散列链(hash link)： 链接所有具有相同hash值的元素，表头在表头数组中
作用域链(scope link)：链接所有在同一作用域中的元素，表头在作用域链中

操作：

  • 查找
    • 首先计算散列函数，然后从散列函数所指示的入口进入某个线性表，在线性表中沿hash link，像查找单链表中的名字一样查找
  • 插入
    • 首先查找，以确定要插入的名字是否已在表中，若不在，则要分别沿hash link和scope link插入到两个链中，方法均是插在表头，即两个表均可看作是栈
  • 删除
    • 把以作用域链连在一起的所有元素从当前符号表中删除，保留作用域链所链的子表，为后继工作使用（如果是临时删除，则下次使用时直接沿作用域链加入到散列链中即可）

散列函数的设计：

  1. 减少冲突，分布均匀
  2. 充分考虑程序设计语言的特点
    如：若有变量V001,V002,…,V300，且首字母的值作为hash值

声明语句的翻译

声明语句的作用是为可执行语句提供信息，以便于其执行；对声明语句的处理，主要是将所需要的信息正确地填写进合理组织的符号表中

变量的声明

类型定义：为编译器提供存储空间大小的信息（预定义&自定义）
变量声明：为变量分配存储空间
组合数据的类型定义和变量声明：
定义与声明在一起，定义与声明分离

决定变量存储空间的是变量的数据类型

  1. 定义确定存储空间，声明分配存储空间
  2. 简单数据类型的存储空间是已经确定的，如integer可以占4个字节，real可以占8个字节，char可以占1个字节等
  3. 组合数据类型变量的存储空间，需要编译器根据程序员提供的信息计算而定

定义就好像typedef struct node{};，声明就好像struct node Node;，使用就好像Node.val=1;

语法制导翻译

  1. 全程量offset：记录当前符号存储的偏移量，初值设为0
  2. 属性.type和.width：变量的类型和所占据的存储空间
  3. 过程enter(name, type, offset)：为type类型的变量name建立符号表条目，并为其分配存储空间(位置)offset
1
2
3
4
5
6
7
产生式：					语义规则：
(1)D→D;D	
(2)D→id:T 	{enter(id.name, T.type, offset); offset:=offset+T.width;}
(3)T→int	{T.type:=integer; T.width:=4;}
(4)T→real	{T.type:=real; T.width:=8;}
(5)T→array [num] of T1 {T.type:=array(num.val, T1.type); T.width:=num.val*T1.width;}
(6)T→^T1	{T.type:=pointer(T1.type); T.width:=4;}

左值与右值

形式上，出现在赋值号左边和右边的变量分别称为左值和右值；
实质上，左值必须具有存储空间，右值可以仅是一个值，而没有存储空间；（变量【简单变量、组合变量】是左值，左值是地址，右值是值，）形象地讲，左值是容器，右值是内容

过程的定义与声明

过程（procedure）：过程头/规格说明(做什么)＋过程体(怎么做)；(有返回值的也称为函数，被操作系统调用的过程称为主程序)
过程的三种形式：过程定义、过程声明和过程调用。
过程定义：过程头+过程体；
过程声明：过程头

先声明后引用的原则，若在引用前已定义，则声明可省略，因为定义已包括了声明

参数的传递

  1. 形参与实参

    • 定义时的参数称为形参(parameter或formal parameter)，形式参数
    • 引用时的参数称为实参(argument或actual parameter)，实在参数

  2. 常见的参数传递形式：（不同的语言提供不同的形式）

    • 值调用（call by value）

      • 过程内部对参数的修改，不影响作为实参的变量原来的值
      • 任何可以作为右值的对象均可作为实参
      • 过程定义时形参被当作局部名看待，并在过程内部为形参分配存储单元
      • 调用过程前，首先计算实参并将值（实参的右值）放入形参的存储单元
      • 过程内部对形参单元中的数据直接访问

    • 引用调用（call by reference）

      • 过程内部对形参的修改，等价于直接对实参的修改

      • 实参必须是左值

      • 定义时形参被当作局部名看待，并在过程内部为形参分配存储单元

      • 调用过程前，将作为实参的变量的地址（左值）放进形参的存储单元

      • 过程内把形参单元中的数据当作地址，间接访问

      • 存在副作用

        1
        2
        3
        4
        5
        6
        7
        int a=2;
        void add_one(int &x){ a=x+1;  x=x+1; }
        void main ()
        {   cout<<"before:  a="<<a<<endl;//2
            add_one(a);
            cout<<"after:   a="<<a<<endl;//4
        }

    • 复写－恢复（copy-in/copy-out）

      • 实参与非本地量共用一个存储空间，使得在过程内改变参数值的同时，也改变了非本地量的值
      • 值调用和引用调用的结合
      • 过程内对参数的修改不直接影响实参，避免了副作用
      • 返回时将形参内容恢复给实参，实现了参数的返回
      • 实参必须是左值
      • 过程定义时形参被当作局部名看待，并在过程内部为形参分配单元(复写)
      • 调用过程前，首先计算实参并将值(实参的右值)放入形参的存储单元
      • 过程内部对形参单元中的数据直接访问
      • 过程返回前将形参的右值放回实参的存储单元(恢复)

    • 换名调用（call by name）

      • 过程被认为宏，每次对过程的调用，实质上是用过程体替换过程调用，替换中用实参的文字替换体中的形参;这样的替换方式被称为宏替换或宏展开
      • 当需要保持实参的完整性时， 可以为实参加括弧
      • 在c++中的形式是宏定义#define【一种折中的方法，c++的内敛函数inline，避免了函数调用的同时，也消除了宏替换的副作用】
      • 运行速度快

  3. 参数传递方法的实质：
    实参是代表左值、右值、还是实参本身的正文

过程的作用域

同样遵守的是静态作用域和最近嵌套原则

设主程序（最外层过程）的嵌套深度dmain=1，
<1> 若过程A直接嵌套定义过程B，则dB=dA+1；
<2> 变量声明时所在过程的嵌套深度，被认为是该变量的嵌套深度

​ 嵌套过程中名字作用域信息的保存，可以用具有嵌套结构的符号表来实现，每个过程可以被认为是一个子符号表，或者是符号表中的一个节点
​ 嵌套的节点之间可以用双向的链表连接，正向的链指示过程的嵌套关系，而逆向的链可以用来实现按作用域对名字的访问

语法制导翻译

1
2
3
4
5
6
7
8
9
10
11
P → D				(1)
D → D ; D  			(2)
   | id : T			(3)
   | proc id ; D; S	(4) 
修改文法，使得在定义D之前生成符号表，LR分析
P → M D					(1)
D → D ; D  				(2)
   | id : T				(3)
   | proc id ; N D; S	(4)
M →ε					(5)
N →ε					(6)

全程量：有序对栈（tblptr, offset）

其中， tblptr保存指向符号表节点的指针，
offset保存当前节点所需宽度。
栈上的操作：push(t, o)、pop、top(stack)

  1. 函数mktable(previous)：建立一个新的节点，并返回指向新节点的指针;参数previous是逆向链，指向该节点的前驱，或者说是外层
  2. 过程enter(table, name, type, offset)：在table指向的节点中为名字name建立新的条目，包括名字的类型和存储位置等
  3. 过程addwidth(table, width)：计算table节点中所有条目的累加宽度，并记录在table的头部信息中
  4. 过程enterproc(table, name, newtable)：为过程name在table指向的节点中建立一个新的条目；参数newtable是正向链，指向name过程自身的符号表节点
1
2
3
4
5
6
7
8
9
10
11
12
产生式：					语义规则：
(1) P → M D		{addwidth(top(tblptr),top(offset)); pop;} 
(2) M → ε 		{t:=mktable(null);  push(t, 0,);} 
(3) D → D ; D
(4) D → id : T	{enter(top(tblptr),id.name,T.type,top(offset));
 top(offset):=top(offset)+T.width;} 
(5) D → proc id ; N D1; S	{ t:=top(tblptr); 
  							  addwidth(t, top(offset));
  							  pop;
  							  enterproc(top(tblptr), id.name, t);
							} 
(6) N → ε 		{t:=mktable(top(tblptr));  push(t,0);}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
序号 产 生 式	   						语 义 处 理 结 果
(1)  M1→ε   						t1 := mktable(null); push(t1, 0); 
(2)  N1→ε	  						t2 := mktable(top(tblptr));  push(t2, 0);
(3)  T1→int  						T1.type=integer,  T1.width=4
(4)  T2→array [10]of T2 			T2.type=array(10,in…≥t),  T2.width=40
(5)  D1→a:T2 						(a,arr,0)填进t2所指节点，top(offset):=40
(6)  T3→int  						T3.type=integer,  T3.width=4
(7)  D2→x:T3						(x,int,40)填进t2所指节点 top(offset):=44
(8)  N2→ε	  						t3:=mktable(top(tblptr));  push(t3,0);
(9)  T4→int  						T4.type=integer,  T4.width=4
(10) D3→i:T4 						(i,int,0)填进t3所指节点，top(offset):=4
(11) D4→proc readarray N2 D3 ; S	t:=top(tblptr); addwidth(t,top(offset)); pop; 											enterproc(top(tblptr),readarray,t);
(12) D7→proc sort N1 D6 ; S			t:=top(tblptr); addwidth(t,top(offset)); pop;
			   						enterproc(top(tblptr),sort,t);
(13) P→M1 D7 						addwidth(top(tblptr),top(offset)); pop;

简单算术表达式与赋值句

简单算术表达式和赋值句，是指表达式和赋值句中变量是不可再分的简单变量

语法制导翻译

  1. 属性.place：存放E的变量地址(符号表中地址或临时变量的编码)
  2. 过程emit(result ‘:=’ arg1 ‘op’ arg2)：生成“result:= arg1 op arg2”的三地址码
1
2
3
4
5
6
7
8
9
10
产生式：					语义规则：
(1) A→id:=E		{emit(entry(id.name) ':=' E.place)} 
(2) E→E1+E2		{E.place:=newtemp； 
 emit(E.place ':=' E1.place '+' E2.place)} 
(3) E→E1*E2		{E.place:=newtemp； 
 emit(E.place ':=' E1.place '*' E2.place)} 
(4) E→-E1		{E.place:=newtemp； 
 emit(E.place ':=' '-' E1.place)} 
(5) E→(E1)		{E.place:= E1.place} 
(6) E→id 		{E.place:=entry(id.name)}

内部类型转换

强制（coercion）：按照一定的原则，将不同类型的变量在内部转换为相同的类型，然后进行同类型变量的计算

三地址码：

T := itr E：将E从整型变为实型，结果存放T中
T := rti E：将E从实型变为整型，结果存放T中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
1. A->id:=E
{ tmode:=entry(id.name).mode;
  if   tmode=E.mode
  then emit(entry(id.name) ':=' E.place);
  else T := newtemp;
        if   tmode=int 
        then emit(T  ':=' rti E.place); 
        else emit(T  ':=' itr E.place);
        end if;
        emit(entry(id.name) ':=' T);
  end if;
} 
2. E→E1 op E2
{ T:=newtemp；E.mode:=real;
  if   E1.mode=int
  then  if   E2.mode=int
        then emit(T ':=' E1.place OPi E2.place);
             E.mode := int;
        else U:=newtemp; 
             emit(U ':=' itr E1.place);
             emit(T ':=' U OPr E2.place);
        end if;
  else 	if   E2.mode=int
        then U:=newtemp;
             emit(U ':=' itr E2.place);
             emit(T ':=' E1.place OPr U);
        else emit(T ':=' E1.place OPr E2.place);
        end if;
  end if;
  E.place:=T;
}

数组元素的引用

确定数组元素地址的两个要素：首地址和相对首地址的偏移量

不同的映射方式（行or列），使得同一个数组元素相对首地址的偏移量不同

确定映射方式的两种方法：

  • 由声明时的语法确定映射方式
  • 由编译器确定映射方式

三个假设条件：

  • 数组元素以行为主存放，推广到n维，就是数组的第i维是di个n-i维的数组(每个成员是一个n-i维的数组) ，其中di是第i维成员的个数
  • 数组每维的下界均为1
  • 每个元素仅占一个标准存贮单元（可以认为是一个字或者一个字节）。

约定：

  • 数组的声明： A[d1, d2, .., dn]
  • 数组元素的引用：A[i1, i2, .., in]

n维数组元素的地址计算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
addr(A[i1，i2，...，in])
=a+((i1-1)*d2*d3*...*dn+(i2-1)*d3*d4*...*dn+...+ (in-1))*w
=a-(d2*d3*...*dn+d3*d4*...*dn+...+dn+1)*w
   +(i1*d2*d3*...*dn+i2*d3*d4*...*dn+...+in-1*dn+in)*w
=a–c*w+v*w
根据假设条件③w=1:  addr(A[i1，i2，...，in])=a–c+v
其中：
c = d2*d3*d4...*dn+d3*d4*d5...*dn+*d4*d5*d6...*dn...+dn+1
  = (d2+1)*d3*...*dn+d4*d5...*dn+...+dn+1
  =((d2+1)*d3+1)*d4*d5...*dn+...+dn+1
    ......
  = (...((d2+1)*d3+1)*d4...+1)*dn+1
同理：
v = (...((i1*d2+i2)*d3+i3)*d4...+in-1)*dn+in 
令： v1 = i1
则： v2 = i1*d2+i2 = v1*d2+i2
     v3 = (v1*d2+i2)*d3+i3 = v2*d3+i3
	......
于是有：  v1 = i1	
          vj = v{j-1}*dj+ij (j=2，3，..., n)		(4.4)
同理可得：c1 = 1	
          cj = c{j-1}*dj+1 (j=2，3，..., n)	
最终得到数组元素引用的地址计算公式：
addr(A[i1，i2，...，in])=a-c+v=CONSPART+VARPART 
注意：如果w≠1,则c和v分别需要乘一个w，即：
addr(A[i1，i2，...，in])=a-cw+vw=CONSPART+VARPART

注意这里计算的时候，最后$i_n$也要减一；同时如果所求的不是起始地址，而是存储地址的时候，则要求写范围，即起始地址-起始地址+w-1

语法制导翻译

数组元素的寻址：CONSPART[VARPART]，或者T1[T]
取值的三地址码：X:=T1[T] 赋值的三地址码：T1[T]:=X

1
2
3
4
5
6
7
8
9
10
11
12
13
A → V := E
     V → id | id[EL] 	  
     EL→ E | EL ，E 
     E → E + E  | ( E ) | V
修改文法以适应递推公式的同步计算，知道名字的时候知道这是一个数组名而不是变量名：
A → V := E		(1)
V → id		(2)
   | EL ]		(3)
EL→ id [ E		(4)
   | EL , E		(5)
E → E + E		(6)
   | ( E )		(7)
   |  V		(8)
  1. 属性.array：数组名在符号表中的入口和数组首地址a
  2. 属性.dim：数组维数计数器，记录当前分析到的维数
  3. 属性.place：
    • 下标列表EL：存放vj=vj-1*dj+ij (j=2，3，…, n)的临时变量，
    • 简单变量id：仍然表示简单变量的地址，
    • 数组元素id[EL]：存放不变部分，一般可以是一个临时变量
  4. 属性.offset：保存数组元素的可变部分，
     简单变量的offset为空，可记为null
  5. 函数limit(array, k)：计算并返回数组array中第k维成员个数dk
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
(1) A→V:=E 
	{if  V.offset=null
	 then emit(V.place ':=' E.place);
	 else emit(V.place'['V.offset']' ':=' E.place);
	 end if;} 
(2) V→id { V.place:=entry(id.name); V.offset:=null;} 
(3) V→EL]
    {V.place:=newtemp; emit(V.place ':=' EL.array '-' c);
     V.offset:=newtemp;emit(V.offset ':=' EL.place '*' w);}
 (4) EL→id[E  { EL.place:=E.place;  EL.dim :=1; 
                EL.array:=entry(id.name);}
(5) EL→EL1,E 
	{ T:=newtemp; k:=EL1.dim+1;
	  dk:=limit(EL1.array, k);
	  emit(T ':='EL1.place '*' dk);	-- Vk-1*dk
	  emit(T ':=' T '+' E.place);  	-- T:=Vk-1*dk+ik
	  EL.array:=EL1.array; EL.place:=T; EL.dim:=k;} 
(6) E→E1+E2
	{ T:=newtemp;
	  emit(T ':=' E1.place '+' E2.place);
	  E.place:=T;} 
(7) E→(E1){ E.place:=E1.place;}
(8) E→V  { if   V.offset=null;
            then E.place:=V.place;
		else T:=newtemp;
  		     emit(T ':=' V.place '['V.offset']')；
		     E.place:=T;
		end if;}

布尔表达式

从高到低：not and or

短路计算可以回避指针为空时对ptr^.data=x的判断，从而

直接计算的语法制导翻译

1
2
3
4
5
6
7
8
9
10
11
(1)E→E1 or E2  { E.place := newtemp; 
		    emit(E.place ':=' E1.place 'or' E2.place);}
(2)  |E1 and E2 { E.place := newtemp; 
		    emit(E.place ':=' E1.place 'and' E2.place);}
(3)  |not E1{ E.place := newtemp; 
		    emit(E.place ':=' 'not' E1.place);}
(4)  |(E1)  { E.place := E1.place;}
(5)  |id1 relop id2
(6)  |id    { E.place:=entry(id.name);}
(7)  |true { E.place:=newtemp; emit(E.place ':=' '1');}
(8)  |false { E.place:=newtemp; emit(E.place ':=''0');}

语法制导翻译

  1. 属性 .true：表达式的真出口，它指向表达式为真时的转向
  2. 属性 .false：表达式的假出口，它指向表达式为假时的转向；
  3. 函数 newlable：与newtemp相似，但它产生的是一个标号而不是一个临时变量

这里.code是综合属性，.true和.false是继承属性

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
(1)E→E1 or E2  
	{ E1.true:= E.true; E1.false:=newlabel;
	  E2.true:= E.true; E2.false:=E.false; 
	  E.code := E1.code||emit(E1.false ':')||E2.code;}
(2)  |E1 and E2
	 { E1.false:= E.false; E1.true:=newlabel;
         E2.false:= E.false; E2.true:=E.true; 
         E.code  := E1.code||emit(E1.true':')||E2.code;} 
(3)  |not E1 { E1.false:=E.true;   E1.true:=E.false;}
(4)  |(E1)   { E1.false:=E.false;  E1.true:=E.true;} 
(5)  |id1 relop id2 
       { E.code := emit
	      ('if'id1.place relop.op id2.place'goto'E.true)
           || emit('goto' E.false);
       }
(6)  |id    { E.code := emit('if' id.place 'goto' E.true)
                  || emit('goto' E.false);}
(7)  |true  { E.code := emit('goto' E.true);}
(8)  |false { E.code := emit('goto' E.false);}

拉链与回填

拉链与回填的基本思想：

  • 当三地址码中的转向不确定时，将所有转向同一地址的三地址码拉成一个链

  • 一旦所转向的地址被确定，则沿此链将所有的三地址码中回填入此地址

    新增函数与属性：

  1. 属性.tc：真出口链，链接所有转向真出口的三地址码
  2. 属性.fc：假出口链，链接所有转向假出口的三地址码
  3. 属性.stat：记录当前第一个可用三地址码的序号
  4. 函数mkchain(i)：为序号是i的三地址码构造一个新链，且返回指向该链的指针
  5. 函数merg(P1，P2)：合并链P1和P2，且P2成为合并后的链头，并返回链头指针
  6. 过程backpatch(P，i)：将P链中相应域中的所有链域均回填为i值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
由于需要增加拉链回填这个语义规则，所以我们在产生式右部引入一个非终结符来实现；同时，为其增加一个新的属性.stat，记录当前第一个可用三地址码的序号
(1)M→ε					{M.stat:=nextstat;} 
(2)E→E1 or M E2 
{backpatch(E1.fc, M.stat);
E.tc:=merge(E1.tc, E2.tc); 
 E.fc:=E2.fc;} 
 
(3)  |E1 and M E2		
{backpatch(E1.tc, M.stat);
E.tc:=merge(E1.fc, E2.fc); 
 E.tc:=E2.tc;} 
 
(4)  |not E1			{E.tc:=E1.fc; E.fc:=E1.tc;}
(5)  |(E1) 				{E.tc:=E1.tc; E.fc:=E1.fc;}
(6) E→id1 relop id2				--这里直接写如a<b，而不用写id1 relop id2，然后再画线了
 { E.tc:=mkchain(nextstat); 
 E.fc:=mkchain(nextstat+1);
 emit('if' id1.place relop.op id2.place 'goto -');
 emit('goto -');
 } 
(7)   |id { E.tc:=mkchain(nextstat);
	 	E.fc:=mkchain(nextstat+1);
      	emit('if' id.place 'goto -');
      	emit('goto -'); }
(8)   |true {E.tc:=mkchain(nextstat); emit('goto -');}
(9)   |false{E.fc:=mkchain(nextstat); emit('goto -');}

控制语句

四类控制语句：

  • 无条件转移：goto （转向某标号所在位置）
       exit、break（退出某个范围）
    • 两个要素
      • 标号所标记的位置和goto所转向的标号
      • 起标记位置作用的标号被称为标号的定义出现
      • 用于goto转向的标号被称为标号的引用出现
      • 在一定的作用域内，标号仅可以定义一次，而可以引用多次
      • 当标号定义出现时，将有关信息填写进符号表中
      • 而当标号引用出现时，根据符号表中的信息生成正确转移的三地址码
      • 但在有些情况下标号的引用先于标号的定义。解决的方法是借助于符号表的拉链与回填
  • 条件转移： if_then_else，while_do：判断布尔表达式
  • 循环： for_loop：设定下限、上限与循环步长
  • 分支： case、switch：根据不同的取值执行不同的分支 
1
2
3
4
5
6
7
8
9
S→ id:S			(1) // 带标号的语句
  | goto id			(2) // goto语句
  | if E then S		(3)
  | if E then S else S	(4)
  | while E do S		(5)
  | A				(6) // 赋值语句
  | begin L end		(7) // 组合语句
L→ L;S			(8) // 语句序列
  | S				(9)

无条件转移

在符号表中为标号设置以下信息域：

  1. type：记录标识符的类型，如‘标号’或‘未知’
  2. def： 若是标号，记录是否已定义，如‘未定义’或‘已定义’
  3. addr：标号定义前作为链头，标号定义后作为此标号对应三地址码的序号

定义过程：fill(entry(id.name), a, b, c)，将a, b, c分别填写到符号表中标识符id的.type、.def、.addr域中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
(1)S→goto id
   { if   entry(id.name).type='未知'       -- 标识符第一次出现
     then fill(entry(id.name),'标号', '未定义', nextstat);
          emit('goto -');
     else if   entry(id.name).type ='标号'   -- 已出现且是标号
          then emit('goto', entry(id).addr)；
               if    entry(id.name).def=‘未定义’ -- 尚未定义，拉链
               then  fill(entry(id.name),'标号','未定义',nextstat-1);
               end if;
          else  error；  -- 标识符已出现且类型不是标号，出错
          end if;
     end if;
   }
(2)S  →LAB S { -- 略（根据S是何种语句，进行相应的翻译）}
(3) LAB→id '：'
    { if   entry(id.name).type='未知'   -- 标识符第一次出现
      then fill(entry(id.name), '标号', '已定义', nextstat);
      else if    entry(id.name).type='标号'  
                 and entry(id.name).def='未定义' -- 还未定义出现
           then q:=entry(id.name).addr;  
                fill(entry(id.name), '标号', '已定义', nextstat);
                backpatch(q, nextstat);
           else error;         -- 其它情况均出错
           end if;
      end if;
    }

条件转移

  1. 属性.begin：语句S开始的三地址码序号
  2. 属性.next： 语句S结束后的三地址码 序号
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
(1) S→if E then S1
{	E.true:=newlabel; E.false:=S.next; S1.next:=S.next;
S.code:=E.code||emit(E.true':')||S1.code;
} 
(2) S→if E then S1 else S2
{ E.true :=newlabel;   E.false:=newlabel;
 S1.next:=S.next; 	S2.next:=S.next;
 S.code := E.code 
	|| emit(E.true ':') || S1.code
      || emit('goto' S.next)
	|| emit(E.false ':') || S2.code; 
}
(3) S→while E do S1
{ S.begin := newlabel; E.true := newlabel;
E.false := S.next;   S1.next := S.begin;
S.code :=   emit(S.begin ':') || E.code
	   || emit(E.true ':')  || S1.code 
	   || emit('goto' S.begin)
	   || emit(E.false ':');
}

当有嵌套等控制流的问题的时候：通过拉链回填的方法

  1. 属性.nc：语句结束后的转向；未确定时拉链，确定后回填
  2. 属性.begin：语句(如while)的三地址码序列首地址 
1
2
3
4
5
6
7
8
9
10
(1)M→ε 		{M.stat:=nextstat;}
(2)S→if E then M S1		{backpatch(E.tc,M.stat);S.nc:= merge(E.fc,S1.nc);}
(3)N→ε		{N.nc:= mkchain(nextstat); emit('goto -');}
(4)S→if E then M1 S1 N else M2 S2
{backpatch(E.tc,M1.stat); backpatch(E.fc,M2.stat);
 S.nc:=merge(S1.nc,merge(N.nc,S2.nc));} 
(5)S→while M1 E do M2 S1
{backpatch(S1.nc,M1.stat); backpatch(E.tc,M2.stat);
 S.nc:=E.fc; emit('goto' M1.stat);} 
(6)S→A		{S.nc := mkchain();}

练习题

  1. 将下述语句翻译成后缀式

    a*-(b+c) abc+-*

    -(a+b)*(c+d)+(a+b-c) ab+-cd+*ab+c-+

    if i<10 then i:=10 else i:=0 i10<i10:=i0:=if-then-else

注意点

  • 老师上课说，给定的优先级顺序不一定和平常相同，即有可能出现+的优先级比*的高的情况，所以需要具体问题具体分析

其他：课后习题答案

转载请注明出处，谢谢。

愿 我是你的小太阳

买糖果去喽