编译原理之文法一

时间:2021-04-29 03:55:54

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


1、字母表:符号的非空有限集合称为字母表


2、符号串:由某一字母表中的符号组成的有限符号序列称为该字母表的符号串


二、非形式化的语言:

 

①语言LM合并LUM={s|sL sM}

 

②语言LM连接LM={st|sLtM}

③语言LKleene闭包L*=     编译原理之文法一

④语言L正闭包L+=     编译原理之文法一


解释:


前面①,②都很好理解,关于③和④,这里说明一下。


③:

集合 的第 i 次幂是集合 L 同自身的 i 次串接的简写。即,L 可以被理解成由 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={VTVNSP}

 

VT是一个非空有限的符号集合,它的每个元素称为终结符号Terminal

 

VN是一个非空有限的符号集合,它的每个元素称为非终结符号(Non-Terminal

 

SVN,称为文法G开始符号

 

P是一个非空有限集合,它的元素称为产生式

 

VTVN=∅


产生式,其形式为αβα称为产生式的左部,β称为产生式的右部,符号“→”表示“定义为”,并且αβ∈(VTVN) *αε,即αβ是由终结符和非终结符组成的符号串。

开始符S必须至少在某一产生式的左部出现一次。

另外可以对形式αβαγ的产生式缩写为αβ|γ,以方便书写。

 

解释:

(VTVN) *:也就是VTVNKleene闭包

αεα不等于空符号串

用小写字母代表终结符,如:abc……,不能被拆分

用大写字母代表非终结符,如:ASBX……,可以被拆分


续:http://blog.csdn.net/wulingmin21/article/details/7485645