最近一直在给网站添加内容,实验都还没有做,老师都要演示了我还没开始,所以我决定先做完实验再做其他事情了。
本程序实现了LR0语法自动分析器,当输入的文法并且输入的句子也正确的情况下可以将产生式归约的过程打印出来,否则报错,没有实现错误处理程序,有兴趣的朋友可以自行实现。用到的知识有自底向上分析概述、LR分析法概述、LR(0)分析、LR(0)分析表构造算法、SLR分析等。
LR分析器(自动机)总体结构如下:
由上图可以知道,LR分析器由分析表(包括动作表和转移表)、产生式序列、输入缓冲区、LR主控程序、状态/符号栈构成。其中产生式序列可以根据输入的文法很容易就得到，输入缓冲区也就是输入的文法句子面加个"$"符号,也很容易得到,状态/符号栈在LR分析算法中会用到,而最重要的也是最难的就是分析表的自动生成。
上图(虽然是LR1自动机,但是原理和LR0或者SLR差不多)是LR自动机,分析表构造过程需要用到,会用到以下函数:
CLOSURE(I)函数:计算项目集I闭包,也就是图中的I0...I13,需要传入一个参数,也就是项目集I。
GOTO(I,X)函数:返回项目集I对应于文法符号X的后继项目集闭包,例如上图所示如果传入I0和S那么求得的结果就是项目集闭包I1。
items()函数:构造LR自动机的状态集,也就是生成I0到I13,在此函数中会调用到CLOSURE函数和GOTO函数。
analysis_table()函数:构造LR分析表，需要用到items()函数构造的自动机状态机。
analyze()函数:实现LR分析法逻辑,只需要传入某个句子即可识别该句子是否为输入文法的合法句子。在识别过程中会将用到的归约产生式输出,如果需要输出状态/符号栈的内容可以在此方法中添加相应的代码就可以实现。
LR 分析算法
- 输入：串w和LR语法分析表，该表描述了文法G的ACTION函数和GOTO函数。
- 输出：如果w在 L(G)中，则输出w的自底向上语法分析过程中的归约步骤；否则给出一个错误指示。
- 方法：初始时，语法分析器栈中的内容为初始状态s0，输入缓冲区中的内容为
w$。然后，语法分析器执行下面的程序：
令a为w$的第一个符号；
while(1) { /* 永远重复*/
令s是栈顶的状态；
if ( ACTION [s，a] = st ) {
将t压入栈中；
令a为下一个输入符号；
} else if (ACTION [s，a] =归约A → β ) {
从栈中弹出│ β │个符号；
将GOTO [t，A]压入栈中；
输出产生式 A → β ；
} else if (ACTION [s，a] =接受) break； /* 语法分析完成*/
else调用错误恢复例程；
}对应python源代码
# LR分析,w表示输入的输入的字符串,lr_table表示LR语法分析表
def analyze(self, w, lr_table):
w = w + "$"
count = 0 # 记录输入字符串的索引
a = w[count] # 指针指向的输入的字符
vt = self.grammar["vt"] # vt表示终结符集合
vn = self.grammar["vn"] # vn表示非终结符集合
action = lr_table[0] # ACTION表
goto = lr_table[1] # GOTO表
status_stack = [0] # 初始状态下状态栈中只有状态0
while True:
s = status_stack[len(status_stack) - 1] # 当前栈顶露出的状态
operation = action[s][vt.index(a)][0] # 获取当前操作
if "s" in operation: # 移入操作
status_stack.append(int(operation[1:])) # 将s后面的状态压入栈顶
count += 1 # 输入指针指向下一个字母
a = w[count] # 赋值
elif "r" in operation: # 归约操作
b = int(operation[1:]) # 获取对应的产生式编号
p = self.production[b] # 获取产生式
right = p.get("right")
left = p.get("left")
num = len(right) # 产生式右部符号个数
for i in range(num):
status_stack.pop() # 弹出状态
c = vn.index(left)
s = status_stack[len(status_stack) - 1]
status_stack.append(int(goto[s][c][0]))
print(left + "→" + right) # 输出产生式
elif operation == "acc": # 语法分析完成
break
else: # 其他就是出错了,需要调用错误恢复函数,此处就不写错误恢复函数了
raise Exception("语法分析错误")CLOSURE()函数
计算给定项目集I的闭包
CLOSURE(I) = I∪{B→ · γ |A→α·Bβ∈CLOSURE(I) , B→γ∈P}
SetOfltems CLOSURE ( I ) {
J = I；
repeat
for ( J中的每个项A → α·Bβ )
for ( G的每个产生式B → γ )
if ( 项B → · γ不在J中 )
将B → · γ加入J中；
until 在某一轮中没有新的项被加入到J中；
return J；
}对应的python源代码
# 计算项目集i的闭包,项目集表示多个项目的集合(列表),每个项目为LR0项目,例如S'→ ·S就是一个LR0项目
def closure(self, i):
j = i
for k in j: # 遍历项目集中的每一个项目
right = k.get("right") # 项目右部
index = right.find("·") # 在这里如果·后面是终结符怎么办？如果是终结符的话不会找到对应的产生式,所以没有影响
if index == -1:
raise Exception("LR0项目有误")
else:
if index != (len(right) - 1): # 表示·不是在最后
for li in self.production: # 遍历文法所有产生式
if li.get("left") == right[index + 1]: # 产生式
obj = {
"left": right[index + 1],
"right": "·" + li.get("right")
}
if obj not in j:
j.append(obj)
return jGOTO ()函数
返回项目集I对应于文法符号X的后继项目集闭包
GOTO( I, X )=CLOSURE({A→αX·β | A→α·Xβ∈I })
SetOfltems GOTO ( I，X ) {
将J 初始化为空集；
for ( I 中的每个项A → α·Xβ )
将项 A → αX·β 加入到集合J 中；
return CLOSURE ( J )；
}对应的python代码
# 返回项目集I对应于文法符号X的后继项目集闭包
def go_to(self, i, x):
j = []
for a in i: # 遍历项目集中的每一项
a_right = a.get("right")
index = a_right.find("·")
if index == -1:
raise Exception("LR0项目有误")
else:
if index != (len(a_right) - 1): # 如果·不是最后
if x == a_right[index + 1]: # 有后继项目
right = a_right[:index] + x + "·" + a_right[index + 2:len(a_right)]
obj = {
"left": a.get("left"),
"right": right
}
j.append(obj)
return self.closure(j)构造LR(0)自动机的状态集
规范LR(0) 项集族(Canonical LR(0) Collection) C={I0}∪{I | ∃J∈C, X∈VN∪VT , I=GOTO(J , X) }
void items( G' ) {
C＝{ CLOSURE ({[ S'→ ·S ] } ) }；
repeat
for (C中的每个项集 I )
for(每个文法符号X )
if ( GOTO ( I，X )非空且不在C中)
将GOTO ( I，X )加入C中；
until在某一轮中没有新的项集被加入到C中；
}对应的python代码
# 构造LR(0)自动机的状态集
def items(self):
# 注意这里self.closure的参数
start = {
"left": self.production[0].get("left"),
"right": "·" + self.production[0].get("right")
}
c = [self.closure([start])]
# 获取终结符和非终结符集合
a = []
for i in self.grammar["vt"]:
a.append(i)
for i in self.grammar["vn"]:
a.append(i)
for i in c:
for x in a:
result = self.go_to(i, x)
if len(result) > 0 and result not in c:
c.append(result)
return cLR(0)分析表构造算法
构造G'的规范LR(0)项集族C = { I0, I1, … , In}
令Ii对应状态i。状态i的语法分析动作按照下面的方法决定：
-
if A→α·aβ∈Ii and GOTO( Ii , a )=Ij then ACTION[ i, a ]=sj
-
if A→α·Bβ∈Ii and GOTO( Ii , B )=Ij then GOTO[ i, B ]=j
-
if A→α·∈Ii 且A ≠ S' then for ∀a∈VT∪{$} do ACTION[ i, a ]=rj
（j是产生式A→α的编号） -
if S'→S· ∈Ii then ACTION [ i, $ ]=acc
没有定义的所有条目都设置为“error”
对应的python代码
# C:LR(0)项集族,lr_type表示LR分析类型,可取lr0或者slr
def analysis_table(self, c, lr_type="lr0"):
status = 0
len3 = len(c) # 状态集个数
len1 = len(self.grammar["vt"]) # 终结符个数
# 可以通过action集合中的每个元素的数组长度判断该文法是否属于lr0文法或者slr文法,如果元素长度小于等于1则说明该文法是对应类型的文法,如果长度大于1说明存在冲突,该文法不是lr0或者slr文法
# 例如lr_type="lr0"是有些元素数组长度等于2,则表明该文法不是lr0文法,其他都一样,只是更改lr_type让其值为"slr"后所有元素数组长度都不大于1的话,那就表明该文法是slr文法
action = [] # ACTION集合,可以看作二维数组,如果每个元素也是一个数组,如果数组中没有元素则表示没有对应项目,初次之外可以是rn,sn,n,acc,如果数组中存在多个元素表示有冲突
for i in range(len3):
temp = []
for j in range(len1):
temp.append([])
action.append(temp)
len2 = len(self.grammar["vn"]) # 非终结符个数
goto = [] # GOTO集合
for i in range(len3):
temp = []
for j in range(len2):
temp.append([])
goto.append(temp)
for i in c: # i表示项目集闭包
for j in i: # j表示项目集中的每个项目
right = j.get("right")
index = right.find("·")
if index == -1:
raise Exception("LR0项目有误")
else:
if index != (len(right) - 1): # 表示非归约状态
a = right[index + 1]
ij = self.go_to(i, a)
if a in self.grammar.get("vt"): # a是终结符
action[status][self.grammar.get("vt").index(a)].append("s" + str(c.index(ij)))
else:
goto[status][self.grammar.get("vn").index(a)].append(str(c.index(ij)))
else: # 归约项目或者接收项目
if j.get("left") == "S'" and right == (self.grammar["start"] + "·"):
action[status][self.grammar.get("vt").index("$")].append("acc")
elif j.get("left") != "S'":
s = right.replace("·", "") # 去除点
count = 0
for t in self.production:
if t.get("left") == j.get("left") and t.get("right") == s: # 获取产生式索引
if lr_type == "lr0": # lr0
for h in range(len1):
action[status][h].append("r" + str(count))
elif lr_type == "slr": # slr
for h in range(len1): # 遍历文法中的每一个终结符
follow = self.follow(j.get("left"))
for f in follow:
if self.grammar["vt"][h] == f: # 如果终结符在follow集中的话就添加到action集
action[status][h].append("r" + str(count))
break
break # 找到产生式就可以跳出循环
count += 1
status += 1
return [action, goto]计算文法符号X的FIRST(X )
不断应用下列规则，直到没有新的终结符或ε可以被加入到任何FIRST集合中为止
- 如果X是一个终结符，那么FIRST ( X ) = { X }
- 如果X是一个非终结符，且 X→Y1…Yk∈P (k≥1)，那么如果对于某个i，a在FIRST (Yi ) 中且ε 在所有的FIRST(Y1) , … , FIRST(Yi-1)中(即Y1...Yi-1 => * ε )，就把a加入到FIRST( X )中。如果对于所有的 j = 1,2, . . . , k，ε在FIRST(Yj)中，那么将ε加入到FIRST( X )
- 如果 X→ε∈P，那么将ε加入到FIRST( X )中
对应的python代码
# 求文法符号x的first集合
def first(self, x):
result = [] # 所求的first集
if x in self.grammar["vt"]: # 终结符的first集为该终结符组成的集合
result.append(x)
elif x in self.grammar["vn"]: # 非终结符
for i in self.production: # 遍历所有产生式
if i.get("left") == x: # 该产生式左部为所求x
right = i.get("right") # 获取产生式右部
if right == "": # 产生式右部为空,直接将空添加到first集中
result.append("")
else:
s = right[0] # 产生式右部不为空则需要考虑第一个符号
if s in self.grammar["vt"]: # 如果是终结符则直接添加到first集中
result.append(s)
else: # 如果是非终结符,则需要判断其是否可以推导出空串
length = len(right) # 获取产生式右部长度
for ly in range(length): # 遍历产生式右部所有的文法符号
if "" in self.first(right[ly]): # 如果yi可以推导出空串则后面一个(yi+1)文法符号的first集添加到first集中
if ly != length - 1: # 当然不能超出索引范围
temp = self.first(right[ly + 1])
if "" in temp: # 如果有空串则去掉
temp.remove("")
result.extend(temp)
else: # 表明产生式右部所有的文法符号都可以推导出空串,将空串添加到first集中
result.append("")
else: # 如果yi不能推导出空串则需要跳出循环,在此之前需要把当前文法符号的first集添加到first集中
temp = self.first(right[ly])
result.extend(temp)
break
return list(set(result)) # 去除重复元素计算串X1X2 …Xn的FIRST 集合
- 向FIRST(X1X2…Xn)加入FIRST(X1)中所有的非ε符号
- 如果ε在FIRST(X1)中，再加入FIRST(X2)中的所有非ε符号；
- 如果ε在FIRST(X1)和FIRST(X2)中，再加入FIRST(X3)中的所有非ε符号，以此类推
- 最后，如果对所有的i，ε都在FIRST(Xi)中，那么将ε加入到
FIRST(X1X2…Xn) 中
算法
不断应用下列规则，直到没有新的终结符可以被加入到任何FOLLOW集合中为止
- 将$放入FOLLOW( S )中，其中S是开始符号，$是输入右端的结束标记
- 如果存在一个产生式A→αBβ，那么FIRST ( β )中除ε 之外的所有符号都在FOLLOW( B )中
- 如果存在一个产生式A→αB，或存在产生式A→αBβ且FIRST ( β ) 包含ε，那么 FOLLOW( A )中的所有符号都在FOLLOW( B )中
对应的python代码
# 求文法符号串x的first集合
def multi_first(self, x):
result = []
first_0 = self.first(x[0])
result.extend(first_0) # 将第一个文法符号的first集添加到first集中
if "" in first_0: # 如果第一个文法符号的first集中存在空串
first_0.remove("") # 将空串删除
result.extend(first_0) # 将第一个文法符号的first集添加到first集中
length = len(x)
for i in range(0, length): # 遍历所有的文法符号
if "" in self.first(x[i]): # 如果空串在某个文法符号的first集中,则需要将其后面文法符号的first集中非空元素添加到first集中
if (i + 1) != length: # 不是最后一个文法符号
temp = self.first(x[i + 1])
temp.remove("")
result.extend(temp)
else: # 此处表明所有文法符号的first集中都存在空串,需要将空串添加到first集中
result.append("")
else:
break
else: # 没有空串的话就直接添加到first集中
result.extend(first_0)
return list(set(result)) # 去除重复元素 计算非终结符A的FOLLOW(A)
- FOLLOW(A)：可能在某个句型中紧跟在A后边的终结符a的集合
- FOLLOW(A)={a| S => αAaβ, a∈VT，α,β∈(VT∪VN)}
- 如果A是某个句型的的最右符号，则将结束符“$”添加到FOLLOW(A)中
# 求文法符号x的follow集
def follow(self, x):
result = [] # follow集合
if x == "S'": # 如果是文法开始符号则将$添加到follow集中
result.append("$")
for i in self.production: # 遍历所有的产生式
right = i.get("right") # 获取产生式右部
length = len(right)
for j in range(length):
if right[j] == x: # 找到文法符号的位置
if (j + 1) == length: # 如果文法符号在末尾，则将产生式左部文法符号的follow集添加到follow集中
if i.get("left") == x: # 如果最后为x的话会进入无限循环,所以要跳出T' → *FT'
break
result.extend(self.follow(i.get("left")))
else:
temp = self.multi_first(right[j + 1:]) # 将其后的文法符号串的first集非空元素添加到follow集中
if "" in temp: # 存在空串
temp.remove("")
result.extend(temp)
result.extend(self.follow(i.get("left")))
else: # 不存在空串直接添加
result.extend(temp)
break # 操作完需要跳出循环
return list(set(result)) # 可能存在重复元素,所以使用set去重完整源代码可以在微信公众号
小海电脑回复LR0语法分析获取。
原文链接:
留言