编译原理之文法一

一、先简单介绍一下形式语言基本知识

 

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……，可以被拆分