1. 编译程序的结构

编译程序通常划分哪几个阶段，每个阶段的主要功能是什么

词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成。

词法分析：对源程序字符串扫描分解，识别出单词符号。（拆分字符串）

语法分析：根据语言的语法规则对符号序列进行语法分析，识别出语法短语，判断语法是否正确。（识别短语，判断正确）

语义分析：对语法分析的结果分析语义错误，收集类型信息。（语义，类型）

中间代码生成：把源程序变成结构简单、含义明确、易生成目标代码的形式。

代码优化：对中间代码或目标代码进行变换改造等优化处理，提高效率。

目标代码生成：将语义分析结果或中间代码变成目标代码。（一般是汇编等）

把汇编语言程序翻译成机器可执行的目标程序的工作是由 ____ 完成的

汇编器

编译方式与解释方式的根本区别在于

编译方式先对源代码进行全面分析和优化后，生成一份高效的机器无关中间代码，再由后端转化为具体机器指令（目标代码），运行时无需源代码和解释器，直接执行机器码。

解释方式则在每个阶段（词法、语法、语义）都实时边读边处理、即时执行，灵活但效率较低。

编译程序的基本任务是翻译、出错处理和 ____

代码优化

2. 文法和语言

LR分析核心思想与“L”、“R”含义：

核心思想为“自底向上”归约，通过状态栈识别活前缀，依据ACTION表和GOTO表执行移进、归约或接受。

“L”指从左到右扫描输入串；“R”代表构造最右推导的逆过程，即规范归约，确保分析过程的准确性与高效性。

在规范归约中，用 ____ 来刻画可归约串。

句柄

自顶向下的语法分析方法遇到的主要问题是递归和 ____

回溯

Chomsky中3型文法又称 ____

正规文法 / 右线性文法。

什么是文法的二义性？文法二义性不可判别是什么原因？

文法中两个产生式存在相同的右部。（同一字符串可通过不同【推导/归约】【生成不同语法树/产生不同语义】）

归约为停机问题 -> 构造一个文法，如果它二义，就对应某个机器停机，否则对应无限循环。既然停机不可判，别的东西也不可能判。不可能100%正确且终止。

3. 词法分析

请构造与正规式R=(b|a)*a(b|a)*等价且状态数最少的DFA，要求写出构造过程。

详细解题

(1) 正规式

$$r = (a|b)^*\,a\,(a|b)^*$$

所求正规集是“至少含一个 $a$ 的所有 $a,b$ 串”。正规式要求串中出现 $a$ 且前后可为任意 $a,b$ 串。

(2) 构造 NFA

$Q=\{0,1,2\}$，$q_0=0$，$F=\{2\}$，$\delta$ 如下：

• $\delta(0,a)=\{0,1\}$，$\delta(0,b)=\{0\}$
• $\delta(1,a)=\{2\}$，$\delta(1,b)=\{2\}$
• $\delta(2,a)=\{2\}$，$\delta(2,b)=\{2\}$

起点 0 循环匹配 $(a|b)^*$；读入 $a$ 转到 1；1 再读一个字符到 2，2 循环匹配右侧 $(a|b)^*$。

(3) NFA 确定化为 DFA（子集构造法）

初始 $A=\varepsilon\text{-closure}(\{0\})=\{0\}$，逐个未标记状态对 $a$、$b$ 求 move 后的 $\varepsilon$-闭包：

状态集合	DFA 状态	经 $a$ 到达	经 $b$ 到达	含终态 2
$\{0\}$	$A$	$\{0,1\}\to B$	$\{0\}\to A$	否
$\{0,1\}$	$B$	$\{0,1,2\}\to C$	$\{0,2\}\to D$	否
$\{0,1,2\}$	$C$	$\{0,1,2\}\to C$	$\{0,2\}\to D$	是
$\{0,2\}$	$D$	$\{0,1,2\}\to C$	$\{0,2\}\to D$	是

DFA 转移图：

DFA 转移表：

DFA 状态	$a$	$b$
$\to A$	$B$	$A$
$B$	$C$	$D$
$*C$	$C$	$D$
$*D$	$C$	$D$

终态集 $F_{DFA}=\{C,D\}$。

(4) DFA 最小化（Hopcroft 划分法）

初始划分 $\Pi_0 = \{\{A,B\},\{C,D\}\}$（非终态、终态）。

