计算方法：表格第一列是DFA状态，每当有一个新的NFA集合时加入一个新项，第二列NFA，NFA的第一行是由开始状态0开始出发经过空串能够到达的状态。输入字符有a和b，a的第一列为NFA的第一列中的状态集合经过a能够到达的状态组成的集合，这个集合的空串闭包。b的第一列是NFA中的第一列中的状态集合经过b能够到达的状态组成的集合，这个集合的空串闭包。上述过程中若出现新的NFA状态集合，则写在左边称为DFA的新状态。以此类推直到没有新的DFA状态为止。最后根据这个图画出DFA，这个图实际上为DFA的状态转换图。计算完之后，看看原来的NFA的结束状态在哪个DFA状态所代表的NFA状态集合中，哪个DFA状态就是结束状态

1.别忘了计算闭包的时候是在自身的基础上往上加东西，就像计算第一个NFA集合的空串的时候是要在第一个NFA集合的基础上加，！！！但是计算move函数的时候不是！！！

2.同时只有闭包完之后的才算新状态，只是move了不算

描述：先计算出{0}这个状态的空串闭包I0，为DFA的初始状态，然后看输入符号，有a和b那么分别对I0求move（I,a）,move的结果再求空串闭包，即分别为DFA状态I0经过标号为a的边到达的DFA状态，若这个状态之前没有出现过，则这是一个新状态，加入到DFA状态集合中。以此类推，直到不再出现新状态为止。

9.DFA最小化（Hopcroft算法）

