与FIRST/FOLLOW避坑指南)
简介：本资源是桂林电子科技大学《编译原理》课程期末考试真题及详解文档，面向计算机科学与技术、软件工程等专业本科生，聚焦编译器构造核心能力训练。内容覆盖乔姆斯基文法分类、LR(0)分析项目识别、语法树推导与句柄判定、属性文法属性类型辨析、运行时存储分配策略、左递归消除与FIRST/FOLLOW集计算、正规语言DFA构造与最小化等高频考点，每道习题均附标准答案与评分依据，便于考前系统复习与自测查漏。资源为单个Word文档（.doc格式），大小422KB，结构清晰，含试卷原题、分步解析、语法树图示及状态转换表等关键学习要素。已有109人下载学习，适合作为期末冲刺、课堂补充与考研基础巩固的权威参考资料。
1. 这不是一份普通考卷：它是桂电编译原理期末实战的「错题黑匣子」，专治语法树画不对、LR(0)项目集推不全、first/follow集合算错这三类高频翻车现场
你是不是也经历过：考前狂背乔姆斯基文法分类，一上考场看到“写出句型(TF+i)的最右推导”，手抖写成最左推导？或者对着“构造识别ba(bba)b的最小DFA”发呆半小时，NFA画得歪歪扭扭，确定化表格填到第三行就发现状态爆炸？这份《编译原理期末考试习题及答案桂电.doc》——表面是2021年桂林电子科技大学A/B两卷真题+标准答案+评分细则，内里却是一份被真实阅卷痕迹反复锤炼过的「抗压训练手册」。它不讲抽象定义，只暴露学生在语法分析、自动机构造、属性文法、运行时存储四大模块中最常卡壳的57个具体操作断点。比如A卷第二题要求画(TF+i)的语法树，答案里直接标出根节点E必须先展开为T而非E+T，否则整棵树结构崩塌；B卷第五题求(ab*|a)*的最小DFA，解法中强制拆解为“NFA→ε-闭包→子集构造→合并等价状态”四步铁律，每步都附带状态合并判据（如{1,2}与{1}是否等价，看其a/b转移后是否同属终态集）。适合正在啃龙书第4章、做头歌编译原理实验卡在SLR(1)表构建、或刷西工大NOJ编译题总被“移进-归约冲突”报错的计算机科班学生——它不教你理论，它教你怎么在120分钟内把分稳稳拿到手。
2. 从文法推导到语法树：用A卷第二题拆解「最右推导」的不可妥协逻辑链
2.1 最右推导的本质：终结符永远在最右端被替换，这是语法树自底向上生长的逆向映射
很多同学误以为“最右推导=从右往左写产生式”，其实核心约束是：每一步推导中，被替换的非终结符必须是当前句型中最右边的那个。以A卷第二题句型(T*F+i)为例，其起始符号是E，目标是得到(T*F+i)。若错误地从E ⇒ E+T开始（因为+在字符串中间），就违背了最右原则——此时E+T中最右非终结符是T，而非E。正确路径必须从E ⇒ T切入，因为T是E的最右直接推导项。后续每一步都严格遵循“找当前串最右非终结符→选其产生式→替换”，这才保证最终语法树的叶子节点顺序与输入串完全一致。答案中E ⇒ T ⇒ F ⇒ (E) ⇒ (E+T) ⇒ (E+F) ⇒ (E+i) ⇒ (T+i) ⇒ (T*F+i)这条链，每个箭头都对应语法树一层节点的展开，漏掉任意一环，树高就少一层。
2.2 语法树绘制的三个硬性校验点：根、叶、分支方向必须闭环
答案给出的语法树虽未图示，但隐含三重校验逻辑：
- 根节点必须是文法开始符号S（本题为E）：若画成T或F为根，说明推导起点错误；
- 所有叶子节点必须是终结符且顺序严格等于输入串：
(T*F+i)共7个字符，树叶子从左到右必须是(、T、*、F、+、i、)，缺一不可； - 内部节点必须是产生式左部，且其子节点严格匹配产生式右部：例如
F节点下必须有(、E、)三个子节点（因F → (E)），若画成F → i则直接判错。
提示：考试时若时间紧，可先写最右推导链，再按链反向逐层画树——推导第n步生成的符号，就是树第n层的节点。
2.3 短语/直接短语/句柄的判定：用“子树叶子序列”代替死记硬背
传统教学常让学生背“短语是某子树所有叶子”，但实操中易混淆子树范围。A卷答案给出的判定法更可靠：
- 列出所有子树：对语法树做DFS，每遇到一个非终结符节点，将其整个子树叶子序列记为一个候选短语；
- 过滤非终结符：剔除含非终结符的序列（如
(E+i)含E，不是短语）； - 直接短语=高度为2的子树叶子：即父节点直接连终结符的子树，如
T*F对应T和F节点下的*； - 句柄=最左直接短语：在
(T*F+i)中，T*F比i位置更左，故为句柄。
B卷第二题句型(a,(a,a))的句柄是a而非(a,a)，正因a所在子树高度为2（S → a），而(a,a)对应T → T,S的子树高度为3。
3. 自动机构造实战：用A卷第四、五题打通NFA→DFA→最小化全流程
3.1 正规文法转NFA：A卷第四题的“状态爆炸预警”与消解策略
A卷第四题文法G[S]：(1) S → Sa | Ab | b (2) A → Sa，若机械套用“每个非终结符一个状态”，会得到S、A、F（终态）三个状态，但S → Sa产生自环，A → Sa引入S到A转移，S → Ab又需A到b转移——此时NFA状态数激增。答案采用终态吸收法：将所有产生式右部终结符直接指向终态F，非终结符转移保留在S/A间。具体步骤：
- 创建初始状态S，终态F；
S → Sa：S加a自环；S → Ab：S经b到新状态A；S → b：S经b直接到F（注意：此处b既是S→b的终结符，也是S→Ab的终结符，需合并）；A → Sa：A经a回到S。
最终NFA仅S、A、F三状态，转移边清晰。关键洞察：正规文法中形如X → aY的产生式，对应NFA中X经a到Y；X → a对应X经a到终态——此规则比教材“增加新终态”更简洁。
3.2 NFA确定化：用子集构造法破解A卷第五题的“ba(bba)b”迷宫
该正规式看似复杂，但确定化过程可拆解为四步：
- 构造NFA：按Thompson算法，
b*用自环，a用单边，(bb*a)用嵌套循环，*外层再套自环； - ε-闭包计算：初始状态0的ε-闭包={0}（无ε边），但进入
b*后需重新计算； - 子集转移表：答案给出的表格
{0}→{1,3}、{1,3}→Φ等，本质是枚举所有可能状态子集，对每个子集计算a/b输入后的下一子集； - 终态判定：只要子集中含原NFA终态，新DFA状态即为终态。
注意：A卷答案中
{1,3}→Φ表示输入a后无转移，这在DFA中合法（意味着拒绝），但考生常误填“error”或留空，导致扣分。
3.3 DFA最小化：B卷第五题“(ab*|a)*”的等价状态合并三原则
B卷第五题答案的最小化过程隐含三条铁律：
- 终态与非终态永不等价：任何含终态的子集必单独成类；
- 转移目标同类才等价：状态p,q等价，当且仅当对所有输入符号a，δ(p,a)与δ(q,a)属于同一等价类；
- 迭代分裂直到稳定：初始将状态分为终态/非终态两类，再检查每类内状态转移是否指向不同类，是则分裂。
B卷答案中{1,2}最终合并，因其对a/b的转移均指向自身类内——这正是最小DFA仅剩两个状态的原因。若考试中时间不够，可优先验证：最小DFA状态数=原NFA中可区分字符串数，对(ab*|a)*，仅需区分空串、a、ab、abb...等，故最小状态数确为2。
4. 文法改造与预测分析：用A/B卷第六、七题攻克LL(1)与算符优先两大难关
4.1 消除左递归的“双保险”写法：A卷第六题T→T,S|S的改造陷阱
A卷第六题文法T → T,S | S是典型直接左递归。标准解法引入新非终结符T'：T → ST'，T' → ,ST' | ε。但考生常犯两错：
- 遗漏T'的ε产生式：导致无法生成单个S（如句型
a）； - 错误保留原产生式：写成
T → ST' | S，造成二义性。
答案采用严格替换法：原产生式T → T,S完全删除，仅保留T → ST'，并确保T'能生成任意长度,S序列。验证方法：取句型(a,a)，推导链为T ⇒ ST' ⇒ (T)T' ⇒ (S)T' ⇒ (a)T' ⇒ (a),ST' ⇒ (a),ST' ⇒ (a),aT' ⇒ (a),aε，完美覆盖。
4.2 FIRST/FOLLOW集合的手算心法：B卷第六题LL(1)表构建的“三不原则”
B卷第六题要求为S → ^ | a | (T),T → ST' | S,T' → ,ST' | ε构造LL(1)分析表。FIRST/FOLLOW计算易错点：
- FIRST不传播ε：
FIRST(T') = {,} ∪ {ε}，但FIRST(T) = FIRST(S) = {^,a,(}，不包含ε（因T→S不推导ε）； - FOLLOW不重复添加：
FOLLOW(T')含#（因T'在句尾），也含)（因S → (T)中T后是)），但FOLLOW(T)不含)（因T后无符号）； - 终结符优先于非终结符：
FOLLOW(S)中#来自文法开始，,来自T' → ,ST'，)来自S → (T)——三者并列，无主次。
答案表格中S行^列填S → ^，a列填S → a，(列填S → (T)，T行,列填T → ST'，#列填T → S（因FOLLOW(T) = {#}），逻辑严密。
4.3 算符优先关系表：B卷第七题firstVT/lastVT的“边界穿透”技巧
B卷第七题给出firstVT/lastVT，要求构造算符优先关系表。关键技巧在于穿透非终结符边界：
a <· b当且仅当存在产生式A → ...ab...或A → ...aBb...且b ∈ firstVT(B)；a ·> b当且仅当存在A → ...Ba...且b ∈ lastVT(B)；a =· b当且仅当存在A → ...ab...。
答案中i <· +成立，因S → SiA且+ ∈ firstVT(A)；+ >· i成立，因A → A+B且i ∈ lastVT(B)。考生常忽略lastVT(B) = {* , (}中(的存在，导致* =· (漏判。
5. LR分析与语义动作：用A/B卷第八、九题直击SLR(1)表构建与回填机制核心
5.1 LR(0)项目集规范族：A卷第八题文法S → BB,B → aB | b的状态爆炸控制术
A卷第八题要求给出LR(0)项目集规范族。该文法虽简单，但B → aB产生自环，易导致无限状态。答案采用闭包截断法：
I0: S' → .S闭包得S → .BB,B → .aB,B → .b；I0经a转移至I3: B → a.B,B → .aB,B → .b；I3经a转移又回I3，形成循环，此时停止扩展，标记I3为自循环状态。
最终仅得I0-I6七个状态，而非理论无穷。考试中若遇类似文法，可声明：“因B → aB产生a自环，I3经a转移不变，故不再生成新状态”。
5.2 SLR(1)分析表填写：A卷第八题Action/Goto表的“follow驱动”逻辑
SLR(1)表中Action列由FOLLOW驱动，Goto列由文法结构驱动。A卷答案中：
I1（S' → S.）对#填acc，因# ∈ FOLLOW(S')；I2（S → B.B,B → .aB,B → .b）对a填s3（移进到I3），对b填s4（移进到I4），对#填r3（归约B → b），因# ∈ FOLLOW(B)；I5（S → BB.）对#填r1（归约S → BB），因# ∈ FOLLOW(S)。
注意：
r2（B → aB）出现在I3对a,b,#的归约列，因FOLLOW(B) = {a,b,#}——这是SLR(1)比LR(0)强的关键：用FOLLOW过滤归约时机。
5.3 语义动作中的回填机制：B卷第九题DO-WHILE的“nxq指针”实战解析
B卷第九题DO-WHILE语义动作中backpatch($2.FC, $1.loop)是核心。$2.FC是S1的false链（跳转地址未定），$1.loop是do标签地址。执行流程：
R → do：记录当前四元式序号nxq为loop地址；U → R S1 while：S1生成代码后，其false链FC暂存，$$.loop = $1.loop传递循环入口；S → U E：E计算后，若为假则需跳转到$1.loop，故backpatch($2.FC, $1.loop)将S1的false链所有待填地址写入$1.loop。
考生常混淆TC（true chain）与FC，答案中Backpatch($2.TC, nxq)确保E为真时继续执行S1，形成闭环。
6. 避坑指南：编译原理期末考前必须扫清的7个致命细节
6.1 现象：最右推导写成最左推导，语法树根节点错位
原因：混淆“最右推导”与“最左推导”定义，误将推导方向等同于书写方向。最右推导要求每步替换最右非终结符，与书写顺序无关。
解决：在草稿纸左侧列句型，右侧写推导式，每步圈出被替换的最右非终结符。如(T*F+i)中，E ⇒ T后句型为T*F+i，最右非终结符是T（非i），故下一步必须替换T。
6.2 现象：DFA最小化时合并了不该合并的状态，导致接受字符串错误
原因：未严格执行“终态/非终态分离”原则，或对转移目标判断失误。例如将含终态与不含终态的状态强行合并。
解决：最小化前先标出所有终态，初始划分必为{终态集, 非终态集}；每次分裂时，对每个子集内状态检查其a/b转移目标是否同属一类，不同则分裂。
6.3 现象：FIRST集合漏算ε，导致LL(1)分析表多填或少填
原因：未理解ε仅在产生式能推导空串时才加入FIRST，且传播需满足“右部全可ε推导”。
解决：对每个非终结符X，初始化FIRST(X)=∅；遍历产生式X → Y1Y2...Yk，若Y1不能ε推导，则FIRST(X) += FIRST(Y1)；若Y1能ε推导，则继续检查Y2，直至某Yi不能ε推导，或全部可ε推导则加ε。
6.4 现象：SLR(1)表中出现“移进-归约冲突”，误判为文法非SLR(1)
原因：未检查FOLLOW集是否与移进符号交集为空。冲突存在不代表文法不合格，需验证FOLLOW(A) ∩ {a} = ∅是否成立。
解决：对冲突项，查归约产生式A → α的FOLLOW(A)，若含移进符号a，则确为冲突；否则是计算错误。A卷第八题I2中a对应移进，FOLLOW(B)={a,b,#}含a，故r3/s3冲突真实存在。
6.5 现象：算符优先关系表中<·与·>颠倒，导致语法分析器死循环
原因：混淆firstVT（最左终结符）与lastVT（最右终结符）的用途。a <· b需b ∈ firstVT(B)，a ·> b需b ∈ lastVT(B)。
解决：记忆口诀“小于号看右边，大于号看左边”：a <· b中b在a右，故查b所在非终结符的firstVT；a ·> b中a在b左，故查a所在非终结符的lastVT。
6.6 现象：语义动作中backpatch参数顺序写反，生成代码跳转地址错误
原因：混淆链表头指针与填入地址。backpatch(chain, addr)是将chain链表中所有待填地址设为addr，非反之。
解决：chain必为四元式序号链表（如100→105→0），addr为具体序号（如200），执行后链表变为200→200→0。
6.7 现象：属性文法中继承属性在父节点未定义就传递给子节点
原因：未遵守“继承属性由父节点或兄弟节点提供，综合属性由子节点计算”。
解决：画语法树，在每个节点旁标注属性类型：父节点箭头向下为继承属性，子节点箭头向上为综合属性。如S → if E then S1 else S2中，S1的in继承自S，S的out综合自S1.out。
7. 考前30分钟急救包：用A/B卷对比表锁定高频考点与命题人偏好
7.1 A卷与B卷核心考点分布对比：抓住桂电命题的“三三制”规律
| 考点模块 | A卷分值 | B卷分值 | 命题特征 |
|---|---|---|---|
| 文法与推导 | 20 | 20 | A卷考最右推导+语法树，B卷考最左推导+句柄；均强调“推导路径唯一性”验证 |
| 自动机构造 | 12 | 12 | A卷考正规文法转DFA，B卷考正规式转DFA；均要求写出NFA→DFA→最小化全过程 |
| 文法改造 | 10 | 10 | A卷考消除左递归，B卷考LL(1)分析表；均以`S → ^ |
| LR分析 | 15 | 15 | A卷考SLR(1)表，B卷考LR(0)项目集；均选用`S → a |
| 语义动作 | 10 | 10 | A卷考NOT-THEN-ELSE，B卷考DO-WHILE；均聚焦backpatch与nxq的协同机制 |
提示：桂电命题明显倾向“同一知识点，AB卷换角度考查”。如自动机部分，A卷给文法求DFA，B卷给正规式求DFA，本质都是子集构造法；语义动作部分，A卷考条件跳转，B卷考循环跳转，核心都是回填链表。
7.2 高频易错点速查清单：考前默写这8条，至少抢回12分
| 序号 | 易错点描述 | 正确结论 | 对应题号 |
|---|---|---|---|
| 1 | 3型文法产生式右部非终结符位置 | 只能在最左或最右，如A → aB或A → Ba，不可A → aBc | A卷一.1 |
| 2 | 语法分析程序输入/输出 | 输入：单词符号（token）；输出：语法单位（语法树节点） | A卷一.2 |
| 3 | LR(0)项目类型判定 | B → .aB为移进项目，B → a.B为待约项目，B → aB.为规约项目 | A卷一.3 |
| 4 | 属性文法两种属性 | 继承属性（父→子），综合属性（子→父） | A卷一.4 |
| 5 | 运行时存储管理方案 | 静态分配、栈式分配、堆式分配（动态分配=栈式+堆式） | A卷一.5 |
| 6 | firstVT/lastVT计算 | firstVT(X)=X能推出的最左终结符集；lastVT(X)=X能推出的最右终结符集 | B卷七 |
| 7 | 算符优先关系<·判定 | 若A → αaBβ且b ∈ firstVT(B)，则a <· b | B卷七 |
| 8 | 四元式backpatch作用 | 将链表中所有0地址替换为指定序号，实现跳转地址回填 | B卷九 |
从那以后我每次考前复盘，都强制走一遍这个清单：先默写8条结论，再对照A/B卷答案验证，最后挑一道题限时重做。不是为了押题，而是让肌肉记住“当看到‘最右推导’四个字时，手指必须先圈出最右非终结符”。希望帮到你。
本文还有配套的精品资源，点击获取