考察 $\{A,B\}$：经 $a$，$A\to B\in\{A,B\}$，$B\to C\in\{C,D\}$ → 不等价，分裂为 $\{A\}$、$\{B\}$。

考察 $\{C,D\}$：经 $a$，$C\to C\in\{C,D\}$，$D\to C\in\{C,D\}$；经 $b$，$C\to D\in\{C,D\}$，$D\to D\in\{C,D\}$ → 等价，不可分裂。

最终划分 $\Pi=\{\{A\},\{B\},\{C,D\}\}$。将 $C,D$ 合并为状态 $C$。

最简 DFA（3 个状态）：

DFA 状态	$a$	$b$
$\to A$	$B$	$A$
$B$	$C$	$C$
$*C$	$C$	$C$

状态 A 表示”尚未读到 $a$“，B 表示”刚读到第一个 $a$“，C 表示”已完成至少一个 $a$“。该 DFA 等价于正规式 $(a|b)^*a(a|b)^*$，状态数 3 为最少。

例：设 $\Sigma=\{a,b\}$ 上的正规集 S 由倒数第二个字符为 $a$ 的所有字符串组成。

(1) 写出该正规集对应的正规式； (2) 根据正规式构造 NFA； (3) 将 NFA 确定化为 DFA； (4) 将 DFA 最小化，得到最简 DFA。

1. 写出对应正规式

思路：字符串长度至少为2，倒数第二个字符固定为a，其余位置字符任意。正规式为：$(a|b)^*a(a|b)$

2. 构造非确定有限自动机 (NFA)

思路：按正规式结构拆解，$(a|b)^*$用带自环的状态表示，经匹配a的转移后，再经匹配任意字符的转移到达终止状态，构建初始状态图。

详细解题

(1) 正规式

$$r = (a|b)^*\,a\,(a|b)$$

(2) 构造 NFA

$Q=\{0,1,2\}$，$q_0=0$，$F=\{2\}$，$\delta$ 如下：

• $\delta(0,a)=\{0,1\}$，$\delta(0,b)=\{0\}$
• $\delta(1,a)=\{2\}$，$\delta(1,b)=\{2\}$
• $\delta(2,\cdot)=\emptyset$

起点 0 可任意循环匹配 $(a|b)^*$；一旦读入 $a$ 转到 1（这一位即”倒数第二个字符为 a”），再读一个字符到终态 2。

(3) NFA 确定化为 DFA（子集构造法）

初始 $A=\varepsilon\text{-closure}(\{0\})=\{0\}$，逐个未标记状态对 $a$、$b$ 求 move 后的 $\varepsilon$-闭包：

状态集合	DFA 状态	经 $a$ 到达	经 $b$ 到达	含终态 2
$\{0\}$	$A$	$\{0,1\}\to$ 新 $B$	$\{0\}\to A$	否
$\{0,1\}$	$B$	$\{0,1,2\}\to$ 新 $C$	$\{0,2\}\to$ 新 $D$	否
$\{0,1,2\}$	$C$	$\{0,1,2\}\to C$	$\{0,2\}\to D$	是
$\{0,2\}$	$D$	$\{0,1,2\}\to C$	$\{0\}\to A$	是

DFA 转移图：

DFA 转移表：

DFA 状态	$a$	$b$
$\to A$	$B$	$A$
$B$	$C$	$D$
$*C$	$C$	$D$
$*D$	$C$	$A$

终态集 $F_{DFA}=\{C,D\}$。

(4) DFA 最小化（Hopcroft 划分法）

初始划分 $\Pi_0 = \{\{A,B\},\{C,D\}\}$（非终态、终态）。

考察 $\{A,B\}$：经 $a$，$A\to B\in\{A,B\}$，$B\to C\in\{C,D\}$ → 不等价，分裂为 $\{A\}$、$\{B\}$。

考察 $\{C,D\}$：经 $b$，$C\to D\in\{C,D\}$，$D\to A\in\{A\}$ → 不等价，分裂为 $\{C\}$、$\{D\}$。

最终划分 $\Pi=\{\{A\},\{B\},\{C\},\{D\}\}$，不可再分，DFA 已是最简（4 个状态，无冗余）。

4. 语法分析-自顶向下语法分析(LL(1))

请描述自顶向下的语法分析方法的基本思想

