目录


引论 -------------------

全文结构

全文结构

编译程序(Compiler)

  • 编译程序是一种翻译程序,它将不能被计算机识别的某种高级语言翻译成计算机能够识别的低级语言
  • 一般编译程序分成五个逻辑模块:词法分析、语法分析、语义分析和中间代码生成、中间代码优化、目标代码生成

解释程序(Intepretter)

  • 解释程序是一种翻译程序,它将不能被计算机识别的某种高级语言翻译成计算机能够识别的低级语言
  • 它是逐个语句翻译的,边翻译边执行,不生成目标代码

文法 -------------------

句子,句型和语言

  • 设G[S]是一文法,若 S =*=> x 则x是文法G[S]的句型
  • 若上述x仅有终结符构成,则称x为文法G[S]的句子
  • 文法G[S]的所有句子组成G[S]定义的语言

文法的类型

  • 0型文法
    • 递归可枚举
    • 与图灵机等价
  • 1型文法(上下文有关文法)
    • 若α->β,则有|β|>=|α|,仅S->ε除外
    • 或αAβ->αcβ(即A的左右是α和β时才能使用产生式)
  • 2型文法(上下文无关文法)
    • 文法中每个产生式α->β都有α∈VN,β∈(VN∪VT)*
  • 3型文法(正则文法)
    • 文法中的每个产生式满足 A->aB 或A->a,其中A,B∈VN,a∈VT*

最左推导与最右推导

  • 每次使用最左侧的非终结符进行替换称为最左推导
  • 每次使用最右侧的非终结符进行替换称为最右推导,也称规范推导

短语

  • S =*=>αAδA =+= > β(任意步推出),则称β是句型αβδ是对于A的短语
  • 特别的,如果有A => β(一步推出),则称β是句型αβδ相对于规则A->β的直接短语(简单短语)
  • 一个句型的最左直接短语称为该句型的句柄

短语的推导树含义

  • 实际上短语就是推导树中A的叶子节点构成的符号串
  • 如果A只有一层叶子节点(简单子树),那么这些叶子节点构成的串是A的直接短语
  • 最左的简单子树构成的符号串称为句柄

词法分析 -------------------

ε-closure

  • ε-closure(I)定义为从I开始,经过任意步ε可以到达的状态
  • **注意:**由于任何状态可以经过ε到达自己,所以I∈ε-closure(I)
  • I是可能状态的集合,所有I包含一个或多个状态

move(I,a)

  • move(I,a)定义为状态I经过步骤a后可以到达的所有状态的集合
  • 在不确定有限自动机中,move(I,a)可以包含多个状态

NFA转DFA

  1. 求初始状态I的ε-closure(I)
  2. 对ε-closure(I)中的状态,对字母表中每个符号求move(I,ai)
  3. 对2中产生的状态求ε-closure,如果得到的集合没有出现过,加入结果集合中
  4. 对产生的新状态不断重复上述求ε-closure,以及move操作,直到不产生新状态

DFA最小化

  1. 无法到达的状态直接去掉
  2. 无效状态射出的弧直接去掉

DFA最小化算法

  1. 去除不可达状态和相关的弧
  2. 将所有节点按照接受状态与非接受状态分成两类
  3. 对每个集合中的状态,分析接受某一元素后的状态改变
    • 如果新的状态均指向当前状态下的某一集合,则这些状态暂时等价
    • 如果新的状态指向当前状态下的不同的集合,则将这些状态分成不同的集合,分裂后的每个集合指向同一目标集合
  4. 重复步骤3,直到不能分裂

正规式与有穷自动机的转换

  1. 有穷自动机转正则式
    • 添加一个x节点,使用ε弧连接所有初始状态
    • 添加一个y节点,使用ε弧连接所有接受状态
  2. 正则式转有穷自动机
    • 状态x到第一个状态或最后状态到y之间可以添加一些ε弧

自顶向下分析 -------------------

FISRT集

  1. FIRST集中的元素都是终结符
  2. FIRST(A)等于A所有可能的推导中右端的第一个终结符

FISRT集算法

  1. 若X->ε,则ε∈FIRST(X)
  2. 若X为终结符,则X∈FIRST(X)
  3. 若X可推出多个符号且前面若干个符号可以推出空,则前面若干为空的符号的(FISRT(Ai)- {ε})∈FIRST(X)
  4. 若X可推出多个符号且所有符号都可以推出空,则FISRT(Ai)∈FIRST(X)且ε∈FIRST(X)
    注意:
  5. 分析一条产生式的FIRST集,如果需要其他符号的FIRST集,则递归的获取
  6. 递归结束后,将元素加入当前FIRST集,并判断当前递归元素是否为空,为空则递归的获取下一个元素的FIRST集
  7. 因为按照条件3,可以在一个产生式中产生多次递归,所以保存递归状态

