编译原理基础

文法与语言描述

二型文法式子左边必须是非终结符，式子右边可以有多个字符。

给出生成下述语言的上下文无关文法（II 型）：
$L (G) = {a^{n} b^{n} a^{m} b^{m} | n, m \geq 0}$

$G (S) : S \rarr A A A \rarr a A b | ϵ$

三型文法式子左边只能有一个字符，而且必须是非终结符；式子右边最多有两个字符。如果有两个字符必须是终结符 + 非终结符的格式，如果是一个字符，那么必须是终结符。

给出生成下述语言的正规文法（III 型）：
$L (G) = {a^{n} b^{m} | n, m \geq 1}$

$G (S) : S \rarr a A | b B A \rarr a A | b B | ϵ B \rarr b B | ϵ$

文法 $G (S) : S \rarr d A B A \rarr a A | ϵ B \rarr B b | ϵ$ 描述的语言 $L (G)$ 是什么？

$L (G) = {d a^{n} b^{m} | n > 0, m \geq 0}$

写一文法，使其语言是偶正整数的集合，要求不允许 0 开头。

$G (S) : S \rarr B (A | B | C)^{*} A \rarr 1 | 3 | 5 | 7 | 9 B \rarr 2 | 4 | 6 | 8 C \rarr 0$

句柄是直接短语中的，位居图最左的一个短语。

已知 $G (S) : E \rarr T | E + T T \rarr F | T * F F \rarr (E) | i$ ，试给出表达式 $i + (i + i)$ 的规范推导及语法树，并给出其短语、直接短语、句柄。

$E \Rarr E + T \Rarr E + F \Rarr E + (E) \Rarr E + (E + T) \Rarr E + (E + F) \Rarr E + (E + i) \Rarr E + (T + i) \Rarr E + (F + i) \Rarr E + (i + i) \Rarr T + (i + i) \Rarr F + (i + i) \Rarr i + (i + i)$

短语： $i_{1} 、 i_{2} 、 i_{3} 、 i_{2} + i_{3} 、 (i_{2} + i_{3}) 、 i_{1} + (i_{2} + i_{3})$

直接短语： $i_{1} 、 i_{2} 、 i_{3}$

句柄： $i_{1}$

正规式、NFA 与 DFA

设计一个 DFA，识别 $R = (a^{*} b)^{*} b a$ 的描述的正规集合。
构造该正规式所对应的 NFA；
将所求的 NFA 确定化；
将所求的 DFA 最小化。

DFA 转 NFA 主要靠“闭包 a”法（先取输入能到达的集合，再取空串能到达的集合，两结果合并）。

$I$ $I_{a}$ $I_{b}$
[S,A,B,G,F] [G,F] [A,B,C,G,F]
[G,F] [G,F] [A,B,G,F]
[A,B,C,G,F] [F,G,Z] [A,B,C,G,F]
[A,B,G,F] [G,F] [A,B,C,G,F]
[F,G,Z] [G,F] [A,B,G,F]
先将终态和非终态分成两个集： $K_{1} = {1, 2, 3, 4}$ ， $K_{2} = {5}$ 对于 $K_{1}$ 中的 3 态输入 a 则进入 $K_{2}$ 集，而 1、2、4 态输入 a 仍然在 $K_{1}$ 中，故 $K_{1}$ 可一分为二 $K_{11} = {1, 2, 4}$ 和 $K_{12} = {3}$ ；考察 $K_{11}$ 对于 1、4 态输入 b 到达 3 态而 2 态输入 b 到达 4 态。故 $K_{11}$ 可一分为二 $K_{111} = {1, 4}$ ， $K_{112} = {2}$ 。
其状态图如下：

$I$	$I_{a}$	$I_{b}$
[S,A,B,G,F]	[G,F]	[A,B,C,G,F]
[G,F]	[G,F]	[A,B,G,F]
[A,B,C,G,F]	[F,G,Z]	[A,B,C,G,F]
[A,B,G,F]	[G,F]	[A,B,C,G,F]
[F,G,Z]	[G,F]	[A,B,G,F]

LL(1) 文法

