编译原理

文法和语言

终结符和非终结符

终结符可以简单地理解为「推导到这里就终结了」，也就是说不能再继续通过生成式向下推倒的元素就是终结符。

比如 T->abc。T 推导为串 abc 后已经得到了实质上的字符，不用在向下推导了，那么 T 为非终结符，abc 无法继续推导，则为终结符。（在一系列生成式中，式子左边的一定是非终结符，从未出现在式子左边的一定是终结符）

句子与句型

如果符号串x是由起始符号推导出的，则称x是文法G[S]的句型。

如果x中只包含终结符，则称x是文法G[S]的句子。

文法描述的语言是该文法一切句子的集合。

四种文法

0型文法：α→β，其中α至少包含一个非终结符。

1型文法（上下文有关文法）：α→β，其中|β|≥|α|，S→ε除外。

2型文法（上下文无关文法）：a→β，其中a是一个非终结符。

3型文法（规范文法）：A→a或A→aB.

4种文法是逐渐增加限制的，所以规范文法一定是0型文法、1型文法、2型文法，上下文无关文法也一定是0型文法、1型文法…

上下文有关文法与上下文无关文法

在应用一个产生式进行推导时，前后已经推导出的部分结果就是上下文。上下文无关指，只要文法的定义里有某个产生式，不管一个非终结符前后的串是什么，就可以应用相应的产生式进行推导。

上下文无关文法例子：

Code
产生式：
Sent -> S V O
S -> 人 | 天
V -> 吃 | 下
O -> 雨 | 雪 | 饭 | 肉

这个文法可以生成如下句子（共 16 种组合）：

｛人吃饭，天下雨，人吃肉，天下雪，人下雪，天下饭，天吃肉，……｝

可以看到，其中有一些搭配在语义上是不恰当的，例如”天吃肉“。其（最左）推导过程为：

Sent -> SVO -> 天VO -> 天吃O -> 天吃肉

而上下文有关文法例子如下：

Code
Sent -> S V O
S -> 人 | 天
人V -> 人吃
天V -> 天下
下O -> 下雨 | 下雪
吃O -> 吃饭 | 吃肉

可以看到，这里对 V 的推导过程施加了约束：虽然 V 还是能推出”吃“和”下“两个词，但是仅仅当 V 左边是”人“时，才允许它推导出”吃“；而当 V 左边是”天“时，允许它推导出”下“。这样通过上下文的约束，就保证了主谓搭配的一致性。类似地，包含 O 的产生式也约束了动宾搭配的一致性。（就是语法的强约束条件，导致上下文有关了）

这样一来，这个语言包含的句子就只有｛人吃饭，天下雨，人吃肉，天下雪｝这四条，都是语义上合理的。

以”人吃饭“为例，推导过程为：

Sent -> SVO -> 人VO -> 人吃O -> 人吃饭

（这与语法的歧义性还是不同的，要有所区分）

1型文法比2型文法识别的语言集合更大？

上例看到，感觉上下文有关文法所解释的句子集合更少。

这里的“1型文法比2型文法识别的语言集合更大” 这里的集合不是产生的结果集（字符串集合），而是语言规则集。 2型文法规则一定是1型文法规则，而有些语言能用1型文法规则描述，但用2型文法规则描述不出来。

语法树

最左推导/最右推导/规范句型

例如 E+E (i+i)：

• E+E => E+i => i+i ——最右推导
• E+E => i+E => i+i ——最左推导

最左推导是指：任何一步α=> β都是对α中的最左非终结符进行替换。

同样，可定义最右推导（又称规范推导）：任何一步α=>β都是对α中的最右非终结符进行替换。

由规范推导所得到的句型称为规范句型。

（要证明某句型为左（右）句型，即最左（最右）推导能推导出该句型）

二义性

一个文法的某个句子对应两棵不同的语法树，则这个文法是二义的。

或一个文法的某个句子有两个不同的最左（右）推导，则这个文法是二义的。

人们已证明，二义性问题是不可判定的，即不存在一个算法，它能在有限步骤内，确切地判断一个文法是否是二义的。（做题时就画两颗不同的语法树来证明其二义性）

自上而下的分析法

基本思想：从文法的开始符号出发，反复使用各种产生式，寻找“匹配”输入符号串的推导。即对任何输入符号串，从文法的开始符号（根结）出发，自上而下地为输入串建立一棵语法树，直到语法树结果正好是输入的符号串为止。

自下而上的分析法

基本思想：从输入串开始，逐步进行“归约”，直至归约到文法的开始符号。即从语法树的末端开始，步步向上“归约”，直到根结。

短语、直接短语、句柄

1. 短语

   令文法G，开始符号为S，αβδ是G的句型（即S=>αβδ），如果S=>αAδ且A=>β，则称β是句型αβδ相对于非终结符A的短语。

   （非终结符不断推导，只剩不能推导的符号）

2. 直接短语

   如短语中有A=>β，则称β是句型相对于规则A→β的直接短语。

   （非终结符一次推导，只剩不能推导的符号，才能称为直接短语）

3. 句柄

   一个句型的最左直接短语称为该句型的句柄。

⒈ 先证明前提