•通过DFA的最小化, 可得到状态数量最少的DFA (若不计同构，则这样的DFA是唯一的

（1）.DFA中状态之间的可区分关系

–对于两个状态s1和s2，如果存在串x，使得从状态s1和s2出发，一个到达接受状态而另一个到达非接受状态，那么x就区分了s1和s2

–对于两个状态s1和s2，如果存在某个串区分了s1和s2，我们就说s1和s2是可区分的，否则它们是不可区分的

（2）.从Пfinal的每个组中选择一个代表状态，作为新DFA中的状态

•开始状态就是包含原开始状态的组的代表

•接受状态就是包含了原接受状态的组的代表(这个组一定只包含接受状态)

（3）.−构造转换关系

•如果s是G的代表，而原DFA中存在从s经a到达t的转化，且t所在组的代表为r，那么最小化DFA中有从s到r的经a的转换

（4）例子：

-初始划分：{ { A, B, C, D }, { E } }

-处理{ A, B, C, D }：b把它细分为{ A, B, C }和{ D }

-处理{ A, B, C }：b把它细分为{ A, C }和{ B }

-选取A, B, D和E为代表，构造得到最小DFA

AC用A来代表，把指向C的指向A，把C出发的改为由A出发

10.Lex中的冲突解决方法

冲突：多个输入前缀与某个模式相匹配，或者一个前缀与多个模式相匹配

–多个前缀可能匹配时，选择最长的前缀

•比如，词法分析器把<=当作一个词法单元识别

–某个前缀和多个模式匹配时，选择列在前面的模式

•如果保留字的规则在标识符的规则之前，词法分析器将识别出保留字

二、语法分析

1.上下文无关文法(Context-Free Grammar)

一个上下文无关文法 (CFG) 包含四个部分

−终结符(terminals)：其实就是tokens

−非终结符(non-terminals)：语法变量

•通常对应于某个程序构造，比如statement(语句)

−产生式：描述终结符和非终结符如何组成串

−开始符：某个被指定的非终结符

格式：头→体

program → statement program

program → ϵ

statement → expression;

statement → if ( expression ) then statement

statement → if ( expression ) then statement else statement

statement → while ( expression ) statement

2.推导

将非终结符替换为它的某个产生式的体

一次替换称推导，连续多次替换也称推导

最左，最右推导：

都是对α中的最左非终结符号进行替换的，同样可定义最右推导。

对于： 1. S->AB|c 2. A->aA|b 3. B->Bc|b;

则最左推导是S->AB->aAB->aaABc………….;

最右推导是:S->c

例：构建一个文法G=abbc

      则此时的最左推导是S->AB->aABc->abbc
 
      则此时的最右推导是S->AB->aAB->abB->abbc

(推导已有文法，最左推导就是优先使用最左非终结符来替换保证符合条件，最右推导也是如此)

3.句子句型和语言

句型：文法S推导出a，则a是文法S的句型，可能包含终结符也可能包含非终结符，也可以是空。

最左句型，最右句型：

经过最左（最右）推导得到的句型

句子：不含非终结符的句型

语言：文法G的语言L（G）是G的所有句子构成的集合

4.语法分析树

（1）定义

推导过程的图形表示

–根结点的标号是文法的开始符

–每个叶子结点的标号是非终结符、终结符、或ε

–每个内部结点的标号是非终结符

–每个内部结点表示某个产生式的一次应用

•结点的标号为产生式的头，其子结点从左到右对应产生式的体

树的所有叶子组成的序列是根(开始符)的一个句型

推导侧重描述程序是如何生成的(how to produce)，而解析树侧重描述程序的结构(structure）

例子：

（2）推导和解析树的对应关系

推导和解析树是多对一的

−给定文法和某个句子，可能有多个推导对应一棵解析树

最左推导和解析树是一对一的

−给定文法、某个句子和某个最左推导，只可得一棵解析树

最右推导和解析树是一对一的

−给定文法、某个句子和某个最右推导，只可得一棵解析树

5.二义性及其消除

（1）定义

二义性 (Ambiguity)：给定文法，若存在某个句子，有多个最左/右推导，即可以生成多棵解析树，则这个文法就是二义的

（2）消除二义性

二义性主要有两个来源：

−算术表达式（算符结合性二义，算符优先级二义）

−悬空else（dangling else，else与哪个then匹配二义）

消除二义性有两种常用方法：

−改写原文法(rewriting)

−引入消除二义性的规则(disambiguating rule)

二义性的消除方法没有规律可循

（3）改写原文法，实现左结合

（4）改写原文法，实现右结合

（5）改写原文法，确定优先级

（6）不改变原文，引入二义性消除规则

6.语法分析技术：自顶向下算法

（1）回溯算法

基本思想

1.采用深度优先策略(对应最左推导)，通过扩展和匹配来构建解析树

2.对于非终结符孩子，扩展；对于终结符孩子，从左至右，依次检查它是否与输入匹配

3.若在某步出现不匹配，停止扩展，回到前一个非终结符，并选择其另一个产生式（backtracking）

可将体中待处理的符号存于栈中，以实现深度优先

因是最左推导，得以自左向右处理输入

缺点

1.对某些文法，算法会陷入无限循环（或递归）（左递归）

•例子： E → E + id |id id + id

2.对于简单文法尚可应付，对于复杂文法，往往因频繁回溯，耗时过多，从而不堪用；特别地，若输入串有语法错误，则最坏时间复杂度是指数级的

消除左递归

1.观察一下原来的文法描述了一个怎样的句子，再去做，注意语义不变

2.别忘了在别的以同样的非终结符开始（A）的产生式后面加上引入的非终结符（R）

消除间接左递归

方法：先将间接左递归变为直接左递归，然后消除直接左递归，最后将产生式汇集起来

通用的左递归消除算法

说人话：

1）按照某个顺序，将产生式排序为A1,A2,…,An

注意，一般将开始符号放在最后，因为接下来的步骤是将排在上面的符号带入下面的产生式，将开始符号放在最后，最终的结果就是开始符号→......

2）从上到下考察每一个产生式Ai(i∈[i,n])，将之前的非终结符号Aj(j∈[1,i-1])带入Ai（如果可以的话）。然后，可以得到Ai的一个产生式，如果存在直接左递归，则消除，否则，开始新的一轮循环，考察Ai+1

即：

再人话一点：

1.先找到所有非终结符，且将非终结符排成一列给予编号i，i=1，2，3，4......

2.从第一个非终结符i=1开始，对这个终结符之前的每个非终结符1...i-1，把有当前非终结符i推出之前的非终结符的产生式改写，改写方法为利用之前的非终结符推出的所有产生式全部带入，注意可能会出现一个i为头的产生式会被利用两次进行展开，检查有没有产生直接左递归，若有则消除，没有就检查下一个。

3.最后将得到的所有产生式总结起来（一般检查i=1的非终结符为头的产生式的时候不会做任何事情，直接写下来，最后总结别忘了加上）

例子：

排列为S、A

i=1时：啥事也不用干

S→Aa | b

i=2时： j=1, 处理产生式A→Sd, 替换得到

A→Aad | bd

消除A的直接左递归，即由A→Ac | Aad | bd | ϵ 得到

A→bdA^′ | A^′

A′→cA^′ | adA^′ | ϵ

汇总，得到

S→Aa | b

A→bdA^′ | A^′

A′→cA^′ | adA^′ | ϵ

算法结束

（2）预测分析算法

基本思想

采用深度优先策略构建解析树，每次为非终结符号选择适当的产生式，以避免回溯

通过向前查看输入中的一个或多个尚未被匹配的终结符来选定产生式

LL(1)文法

我们先从简单的情况着手，即先考虑通过向前查看一个输入符号就能用预测分析算法解析的文法；人们将这类文法定义为LL(1)文法

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

第二个“ L”表示最左推导

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

构建解析表

解析表例子：

解析表含义：当读到的输入符号为id，栈顶的非终结符为E时，使用产生式（E，id）项内的产生式。

•构建解析表需要两个函数：

1.FIRST()

2.FOLLOW()

FIRST函数

注：α是由终结符和非终结符组成的某个串

定义：FIRST(α)是可以出现在α导出的句型的开头的终结符的集合，如果α ϵ，那么ϵ也在FIRST(α)中

人话：FIRST(α)被定义为可从α推导得到的串的首符号的集合，其中α是任意的文法符号串

计算方法（标准）：

（1）若X是终结符，将X加入

（2）若存在产生式X → ϵ，那么将ϵ加入

（3）若X是非终结符，按照下面两个规则不断迭代，直到所有的FIRST集合都不再变化为止

若存在产生式X → Y1Y2…Yk

•如果ϵ在FIRST(Y1), … , FIRST(Yi-1)中，且a 在FIRST(Yi)中，那么将a加入

•如果ϵ在FIRST(Y1), … , FIRST(Yk)中，那么将ϵ加入

（4）X是串X1X2…Xk ，即需计算FIRST(X1X2…Xk)

•将FIRST(X1)中的所有非ϵ符号加入

•若ϵ在FIRST(X1)中，将FIRST(X2)中所有非ϵ符号加入...以此类推

•若ϵ在所有FIRST(Xi)中，那么将ϵ加入

计算方法（简易）：

First集规则（相应字母在->左边，查找->右边第一个东西）

当A为终结符，直接加入

当A为非终结符时：

①A->aB，a加进First（A）；

     （->右边第一个是终结符，加进集合）

②A->ε，ε加进First（A）；

③A->Xa,将集合First（X）\ε加入First（A）中。

     （->右边第一个是非终结符，将该非终结符的First集（去空）加进集合）

（如果取了空，那头就不是头了）； FIRST函数的意义

在有些情况下，假设A的产生式为 A → α | β，FIRST(α)和FIRST(β)不相交，且下一个输入符号是x，那么：

若x ∈FIRST(α)，则选择 A → α；

若x ∈FIRST(β)，则选择 A → β

FOLLOW函数

定义

FOLLOW(X )

–可以在某些句型中紧跟在X右边的终结符的集合

对于非终端符号，FOLLOW(A)被定义为可能在某些句型中紧跟在A右边的终端字符的集合。

FOLLOW函数的意义

–如果A → α，当α 能够推出 ϵ时，FOLLOW(A) 可以帮助我们选择恰当的产生式

–例如：A → α，而b属于FOLLOW(A)，如果α 能够推出 ϵ ，而当前输入符号是b，则可以选择A → α，因为A最终到达了ϵ，而且后面紧跟着b

计算方法（标准）：

若S为文法开始符，则将右端结束标记$加入FOLLOW(S)中

然后，按照下面两个规则不断迭代，直到所有的FOLLOW集合都不再变化为止

•如果存在产生式A → αBβ，那么FIRST(β)中所有非ϵ的终结符都加入FOLLOW(B)中

•如果存在产生式A → αB，或者A → αBβ且FIRST(β)包含ϵ，那么FOLLOW(A)中的所有符号都加入FOLLOW(B)中

计算方法（简易）：

Follow集合规则（相应字母在->右边，查找相应字母的右边的东西）

①A是开始符号，Follow（A）有$；

②B->Aa，Follow（A）有a

     （后面是终结符，加进我的Follow集）

③B->AC，First（C）\ε加入Follow（A）。

     （后面是非终结符，将该非终结符的First集加进我的Follow集）

④B->aA或B->aAC，C->ε。将Follow（B）加入Follow（A）

     （后面没东西，或者后面有东西，但这个东西可以取空。将->左边字母的Follow集加入我的Follow集）

直到所有FOLLOW集合不再变化为止

START函数

START(A → β)

基于FIRST(β)和FOLLOW(A)

START(A → β)的意义

–在解析过程中，遇到哪些符号时选择产生式A → β

解析表构建算法

例如：START（E→TE'）集合中的终结符有id和（，那么在解析式的[E,id]和[E,（]两个格子中写上该解析式

LL(1)文法新定义

LL(1)文法定义：

给定一个文法，若其解析表的任何一个表项至多有一个产生式，则该文法是LL(1)文法

提取左公共因子

有些文法，经该算法处理后是LL(1)文法，有些不是

( 3 ) 递归下降算法

为了实现确定的自顶向下分析，要求文法满足下述两个条件：（1）文法不含左递归，即不存在这样的非终结符A：有A->A……存在；（2）无回溯，对文法的任一非终结符号，当其产生式右部有多个候选式可供选择时，各候选式所推出的终结符号串的首字符集合要两两不相交。因为文法如果包含左递归和回溯在文法分析的时候就可能会做大量无用的工作，导致分析效率降低。因此，第一步是对文法消除左递归和回溯

递归下降算法过程：

抽象语法树

精简版的解析树

每个结点代表一个语法结构，比如对应某个运算符

结点的每个子结点代表其子结构，比如对应运算分量

表示这些子结构按照特定的方式组成了较大的结构

可以忽略掉一些标点符号等非本质的东西

7.语法分析技术：自底向上算法

基本思想

基本思想：一边从左⟶右扫描输入，一边自叶⟶根构造解析树，不成功则报错

主要方法：移入-归约

归约

自底向上的语法分析过程 = 将输入归约为文法开始符的过程

概念：将一个与某产生式体相匹配的子串替换为该产生式的头(非终结符)

对于句型T ∗ id，有两个子串和某产生式右部匹配，该如何选择？

（最右推导：总是选择每个句型的最右非终结符进行替换。从文法的开始符经过最右推导得到的句型称为最右句型。）

应该选择一个在归约后能够产生最右句型的一个，使得每一次归约后的结果都为最右句型

句柄

最右句型中和某个产生体相匹配的子串，对其归约对应着最右推导的一步，得到前一个最右句型

人话：经过最右推导得出来的右边或者是利用的产生式称为句柄

特点：

−在一个最右句型中，句柄右边只有终结符

−如果文法是无二义性的，那么每个句型有且只有一个句柄

移入-归约技术

使用一个栈来保存移入/归约的文法符号

栈中符号 (从底向上) 和待扫描的符号组成了一个最右句型

开始时刻：栈中只包含$，而输入为w

结束时刻：栈中为S，而输入为$

在分析过程中，不断移入符号，并在识别出句柄时进行归约

句柄被识别时总是出现在栈的顶部

例子：

id ∗ id

移入：将下一个输入符号移入到栈顶

归约：将句柄归约为相应的非终结符号

句柄总是在栈顶

具体操作时弹出句柄，压入非终结符

接受：宣布分析过程成功完成

报错：发现语法错误，调用错误处理子程序

移入-归约技术存在两种困难：

1.如何识别句柄？

给定位于栈顶的一串符号，如何判断它到底是不是句柄

2.对于某些文法，即使识别出句柄，在如何确定下一步动作时，仍有可能面临两种冲突：

shift/reduce冲突

reduce/reduce冲突

为了应对这些困难，人们提出了移入-归约框架下的LR语法分析技术。

LR语法分析技术

特点：

1.手工生成工作量很大，但是语法分析器生成工具可以方便地自动生成

2.对几乎所有的程序设计语言，只要写出上下文无关文法就能构造出识别该语言的LR分析器

3.最通用的无回溯移入-分析归约技术

4.能分析的文法比LL（K）更多

LR解析表的结构：

分两个部分：动作ACTION，转换GOTO

ACTION表项有两个参数：状态i，终结符a；以此确定四个动作：移入、归约、接受、报错

GOTO表项有两个参数：状态i，非终结符A； GOTO[i,A]=j

栈中存放的是状态序列

分析程序根据栈顶状态和当前输入，通过解析表确定下一步动作。

例子：

这个解析表怎么读？（对”LR语法分析器行为''的理解）

1.起始栈里为状态0，下一个输入符号为id，因此查询Action[0,id],为S5，含义为移入状态5并且读入输入符号id。

2.此时栈顶为5，下一个输入符号为*，因此查询Action[5,*],为r6，含义为归约，使用标号为6的产生式归约。归约掉了id一个符号，因此推掉一个栈，退掉栈后栈顶为状态0，刚归约用的产生式头部的非终结符为F，所以查表GOTO[0,F]，为3，所以压入状态3。

3.以此类推

总结：

根据栈顶状态n和下一个输入符号α去读解析表的Action[s,α]读出来的内容：

1.若为s，则动作为移入，看下标，栈中移入下标所写状态，将输入符号读入（在输入串中删除）

2.若为r，则动作为归约，看下标，使用下标所标号的产生式进行归约。归约掉了几个符号（使用的产生式的右边）就退掉几个栈，根据退栈后栈顶状态和刚才归约所使用的产生式的左侧的非终结符查询GOTO表，将查到的状态压入栈。

LR语法分析器的格局

1.包含栈中内容和余下输入（s0s1s2...sm , aiai+1ai+2....an)

第一分量是栈中内容，sm为栈顶

第二分量为余下的输入

2.LR语法分析器的每一个状态都对应一个文法符号（s0除外）

每个s对应一个终结符或者非终结符

令Xi为si对应的文法符号，那么X1X2...Xm aiai+1...an对应于一个最右句型

LR语法分析器的行为

LR语法分析算法

栈顶的是状态，读取的是输入串，输入串不进栈。从栈顶弹出的符号也为状态。只有shift t时才会读取下一个输入符号

不同的LR分析器

LR分析器的不同体现在：

-LR解析表不同，即构造解析表时是否向前看，以及向前看时，所看输入符号个数的不同

几种常见的LR语法分析器：

1.LR（K）：

--LR（0）向前看0个输入符号，分析表最简单，状态数量在几百级别

--LR（1）向前看1个输入符号，可用于大部分编程语言，但状态数量庞大，几千级别

2.SLR（1）：Simple LR（1），状态数量与LR（0）相当，几百级别

3.LALR（1）：LookAhead LR（1），状态数量与LR（0）相当，几百级别

LR(0)< SLR(1)<LALR(1)<LR(1)

LR解析表构建

LR（0）项

概念：加点的产生式，项目描述了句柄识别的状态

例如：

A→ ·XYZ 、移入项（特殊的待约项）

A→X·YZ 、待约项

A→XY·Z 、待约项

A→XYZ· 归约项

含义：解析过程已经处理了产生式体的多少部分（从左边算）

项A→X·Y 标识解析式已经扫描/归约到了X（出现在栈顶）并期望接下来能够扫描或者归约得到Y，从而将XY归约到A

项集

对A→X·YZ

在当前状态下我们希望将YZ或者能归约为YZ的某个符号移入栈顶

假设当前状态下，我们有下面三个项：

A→X·YZ

Y→·u

Y→·w

在该状态下，我们已经识别出了X，并且期望接下来的输入符号串可以由YZ推导出来（也就是可以归约到YZ再归约到A)，这等价于说期望接下来的符号串可以由u或w推导出来

