‘‘‘
S
S->AB
A->&
B->&
C->AD
D->aS
S->bC
A->b
B->aD
C->b
D->c
#->#
‘‘‘
G?=?{}
#?input
print（“請(qǐng)輸入文法的開(kāi)始符:“）
S?=?input（）
print（“請(qǐng)輸入文法.（如:‘S->AB‘）.最后文法以‘#->#‘結(jié)束.“）
while?True:
????keyvalue?=?input（）.split（“->“）
????if?key==‘#‘?and?value?==?‘#‘:?break
????elif?key?in?G.keys（）:G[key].append（value）
????else:?G[key]?=?[value]

#?print（G）

#?first
def?first（strfirstset=[]）:
????t?=?str[0]
????if?t==‘&‘:?firstset.append（‘&‘）
????elif?t>=‘A‘?and?t<=‘Z‘:
????????for?s?in?G[t]:
????????????tempset?=?first（s?firstset=[]）
????????????firstset.extend（tempset）
????????????if?‘&‘?in?tempset?and?len（str）>1:
????????????????firstset.extend（first（str[1:]firstset））?????????????????
????else:?firstset.append（t）
????return?set（firstset）

#?print?first
#?print（first（input（）?firstset=[]））

#?follow
def?follow（chfollowset=[]father=[]）:
????father.append（ch）
????if?ch==S:
????????followset.append（‘#‘）
#?????????return?followset
????for?key?in?G:
????????for?s?in?G[key]:
????????????if?ch?in?s:
#?????????????????print（ss.index（ch））
????????????????i?=?s.index（ch）
????????????????if?i?==?len（s）-1:
#?????????????????????print（father）
????????????????????if?key?in?father:?continue
????????????????????followset.extend（follow（keyfollowsetfather））
????????????????elif?i?????????????????????tempset?=?first（s[i+1:]?firstset=[]）
????????????????????#print（tempset）
????????????????????if?‘&‘?in?tempset:
????????????????????????if?key?in?father:?continue
#?????????????????????????print（‘tempset=‘tempset）
????????????????????????tempset.remove（‘&‘）
????????????????????????followset.extend（tempset）
#?????????????????????????print（‘tempset=‘tempset）
????????????????????????followset.extend（follow（keyfollowsetfather））
????????????????????else:followset.extend（tempset）
????return?set（followset）

#?print?follow?????????????
#?print（follow（input（）?followset=[]））

#?select
selectset={}
def?select（）:
????for?key?in?G:
????????for?s?in?G[key]:
????????????selectset[key+‘->‘+s]?=?first（s?firstset=[]）
????????????if?‘&‘?in?selectset[key+‘->‘+s]:
????????????????selectset[key+‘->‘+s].remove（‘&‘）
????????????????selectset[key+‘->‘+s]?=?selectset[key+‘->‘+s]?|?set（follow（key?followset=[]father=[]））
????return?selectset

#?print?selectset
#?print（select（））

def?judeLL1（）:
????flag?=?True
????select（）
????print（‘文法的select?set如下：‘）
????for?key?in?selectset:
????????print（key+‘:‘selectset[key]）
????print（‘LL（1）判斷過(guò)程如下（即select集合的求交集過(guò)程）：‘）
????for?key1?in?selectset:
????????for?key2?in?selectset:
????????????if?key1==key2:?continue
????????????elif?key1[0]==key2[0]:
????????????????print（selectset[key1]‘U‘selectset[key2]end=‘‘）
????????????????tempset?=?selectset[key1]?&?selectset[key2]
????????????????if?tempset:
????????????????????flag?=?False
????????????????????print（‘?=‘tempset）
????????????????else:print（‘?=?NULL‘）
????return?flag
????
#?jude?LL（1）?????????
#?