编译原理大作业
论文
学号：1093710411
姓名：周国栋
哈尔滨工业大学软件学院
2012年1月
第一章 综述
第1章 综述
1.1 语法分析概述
语法分析是编译过程的一个逻辑阶段。语法分析的任务是在词法分析的基础上将单词序列组合成各类语法短语
1.2 分析方法
语法分析主要有两种：自顶向下的分析方法和自底向上的分析方法。不论是哪一种方法，语法分析器都是自左向右地扫面输入字符串，每次读取一个符号。本文讨论基于以上两种分析方式的五种文法：LL(1)，LR(1)，SLR(1)，LALR(1)以及算符优先文法。最有效的自顶向下和自底向上分析方法只能处理文法的一些子类。对文法的要求比较高，然而这些文法的子类就足以描述程序设计语言中的大部分语言结构。
- 1 -
错误！使用“开始”选项卡将 标题 1,章标题(有序号) 应用于要在此处显示的文字。 错误！使用“开
始”选项卡将 标题 1,章标题(有序号) 应用于要在此处显示的文字。
第2章 五种文法的比较
2.1 LL(1)文法
2.1.1 概述
LL(1)语法分析属于自顶向下的语法分析。所谓自顶向下的语法分析，就是对给定的输入单词序列w，试图自根向叶为其建立一棵语法分析树。或者说从文法开始符号出发，寻求所给的输入符号串的一个最左推导。
2.1.2 存在的问题
但是无论哪种方法，在分析过程中都可能会遇到一些共同的问题：
1 二义性问题;
2 回溯问题;
3 左递归引起的无穷推导问题。
所以说，自顶向下的语法分析方法并不能处理所有的文法，有时为了适应所选择的分析方法，常常需要对原始文法进行改造，包括如下3步：
1消除二义性。这一步只能是人工手动的修改文法。
2消除左递归。这一步可以由程序来处理。假设有n个语法变量，那么这一步的时间复杂度是O（错误！未找到引用源。）。
3提取左公因子。这一步也主要有人工手动处理。经过这三步处理后的文法，便可以使用预测分析法或者递归下降分析法来进行语法分析了。
2.1.3 处理过程
在接下来的处理中，两种方法都需要进行三步预处理，即：
1 求出单个文法符号X和文法符号串α的FIRST集；
2 求FOLLOW集；
- 2 -
错误！使用“开始”选项卡将 标题 1,章标题(有序号) 应用于要在此处显示的文字。 错误！使用“开
始”选项卡将 标题 1,章标题(有序号) 应用于要在此处显示的文字。
3 求LL（1）分析表。
所以改造后的文法LL（1）有一些特殊的性质。它不是二义性的，也不含左递归。可以证明，G是LL(1)文法，当且仅当G的任何两个不同的产生式A→α|β满足下面条件：
1、不存在这样的终结符α，使得α和β导出的串都以a开始
2、α和β中至多有一个能导出空串
3、如果β→ε，那么α不能导出以FOLLOW(A)中的终结符开始的任何串。
对于求单个文法符号X的时间复杂度，假设文法符号的个数为n，非终结符个数为m，由于循环的次数与嵌套的层数和计算的顺序有极大的关联，最坏情况要循环O（n）次，为方便计算，再根据实际情况假设每个产生式右部的文法符号个数为10，所以，求单个文法符号X的时间复杂度为O（10*n*m）= O(mn),而对于符号串α，假设它包含k个符号，则计算它的时间复杂度为O（mnk），求出了FIRST集采能求FOLLOW集，易知求FOLLOW集的时间复杂度也为O（mn）。
构造预测分析表的方法：
输入：文法G
输出：分析表M。
方法：
1、对于文法中的每个产生式A→α，执行第二步和第三步
2、对FIRST(α)中的每个终结符α，将A→α加入到M[A,a]中
3、若ε在FIRST(α)中，则对FOLLOW(A)的每个终结符b，将A→α加[]入到M[A,b]中，若ε在FIRST(α)中，且﹟在FOLLOW(A)中，则将A→α加入到M[A,﹟]中
4、将M中每个没定义的表项均置为error
分析表是一个二维数组M[A,a],A是语法变量，a是输入符号或#。也可以在O（mn）的时间内求出，两种方法其实都用到了预测LL（1）分析表，只不过使用的方法不太一样。
2.1.4 预测分析法
对于预测分析法，它采用表驱动的方式来实现，它具有一个输入缓冲区、一个分析栈、一张LL（1）分析表和一个输出流。输入缓冲区中包含待
- 3 -
错误！使用“开始”选项卡将 标题 1,章标题(有序号) 应用于要在此处显示的文字。 错误！使用“开
始”选项卡将 标题 1,章标题(有序号) 应用于要在此处显示的文字。
分析的串和结束符#。分析栈用来存放文法符号序列，栈底符号是#。初始时，栈中只有文法开始符号及其下的#。整个分析过程在于从文法开始符号开始，试图构造输入缓冲区中待分析串的最左推导。假设某程序共有符号s个，整个控制程序的时间复杂度为O（s）。
使用预测分析的主要困难在于为源语言编写一个能构造出预测语法分析器的文法。虽然消除左递归和提取左因子都非常简单，但它们使得结果文法很难阅读而且不易翻译。
2.1.5 递归下降分析法
而对于递归下降分析法，是指根据各个候选式的结构，为文法的每个语法变量编写一个处理子程序，用来识别该语法变量所代表的语法成分。设有产生式A X1X2X3„Xk„Xn，则与A对应的处理子程序遇到的Xk是终结符时直接进行匹配，而遇到Xk是语法变量时就调用与Xk对应的处理子程序。由于产生式中的语法变量可能是递归定义的，所以这种实现方法要求处理子程序可以递归调用。另外，这种分析方法也是寻求输入串的一个推导过程，所以称为递归下降分析法。实际上，上面所说的预测分析法是一种特殊的递归下降分析法，它是通过显示地维护一个状态栈而不是通过隐式的递归来实现的。如果编译程序的实现语言允许进行过程的递归调用，则可以采用一般形式的递归下降分析法。这种方法的主要优点是易于实现。此外，由于分析器和文法的紧密对应性，这种方法还易于保证语法分析器的正确性。其缺点是频繁的递归调用会降低分析器的效率，而且与预测分析法相比，这种分析器的代码规模非常大。尽管如此，递归子程序法仍然是一种有效的语法分析方法，因为在实际应用中，递归的层次往往不会太深，许多高级程序设计语言的编译系统都采用这种分析方法。
2.1.6 综述
总之，自顶向下分析法只能处理上下文无关文法的一些子类，对于文法的限制也比较多，而且其中许多部分必须人工手动完成，比较难以实现自动化，与之相反的是自底向上的LR分析法，基于LR分析法的良好形式和理论基础，人们可以寻求这种方法的进一步自动化，于是就有了Yacc之类的语法分析程序自动生成工具。
- 4 -
错误！使用“开始”选项卡将 标题 1,章标题(有序号) 应用于要在此处显示的文字。 错误！使用“开
始”选项卡将 标题 1,章标题(有序号) 应用于要在此处显示的文字。
2.2 LR(0)文法
LR(0)语法分析属于自底向上的语法分析。自底向上的语法分析的思想就是从输入串出发，反复利用产生式进行归约，如果最后能得到文法的开始符号，则输入串是句子，否则输入串有语法错误。核心是寻找句型中的当前归约对象——“句柄”进行归约,用不同的方法寻找句柄，就可获得不同的分析方法。
LR(0)文法
如果其LRSM0的每个状态S都有|Γ0(S)|=1，即Γ0(S)只包含一个元素，我们称文法G是LR(0)文法。
若Γ0(S)={ Shift }，则表示S只含移入项目
若Γ0(S)={ Reduce j }，则表示S只含一个[j]归约项目。
每个状态的移入/归约动作的确定没有冲突，而且不依赖于输入符号 LR(0)分析方法的不足
LR(0)方法对文法的要求严格。
LR(0)方法容易出现冲突状态。
2.3 SLR(1)文法。
上下文无关文法不是都能用LR(0)方法进行分析的，也就是说，CFG不
- 5 -
错误！使用“开始”选项卡将 标题 1,章标题(有序号) 应用于要在此处显示的文字。 错误！使用“开
始”选项卡将 标题 1,章标题(有序号) 应用于要在此处显示的文字。
总是LR(0)文法。当文法分析过程中会出现归约—归约冲突和移进-规约冲突时，此文法就不是LR（0）文法。
下面写一下对几种自底向上文法的比较。LR(1)总体来说，就是从左到右扫描输入符号。最右推导对应的最左归约，超前读入1个符号，以便确定归约用的产生式。
为解决LR（0）中的冲突，SLR分析法引入了每个符号的FOLLOW集，SLR(1)分析方法描述能力强于 LL(1) ，SLR(1)还考虑FOLLOW集中的符号，LL(1) 仅考虑产生式的首符号。
SLR(1) 文法是在LR（0）分析表的基础上增加了FOLLOW集，可以解决一部分冲突，但是，SLR文法依然有解决不了的问题。SLR（1）只孤立地考察输入符号是否属于归约项目A→α.相关联的集合FOLLOW（A），而没有考察符号串α所在规范句型的“上下文”。即未考虑规约的有效性，即只考虑了FOLLOW集是否符合规约条件，而没有考虑输入串中后面的字符。
SLR(1)和LR(0)具有相同的状态机
LR(0)只看分析栈的内容，不考虑当前输入符;SLR(1)考虑输入符，用follow集来解决冲突，因此SLR(1)要比LR(0)分析能力强
2.4 LL（1）文法
LR(1)分析方法的引入
LR(0)方法不依赖输入流，直接判定归约，容易出现冲突。
SLR(1)方法简单的把非终极符的follow集做为可归约的依据，并不精确。 一个非终极符在不同的位置上出现，它所允许的后继符是不同的。LR(1)针对不同产生式上的非终极符，分别定义其后继符集（展望符集Reducelookup），减少了移入/归约冲突。
LR(1)分析方法
∙ LR(1)方法研究的对象是二元组：(α, b)，其中α是活前缀，而b是一个输入符号。我们称上述(α , b)为LR1前缀模式。
∙ 如果α是文法的归约活前缀，b是α的合法后继续符，则称(α , b)为LR1归约前缀模式。
LR(1)文法
- 6 -
错误！使用“开始”选项卡将 标题 1,章标题(有序号) 应用于要在此处显示的文字。 错误！使用“开
始”选项卡将 标题 1,章标题(有序号) 应用于要在此处显示的文字。
投影函数Γ2 :
·Γ2：(StateSet×VT∪{#})→2Ω
·Γ2(S,a)=
{Reducej |[B→π·, a]∈S, B→π是产生式j}∪( if 存在a∈VT 使得[A→α·aβ, b]∈S then {Shift} else φ)
如果LR(1)状态机的任一状态S和输入符a，都使得|Γ2(S,a)|≤1，则称文法为LR (1)文法。
因为LR（1）在构造状态时就考虑follow集，而不是在规约时考虑。与LR（0）文法类似，识别文法全部活前缀的DFA的每一状态也是用一个LR
（1）项目集来表示，为保证分析时，每一步都在栈中得到规范句型的活前缀，应使每一个LR（1）项目集仅由若干个对相应活前缀有效的项目组
成。但是文法的强大也会带来一些代价，LR（1）分析表相比起LR（0）和SLR（1）庞大许多，相对来说也会有比较大的运行开销
- 7 -
错误！使用“开始”选项卡将 标题 1,章标题(有序号) 应用于要在此处显示的文字。 错误！使用“开
始”选项卡将 标题 1,章标题(有序号) 应用于要在此处显示的文字。
2.5 LALR(1) 文法
LALR(1)的思想来源
LR(1)状态机和LR(0)状态机从它们所表示的自动机角度来看是等价的 ； ·自动机可通过合并等价状态来减少状态个数。
·在LR(1)状态机出现很多同心状态，而LALR(1)状态机则不产生同心的状态，从而大大减少状态 数，这就是LALR(1)和LR(1)的主要差别。
LALR(1)语法分析属于自底向上的语法分析。LALR（1）是对LR（1）状态的简化，不同的LR(1)项目闭包可能有相同的LR(0)项目，但后继符可能不同，我们称这种情况为两个闭包同心，将两个同心闭包合并，即是LALR
（1）文法。它的显著好处就是减少了状态的数量，缩减了分析表，但是合并后可能带来归约—归约冲突。合并那些不会带来冲突的同心的LR(1)闭包/状态，可以得到LALR（1）分析表，反之，如果合并会出现规约-规约冲突，那么不能使用LALR（1）分析法，换句话说，存在合并后规约规约冲突的文法不是LALR（1）文法。分析能力LALR（1）强于SLR（1），因为合并后的后继符仍然是FOLLOW集的子集，弱于LR（1），因为有上述局限性。
2.6 算符优先文法
2.6.1 概述
算符优先分析法是一种简单适用的方法，用这种方法分析程序设计语言中的各类表达式尤为有效。由于这种方法简单直观，它还特别适用于手工方式来实现。所谓算符优先分析就是将句型中的终结符当做算符，然后定义算符之间的某种优先关系，利用这种优先关系来寻找句柄并进行规约，也是一种自下而上的分析方法。
- 8 -
错误！使用“开始”选项卡将 标题 1,章标题(有序号) 应用于要在此处显示的文字。 错误！使用“开
始”选项卡将 标题 1,章标题(有序号) 应用于要在此处显示的文字。
2.6.2 过程
首先要构造FIRSTOP集合和LASTOP集合，构造过程中分别使用了一个|V|*|T|大小的二维布尔数组来表示某个终结符b是否在B的FIRSTOP集合或LASTOP集合中，又使用了一个栈来帮助计算其他非终结符的这两个集合。算法的时间复杂度主要主产生式的个数有关，设产生式个数为p，则该算法时间复杂度为O（）
- 9 -
错误！使用“开始”选项卡将 标题 1,章标题(有序号) 应用于要在此处显示的文字。 错误！使用“开
始”选项卡将 标题 1,章标题(有序号) 应用于要在此处显示的文字。
第3章 总结
综上，各种分析文法其实无所谓孰优孰劣，就看适用在那些场合，就分析能力来说，LR（1）>LALR(1) >SLR(1)>LL(1)>LR(0)，但是相对来说就可能带来更大的实现复杂度和开销。我们在决定使用哪种分析方法时，主要是看定义的文法，一般的文法只要稍加修改，SLR（1）和LALR（1）的要求是很容易满足的，可以适用于大部分分析程序，比如yacc语法分析器内部就是使用SLR（1）分析法。
- 10 -
错误！使用“开始”选项卡将 标题,章标题(无序号) 应用于要在此处显示的文字。
- 11 -
编译原理大作业
论文
学号：1093710411
姓名：周国栋
哈尔滨工业大学软件学院
2012年1月
第一章 综述
第1章 综述
1.1 语法分析概述
语法分析是编译过程的一个逻辑阶段。语法分析的任务是在词法分析的基础上将单词序列组合成各类语法短语
1.2 分析方法
语法分析主要有两种：自顶向下的分析方法和自底向上的分析方法。不论是哪一种方法，语法分析器都是自左向右地扫面输入字符串，每次读取一个符号。本文讨论基于以上两种分析方式的五种文法：LL(1)，LR(1)，SLR(1)，LALR(1)以及算符优先文法。最有效的自顶向下和自底向上分析方法只能处理文法的一些子类。对文法的要求比较高，然而这些文法的子类就足以描述程序设计语言中的大部分语言结构。
- 1 -
错误！使用“开始”选项卡将 标题 1,章标题(有序号) 应用于要在此处显示的文字。 错误！使用“开
始”选项卡将 标题 1,章标题(有序号) 应用于要在此处显示的文字。
第2章 五种文法的比较
2.1 LL(1)文法
2.1.1 概述
LL(1)语法分析属于自顶向下的语法分析。所谓自顶向下的语法分析，就是对给定的输入单词序列w，试图自根向叶为其建立一棵语法分析树。或者说从文法开始符号出发，寻求所给的输入符号串的一个最左推导。
2.1.2 存在的问题
但是无论哪种方法，在分析过程中都可能会遇到一些共同的问题：
1 二义性问题;
2 回溯问题;
3 左递归引起的无穷推导问题。
所以说，自顶向下的语法分析方法并不能处理所有的文法，有时为了适应所选择的分析方法，常常需要对原始文法进行改造，包括如下3步：
1消除二义性。这一步只能是人工手动的修改文法。
2消除左递归。这一步可以由程序来处理。假设有n个语法变量，那么这一步的时间复杂度是O（错误！未找到引用源。）。
3提取左公因子。这一步也主要有人工手动处理。经过这三步处理后的文法，便可以使用预测分析法或者递归下降分析法来进行语法分析了。
2.1.3 处理过程
在接下来的处理中，两种方法都需要进行三步预处理，即：
1 求出单个文法符号X和文法符号串α的FIRST集；
2 求FOLLOW集；
- 2 -
错误！使用“开始”选项卡将 标题 1,章标题(有序号) 应用于要在此处显示的文字。 错误！使用“开
始”选项卡将 标题 1,章标题(有序号) 应用于要在此处显示的文字。
3 求LL（1）分析表。
所以改造后的文法LL（1）有一些特殊的性质。它不是二义性的，也不含左递归。可以证明，G是LL(1)文法，当且仅当G的任何两个不同的产生式A→α|β满足下面条件：
1、不存在这样的终结符α，使得α和β导出的串都以a开始
2、α和β中至多有一个能导出空串
3、如果β→ε，那么α不能导出以FOLLOW(A)中的终结符开始的任何串。
对于求单个文法符号X的时间复杂度，假设文法符号的个数为n，非终结符个数为m，由于循环的次数与嵌套的层数和计算的顺序有极大的关联，最坏情况要循环O（n）次，为方便计算，再根据实际情况假设每个产生式右部的文法符号个数为10，所以，求单个文法符号X的时间复杂度为O（10*n*m）= O(mn),而对于符号串α，假设它包含k个符号，则计算它的时间复杂度为O（mnk），求出了FIRST集采能求FOLLOW集，易知求FOLLOW集的时间复杂度也为O（mn）。
构造预测分析表的方法：
输入：文法G
输出：分析表M。
方法：
1、对于文法中的每个产生式A→α，执行第二步和第三步
2、对FIRST(α)中的每个终结符α，将A→α加入到M[A,a]中
3、若ε在FIRST(α)中，则对FOLLOW(A)的每个终结符b，将A→α加[]入到M[A,b]中，若ε在FIRST(α)中，且﹟在FOLLOW(A)中，则将A→α加入到M[A,﹟]中
4、将M中每个没定义的表项均置为error
分析表是一个二维数组M[A,a],A是语法变量，a是输入符号或#。也可以在O（mn）的时间内求出，两种方法其实都用到了预测LL（1）分析表，只不过使用的方法不太一样。
2.1.4 预测分析法
对于预测分析法，它采用表驱动的方式来实现，它具有一个输入缓冲区、一个分析栈、一张LL（1）分析表和一个输出流。输入缓冲区中包含待
- 3 -
错误！使用“开始”选项卡将 标题 1,章标题(有序号) 应用于要在此处显示的文字。 错误！使用“开
始”选项卡将 标题 1,章标题(有序号) 应用于要在此处显示的文字。
分析的串和结束符#。分析栈用来存放文法符号序列，栈底符号是#。初始时，栈中只有文法开始符号及其下的#。整个分析过程在于从文法开始符号开始，试图构造输入缓冲区中待分析串的最左推导。假设某程序共有符号s个，整个控制程序的时间复杂度为O（s）。
使用预测分析的主要困难在于为源语言编写一个能构造出预测语法分析器的文法。虽然消除左递归和提取左因子都非常简单，但它们使得结果文法很难阅读而且不易翻译。
2.1.5 递归下降分析法
而对于递归下降分析法，是指根据各个候选式的结构，为文法的每个语法变量编写一个处理子程序，用来识别该语法变量所代表的语法成分。设有产生式A X1X2X3„Xk„Xn，则与A对应的处理子程序遇到的Xk是终结符时直接进行匹配，而遇到Xk是语法变量时就调用与Xk对应的处理子程序。由于产生式中的语法变量可能是递归定义的，所以这种实现方法要求处理子程序可以递归调用。另外，这种分析方法也是寻求输入串的一个推导过程，所以称为递归下降分析法。实际上，上面所说的预测分析法是一种特殊的递归下降分析法，它是通过显示地维护一个状态栈而不是通过隐式的递归来实现的。如果编译程序的实现语言允许进行过程的递归调用，则可以采用一般形式的递归下降分析法。这种方法的主要优点是易于实现。此外，由于分析器和文法的紧密对应性，这种方法还易于保证语法分析器的正确性。其缺点是频繁的递归调用会降低分析器的效率，而且与预测分析法相比，这种分析器的代码规模非常大。尽管如此，递归子程序法仍然是一种有效的语法分析方法，因为在实际应用中，递归的层次往往不会太深，许多高级程序设计语言的编译系统都采用这种分析方法。
2.1.6 综述
总之，自顶向下分析法只能处理上下文无关文法的一些子类，对于文法的限制也比较多，而且其中许多部分必须人工手动完成，比较难以实现自动化，与之相反的是自底向上的LR分析法，基于LR分析法的良好形式和理论基础，人们可以寻求这种方法的进一步自动化，于是就有了Yacc之类的语法分析程序自动生成工具。
- 4 -
错误！使用“开始”选项卡将 标题 1,章标题(有序号) 应用于要在此处显示的文字。 错误！使用“开
始”选项卡将 标题 1,章标题(有序号) 应用于要在此处显示的文字。
2.2 LR(0)文法
LR(0)语法分析属于自底向上的语法分析。自底向上的语法分析的思想就是从输入串出发，反复利用产生式进行归约，如果最后能得到文法的开始符号，则输入串是句子，否则输入串有语法错误。核心是寻找句型中的当前归约对象——“句柄”进行归约,用不同的方法寻找句柄，就可获得不同的分析方法。
LR(0)文法
如果其LRSM0的每个状态S都有|Γ0(S)|=1，即Γ0(S)只包含一个元素，我们称文法G是LR(0)文法。
若Γ0(S)={ Shift }，则表示S只含移入项目
若Γ0(S)={ Reduce j }，则表示S只含一个[j]归约项目。
每个状态的移入/归约动作的确定没有冲突，而且不依赖于输入符号 LR(0)分析方法的不足
LR(0)方法对文法的要求严格。
LR(0)方法容易出现冲突状态。
2.3 SLR(1)文法。
上下文无关文法不是都能用LR(0)方法进行分析的，也就是说，CFG不
- 5 -
错误！使用“开始”选项卡将 标题 1,章标题(有序号) 应用于要在此处显示的文字。 错误！使用“开
始”选项卡将 标题 1,章标题(有序号) 应用于要在此处显示的文字。
总是LR(0)文法。当文法分析过程中会出现归约—归约冲突和移进-规约冲突时，此文法就不是LR（0）文法。
下面写一下对几种自底向上文法的比较。LR(1)总体来说，就是从左到右扫描输入符号。最右推导对应的最左归约，超前读入1个符号，以便确定归约用的产生式。
为解决LR（0）中的冲突，SLR分析法引入了每个符号的FOLLOW集，SLR(1)分析方法描述能力强于 LL(1) ，SLR(1)还考虑FOLLOW集中的符号，LL(1) 仅考虑产生式的首符号。
SLR(1) 文法是在LR（0）分析表的基础上增加了FOLLOW集，可以解决一部分冲突，但是，SLR文法依然有解决不了的问题。SLR（1）只孤立地考察输入符号是否属于归约项目A→α.相关联的集合FOLLOW（A），而没有考察符号串α所在规范句型的“上下文”。即未考虑规约的有效性，即只考虑了FOLLOW集是否符合规约条件，而没有考虑输入串中后面的字符。
SLR(1)和LR(0)具有相同的状态机
LR(0)只看分析栈的内容，不考虑当前输入符;SLR(1)考虑输入符，用follow集来解决冲突，因此SLR(1)要比LR(0)分析能力强
2.4 LL（1）文法
LR(1)分析方法的引入
LR(0)方法不依赖输入流，直接判定归约，容易出现冲突。
SLR(1)方法简单的把非终极符的follow集做为可归约的依据，并不精确。 一个非终极符在不同的位置上出现，它所允许的后继符是不同的。LR(1)针对不同产生式上的非终极符，分别定义其后继符集（展望符集Reducelookup），减少了移入/归约冲突。
LR(1)分析方法
∙ LR(1)方法研究的对象是二元组：(α, b)，其中α是活前缀，而b是一个输入符号。我们称上述(α , b)为LR1前缀模式。
∙ 如果α是文法的归约活前缀，b是α的合法后继续符，则称(α , b)为LR1归约前缀模式。
LR(1)文法
- 6 -
错误！使用“开始”选项卡将 标题 1,章标题(有序号) 应用于要在此处显示的文字。 错误！使用“开
始”选项卡将 标题 1,章标题(有序号) 应用于要在此处显示的文字。
投影函数Γ2 :
·Γ2：(StateSet×VT∪{#})→2Ω
·Γ2(S,a)=
{Reducej |[B→π·, a]∈S, B→π是产生式j}∪( if 存在a∈VT 使得[A→α·aβ, b]∈S then {Shift} else φ)
如果LR(1)状态机的任一状态S和输入符a，都使得|Γ2(S,a)|≤1，则称文法为LR (1)文法。
因为LR（1）在构造状态时就考虑follow集，而不是在规约时考虑。与LR（0）文法类似，识别文法全部活前缀的DFA的每一状态也是用一个LR
（1）项目集来表示，为保证分析时，每一步都在栈中得到规范句型的活前缀，应使每一个LR（1）项目集仅由若干个对相应活前缀有效的项目组
成。但是文法的强大也会带来一些代价，LR（1）分析表相比起LR（0）和SLR（1）庞大许多，相对来说也会有比较大的运行开销
- 7 -
错误！使用“开始”选项卡将 标题 1,章标题(有序号) 应用于要在此处显示的文字。 错误！使用“开
始”选项卡将 标题 1,章标题(有序号) 应用于要在此处显示的文字。
2.5 LALR(1) 文法
LALR(1)的思想来源
LR(1)状态机和LR(0)状态机从它们所表示的自动机角度来看是等价的 ； ·自动机可通过合并等价状态来减少状态个数。
·在LR(1)状态机出现很多同心状态，而LALR(1)状态机则不产生同心的状态，从而大大减少状态 数，这就是LALR(1)和LR(1)的主要差别。
LALR(1)语法分析属于自底向上的语法分析。LALR（1）是对LR（1）状态的简化，不同的LR(1)项目闭包可能有相同的LR(0)项目，但后继符可能不同，我们称这种情况为两个闭包同心，将两个同心闭包合并，即是LALR
（1）文法。它的显著好处就是减少了状态的数量，缩减了分析表，但是合并后可能带来归约—归约冲突。合并那些不会带来冲突的同心的LR(1)闭包/状态，可以得到LALR（1）分析表，反之，如果合并会出现规约-规约冲突，那么不能使用LALR（1）分析法，换句话说，存在合并后规约规约冲突的文法不是LALR（1）文法。分析能力LALR（1）强于SLR（1），因为合并后的后继符仍然是FOLLOW集的子集，弱于LR（1），因为有上述局限性。
2.6 算符优先文法
2.6.1 概述
算符优先分析法是一种简单适用的方法，用这种方法分析程序设计语言中的各类表达式尤为有效。由于这种方法简单直观，它还特别适用于手工方式来实现。所谓算符优先分析就是将句型中的终结符当做算符，然后定义算符之间的某种优先关系，利用这种优先关系来寻找句柄并进行规约，也是一种自下而上的分析方法。
- 8 -
错误！使用“开始”选项卡将 标题 1,章标题(有序号) 应用于要在此处显示的文字。 错误！使用“开
始”选项卡将 标题 1,章标题(有序号) 应用于要在此处显示的文字。
2.6.2 过程
首先要构造FIRSTOP集合和LASTOP集合，构造过程中分别使用了一个|V|*|T|大小的二维布尔数组来表示某个终结符b是否在B的FIRSTOP集合或LASTOP集合中，又使用了一个栈来帮助计算其他非终结符的这两个集合。算法的时间复杂度主要主产生式的个数有关，设产生式个数为p，则该算法时间复杂度为O（）
- 9 -
错误！使用“开始”选项卡将 标题 1,章标题(有序号) 应用于要在此处显示的文字。 错误！使用“开
始”选项卡将 标题 1,章标题(有序号) 应用于要在此处显示的文字。
第3章 总结
综上，各种分析文法其实无所谓孰优孰劣，就看适用在那些场合，就分析能力来说，LR（1）>LALR(1) >SLR(1)>LL(1)>LR(0)，但是相对来说就可能带来更大的实现复杂度和开销。我们在决定使用哪种分析方法时，主要是看定义的文法，一般的文法只要稍加修改，SLR（1）和LALR（1）的要求是很容易满足的，可以适用于大部分分析程序，比如yacc语法分析器内部就是使用SLR（1）分析法。
- 10 -
错误！使用“开始”选项卡将 标题,章标题(无序号) 应用于要在此处显示的文字。
- 11 -