将对应解析器同一状态的所有等价项放在一起，就构成了项集

简而言之，状态与项集一一对应。

增广文法

文法G中添加新开始符S'并且添加产生式S‘→S即可得到G’

二者接受相同的语言，并且按照S‘→S进行归约时，表示已经将所有输入符号归约为开始符

注意：增广文法仅是为了使得文法开始符号仅出现在一个产生式的左边，从而使得分析器只有一个接受状态。

LR(0)项集闭包CLOSURE

LR（0）项集闭包：如果I是文法G的一个项集，CLOUSURE(I)是根据下列两条规则从I构造的项集

1.将I中各项加入CLOSURE（I）中

意义：

人话计算方法：

1.先把项集中各项加入闭包

2.点后面的非终结符记为X，若有X作为头部的产生式，且不在闭包中，就将该产生式在箭头右边加点，加入到闭包中，注意衍生，直到没有新项可以加入为止

闭包计算结果仍然为一个项集

LR(0)项集闭包的构造算法

例子：

GOTO函数

GOTO函数讲人话：

一个项集I，文法符号X，GOTO(I,X)的含义为I中所有X前一位有点的项将点挪到X后面一位的项所构成的项集的闭包

规范LR(0)项集族的构造算法

讲人话：

对于一个增广文法G‘，先求S’→S的项集闭包，记为C，然后循环：对于C中所有项集I和语法符号X，将GOTO（I,X)加入C中，注意：X中不包含开始符，X是前面有点的文法符号