从文法开始符号（S）出发，逐个产生式展开直到匹配输入串的终结符符号（LL(1)文法通过FIRST/FOLLOW集预先预测，消去左递归和公因子后避免回溯）。

例：已知文法 $G[S]：S→aSBc | a; B→Bb | d$

(1)改写文法使其适合自顶向下分析，写出改写结果； (2)分别计算改写后文法的右部文法符号串的 FIRST 集和 非终结符的FOLLOW集； (3)判断该文法是否为LL(1)，若是，构造预测分析表；若不是，说明原因。

总结：LL(1)分析的关键在于预处理文法（消左递归、提公因子），并确保任意非终结符的SELECT集互不相交。

详细解题

(1) 改写文法

提取左公因子（$S\to aSBc$ 与 $S\to a$ 公因子为 $a$）：

$$S \to aS'\qquad S' \to SBc \mid \varepsilon$$

消除直接左递归（$B\to Bb\mid d$，引入 $B'$）：

$$B \to dB'\qquad B' \to bB' \mid \varepsilon$$

改写后文法 $G'$：

$$\begin{aligned} (1)&\ S \to aS' \\ (2)&\ S' \to SBc \\ (3)&\ S' \to \varepsilon \\ (4)&\ B \to dB' \\ (5)&\ B' \to bB' \\ (6)&\ B' \to \varepsilon \end{aligned}$$

(2) 计算 FIRST 与 FOLLOW 集

FIRST 集（自底向上）：

符号	FIRST	依据
$B'$	$\{b,\varepsilon\}$	$B'\to bB'$ 给 $b$；$B'\to\varepsilon$
$B$	$\{d\}$	$B\to dB'$，$d$ 为首终结符
$S$	$\{a\}$	$S\to aS'$
$S'$	$\{a,\varepsilon\}$	$S'\to SBc$，$FIRST(S)=\{a\}$；$S'\to\varepsilon$

右部串的 FIRST：

产生式右部	$FIRST$
$aS'$	$\{a\}$
$SBc$	$\{a\}$
$\varepsilon$	$\{\varepsilon\}$
$dB'$	$\{d\}$
$bB'$	$\{b\}$

FOLLOW 集（初始 $\#\in FOLLOW(S)$，反复传播至稳定）：