⒉ 给出语法树（注意文法是否是二义性的）

　如题文法G[E]: E→ E+E|E*E|(E) | i

证明i+i*i是G的一个句型，并指出这个句型的所有短语、直接短语、句柄。

⒊ 根据每棵语法树得出短语、直接短语、句柄

　（注意编号）

词法分析

NFA→ DFA的转换（NFA的确定化）

确定化的有关运算

（1）ε_closure(I) ——状态集合I的ε闭包(等价状态集)

设I是状态集的一个子集，ε_closure(I)定义为：

​ a.若S∈I，则S∈ε_closure(I)；

​ b. 若S∈I，那么从S出发经过任意ε弧而能到达的任意状态S’都属于ε_closure(I)；

（2）Move(I, a)——状态集合I的a弧转换

假定I是状态集的一个子集，a是Σ中的一个字符，定义

​ Ia ＝ ε_closure(J)

其中J是所有那些可从I中的某一状态出发经过一条a弧而到达的状态结的全体。

　(3)Ia＝ ε_closure(Move(I, a))

子集化的具体过程

为了方便起见，令Σ中只有a,b两个字母，即Σ＝{a, b}

（1）构造一张表，此表的每一行有三列，第一列为I，第二列为Ia，第二列为Ib。即

I	Ia	Ib
ε_closure(K0)

首先置该表的第一列为ε_closure(K0)

（2）一般而言，若某一行的第一列的状态子集已确定，例如记为I，则可以求出Ia和Ib

（3）检查Ia和Ib是否已在表的第一列中出现，把未曾出现者填入到后面空行的第一列位置上。

（4）对未重复Ia 、Ib的新行重复上述过程(2)、(3)，直到所有第二列和第三列的子集全部在第一列中出现

DFA 的初态位该表第一行第一列的状态

DFA 的终态为含有原 NFA 的终态的状态子集

I	Ia	Ib	S	a	b
{0,1,2,4,7}	{1,2,3,4,6,7,8}	{1,2,4,5,6,7}	0	1	2
{1,2,3,4,6,7,8}	{1,2,3,4,6,7,8}	{1,2,4,5,6,7,9}	1	1	3
{1,2,4,5,6,7}	{1,2,3,4,6,7,8}	{1,2,4,5,6,7}	2	1	2
{1,2,4,5,6,7,9}	{1,2,3,4,6,7,8}	{1,2,4,5,6,7,10}	3	1	4
{1,2,4,5,6,7,10}	{1,2,3,4,6,7,8}	{1,2,4,5,6,7}	4	1	2

DFA的化简

1. 将得到的状态进行划分 ∏ ，划分为两部分，一部分为终态，一部分为为非终组。
2. 继续进行划分，通过其可以匹配的字符进行判断，若该组内所有成员匹配字符都落在同一组内，即不可再分，否则重新划分组
3. 若 ∏new = ∏ ，则进入步骤4，否则返回2
4. 在分组 ∏new 每个组中选取一个状态作为代表，代表DFA的最简状态。

正规式→NFA

自顶向下语法分析方法

对于任一输入符号串，从文法的识别符号出发，根据当前的输入符号，唯一的确定一个产生式，用产生式的右部的符号串替代相应的非终结符往下推导，或构造一棵语法树。若能推导出输入串或构造语法树成功则输入串是句子，否则不是。

开始符号FIRST集合

理解

FIRST(A)是以A开始符的集合，A的所有可能推导的开头终结符或者是ε

例子

1. 后面跟的不是非终结符

   ...
   A->aB|ε
   A->c
   ...
   First(A)={a,ε,c}

2. 后面跟非终结符（一）

   ...
   A->Ba
   A->b
   ...
   First(A)={b}

3. 后面跟的非终结符（二）

   ...
   A->Bc
   B->b|ε
   ...
   First(A)={b,c}

4. 后面跟的非终结符（三）

   ...
   A->BC
   B->b|ε
   C->c|ε
   ...
   First(A)={b,c,ε}

构造文法G的每一文法符号X，X ∈ (VT∪VN)

• 如果 X 是终结符号，那么FIRST(X)={X}

• 如果 X 是非终结符号，且 X -> Y1Y2Y3…Yk 是产生式

  • 如果a在FIRST(Yi)中，且 ε 在FIRST(Y1)，FIRST(Y2)，…，FIRST(Yi-1)中，那么a也在FIRST(X)中；
  • 如果ε 在FIRST(Y1)，FIRST(Y2)，…，FIRST(Yk)中，那么ε在FIRST(X)中；

• 如果X是非终结符号，且有X->ε，那么ε在FIRST(X)中

后跟符号FOLLOW集合

理解

Follow(A)为非终结符A后跟符号的集合，Follow(A)是所有句型中出现在紧接A之后的终结符或’#‘

求解规则

将标记 # 放到 FOLLOW(S) 中

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

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

理解求解规则

1. 将标记 # 放到 FOLLOW(S) 中

