编译原理分知识点习题 自下而上语法分析

1．★已知文法G[S]： S→SaA|A A→AbB|B B→cSd|e

请证实AacAbcBaAdbed是文法的一个句型，并写出该句型的所有短语、素短语以及句柄。 解：本题考查“句型”、“短语”、“句柄”、“素短语”等概念。 符号栈S 关系 输入串 最左素短语 S1 S2 S3 S4 S5 S6 S7 ＃ #<( #<(< a #<( V #<( V < < > > = > R1 R2 R3 R4 R5 R6 ( a d b ) # a d b ) # d b ) # d b ) # b ) # ) # ) # ) # # (V) b VdV d # V # 接受 因为存在从文法开始符号S到符号串AacAbcBaAdbed的推导过程（如图6.1中的语法树所示），所以符号串AacAbcBaAdbed是文法的句型。

从图6.1中句型A1a1c1 A2b1c2Ba2 A3d1b2ed2的语法树可知，该句型的短语有：A1、B、 Ba2 A3、c2Ba2 A3d1、A2b1c2Ba2 A3d1、e、A2b1c2Ba2 A3d1b2e、c1 A2b1c2Ba2 A3d1b2ed2、 A1a1c1 A2b1c2Ba2 A3d1b2ed2

该句型的素短语有：Ba2 A3、e 该句型的句柄为：B 2．★已知文法G[S]： S→*A A→0A1|*

（1） 求文法G的各非终结符号的FIRSTVT集和LASTVT集;

（2） 构造文法G的优先关系矩阵，并判断该文法是否是算符优先文法； （3） 分析句子*0*1，并写出分析过程。 解：本题考查算符优先分析法中的有关知识：非终结符号的FIRSTVT集和LASTVT集的求法、算符优先关系的构造、算符优先文法的定义、算符优先分析过程等。 （1） 求文法G的各非终结符号的FIRSTVT集和LASTVT集。 根据非终结符号的FIRSTVT集定义得到 FIRSTVT（S）＝｛*｝ FIRSTVT（S）＝｛0，*｝ 根据非终结符号的LASTVT集定义得到 LASTVT（S）＝｛*，1｝ LASTVT（S）＝｛1，*｝

S S a1 A

A1 B

c1 S d2

A

A b2 B A2 b1 B e c2 S d1

S a2 A3

A B 图6.1句型AacAbcBaAdbed的语法树

（2） 构造文法G的优先关系矩阵。

根据（1）中的FIRSTVT集和LASTVT集及算符优先关系构造算法 对S→*A，按算法第3种情形有：（*<0），（*<*） 对A→0A1，按算法第1种情形有：（0|＝1）

按算法第3种情形有：（0|<0）,(0|<*) 按算法第4种情形有：（1|>1），(*|>1),

根据上述算符优先关系得到算符优先关系矩阵如表6.1所示。表中空白元素表示相应终结符号对之间没有算符优先关系，即它们不会在任何句型中相继出现。

表6.1 文法的算符优先关系矩阵 0 1 * 0 1 |< |= |> |< |< * |< |> (3)对句子“*0*1#”分析过程如表6.2所示。 表6.2 分析输入符号串“*0*1#”的过程 符 号 栈S 输 入 串 关 系 S1 S2 S3 S4 S5 S6 S7 R1 R2 R3 R4 R5 # #< * #< *< 0 #< *< 0< * #< *< 0 V #< *< 0 V= 1 #<* V < < < > = > > * 0 * 1 # 0 * 1 # * 1 # 1 # # # # # 最左素短语 * 0V1 *V 接受 # V 3．试为下列优先矩阵构造优先函数。 （1）

S1 S2 S1 S2 S3 S4 S3 ± > > S4 ± > > (2)

S1 S2 S3 S1 < S2 ± S3 > > < ± S4 > S4 ± 解：本题考查优先函数的构造方法。 （1） 采用迭代法求优先函数，过程如下。 （2） 初始状态： S1 S2 f g 第1次迭代：

f g 第2次迭代：

f S1 1 S2 1 S1 1 1 S2 1 1 1 1 1 1 S3 1 1 S3 2 1 S3 2 S4 1 1 S4 2 1 S4 2 g 1 1 1 1 第2次迭代没有变化，所以第2次迭代结果便是优先函数。 （3） 采用Bell有向图法构造优先函数(省略)。 因为

