|
1. 实验要求
（1）已知文法G[S']
(0) S'→E
(1) E→aA
(2) E→bB
(3) A→cA
(4) A→d
(5) B→cB
(6) B→d
手工建立文法G[S']的LR(0)的项目集规范族DFA和LR(0)分析表。
（2） 根据清华大学版《编译原理（第3版）》教材上LR(0)语法分析的算法思想及算法流程，构造LR(0)语法分析程序。
（3）用该LR(0)语法分析程序对任意给定的键盘输入串进行语法分析，并根据栈的变化状态输出给定串的具体分析过程。如果分析成功，则输入输出串是给定文法的合法句子的结论；如果分析不成功，则输入输出串不是给定文法的句子的结论。
详细分析过程可以看看这篇：
LR(0)分析法 - ISGuXing - 博客园 (cnblogs.com)
2. 分析结果输出
3. Python代码实现
import copy
class Stack(): # 定义类
def __init__(self): # 产生一个空的容器
self.__list = []
def size(self): # 返回栈中元素个数
return len(self.__list)
def push(self, item): # 入栈
self.__list.append(item)
def push_list(self, list): # 末尾添加多个元素
for i in range(len(list)):
self.push(list[i])
def pop(self): # 出栈
return self.__list.pop()
def pop_list(self, n): # 出栈n个元素
for i in range(n):
self.pop()
def peek(self): # 返回栈顶元素
return self.__list[-1]
def is_empty(self): # 判断是否已为空
return not self.__list
def deep_copy(self): # 深拷贝
new_stack = Stack()
for i in range(self.size()):
new_stack.push(self.__list[i])
return new_stack
def bottom_output(self): # 从栈底开始排列输出
string = ""
for i in range(self.size()):
string += str(self.__list[i])
return string
def top_output(self): # 从栈顶开始排列输出
string = ""
for i in range(self.size() - 1, -1, -1):
string += str(self.__list[i])
return string
# LR(0)分析表
LR0_table = {
0: {'a': 'S2', 'b': 'S3', 'c': None, 'd': None, '#': None, 'E': 1, 'A': None, 'B': None},
1: {'a': None, 'b': None, 'c': None, 'd': None, '#': 'acc', 'E': None, 'A': None, 'B': None},
2: {'a': None, 'b': None, 'c': 'S4', 'd': 'S10', '#': None, 'E': None, 'A': 6, 'B': None},
3: {'a': None, 'b': None, 'c': 'S5', 'd': 'S11', '#': None, 'E': None, 'A': None, 'B': 7},
4: {'a': None, 'b': None, 'c': 'S4', 'd': 'S10', '#': None, 'E': None, 'A': 8, 'B': None},
5: {'a': None, 'b': None, 'c': 'S5', 'd': 'S11', '#': None, 'E': None, 'A': None, 'B': 9},
6: {'a': 'r1', 'b': 'r1', 'c': 'r1', 'd': 'r1', '#': 'r1', 'E': None, 'A': None, 'B': None},
7: {'a': 'r2', 'b': 'r2', 'c': 'r2', 'd': 'r2', '#': 'r2', 'E': None, 'A': None, 'B': None},
8: {'a': 'r3', 'b': 'r3', 'c': 'r3', 'd': 'r3', '#': 'r3', 'E': None, 'A': None, 'B': None},
9: {'a': 'r5', 'b': 'r5', 'c': 'r5', 'd': 'r5', '#': 'r5', 'E': None, 'A': None, 'B': None},
10: {'a': 'r4', 'b': 'r4', 'c': 'r4', 'd': 'r4', '#': 'r4', 'E': None, 'A': None, 'B': None},
11: {'a': 'r6', 'b': 'r6', 'c': 'r6', 'd': 'r6', '#': 'r6', 'E': None, 'A': None, 'B': None},
}
# 产生式
Product = {
0: {'S': 'E'},
1: {'E': 'aA'},
2: {'E': 'bB'},
3: {'A': 'cA'},
4: {'A': 'd'},
5: {'B': 'cB'},
6: {'B': 'd'},
}
# 终结符
VT = ['a', 'b', 'c', 'd', '#']
# 非终结符
VN = ['S', 'A', 'B', 'E']
# 记录分析结果
analyzeResult = False
# 记录分析步骤
analyzeStep = 0
# 状态栈、符号栈、字符串栈
stateStack = Stack()
symbolStack = Stack()
stringStack = Stack()
# 字符串翻转
def reverseString(string):
return string[::-1]
# 检查输入串
def checkString(string):
stringLegal = True
if (len(string) == 0):
print("输入出错：输入串不能为空！")
stringLegal = False
if (string[-1] != "#"):
print("输入出错：输入串缺少结束符'#'！")
stringLegal = False
for i in range(len(string)):
if (string[i] not in VT):
print("输入出错：存在不是终结符的字符！")
stringLegal = False
break
return stringLegal
# 初始化三个栈
def initStack(string):
# 状态栈，入栈0
stateStack.push(0)
# 符号栈，入栈#
symbolStack.push('#')
# 输入串入栈，即string逆序入栈
stringStack.push_list(reverseString(string))
# 调用分析函数
toAnalyze()
# 根据栈中内容进行分析
def toAnalyze():
global analyzeResult
global analyzeStep
analyzeStep += 1
stateStack_top = stateStack.peek()
stringStack_top = stringStack.peek()
curren = LR0_table[stateStack_top][stringStack_top]
# LR(0)分析表中查到None
if (curren == None):
print(
"|{:^5}|{:^20}|{:^20}|{:^20}|{:^10}|{:^10}|".format(analyzeStep, stateStack.bottom_output(),
symbolStack.bottom_output(), stringStack.top_output(),
'None', ''))
print("错误：Action值为None!")
analyzeResult = False
return
# LR(0)分析表中查到acc
if (curren == 'acc'):
print(
"|{:^5}|{:^20}|{:^20}|{:^20}|{:^10}|{:^10}|".format(analyzeStep, stateStack.bottom_output(),
symbolStack.bottom_output(), stringStack.top_output(),
'acc', ''))
analyzeResult = True
return
# LR(0)分析表中查到S
elif (curren[0] == 'S' ):
print(
"|{:^5}|{:^20}|{:^20}|{:^20}|{:^10}|{:^10}|".format(analyzeStep, stateStack.bottom_output(),
symbolStack.bottom_output(), stringStack.top_output(),
curren, ''))
# 状态栈进S下标
curren = curren.replace('S', '')
stateStack.push(int(curren))
# 字符栈弹栈顶部元素进符号栈
symbolStack.push(stringStack.pop())
# 接着分析
toAnalyze()
# LR(0)分析表中查到r
elif (curren[0] == 'r' ):
# 保存一下curren, stateStack和symbolStack,，以便后续打印出来
save_curren = curren
save_stateStack = stateStack.deep_copy()
save_symbolStack = symbolStack.deep_copy()
# 根据r下标，寻找归约所用的产生式的key和value
curren = curren.replace('r', '')
key = list(Product[int(curren)].keys())[0]
value = list(Product[int(curren)].values())[0]
# 根据产生式左部value的长度，对状态站和符号栈进行退栈操作
val_len = len(value)
stateStack.pop_list(val_len)
symbolStack.pop_list(val_len)
# 根据状态站当前栈顶元素和产生式左部key，寻找GOTO值
state_top = stateStack.peek()
tmp_GOTO = LR0_table[state_top][key]
# GOTO值为None，打印错误信息
if (tmp_GOTO == None):
print(
"|{:^5}|{:^20}|{:^20}|{:^20}|{:^10}|{:^10}|".format(analyzeStep, save_stateStack.bottom_output(),
save_symbolStack.bottom_output(),
stringStack.top_output(),
save_curren, 'None'))
print("错误：GOTO值为None!")
analyzeResult = False
return
# GOTO值不为None,将GOTO值入状态栈，产生式左部key入符号栈
else:
print(
"|{:^5}|{:^20}|{:^20}|{:^20}|{:^10}|{:^10}|".format(analyzeStep, save_stateStack.bottom_output(),
save_symbolStack.bottom_output(),
stringStack.top_output(),
save_curren, tmp_GOTO))
stateStack.push(tmp_GOTO)
symbolStack.push(key)
toAnalyze()
if __name__ == '__main__':
print("请输入待分析的字符串：")
string = input()
# 滤空格
string = string.replace(" ", "")
if (checkString(string)):
print(
"|{:^4}|{:^18}|{:^18}|{:^18}|{:^10}|{:^10}|".format('步骤', '状态栈', '符号栈', '输入串', 'Action', 'GOTO'))
initStack(string)
if (analyzeResult):
print("由以上分析可知，该串是文法的合法句子。\n")
else:
print("由以上分析可知，该串不是文法的合法句子。\n")
|