2. 形如A -> αBβ

   （α可以是终结符或者非终结符或者直接为空，β可以是终结符或者非终结符，注意β不能为空，B后面要有东西）

   比如

   A->B
   A->cB
   
   A->dBC
   C->ε

   那么 FOLLOW(A) 中的所有符号都加入到 FOLLOW(B) 中

   例子一

   注意：[if] 是一个终结符，同理[b] [other] [else] [then]

   G(S)：S->IETSP|O
   I->if
   E->b
   O->other
   L->else
   T->then
   P->LS|ε

   First	Follow
   First(S)={if,other}	Follow(S)={井号 ,else}
   First(I)={if}	Follow(I)={b}
   First(E)={b}	Follow(E)={then}
   First(O)={other}	Follow(O)={else,井号}
   First(L)={else}	Follow(L)={if,other}
   First(P)={else,ε}	Follow(P)={else,井号}
   First(T)={then}	Follow(T)={if,other}

Select集合

理解

1. 如果a不能=>ε，则 Select(A->a)=First(a)
2. 如果a=>ε，则 Select(A->a)=(First(a)-{ε})UFollow(A)

LL(1) 文法的判别

满足定义

1. 求出能推出ε的非终结符
2. 求FIRST集合；
3. 求FOLLOW集合；
4. 计算SELECT集合。
5. 对同一非终结符的不同产生式求Select交集

某些非LL(1)文法到LL(1)文法的等价转换

存在左公因子

解决方法：提取左公因子

若文法中存在形如：

A->ay|ab   
两个产生式左部第一个符号相同，则不符合LL（1）文法，指代不明，则表示存在左公因子

解决方法：
转换成 A->aM1,aM2，aM3....的形式：
得：
A->aM
M->y|b
则成功提取左公因子；

存在左递归

（1）直接左递归

A->AB, A∈Vn，B属于V*

方法：左递归变右递归

P->β1P'|β2P'|…|βnP'
P'->α1P'|α2P'|…|αmP'|ε

例：给定文法G(S):

E->E+T|T
T->T*F|F
F->(E)|i

消除其直接左递归G(E):

E->TE'
E'->+TE'|ε
T->FT'
T'->*FT'|ε
F->(E)|i

（2）间接左递归

A->Bb
B->Aa
A,B∈Vn，a，b属于V*

（这里第二种情况注意，因为是左递归，所以看得就是第一个字符，一定要跟这个类型一样的A->B…. 以及B->A…. 这种才是左递归，如果A->B…. ,B->aA…, 这种就不是左递归了，因为样式不同，请注意）

同样消除左递归的方法：

如果是间接左递归，则先转换成直接左递归：

例子：

A->Bb | c
B->Aa

将B->Aa代入到另一个式子：

A->Aab | c

转换

A->cM
M->abM
M->ε

递归下降子程序

已知文法G[S]：

S→aH
H→aMd | d  
M→Ab |ε  
A→aM | e

构造其递归下降分析程序

PROCEDURE S
BEGIN
	IF SYM=‘a’ THEN 
	BEGIN
		ADVANCE;
		H ;
	END
	ELSE    
		ERROR
END

PROCEDURE  H
BEGIN    
    IF SYM=‘d’ THEN		
    	ADVANCE;
   	ELSE
   		IF SYM=‘a’ THEN
   		BEGIN
   			ADVANCE;
   			M;
   			IF SYM=‘d’ THEN
                ADVANCE;
   			ELSE      
   				ERROR
   		END
   	ELSE
   		REEOR
END

PROCEDURE  M
BEGIN    
    IF SYM=‘a’ || SYM=‘e’ THEN
    BEGIN
    	A;
        IF SYM=‘b’ THEN
        	ADVANCE;       
        ELSE  
            ERROR;
    END
END

PROCEDURE  A
BEGIN    
     IF SYM=‘e’ THEN
     	ADVANCE;
     ELSE
     	IF SYM=‘a’ THEN
     	BEGIN
     		ADVANCE;
     		M;
     	END
     ELSE
     	ERROR
END

构造预测分析表

构造预测分析表的步骤

1. 对每个终结符 a∈FIRST(a)，将 A->a 加到 M[A, a] 中
2. 如果 ε∈FIRST(a)，则对于任何 b∈FOLLOW(A)，将 A->a 加到 M[A, b] 中

期中考

文法与语言

• 说明文法的语言
• 产生式的所有元素
• 写出最左/最右推导，或证明其为左/右句型
• 画出语法树（证明二义性）
• 写出所有短语、简单短语、句柄

词法分析

• 正规式->NFA
• NFA->DFA
• DFA的化简

自顶向下语法分析方法

• LL1文法判别
  • first
  • follow
  • Select
• 文法的等价转换（消除左递归、左公因子）
• 不带回溯的递归子程序
• 预测分析表
• 分析过程

自底向上优先分析

算符优先文法

概述

算符优先分析法(Operator Precedence Parse)是仿效四则运算的计算过程而构造的一种语法分析方法。算符优先分析法的关键是比较两个相继出现的终结符的优先级而决定应采取的动作。

优点：简单，有效，适合表达式的分析。

缺点：只适合于算符优先文法，是一个不大的文法类。

算符优先关系的定义

（算符优先三种关系的符号，中间都有圆点）

• a < b 文法中有形如 A→…aB… 的产生式而 B=>b… 或 B=>Cb…
• a < b 文法中有形如 A→…ab… 或 A=>…aBb… 的产生式
• a > b 文法中有形如 A→…Bb… 的产生式而 B=>…a 或 B=>…aC

