【本复习内容供于个人专用，同学们还请仅供参考】 by：cyj
编译原理复习
1．① ∑
*
表示∑上的所有符号串的全体，空字 ε 也包括在其中。
例：若∑=则∑
*
=
若
*
，B
*
则 AB={abbb, abcca, abaac, acbb, accca, acaac, bcbb, bccca, bcaac}
规定
ε，含
*
称
*
是 V 的闭包。
记
+
=V
*
，称
+
是 V 的正规闭包(没有空集的闭包)，即如果没有
的叫做正规闭
包。
一个上下文无关文法 包括四个组成部分：
一组终结符号，一组非终结符号，一个开始符号，以及一组产生式。
是一个四元式
，其中
是一个非空有限集，它的每个元素称为终结符号；
是一个非空有限集，它的每个元素称为非终结符号；
是一个非终结符号，称为开始符号；
是一个产生式集合有限，每个产生式形式是 ，开始符号 至少必须在某个
产生式的左部出现一次。
若
表示：从
出发，经一步或若干步，可推导出
而
表示：从
出发，经 步或若干步，可推导出
即 ! 意味着，或者 !，或者或者 !
如果 ，则 是一个句型，仅含终结符号的句型是一个句子。
如："#"$" 是一个句子。
文法 所产生的句子的全体是一个语言，记为 L(G)。
例：一个文法 ：
%
它定义了一个什么样的语言呢？
解：ÞÞ
ÞÞÞ
&
&
&
ÞÞÞÞ
'(
% )
*第一，文法中不含任何下面形式的产生式：
因为，这种产生式除了引起二义性外没有任何用处。
第二，每个非终结符 必须都有用处： !
2．① 例：令∑=下面是∑上的正规式和相应的正规集：
正规式 正规集
*
上所有以 b 为首后跟任意多个 的字。
%
*
上所有以 a 为首的字。
%
*
%%
*
上所有含有两个相继的 a 或两个相继的 b 的字。
例：
*
+
不包含
%
*
= 和 只选一个
若两个正规式所表示的正规集相同，则认为二者等价。
例：
*
*
b
时间：08-11-23
1
P
26
Þ
+
Þ
+
P
46
*
Þ
*
Þ
*
Þ
*
Þ
