编译原理-第2部分形式语言导论-第二节文法和语言-第一小节文法和语言的概念（文法）

    上一讲述的是“语言”的概念，这一篇和大家分享的是“文法”的概念。分享完文法的概念之后，会给大家三个例子，帮助我们来更好地理解“文法”这个抽象的概念。

 文法通常表示成四元组G=(，，S，ξ)，其中：

(1) 为终结符号集，这是一个非空有限集，它的每个元素称为终结符号；

(2) 为非终结符集，它也是一个非空有限集，其每个元素称为非终结符号，且有∩=Φ；

(3) S为一文法开始符，是一个特殊的非终结符号，即S∈；

(4) ξ是产生式的非空有限集，其中每个产生式(或称规则)是一序偶(α，β)，通常写作

                      α→β或α::=β

    读作“α是β”或“α定义为β”。在此，α为产生式的左部，而β为产生式的右部，α、β是由终结符和非终结符组成的符号串，α∈(∪)+且至少有一个非终结符，而β∈(∪)*。

    终结符号是指语言不可再分的基本符号，通常是一个语言的字母表；终结符代表了语法的最小元素，是一种个体记号。
非终结符号也称语法变量，它代表语法实体或语法范畴；非终结符代表一个一定的语法概念，因此，一个非终结符是一个类、一个集合。

     例如，在程序语言中，可以把变量、常数、“+”、“*”等看作是终结符，而像“算术表达式”这个非终结符则代表着一定算术式组成的类，如i*(i+i)、i+i+i等；也即每个非终结符代表着由一些终结符和非终结符且满足一定规则的符号串组成的集合。

    文法开始符号是一个特殊的非终结符，它代表文法所定义的语言中我们最终感兴趣的语法实体，即语言的目标，而其它语法实体只是构造语言目标的中间变量；如表达式文法的语言目标是表达式，而程序语言的目标通常为程序。
产生式(也称产生规则或规则)是定义语法实体的一种书写规则。
一个语法实体的相关规则可能不止一个。
例如，有：
P→α1
P→α2
      …

P→αn

为书写方便，可将这些有相同左部的产生式合并为一个，即缩写成

P→α1∣α2∣…∣αn

    其中，每个αi(i=1,2,…,n)称为P的一个候选式，直竖“∣”读为“或”，它与“→”一样是用来描述文法的元语言符号(即不属于Σ的字符)

    由文法定义可知，文法是对语言结构的定义和描述，文法四大要素中关键是规则的集合。

3.1 例题一

    设字母表∑={a, b}，试设计一个文法，描述语言 L= { a^2n, b^2n | n≥1 }。

    分析  设计一个文法来描述一个语言, 关键是设计一组规则生成语言中的符号串。因此，为设计该语言文法，必须分析这个语言是由怎样一些符号串组成的，即首先分析语言中串的结构特征：

当n＝1   L={aa, bb}

当n＝2   L={aaaa, bbbb}

当n＝3  L={aaaaaa, bbbbbb}

……

L={aa, bb, aaaa, bbbb, aaaaaa, bbbbbb, … …} 

语言L是由偶数个a，偶数个b这样的符号串组成的集合。

3.2 例题二

    题意是用文法定义标识符，必须确定文法中的规则。为了设计出一组规则，首先应搞清楚语言中标识符的结构特征。我们认为标识符是以字母开头，后面加上字母或者数字。用I代表标识符；L代表字母；D代表数字; 则定义标识符的文法为：

3.3 例题三

    写一文法，使其语言是奇数集合，但不允许出现以0打头的奇数。

    根据题意，我们可以将奇数划分为如图2–1所示的三个部分，即最高位允许出现1～9，用非终结符B表示；中间部分可以出现任意多位数字0～9，每一位用非终结符D表示；最低位只允许出现1、3、5、7、9等奇数，用A表示。（如下图所示）

由于中间部分可出现任意位，所以另引入了一个非终结符M，它包括最高位和中间位部分。
            假定开始符为N，则可得到文法G[N]为：
           G=({0,1,…,9},{N,A,M,B,D},N,ξ)
ξ:N→A∣MA /*一位数字│多位数字*/
     M→B∣MD /*仅两位数字(无中间位)│多于两位数字*/
     A→1∣3∣5∣7∣9
     B→1∣2∣3∣4∣5∣6∣7∣8∣9

     D→0∣B

    又是一次分享，又是一次收获，这三个例子，还是要认真地去理解，有助于加深我们对“文法”的认识。

    分享和帮助是人生一大乐事，希望可以帮助您。本人才疏学浅，如果有不当之处，还请批评指正。同时欢迎大家评论、点赞及转发！