[TOC]

词法分析

词法单元：进行词法分析的基本单位，输入的源程序中的字符串都要被识别为词法单元进行分析

词素：源程序中被识别为词法单元的字符串。

模式：即词法单元匹配词素用的式子，如正则表达式，简单的字符串序列等

字母表：所有可能输入的字符

有穷自动机FA包含不确定的又穷自动机NFA和确定的有穷自动机DFA。他们的表达能力和正则表达式相同。区别在于： NFA中对于一个符号可以有多条对应的边离开一个状态，且空符号也有边；但是DFA对于一个符号只有一条边离开一个状态，且空符号没有边。我们最终需要DFA。

有穷自动机只会回答对于一个符号串是或者否接收。如果存在一条路径可以到达接受态，而且路径上的边组成了该输入串，则可以接受。

子集构造法

子集构造法用于从NFA构造DFA，它的原理是识别出符号串可能对应的每个状态，并将这个状态集合并为一个状态。简而言之，就是处理空转换和多条相同路径转换带来的问题。

建立NFA，DFA的状态转换表

方法：

先将初始状态A识别为其中s是NFA初始状态。
看依次查看字母表中的符号，例如a，此时将下一个状态B识别为 move(A,a) 即从状态集合A按照路径a所能到达的所有状态。对每个DFA状态，将符号表中的所有符号全部分析一遍
重复以上过程来分析下一个新产生的DFA状态，直到检查完了所有的NFA

其中至少含有一个NFA接受态的集合为DFA接受态。

DFA最小化

每个NFA可能有很多DFA，但是状态数最少的DFA只有一个。也就是有些状态通过任意的相同符号可以到达相同的状态。

若存在一个符号串x，使得不同的状态s，t到达不同的状态，其中一个是接收状态，则s，t可以被x区分。

可以通过算法求得最小状态划分。

先将DFA状态划分为两个状态集，一个非接受态集合，一个接受态集合。
分析上述划分，对于其中的每个状态集，测试每一个符号，此时从刚刚画出的DFA图上分析。若存在一个符号使得s，t状态被区分，则可以从中划分出新的状态集合。
得到新的划分，若该划分与分析前的划分相同，则该划分就是最小状态集合；否则重复上述分析。

即求划分闭包的过程。

最后需要消除死状态。

Thompson算法：从正则表达式得到NFA

先构造正则表达式的语法树：将连接，|（或），*（kleenen闭包），括号，看作运算符。自下而上构造NFA

基本规则：

表达式的NFA生成
表达式的NFA生成（和上面相同）

归纳规则：假设正则表达式s，t的NFA是N（s），N（t）

对于r=s|t，N（r）的生成
对于r=st ，N（r）的生成
对于 r=s* ，N（r）的生成
对于r=（s），N（r）=N（s）

语法分析

文法给出了一个程序设计语言精确易懂的语法规约。

语法分析器依照文法来处理输入的词法单元流。语法分析器大体可分为三种，通用的，自上而下的（即自上而下从根节点开始构建语法分析树），自下而上（即从叶子节点开始构建语法分析树）的。后两种方法分别用在进行LL文法和LR文法的分析过程中。

LL文法：一方面可以描述一个文法的规则，也可以描述对应文法的分析器类型。LL(1)文法即从左到右检测输入流，生成最左推导，每次只向前看1个词法单元。

文法是产生式的集合。一个文法G要选定一个开始符号S（非终结符），从开始符号任意步推导出的符号串都称作G的句型，若句型都由终结符组成，那么也称作句子。

如果推导的过程中每次只选择最左边的非终结符进行推导，则推到过程被称为最左推导。最右推导则反之。对于一次推导，我们可以在推导的每一个阶段的句型构造一个对应阶段的语法分析树，推导结束则语法分析树的构造结束，产生最终的句子，即语法分析树自左向右的所有叶子节点。推导过程对应语法分析树的构建。

二义性：相同的文法，对于相同的输入流，选择不同产生式，能够造出不同的语法分析树。

上下文无关文法：表达能力强于正则表达式，

二义性文法可以被消除。

左递归文法的消除：若存在推导AAa（+ 一步或多步），则这个文法左递归。自顶向下方法不能处理左递归文法。（因为每个非终结符在分析的过程中对应一个过程或者函数，如A对应有一个函数A()来处理它，若出现左递归，则要么分析出现错误，要么就是无尽递归循环，不停进入A()过程）

