编译原理期末 · 题型与方法

这张图讲什么

「编译原理期末 · 题型与方法」是 SeekFlaw 编辑团队整理的思维导图,分 7 个一级分支:编译阶段与文法推导基础题;正规式、NFA、DFA 题怎么做;消除左递归和提左公因子怎么做;FIRST 和 FOLLOW 集怎么求;LL(1) 分析表和分析过程怎么做;LR 分析:项目集、分析表和冲突;语义分析、中间代码和优化题,共 114 个节点、113 张记忆卡,含 6 张配图。

这张图按题型组织编译原理期末的常见题:先补编译阶段和文法推导的基础,再依次是正规式与有限自动机、消除左递归与提左公因子、FIRST 与 FOLLOW、LL(1) 分析、LR 分析,最后是语义分析、中间代码、优化与运行时。每个题型给一套步骤和一个自己算过的小例子。建议先做前五枝的算例,再背对照卡。

5 个要点

  • 编译阶段与文法推导基础题:这一枝是选择、填空、简答的常见考点:阶段划分、三类错误、四类文法、推导与句柄。
  • 正规式、NFA、DFA 题怎么做:这一枝按题型走:先给语言写正规式,再 Thompson 构造得到 NFA,用子集法变 DFA,最后最小化。
  • 消除左递归和提左公因子怎么做:自顶向下分析前必须先改文法:消除左递归和提取左公因子。
  • FIRST 和 FOLLOW 集怎么求:FIRST、FOLLOW 是 LL(1) 与 SLR 的共同基础,期末常见的计算题。
  • LL(1) 分析表和分析过程怎么做:LL(1) 题型固定:求 FIRST、FOLLOW → 算 SELECT → 填预测分析表 → 对输入串写栈变化。

适用:大学期末复习。用法:点开任一节点先自己答,再翻面核对。

配图:编译程序六个阶段的流程图;子集构造法把 NFA 变成 DFA 的状态表;DFA 划分法与最小 DFA 的状态图;预测分析器对 abd 的栈变化表;项目集规范族的 6 个状态转移图;SLR(1) 分析 aacbb 的栈变化表。

更新于

一句话:这张图把「编译原理期末 · 题型与方法」整理成 114 个节点、113 张记忆卡;点开节点翻面就能看答案。

按题型给出步骤:正规式与自动机、消除左递归、FIRST/FOLLOW、LL(1)、LR 分析表,附算例,适合期末突击。点开任一节点翻面看答案,登录后可存进自己的空间,按遗忘曲线复习。

SeekFlaw 求瑕是面向初中、高中、考研、考公考前速记的思维导图与记忆卡平台:把课件、讲义变成思维导图,节点翻面就是记忆卡,按遗忘曲线安排复习。

114 个节点 · 113 张记忆卡。作者:SeekFlaw 编辑团队;发布于 2026-11-20。

先看这 3 条

  1. 编译程序一般分哪几个阶段:按顺序是词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成,其中 符号表管理 和 出错处理 贯穿各阶段。
  2. FIRST 集的计算规则:终结符 a: FIRST(a)={a} 。
  3. 综合属性和继承属性怎么区分:看信息往哪个方向传:综合属性是自底向上,继承属性是自上而下或横向。