PS：别忘了记录一下哪个项集是通过哪个项集和非终结符应用GOTO函数构造出来的，后面有用

LR(0)解析表构造算法

记住即可

移入项移入，归约项归约

移入：看规范项集族里面，项集之间的GOTO关系，为通过终结符的，就写到移入里面，比如状态I1通过aGOTO到状态I2，那么在LR0语法分析表的ACTION部分，[状态1，a]的值为s2，为非终结符的，就写到GOTO里面，比如状态I1通过FGOTO到状态I5，那么在LR0语法分析表的GOTO部分，[状态1，F]的值为5

归约：如果在某个项集内，存在归约项，即点在产生式最后面，（前提是不是开始符所在的那个产生式！！！）则这个状态下对所有终结符，ACTION内容均为归约，归约使用的产生式就是这个产生式去掉点那个产生式

接收：若在某个项集内，有着开始符为头的那个产生式，那么在这个项集对应的状态的[I,$]的值为accept

总：先写出移入，再写出归约，看有无冲突，无冲突说明是LR（0）文法

LR(0)分析的不足在于：

只能对付简单的文法，文法稍微复杂一点，就有可能产生冲突：移入归约冲突/归约归约冲突

如果LR(0)解析表中没有语法分析动作冲突，那么给定的文法就称为LR(0)文法

