19.
三.单项选择题
1. LR语法分析栈中存放的状态是识别________的DFA状态。 a. 前缀；b. 可归前缀；c. 项目；d. 句柄；
2. 算符优先分析法每次都是对________进行归约： (a)句柄 （b）最左素短语 (c)素短语 (d)简单短语
3. 有文法G＝（｛S｝，｛a｝，｛S→SaS，S→ε｝，S），该文法是________。 a. LL(1)文法；b.二义性文法；c.算符优先文法；d.SLR(1)文法；
4. 在编译程序中，语法分析分为自顶向下分析和自底向上分析两类，_____ 和LL(1)分析法 属于自顶向下分析； a. 深度分析法 b. 宽度优先分析法 c. 算符优先分析法 d. 递归下降子程序分析法
5. 自底向上语法分析采用____ 分析法，常用的是自底向上语法分析有算符优先分析法和LR 分析法。 a. 递归 b. 回溯 c. 枚举 d. 移进－归约
6. 一个LR(k)文法，无论k取多大，____。 a. 都是无二义性的；b. 都是二义性的；c. 一部分是二义性的；d. 无法判定二义性；
7. 在编译程序中，语法分析分为自顶向下分析和自底向上分析两类，____和LR分析法属于 自底向上分析。 a. 深度分析法 b. 宽度优先分析法 c. 算符优先分析法 d. 递归下降子程序分析法
8. 在编译程序中，语法分析分为自顶向下分析和自底向上分析两类，自顶向下分析试图为 输入符号串构造一个____； a. 语法树 b. 有向无环图 c. 最左推导 d. 最右推导
9. 在编译程序中，语法分析分为自顶向下分析和自底向上分析两类，自底向上分析试图为 输入符号串构造一个____ 。 a. 语法树 b. 有向无环图 c. 最左推导 d. 最右推导
10. 采用自顶向下分析方法时，要求文法中不含有____。
a. 右递归 b. 左递归 c. 直接右递归 d. 直接左递归
11. LR分析是寻找右句型的____；而算符优先分析是寻找右句型的____。 a. 短语； b. 素短语； c. 最左素短语； d. 句柄
12. LR分析法中分析能力最强的是____；分析能力最弱的是_____。 a. SLR(1)； b. LR(0)； c. LR(1)； d. LALR(1)
13. 设有文法G： T->T*F | F
F->F↑P | P P->(T) | a
该文法句型T*P?(T*F)的最左直接短语是下列符号串________。 a. (T*F)， b. T*F， c. P， d. P↑(T*F)
14. 在通常的语法分析方法中，（ ）特别适用于表达式的分析。 a．算符优先分析法 b．LR分析法 c．递归下降分析法 d．LL(1)分析法
15. 运算符的优先数之间有几种关系____ 。 a.3种 b. 2种 c. 4种 d. 1种
16. 算符优先法属于（ ） a.自上而下分析法 b.LR分析法 c.ＳLR分析法 d.自下而上分析法
17. 在LR分析法中，分析栈中存放的状态是识别规范句型____ 的DFA状态。 a.句柄 b. 前缀 c. 活前缀 d. LR(0)项目
解答: 1. 2. 3. 4. 5. 6. 7. 8. 9. 10.
11. 12. 13. 14. 15. 16. 17.
四.名词解释
1. 短语，直接短语，句柄；
2. 规范归约，规范推导；
3. 算符文法，算符优先文法；
4. 素短语，最左素短语；
5. 前缀，活前缀；
6. LR(0)项目，LR(0)项目集规范族； 解答: 1. 2. 3. 4. 5. 6.
五.简答题
1. 说明任何SLR(1)文法都是LR(1)文法。
2. 为什么移进－归约法不是一种语法分析方法？
3. LR(k)分析法是如何做到严格地自左向右进行分析的？
4. 使用状态有限的识别可归前缀的有穷自动机，为什么可以识别语言的无穷多个句子？
5. LR项目的含义是什么？
解答: 1. 2. 3. 4. 5.
六.应用题
1. 文法如下： S→a | L | (T) T→T, S | S (1) 计算该文法的Firstvt和Lastvt； (2) 构造算符优先关系表,并说明该文法是否是OPG文法； (3) 计算优先函数； (4) 给出串(a,a)#和(a,(a,a)) #的算符优先分析过程。
2. 下列文法是否为SLR(1)文法？若是，请构造相应的分析表。若不是，请说明理由。 S→Sab | bR R→S | a
3. 证明下面文法是SLR(1)文法，并构造其SLR分析表。 E→E+T|T T→TF|F F→F*|a|b 输入串b+ab*是该文法的句子吗？给出对该串的分析过程。
4. 下面文法属于哪类LR文法？试构造其分析表。 S→(SR|a R→,SR|) 输入串（a,a）是文法的句子吗？给出分析过程。
5. 设文法G为 S → A A → BA | ε B → aB | b （1）证明它是LR(1)文法； （2）构造它的LR(1)分析表； （3）给出输入符号串abab的分析过程。
6. 为下面的文法构造LALR(1)分析表 S→E E→E+T | T T→(E) | a 并给出对输入串(a+a)的分析过程。
7. 已知文法 S →L.L S →L L →LB L →B B →0 B →1 用LR分析法说明符号串101.110是否文法的句子。
8. 对于文法 S→AB A→aB B→b (1) 构造LR(1)分析表； (2) 给出用LR(1)分析表对输入符号串abab的分析过程。
9. 给定文法G[Z]： ①Z→C S ②C→if E then ③S→A＝E ④E→E∨A ⑤E→A ⑥A→i 其中：Z、C、S、A、E∈VN ；if、then、＝、∨、i∈VT a) 构造此文法的LR(0)项目集规范族，并给出识别活前缀的DFA。 b) 构造其SLR（1）分析表。
10. 设有文法G[S]： S→aA A→Ab A→b 求识别该文法所有活前缀的DFA；构造合适的LR分析表，并给出对输入串abb的分析过程 。
11. 给定文法 G[S] ： S → SaA|a A → AbS|b ⑴请构造该文法的以 LR(0) 项目集为状态的识别规范句型活前缀的 DFA 。