可以化为 :

提取左公因式：

即改写产生式，无法决定产生式的选择时，将产生式的选择推后，等到积累了足够多的信息再进行产生式子的选择。如何改写？提取左公因式。

变成

Tip：这里所说的文法都是默认上下文无关的，上下文有关文法的实现如变量的声明后调用，可以在语义分析阶段完成（当然也可以在语法分析时完成，但比较困难）

自顶向下的语法分析

为输入串经过深度优先的创建语法树节点，构建语法分析树的过程。等价于寻找最左推导的过程。

确定一个非终结符号应用哪个产生式
将产生式体中的终结符号和输入流匹配

递归下降语法分析是自顶向下分析的通用形式，这种方法可能需要回溯。一个递归下降的语法分析有一组过程组成，每个非终结符号有一个对应的过程。程序从开始符号对应的过程开始，如果该过程扫描了整个输入符号流，则分析结束。

回溯要求重复扫描输入，并按照顺序尝试非终结符所有的产生式，仅当所有产生式都和输入不匹配才报告错误。所以输入流的指针需要被保存，以便尝试新的产生式时进行还原输入流位置。

FIRST & FOLLOW

FIRST和FOLLOW帮助我们根据下一个输入选择应用哪个产生式。FIRST(a)是可从a（任意文法符号串）推导出的串的首终结符集合；FOLLOW(A)是可能在某些句型中紧跟在A右边的终结符集合。

计算FIRST(a):

若a是终结符，则FIRST（a）=a
若a是非终结符且拥有：则若A^1^A^2^可以在任意步推到到空，且a在FIRST(A^3^)中，则a可以被加入FIRST（A）。即

FIRST（A^1^）的所有符号一定在FIRST（A）中，但是若A^1^不能推导到空则就不能往FIRST（A）中增加任何字符以此类推。

若 , 则FIRST（A）中可添加

计算FOLLOW（A）：

先将FOLLOW （S）中添加$(结束符)
若存在则FIRST（b）中所有字符（除了空）均在FOLLOW（A^1^）中。
若存在，则FOLLOW（A^1^）包含了FOLLOW(A)

SELECT（）即需要选择产生式的终结符集合。SELECT（）= ( FIRST（a）- {} ) FOLLOW（A）

LL(1)文法的充要条件就是 SELECT（） SELECT（）=

LL（1）文法

对于非终结符任意两个不同的产生式，FIRST（a）和FIRST（b）是不相交的集合，这样才能通过一个终结符识别产生式的选择；若则FIRST(b)和FOLLOW（A）需不相交。

通过将FIRST FOLLOW集合中的信息放到预测分析表（一个二维数组）中，来实现产生式的选择。行为各种终结符和结束符，列为非终结符，表内是各种的产生式，空项代表错误。

对于产生式，查看FIRST()中的所有终结符a，将该产生式放入TABLE[A][a];
若存在于FIRST（），则查看FOLLOW（A）中的所有终结符b，并将产生式放入TABLE[A][b]；若 $存在于中，则同时将产生式放入$ ]中。

通过预测分析表，可以制造一个表驱动的预测分析器。它由一个栈结构（包含文法符号），输入流，和分析程序组成。

开始时，栈顶是开始符号S，栈底是结束符号$。通过查看栈顶的符号和当前输入流指针下的符号.
若为非终结符，在表中选择一个合适的产生式，然后弹出栈顶，将产生体自右向左放入栈内；
若为终结符，则查看是否和输入流指针下的符号相同，然后弹出栈顶，移动指针。
重复上述操作，直到检查到栈底的$.

自底向上的语法分析

移入-规约语法分析是自底向上语法分析的通用框架。LR文法类可以构造出移入-规约语法分析器。

规约：可以看作是推导的逆过程，即将某一个与产生式体相匹配的特定子串替换为产生式头部的非终结符。若最终归约到开始符号S，则规约完成。其中被替换掉的子串成为句柄。句柄的右边必定都是终结符。因为规约形成最右推导的逆过程，所以规约每次只能替换最左边的符号，即自左向右替换

移入：在移入规约语法分析中，类似LL1的预测分析器，需要一个栈保存文法符号，一个缓冲区保存输入流。开始时栈只有一个$。每次将输入流移入栈顶，直到栈顶的符号（即句柄）可以被规约。直到检测到语法错误或者栈顶为S且缓冲区为空。这样正好是自左向右替换输入流符号，与上面的想法不谋而合。

