编译原理 LL1文法的判断和句子识别

时间:2021-11-19 03:01:15

编译原理 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,

编译原理 LL1文法的判断和句子识别

样例2

编译原理 LL1文法的判断和句子识别