SLR（1）

为了能够解决上面LR（0）语法分析技术的冲突问题，引入SLR（1）

SLR(1)分析的基本思想

已知项集 I 包含：

A1→α1.a1β1

A2→α2.a2β2

…

Am→αm.amβm

这样m个移入项

B1→γ1.

B2→γ2.

…

Bn→γn.

这样n个归约项

若集合{a1, a2, …, am}、FOLLOW(B1)、 FOLLOW(B2)、…、FOLLOW(Bn)两两不相交，则项集I中的冲突可以按以下原则解决：

设a是下一个输入符号

若a∈{ a1, a2, …, am }，则移入a

若a∈FOLLOW(Bi)，则用产生式 Bi→γi 归约

此外，报错

SLR(1)解析表构建算法

移入项不变，对于归约项，先看以下要归约的项产生式头的FOLLOW集，下一个输入符号在哪个产生式头部非终结符的FOLLOW集中就用哪个产生式归约，写r几

SLR（1）分析仍然有所不足。

当项集中包含[A→α⋅]时：

按照A→α进行归约的条件是下一个输入符号b∈ FOLLOW(A)，

但是，该条件不充分，原因：假设此时栈中的符号串为βα，

如果βAb不是任何最右句型的前缀，那么即使b∈ FOLLOW(A)，也不能按照此产生式进行归约。

在特定位置，A的后继符号集合应是FOLLOW(A)的特定子集，

但SLR(1)分析过程并未考虑这种特殊性，因而出现冲突。

LR(1)语法分析技术

LR（1）项

LR(1)项的形式 [A→α⋅β , b]

b称为该项的展望符，可以是终结符或者$

b表示：如果将来要按照A→αβ进行归约，下一个输入符号必须是b

虽然，在形如[A→α⋅β, b]且β≠ϵ的项中，"展望符" b没有任何作用，但是，对于形如[A→α⋅, b]的项，只有在下一个输入符是b的情况下，才可以按A→α进行归约

这样的b的集合是FOLLOW(A)的一个子集，而且通常是它的一个真子集

LR(1)项中包含了更多信息，来剔除某些归约动作，在效果上，相当于“拆分”一些LR(0)状态，精准指明何时才能进行归约

等价的LR(1)项

LR(1)项集闭包CLOSURE

在求CLOSURE的时候，当由项 [A→α⋅Bβ,a] 生成新项 [B→⋅η,b] 时， b必须在FIRST(βa)中

由于展望符的存在，基本原理与LR（0）项集闭包类似，但是需要条件：生成新项的展望符必须在旧项βa的FIRST集合中

在计算闭包的时候，生成的新项的展望符是FIRST(βa)，多个也一起写上。

LR(1)项集的GoTo算法

与LR（0）项集GOTO算法相同

规范LR(1)项集族的构造算法

与LR（0）项集族构造相同。

LR(1)解析表构造算法

对于归约项，只有终结符是产生式的展望符才使用该产生式归约

LALR(1)语法分析技术

LALR(1)是实践中常用的方法，能够处理大部分常见的程序设计语言，l能力接近LR(1)，状态数量接近SLR(1)

LALR(1)分析技术的基本思想

首先，寻找具有相同核心的LR(1)项集，并将这些项集合并为一个项集。所谓项集的核心就是其第一分量的集合

一个LR(1)项集的核心是一个LR(0)项集

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

GoTo(I, X)的核心只由I的核心决定，因此被合并项集的GoTo目标也可以合并

这表示合并之后，我们仍可以建立GOTO关系

合并：比如I10和I8合并，留下I8，那么原来指向I10的指向I8，原来从I10出去的改成从I8出去

LALR（1）语法分析表的构建

三、语义分析

语法制导翻译的基本思想

如何表示语义信息？