可能的冲突：知道了输入流前几个字符但不确定是继续移入还是规约；规约时不知道选择哪个产生式。（通过设置复杂的词法单元名以及使用离栈顶很远的信息来进行规约选择）

LR文法

通过建立语法分析表和移入-规约语法分析器，实现LR语法分析

LL(*) 文法优先级上升算法

可以处理二义性文法（比如优先级带来的二义性文法），直接左递归（无法处理间接左递归）

precedence（优先级）

predicates（谓词）

优先级上升算法可以改写原文法，使之二义性和左递归消除（变为迭代版本）。

先对原来的文法中的一个非终结符的每个产生式分配一下优先级。（可以看作运算符的优先级）

将非终结符的处理写成一个递归函数，函数有一个参数即优先级。与非左递归的匹配作为基线条件。而左递归的匹配变为迭代版本且产生式的选择有条件限制，即优先级要满足条件。默认开始时的调用优先级是0.

同时，对于左递归的匹配，外层有一个星号，对应一个while循环，即在某个优先级下的循环匹配。while循环便于往深处递归和返回到上一层（若都不匹配或优先级不够无法执行），在不同优先级下对非终结符进行匹配。

不同优先级对应一个语法树的深度。优先级越大，语法树的深度越大，如果优先级不够，就不能在语法树的这个层数上匹配（展开）非终结符。下面的文法中也可以看出来，乘法的优先级大于加法。

根本问题：在非终结符当前调用中匹配下一个运算符还是让该非终结符的调用者匹配下一个运算符。

左结合的，优先级上升一级（比自己的优先级大1），右结合的优先级不变（如右图）。

前缀运算符的不是左递归的，而且是右结合的，所以放到基础条件处理，而且调用时，优先级不变（使用自己本身的优先级）。

后缀运算符是左递归的，左结合，所以到while循环处理，而且优先级上升一级。

语法制导的翻译

语法制导的翻译是通过语法分析的结果或者说是伴随语法分析进行语义分析。

SDD是语法制导定义，其中包含与符号关联的属性和与产生式关联的（语义）规则。属性反映了符号的语义信息，而规则定义了属性的产生过程。

属性分为综合属性syn和继承属性inh。综合属性只能从符号对应语法树节点N的自身属性或者子孙节点来定义，即该符号一定是产生式头的符号。继承属性可以通过符号对应节点本身属性，父节点，兄弟节点来定义。

只有综合属性的SDD也叫S属性的SDD，两种属性都有的的SDD也叫L属性的SDD。没有副作用的SDD也叫属性文法。（副作用：即在规则中执行一些与属性定义无关的语义动作，如属性的打印，对符号表的访问）

对于终结符的属性定义是词法分析器给予的。语法制导定义只需对非终结符的属性进行定义。

标注语法树是指在语法分析树的基础上，对节点标注对应的属性值。

确定语法树上节点属性值的求值顺序是十分关键的。S属性的SDD可以对语法树进行后序遍历（自底向上便利）实现每个节点属性的计算。（如果是LR语法树，则可以在构建语法树的同时进行翻译，因为都是自底向上的分析）

L属性的SDD也可以通过自底向上遍历实现属性的定义。但是继承属性要满足：若在产生式中求的继承属性，则只能使用

A的继承属性
之前的和本身符号的属性（继承/综合）
上述属性不存在依赖环（属性不能循环依赖）

在语法树上体现为，节点a只能使用他左上的节点属性。（右边的继承属性传不过来）继承属性可以将信息从语法分析树的一边传递到另一边。

SDD中可以加入受控的副作用，即在SDT（语法制导的翻译方案）和SDD中找到一个平衡。只要副作用不对属性求值产生影响。如抽象语法树的生成就可以在规则中加入生成结点的语句来实现。

语法制导的翻译方案SDT

SDT是在产生式体中任意位置插入语义动作的上下文无关文法。语义动作用花括号包括。是对SDD的一种补充。SDD可以被转化为对应的SDT。任何SDD的应用都可以通过SDT实现。

SDT通过构建一个语法分析树，对其进行前序遍历（从左到右的DFS，自顶向下）来实现。当然也可以在构建的过程中同时实现。当语法动作之前的非终结符全部分析完成后，语义动作立刻执行。