FOLLOW集

  1. FOLLOW集中所有元素都是终结符
  2. FOLLOW(A)等于从S开始任意推导过程中,所有出现在A之后的终结符
  3. 也可以表述为从S开始任意推导过程中,所有出现在A之后的符号的FISRT集

FOLLOW集算法

  1. 对于文法开始符号S,有#∈FOLLOW(S)
  2. 若有(B->aA)则FOLLOW(B)是FOLLOW(A)的子集
  3. 若有(B->aAp)
    • 则(FISRT(p)- {ε})∈FOLLOW(A)
    • 若ε∈FIRST(p),则FOLLOW(B)是FOLLOW(A)的子集
      说明:
  4. 一定主要要先将#加入S的FOLLOE集
  5. 对于类似A->BC的产生式,相当于B->aA与B->εAp
    • 有FOLLOW(A)∈FOLLOW(C)
    • 有(FISRT(C)- {ε}) ∈ FOLLOW(B) 且 若ε∈FIRST(C)有FOLLOW(A)∈FOLLOW(B)
  6. 产生式右部如果只有一个元素,则无任何信息

SELECT集

  1. FOLLOW集中所有元素都是终结符
  2. 当A->a有a不能推导空,则SELECT(A->a) = FIRST(a)
  3. 当A->a可以为空时,SELECT(A->a) = (FIRST(a) - {ε})∪FOLLOW(A)

LL(1)文法

  • 第一个L表示从左向右扫描,第二个L表示最左推导,1表示向前查看一个符号
  • 当一个文法中的任意符号A的任意产生式的SELECT集不相交,则该文法是LL(1)文法

文法的等价变换

  1. 提取左公因子
  2. 消除左递归
    • 对于产生式 A->Ab|r 可直接改写为 A->rA’ A’->bA’|ε
    • 对于间接的递归,先使用带入变成直接递归,再消去直接递归
    • 注意:
      1. 对于间接递归,不要忘记加入之前的非带入的部分
      2. 消除递归后一定要有一个推出ε的结束条件

自底向上分析 ----------------