已知文法 $G (S) : S \rarr S + a F | a F | + a F F \rarr * a F | * a$ ，求：
消除左递归和回溯；
构造 FIRST、FOLLOW、SELECT 集合；
判断其是否是 LL(1) 文法；
构造 LL(1) 文法分析表；
分析 +a*a 是否是文法的句子。

$G (S) : S \rarr a F S | + a F S^{'} S^{'} \rarr + a F S^{'} | ϵ F \rarr * a F^{'} F^{'} \rarr F | ϵ$

First 元素即取右部的第一个终结字符；Follow 元素指的是左部符号在全局任意右部之后的终结字符，而不是 First 元素之后的元素；Select 元素指的是推导式中左部能推出的全部起始符号，如果右部为空则指向左部的 Follow 集合与右部的 First 集合（去掉空串）的并集。

$F I R S T (S) = {a, +} F I R S T (S^{'}) = {+, ϵ} F I R S T (F) = {*} F I R S T (F^{'}) = {*, ϵ}$
$F O L L O W (S) = {#} F O L L O W (S^{'}) = {#} F O L L O W (F) = {+, #} F O L L O W (F^{'}) = {+, #}$
$S E L E C T (S \rarr a F S^{'}) = {a} S E L E C T (S \rarr + a F S^{'}) = {+} S E L E C T (S^{'} \rarr + a F S^{'}) = {+} S E L E C T (S^{'} \rarr ϵ) = {#} S E L E C T (F \rarr * a F^{'}) = {*} S E L E C T (F^{'} \rarr F) = {*} S E L E C T (F^{'} \rarr ϵ) = {+, #}$
因为 ${a} \cap {+} = \empty$ 、 ${+} \cap {#} = \empty$ 、 ${*} \cap {+, #} = \empty$ ，故该文法是 LL(1) 文法。
预测分析表为：
a + * #
S $S \rarr a F S^{'}$ $S \rarr + a F S^{'}$
S' $S^{'} \rarr + a F S^{'}$ $S^{'} \rarr ϵ$
F $F \rarr * a F^{'}$
F' $F^{'} \rarr ϵ$ $F^{'} \rarr F$ $F^{'} \rarr ϵ$
符号串 +a*a 是否为句子的分析过程：
步骤符号栈 S 输入串规则
1 $# S$ +a*a# $S \rarr + a F S^{'}$
2 $# S^{'} F a +$ +a*a# 匹配
3 $# S^{'} F$ *a# $F \rarr * a F^{'}$
4 $# S^{'} F^{'} a *$ *a# 匹配
5 $# S^{'} F^{'}$ # $F^{'} \rarr ϵ$ ， $S^{'} \rarr ϵ$
5 $#$ # 成功，STOP

	a	+	*	#
S	$S \rarr a F S^{'}$	$S \rarr + a F S^{'}$
S'		$S^{'} \rarr + a F S^{'}$		$S^{'} \rarr ϵ$
F			$F \rarr * a F^{'}$
F'		$F^{'} \rarr ϵ$	$F^{'} \rarr F$	$F^{'} \rarr ϵ$

步骤	符号栈 S	输入串	规则
1	$# S$	+a*a#	$S \rarr + a F S^{'}$
2	$# S^{'} F a +$	+a*a#	匹配
3	$# S^{'} F$	*a#	$F \rarr * a F^{'}$
4	$# S^{'} F^{'} a *$	*a#	匹配
5	$# S^{'} F^{'}$	#	$F^{'} \rarr ϵ$ ， $S^{'} \rarr ϵ$
5	$#$	#	成功，STOP

LR(0) 与 SLR(1) 文法

给定文法 $G (A) : A \rarr a A d | a A b | ϵ$ ，
判断该文法是否是 SLR(1) 文法；
若是，则构造其分析表；
对输入串 ab 进行分析。

拓广文法：
$G (A) : A^{'} \rarr A (0) A \rarr a A d (1) A \rarr a A b (2) A \rarr ϵ (3)$
构造识别该文法所有规范句型活前缀的 DFA：
发现 $I_{2}$ 存在移进-规约冲突。
因 $F I R S T (A) = {a, ϵ} F O L L O W (A) = {d, b, #}$ ，故 $F O L L O W (A) \cap {a} = \empty$ ，是 SLR(1) 文法。