SDD
- 是关于语言翻译的高层次规格说明
- 隐蔽了许多具体实现细节，使用户不必显式地说明翻译发生的顺序
SDT
- 可以看作是对SDD的一种实现，是SDD的具体实施方案,需要紧密关联语法分析时的细节
- 将代码片段嵌入产生式，显式地指明了语义规则的计算顺序，以便说明某些实现细节

中间代码生成

中间表示有抽象语法树和三地址代码。这里介绍三地址代码。

通过语法制导的翻译实现中间代码生成。有简单模式（只有综合属性），困难模式，回填技术等。使用复杂技术可以生成效率更高的中间代码。

主要的翻译目标有：赋值语句，布尔表达式，if语句，while语句，break，continue语句，布尔表达式短路求值。

简单模式：

目标代码生成 RISC-V

指示符

三个段与x86相同 .text .bss .data

.global main 指定全局符号（入口函数）

.string “str”	将字符串str放入内存
.byte b1,…,bn	在内存中连续存储n个单字节
.half w1,…,wn	在内存中连续存储n个半字(2字节)
.word w1,…,wn	在内存中连续存储n个字(4字节)
.dword w1,…,wn	在内存中连续存储n个双字(8字节)
.float f1,…,fn	在内存中连续存储n个单精度浮点数
.double d1,…,dn	在内存中连续存储n个双精度浮点数

如：

在内存定义一个变量j 初始化为0 ，大小4Byte‘

$，，，，$

寄存器

RISC-V 32个通用寄存器均可以用来表示，但也有别名

zero，0号寄存器，永远为0

ra（return address），保存函数调用返回地址

共7个临时寄存器

pc 下一条指令地址位置

指令

常用指令：

用于寄存器和寄存器之间操作的R类型指令

算术指令：add, sub

逻辑指令：add, or, xor

移位指令：sll, srl, sra

均有立即数版本可以符号拓展
用于短立即数和访存load的I型指令
用于访存store的S型指令
用于条件跳转的B型指令
用于长立即数的U型指令
用于无条件跳转的J型指令

**li , 100 #加载立即数到寄存器 **

addi t0 , zero , 100 #寄存器和立即数相加等价于上面的指令

add t2 , t1 , t0

sub t6， t2, t5 #将t2-t5并存入t6 没有subi

mv t1 , t0 #将t0移到t1中

加载

la t0，j #直接将变量j的地址加载到t0 （绝对地址加载）

lw t0 , 0(t0) #将t0中保存的地址+偏移量作为首地址，往后获取4个Byte的内容，偏移量是按照字节为单位计算的

同理还有lb lh

可以直接从变量地址加载变量内容 lw t0，a

la t0 , result

sw t6 , 0(t0) #将t6中的值存到t0保存的位置（即result位置）上

上面两行同理可以压缩为 sw t6 , result , t0 (t0是用来暂存result地址的)

跳转

bge t0,t1 label #若t0>=t1则跳转

bltz t5 , label #若t5<0则跳转

j label #无条件跳转

系统调用

根据a7寄存器的值来确定系统调用的类型，即a0-a7是用来传参的（函数调用也是用它们）

ecall进行系统调用

1是进行print打印整数
4是进行print打印字符串

函数调用

传参时，将变量的值放入a寄存器中，如

lw a0 , a #将内存中a变量的值加载到a0中
jal ra，max 指令调用函数max，同时保存返回地址到ra

可以简化为 jal max ；可以更简化为call max
返回值约定俗成，可以保存在a0，a1
函数max调用结束后使用jalr zero, 0(ra) 跳转到ra指定地址，同时将max下一条指令保存在第一个寄存器（这里保存在zero，可理解为扔掉了）

可以简化为 jr ra ;可以**更简化为 ret **

使用栈来保存寄存器状态

如递归调用，可以先保存原寄存器值到栈中，调用函数，完成后再把寄存器值从栈中取出来。

addi sp ,sp -8 #栈指针下移8Byte

sw a0 , 4(sp) #将a0保存在栈顶指针处

sw ra , 0(sp) #

call func

mv t0 , a0 #保存a0值（不然返回值没了）

lw a0, 4(sp) #还原a0

lw ra, 0(sp) #还原ra

调用者需要自己保存a0-a7，ra ，以及t寄存器的值来保证值可以恢复。

被调用者需要保证sp的值在调用前后不变。压了多少栈就弹出多少

若调用链长，ra必须被保存到栈中

大二下编译原理总结