为CFG中的文法符号设置语义属性，以表示其对应的语义信息

如何计算语义属性的值？

通过语义规则来计算文法符号的语义属性值，而语义规则与文法符号所在的产生式(语法规则)紧密相关

对于给定的输入串x，构建x的语法分析树，当应用某个产生式时，就利用与之关联的语义规则来计算分析树中相关结点的语义属性值

制定与执行语义规则

语法制导定义(Syntax-Directed Definitions, SDD)

语法制导翻译方案(Syntax-Directed Translation Scheme, SDT)

语法制导定义(SDD)

SDD是对CFG的推广

将文法符号和语义属性相关联，按照需要来确定各个文法符号需要哪些属性

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

(描述文法符号的语义属性怎么来的)

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

产生式	语义规则
(1) L ® E$ (2) E ® E1 + T (3) E ® T (4) T ® T1 * F (5) T ® F (6) F ® ( E ) (7) F ® digit	L.val = E.val E.val = E1 .val + T.val E.val = T.val T.val = T1 .val ×F.val T.val = F.val F.val = E.val F.val = digit.lexval

语法制导翻译方案(SDT)

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

SDD与SDT的比较

SDD

是关于语言翻译的高层次规格说明

隐蔽了许多具体实现细节

SDT

可以看作是对SDD的一种补充，是SDD的具体实施方案

明确指明语义规则的计算顺序，说明实现细节

SDD是把语义规则和属性写在一起，SDT是把语义动作插入到产生式中

语法制导定义(SDD)

文法符号的属性：综合属性

假设分析树结点N对应非终结符A，只能通过N的子结点或N本身的属性值来定义的属性称为A的综合属性

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

注意：这个产生式的头一定是A

继承属性(inherited attribute)

假设解析树结点N对应非终结符A，只能通过N的父结点、N的兄弟结点或N本身的属性值来定义的属性称为A的继承属性

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

注意：这个产生式的体一定包含A

继承属性的作用：一颗语法分析树的结构和源代码的抽象语法不匹配时，有用，比如在左右子节点之间传递数值。

属性文法 (Attribute Grammar)

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

在属性文法的语义规则中，仅仅通过其它属性值和常量来定义一个属性值

SDD的求值顺序

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

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

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

依赖图(Dependency Graph)

依赖图是一个有向图，它描述了分析树中结点属性之间的依赖关系

解析树中每个标号为X的结点的每个属性a都对应着依赖图中的一个结点

如果属性X.a的值依赖于属性Y.b的值，则依赖图中有一条从Y.b的结点指向X.a的结点的有向边

例如：

属性值的计算顺序

任何一个可行的求值顺序都必须是满足下列条件的结点序列N1, N2, … , Nk ：

如果依赖图中有一条从结点 Ni 到 Nj 的边(Ni → Nj ), 那么i < j（即：在节点序列中， Ni 排在 Nj的前面）

这个顺序称为这个依赖图的拓扑排序(topological sort)

对于只涉及综合属性的SDD，可以按照任何自底向上的顺序计算它们的值

对于同时具有继承属性和综合属性的SDD，不能保证存在一个顺序来对各个节点上的属性进行求值

如果图中没有环，那么至少存在一个拓扑排序

一般说来，给定一个SDD，很难确定是否存在某棵语法分析树，使得SDD的属性之间存在循环依赖关系

然而，存在两类SDD，它们不允许产生带有环的依赖图，因而能够保证每棵语法分析树都存在一个求值顺序；不仅如此，它们还可以与自顶向下或自底向上的语法分析过程一起，高效地实现

S属性定义(S-Attributed Definitions, S-SDD)

L属性定义(L-Attributed Definitions, L-SDD)

S属性SDD

定义：每个属性都是综合属性，都是根据子构造的属性计算出父构造的属性

在依赖图中，总是通过子结点的属性值来计算父结点的属性值，可以与自底向上或自顶向下的语法分析过程一起计算

若是自底向上的语法分析过程，则

在构造分析树结点的同时计算相关的属性值(此时其子结点的属性值必然已经计算完毕)

若是自顶向下的语法分析过程，则

在递归下降方法中，在过程A()最后计算A的属性值 (此时A调用的其它过程(对应于其子结构) 已经调用完毕)

若在分析树上计算SDD，只需按照后序遍历的顺序计算属性值即可

L属性SDD

思想：在一个产生式体所关联的各个属性之间，依赖图的边总是从左到右，而不能从右到左

定义：

每个属性

是综合属性

或是继承属性，且A→X1 X2 … Xn 中计算Xi.a的规则只用到

1.A的继承属性，或

2.Xi 左边的文法符号Xj 的继承属性或综合属性，或

3.Xi 自身的继承或综合属性 (这些属性间的依赖关系不会形成环)

特点：

依赖图中的边

综合属性从下到上

继承属性从上到下，或从左到右

计算一个属性值时，它所依赖的属性值都已计算完毕

L属性SDD和自顶向下语法分析

L_visit(node) {

for each 从左到右node的每个子节点m

do{

计算m的继承属性; L_visit(m);

}

计算node的综合属性;

}

四、中间代码生成

中间代码表示及其好处

•形式

–多种中间表示，不同层次

–抽象语法树

–三地址代码

•高层次的优化

优化与源语言和目标机器都无关

•中间代码生成的过程可以用语法制导翻译来描述和实现

•对于抽象语法树这种中间表示的生成，第五章已经介绍过

