编译原理 LL1文法的判断和句子识别
LL1文法概述
点击查看百度百科
对文法G的句子进行确定的自顶向下语法分析的充分必要条件是，G的任意两个具有相同左部的
产生式A—>α|β 满足下列条件：
（1）如果α、β均不能推导出ε，则 FIRST(α) ∩ FIRST(β) = Φ。
（2）α 和 β 至多有一个能推导出 ε。
（3）如果 β *═> ε，则 FIRST(α) ∩ FOLLOW(A) = Φ。
将满足上述条件的文法称为LL(1)文法。
第一个L代表从左向右扫描输入符号串，第二个L代表产生最左推导，1代表在分析过程中执行每一步推导都要向前查看一个输入符号——当前正在处理的输入符号。
LL(1)文法既不是二义性的，也不含左递归，对LL(1)文法的所有句子均可进行确定的自顶向下语法分析。
需要注意的是，并不是所有的语言都可以用LL(1)文法来描述，而且不存在判定某语言是否是LL(1)文法的算法。也就是说，确定的自顶向下分析只能实现一部分上下文无关语言的分析，这就是LL(1)文法所产生的语言。另外，在上述LL(1)文法的条件中，要求：ε ∈ FIRST(α1)，ε ∈ FIRST(α2)，…ε ∈ FIRST(αn) 中至多有一个成立。
程序介绍
算法参考张素琴等《编译原理》第二版，清华大学出版社。编程语言和环境：python3.5 ，window86-32bite
求能导出空串的非终结符
1、创建一个键为字母表（包括，用表示空串，下同） ，值为1的字典,并将空串的值变为0：
| S | A | B | a | b | * |
|---|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 1 | 0 |
2、扫描每条产生式，若产生式右部所有的字符对应的值为0，就把左部的非终结符对应的值赋0
3、重复2，直到字典不在改变为止
计算非终结符FIRST集F
1、构建每一非终结符的FIRST集，开始为空
2、对于每一文法符号
若x为终结符，则FIRST（x）={x}
若x为非终结符：
若有x->aG,G为字母表上的符号串，a属于FIRST（x）
若x->,则 属于FIRST（x）
若x的产生式右部全都是非终结符Y1~Yn，若Y1~Yn全部能导出空串，则FIRST（x）＝FIRST（Y1）U …U FIRST（Yn） U {*}
若Y1~Yi-1都能推出空串，则FIRST（Yi）-{*}，I为1~i-1，和FIRST（YI）都在FIRST（x）中
3、重复步骤2，直到FIRST不在增大
计算产生式右部字符串的FIRST集F1
逐个扫描串上的字母，方法同计算非终结符FIRST集F。
计算FOLLOW集follow
1、构建每一个非终结符的follow集，并给开始符的follow集加上{#}
2、若有A->aBc,则把FIRST（c）的非空元素加入follow（B），若有c->*，则把follow（A）加入follow（B）
3、若有A->aB,则把follow（A）加入follow（B）
4、重复步骤2，3，直到follow不再变化
计算SELECT集S
对于A->a
若a不能导出空，则select（A->a）=FIRST（a）
若a能导出空，则select（A->a）=(FIRST（a）-{*}) U follow(A)
判定是否为LL1文法
遍历产生式，若有相同左部的产生式的交集不为空，则不是LL1文法
若是LL1文法，输入句子匹配
1、构造分析栈st={#，start}，start为开始符。
2、从st栈顶选取元素a，从要匹配句子S选取最左边元素b，若a=b，则a，b出栈，若不相等，则：
对于a寻找以a开头的产生式a->(右部)的select集，使b属于select，a出栈，右部逆序入st。若找不到，匹配失败结束程序
3，重复步骤2，直到st和S均为#，匹配成功。
源代码
def put_in():#输入文法五元组
global a,vn,vt,start
#a=[list('S->AB'),list('S->bC'),list('A->*'),list('A->b'),list('B->*'),list('B->aD'),list('C->AD'),list('C->b'),list('D->aS'),list('D->c')]
#vn=['S','A','B','C','D']
#vt=['a','b','c']
a=[list('E->TA'),list('A->+TA'),list('T->FB'),list('A->*'),list('B->-FB'),list('B->*'),list('F->i'),list('F->(E)')]
vn=['E','A','B','F','T']
vt=['+','-','(',')','i']
start='E'
print('文法产生式为：')
for i in a:
print (i)
def judge_null():#求能推出空串的非终结符
null=['*']
values=[1]*len(vn+vt+null)
dic=dict(zip(vn+vt+null,values))
dic['*']=0
for un_relation in range(5):
for i in a:
sum=0
for j in range(3,len(i)):
sum=sum+dic[i[j]]
if sum==0:
dic[i[0]]=0
return dic
def first():#求每一个非终结符的FIRST集
dic=judge_null()
global f
f=[]
for i in range(len(vn)):
f=f+[set()]
for ji in range(5):
for i in range(len(vn)):
for j in a:
if vn[i]==j[0]:
oo=0
for i1 in range(3,len(j)):
if dic[j[i1]]==0:
oo=oo+1
if oo==len(j)-3 and j[3]!='*':#若右部全部是能推出空符的非终结符
for i1 in range(3,len(j)):
f[i]=f[i]|f[vn.index(j[i1])]
f[i]=f[i]|{'*'}
else:
if j[3] in vt:
f[i].add(j[3])
elif j[3]=='*':
f[i].add('*')
else:
for i1 in range(3,len(j)):
if dic[j[i1]]==0:
if '*' in f[vn.index(j[i1])]:
f[i]=(f[vn.index(j[i1])]|f[i])-{'*'}
else:
f[i]=(f[vn.index(j[i1])]|f[i])
else:
f[i]=(f[vn.index(j[i1])]|f[i])
break
print('非终结符的FIRST集依次为：')
print(f)
def first_chuan():#求每一个产生式右部符号串的FIRST集
global f1
dic=judge_null()
f1=[]
for i in range(len(a)):
f1=f1+[set()]
for i in a:
k=a.index(i)
oo=0
for j in range(3,len(i)):
if dic[i[j]]==0:
oo=oo+1
if oo==len(i)-3 and i[3]!='*':#若全部是能推出空符的非终结符
for j in range(3,len(i)):
f1[k]=f1[k]|f[vn.index(i[j])]
f1[k]=f1[k]|{'*'}
else:
if i[3] in vt:#若是以终结符开头
f1[k].add(i[3])
elif i[3]=='*':#若是空符
f1[k].add('*')
else:
for j in range(3,len(i)):
if dic[i[j]]==0:
f1[k]=(f[vn.index(i[j])]|f1[k])-{'*'}
else:
f1[k]=(f[vn.index(i[j])]|f1[k])
break
print('符号串的FIRST集依次为：')
print(f1)
def index1(li,k): #神奇勿动，求在产生式右部某元素在列表第一次出现的位置
for i in range(3,len(li)):
if li[i]==k:
return i
def follow_():#计算非终结符的FOLLOW集
dic=judge_null()
global follow
follow=[]
for i in range(len(vn)):
follow=follow+[set()]
follow[vn.index(start)]=follow[vn.index(start)]|{'#'}
for iii in range(5):
for i in range(len(vn)):
for j in a:
for k in j[3:]:
if k==vn[i]:
if index1(j,k)==len(j)-1:
follow[i]=follow[i]|follow[vn.index(j[0])]
else:
if j[index1(j,k)+1] in vt:
follow[i]=follow[i]|{j[index1(j,k)+1]}
else:
if dic[j[index1(j,k)+1]]==1:
follow[i]=(follow[i]|f[vn.index(j[index1(j,k)+1])])-{'*'}
else:
follow[i]=(follow[i]|f[vn.index(j[index1(j,k)+1])])-{'*'}
follow[i]=follow[i]|follow[vn.index(j[0])]
print('follow集依次为：')
print(follow)
def select():
dic=judge_null()
global s
s=[]
for i in range(len(a)):
s=s+[set()]
for i in a:
k=a.index(i)
oo=0
for j in range(3,len(i)):
if dic[i[j]]==0:
oo=oo+1
if oo==len(i)-3 :#若全部是能推出空符
s[k]=(f1[k]-{'*'})|follow[vn.index(i[0])]
else:
s[k]=f1[k]
print('select集依次为：')
print(s)
def judge():#判断文法是不是LL1文法
b=set()
zz=0
for i in range(len(a)):
for k in range(len(a)):
if a[i][0]==a[k][0] and i!=k:
b=s[i]&s[k]
if len(b)!=0:
print('不是LL（1）文法,因为：')
print(a[i],'和',a[k],'的select集的交集不为空')
zz=1
if zz==1:
return 1
else:
return 0
def pipei():#匹配字符串
if judge()==1:
return 0
c=list(input('请输入待匹配子串'))
st=['#',start]
while True:
i=0
for k in range(len(s)):
if st[len(st)-1]==a[k][0] and c[0] in s[k]:
i=1
st.pop()
for j in range(3,len(a[k])):
st=st+[a[k][len(a[k])-j+2]]
if st[len(st)-1]=='*':
st.pop()
if st[len(st)-1]==c[0]:
if c==['#'] and st==['#']:
print('Accept')
return 0
c.remove(c[0])
st.pop()
if c==['#'] and st==['#']:
print('Accept')
return 0
if i==0:
print('error')
return 0
def run():
put_in()
first()
first_chuan()
follow_()
select()
judge()
pipei()
run()程序运行结果
样例1，
样例2
