#-*-coding:utf-8-*-
G = raw_input("提示输入文法：");  #G为文法
S = G[2]  #识别符号S

Vn = raw_input("提示输入Vn：");  #Vn为非终结符号集
charactersVn = Vn.split(‘,‘);  #记录每个非终结符号
VnString = "";
for var in charactersVn:
    VnString += var + ",";
vAll = [];
lefties = [];  #所有产生式左边的符号
setAllVt = set([]);  #含重复元素
setVtAndVn = set([]);  #非终结符号集的集合

P = raw_input("提示依次输入产生式规则:");  #P为产生式集
setP = P.split();  #根据空格分
for varP in setP:
    n_t = varP.split(‘::=‘); 
#    leftOfP = n_t[0];  #产生式左边
    lefties.append(n_t[0]);
    rightOfP = n_t[1];  #产生式右边
    rightChar = rightOfP.split(‘|‘);  #产生式右边的分割
    setAllVt = setAllVt | set(rightChar);  #所有产生式右边的式子的集合

#只保留式子右边中的单个符号
for ele in list(setAllVt):
 #   if len(ele) == 1:
 #       setVtAndVn = setVtAndVn | set(ele);
    for i in range(0, len(ele)):
        setVtAndVn = setVtAndVn | set(ele[i]);

setVt = list(setVtAndVn - set(charactersVn))  #利用集合的差求非终结符号集
VtString = "";
for var in setVt:
    VtString += var + ",";
#print setVt;

#print len(lefties);
flag = 0;  #代表几型文法
length = 0;
#记录并判断产生式左边长度是否都为1
for varLefty in lefties:
    length += len(varLefty)

if length == len(lefties):  #长度都为1
    flag = 2;
else:
    flag = 1;

#在0型文法和1型文法之间进行判断
if flag == 1:
    for varP in setP:
        n_t = varP.split(‘::=‘);
    left = n_t[0];
        right = n_t[1];
        righties = right.split(‘|‘);
        for righty in righties:
            if len(left) > len(righty):
                flag = 0;

#在2型文法和3型文法中间进行选择
count = 0;
total = 0;
twoOrThird = 0;
if flag == 2:
    twoOrThird = 1;
    for varP in setP:
        n_t = varP.split(‘::=‘);
        right = n_t[1];  #::=的左边
        righties = right.split(‘|‘);  #|分割后的每个产生式右边（由于表达形式的原因，要再次区分并计数）
        for righty in righties:
            total += 1;
            if len(righty) == 1 and righty[0] in setVt:  #右边为单个终结符合
                count += 1;
            elif len(righty) == 2 and righty[0] in setVt and righty[1] in charactersVn:  #右边为单个终结符号加单个非终结符号
                count += 1;

if count == total and twoOrThird == 1:
    flag = 3;

print "文法" + G + "= ({" + VnString[:-1] + "} ,{" + VtString[:-1] + "}, P, " + G[2] + ")\n" ;
print P + "\n"
print "该文法是Chomsky%d型文法" % flag;