概论

编译和解释

编译器就是要生成一个程序后才能执行。

解释器将代码一行行执行。

编译过程

词法分析 -> 语法分析 -> （语义分析、中间代码生成） -> 循环优化 -> 生成目标代码

编译的T型图

左臂上是初始语言，右臂上是目标语言，下面是编译器语言

自增和移植产生代码

自增就是通过自己的语言（比如汇编）先编译一小部分目标语言，假设目标为C语言，则可以分为small C middle C large C三个部分，编译出small C，然后结合small C编译middle C这样子。

移植就是更改语言类型。

基本概念

程序语言的定义

语法是指一组规则，可以分为词法规则和语法规则

词法规则

规定了单词符号（变量名运算符那些）的形成规则，描述工具为有限自动机

语法规则

即如何从单词符号形成更大的结构（语法单位），描述工具为上下文无关文法

程序语言的语法描述

基本概念

  • 字母表

    符号的非空有限集

  • 符号串

    即符号的有穷序列，空符号串用ϵ\epsilon表示

  • 符号串集合

    定义很直观了，就是符号串构成的集合

  • 符号串的运算

    • 相等

    • 长度

    • 积

      就是两个连起来，且连起来的积也是Σ\Sigma上的符号串

  • 符号串集合的运算

    • 乘积

      按顺序枚举连接即可得到，如A={s,t},B={u,v} AB={su,sv,tu,tv}

    • 幂运算

      就按乘法来就可以

    • 闭包

      A+=A1∪A2∪...∪AnA^+=A^1 \cup A^2 \cup ... \cup A^n为正闭包

      A∗=A0∪A+A^* = A^0 \cup A^+为A的闭包

约定

  • 非终结符

    A,B,C

  • 终结符

    a,b,c

  • 终结符/非终结符

    X,Y,Z

  • 终结符号串

    x,y,z

  • 终结符/非终结符构成的符号串

    α,β\alpha,\beta

  • 在产生式A->α\alpha中

    A是产生式的左边

    α\alpha是产生式的右边

文法

一组规则用"::="表示定义为，比如A::=α\alpha，A为非终结符，称为产生式的左边部分，α\alpha是由终结符或非终结符组成的一串符号，这种规则称为巴科斯范式（BNF）

文法定义为一个四元组(VN,VT,P,SV_N,V_T,P,S)

  • VNV_N为非终结符号集
  • VTV_T为终结符号集
  • P为产生式（规则）集合
  • S称作开始符号，至少要在一条规则中作为左部出现

例如文法G=({S}, {0,1}, {S->0S1, S->01}, S)或者简写为G[S]: S->0S1, S->01

句子

文法推出的只有终结符组成的符号串

语言

文法推出的句子的集合，用L(G)表示

等价

即判断L(G1) == L(G2)

二义性

最左推导

在推导的任何一步α=>β，其中α、β是句型， 都是对α中的最左(右)非终结符进行替换

若一个文法存在某个句子对应两棵不同的语法树(或一个文法存在某个句子有两个不同的最左(右)推导)，则称这个文法是二义的

词法分析

术语

词法单元(token): 由词法单元名和可选的属性值组成

词素(lexeme)：词法单元的实例

模式(pattern)：词素可能实例组成的集合

词法分析器

例子

对于while(i == j) i++这个语句，词法分析是逐个识别输出的。

  1. <$WHILE, _>

  2. <$LPAR, _>

  3. <$ID, pointer to i>

  4. <$EQUAL, _>

  5. <$ID, pointer to j>

    …

其中第一个元素为单词符号的助忆符，第二个为可选的属性值，例如第三行就是指向i的指针。

主要功能

  • 读取源程序生成单词符号
  • 过滤注释和空白
  • 关联编译器生成的错误与源程序的位置。

但是得注意，它只能处理不符合合法标识符拼写的错误，其他的错误只能交给其他阶段完成，但是可以完成错误链接的步骤。

设计结构

由预处理和扫描器两部分组成。预处理将源程序文本进行扫描，减去一些/\t/符号，并放置到扫描缓冲区中，等候扫描器来处理。

对于扫描缓冲区，如果只有一个顺序缓冲区，预处理程序和扫描器程序只能交替进行，即写完再读，但是通过双缓冲区的技术，将两个缓冲区的头尾连接，能够边写边读，可以大大提升速度。

状态转换图

为一个有限方向图

  • 结点代表状态
  • 状态之间用箭弧连接
  • 箭弧上的标记字符代表起始结点状态下