优先关系分析

  • HEAD(A)是A可以推导的所有的字符串的第一个字符组成的集合
  • LAST(A)是A可以推导的所有的字符串的最后一个字符组成的集合
  • 注意:
    1. HEAD和LAST集中包含终结符非终结符,不需要消去左递归,可以包含本身
    2. 一定要先加入产生式中的非终结符,每一步推导都要及时加入非终结符
    3. #小于任何相邻的符号
  • 优先级实际上就是可以规约符号的比两边的符号大
  • 所以只用分析一个终结符a与一个非终结符X相邻的情况
    • 如果有aX,则a小于所有X的HEAD集元素
    • 如果有Xa,则X的所有LAST集元素大于a
    • 直接相邻的两个符号相等(#除外),其他没有出现的关系都是未定义的

简单优先文法

  • 简单优先文法满足以下条件
    1. 任意两个符号之间只有一种优先关系
    2. 任意两个产生式有不同的右部
  • 规约过程
    1. 向右加入符号,直到有S[j] > S[j+1]
    2. 再向左寻找,直到有S[i - 1] < S[i]
    3. 将S[i]到S[j]之间的符号取出,查询产生式右部,进行替换
    4. 重复上述操作,直到规约为开始符号
  • 可以看到规约的本质就是可以规约的串大于两端的串,从而进行识别和规约

算符优先分析

  • FIRSTVT集合LASTVT集定义与之前类似,大于小于的情况也类似
  • 但是限定必须是终结符,而且在任意字符串中,可以忽略开始或者结束的非终结符
  • 如果两个符号相邻或者中间间隔一个非终结符,则相等

注意:

  • 无论是简单优先还是算符优先,都不要忘记先加上S’->#S#,否则后面都白做了
  • 对于算符优先,一定要注意可以忽略非终结符的特点,对于等号的判断有较大影响

素短语与最短素短语

  • 素短语是这样的一个短语, 它至少含有一个终结符, 并且除它之外不再含更小的素短语
  • 最左素短语是指处于句型最左边的素短语

简单优先与算符有限比较

  • 两种方法都是自下而上分析法, 但简单优先法是找句柄归约成某个非终结符, 而算符优先法是找最左素短语归约成统一的一个非终结符

LR分析 -------------

最右推导与最左规约

  1. 最右推导指每次使用最右侧非终结符进行推导
  2. 最左规约指每次都将最左侧的符号规约成非终结符
  3. 两个正好是互逆的过程
  4. 最右推导也称为规范推导

活前缀

从S开始,由规范推导产生的任意一个句型中,不超过句柄的部分称为活前缀

LR分析过程

  • 一般RL分析程序由总控程序,分析栈(状态栈和符号栈),分析表构成
  • 开始分析时,先将初始状态和左界符#入栈
  • 分析到某一步时,首先根据栈顶状态S[i]与带读入符号a,查询ACTION[S[i],a]
    • 如果ACTION[S[i],a] = S[j], 则表示要进行移入操作,将a与S[j]入栈
    • 如果ACTION[S[i],a] = R[j], 则表示要进行规约操作
      • 首先根据第j条产生式的要求,将栈顶的k个元素出栈
      • 然后将规约后的符号入栈(设该符号为A)
      • 最后根据GOTO[S[i-k],A]查询相应的状态,并将状态入栈
    • 如果ACTION[S[i],a] = acc, 则表示分析完毕,接受输入的句子
    • 如果ACTION[S[i],a] = ERROR或空白, 则表示分析的句子有错

LR(0)规范族的构造

1. 求闭包

  1. I的项目均在CLOSEURE(I)中
  2. 若A-> a.Bp 属于CLOSEURE(I), 则每一个形如 B-> .r 的项也属于CLOSEURE(I)
  3. 重复2的过程直到CLOSEURE(I)不增加
    注意:
  4. 此处B是非终结符
  5. 一定要重复添加操作,直到小圆点后只有终结符

2. 状态转移

  1. 对于形如A-> a.Bp的项目,产生一条标记为B的弧连接A-> aB.p
  2. 新产生的状态称为核,此节点的值等于核的闭包
  3. 对于形如A->E.的项目,进入了规约状态,不转移到其他状态
  4. 不断的转移获得核和求核的闭包,直到不产生新的状态

3. GO(I,X)的定义

  • GO(I,X) = CLOSEURE(J),其中J = {任何形如A->aX.p的项目|A->a.Xp属于I}
  • 对应到DFA,即为当前节点上通过X弧到达的节点

4. 构造LR(0)分析表

  1. 若项目A->C.aB属于I[k]且GO(I[k],a) = I[j]
    • 若a为终结符,则ACTION[k,a] = S[j]
    • 若a为非终结符,则仅仅置GOTO[k,A] = j
    • 补充: ACTION表中只有终结符的列,GOTO表中只有非终结符的列
  2. 若项目A->c.属于I[k]
    • 则对任意终结符a[i]和#,有ACTION[k,a[i]] = r[j] 和ACTION[k,#] = r[j]
    • 其中r[j]表示第j条产生式
  3. 若项目S’->S. 属于I[k], 则ACTION[k,#] = acc

LR(0)的冲突

  1. 移入-规约冲突
    • 即在一个节点同时包含形如A->E.和A->a.bp这样需要规约或者移入的项目
    • 由于LR(0)不向后查看符号,因此难以确定上述两种产生式如何选择
  2. 规约-规约冲突
    • 即在一个节点上包含形如A->E.和B->F.这样同时多种不同需要规约的项目

SLR(1)分析表构造

  1. 表的基本构造方法与LR(0)相同
  2. 添加额外的冲突解决方法

冲突解决方法

  • 设有一个规范族中有如下一个状态 I = {X->a.bp, A->r., B->d.}
  1. 如果移入符号与各规约符号的FOLLOW集两两不相交,则可以解决冲突
  2. 即 FOLLOW(A)交FOLLOW(B)为空,FOLLOW(A)交{b}为空,FOLLOW(B)交{b}为空
    在此状态的分析报表中,任意一个符号a
  3. 如果a=b 则ACTION[k,a] = I[j]
  4. 如果a属于FOLLOW(A),则ACTION[k,a] = r[j]
  5. 如果a属于FOLLOW(B),则ACTION[k,a] = r[j]
  6. 其他情况,报错

改进的SLR(1)分析表

  1. 基本构造与SLR(1)分析表相同
  2. 对于形如 A->r.的产生式,只有a属于FOLLOW(A)的元素,在表中填入转移状态,其他可以直接报错

说明:

  1. 比较来看,唯一的改进就是对于所有的符号,都按照冲突解决办法,求解了FOLLOW集
  2. 并且对于不在FOLLOW集中的元素,都直接进行了报错处理,从而提前发现错误

LR(1)构造方法

  1. 初始S'->.S,#属于项目I
  2. I的项目均在CLOSEURE(I)中
  3. A-> α.Bβ,a 属于CLOSEURE(I), B->r是文法的产生式,若β∈V*, b∈FIRST(βa),则B->.r,b也属于CLOSEURE(I)
  4. 重复2的过程直到CLOSEURE(I)不增加

注意:

  1. 通常β是终结符,因此没有求FIRST集的过程
  2. 如果β为空,则实际上就是由a决定
  3. 后续的步骤与LR(0)基本相同,但在规约的是时候,只有相应的前向搜索符时才规约

语法制导翻译 -------------

继承属性与综合属性

  • 设有产生式A->α且b = f(c1,c2,..,ck)
  • 若b是A的属性,则b是综合属性
  • 若b是产生式右部的某个符号的属性,则b是继承属性

说明:

  • 综合属性是从语法树下面的属性计算出来的
  • 继承属性是从语法树上面继承下来的
  • 终结符只有综合属性,该属性由此法分析程序提供

语法制导翻译与翻译模式

  • 在语法分析过程中, 随着分析的步步进展, 每当进行推导或归约时, 同步的去执行每个产生式所附带的语义规则描述的语义动作或语义子程序, 这样进行翻译的办法称作语法制导翻译
  • 如果在构造属性文法时把语义规则用花括号括起来, 插入到产生式右部的合适位置上, 用以指明语义规则的计算次序, 这样的属性文法称为翻译模式(或称为翻译方案)

四元式

  • (OP,ARG1,ARG2,RESULT)
  • 四元式直接通过临时变量相互联系
  • 单目运算使用ARG1域,转移语句目标位置放在RESULT域

三元式

  • 编号 (OP,ARG1,ARG2)
  • 其中ARG1与ARG2是指向符号表或其他三元式的指针

间接三元式

  • 结构与三元式相同
  • 间接码表包含一个指示三元式编号的域,其中的出现顺序指示执行顺序

目标程序运行时组织 -------------

运行时存储区结构

  • 目标代码区
  • 静态数据区
  • 栈区
  • 堆区

几个术语

  • name 变量名
  • environment 将名字映射到存储位置
  • storage 存储位置
  • state 将存储位置映射到值
  • value 值

内存分配方式

  • 静态分配
    • 在编译时确定空间,如C中的静态变量,全局变量
  • 动态分配
    • 栈式动态分配
    • 堆式动态分配

代码优化 -------------

代码优化技术

  1. 删除多余运算(删除公共子表达式)
    • 如果统一表达式在多处出现,可以只计算一次,其他地方直接引用
  2. 循环不变代码外提
  3. 强度削弱
    • 将乘法转化为加法
  4. 变换循环控制条件
    • 通过改变循环变量,尝试去除一些变量
  5. 合并已知量和复写传播
    • 编译时初始值已知的运算可以在编译过程中直接计算出来,从而减少运行时运算(合并已知量)
    • 变量T被变量S赋值,后续引用变量T时若T未改变,可改为直接引用变量S(复写传播)
  6. 删除无用赋值
    • 经过变换循环控制条件和复写传播,可能有一些变量被赋值后却没有引用,可以直接删除这些变量

基本块

  • 指程序中一个单入口、单出口的线性程序块(顺序执行的语句序列)
  • 所谓基本块, 是指程序中一个单入口、单出口的线性程序块(顺序执行的语句序列)

入口语句

  1. 程序的第一个语句
  2. 条件转移语句或无条件转移语句的转移目标语句
  3. 紧跟在条件转移语句后面的语句

基本块划分算法

  1. 找到所有的入口语句
  2. 基本块时从入口语句开始到下一个入口语句之前的所有语句
  3. 没有被划分到任何基本块的语句是不可到达的,可以直接删除

基本块内优化方法

  1. 删除公共子表达式
  2. 删除无用代码
  3. 重新命名临时变量
  4. 交换语句次序

最后更新: 2024年03月28日 23:43

版权声明:本文为原创文章,转载请注明出处

原始链接: https://lizec.top/2018/01/13/%E7%BC%96%E8%AF%91%E5%8E%9F%E7%90%86%E7%AC%94%E8%AE%B0/