编译原理之文法一
一、先简单介绍一下形式语言基本知识
?
1、字母表：符号的非空有限集合称为字母表
?
2、符号串：由某一字母表中的符号组成的有限符号序列称为该字母表的符号串
?
二、非形式化的语言：
?
①语言L和M的合并，LUM={s|s∈L或?s∈M}
?
②语言L和M的连接，LM={st|s∈L，t∈M}
③语言L的Kleene闭包，L*= ? ??
④语言L的正闭包，L+= ? ??
解释：
前面①，②都很好理解，关于③和④，这里说明一下。
③：
集合?L?的第 i 次幂是集合 L 同自身的 i 次串接的简写。即，Li??可以被理解成由 L 中的符号形成的所有长度为 i 的字符串的集合。
?L?= ?{"ab", "c"}
?L0?= ?{ε}
?L1?= ?{?"c"}（由L中符号形成的所有长度为1的字符串的集合）
?L2?={"ab"}?，{"cc"}（由L中符号形成的所有长度为2的字符串的集合）等等
?
由此，Kleene 星号应用于字符串集合的例子：
?L*?= ?{"ab", "c"}* = ? ???
?
={ε}∪{?"c"}∪{"ab"}?∪{"cc"}∪{"abc"}?∪{"cab"}∪{"ccc"}∪{"abcc"}∪{"abab"}∪{"cabc"}∪{?"ccab"}∪{"ababc"}∪{"abcab"}∪{"cabab"}∪{"ababab"}∪……}
={ε,?"c",?"ab","cc",??"abc","cab",??"ccc","abab",??"cabc", "ccab",?"abcc",??"ababc", "abcab","cabab",?"ababab",……}
同理，Kleene 星号应用于字符集合的例子：
{'a', 'b', 'c'}* = {ε, "a", "b", "c", "aa", "ab", "ac", "ba", "bb", "bc", ...}
?
④：
和③类似，只不过④中没有?L0?= ?{ε}
更多参见：http://zh.wikipedia.org/wiki/Kleene%E9%97%AD%E5%8C%85
三、文法(Grammar)：
?
G={VT，VN，S，P}
?
VT是一个非空有限的符号集合，它的每个元素称为终结符号（Terminal）
?
VN是一个非空有限的符号集合，它的每个元素称为非终结符号（Non-Terminal）
?
S∈VN，称为文法G的开始符号
?
P是一个非空有限集合，它的元素称为产生式。
?
VT∩VN=?
?
产生式，其形式为α→β，α称为产生式的左部，β称为产生式的右部，符号“→”表示“定义为”，并且α、β∈(VT∪VN)*，α≠ε，即α、β是由终结符和非终结符组成的符号串。
开始符S必须至少在某一产生式的左部出现一次。
另外可以对形式α→β，α→γ的产生式缩写为α→β|γ，以方便书写。
?
解释：
(VT∪VN)?*：也就是VT∪VN的Kleene闭包
α≠ε：α不等于空符号串
?
用小写字母代表终结符，如：abc……，不能被拆分
用大写字母代表非终结符，如：ASBX……，可以被拆分