FIRSTVT和LASTVT的构造规则

FIRSTVT
找FIRSTVT的三条规则：如果要找A的FIRSTVT，A的候选式中出现：

• A->a…，即以终结符开头，该终结符入FIRSTVT
• A->B…，即以非终结符开头，该非终结符的FIRSTVT入A的FIRSTVT
• A->Ba…，即先以非终结符开头，紧跟终结符，则终结符入FIRSTVT

LASTVT
找LASTVT的三条规则：如果要找A的LASTVT，A的候选式中出现：

• A->…a，即以终结符结尾，该终结符入LASTVT
• A->…B，即以非终结符结尾，该非终结符的LASTVT入A的LASTVT
• A->…aB，即先以非终结符结尾，前面是终结符，则终结符入FIRSTVT

构造算法优先关系表

• a=b 关系

  可直接查看产生式的右部，对如下形式的产生式

  A->…ab…

  A->…aBb…

  则有 a=b 成立

• a<b 关系

  对于所给表达式文法中终结符 a 在前，非终结符 B 在后的所有相邻符号对，有 b 属于FIRSTVT(B)，则 a<b 成立

  a<FIRSTVT()

• a>b 关系

  对于所给表达式文法中非终结 B 在前，终结符 a 在后的所有相邻符号对，有 a 属于LASTVT(B)，则 b>a 成立

  LASTVT()>a

例子

已知文法：
S -> a|^|(T)
T -> T,S|S

FIRSTVT和LASTVT的构造

FIRSTVT(S)={a, ^, (}

FIRSTVT(T)={a, ^, (, 逗号}

LASTVT(S)={a, ^, )}

LASTVT(T)={a, ^, ), 逗号}

构造算法优先关系表

1. 引进产生式 S’ -> #S#

2. 找 a=b 关系

   S -> (T) 有 (=)

   S’ -> #E# 有 #=#

3. 找 a<b 关系

   S -> (T) 有 ( < FIRSTVT(T)={a, ^, (, 逗号}

   T -> T,S 有 逗号 < FIRSTVT(S)={a, ^, (}

   S’ -> #S# 有 # < FIRSTVT(S)={a, ^, (}

4. 找 a>b 关系

   S -> (T) 有 LASTVT(T)={a, ^, ), 逗号} > )

   T -> T,S 有 LASTVT(T)={a, ^, ), 逗号} > 逗号

   S’ -> #S# 有 LASTVT(S)={a, ^, )} > #

结果如下表

	a	^	(	)	,	#
a				>	>	>
^				>	>	>
(	<	<	<	=	<
)				>	>	>
,	<	<	<	>	>
#	<	<	<			=

规约过程

• 因为非终结符不能影响语法分析，所以不需要区分它们，于是在这里用 S 来代替它们
• 优先关系比较，是比较栈顶的终结符和下一个输入符之间的优先关系
• 如果栈顶的终结符和下一个输入符之间的优先关系是 < 或 = ，则移进，如果是 > 关系，就调用归约

(a, a)#

步骤	符号栈	优先关系	剩余输入串	动作
(1)	#	<	(a,a)#	移进
(2)	#(	<	a,a)#	移进
(3)	#(a	>	,a)#	规约(S -> a)
(4)	#(S	<	,a)#	移进(忽略S进行比较)
(5)	#(S,	<	a)#	移进
(6)	#(S,a	>	)#	规约(S -> a)
(7)	#(S,S	>	)#	规约(T -> T,S)
(8)	#(S	=	)#	移进(未分析完成，继续)
(9)	#(S)	>	#	规约(S -> (T))
(10)	#S	=	#	分析成功

名词解释

• 短语

  令文法G，开始符号为S，αβδ是G的句型（即S=>αβδ），如果S=>αAδ且A=>β，则称β是句型αβδ相对于非终结符A的短语。

  （非终结符不断推导，只剩不能推导的符号）

• 直接短语

  如短语中有A=>β，则称β是句型相对于规则A→β的直接短语。

  （非终结符一次推导，只剩不能推导的符号，才能称为直接短语）

• 句柄

  一个句型的最左直接短语称为该句型的句柄。

• 素短语

  文法G某句型的一个短语是素短语，当且仅当它至少含有一个终结符，且除它自身之外不再含更小的素短语。

• 最左素短语

  在具有多个素短语的句型中处于最左边的那个素短语

做法：画语法树

LR 分析

注：由于 # 的转义问题，有些地方用 井 代替

LR(0)分析

结构

LR分析表的结构如上，其分为两个部分Action、Goto

Action

两个参数状态i，终结符号a（s(i)代表第i个状态，r(i)代表第i条表达式）

• 移入j：j是一个状态，把j压入栈（同时移入a）
• 归约A->B：把栈顶的B归约到A（并根据Goto表项压入新状态）
• 接受：接受输入，完成分析
• 报错：在输入中发现语法错误

Goto

Goto[i,A]=j

项目

• 移进项目。原点为终结符的项目，比如 E->a·bB

• 规约项目。圆点在产生式右部最后的项目，比如 A->d·