双圆圈代表最终状态或接收状态

image-20210315142248976

如过终态结点上打了一个星号，意味着多读进了一个不属于标识符部分的字符时，退回给输入串。

状态转换图的实现

将每个状态结点对应一段程序，转换即可。

正则表达式和有限自动机

正则表达式和正则集

  1. ϵ\epsilon和∅\varnothing是Σ\Sigma上的正则式，其正则集为{ϵ\epsilon}和∅\varnothing
  2. 任何a∈Σa\in \Sigma，a是Σ\Sigma上的一个正则式，正则集为{a}
  3. 假定U和V都是Σ\Sigma上的正则式，正则集为L(U)和L(V)，那么对UV的交并闭包，也能产生正则集

例子

image-20210315145818981

正则式运算

相等

当且仅当两个正则式的正则集相同时，记为U=V

交并规律

跟集合操作类似

有限自动机

有限自动机作为一种识别装置，能够准确地识别正则集合，即识别正则文法所定义的语言与正则式所表示的集合。

分为确定和不确定的有限自动机(DFA和NFA)，如果在同一个状态上存在不止一种的转换，我们定义这个自动机为不确定的。

DFA

定义为一个五元式 M = (S,Σ,δ,s0,FS, \Sigma, \delta, s_0, F)分别为有限集，有穷字母表，单值映射，初态和终态集。

NFA

相比DFA单值映射变为了到S集合的单值映射，初态也变成了非空初态集，终态是一可空的终态集。

NFA的确定化

先来定义对状态集合I的几个有关运算：

  • ϵ\epsilon-闭包，定义为一状态集，包括
    • I中的任何状态s
    • I中s经过任意条ϵ\epsilon能够到达的状态的集合
  • a弧转换Ia=ϵ\epsilon-closure(move(I, a)) = ϵ\epsilon-closure(J)，J定义为可从I的某一状态经过一条a弧而到达的状态的全体.

DFA最小化

即寻找一个状态数更少的DFA M’ 使得L(M) = L(M’)

最小DFA有两个条件

  • 不存在多余状态
  • 不存在相互等价的两个状态

最小化算法的核心就是将状态集分为不相交的子集

image-20210317115032453image-20210317115047251

正则式和有限自动机的相互转换

见PPT

词法分析程序的自动生成

通过写正则表达式描述词法规则，然后通过LEX可以可以生成将源代码变为单词和字符串的词法分析器。

LEX程序分为两部分：正则定义式为（简名->正则式）的组合，以及识别规则。即正则定义式和其识别出来后的动作。

LEX的工作过程就是将LEX源程序编译成一个.c文件，再通过C编译器编译成一个词法分析器。

自顶向下的语法分析

语法分析器的原理就是识别输入的符号串是否为一个正确的句子。

LL(1)分析法

LL(1)中的第一个L表示从左到右扫描输入串，第二个L表示最左推导，1表示分析时每一步只需向前查看一个符号。

满足条件

  • 不含左递归
  • 非终结符的产生式的FIRST集之间没有交集
  • 对于每个非终结符，如果存在某个FIRST集包含ϵ\epsilon则FIRST和FOLLOW集没有交集

改造成ll1文法

消除左递归

掌握此公式即可

image-20210322153137185

但是这个只能消除直接的左递归，对间接的，例如 A->B B->Ac就得有带入算法

一般算法

image-20210322154143978

消除回溯、提取左因子

非终结符的候选首符集之间没有交集时，则消除了回溯。对于有交集的首符集可以采取提取左因子的形式，引入新的非终结符来消除回溯的可能。

FIRST和FOLLOW的推断可以看这个https://www.gatevidyalay.com/first-and-follow-compiler-design/

预测分析程序

程序由一个栈和一个预测分析表组成，输入为串w和文法G的分析表M，输出如果w∈L(G)w\in L(G)则产生w的最左推导，否则输出错误信息。

预测分析表由First集合Follow集构成，具体方法为：

image-20210329153500372

预测分析的方法为

image-20210329153623426

例子

image-20210329153958974

自下而上的语法分析

移动归约法

短语、直接短语、句柄

image-20210329154922700

短语即一颗子树（包括根所在的）上的叶子从左到右连成的句型。

直接短语就是深度为2的子树对应的短语。

规范归约

image-20210329160816870

例子

image-20210331103209586

算符优先分析法

