编译原理分知识点习题(全).pdf

编译原理 1 / 45 词法分析与有穷自动机词法分析与有穷自动机 1. 将图 1 所示的有穷自动机转换成与其等价的正规文法，其中 4、5 为终止状态。 解答：本题考查有穷自动机到正规文法的转换方法。 这类题只需要书中所介绍的方法进行即可得到正规文法，本题有穷自动机对应的正规文法 GS为： AaB|bB|cC BaB|bD|aE|cC|b|a CbB|cC|cE|c DbD|b EaE|a 图 1 有穷自动机的状态转换图 2.给定如图 2 所示的有穷自动机，试用正规表达式给出它能接受的语言集合。 图 2 有穷自动机 解：本题考查正规表达式与有穷自动机的等价性。 对于一个在输入字母表上的 FAM，一定可以在字母表上构造一个正规表达式 e，使得 L(e)=L(M) . 根据状态转换图， 从开始状态出发， 可以有任意个 （包括 0 个） b 作为句子的开始部分； 从 0 状态出发， 0 1 2 3 a a a b b a b b 1 2 3 4 5 start a b b c b c a a c b 编译原理 2 / 45 每输入一个 a，不许输入两个 b 才能到达终止状态后，还可以通过输入 a 回到状态 1，或输入 b 回到状态 0， 然后进入递归过程，再输入相同的符号串，所以，该有穷自动机描述的语言为： (b*(aa*b)*b)* 3. 构造下述正规表达式的 DFA。 Xy*|yx*y|xyx 解： 本题考查由正规表达式构造有穷自动机的方法， 本题可按照由正规表达式构造等价的 NFA，NFA 确定化，DFA 最小化 3 步进行求解。 （1） 根据题中所给的正规表达式得到相应的 DFA 如图 3 所示。 图 3 正规表达式 Xy*|yx*y|xyx 的 DFA。 （2） 依据该 NFA 采用子集法构造确定 DFA 其过程如表 1（已换名）所示。 表 1 将 NFA 确定化为 DFA 的过程 I Ix Iy S 0 A, B, F, Z 1 C, D, E 2 A, B, F, Z 1 B, G, Z 3 C, D, E 2 D, E 4 Z 5 B, G, Z 3 Z 5 B, Z 6 D, E 4 D, E 4 Z 5 Z 5 B, Z 6 B, Z 6 以所有包含 NFA 的终止状态 Z 的 DFA 状态作为终止状态，得到 DFA 相应的状态转换图如 图 4 所示 S A B F G D E Z C x y x x x y y y 编译原理 3 / 45 图 4 DFA 的状态转换图 （3） 对 DFA 进行最小化，过程如下： 已知 K=0,1,2,3,4,5,6。首先将 K 分成两个子集 K1=0,2,3 （非终态集） K2=1,3,4,6 （终态集） 在状态集合 K1=0,2,3中，因为 0x=1K2 2,4x=4K1 所以状态 0 与状态 2，4 不等价，故 K1 可分割为 K11=0 K12=2,4 在状态集合 K12=2，4中，因为有 2，4x=4 2,4y=5K2 所以，状态 2 和状态 4 等价。 在状态集合 K2=1,3,4,6中，状态 5 无输入，状态 3 有 x、y 输入，状态 1 与状态 6 只有 y 输入，所以 可将 K2分割为 K21=1,6 K22=3 K23=5 在状态集合 K21=1，6中，状态 1 输入 y 到达状态 3，状态 6 输入 y 到达状态 6，所以状态 1 与 6 也不 等价。进一步将 K21分割为 K211=1 K212=6 于是，将原状态集合划分为：0、2，4、1、3、5、6。 选2，4中的 2 作为代表，原来由状态 4 导入（出）其余状态的弧改为有状态 2 导入（出） ；然后消去 状态 4。最后得到最小化后的状态转化图如图 5 所示。 0 2 4 5 5 6 1 3 x x x x y y y y y y 编译原理 4 / 45 图 5 正规表达式 Xy*|yx*y|xyx 的最小化 DFA 4. 构造正规表达式（011）*00 相应的 DFA。 解：本题考查由正规表达式构造确定的有穷自动机的方法。 （1） 构造正规表达式（011）*00 的 DFA。 按照图 3.2 所示的转换规则构造正规表达式（011）*00 对应的 NFA 如图 6 所示。 图 6 正规表达式（011）*00 的 DFA （2） 由正规表达式（011）*00 的 NFA 构造确定的有穷自动机 DFA。 以 NFA 的开始状态 S 的闭包-CLOSURE（S）作为 DFA 的开始状态，采用子集法将图 3.43 中所式 的 NFA 确定化，其过程如表 2 所示。 表 2 将 NFA 确定化为 DFA 的过程 I Ix Iy S，A, B 0 A, B, C 1 A, B 2 A, B, C 1 A, B, C, Z 3 A, B 2 A, B 2 A, B, C 1 A, B 2 A, B, C, Z 3 A, B, C, Z 3 A, B 2 以所有包含 NFA 的终止状态 Z 的 DFA 状态作为终止状态，得到 DFA 相应的状态转换图（以换名）如图 7 所 示。 S B C Z A 0 1 0 0 0 2 5 5 6 1 3 x y y y y y x x 编译原理 5 / 45 图 7 正规表达式（0|1）*00 的 DFA （3） 对该 DFA 进行最小化。 采用够造状态集划分的方法对 DFA 进行最小化，过程如下： 以知 K=0，1，2，3。首先将 K 分成两个子集 K1=0,1,2 （非终态集） K2=3 （终态集） 在 K1=0,1,2中，有 00=1K1 10=3K2 20=1K1 01=2K1 11=2K1 21=2K1 自上而下语法分析自上而下语法分析 1已知文法 GS： SSaA|A AAbB|B BcSd|e 请证实 AacAbcBaAdbed 是文法的一个句型，并写出该句型的所有短语、素短语以及句柄。 解：本题考查“句型” 、 “短语” 、 “句柄” 、 “素短语”等概念。 符号栈 S 关系 输入串 最左素短语 S1 S2 S3 S4 S5 S6 S7 R1 R2 R3 R4 R5 R6 ( a d b ) # #( a d b ) # #( d b ) # d #( V d b ) # #( Vd b ) # #( Vd ) # b 0 1 2 3 0 1 1 0 0 0 1 1 编译原理 6 / 45 #( V ) # VdV #( V = ) # # # (V) # 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已知文法 GS： S*A A0A1|* （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 的语法树 编译原理 7 / 45 （2） 构造文法 G 的优先关系矩阵。 根据（1）中的 FIRSTVT 集和 LASTVT 集及算符优先关系构造算法 对 S*A，按算法第 3 种情形有： （*0） ， （*） 对 A0A1，按算法第 1 种情形有： （0|1） 按算法第 3 种情形有： （0|1), 根据上述算符优先关系得到算符优先关系矩阵如表 6.1 所示。表中空白元素表示相应终结符号对之间 没有算符优先关系，即它们不会在任何句型中相继出现。 表 6.1 文法的算符优先关系矩阵 0 1 * 0 | |= | * | | (3)对句子“*0*1#”分析过程如表 6.2 所示。 表 6.2 分析输入符号串“*0*1#”的过程 符 号 栈 S 关 系 输 入 串 最左素短语 S1 S2 S3 S4 S5 S6 S7 R1 R2 R3 R4 R5 # * 0 * 1 # # * 0 * 1 # # * 0 * 1 # # * 0 1 # * # * 0 V = # # S4 (2) S1 S2 S3 S4 S1 S2 S3 S4 解：本题考查优先函数的构造方法。 （1） 采用迭代法求优先函数，过程如下。 （2） 初始状态： S1 S2 S3 S4 f 1 1 1 1 g 1 1 1 1 第 1 次迭代： 编译原理 8 / 45 S1 S2 S3 S4 f 1 1 2 2 g 1 1 1 1 第 2 次迭代： S1 S2 S3 S4 f 1 1 2 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 S4 f 7 6 2 5 g 5 2 5 1 4.试为文法 GZ： ZA( ) A(|Ai|B) Bi 构造算符优先关系和优先函数。 解：本题考查算符优先关系的构造方法和优先函数的构造方法。 （1） 构造算符优先关系。 首先构造 FIRSTVT 集和 LASTVT 集，根据定义有： FIRSTVT（Z） （， i， ） FIRSTVT（A） （， i， ） FIRSTVT（B）i 和 LASTVT（Z） LASTVT（A） （， ） ， i LASTVT（B）i 按照构造算符优先关系的算法得到如下算符优先关系： “”的构造 有产生式 ZA（） 按算法第 1 种情形有： （ （） ） “（） ， （）（） ， （i（） 有产生式 AAi 按算法第 4 种情形有： （ （i）, ( )i） ， （ii） 有产生式 AB) 按算法第 4 种情形有： (i) ) 综合上述算符优先关系得到该文法的算符优先关系矩阵如表 6.4 所示。 （ ） i （ = 编译原理 9 / 45 ） I (2)构造优先函数。 采用迭代法（先考虑所有的大于关系，再考虑所有的等于关系） 。 初始状态： （ ） i f 1 1 1 g 1 1 1 第 1 次迭代： （ ） i f 2 2 2 g 1 2 1 第 2 次迭代： （ ） i f 2 2 3 g 1 2 1 第 3 次迭代： （ ） i f 2 2 3 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 文法的优先函数 （ ） i F 4 3 5 G 1 4 1 5.给出文法 G2： SSaS|SbS|cSd|eS|f （1）请证实这是一个二义文法； （2）给出什么样的约束条件，可构造出无冲突的 LR 分析表？请证实你的论点。 解：本题考查“二义文法”及二义文法的 LR 分析法。 （1）该文法是二义文法，因为它存在句子： fafbf 该句子有两棵不同的语法树，如图 6.3 中的（a） ， （b）所示。 编译原理 10 / 45 （2）构造文法的无冲突的 LR 分析表。 首先对文法进行拓广得到 SS 0 SSaS 1 SSbS 2 ScSd 3 SeS 4 Sf 5 在此基础上构造文法的识别活前缀的有穷自动机(省略)。 因为：FOLLOW(S)=#，a，b，d 构造文法的 SLR(1)分析表如表 6.6 所示。 表表 6.6 文法的文法的 SLR(1)分析表分析表 状态状态 ACTION GOTO a b c d e f # S 0 S2 S3 S4 1 1 S5 S6 acc 2 S2 S3 S4 9 3 S2 S3 S4 10 4 r5 r5 r5 r5 7 5 S2 S3 S4 7 6 S2 S3 S4 8 7 r1/S5 r1/S6 r1 r1 8 r2/S5 r2/S6 r2 r2 9 S5 S6 S11 10 r4/S5 r4/S6 r4 r4 11 r3 r3 r3 r3 6.已知文法： GA：AAA|(A)| （1）该文法是 LR(0)文法吗？为什么？ （2）请构造该文法的以 LR(0)项目集为状态的识别活前缀的 DFA。 （3）规定：出现“移进-归约”冲突时，移进优先；出现“归约-归约”冲突时，优先采用文法中出现在前 的产生式进行归约。构造该文法的 LR 分析表。 解：本题考查对二义性文法进行 LR 分析的方法。 先构造出识别活前缀的有穷自动机，然后根据其中出现的冲突情况确定无二义规则的使用。 S S b S f S a S f f S S a S f S b S f f 图图 6.3 句子句子 fafbf 的两棵语法树的两棵语法树 编译原理 11 / 45 首先构造拓广文法如下： 0 A A 1 AAA 2 A(A) 3 A （1）该文法不是 LR(0)文法。因为文法存在有相同左部的产生式 AAA 和 A 产生式 A在任何时候都只产生归约项目。当由项目 A .A 派生出新项目时，同时得到 A.(A) 和 A. 将出现“移进归约”冲突。所以该文法不是 LR(0)文法。 （2）构造该文法的以 LR(0)项目集为状态的识别活前缀的 DFA 如图 6.4 所示。 （3）因为出现“移进规约”冲突时，移进优先；出现“规约规约”冲突时，优先采用文法中出现在前 的产生式进行规约，所以得到该文法的 LR 分析表如表 6.7 所示。 图图 6.4 文法的以 LR(0)项目集为状态的识别活前缀的 DFA 表表 6.7 文法的文法的 LR 分析表分析表 状态 ACTION GOTO ( ) # A 0 S2 r3 r3 1 1 S2 r3 acc 2 2 S2 r3 r3 3 3 S2 r1 r1 4 4 S2 S5 r3 5 5 r2 r2 r2 7“算符优先分析采用“移进归约”技术，其规约过程是规范的。 ”这种说法是否正确？ 解：本题考查算符优先分析法中句型的规约过程。 A ( I0 A A AAA A(A) A I1 A A AAA AAA A （A） A I2 A(A) AAA A （A） A I3 AA A AAA AAA A （A） A I4 I5 A(A) ( A ( ( ) A( A) AAA AAA A （A） A A A ( A 编译原理 12 / 45 在算符优先分析法中，每步自下而上分析、识别和归约的是当前句型的最左素短语，而不是严格地从 左到右归约句柄。 算符优先分析法只对算符优先文法进行，利用的是算符优先关系矩阵，该矩阵中只有终结符号间的优 先关系，在归约过程中，利用算符优先关系矩阵无法找到句型中相应于产生式的句柄。因此，在算符优先 分析法中，每次归约时，归约的是当前句型的最左素短语所以产生式对归约没有起作用，因而算符优 先分析不是规范规约。 例如文法 GE： EE+TT TT*FF FPFP P（E）i 对句子 i+i 的归约过程如图 6.5 所示。从图 6.5 可见，算符优先分析中的归约不是规范规约。 E E E + T P + P T F i i F i i 规范归约识别 i+i 的过程 算符优先分析识别 i+i 的过程 图 65 算符优先分析的归约 8、证明 GA是 LR(1)文法。 GA:ABA BAbb 解:本题考查“LR(1)文法” ，涉及构造以 LR（1）项目集为状态的识别活前缀的有穷自动机的方法。 首先构造文法的托广文法，得到 GS：SA 0 ABA 1 A 2 BaB 3 bb 4 根据该托拓广文法构造以 LR1项目集为状态的识别活动前缀的有穷自动机如图 6.6 所示。 从图 6.6 中可知，所有的状态都不含有 “移进归约” 、 “归约归约”冲突，因而该文法是 LR(1)文法。 编译原理 13 / 45 图 6.6 有穷自动机 自上而下语法分析自上而下语法分析 1.设有文法 GS： SAB AbB|Aa BSb|a 试消除该文法的左递归。 解：本题考查消除左递归的方法。 应用消除文法左递归的算法对文法 GS消除左递归的过程如下： （1） 将非终结符排序为：U1=S，U2=A，U3=B （2） 进入算法排序： i=1 时，对文法无影响 i=2，j=1 时：AAa 有直接左递归，消去该直接左递归，得 AbBA AaA| i=3，j=1 时：改写文法，有 BABb|a j=2 时：改写文法，有 BbBABb|a 无左递归。 B A a b b BaB ，a/b/# I2 I1 I5 ABA ，# ABA，# ABA，# A ，# BaB，a/b/# Bb，a/b/# I4 Bb ，a/b/# I3 BaB，a/b/# BaB，a/b/# Bb，a/b/# I6 I0 SA，# ABA，# A ，# BaB，a/b/# Bb，a/b/# A B a b B a SA ，# 编译原理 14 / 45 （3） 所以文法 GS消除左递归后变为： GS：SAB AbBA AaA| BbBABb|a 2.设有文法 GE: EAa|Bb AcA|eB Bbd 试按照递归子程序法为该文法构造语法分析程序。 解：本题考查递归子程序的构造方法。 首先判断文法是否满足递归子程序法对文法的要求，然后再构造递归子程序。 因为： （1） 该文法无左递归。 （2） 文法的产生式 EAa|Bb 和 AcA|eB 的右部有若干选项， 判断这两条产生式右部各 候选式的终结首符号集合是否两两互不相交。 对产生式 EAa|Bb，有 FIRST(Aa)FIRST(Bb)=c，eb= 对产生式 AcA|eB，有 FIRST(cA)FIRST(eB)=ce= 文法中其他产生式都只有一个非空的右部。 综合（1） 、 （2） ，该文法可以采用自上而下分析方法进行语法分析而不会出现回朔和无限 循环。 下面为该文法的每一个非终结符号构造递归子程序。 假设用 READAWORD 代表读下一个单词。用 P(E)、P(A)、P(B)分别表示非终结符号 E、 A、B 对应的子程序名。约定输入符号串以“#”作为输入结束符。 P(E)的递归子程序为： PROCEDURE P(E); BEGIN IF WORD IN FIRST(Aa) THEN BEGIN P(A); READAWORD; IF WORD=a THEN READAWORD ELSE ERROR END ELSE IF WORD IN FIRST(Bb) THEN BEGIN P(B); READAWORD; IF WORD=b THEN READAWORD ELSE ERROR 编译原理 15 / 45 END ELSE ERROR END; P(A)的递归子程序为： PROCEDURE P(A); BEGIN IF WORDD=c THEN BEGIN READAWORD; P(A) END ELSE IF WORD=e THEN BEGIN READWORD; P(B) END ELSE ERROR END; P(B)的递归子程序为： PROCEDURE P(B); BEGIN IF WORD=b THEN BEGIN READAWORD; IF WORD=d THEN READAWORD ELSE ERROR END ELSE ERROR END; 主程序中的主要内容为： READAWORD; P(E); IF WORD=”#” THEN WRITE(“RIGHT!”) ELSE WRITE(“ERROR!”) 3.已知文法 GE： GE：EE+T|T TT*F|F Fi|(E) 请按递归子程序法为其构造语法分析程序。 解：本题考查递归子程序的构造方法。 本题所给文法存在左递归， 不满足递归子程序法对文法的要求， 必须首先消除文法左递归， 然后再构造分析程序。 因为文法只有左递归，采用扩充的 BNF 范式消除文法左递归得到： 编译原理 16 / 45 GE：ET+T TF*F Fi|(E) 然后再应用书中介绍的方法即可求解。 假定用“ADVANCE;”表示对读取下一个单词的过程的调用。 相应的递归子程序为： PROCEDURE P(E); BEGIN P(T); WHILE SYM=+ DO BEGIN ADVANCE; P(T) END END; PROCEDURE P(T); BEGIN P(F); WHILE SYM=* DO BEGIN ADVANCE; P(F) END END; PROCEDURE P(F); BEGIN IF SYM=i THEN ADVANCE ELSE IF SYM=( THEN BEGIN ADVANCE; P(E); IF SYM=) THEN ADVANCE ELSE ERROR END ELSE ERROR END; 主程序中的主要内容为： ADVANCE; P(E); IF WORD=”#” THEN WRITE(“RIGHT!”) ELSE WRITE(“ERROR!”) 4文法 GM是否是 LL(1)文法，说明理由。 GM：MTB TBa| BDb|eT| Dd| 编译原理 17 / 45 解：本题考查 LL(1)方法对文法的要求，涉及到 FIRST 集、FOLLOW 集的求法。 首先求出文法的每一个非终结符号的 FIRST 集、FOLLOW 集： FIRST(D)=FIRST(d)FIRST()=d, FIRST(B)=FIRST(Db)FIRST(eT)FIRST() =FIRST(db)FIRST(b)FIRST(eT)FIRST() =d，b，e， FIRST(T)=FIRST(Ba)FIRST()=d，b，e，a， FIRST(M)=FIRST(Tb)= d，b，e，a， FOLLOW(M)=# FOLLOW(B)=FOLLOW(M)FIRST(a)=a，# FOLLOW(T)=FOLLOW(B)FOLLOW(M) FOLLOW(B)=d，b，e，#，a FOLLOW(D)=FIRST(b)=b 可以看出，对文法 GM的产生式 TBa|，有 FIRST(Ba)FOLLOW(T)=d，b，e，ad，b，e，#，a=d，b，e，a 仅此一条就会导致在自上而下的语法分析过程中出现回朔。 所以文法 GM不是 LL(1)文法。 5构造一个 LL(1)文法 G，识别语言 L： L=|为0，1上不包括两个相邻的 1 的非空串 并证明你的结论。 解：本题考查文法的构造方法以及 LL(1)文法的要求。 首先构造出描述该语言的文法，然后证明该文法是 LL(1)文法。 （1） 根据题目要求句子为不包括两个相邻的 1 的非空串，首先得到一个能够描述所 有句子的文法 GS：S0S|1A|0|1 A0S|0 再根据 LL(1)文法的要求，将文法改写为 GS：S0B|1C A0B BS| CA| （2） 下面证明文法 GS是 LL(1)文法。 对产生式 S0B|1C，没有空产生式右部()，所以只要考查终结首符号集是否两两 互不相交。有 FIRST(0B)FIRST(1C)=01= 对产生式 A0B，只有唯一的不为空的右部，不用考查。 对产生式 BS|，因为有空产生式右部，所以要考查终结首符号集与后继终结符 号集是否相交。由于 FIRST(S)=0，1 FIRST()= FOLLOW(B)= FOLLOW(S) FOLLOW(A)= FOLLOW(S) FOLLOW(C) =FOLLOW(S)=#FOLLOW(B)=# 所以有 FIRST(S)FIRST()= 和 FIRST(B)FOLLOW(B)= 对产生式 CA|，因为有空产生式右部，所以要考查终结首符号集与后继终结符 号集是否相交。由于 编译原理 18 / 45 FIRST(A)=0 FIRST()= FOLLOW(C) =FOLLOW(S) =# 所以有 FIRST(A)FIRST()= 和 FIRST(C)FOLLOW(C)= 综上所述，文法 GS的每一条形如 UX1|X2|Xn的产生式都满足 FIRST(Xi)FIRST(Xj)= (ij) 如果 Xj时，还满足 FIRST(X1)FOLLOW(U)= 所以，文法 GS是 LL(1)文法。 6有文法 GS： SaABbcd| AASd| BSAh|eC| CSf|Cg| DaBD| 求每一个非终结符号的 FOLLOW 集合。 对每一个非终结符号的产生式选择，构造 FIRST 集合。 该文法是 LL(1)文法吗？ 解：本题考查 LL(1)文法的要求，涉及文法符号串 FIRST 集，文法非终结符号的 FOLLOW 集的求法。 首先将文法压缩，得到 SaABbcd| AASd| BSAh|eC| CSf|Cg| 求每一个非终结符号的 FOLLOW 集合： S 为开始符号，且有产生式 AASd BSAh CSf FOLLOW(S)=#FIRST(d)FIRST(Ah)FIRST(f)=#，d，a，h，f SaABbcd AASd BSAh FOLLOW(A)=FIRST(Bbcd)FIRST(Sd)FIRST(h)=b，a，d，h，e SaABbcd FOLLOW(B)=FIRST(bcd)=b BeC CCg FOLLOW(C)=FOLLOW(B)FIRST(g)=b，g 对每一个非终结符号的产生式右部选项，构造 FIRST 集合 对 S：FIRST(aABbcd)=a FIRST()= 对 A：FIRST(ASd)=a，d FIRST()= 对 B：FIRST(SAh)=a，d，h FIRST(eC)=e FIRST()= 对 C：FIRST(Sf)=a，f FIRST(Cg)=a，f，g FIRST()= 由于存在产生式 CSf|Cg| FIRST(Sf)FIRST(Cg)=a，fa，f，g 所以该文法不是 LL(1)文法。 7已知文法 编译原理 19 / 45 GA：AaAa| （1）该文法是 LL(1)文法吗？为什么？ （2）若采用 LL(1)方法进行语法分析，如何得到该文法的 LL(1)分析表？ （3）若输入符号串“aaaa” ，请给出语法分析过程。 （4）请给出该文法的递归下降分析子程序。 解： （1）因为产生式 AaAa|有空产生式右部，而 FOLLOW(A)=#FIRST(a)=a，# 造成 FIRST(A)FOLLOW(A)=a，a，# 所以该文法不是 LL(1)文法。 （2）若采用 LL(1)方法进行语法分析，必须修改该文法。 因该文法产生偶数（可以为 0）个 a，所以得到文法 GA：AaaA| 此时对产生式 AaaA|，有 FOLLOW(A)=#FOLLOW(A)=#，因而 FIRST(A)FOLLOW(A)=a，#= 所以文法 GA是 LL(1)文法，按 LL(1)分析表构造算法构造该文法的 LL(1)分析表如表 5.1 所示。 表表 5.1 5.1 文法文法 G GAA的的 LL(1)LL(1)分析表分析表 A # A AaaA A （3）若采用 LL(1)方法进行语法分析，对符号串“aaaa”的分析过程如表 5.2 所示 表表 5.2 对符号串“对符号串“aaaaaaaa”的分析过程”的分析过程 步 骤 分析栈 输入串 产生式/动作 1 #A aaaa# AaaA 2 #Aaa aaaa# 匹配 3 #Aa aaa# 匹配 4 #A aa# AaaA 5 #Aaa aa# 匹配 6 #Aa a# 匹配 7 #A # A 8 # # 接受 （4）构造文法 GA的递归子程序如下（假定用“ADVANCE； ”表示对读取下一个单词 的过 程的调用） ： PROCEDURE P(A); BEGIN IF WORD=a THEN BEGIN ADVANCE; IF WORD=a THEN BEGIN READAWORD; P(A); END ELSE ERROR 编译原理 20 / 45 END ELSE IF NOT(WORD IN FOLLOW(A) THEN ERROR END; 主程序中的主要内容为： ADVANCE; P(A); IF WORD=”#” THEN WRITE(“RIGHT!”) ELSE WRITE(“ERROR!”) 8.设文法 GS： SSbA|aA BSb ABc 将该文法改写成 LL(1)文法。 求文法的每一个非终结符号的 FIRST 集合和 FOLLOW 集合。 构造相应的 LL(1)分析表。 解：本题考查“LL(1)文法”的概念及 LL(1)分析表的构造方法，涉及文法符号串的 FIRST 集，文法非终结符号的 FOLLOW 集的求法。 将该文法改写成 LL(1)文法。 因为 SSbA|aA 有左递归，将其改写为 SaAbA 文法变为 GS：SaAbA BSb ABc 文法 GS满足 LL(1)文法的条件 文法 GS中每一个非终结符号的 FIRST 集合为 FIRST(S)=a FIRST(A)=a FIRST(B)=a 文法 GS中每一个非终结符号的 FOLLOW 集合为 S 为开始符号，且有产生式 BSb FOLLOW(S)=#FIRST(b)=#，b SaAbA FOLLOW(A)=FIRST(bA)FOLLOWS=#，b ABc FOLLOW(B)=FIRSTc=c 构造相应的 LL(1)分析表 FIRST(aAbA)=a MS，a=SaAbA FIRST(A)=a MA，a=BBc FIRST(B)=a MB，a=BSb 文法 GS的分析表如表 5.3 所示。 表表 5.3 文法文法 GS的分析表的分析表 a b c # S SaAbA 编译原理 21 / 45 A ABc B BSb 9.考虑文法 G： AAB|B BBC|C CD|D D(A)|i 试问该文法是否是 LL(1)文法，为什么？ 写出与该文法等价的 LL(1)文法 G1。 构造 G1 的 LL(1)分析表。 解：本题考查 LL(1)文法的要求，以及 LL(1)分析表构造方法，涉及文法符号串的 FIRST 集 合的求法，文法非终结符号的 FOLLOW 集合求法。 该文法不是 LL(1)文法。 因为对产生式 AAB|B，有 FIRST(AB)FIRST(B)=FIRST(B) 不满足 LL(1)文法的条件。 构造与该文法等价的 LL(1)文法 G1。 这一问题实际上是要使该文法满足 LL(1)文法的要求。 文法含有左递归，将导致无限循环。将文法消除左递归，得 G1 ABA A BA| BCB B CB| CD|D D(A)|i 对产生式 A BA|，有 FIRST(BA)FOLLOW(A)=#，)= 对产生式 B CB|，有 FIRST(CB)FOLLOW(B)=#，)，= 对产生式 CD|D，有 FIRST(D)FIRST(D)=(，i= 对产生式 D(A)|i，有 FIRST(A)FIRST(i)=(i= 文法中其他产生式都只有一个非空()的右部，所以文法 G1 已满足 LL(1)文法的要求。 因为 对产生式 ABA有 FIRST(BA)=，(，i 对产生式 BCB有 FIRST(CB)=，(，i 对产生式 A BA|有 FIRST(BA)= 和 FOLLOW(A)=#，) 对产生式 B CB|有 FIRST(CB)= 和 FOLLOW(B)=，#，) 对产生式 CD|D 有 FIRST(D)= 和 FIRST(D)=(，i 对产生式 D(A)|i 有 FIRST(A)=() 和 FIRST(i)=i 所以文法 G1 的 LL(1)分析表如表 5.4 所示。 编译原理 22 / 45 表表 5.4 文法文法 G1 的的 LL(1)分析表分析表 （ ） i # A BA BA BA A BA B CB CB CB B CB C D D D D (A) i 10.已知文法 GA为： AaABe|a BBb|d (1)试给出与 GA等价的 LL(1)文法 GA。 (2)构造 GA的预测分析表并给出输入串 aade#的分析过程。 解：本题考查“LL(1)文法”的条件，LL(1)分析表的构造方法和 LL(1)语法分析过程等内容。 预测分析表就是 LL(1)分析表。 (1)文法 GA不是 LL(1)文法，原因在于： 存在产生式 AaABe|a，使得 FIRST(aABe)FIRST(a)=a 将造成语法分析过程中出现回朔。 存在含有左递归的产生式 BBb|d，使得语法分析过程中会出现无限循环。 要构造与GA等价的LL(1)文法， 实质上就是要修改原文法中存在上述两种问题的产生式。 对产生式 AaABe|a 修改为 AaC CABe| 对产生式 BBb|d 修改为 BdB BbB| 因此得到文法 GA： AaC CABe| BdB BbB| 求出每一个非终结符号的 FIRST 集和 FOLLOW 集： FIRST(A)=a FOLLOW(A)=FIRST(Be)#=#，d FIRST(B)=d FOLLOW(B)=FIRST(e)=e FIRST(B)=b， FOLLOW(B)=FOLLOW(B)=e FIRST(C)=a， FOLLOW(C)=FOLLOW(A)=#，d 可以看出，对产生式 BbB|有 FIRST(bB)FOLLOW(B)=be= 对产生式 CABe|有 FIRST(ABe)FOLLOW(C)=a#，d= 而文法的其他产生式都只有一个非空的产生式右部， 在自上而下的语法分析过程中不会出现 回朔。 编译原理 23 / 45 所以文法 GA就是所求的与原文法等价的 LL(1)文法。 (2)构造 GA的预测分析表。 分析表 M 的构造算法为： 对 FIRST(x)中的每一终结符号 a，置 MU，a=“Ux” ； 如果FIRST(x)，则对于属于 FOLLOW(U)的每一个终结符号 b 或#，分别置 MU， b=“Ux”和 MU，#=“Ux” ； 将 M 中所有不能按规则与构造的元素置出错标志 ERROR(用空格表示)。 在应用算法的第二条时要注意， “对于属于 FOLLOW(U)的每一个终结符号 b 或#”是指