• 待约项目。圆点后为非终结符的项目，比如 E->b·B

• 接受项目。规约项目为 S’->S·，表示已分析成功

项目集非法情况：

• 移进和规约项目同时存在
• 规约和规约项目同时存在

若不存在上述情况，称文法为 LR(0) 文法

LR(0)分析表构造

若有定义二进制数的方法如下：
E->aA | bB
A->cA | d
B->cB | d
试为该文法构造 LR 分析表

因为本题入口有两个—— E -> aA 和 E -> bB，所以需要构造额外的产生式 S’->E

1. 扩充

   (0) S'->E
   (1) E->aA
   (2) E->bB
   (3) A->cA 
   (4) A->d
   (5) B->cB 
   (6) B->d
   //考试时要标好序号

2. 项目

   接下来求文法的项目，就是给每个规则加一个点以后然后挪位置，挪一个位置就得到一个项目，如下

   1.S'->·E    2.S'->E·    3.E->·aA    4.E->a·A    5.E->aA·    6.A->·cA   
   7.A->c·A    8.A->cA·    9.A->·d     10.A->d·    11.E->·bB   12.E->b·B   
   13.E->bB·   14.B->·cB   15.B->c·B   16.B->cB·   17.B->·d    18.B->d·

3. 项目集规范族

   把有 S’ 的项目而且点在最左边的项目作为状态 I0 的核，放在开头。然后看这个点后面的非终结符，是个 E，接下来就去项目中找左部是 E 的而且点在最左边开头位置的项目，列在核的下面，这就是状态 I0

   • S’->·E
   • E->·aA
   • E->·bB

   接下来还是先看核里面点后的这个非终结符E，输入E（你可以理解为在箭弧上标了个E），把点向后移一位，得到 S’->E·，这其实是得到了一个新的状态的核。当然另外两个也一样，输入点后面的符号，比如输入a得到 E->a·A 为核的新状态，输入b得到 E->b·B 为核的新状态。得到新状态的核了，就是看核的点后面的非终结符，找以这个非终结符为左部的点在最左边的项目。如果点后面没有东西就不用找了。

   

   接下来就是重复上面的工作，从每一个新状态出发，逐个输入每个项目点后面的符号，就是后移一位，又分别作为新的状态的核然后根据核找下面的同状态里的项目。找到找不动为止。

   （项目集标号（I0，I1…）最好按照广度优先搜索的方式标号）

   

4. 分析表

   先写好 ACTION 和 GOTO 两个列标题，然后在 ACTION 下面写一排文法的所有的终结符，别忘了还有 #，GOTO下面写文法中除了 S’ 以外的所有的非终结符。

   

   1. 找项目集规范族有 S’->A· 这种形状的那个状态 Ik，就是第 k 个状态，则把分析表第 k 行的 # 列标上 acc

      （例子中，状态 I1 里面有 S’->E·，所以 acc 在第1行）

   2. 按顺序（一般是按状态序号顺序）分析状态的项目和GOTO函数，主要就是看每个项目的 · 后面的符号

      1. 如果是终结符，看输入这个终结符后去的哪个状态，比如当前是状态 I0，对于第二个项目 E->·aA，输入 a 以后去了状态 I2，那就在分析表中第 0 行的 a 列写上 S2，意思就是状态 Ik 输入 Vt 后去了 Ij 状态。
      2. 如果为非终结符，这个更好理解，比如从状态 Ik 输入这个非终结符以后去了状态 Ij ，那就在GOTO表的第 k 行第 Vn 列写 j。

   3. 有的项目的点是在最后。先看这个项目所在的状态，再看点前面的规则是文法里面的第几个规则，比如说状态 I10 的 A->d· 里面的 A->d 就是文法的第 4 条规则，那就在分析表的第 10 行所有的终结符列包括 # 列写上 r4，就是 ACTION 列的一行写满。即状态 Ik 的项目来自于文法的第 j 条规则，则分析表的第 k 行都是 rj。

   结果如下：

   

5. 分析过程

   分析bccd

   符号栈中是#，输入符号串就是给定的要分析的串，状态栈因为从0开始，所以状态栈直接填0

   当前输入串bccd#，即将输入b，看状态栈顶是0，看分析表第0行第b列是S3。把角标3压状态栈，b压符号栈，输入串少一个。

   当前为ccd#，即将压c，状态栈顶为3，看分析表第3行第c列是S5，5和c分别压栈。

   当前为cd#，即将压c，状态栈顶为5，看分析表第5行第c列是S5，5和c分别压栈。

   当前为d#，即将压d，状态栈顶为5，看分析表第5行第d列是S11，11和d分别压栈。

   当前为#，即将压#，状态栈顶为11，看分析表第11行第#列是r6。看文法的第6条规则，把符号栈顶归约为B，状态栈顶11弹出。然后再看状态栈顶5和符号栈顶B，GOTO表第5行第B列是9，记得在分析过程这一步的GOTO写9，然后把9压状态栈。这里要分清栈操作的先后顺序。

   当前为#，即将压#，状态栈顶为9，看分析表第9行第#列是r5，看文法的第5条规则，cB 归约成 B ，状态栈顶5和9弹出，然后找GOTO表把新状态9压栈。

   重复上面的操作。

   最后一步，状态栈顶为1，即将压#，分析表第1行第#列为acc，至此分析结束，bccd是该文法的产生式。

   步骤	状态栈	符号栈	输入串	ACTION	GOTO
   1	0	#	bccd#	S3
   2	03	#b	ccd#	S5
   3	035	#bc	cd#	S5
   4	0355	#bcc	d#	S11
   5	0355(11)	#bccd	#	r6	9
   6	03559	#bccB	#	r5	9
   7	0359	#bcB	#	r5	7
   8	037	#bB	#	r2	1
   9	01	#E	#	acc