•对于三地址代码，则可通过后序遍历抽象语法树来完成

三地址代码

•每条指令右侧最多有一个运算符

一般情况可以写成x = y op z

•允许的运算分量

标识符：源程序中的标识符作为三地址代码的地址

常量：源程序中出现或生成的常量

编译器生成的临时变量

指令集合

– 运算/赋值指令：	x = y op z	x = op y
– 复制指令：	x = y
– 无条件转移指令：	goto L
– 条件转移指令：	if x goto L	if False x goto L

条件转移指令：

if x relop y goto L

–过程调用/返回

•param x1

•param x2

•…

•param xn

•call p, n

–带下标的复制指令：x = y[i] x[i] = y

•注意：i表示离开数组位置第i个字节，而不是数组的第i个元素

–地址/指针赋值指令

x = &y x = y* x* = y

三地址指令的四元式表示方法

•在实现时，可使用四元式来表示三地址指令

•四元式可以实现为记录 (或结构)

静态单赋值 (SSA)

•Static Single Assignment (SSA) 中的所有赋值都是针对不同名的变量

•对于同一个变量在不同路径中定值的情况，可以使用φ函数来合并不同的定值

SSA（静态单赋值）是一种中间表示形式，其中每个变量都只被赋值一次。为了实现这一点，需要在程序中插入φ函数。φ函数是一种特殊的函数，它接受多个参数，根据控制流选择其中一个参数作为其结果。在SSA中，每个变量在其定义点处都有一个φ函数。这个φ函数接受来自不同控制流的值，并将其传递给变量的使用点。这样，每个变量都只有一个定义点，简化了程序分析和优化。

增量式翻译方案

边遍历AST边通过gen生成新的三地址指令，并将它添加到至今为止已生成的指令序列之后

控制流的翻译

•布尔表达式可以用于改变控制流

•文法

–B ⇒ B ‖ B | B && B | ! B | ( B ) | E rel E | true | false

•语义

–B1 ‖ B2中B1为真时，不计算B2，整个表达式为真，因此，

当B1为真时应该跳过B2的代码

–B1 && B2中B1为假时，不计算B2，整个表达式为假

例子：

•语句

– if (x < 100 ‖ x > 200 && x != y) x = 0;

•代码

if x < 100 goto L2

if False x > 200 goto L1

if False x != y goto L1

L1：x = 0

L2：接下来的代码

S ⇒ if (B) S1

S ⇒ if (B) S1 else S2

S ⇒ while (B) S1

例子

涉及到数组下标时，假设j=n，v=a[n]，这个n是离开数组位置第i个字节，而不是数组的第i个元素，因此在把数组某个值赋给变量时，要把方括号里面的东西乘以4，比如(3)(4)

五、代码优化

优化分类

机器相关与否

机器无关优化，针对中间代码

机器相关优化，针对目标代码

范围

局部优化

全局优化

中间代码基本块

基本块是满足下面两个条件的极大的指令序列：

控制流只能从基本块的第一条指令进入

除基本块的最后一条指令外，控制流不会跳转/停机

划分基本块的算法

输入：三地址指令序列

输出：基本块的列表

方法

确定首指令 (leaders )

1.第一个三地址指令

2.任意一个(条件或无条件) 转移指令的目标指令

3.紧跟在一个(条件或无条件) 转移指令之后的指令

确定基本块

基本块：从首指令开始到下一个首指令之前的部分

例子：

如何找基本块

1.极大的意思是尽可能的大，

2.控制流只能从基本块的第一条指令进入，不能从基本块的中间进入

3.控制流不会在基本块的中间进行跳转

方法：就是找首语句，找首语句的方法：第一个三地址指令、任意一个(条件或无条件) 转移指令的目标指令、紧跟在一个(条件或无条件) 转移指令之后的指令

这里第一条指令和第二条指令都单独作为一个基本快的原因是后面有goto（2），若（2）不单独作为一个基本块的话，会导致控制流从基本块中间进入

控制流图

控制流图是以基本块为结点的有向图，其边指明了基本块在运行过程中的前驱后继关系

控制流图可以作为优化的基础

它指出了基本块之间的控制流

可以根据控制流图了解到一个值是否会被使用等信息

控制流图的构造

-从基本块B到基本块C之间有一条边当且仅当基本块C的第一个指令可能紧跟在B的最后一条指令之后执行

•有两种方式可以确认这样的边：

1.C紧跟在之B后，且B的结尾不存在无条件跳转语句

2.B的结尾有一个跳转到C的开头的条件或无条件跳转语句

例子：

常用的机器无关优化方法

1.删除公共子表达式

如果表达式 x op y 先前已被计算过，并且从先前的计算到现在，x op y 中变量的值没有改变，那么 x op y 的这次出现就称为公共子表达式(common subexpression)

例子：

（1）基本快范围内公共子表达式的删除

这里t7和t10都是重复计算过的

修改为：

就是直接删掉重复的子表达式，然后用再用到子表达式的结果的地方使用第一次计算的结果

（2）全局范围的公共子表达式

例子：

这里有两个表达式在前面的基本块内计算过

修改为：

2.删除无用代码

无用代码(死代码Dead-Code ) ：其计算结果永远不会被使用的语句

例子：

修改后：

3.常量合并constant folding

常量合并

如果一个表达式的值是常量，就可以使用该常量来替代这个表达式

例子：

4.代码移动code motion

