选题二、文法的表示及语言中句子的判定

一、    问题描述
定义1（字母表）字母表是一个非空有穷集合，字母表中的元素称为该字母表中的一个字母，也可称为符号或字符。

定义2（正闭包和克林闭包）由字母表中的字符组成的所有字符串（不包含空串）构成的集合记为+，称为的正闭包。由字母表中的字符组成的所有字符串（含空串）构成的集合记为*，称为的克林闭包。
注意：+＝*∪{}。其中，为空串。

例1. 给定字母表＝{a,b}，则*是由字符a和b组成的任意长度（包括长度为0的空串）的字符串的集合。a,aa,aaa,ab,ba,aab,abb,baa,aba.bab,bba,…,等等都是*中的元素。



定义3（文法）文法G=(V,T,P,S)是一个四元组，其中
    V：语法变量的非空有穷集合。AV, A称作一个语法变量，也称作非终极符号。
    T：终极符号的非空有穷集合。aT, a称作一个终极符号。V∩T=。
    P：产生式的非空有穷集合。P中的每个元素称为一个产生式，其形如，读作定义为。称为产生式的左部，称为产生式的右部。其中(V∪T)+，且中至少有V中的一个元素出现；(V∪T)*。产生式又称作语法规则。
    S：文法的开始符号。SV。
对于一组有相同左部的产生式：1，2，…，n，可简记为：1|2|…|n，其中1，2，…，n称为候选式。称所有定义的产生式为产生式。
注意：V∩T=的含义是：语法变量与终极符号是互不相同的字符。SV的含义是：开始符号必须是一个语法变量。是由语法变量或终极符号组成的字符串，且不能为空串，且其中至少含有一个语法变量。是由语法变量或终极符号组成的字符串，但可以为空串，且其中可以不含语法变量。

定义4（推导）G=(V,T,P,S)是一个文法，如果P，，(V∪T)*，则称在G中直接推导(或直接派生)出，记作。在不特别强调推导的直接性时，直接推导可简称为推导（或派生）。
推导的本质是：用产生式的右部替换产生式的左部在字符串中的某个出现。通常情况下，对产生式的左部在字符串中的哪个出现最先施加推导并无严格规定。
当12…n-1，则记为n。读作经n步推导出。当n可以为0或任意多时，记为*。

定义5（语言，句子）设文法G=(V,T,P,S)，则称L(G)＝{w|wT且S*w }为文法G产生的语言。wL(G)，w称为G产生的一个句子。
   G产生的句子是：由开始符号推导出的，全部由终极符号组成（即不含语法变量）的字符串。G产生的语言是：由G产生的全部句子所组成的集合。

约定：当字符串w的某个子串s在w中连续出现时，可将其简记为sn。将简记后的形式称为一般形式。例如，w=aabcbcbcd，可简记为w=a2(bc)3d。类似地，有a+表示所有由若干（不少于1）个a组成的字符串，a*表示所有由若干（含0）个a组成的字符串。

例2．文法G＝(V,T,P,S)定义如下：V={S}，T={x,y}，P={Sxy，S xSy}。则有，直接推导：Sxy和S xSy。由后者，有S xSyxxSyyxxxSyyy…。以此类推，可知S*xnyn。即G所定义的语言是由所有满足如下条件的字符串构成的集合：全部由字符x所组成的字符串和全部由字符y所组成的字符串拼接而成的字符串，且字符串中字符x的个数与y的个数相同。换句话说，语言L(G)中的任何一个句子，一定可分为前后两部分，前面都是字符x，后面都是字符y，且x的个数与y的个数一样多。

定义6（派生树）设有文法G＝(V,T,P,S)，G的派生树是满足如下条件的（有序）树：
1．树的每个结点有一个标记X，且XV∪T∪{}。
2. 根的标记为S。
3. 如果一个非叶子结点v标记为A，v的儿子从左到右依次为v1，v2，…，vn，并且它们分别标记为X1，X2，…，Xn，则AX1X2…XnP。
4. 如果X是一个非叶子结点的标记，则XV。
5. 如果一个结点v标记为，则v是该树的叶子，并且v是其父结点的唯一儿子。
派生树也称作生成树、分析树、语法树。

例3. 文法G＝({E},{id,+,-,*,/},{Eid, EE+E, EE-E, EE*E, EE/E},E)的句子id+id×id的派生树为：
请开发一个软件系统完成文法的存储；并可根据给定文法输出它所产生的语言；并能判断任给的一个字符串是否为该文法所产生的句子。

二、基本需求
1. 可输入、输出、存储任给的文法G。
2. 可输出文法G定义的语言L(G)。当L(G)为无穷语言时，可给出其一般形式的表示。
3. 对任给的字符串w，可判定w是否为L(G)中的句子。若wL(G)（即w是L(G)中的句子），则可给出至少一个推导过程。
4. 输入输出形式可任意，但应做到尽量友好，符合习惯。

5、 可判断任给的两个文法是否等价。（注：文法G和G’，当L(G)= L(G’)时，称G和G’等价）。