关键是定义两个可能相继出现的终结符之间的优先关系， 并根据这种优先关系寻找“可规约串”并进行规约(非规范规约)。

算法文法

image-20210331104404298

但是要注意，a优先于b不能推出b次优先于a，优先没有传递性。

如果a<`b，则a和b不在一个句柄中，b先被归约，

a=`b，则a和b在同一个句柄中

a>`b，则a先被归约

素短语

素短语指至少含有一个终结符，并且除了本身以外没有更小的素短语。

最左素短语就是句型最左边的素短语，并且这就是算符优先分析法的可归约串。

一个算符优先文法的句型为如下形式

#N1a1N2a2...NnanNa+1#\#N_1a_1N_2a_2...N_na_nN_{a+1}\#

其中ai是终结符，Ni是可存在或无的非终结符。

FIRSTVT LASTVT

image-20210412222914196

其实就看最后两句话就行，这两种集合就是用来构建表的。

构建FIRSTVT§的算法

  1. 若有P->a，或P->Qa，则将a加入集合
  2. 若有a在Q的FIRSTVT集合中，又有P->Q，则a也在P的FIRSTVT中。

算法思想

用栈存储输入符号，用优先关系判断是否进行移动还是归约。

例子

image-20210412232128314

总之就是遇到<或者=就移进，>就归约，优先关系为栈中最顶上的终结符和当前符号的比较。

改进

利用优先函数改进算符优先级的存储数组（n方空间复杂），只需要用线性复杂度即可。

LR分析法

LR分析的优点有以下几点:

• LR语法分析器能识别几乎所有能用上下文无关文法描述的程序设计语言的结构。

• LR分析法是已知的最一般的无回溯移动归约语法分析法，而且可以和其他移动 归约分析一样被有效地实现。

• LR分析法分析的文法类是预测分析法能分析的文法类的真超集。

• 在自左向右扫描输入符号串时，LR语法分析器能及时发现语法错误。

这种分析方法的主要缺点：

对典型的程序设计语言文法，手工构造LR语法分析器的工作量太大，需要专门的工具。

基本思想

LR分析法的基本思想是，在规范归约过程中，一方面记住过去已经移进和归约出的整个符号串，另一方面用产生式推测未来可能遇到的输入符号。

LR分析器结构

表分为ACTION表和GOTO表，ACTION[s ,a]规定了当前状态s面临输入符号a时应采取什么动作。 GOTO[s, X]规定了状态s面对文法符号X(终结符或非终结符)时下一个状态是什么。

即ACTION规定了面临输入符号采取的动作，GOTO规定了状态面对一个符号的下一状态

ACTION表

ACTION表中对应的动作有4种，分别是移进、归约、接收和报错。

image-20210419144408429

例子

image-20210419144506814

LR文法

如果能为一个文法构造一个分析表使得其每个入口均是唯一确定的，则这个文法为LR文法。

如果一个文法能用每步顶多向前检查k个输入符号的LR分析法称为LR(K)文法。

LR(0)项目集族的构造

前缀即一个字的任一首部。

活前缀是指规范句型的一个前缀 ，规范句型就是规范推导推出的一个句型。

项目

一个项目即指产生式右部的符号间插入一个圆点，即是一个LR(0)项目。

例如A->BC

有3个项目A->·BC,A->B·C,A->BC·

如何理解一个项目的作用，我个人认为是推导的百分比，点在最前面的时候皆有可能，对于A->B·C来说，指推导到了B这个符号，可能会推导出C（因为不知道是否有其他的，我们这只举出了一个产生式）。

项目分类

对项目我们也能进行分类

  • 归约项目

    凡圆点在最右的项目，如A→α•称为一个“归约项目”

  • 接受项目

    对文法的开始符号S’的归约项目，如S’→α•称为“接受”项目。

  • 移进项目

    形如A→α•aβ的项目，其中a为终结符，称为“移进”项目。

  • 待约项目

    形如A→α•Bβ的项目，其中B为非终结符，称为“待约”项目

构造过程

首先我们要从文法G构造一个G’文法，它包含了整个G，只是在文法中引入了一个不存在的非终结符S’，并指向文法的开始符号，G’被称为扩广文法，通过扩广文法，我们就有了唯一的一个接收状态。

构造过程分为两种，一种是通过接收状态开始推导，先构造NFA，再进行NFA确定化，但相对来说比较繁琐。

所以我们使用ϵ−closure\epsilon-closure的方式来构造项目集规范族。

构造CLOSURE(I)的方法是：

  1. 将I中所有项目加入集合
  2. 对任一·后是非终结符B的，将非终极符B在左边的产生式的项目B->·y加入集合
  3. 重复12步直到无法增大

GO函数

GO函数在构造项目集规范族中起作用。

对I0I_0中，假设有项目A->·aB，则可以令G(I0I_0,a)=I1I_1为一个转化函数并且I1I_1就是CLOSUER({A->a·B})

分析表的构造

image-20210419185255121

LR(0)文法

我们说G是一个LR(0)文法的条件是G’的每个项目集都不存在以下情况

  • 含移进项目和归约项目
  • 含有多个归约项目

SLR分析法

由于LR(0)文法可能存在移进归约冲突和归约归约冲突，即某个项目集中可能同时包含移进项目和归约项目或者含有多个归约项目，便有了解决冲突的SLR分析法。

SLR利用了非终结符的FOLLOW集来解决冲突。

具体解决方式为，如果能移进，则选择合适的项目进行移进，如果没有则选择输入符号a所在的FOLLOW集对应的非终结符的对应项目进行归约。这种解决方法被称为SLR(1)解决方法。

SLR语法分析表的构造算法

image-20210419185327609

规范LR语法

我们学习完SLR语法，能够发现其虽然解决了一些LR语法中的冲突问题，但是其自身仍然存在冲突，可能存在归约和移进的冲突。所以有了规范LR语法分析，给出如下解决方案：

重新定义一个项目，使其包含一个终结符串作为第二个分量，包含更多的信息。

于是一个项目的一般形式变成[A->α⋅β\alpha·\beta, a1a2…an]

其中a1a2…an被称为向前搜索符串，这样的一个项目意味着，将α\alpha归约成A的条件是，项目的状态为当前状态，且后续k个输入符号为a1a2…an。但是在这里只讨论k<=1的情况，即LR(1)

CLOSURE闭包

要计算CLOSURE闭包我们需要定义：一个项目[A->α⋅β\alpha·\beta, a]对活前缀γ有效，是存在规范推导S=>δAω=>δαβω:

• γ=δα

• a是ω的第一个符号，或者ω是空串，a是#。

于是有CLOSURE(I)闭包：

  • I的任何项目都属于CLOSURE(I)

  • LR(0)项目的选取类似，向前搜索串定义为:

    若有[A->α⋅Bβ\alpha·B\beta, a]，B->·k为一个LR(0)项目，则将First(βa\beta a)中的每一个非终结符b，将[B->·k, b]加入CLOSURE

  • 重复上面两步

语法分析表构造

image-20210420200147373

语义分析

属性文法

属性的计算

属性有综合属性和继承属性两种

综合属性是自下而上传递信息

继承属性是自上而下传递信息

对出现在产生式右边的继承属性和左边的综合属性必须提供计算规则，如果有在左边的继承属性和右边的综合属性由其他产生式决定。

例如A->BC，A的综合属性和BC的继承属性由这条产生式的计算规则提供，如果要求A的继承属性，则去找右端为A的产生式的计算规则，对BC的综合属性类似。

综合属性

结点的综合属性由其子节点的属性值决定。通常采用自底向上的方法计算综合属性。

继承属性

结点的继承属性由父节点或兄弟结点的某些属性决定，因此是自上而下的。

L属性文法的自上而下翻译

我们称一个属性文法是L属性文法是：

对每一个产生式A->X1X2…Xn，其语义规则中的每个属性，要么是综合属性，要么是继承属性且仅依赖于A的继承属性和左边符号的属性。

语法制导翻译

语法制导翻译给出了使用语义规则进行计算的次序，这样就可以把某些细节表示出来。语义动作用花括号括起来，插入到产生式右部的合适位置上。并且在语法分析树上将花括号的内容作为一个结点构造语法树。

例如

image-20210421104256138

设计过程

  • (最基本)当动作引用某个属性时，这个属性必须是可用的。
  • 只有综合属性时，为每一个语义规则建立一个包含赋值的动作，并且把动作放在末尾
  • 同时存在综合属性和继承属性时
    1. 产生式右部符号的继承属性必须在这个符号以前的动作中计算出来
    2. 一个动作不能引用右部符号的综合属性
    3. 产生式左部非终结符的综合属性只有在其引用的所有属性值都计算出来以后才能计算。计算该属性的动作通常放在产生式右部的末尾。

为了实现不带回溯的自顶向下语法分析，需要消除左递归。