终结符,并且除自身之外,不再包含其他的素短语.句型 最左边的素短语称为最左素短语.
5.判断题 X ①存在有左递归规则的文法是LL(1)的 √ ②任何LL(1)文法都是无二义性的 √ ③每一个SLR(1)文法也都是LR(1)文法 ④存在一种算法,能判定任何上下文无关文法是否是 √ LL(1)的 ⑤LR(1)括号中的1是指,在选用产生式Aα进行分 析,看当前读入符号是否是在FIRST(α) X ⑥设有一个LR(0)项目集I={Xα.Bβ,Aα.},该项目 X 集含有”移进-规约”冲突. ⑦设有一个LR(1)项目集I={[Xa.bβ,a][Aα.,a]}, 该项目集含有”移进-规约”冲突 X
9. 下面文法属于哪类LR文法?试构造其SLR分析表. S(SR | a R,SR | ) 解:(1)拓广文法 (2)构造识别活前缀的DFA
(3)分析表如下:
10. 设文法G为: SA ABA | ε BaB | b (1)证明它是LR(1)文法. (2)构造它的LR(1)分析表. (3)给出输入符号串abab的分析过程.
8. (课本P100)设文法G为: SA AB | AiB BC | B+C C)A* | ( (1)将文法改写成LL(1)文法 (2)计算每个非终结符的FIRST集和FOLLOW集 (3)构造它的预测分析表
●
LL(1)分析表的构造
构造分析表步骤：为每个非终结符 A 和产生式 A→α重复以下两 个步骤： 1) 对于 First(α) 中的每个记号a ，都将 A→α添加到 表项目 M[A,a]中. 2) 若ε在 First(α)中, 则对于 Follow(A) 中的每个元素a ( 记号或 $), 都将 A→α添加到 M[A,a]中.
第 练习题
1.在高级语言编译程序常用的语法分析方法中,递 归下降分析法属于____分析方法. B A.自左至右 B 自上而下 C自下而上 D自右向左
2.设有文法G[E]: ETE’ E’+TE’|ε TFT’ B T’*FT’| ε FIRST(T’)=____ C F(E)|id FOLLOW(F)=____ A.{(, id} B {*, ε} C{*,+,),$} D{+,),$}
③算符优先分析法 C,D: ①语法数 ③最左推导 E: ①右递归 ③直接右递归 ④预测递归分析法 ② 有向无环图 ④最右推导 ② 左递归 ④直接左递归
④ 7.自底向上语法分析采用 A 分析法,常用的是自底 向上语法分析有算符优先分析法和LR分析法.LR分 ④ 算符优先分析是寻找右句 析是寻找右句型的B ;而 ③ ③ 型的 C .LR分析法中分析能力最强的是 D ;分析能力 最若的是 E .② A: ①递归 ② 回溯 ③枚举 ④移进-规约 B,C: ①短语 ② 素短语 ③最左素短语 ④句柄 D,E: ①SLR(1) ② LR(0) ③LR(1) ④LALR(1)
11. (P101)设文法G为: SrD DD,i | i (1)构造识别文法活前缀的DFA. (2)该文法是LR(0)文法吗?请说明理由 (3)该文法是SLR(1)文法吗?若是,构造它的SLR(1)分 析表.
12. (课本P101)设文法G为: EE+T | E-T | T TT*F | T/F | F FF↑P | P P(E) | a 试给出句型T-T/F+a 和 T+T*F-F ↑a的短语、句柄、 素短语。 句型1:短语T-T/F+a, T-T/F, T, T/F, a 句型T 素短语: T/F, a 句型2:短语E+T*F-F ↑a, E+T*F, T*F, F ↑a, a 句型T*F 素短语: T*F , a
B 3.自下而上语法分析法的原理是___ A.”移进-推导法” B ”移进-规约法” C ”最左推导法” D ”推导-规约法” 4.设有文法G[E]: EE+T|T TT*F|F F(E)|a 句型T+T*F+a的素短语是___ AB A. a B T*F C.T D.T+T*F
◆所谓句型的素短语是指这样一种短语,它至少包含一个
6.从供选择的答案中,选出应填入__内的正确答案 在编译程序中,语法分析分为自顶向下分析和自底向 ④ 上分析两类. A 和LL(1)分析法属于自顶向下分析; ③B 和LR分析法属于自底向上分析.自顶向下分析 试图为输入符号串构造一个③ ;自底向上分析试图 C ④ 为输入符号串构造一个_D__. 采用自顶向下分析方 法时,要求文法中不含有 E② . A,B: ①深度分析法 ② 宽度优先分析法