编译原理之三：文法和语言

　　语言和文法？语言我们知道，计算机语言，人类的语言，动物的语言，不同国家的语言，不同种族的语言等等。那神马是文法呢？所谓文法 ，文，文字，法，规则，法则，法律。组合起来就是，文字的规则。每种语言都有自己的文法，不同的语言有不同的文法。例如我们的中文的文法，用一种规则来定义句子的组成，还拿“我是中国人”为例。

 

　　我们的个中文句子构造规则：<主语><谓语><宾语><补语><状语>。  而英语的句子构造：S十V主谓结构 S十V十F主系表结构 S十V十O主谓宾结构 S十V十O1十O2 主谓双宾结构 S十V十O十C 主谓宾补结构 说明：S＝主语；V＝谓语；P＝表语；O＝宾 语；O1＝间接宾语；O2＝直接宾语；C＝宾语补足语。 我们可以看出汉语和英语有不同的编排，不同的规则，这就是 文法。 

         

　　我们这里要说的是编译程序的文法。

 

　　书中的文法定义：使用文法作为工具，不仅为了严格地定义句子的结构，也是为了适当条数的规则把语言的全部句子描述出来，可以说文法是以有穷集合刻画无穷集合的工具。

 

　　接下来了解一些关于表示文法的一些基本定义：

 

　　一些基本定义

 

　　符号和符号串：

　　正如我们学习的English是由单词和标点符号构成的，单词又是有字母构成的，计算机语言也是如此，也是由字母和数字等一些基本符号构成的，一个源程序就是一个“基本符号串”，所以我们开始了解符号和符号串相关的定义。

 

　　字母表：

　　元素的非空有穷集合。不同的语言有他自己不同的字母表，我们的计算机语言字母表就是 数字，字母，标点等若干符号了。中文的字母表就是汉字了。

 

　　符号串：

　　字母表的符号组成任何又穷序列的符号串。例如字母表A={a,b,c}则由这个字母表组成的符号串包括： {ab,ac,bc,abc,a,b,c}。

 有了这些就相当于有了123456，接下来就是一些运算了，符号串的一些运算了。

 

　　连接运算：

　　eg：x=bay=nana xy=banana （很简单，连接在一起）

 

　　方幂运算：

　　x^0= e  ; x^1 = x;.....;（和小学数学的方幂一致）

 

　　两个字母表乘积：

　　∑1={0,1}, ∑2={a,b},∑1∑2 ={0a,0b,1a,1b}；（小学数学结合运算）

 

　　∑的正闭包：

　　∑+=∑∪∑2∪∑3∪∑4∪……

 

　　∑的克林闭包（kleene Closure）：

　　∑*=∑0∪∑+ （与正闭包区别哦，这算是新概念）

　　例如：{0,1}+ = {0，1，00，01，11，000，001，010，011，100，……}

　　　　　{0,1}* = {ε，0，1，00，01，11，000，001，010，011，100，…}

  

 

　　我们用这些规则将我们的语言形式化：

 

　　“我是中国人”：名词:: =中国人；代词::= 我；动词::= 是；

　　编译程序的文法把计算机语言形式化的定义：A->b ;读作：A定义为b；或把他说成是一条关于A的规则（产生式）；

 

　　更加规范的定义：

　　文法G的定义：四元组(Vn，Vt，P，S) 

　　Vn：是非终结符集；

　　Vt：终结符集；

　　P：表示一种规则（a->b）ab表示终结符和非终结符的集合，但a中至少包括一个非终结符。Vn，Vt，P是非空有穷集合。

　　S：表示开始符，他是一个非终结符，至少要有一条规则在左侧。

  

　　那什么是终结符和非终结符呢？规则又是怎样？开始符？

　　下面来看一个英文句子，以英文句子为例，说说这个过程，幻灯片上的这个例子很适合初学者。

　　分析句子：The grey wolf will eat  the  goat .

 

 

　　句子的组成规则：