编译阶段与文法推导基础题

  • 编译程序一般分哪几个阶段:按顺序是词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成,其中 符号表管理 和 出错处理 贯穿各阶段。 区分 前三个阶段偏「看懂源程序」(前端),后面偏「生成目标代码」(后端)。 易错 阶段是功能划分,实际编译程序常把几…
  • 词法、语法、语义错误怎么区分:看出错的层次:词法错误是 单个单词 不合法,例如出现语言字母表以外的字符;语法错误是 结构 不合文法,例如括号不配对、缺少 then ;语义错误是结构合法但 意义 不对,例如使用未声明的变量、类型不匹配。 易错 括号不配对属于语法错误,不…
  • 编译和解释有什么区别:编译先把 整个 源程序翻成目标程序,再运行目标程序,目标程序可反复执行、速度快;解释是 逐句翻译、立即执行 ,不生成完整目标程序,每次运行都要重新翻译。 区分 解释便于调试和交互,代价是运行慢;编译的错误在运行前集中报告。
  • 「遍」和「阶段」是一回事吗:不是。 阶段 是功能上的划分;一遍是把源程序(或中间表示)从头到尾扫描一遍。一遍里可以包含多个阶段,一个阶段也可能要跨多遍。 区分 一遍编译边分析边生成代码,占空间小;多遍编译便于模块化和优化。
  • 词法分析器输出什么:输出单词序列,每个单词常表示成二元式 (种别, 属性值) 。 例 源码 if x1 >= 10 then 得到 5 个单词: if (关键字)、 x1 (标识符,属性指向符号表)、 >= (运算符)、 10 (整常数,属性是 10)、 t…
  • 乔姆斯基四类文法怎么区分:0 型: α → β ,α 至少含一个非终结符,无其他限制;1 型:要求 α 的长度 不超过 β 的长度;2 型:左部是 单个非终结符 ,即 A → β ;3 型:在 2 型基础上,右部形如 aB 或 a (右线性),或 Ba 或 a (…
  • 最左推导和最右推导有什么区别:每步替换 最左 (最右)的非终结符。最右推导又叫 规范推导 ,它的逆过程就是 LR 分析里的规范归约;LL 分析对应最左推导。 例 文法 S → AB , A → a , B → b ,句子 ab :最左推导 S⇒AB⇒aB⇒ab;最右推…
  • 怎样证明一个文法有二义性:找 一个句子 ,它有两棵不同的语法树(等价地,有两个不同的最左推导)。 例 文法 E → E+E | E*E | id ,句子 id+id*id :一棵先算 id*id 再相加,另一棵先算 id+id 再相乘,是两棵不同的树,所以文法二义…
  • 句型、句子、语言有什么区别:从开始符号推出的符号串(可含非终结符)是 句型 ;只含终结符的句型是 句子 ;文法生成的全部句子构成 语言 。 例 文法 S → aSb | c : aSb 是句型但不是句子; aacbb 是句子;语言是 $\{a^n c b^n \mi…
  • 短语、直接短语、句柄怎么找:看语法树:子树叶子从左到右连起来是短语;只有父子两层的子树对应直接短语;最左的直接短语是句柄。 例 文法 S → aSb | c ,句型 aaSbb :短语有 aSb 和 aaSbb ;直接短语只有 aSb ,它也是 句柄 ,可归约为 S…

正规式、NFA、DFA 题怎么做

  • 正规式运算的优先级怎么记:闭包 * 最高,连接次之,选择 | 最低。 例 a|bc* 表示「一个 a」或「b 后面跟零个或多个 c」,等价于 a|(b(c*)) , 不是 (a|b)c* 。 易错 括号决定闭包管谁: (ab)* 重复整体 ab , ab* 只重复…
  • 「以 a 开头、以 b 结尾」怎么写:字母表 {a,b} 时写 a(a|b)*b 。 步骤 固定头 a,中间任意(零个或多个),固定尾 b。 易错 串的长度 至少是 2 :单个 a 不以 b 结尾,所以不在语言里。
  • 「含子串 ab」的串怎么写:字母表 {a,b} 时写 (a|b)*ab(a|b)* :前后各任意,中间固定 ab 。 例 bbabb 拆成 bb 、 ab 、 b ,匹配; bbba 里没有 ab ,不匹配。 易错 不能写成 a*b* :它只表示「若干 a 后接若干…
  • 「不含子串 aa」的串怎么写:字母表 {a,b} 时写 (b|ab)*(a|ε) 。 步骤 每个 a 后面要么是 b、要么到串尾:把串拆成若干块 b 或 ab ,末尾最多再补一个 a。 例 babab 拆成 b 、 ab 、 ab ,属于 (b|ab)* ; baab…
  • 「a 的个数是偶数」怎么写:字母表 {a,b} 时写 b*(ab*ab*)* :a 成对出现,b 可以随意插入。 例 abbab 有 2 个 a:按 ab* 拆成 abb 、 ab ,匹配成功; bb 一个 a 也没有,由前面的 b* 匹配,也属于语言。 记法 个数…
  • 正规式等价有哪些常用恒等式:常用: (a*)* = a* , a*a = aa* , (a|b)* = (a*b*)* , (a|ε)* = a* 。 易错 (a|b)* 与 a*|b* 不等价 :前者含 ab ,后者不含; (ab)* 与 a*b* 也不等价:前者…
  • 标识符、整数、小数的正规定义怎么写:先设 letter 为任一字母, digit 为任一数字:标识符 letter(letter|digit)* ;无符号整数 digit digit* (即 digit+ );无符号小数 digit+ . digit+ 。 易错 标识符 不…
  • Thompson 构造的基本规则有哪几条:符号 a:两个状态、一条 a 边。选择 r|s :新起点用 ε 边连 r、s 的起点,r、s 的终点用 ε 边连新终点。连接 rs :r 的终点与 s 的起点用 ε 边相连。闭包 r* :新起点和新终点,加 ε 边:起点→r 起点、r 终…
  • ε-closure 和 move 怎么算:ε-closure(S) :从 S 中任一状态出发, 只走 ε 边 能到的所有状态, 包括 S 本身 。 move(S,a) :从 S 中任一状态走 一条 a 边 到达的状态集,不再沿 ε 边扩展。 例 0 –ε→ 1,1 –ε→ 2,0…
  • 子集构造法的步骤:从 NFA 初态的 ε-闭包出发,逐个状态集、逐个输入符号地算新状态集,直到没有新集合。 步骤 ① 起始状态 A = ε-closure({初态}) ;② 对每个未处理的状态集 T 和输入符号 a,算 U = ε-closure(move…
  • 例:一个 NFA 怎样变成 DFA:NFA 状态 0~4,初态 0,终态 4:0–ε→1,0–ε→2,1–a→1,1–a→3,2–b→2,2–b→3,3–b→4。 步骤 A=ε-closure(0)={0,1,2};A 读 a 得 {1,3}=B,读 b 得 {2,3}=C…
  • NFA 和 DFA 有什么区别:DFA 每个状态对每个符号 至多一条 转移,没有 ε 边;NFA 可以有多条同符号转移,也可以有 ε 边。两者 识别能力相同 ,都恰好识别正规集。 区分 NFA 构造简单、状态少;DFA 便于直接编程实现。 易错 含 n 个状态的 NFA…
  • DFA 最小化(划分法)的步骤:先按终态和非终态分块,再反复按「读符号后去哪一块」拆块,拆不动时每块合成一个状态。 步骤 ① 删去不可达状态;② 分成终态、非终态两块;③ 对每块,看块内各状态读每个符号后落到哪一块, 去向不同就拆开 ;④ 重复到不能再拆;⑤ 每块合并成…
  • 例:6 个状态的 DFA 最小化:状态 1~6,终态 5、6:1–a→2,1–b→3,2–a→4,2–b→5,3–a→4,3–b→6,4–a→4,4–b→5,5–a→4,5–b→5,6–a→4,6–b→6。 步骤 初分 {5,6}、{1,2,3,4};状态 1 读 a、b…
  • 最小化前要先删掉哪些状态:最小化前一定要删 不可达状态 (从初态走不到); 死状态 (走不到任何终态)可以留到最小化后再去掉,最小化过程中把死状态当作一个陷阱状态一起划分。 区分 不可达状态删去后语言不变;死状态删去后,对应转移变成「没有」,需要补全时再加回陷阱状…
  • DFA 怎样转成正规式:用 Arden 引理 联立方程:若 X = rX | s (r 不含 ε),则 X = r*s 。 例 DFA 有状态 A(初态且终态)、B:A–a→B,B–a→A,A–b→A,B–b→B。列 A = bA|aB|ε , B = bB|a…
  • 词法分析里最长匹配怎么处理:从当前位置起尽量多读,取能被识别的最长串作为一个单词( 最长匹配 );关键字通常按标识符识别,再查保留字表确定。 例 输入 ifx>=3 : ifx 整体是标识符,不是 if 加 x ; >= 是一个运算符,不是 > 和 = 。 易错 读…
  • 右线性文法怎样转成 NFA:每个非终结符对应一个状态,开始符号对应初态,再按产生式连边。 步骤 A → aB :A 读 a 到 B; A → a :A 读 a 到新增的终态 F; A → ε :A 本身是终态。 例 文法 S → aS | bA , A → aA |…

消除左递归和提左公因子怎么做

  • 为什么要先消除左递归:左递归 A → Aα 会使递归下降或预测分析在 不读入任何符号 的情况下反复展开 A,陷入无限循环,所以含左递归的文法不是 LL(1) 文法。 易错 消除左递归 不改变 生成的语言,但语法树形状会变(左递归变成右递归形式)。
  • 直接左递归的消除公式:A → Aα1 | Aα2 | β1 | β2 (βi 不以 A 开头)改写为 A → β1A' | β2A' , A' → α1A' | α2A' | ε 。 记法 非左递归的候选式后面接 A';递归的那部分去掉 A 后放进 A' 里,…
  • 例:消除直接左递归:文法 A → Ab | Acd | e | f 。 步骤 α 有 b 、 cd ,β 有 e 、 f ,改写为 A → eA' | fA' , A' → bA' | cdA' | ε 。 验证 原文法 A⇒Ab⇒Acdb⇒ecdb,新文法…
  • 间接左递归怎么消除:先给非终结符排序,再按序把前面符号的候选式代入,最后消除直接左递归。 步骤 ① 排序 A1, A2, …, An;② 对 i 从小到大,把 Ai → Ajγ (j<i)中的 Aj 用它的全部候选式代入;③ 消除 Ai 的直接左递归。 易错…
  • 例:消除间接左递归:文法 S → Aa | b , A → Ac | Sd | e ,按 S、A 排序。S 无直接左递归;A 的候选 Sd 代入 S 的候选式,得 A → Ac | Aad | bd | e 。 结果 消除直接左递归: A → bdA' | …
  • 提取左公因子的步骤:候选式有公共前缀: A → αβ1 | αβ2 | γ ,改写为 A → αA' | γ , A' → β1 | β2 。 步骤 取 最长 公共前缀 α;新非终结符 A' 的候选式如果还有公共前缀,继续提,直到没有为止。 目的 向前看一个…
  • 例:提取左公因子:文法 A → abc | abd | ae | f 。 步骤 先提 a: A → aA1 | f , A1 → bc | bd | e ;A1 的前两个候选还共有 b,再提: A1 → bA2 | e , A2 → c | d 。 验证 …
  • 悬空 else 为什么不是 LL(1):文法 S → if E then S | if E then S else S | other ,提公因子得 S → if E then S S' | other , S' → else S | ε 。 分析 else 既在 S' → e…

FIRST 和 FOLLOW 集怎么求

  • FIRST 集的计算规则:终结符 a: FIRST(a)={a} 。若有 X → ε ,则 ε∈FIRST(X)。 X → Y1Y2…Yk :先把 FIRST(Y1) 去掉 ε 后加入;若 Y1 可空,再加 FIRST(Y2) 去掉 ε 的部分,依次类推; 只有所…
  • 符号串的 FIRST 怎么算:从左往右:加入 FIRST(X1)−{ε} ,若 X1 可空,再看 X2,依此类推;全部可空才加 ε。 例 文法有 B → b | ε , C → cC | d : FIRST(BC) 先得 {b} ;B 可空,再加 FIRST(C)={…
  • 例:求一个文法的 FIRST:文法 S → ABC , A → aA | ε , B → b | ε , C → cC | d 。 结果 FIRST(A)={a,ε} , FIRST(B)={b,ε} , FIRST(C)={c,d} ;S 的右部 ABC 中 A、B…
  • 怎么判断非终结符可空:有 A → ε ,或某个候选式 A → Y1…Yk 的每个 Yi 都可空,则 A 可空;反复推导到不再变化。 例 A → BC , B → ε , C → ε | c :B 可空,C 可空,所以 A 也可空。 易错 候选式里只要含一个 终…
  • FOLLOW 集的三条规则:① 开始符号 S: # ∈ FOLLOW(S) ;② A → αBβ : FIRST(β)−{ε} 加入 FOLLOW(B) ;③ A → αB ,或 A → αBβ 且 β 可空: FOLLOW(A) 加入 FOLLOW(B) 。 易错…
  • 例:求一个文法的 FOLLOW:文法 S → ABC , A → aA | ε , B → b | ε , C → cC | d 。 步骤 FOLLOW(S)={#} ;A 后面是 BC, FIRST(BC)={b,c,d} ,所以 FOLLOW(A)={b,c,d} …
  • FIRST 和 FOLLOW 怎么区分:FIRST 针对 符号串 ,是它能推出的串的首终结符,可含 ε;FOLLOW 只针对 非终结符 ,是句型里紧跟它之后的终结符,含 # ,不含 ε。 记法 FIRST 往里看(A 能推出什么开头),FOLLOW 往外看(A 的后面能出现什么…
  • 手算 FOLLOW 怎样不漏项:把关系列出来再反复代入,直到集合不再变化。 步骤 ① 把每个非终结符在所有右部里的出现位置逐个列出;② 按规则②③写成关系,如 FOLLOW(S) ⊆ FOLLOW(C) ;③ 反复代入至不变。 易错 同一非终结符在多条产生式里出现, 每…

LL(1) 分析表和分析过程怎么做

  • LL(1) 的 LL 和 1 是什么意思:第一个 L:从左到右扫描输入;第二个 L:构造 最左推导 ;括号里的 1:每步 向前看 1 个 输入符号决定用哪条产生式。 易错 LL(1) 文法不能含左递归,也不能二义。
  • SELECT 集怎么算:对产生式 A → α :若 ε∉FIRST(α),则 SELECT = FIRST(α) ;若 ε∈FIRST(α),则 SELECT = (FIRST(α)−{ε}) ∪ FOLLOW(A) 。 例 A → ε 的 SELECT 就是 …
  • LL(1) 文法的判定条件:对同一非终结符的任意两个候选式 A → α | β ,两者的 SELECT 集 不相交 。等价写法:① FIRST(α) ∩ FIRST(β) = ∅ ;② 若 ε∈FIRST(β),则 FIRST(α) ∩ FOLLOW(A) = ∅ …
  • 例:判定文法是不是 LL(1):文法 S → ABC , A → aA | ε , B → b | ε , C → cC | d : SELECT(A→aA)={a} , SELECT(A→ε)={b,c,d} ; SELECT(B→b)={b} , SELECT(B→…
  • 文法不是 LL(1) 有哪几种原因:三种:① 含 左递归 ;② 有 左公因子 ;③ 二义性,或 FIRST 与 FOLLOW 冲突。 区分 前两种能靠改写消除;二义性通常要改文法本身,或像悬空 else 那样人为规定一条匹配规则。 易错 消除了①②,仍可能不是 LL(1)。
  • 预测分析表怎么构造:按每条产生式的 SELECT 集把它填进表里,其余格子是出错。 步骤 ① 求 FIRST、FOLLOW;② 对每条 A → α 求 SELECT;③ 对 SELECT 里每个终结符 a(含 # ),令 M[A,a] = A → α ;④ …
  • 例:一个文法的预测分析表:文法 S → ABC , A → aA | ε , B → b | ε , C → cC | d 。 结果 S 行:a、b、c、d 列都填 S→ABC ;A 行:a 列填 A→aA ,b、c、d 列填 A→ε ;B 行:b 列填 B→b …
  • 预测分析器的栈怎么动:看栈顶 X 和当前输入 a:X 与 a 都是 # → 接受 ;X 是终结符且等于 a → 弹出 X、读下一个符号;X 是非终结符 → 查 M[X,a] ,弹出 X,把右部 逆序 压栈(右部第一个符号在栈顶), X→ε 就只弹出;表格为空 …
  • 例:对输入串 abd 写分析过程:文法 S → ABC , A → aA | ε , B → b | ε , C → cC | d ,输入 abd# 。 步骤 栈 S、# 起始: S→ABC , A→aA ,匹配 a, A→ε , B→b ,匹配 b, C→d ,匹配 d…
  • 递归下降和表驱动分析有什么区别:两者都是 LL(1) 的自顶向下分析,对文法的要求一样(无左递归、无公因子)。 递归下降 :每个非终结符写一个函数,靠函数调用栈; 表驱动 :一个通用程序加显式的栈和预测分析表。 区分 递归下降手写直观;表驱动只换表就能处理别的文法,易于…
  • 预测分析遇到空表项怎么办:空表项表示 语法错误 ,分析器报错。常见的恢复办法是 恐慌模式 :丢弃输入符号,直到遇到同步符号(常取 FOLLOW 集里的符号),再弹栈继续分析。 易错 空表项不是「接受」,也不是「ε 产生式」; A→ε 对应的格子是填了的。

LR 分析:项目集、分析表和冲突

  • LR 分析和 LL 分析有什么区别:LL 自顶向下,从开始符号 推导 出输入串,对应最左推导;LR 自底向上,把输入串 归约 到开始符号,归约顺序是最右推导的逆( 规范归约 ),句柄总在栈顶。 区分 LR 每一步决定「移进还是归约、按哪条产生式归约」;LR(1) 文法类比 …
  • LR 项目有哪几类:项目 = 产生式 + 圆点位置,按圆点后的符号分四类。 区分 圆点后是终结符, 移进项目 ;圆点后是非终结符, 待约项目 ;圆点在最右, 归约项目 ; S' → S· 是接受项目。 例 S → aSb 有 4 个项目: S→·aSb , …
  • 为什么要拓广文法:增加新的开始符号和产生式 S' → S ,使 接受状态唯一 :只有当 S'→S· 出现并且输入读完时才接受。 易错 拓广文法的 S' 只出现在左部,且只有这一条产生式。
  • CLOSURE 和 GOTO 怎么算:CLOSURE(I) :若 A→α·Bβ 在 I 中,就把 B 的所有产生式 B→·γ 加入,反复到没有新项。 GOTO(I,X) :取 I 中圆点后是 X 的项目,圆点右移一位,再求 CLOSURE。 例 文法 S→aSb | c ,令…
  • 例:画出项目集规范族:拓广文法:(0) S'→S ,(1) S→aSb ,(2) S→c 。 结果 共 6 个状态:I0= {S'→·S, S→·aSb, S→·c} ;I1=GOTO(I0,S)= {S'→S·} ;I2=GOTO(I0,a)= {S→a·S…
  • 含 ε 产生式的项目怎么处理:A → ε 只有项目 A→· ,它是 归约项目 ,一进入状态就可按 A→ε 归约;归约时 弹出 0 个 符号,直接查 GOTO。 例 文法 S→Ab , A→ε : I0={S'→·S, S→·Ab, A→·} 。SLR 里 FOLLOW…
  • ACTION 表和 GOTO 表怎么填(SLR(1)):① 圆点后是终结符 a 且 GOTO(Ik,a)=Ij : ACTION[k,a]=sj ;② 归约项目 A→α· (A 不是 S'):对 a∈FOLLOW(A) 填 rn (n 是产生式编号);③ S'→S· : ACTION[k,#]…
  • 例:一个文法的 SLR(1) 分析表:文法 (1) S→aSb ,(2) S→c , FOLLOW(S)={b,#} 。 结果 状态 0:a→s2,c→s3,GOTO[S]=1;1: # →acc;2:a→s2,c→s3,GOTO[S]=4;3:b、 # →r2;4:b→s5…
  • 例:用分析表对 aacbb 写分析过程:对输入 aacbb# :先移进 a、a、c,再按 r2、r1、r1 归约,最后接受。 条件 文法 (1) S→aSb ,(2) S→c ;SLR(1) 表:状态 0:a→s2,c→s3,GOTO[S]=1;1: # →acc;2:a→s2…
  • 归约时状态栈要弹出几个状态:弹出的个数等于所用产生式 右部符号的个数 (右部为 ε 弹 0 个);弹完后看栈顶状态 k,再查 GOTO[k,A] ,把得到的新状态压栈。 例 按 S→aSb 归约弹 3 个,按 A→ε 归约弹 0 个。 易错 弹出个数由产生式长度决定…
  • LR(0) 有冲突而 SLR(1) 没有的情形:项目集里同时有归约项目和移进项目( 移进-归约冲突 ),LR(0) 无法判定;SLR(1) 只在 FOLLOW(A) 的符号上归约,移进符号若不在 FOLLOW 里,就没有冲突。 例 文法 E→T+E | T , T→a ,状态 {E→T…
  • SLR(1) 为什么还会有冲突:SLR 对归约项目 A→α· 一律用整个 FOLLOW(A) 作向前搜索符,太粗:有些符号在 这个具体状态 里其实不可能跟在 A 后面。LR(1) 的项目带着与状态相关的向前搜索符,更精确。 易错 不是文法有问题,是 SLR 表用的信息不…
  • 例:SLR(1) 有冲突而 LR(1) 没有的文法:文法 S→aAd | bBd | aBe | bAe , A→c , B→c ,FOLLOW(A)=FOLLOW(B)={d,e}。 SLR 读 ac 后状态 {A→c·, B→c·} ,d、e 上两条都能归约, 归约-归约冲突 。 LR…
  • LR(1) 项目的向前搜索符怎么算:求闭包时,对 [A→α·Bβ, a] 和每条 B→γ ,加入 [B→·γ, b] ,其中 b ∈ FIRST(βa) 。 例 [S→a·Ad, #] :β 是 d ,所以 b ∈ FIRST(d#)={d} ,加入 [A→·c, d] 。…
  • LALR(1) 和 LR(1) 是什么关系:LALR(1) 把 LR(1) 里 核(去掉搜索符的项目集)相同 的状态合并,搜索符取并集,状态数和 LR(0) 一样少;能力介于 SLR(1) 与 LR(1) 之间。合并 不会产生新的移进-归约冲突 ,但 可能产生归约-归约冲突 。 例…
  • LR(0) 到 LR(1) 的包含关系:LR(0) ⊂ SLR(1) ⊂ LALR(1) ⊂ LR(1);LL(1) 文法也都是 LR(1) 文法。 区分 判定时依次往后试,哪一类表没有冲突就属于哪一类。 易错 二义文法不属于其中任何一类。
  • 二义文法能不能用 LR 分析:二义文法不是 LR(k) 文法,分析表必有冲突;但可以按优先级和结合性规定 人为消解冲突 后继续使用。 例 E→E+E | E*E | id ,状态里有 E→E+E· 和 E→E·*E :遇 * 选 移进 ( * 优先于 + );遇 + …

语义分析、中间代码和优化题

  • 综合属性和继承属性怎么区分:看信息往哪个方向传:综合属性是自底向上,继承属性是自上而下或横向。 区分 综合属性 由子结点(和自身)算出; 继承属性 由父结点或兄弟结点算出。 例 算术表达式的 E.val 是综合属性;声明 int a,b 中把类型传给 a、b 的 L…
  • S-属性文法和 L-属性文法有什么区别:S-属性文法 只含综合属性 ,可在 LR 归约时自底向上求值;L-属性文法中,产生式右部符号的继承属性只依赖父结点的继承属性和它左边兄弟的属性,适合边自顶向下分析边求值。 易错 S-属性文法是 L-属性文法的 特例 ,不是反过来。
  • 例:用综合属性求 3+4*2:规则: E → E1+T : E.val=E1.val+T.val ; E → T : E.val=T.val ; T → T1*F : T.val=T1.val*F.val ; T → F : T.val=F.val ; F → dig…
  • 例:继承属性怎样给变量填类型:规则: D→T L , T→int | real , L→L1, id | id ; L.in=T.type , L1.in=L.in ,并对每个 id 把类型 L.in 填入符号表。 例 int a, b : T.type=int , …
  • 语法制导定义和翻译方案有什么区别:区别在于有没有规定动作的位置:语法制导定义(SDD)只说明属性之间的关系,翻译方案(SDT)把语义动作 { } 嵌进产生式右部,明确执行顺序。 区分 SDD 给文法符号配 属性 、给产生式配 语义规则 ;SDT 的动作 放在右部哪个位置 …
  • 四元式、三元式有什么区别:四元式的结果有名字,三元式的结果用序号表示;间接三元式再加一张指令表。 区分 四元式 (op, arg1, arg2, result) ,结果放临时变量, 便于调整顺序 ;三元式 (op, arg1, arg2) ,结果用所在序号表示,省…
  • 例:写出 a=b*(c+d)−e 的中间代码:三地址码: t1=c+d , t2=b*t1 , t3=t2-e , a=t3 。 四元式 (+,c,d,t1) , (*,b,t1,t2) , (-,t2,e,t3) , (=,t3,-,a) 。 三元式 (1) (+,c,d) ,(2…
  • 后缀式(逆波兰)怎么写和求值:后缀式把运算符放在运算对象之后, 不需要括号 ;求值用栈:运算对象入栈,遇运算符弹出两个对象运算再入栈。 例 a*(b+c)-d/e 的后缀式是 abc+*de/- 。令 a=2,b=3,c=4,d=10,e=5:3+4=7,2 乘 7 …
  • 基本块的划分规则:先找出入口语句,再从每个入口划到下一个入口之前。 条件 三类入口:① 程序第一条语句;② 能被条件或无条件转移语句转到的语句;③ 紧跟在转移语句之后的语句。 易错 转移语句本身是它所在块的 最后一句 ,不是下一个块的入口。
  • 例:把 8 条语句划分成基本块:(1) s=0 ,(2) i=1 ,(3) if i>5 goto (8) ,(4) t=i*2 ,(5) s=s+t ,(6) i=i+1 ,(7) goto (3) ,(8) return s 。 入口 (1) 是第一条;(3) 是 …
  • 局部优化常用哪几种:常量折叠、公共子表达式删除、复制传播、死代码删除,四种都在基本块内做。 例 t=2*3.14 折叠成 t=6.28 ; x=a+b; y=a+b; z=x*y ,a、b 在其间没有被改:变成 x=a+b; y=x; z=x*y ,复制传播…
  • 基本块内的 DAG 怎样帮助优化:用 DAG 表示基本块里的运算:运算符和运算对象都相同的结点只建一个,所以 公共子表达式自然合并 ,结果变量作为这个结点的标记。 例 t1=a+b; t2=a+b; t3=t1*t2 : a+b 只建一个结点,标记 t1、t2;t3 是该…
  • 循环优化有哪几种:常见三种:代码外提、强度削弱、删除归纳变量。 例 循环内 t=a*b+i ,a、b 在循环中不被赋值, a*b 可 外提 到循环前只算一次;循环内 j=4*i ,i 每次加 1,可改为 j 每次加 4(强度削弱:乘法换加法)。 易错 外提…
  • 运行时存储有哪三种分配方式:静态分配、栈式分配、堆式分配三种。 区分 静态分配:编译时确定所有地址,不支持递归和大小可变的数据;栈式分配:调用时在栈上建活动记录,返回时撤销,支持递归;堆式分配:运行时按需申请、释放,用于动态数据结构。 易错 静态分配 不能 支持递归…
  • 活动记录里通常放什么:局部变量、形式参数、返回地址、 控制链 (指向调用者的活动记录)、 访问链 (嵌套过程访问非局部变量)、临时变量和返回值。 例 递归函数 f(3) 调用 f(2) 时,栈上有两个 f 的活动记录,各有自己的参数 n。
  • 传值和传地址有什么区别:传值是把实参的值复制给形参,改形参不影响实参;传地址是形参取得实参的地址,改形参就是改实参。 例 swap(x,y) 在函数里交换两个形参: 传值 调用后实参 x、y 不变; 传地址 调用后实参 x、y 互换。
  • 符号表的作用是什么:记录标识符的 名字、类型、作用域、存储地址 等信息,供语义检查(未声明、重复声明、类型匹配)和代码生成使用,常用哈希表实现。 易错 作用域嵌套时,进入作用域新建一层符号表(压栈),退出时撤销这一层(弹栈);查找从最内层向外层逐层进行。

本图由 SeekFlaw 编辑团队整理。发现错误,欢迎到学习论坛指出。

打开这张导图:点节点翻面看答案 →