1. $S'\to SBc$：$FIRST(Bc)=\{d\}$（$B$ 非空），故 $d\in FOLLOW(S)$；$B$ 后跟 $c$，$c\in FOLLOW(B)$。
2. $S\to aS'$：$S'$ 在末尾，$FOLLOW(S)\subseteq FOLLOW(S')$。
3. $B\to dB'$：$B'$ 在末尾，$FOLLOW(B)\subseteq FOLLOW(B')$。
4. $B'\to bB'$：$B'$ 在末尾，自反无新信息。

迭代后稳定：

非终结符	FOLLOW
$S$	$\{\#,d\}$
$S'$	$\{\#,d\}$
$B$	$\{c\}$
$B'$	$\{c\}$

(3) SELECT 集与 LL(1) 判别、预测分析表

SELECT 集：

产生式	$FIRST$ 含 $\varepsilon$？	SELECT
$S\to aS'$	否	$\{a\}$
$S'\to SBc$	否	$\{a\}$
$S'\to\varepsilon$	是	$FOLLOW(S')=\{\#,d\}$
$B\to dB'$	否	$\{d\}$
$B'\to bB'$	否	$\{b\}$
$B'\to\varepsilon$	是	$FOLLOW(B')=\{c\}$

LL(1) 判别（同左部 SELECT 集相交）：

• $S'$：$\{a\}\cap\{\#,d\}=\emptyset$ ✓
• $B'$：$\{b\}\cap\{c\}=\emptyset$ ✓
• $S$、$B$ 各一个产生式，无冲突 ✓

该文法是 LL(1) 文法。

预测分析表 $M[A,a]$（$V_T=\{a,b,c,d,\#\}$）：

非终结符	$a$	$b$	$c$	$d$	$\#$
$S$	$S\to aS'$
$S'$	$S'\to SBc$		$S'\to\varepsilon$	$S'\to\varepsilon$	$S'\to\varepsilon$

说明：$S'\to\varepsilon$ 的 SELECT 集为 $\{\#,d\}$，故仅在 $d$、$\#$ 列填；$c$ 列为空，修正表如下。

非终结符	$a$	$b$	$c$	$d$	$\#$
$S$	$S\to aS'$
$S'$	$S'\to SBc$			$S'\to\varepsilon$	$S'\to\varepsilon$
$B$				$B\to dB'$
$B'$		$B'\to bB'$	$B'\to\varepsilon$

分析过程流图（以输入 $adbcbc\#$ 为例，展示归约式分析过程）：

5. 语法分析-算符优先文法分析

名词解释：句柄、素短语

句柄：最左直接短语。

素短语：句型中具有句法独立性且不可再分的最小短语结构。（去短语中找，并且要满足两条规则：1)包含终结符 2)除了他自身不能包含素短语）

例.给定文法 $G[E]$：

$$E → E+T|T; T → T*F|F; F → F↑P|P; P → (E) | I$$

(1)给出句型 $F↑P+T*(E+T)$ 的短语、直接短语、句柄、素短语、最左素短语。 (2)计算每个非终结符的 FIRSTVT 和 LASTVT 集，并据此构造算符优先关系表。 (3)对输入串 $i↑i+i* i$ 执行算符优先分析，写出分析过程（包括栈、输入串、动作）。

详细解题

(1) 句型 $F↑P+T*(E+T)$ 的短语、直接短语、句柄、素短语、最左素短语

语法树（最右推导 $E\Rightarrow E+T\Rightarrow E+T*F\Rightarrow E+T*(E)\Rightarrow E+T*(E+T)\Rightarrow F↑P+T*(E+T)$ 的逆过程）：

叶子自左向右：$F,\ \uparrow,\ P,\ +,\ T,\ *,\ (,\ E,\ +,\ T,\ )$。

短语集合（每棵子树叶节点串）：

短语	来自子树
$F$	子叶 $F$（父 $F\to F↑P$ 的左子）
$P$	子叶 $P$（$↑$ 右子）
$F↑P$	$F\to F↑P$
第一个 $T$	叶 $T$ 自身
括号内 $E$、$T$	子叶
$E+T$	$E\to E+T$（括号内）
$(E+T)$	$P\to(E)$
$T*(E+T)$	$T\to T*F$
$F↑P+T*(E+T)$	根 $E$ 整棵树

直接短语（子树高度为 1，父节点一步推出该叶子串）：

直接短语	单步归约依据
$F$	叶 $F$，其父直接派生
$P$	叶 $P$
$E+T$	$E\to E+T$ 单步
$(E+T)$	$P\to(E)$ 单步

注：$F↑P$ 需 $F\to F↑P$ 后叶子 $P$ 再由 $P\to i$ 派生，高度 > 1，不是直接短语；$T*(E+T)$ 同理。

句柄 = 最左直接短语：最左叶子是 $F$，对应的直接短语即 $F$。

素短语（含至少一个终结符，且不含其他素短语的短语）：

• $F↑P$：含 $\uparrow$，内部 $F$、$P$ 不含终结符 → 素短语 ✓
• $E+T$：含 $+$，内部 $E$、$T$ 不含终结符 → 素短语 ✓
• $(E+T)$：含子短语 $E+T$（已含终结符）→ 不素
• $T*(E+T)$、整句：含子素短语 → 不素

素短语集合：$\{F↑P,\ E+T\}$

最左素短语：最左的素短语 → $F↑P$（位置 1–3）。

结果汇总：

项	结果
短语	$F,\ P,\ F↑P,\ T,\ E+T,\ (E+T),\ T*(E+T),\ F↑P+T*(E+T)$
直接短语	$F,\ P,\ E+T,\ (E+T)$
句柄	$F$
素短语	$F↑P,\ E+T$
最左素短语	$F↑P$

(2) FIRSTVT、LASTVT 集与算符优先关系表

FIRSTVT 集（规则：$A\to a\cdots$ 或 $A\to Ba\cdots$ 给 $a$；$A\to B\cdots$ 继承 $FIRSTVT(B)$）：

非终结符	FIRSTVT	依据
$P$	$\{(,\ i\}$	$P\to(\cdots$，$P\to i$
$F$	$\{\uparrow,\ (,\ i\}$	$F\to F↑P$ 给 $\uparrow$；$F\to P$ 继承 $FIRSTVT(P)$
$T$	$\{*,\ \uparrow,\ (,\ i\}$	$T\to T*F$ 给 $*$；$T\to F$ 继承 $FIRSTVT(F)$
$E$	$\{+,\ *,\ \uparrow,\ (,\ i\}$	$E\to E+T$ 给 $+$；$E\to T$ 继承 $FIRSTVT(T)$

LASTVT 集（规则：$A\to\cdots a$ 或 $A\to\cdots aB$ 给 $a$；$A\to\cdots B$ 继承 $LASTVT(B)$）：

非终结符	LASTVT	依据
$P$	$\{),\ i\}$	$P\to(\cdots)$ 给 $)$；$P\to i$
$F$	$\{\uparrow,\ ),\ i\}$	$F\to F↑P$ 给 $\uparrow$；$F\to P$ 继承 $LASTVT(P)$
$T$	$\{*,\ \uparrow,\ ),\ i\}$	$T\to T*F$ 给 $*$；$T\to F$ 继承 $LASTVT(F)$
$E$	$\{+,\ *,\ \uparrow,\ ),\ i\}$	$E\to E+T$ 给 $+$；$E\to T$ 继承 $LASTVT(T)$

$\doteq$ 关系（产生式右部相邻终结符）：

• $P\to(E)$ → $( \doteq )$

$\lessdot$ 关系（$A\to\cdots aB\cdots$，$b\in FIRSTVT(B)$ → $a\lessdot b$）：

产生式	$a$	$B$	$b\in FIRSTVT(B)$	关系
$E\to E+T$	$+$	$T$	$\{*,\uparrow,(,i\}$	$+\lessdot *$, $\uparrow$, $($, $i$
$T\to T*F$	$*$	$F$	$\{\uparrow,(,i\}$	$*\lessdot \uparrow$, $($, $i$
$F\to F↑P$	$\uparrow$	$P$	$\{(,i\}$	$\uparrow\lessdot ($, $i$
$P\to(E)$	$($	$E$	$\{+,\ *,\uparrow,(,i\}$	$(\lessdot+,\ *,\uparrow,(,i$
句括号	$\#$	$E$	$\{+,\ *,\uparrow,(,i\}$	$\#\lessdot+,\ *,\uparrow,(,i$

$\gtrdot$ 关系（$A\to\cdots Bb\cdots$，$a\in LASTVT(B)$ → $a\gtrdot b$）：

产生式	$B$	$b$	$a\in LASTVT(B)$	关系
$E\to E+T$	$E$	$+$	$\{+,\ *,\uparrow,),i\}$	$+,\ *,\uparrow,),i\gtrdot +$
$T\to T*F$	$T$	$*$	$\{*,\ \uparrow,),i\}$	$*,\ \uparrow,),i\gtrdot *$
$F\to F↑P$	$F$	$\uparrow$	$\{\uparrow,\ ),i\}$	$\uparrow,),i\gtrdot\uparrow$（$\uparrow\gtrdot\uparrow$ 表右结合）
$P\to(E)$	$E$	$)$	$\{+,\ *,\uparrow,),i\}$	$+,\ *,\uparrow,),i\gtrdot)$
句括号	$E$	$\#$	$\{+,\ *,\uparrow,),i\}$	$+,\ *,\uparrow,),i\gtrdot\#$

算符优先关系表：

	$+$	$*$	$\uparrow$	$($	$)$	$i$	$\#$
$+$	$\gtrdot$	$\lessdot$	$\lessdot$	$\lessdot$	$\gtrdot$	$\lessdot$	$\gtrdot$
$*$	$\gtrdot$	$\gtrdot$	$\lessdot$	$\lessdot$	$\gtrdot$	$\lessdot$	$\gtrdot$
$\uparrow$	$\gtrdot$	$\gtrdot$	$\gtrdot$	$\lessdot$	$\gtrdot$	$\lessdot$	$\gtrdot$
$($	$\lessdot$	$\lessdot$	$\lessdot$	$\lessdot$	$\doteq$	$\lessdot$
$)$	$\gtrdot$	$\gtrdot$	$\gtrdot$		$\gtrdot$		$\gtrdot$
$i$	$\gtrdot$	$\gtrdot$	$\gtrdot$		$\gtrdot$		$\gtrdot$
$\#$	$\lessdot$	$\lessdot$	$\lessdot$	$\lessdot$		$\lessdot$	$\doteq$

说明：$\uparrow\gtrdot\uparrow$ 体现幂运算右结合。

(3) 对 $i↑i+i*i$ 的算符优先分析过程

栈底 $\#$，输入 $i↑i+i*i\#$。比较栈顶终结符 $a$ 与当前输入 $b$ 的优先关系：$\gtrdot$ 触发归约（找最左素短语），$\lessdot$ 或 $\doteq$ 移进。归约结果统一记为非终结符 $N$（不关心具体名）。

步骤	符号栈	当前输入串	关系（栈顶终结符 vs 输入）	动作
1	$\#$	$i↑i+i*i\#$	$\#\lessdot i$	移进 $i$
2	$\#i$	$↑i+i*i\#$	$i\gtrdot ↑$	归约 $i\to N$
3	$\#N$	$↑i+i*i\#$	$\#\lessdot ↑$	移进 $↑$
4	$\#N↑$	$i+i*i\#$	$↑\lessdot i$	移进 $i$
5	$\#N↑i$	$+i*i\#$	$i\gtrdot +$	归约 $i\to N$
6	$\#N↑N$	$+i*i\#$	$↑\gtrdot +$	归约 $N↑N\to N$
7	$\#N$	$+i*i\#$	$\#\lessdot +$	移进 $+$
8	$\#N+$	$i*i\#$	$+\lessdot i$	移进 $i$
9	$\#N+i$	$*i\#$	$i\gtrdot *$	归约 $i\to N$
10	$\#N+N$	$*i\#$	$+\lessdot *$	移进 $*$
11	$\#N+N*$	$i\#$	$*\lessdot i$	移进 $i$
12	$\#N+N*i$	$\#$	$i\gtrdot \#$	归约 $i\to N$
13	$\#N+N*N$	$\#$	$*\gtrdot \#$	归约 $N*N\to N$
14	$\#N+N$	$\#$	$+\gtrdot \#$	归约 $N+N\to N$
15	$\#N$	$\#$	$\#\doteq \#$	接受

分析过程示意：

6. 语法分析 - LR分析

LR分析器与优先关系分析器在识别句柄时的主要异同是什么？

相同点：

两类分析器均通过扫描输入串、维护栈和输入指针（或状态），结合文法规则（或表）逐步推进，依次识别终结符句柄（handle）以规约。

不同点：

• 驱动方式：LR使用自底向上DFA（LR(0)/LR(1)/LALR等），优先关系使用LL(1)预测表或预测函数，驱动策略不同（LR依赖goto表，优先依赖预测表）。
• 识别过程：LR识别单个句柄，优先关系可识别多个/单个（LL中先看FIRST集）。
• 文法支持：LR支持左递归，优先关系不支持。
• 构造复杂度：LR表构造更复杂，优先关系更简单。

例. 已知文法 G 如下：

0. $S' \to S$;
1. $S \to E$;
2. $E \to E+T$;
3. $E \to T$;
4. $T \to T*F$;
5. $T \to F$;
6. $F \to (E)$;
7. $F \to i$;

(1) 画出识别该文法所有活前缀的 LR(1) 项目集规范族 (DFA)。 (2) 构造 LR(1) 分析表（要求给出 ACTION 和 GOTO 表）。 (3) 给出输入串 $i+i*i$ 的分析过程（要求列出栈、输入、动作）。

详细解题

本文法的 LR(1) 项目核心（同心部分）与材料 6.10 节 SLR(1) 的 DFA 结构相同，但每个归约项目携带状态相关的向前看符号，而非全局 FOLLOW 集。为便于作图，下面先给出与 SLR(1) 同心的 LR(0) 骨架 DFA，再在 (2) 的分析表中以 LR(1) 向前看符号决定归约栏。

(1) LR(1) 项目集规范族（DFA）

LR(1) 项目形如 $[A\to\alpha\cdot\beta,\ a]$，闭包：若 $[A\to\alpha\cdot B\beta,\ a]\in I$，加入 $[B\to\cdot\gamma,\ b]$，$b\in FIRST(\beta a)$。

核心项目集（圆点结构与 SLR 的 $I_0$–$I_{11}$ 同心，列出关键状态及向前看符号）：

状态	LR(1) 项目集（向前看符号标于末尾）
$I_0$	$[S'\to\cdot S,\#]$；$[S\to\cdot E,\#]$；$[E\to\cdot E+T,\#]$、$[E\to\cdot E+T,+]$；$[E\to\cdot T,\#]$、$[E\to\cdot T,+]$；$[T\to\cdot T*F,\#]$、$[.,+]$、$[.,*]$；$[T\to\cdot F,\#]$、$[.,+]$、$[.,*]$；$[F\to\cdot(E),\#]$、$[.,+]$、$[.,*]$；$[F\to\cdot i,\#]$、$[.,+]$、$[.,*]$
$I_1$	$[S'\to S\cdot,\#]$（接受）
$I_2$	$[S\to E\cdot,\#]$；$[E\to E\cdot+T,\#]$、$[E\to E\cdot+T,+]$
$I_3$	$[E\to T\cdot,\#]$、$[E\to T\cdot,+]$；$[T\to T\cdot*F,\#]$、$[.,+]$、$[.,*]$
$I_4$	$[T\to F\cdot,\#]$、$[.,+]$、$[.,*]$
$I_5$	$[F\to(\cdot E),\#]$、$[.,+]$、$[.,*]$（闭包后同 $I_0$ 结构，但带向前看 $\{),+,*\}$）
$I_6$	$[F\to i\cdot,\#]$、$[.,+]$、$[.,*]$（归约 $r_7$）
$I_7$	$[E\to E+\cdot T,\#]$、$[.,+]$（闭包后 $T,F,(,i$ 带 $\{\#,+,*\}$）
$I_8$	$[T\to T*\cdot F,\#]$、$[.,+]$、$[.,*]$（闭包后 $F,(,i$ 带 $\{\#,+,*\}$）
$I_9$	$[F\to(E\cdot),\#]$、$[.,+]$、$[.,*]$；$[E\to E\cdot+T,)]$、$[E\to E\cdot+T,+]$
$I_{10}$	$[E\to T\cdot,)]$、$[.,+]$；$[T\to T\cdot*F,)]$、$[.,+]$、$[.,*]$
$I_{11}$	$[T\to F\cdot,)]$、$[.,+]$、$[.,*]$

$I_5,I_7,I_8$ 经 $(\ ,\ i$ 等 GOTO 后会产生与上述状态 同心 但向前看符号不同的新状态。整体结构与 SLR(1) 的 DFA 同心。

DFA 转移图（同心骨架，标注圆点后读入的符号）：

注：$I_5, I_7, I_8$ 各自经 $($ 和 $i$ 的 GOTO 指向同心状态（与 $I_5, I_6$ 同心但局部向前看符号不同）。上图为同心骨架示意。

(2) LR(1) 分析表

由 LR(1) 项目集族填表：归约仅在该状态存在 $[A\to\alpha\cdot,\ a]$ 且当前输入为 $a$ 时执行。

状态	$i$	$+$	$*$	$($	$)$	$\#$	$S$	$E$	$T$	$F$
0	$S_6$			$S_5$			1	2	3	4
1						acc
2		$S_7$				$r_1$
3		$r_3$	$S_8$			$r_3$
4		$r_5$	$r_5$			$r_5$
5	$S_6$			$S_5$				9	10	11
6		$r_7$	$r_7$			$r_7$
7	$S_6$			$S_5$					10	11
8	$S_6$			$S_5$						11
9		$S_7$			$S_{11}'$
10		$r_3$	$S_8$		$r_3$
11		$r_5$	$r_5$		$r_5$

说明：

• 状态 2 含 $[S\to E\cdot,\#]$ ⟹ 仅 $\#$ 列归约 $r_1$；含 $[E\to E\cdot+T]$ ⟹ $+$ 移进。LR(1) 精确到状态，无冲突。
• 状态 9 的 $)$ 项应为归约 $r_6$（由 $F\to(E)\cdot$ 在括号上下文中以 $)$ 为向前看符号触发），表示为 $r_6$（修正下表）。
• 状态 4、11 等归约 $r_5$（$T\to F$）。
• 状态 6 归约 $r_7$（$F\to i$）。
• GOTO 列：状态 0 行 $S=1,E=2,T=3,F=4$；状态 5 行 $E=9,T=10,F=11$；状态 7 行 $T=10,F=11$；状态 8 行 $F=11$。

修正后的 LR(1) 分析表：

状态	$i$	$+$	$*$	$($	$)$	$\#$	$S$	$E$	$T$	$F$
0	$S_6$			$S_5$			1	2	3	4
1						acc
2		$S_7$				$r_1$
3		$r_3$	$S_8$			$r_3$
4		$r_5$	$r_5$			$r_5$
5	$S_6$			$S_5$				9	10	11
6		$r_7$	$r_7$			$r_7$
7	$S_6$			$S_5$					10	11
8	$S_6$			$S_5$						11
9		$S_7$			$r_6$
10		$r_3$	$S_8$		$r_3$
11		$r_5$	$r_5$		$r_5$

产生式编号：$r_1:S\to E$，$r_2:E\to E+T$，$r_3:E\to T$，$r_4:T\to T*F$，$r_5:T\to F$，$r_6:F\to(E)$，$r_7:F\to i$。 状态 14（对应 $E\to E+\cdot T$ 经 $T$ 后）含 $[E\to E+T\cdot,\#]$，$\#$ 归约 $r_2$，$*$ 移进 — 与状态 9 同心但向前看不同。表中状态 9 对应括号内 $E$ 已归约的场景（$)$归约 $r_6$、$*$? 实际 $I_9$ 不含 $*$ 移进）。上表已据同心 DFA 简化。

(3) 输入串 $i+i*i$ 的分析过程

利用 LR(1) 分析表（与材料 6.9 节 SLR(1) 分析过程动作相同，因本文法对应部分动作一致）：

步骤	状态栈	符号栈	输入串	ACTION	GOTO
(1)	0	$\#$	$i+i*i\#$	$S_6$
(2)	06	$\#i$	$+i*i\#$	$r_7$	4
(3)	04	$\#F$	$+i*i\#$	$r_5$	3
(4)	03	$\#T$	$+i*i\#$	$r_3$	2
(5)	02	$\#E$	$+i*i\#$	$S_7$
(6)	027	$\#E+$	$i*i\#$	$S_6$
(7)	0276	$\#E+i$	$*i\#$	$r_7$	11
(8)	027(11)	$\#E+F$	$*i\#$	$r_5$	10
(9)	027(10)	$\#E+T$	$*i\#$	$S_8$
(10)	027(10)8	$\#E+T*$	$i\#$	$S_6$
(11)	027(10)86	$\#E+T*i$	$\#$	$r_7$	11
(12)	027(10)8(11)	$\#E+T*F$	$\#$	$r_4$	10
(13)	027(10)	$\#E+T$	$\#$	$r_2$	2
(14)	02	$\#E$	$\#$	$r_1$	1
(15)	01	$\#S$	$\#$	acc

关键步骤解析：

• (2) $r_7$：状态 6 含 $[F\to i\cdot,\{+,*,\#\}]$，输入 $+\in\{+,*,\#\}$ ⟹ 归约 $F\to i$。弹出 1 个状态（6）和 1 个符号（$i$），栈顶状态 0，左部 $F$ 查 GOTO[0,F]=4 ⟹ 压 $F$ 和 4。
• (3) $r_5$：状态 4 含 $[T\to F\cdot,\{\#,+,*\}]$ ⟹ 归约 $T\to F$，GOTO[0,T]=3。
• (4) $r_3$：状态 3 含 $[E\to T\cdot,\{\#,+\}]$，输入 $+\in\{\#,+\}$ ⟹ 归约 $E\to T$，GOTO[0,E]=2。
• (5) $S_7$：状态 2 含 $[E\to E\cdot+T]$，输入 $+$ ⟹ 移进到 $I_7$。
• (13) $r_2$：状态（同心 $I_9$ 对应的 $E+T$ 归约态）含 $[E\to E+T\cdot,\#]$，输入 $\#$ ⟹ 归约 $E\to E+T$（弹出 3 个状态和 $+T$ 三符号），栈顶状态 0，GOTO[0,E]=2。
• (14) $r_1$：状态 2 含 $[S\to E\cdot,\#]$，输入 $\#$ ⟹ 归约 $S\to E$，GOTO[0,S]=1。
• (15) acc：状态 1 含 $[S'\to S\cdot,\#]$，输入 $\#$ ⟹ 接受。

LR(1) 比 SLR(1) 更精细：归约向前看符号是 项目自身携带的状态相关向前看集合 ，而非全局 FOLLOW 集，能区分“括号内归约（向前看含 $)$）”与“顶层归约（向前看含 $\#$）”。输入串 $i+i*i$ 被成功分析，是该 LR(1) 文法的句子。

分析过程流图：