对于那些不管循环执行多少次都得到相同结果的表达式，在进入循环之前就对它们求值

例子：

源程序

for( n=10; n<360; n++ )

{ S=1/360*pi*r*r*n;

printf( “Area is %f ”, S );}

修改为：

5.强度削弱(strength reduction)

用较快的操作代替较慢的操作

例子：

加法比乘法快，乘法比除法快，乘法比乘方快，记住这个多项式特殊处理--

局部优化，亦称基本块优化

变量的活跃性和后续使用信息

三地址语句 i 向变量 x 赋值，如果另一个语句 j 的运算分量为 x，且从 i 到 j 有一条路径，且路径上没有对 x 赋值，那么 j 就使用了 i 处计算得到的 x 的值此时，我们说变量 x 在程序点 j 处活跃

在一个地方得到x值，能到且到了j语句，这个变量x没有改变过，而且j语句用到了变量x，则说明x在j处活跃

确定基本块中变量的活跃性和后续使用信息

•输入：基本块B(开始时B中的所有非临时变量都是活跃的)

•输出：各个语句i上变量的活跃性和后续使用信息

•方法：

从B的最后一个语句开始反向扫描

对于每个语句i：x = y + z

令语句i和x、y、z的当前活跃性信息/使用信息关联

设置x为“不活跃”和“无后续使用”

设置y和z为“活跃”，并将其后续使用设置为语句i

例子：

i, j, a非临时变量，在出口处活跃，其余变量不活跃

–8) i, j, a活跃，j被 8 使用

–7) i, j, a, t4活跃，a和t4被7使用

–6) i, j, a, t3活跃，t4不活跃，t3被6使用

–5) i, j, a, t2活跃，t4, t3不活跃，t2被5使用

–4) i, j, a, t1活跃，t4, t3, t2不活跃，t1和j

被4使用

–3) i, j, a活跃，t4, t3, t2, t1不活跃，i被3使用

从下往上看，在左侧就记为不活跃，从右侧就记为活跃。特例是数组，左边的数组名和下标都是活跃。从下往上依次更新，出现依次该变量就根据情况更新以下该变量的活跃性。

基于DAG图的局部优化

DAG图的构造

•为基本块中出现的每个变量建立结点(表示初始值)，各变量和相应结点关联

•顺序扫描各三地址指令，进行如下处理

–指令x = y op z

•为该指令建立结点N，标号为op，令x和N关联

•N的子结点为y、z当前关联的结点

–指令x = y

假设y关联到N，那么x现在也关联到N

例子：

删除局部公共子表达式

•局部公共子表达式的发现

–建立某个结点M之前，检查是否存在一个结点N，它和

M具有相同的运算符和子结点 (顺序也相同)

–如果存在，则不需要生成新的结点，用N代表M

例子：

DAG的重构

•重构DAG得到优化结果

–每个结点构造一个三地址语句，计算对应的值

–结果应该尽量赋给一个活跃的变量

–如果结点有多个关联的变量，则需要用复制语句进行赋值

删除死代码

•在DAG图上消除没有附加活跃变量的根结点

活跃代表有访问到，没有附加活跃变量的根节点其实是没访问到

基于代数恒等式的优化

声明：本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】

山东大学软件学院2023-2024学年第一学期编译原理笔记&期末考试回忆_编译原理与技术山东大学

期末考试回忆：

编译原理

一 词法分析

1.词法分析器的作用

2.词法分析：

（1）词素 (lexeme)

（2）词法单元 (token)

（3）模式

（4）属性

（5）如何选择词法单元

（6）例子：

3.正则表达式

（1）字母表

（2）串

（3）串的运算

（4）语言

（5) 语言的运算

（6）正则定义

（7）运算符扩展

4.词法单元的识别（状态转换图）

（1）状态转换图

（2）保留字和标识符的识别

5.非确定有限自动机(NFA)

6.确定有限自动机 (DFA)

7.从正则表达式到非确定自动机（从正则表达式到NFA）：Thompson算法

8.从非确定自动机到确定自动机（从NFA到DFA)：子集构造法

9.DFA最小化（Hopcroft算法）

10.Lex中的冲突解决方法

二、语法分析

1.上下文无关文法(Context-Free Grammar)

2.推导

3.句子 句型和语言

4.语法分析树

（1）定义

（2）推导和解析树的对应关系

5.二义性及其消除

（1）定义

（2）消除二义性

（3）改写原文法，实现左结合

（4）改写原文法，实现右结合

（5）改写原文法，确定优先级

（6）不改变原文，引入二义性消除规则

6.语法分析技术：自顶向下算法

（1）回溯算法

基本思想

缺点

消除左递归

（2）预测分析算法

LL(1)文法

构建解析表

FIRST函数

FOLLOW函数

START函数

解析表构建算法

LL(1)文法新定义

提取左公共因子

( 3 ) 递归下降算法

抽象语法树

7.语法分析技术：自底向上算法

基本思想

归约

句柄

移入-归约技术

LR语法分析技术

LR解析表构建

LR(0)解析表构造算法

SLR（1）

SLR(1)解析表构建算法

LR(1)语法分析技术

LALR(1)语法分析技术

三、语义分析

语法制导翻译的基本思想

如何表示语义信息？

如何计算语义属性的值？

制定与执行语义规则

语法制导定义(SDD)

语法制导翻译方案(SDT)

SDD与SDT的比较

语法制导定义(SDD)

一词法分析

3.句子句型和语言