SLR(1) 分析

SLR分析表的构造步骤

1. 拓广文法并对产生式编序号
2. 构造相应的SLR的识别活前缀的DFA
3. 求出相关非终结符的Follow集合
4. 判断是否为SLR文法
5. 如是，则构造分析表

分析表构造

考察算术表达式文法的拓广文法：

(0) S’ -> E    (1) E -> E+T    (2) E -> T   (3) T -> T*F
(4) T -> F     (5) F -> (E)    (6) F -> i

前三步同 LR(0) 文法,，得到如下：

红框处存在移进-规约冲突（比如I1中 S’->E· 是规约项目，E->E·+T是移进项目）

首先找出所有点在最后的，即规约项目：

S’ -> E·  
E -> E+T·   
E -> T·  
T -> T*F·
T -> F·    
F -> (E)·   
F -> i·

求相关follow集（圆点·不算进去）

follow规则

将标记 # 放到 FOLLOW(S) 中

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

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

求得：

FOLLOW(S')={#}
FOLLOW(E)={#, +, )}
FOLLOW(T)=FOLLOW(F)={#, +, ), *}

分析表构造规则

1. 若项目 A→α • aβ 属于 Ik 且GO(Ik , a)= Ij，a 为终结符，则置 ACTION[k, a] 为“把(j, a)移进栈”，简记为“Sj”；
2. 若项目 A→α • 属于 Ik，那么对于任何输入符号 a，其中 a∈FOLLOW(A)，置 ACTION[k, a] 为“用产生式A→α进行归约”，简记为“rj”。这里的j指产生式 A→α 是文法 G’ 的第 j 个产生式；
3. 若项目 S’→S • 属于 Ik，则置 ACTION[k, #] 为“接受”，简记为“acc”；

步骤

1. 先填状态0，接受 i 到达5状态，所以填 S5；接受（ 到达4状态，填 S4；
2. 接受 E、T、F 分别到达1，2，3，在 GOTO 分别填1，2，3
3. 状态1，接收 + 到达6状态，填 S6
4. S’->E· 为接受项目，在 1 行的 # 列填 acc
5. 状态2，接受 * 到达7状态，* 列填 S7
6. FOLLOW(E)={+,井, )}，与 * 的交集为空，所以2行 +、）、井 列用产生式 E -> T 进行规约，填 r2，* 列移进，填 S7
7. 状态3，FOLLOW(T)={+,井, )，*}，在3行这些列用产生式 T -> F 进行规约，填 r4
8. 状态4-8按 SLR 规则填
9. 状态9，接受 * 到达7状态，* 列填 S7
10. FOLLOW(E)={井, +, )}，与 * 的交集为空，所以2行 +、）、井 列用产生式 E -> E+T 进行规约，填 r6，* 列移进，填 S7
11. 状态10、11填完，最终图如下：

可以看到，SLR(1) 分析表的构造和 LR(0) 分析表的构造类似，但有两处不同：

• SLR 在含有冲突的项目集中分别进行处理
• 只有一个规约项目时，LR不论输入符号，一律规约，而 SLR 只有当输入符号属于 FOLLOW 集合才能规约

LR(1)分析

解决 SLR(1) 不能解决的冲突

例子：

(0) S’ -> S      (1) S -> BB      (2) B -> aB       (3) B -> b

LR(1)项目集族的构造

规则

构造闭包函数：

I是一个项目集，closure(I)为：
(1) I的任何项目都是属于closure(I)；
(2) 若[A→α • Bβ,  a] 属于closure(I)， B→γ是一个产生式，那么对于FIRST(βa)中的每个终结符b，项目[B→ • γ,  b]也属于closure(I)；
(3) 重复执行步骤2，直到closure(I)不再增大为止。
注：b可能是从β推导出的第一个符号，或者，若β推导出ε，则b就是a。即b∈FIRST(βa)。展望符号通过自展来改变，传播不改变。

构造转换函数与 LR(0) 类似
令I是一个项目集，X 是一个文法符号，函数 GO(I,X) 定义为：
GO(I,X) = closure(J)
其中  J = {任何形如[A→α X• β,  a] 的项目 | [A→α • Xβ, a] ∈I}

步骤

1. 首先构造 I0。把 [S’ -> •S, 井] 放入，找出所有左部是 S 的而且点 • 在最左边开头位置的项目，有 [S -> •BB]，而 FIRST(井)={井}，所以为 [S -> •BB, 井]

   再找出所有左部是 B 的而且点 • 在最左边开头位置的项目，有 [B -> •aB] 和 [B -> •b]，而 FIRST(B井)={a,b}，所以为 [B -> •aB, a/b] 和 [B -> •b, a/b]

   I0为:

   • S’ -> •S , 井
   • S -> •BB, 井
   • B -> •aB, a/b
   • B -> •b, a/b

2. 接下来先看核里面点后的这个非终结符E，输入S（你可以理解为在箭弧上标了个 S），把点向后移一位，得到 [S’ -> S·,#]，这其实是得到了一个新的状态的核。当然另外两个也一样，输入点后面的符号，比如输入 a 得到 [B->a·B, a/b] 为核的新状态，输入b得到 [E->b· ,a/b] 为核的新状态。得到新状态的核，继续按照构造闭包函数规则构造，结果如下：

   

LR(1)分析表的构造

规则

假定 C={I0, I1,……, In}，令每个项目集 Ik 的下标 k 为分析器的一个状态。令那个含有项目 [S’→•S, #] 的 Ik 的下标 k 为初态，函数 ACTION 表和 GOTO 表可按如下方法构造：

1. 若项目 [A→α • aβ, b] 属于 Ik 且 GO(Ik , a)= Ij，a为终结符，则置 ACTION[k, a] 为“把 (j, a) 移进栈”，简记为“Sj”；
2. 若项目 [A→α •, a] 属于 Ik，那么置 ACTION[k, a] 为“用产生式 A→α 进行归约”，简记为“rj”。这里的j指产生式 A→α 是文法G’的第 j 个产生式；
3. 若项目 [S’→S •, #] 属于 Ik，则置 ACTION[k, #] 为“接受”，简记为“acc”；
4. 若 GO(Ik,A) = Ij ，A 为非终结符，则置 GOTO(k , A) = j；
5. 分析表中凡是不能用规则1到4填入信息的空白格，均置上“报错标志”

步骤

1. 状态0，接受 a 到达3状态，填 S3；接受 b 到达4状态，填 S4；

   接受 S，B到达1，2状态，在 GOTO 分别填1，2

2. 状态1，为 [S’→S •, #] ，# 列填 acc

3. 状态2，接受 a 到达6状态，填 S6；接受 b 到达7状态，填 S7；接受 B 到达5状态，在 GOTO 填5

4. 状态3，接受 a 到达3状态，填 S3；接受 b 到达4状态，填 S4；接受 B 到达8状态，在 GOTO 填8

5. 状态4，使用规则2，用产生式 B -> b 进行规约，a、b 列填 r3

6. 状态5，使用规则2，用产生式 S -> BB 进行规约，# 列填 r1

7. 按规则填完，结果如图：

   

LALR(1)分析

基本思想：

• 寻找具有相同核心的LR (1) 项集，并将这些项集合并为一个项集。 所谓项集的核心就是其第一分量的集合，即合并同心集
• 然后根据合并后得到的项集族构造语法分析表

首先构造 LR(1)项目集族，若不存在冲突，就把同心集合并

分析表的方法同 LR(1)

语义分析

后缀式

波兰表示是一种既不须考虑优先关系、又不用括号的一种表示表达式的方法（前缀式）。
逆波兰表示形式，称为后缀式，即运算符在后。

求法：

对单目运算符，直接将其放到变量后面，然后按照运算优先顺序，对双目运算符进行转换

例：

a+b -> ab+
a*(b+c) -> abc+*
-a+b*c -> a@bc*+ //单目减运算(即'-'负号用@符号代替)

三元式

三元式由三个部分组成：

• 算符：OP
• 第一运算分量：ARG1
• 第二运算分量：ARG2

X:=A+B*C 可表示成

	OP	ARG1	ARG2
(1)	*	B	C
(2)	+	A	(1)
(3)	:=	X	(2)

间接三元式

为便于代码优化处理，常常不直接使用三元式，而是另设一张指示器表（称为间接码表），它将按运算的先后顺序列出的有关三元式在三元表中的位置。即，用一张间接码表辅以三元式表来表示中间代码，这种表示法称为间接三元式。

例如 语句 X:=(A+B)*C; Y:=D ↑(A+B)的间接三元式表示

注意：在间接三元式下，相同的三元式，无需重复填进三元式表中，如上例中的(A+B)。但三元式和四元式需要重复填

四元式

四元式由四个部分组成：

• 算符：OP
• 第一运算分量：ARG1
• 第二运算分量：ARG2
• 运算结果：RESULT

ARG1、ARG2、RESULT有时指用户自定义的变量，有时指编译程序引进的临时变量。如果OP是一个算术或逻辑算符，则RESULT总是一个新引进的临时变量，用来存放运算结果

例：

A:=-B*(C+D)的四元式表示：

	OP	ARG1	ARG2	RESULT	注释
(1)	@	B	-	T1	T1是临时变量
(2)	+	C	D	T2	T2是临时变量
(3)	*	T1	T2	T3	T3是临时变量
(4)	:=	T3	-	A	赋值运算

凡只需一个运算量的算符一律规定使用ARG1

如同三元式一样，四元式出现的顺序与表达式计值的顺序是一样的

练习

写出 -A*(B+C)-D*(B+C)​ 的后缀式、三元式、间接三元式、四元式

后缀式：

A@BC+*DBC+*-

三元式：

	OP	ARG1	ARG2
(1)	@	A	-
(2)	+	B	C
(3)	*	(1)	(2)
(4)	+	B	C
(5)	*	D	(4)
(6)	-	(3)	(5)

间接三元式：

三元式表								
(1) (@,A,-)
(2) (+,B,C)
(3) (*,(1),(2))
(4) (*,D,(2))
(5) (-,(3),(4))

间接码表
(1)
(2)
(3)
(2)
(4)
(5)

四元式：

(1) (@,A,-,T1)
(2) (+,B,C,T2)
(3) (*,T1,T2,T3)
(4) (+,B,C,T4)
(4) (*,D,T4,T5)
(5) (-,T3,T5,T6)

---

写出 A+B*(C-D)+E/(C-D)**N 的后缀式、三元式、间接三元式、四元式

后缀式：

ABCD-*+ECD-N**/+

三元式：

(1) (-,C,D)
(2) (*,B,(1))
(3) (+,A,(2))
(4) (-,C,D)
(5) (**,(4),N)
(6) (/,E,(5))
(7) (+,(3),(6))

间接三元式：

三元式表
(1) (-,C,D)
(2) (*,B,(1))
(3) (+,A,(2))
(4) (**,(1),N)
(5) (/,E,(4))
(6) (+,(3),(5))

间接码表
(1)
(2)
(3)
(1)
(4)
(5)
(6)

四元式：

(1) (-,C,D,T1)
(2) (*,B,T1,T2)
(3) (+,A,T2,T3)
(4) (-,C,D,T4)
(5) (**,T4,N,T5)
(6) (/,E,T5,T6)
(7) (+,T3,T6,T7)

翻译

对作为转换条件的布尔式E，可以把它翻译成仅含下述三种形式的四元式序列：

• ( jnz, A, - , p): 若 A 为真（1，非0），则转向第 p 个四元式；
• (jθ, A1, A2, p): 若关系 A1 θ A2 为真，则转向四元式 p；
• (j, -, -, p ) : 无条件转向四元式 p。

写出语句If ﹁A ∨ B<C ∧ D<E then X:= Y+Z else X:=Y*Z 的四元式序列

100 (jnz,A,-,102) 
101 (j,-,-,106) //如果A为假，跳转106
102 (j<,B,C,104)
103 (j,-,-,109)
104 (j<,D,E,106)
105 (j,-,-,109)
106 (+,Y,Z,T1)
107 (:=,T1,-,X)
108 (j,-,-,0) //if的跳转语句
109 (*,Y,Z,T2)
110 (:=,T2,-,X)

---

写出四元式序列
if a>b then 
	if c>0 ∧ d>0 then  x:=1  else x:=2
else  x:=3 

答：
100 (j>,a,b,102) 
101 (j,-,-,110) 
102 (j>,C,0,104)
103 (j,-,-,108)
104 (j>,D,0,106)
105 (j,-,-,108)
106 (:=,1,-,X)
107 (j,-,-,0) //内if的跳转语句
108 (:=,2,-,X) 
109 (j,-,-,107) //外if的跳转语句
110 (:=,3,-,X)

---

将下列的IF语句翻译成四元式序列

if A and B and (C > D)
then
	if A < B then F := 1
	else F := 0
else G := G + 1

100 (jnz,A,-,102) 
101 (j,-,-,112) 
102 (jnz,B,-,104)
103 (j,-,-,112)
104 (j>,C,D,106)
105 (j,-,-,112)
106 (j<,A,B,108)
107 (j,-,-,110) 
108 (:=,1,-,F) 
109 (j,-,-,0) //内if的跳转语句
110 (:=,0,-,F)
111 (j,-,-,109) //外if的跳转语句
112 (+,G,1,T)
113 (:=,T,-,G)

---

将下列的FOR语句翻译成四元式序列

for i := a + b * 2 to c + d + 10 do
	if h > g then p := p + 1

100 (*,b,2,T1) 
101 (+,a,T1,T2) 
102 (+,c,d,T3)
103 (+,T3,10,T4)
104 (:=,T2,-,i) //i=a+b*2
105 (:=,T4,-,T) //T=c+d+10
106 (j,-,-,109)
107 (+,i,1,T5)
108 (:=,T5,-,i) 
109 (j<=,i,T,110) //判断i<=T
110 (j>=,h,g,112) //判断h>g
111 (j,-,-,109)  //if的跳转语句
112 (+,p,1,T6)
113 (:=,T6,-,p)
114 (j,-,-,107) //跳转到i++

期末考

自底向上优先分析

• 计算 FIRSTVT 和 LASTVT
• 构造算法优先关系表，判断是否为算符优先算法
• 给出算符优先分析过程
• 指出句型的短语、句柄、素短语和最左素短语

预计两题

LR分析

• LR(0)，LR(1)，SLR(1)，LALR(1) 分析表和分析过程（四选一，感觉 LALR(1) 不太会考，LR(0) 也不太会考）

一题

语义分析

• 后缀式、三元式、间接三元式、四元式
• 翻译成四元式序列

预计两题