#-*-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;