fs1可以到达的结点：gs3，gs4，fs4，gs3，gs2 fs2可以到达的结点：gs3，fs3，gs2，fs4，gs1 fs3可以到达的结点：gs2，fs3

fs4可以到达的结点：gs1，gs3，fs3，gs2，fs4 gs1可以到达的结点：fs3，fs4，gs2，gs1，gs3 gs2可以到达的结点：fs3，gs2

gs3可以到达的结点：fs4，fs3，gs1，gs3，gs2 gs4可以到达的结点：无

于是得到优先函数如表6.3所示。 S1 S2 S3 f 7 6 2 g 5 2 5 4.试为文法G[Z]： Z→A( ) A→(|Ai|B) B→i

构造算符优先关系和优先函数。

解：本题考查算符优先关系的构造方法和优先函数的构造方法。 （1） 构造算符优先关系。

首先构造FIRSTVT集和LASTVT集，根据定义有：

FIRSTVT（Z）＝｛（， i， ）｝ FIRSTVT（A）＝｛（， i， ）｝ FIRSTVT（B）＝｛i｝

S4 5 1 和 LASTVT（Z）＝｛｝｝

LASTVT（A）＝｛（， ）， i｝ LASTVT（B）＝｛i｝

按照构造算符优先关系的算法得到如下算符优先关系： “＝”的构造

∵有产生式Z→A（） ∴按算法第1种情形有： （ （＝） ） “<”的构造

文法没有满足“<”的相邻符号 “>”的构造

∵有产生式Z→A（） ∴按算法第4种情形有： （ (>（） ，（）>（），（i>（） ∵有产生式A→Ai ∴按算法第4种情形有： （ （>i）, ( )>i） ，（i>i） ∵有产生式A→B) ∴按算法第4种情形有： (i>) )

综合上述算符优先关系得到该文法的算符优先关系矩阵如表6.4所示。 i （ ） （ ） > > = > > > I > > (2)构造优先函数。 ① 采用迭代法（先考虑所有的大于关系，再考虑所有的等于关系）。 初始状态：

i （ ） f g 第1次迭代：

f g 第2次迭代：

f g 第3次迭代：

f （ 2 ） 2 i 3 （ 2 1 ） 2 2 i 3 1 （ 2 1 ） 2 2 i 2 1 1 1 1 1 1 1 g 1 2 1 第3次迭代没有变化，所以第3次迭代的的结果便是优先函数。 ② 采用Bell有向图法构造优先函数，其过程如图6.2所示。

图6.2构造优先函数

因为

f（可以到达的节点：g（，g），gi，f（ f）可以到达的节点：g（，gi fi 可以到达的节点：g（，g），gi，f（ g（可以到达的节点：无 g）可以到达的节点：g（，g），gi，f（ gi 可以到达的节点：无

于是得到优先函数如表6.5所示。

表6.5 文法的优先函数 （ F G 4 1 ） 3 4 i 5 1 5.给出文法G2： S→SaS|SbS|cSd|eS|f

（1）请证实这是一个二义文法；

（2）给出什么样的约束条件，可构造出无冲突的LR分析表？请证实你的论点。 解：本题考查“二义文法”及二义文法的LR分析法。 （1）该文法是二义文法，因为它存在句子： fafbf

该句子有两棵不同的语法树，如图6.3中的（a），（b）所示。 S S S b f S f S f S a b S f S f S f a S 图6.3 句子fafbf的两棵语法树

（2）构造文法的无冲突的LR分析表。 首先对文法进行拓广得到 S’→S 0 S→SaS 1 S→SbS 2 S→cSd 3 S→eS 4 S→f 5

在此基础上构造文法的识别活前缀的有穷自动机(省略)。 因为：FOLLOW(S)={#，a，b，d}

构造文法的SLR(1)分析表如表6.6所示。 表6.6 文法的SLR(1)分析表 状态 0 1 2 3 4 5 6 7 ACTION a S5 r5 r1/S5 b S6 r5 r1/S6 c S2 S2 S2 S2 S2 d r5 r1 e S3 S3 S3 S3 S3 f S4 S4 S4 S4 S4 # GOTO S 1 9 10 7 7 8 acc r5 r1

本文来源：https://www.bwwdw.com/article/yyc2.html