版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、-. z.计算机科学与通信工程学院编译原理实验报告题目: 1.词法分析器2. LL(1)分析器 3. LR(0)分析器班级:: *:指导教师:2017年月-. z.-. z.目录 TOC o 1-3 h z u HYPERLINK l _Toc483942693一、实验题目 PAGEREF _Toc483942693 h 1HYPERLINK l _Toc483942694二、实验目的和要求 PAGEREF _Toc483942694 h 1HYPERLINK l _Toc483942695三、代码实现 PAGEREF _Toc483942695 h 1HYPERLINK l _Toc4839
2、42696四、总结 PAGEREF _Toc483942696 h 1-. z.-. z.实验题目词法分析器分析一段程序代码,将代码中的单词符号分解出来,并对其进展检查,输出token表和error表LL(1)文法分析器分析给定文法。求出文法的FIRST集,FOLLOW集,并构建分析表,对给定输入串进展分析。LR(0)文法分析器分析给定文法。用_CLOSURE方法构造文法的LR(0)工程集规*族,根据状态转换函数GO构造出文法的DFA,并转换为分析表,对给定输入串进展分析。实验目的和要求学会词法分析器的实现思路。学会求解FIRST集, FOLLOW集,构造LL(1)分析表。学会_CLOSURE
3、方法,状态转换函数GO, 构造LR(0)分析表。代码实现词法分析器program.t*t 中存放要分析的文法:E-TRR-+TR|-TR|T-FGG-*FG|/FG|F-(E)|i:KEYWORD_LIST = while, if, else, switch, caseSEPARATOR_LIST = ;, :, , (, ), , , , OPERATOR_LIST1 = +, -, *OPERATOR_LIST2 = =, , =CATEGORY_DICT = # KEYWORD while: while: , if: if: , else: else: , switch: switch:
4、 , case: case: , # OPERATOR +: +: , -: -: , *: *: , =: relop: LE, =: relop: GE, : relop: GT, =: relop: EQ, =: =: , # SEPARATOR ;: ;: , : : , ,: ,: , (: (: , ): ): , : : , : : , : : , : : ,CONSTANTTABLE = TOKENTABLE = OPERATORTABLE = KEYWORDTABLE = SEPARATORTABLE = UNDEFINEDTABLE = # READ FILEdef rea
5、d_file(path, method): temp_str = try: file = open(path, method) for line in file: line = line.replace(n, ) temp_str += line temp_str = str(temp_str) e*cept IOError as e: print(e) e*it() finally: file.close() return temp_str.strip() + # GETBEdef getbe(): global token getchar() token = return# GETCHAR
6、def getchar(): global character global location while all_stringlocation = : location = location + 1 character = all_stringlocation return character# LINK TOKENdef concatenation(): global token global character token = token + character# IS NUMBERdef digit(): if 0 = character = 9: return True return
7、 False# IS ALPHABETdef letter(): if A = character = Z or a = character = z: return True return False# IS IDENTIFIERdef reserve(): if token in KEYWORD_LIST: return CATEGORY_DICTtoken else: return 0# RETRACTdef retract(): global location global character # location = location - 1 character = return# M
8、AIN FUNCTIONdef main(): global token global character global location s = getchar() getbe() if a = s = z or A = s = Z: while letter() or digit(): concatenation() location = location + 1 character = all_stringlocation retract() c = reserve() if c = 0: TOKENTABLE.append(token) print(这是标识符:, token, :,
9、TOKENTABLE.inde*(token), ) else: KEYWORDTABLE.append(token) print(这是保存字:, CATEGORY_DICTtoken) elif 0 = s = 9: while digit(): concatenation() location = location + 1 character = all_stringlocation retract() CONSTANTTABLE.append(token) print(这是常数:, token, :, CONSTANTTABLE.inde*(token), ) elif s in OPE
10、RATOR_LIST1: location = location + 1 OPERATORTABLE.append(s) print(这是单操作符:, CATEGORY_DICTs) elif s in OPERATOR_LIST2: location = location + 1 character = all_stringlocation if character = =: OPERATORTABLE.append(s + character) print(这是双操作符:, CATEGORY_DICTs + character) else: retract() location = loc
11、ation + 1 OPERATORTABLE.append(s) print(这是单操作符:, CATEGORY_DICTs) elif s in SEPARATOR_LIST: location = location + 1 SEPARATORTABLE.append(s) print(这是分隔符:, CATEGORY_DICTs) else: location += 1 UNDEFINEDTABLE.append(s) print(error:undefined identity :, s, )if _name_ = _main_: character = token = all_str
12、ing = read_file(program.t*t, r) location = 0 while location + 1 TRR-+TR|-TR|T-FGG-*FG|/FG|F-(E)|i输入串:i+i*i代码:NonTermSet = set() # 非终结符集合TermSet = set() # 终结符集合First = # First集Follow = # Follow集GramaDict = # 处理过的产生式Code = # 读入的产生式AnalysisList = # 分析表StartSym = # 开场符号EndSym = # # 完毕符号为#Epsilon = # 由于没
13、有epsilon符号用代替# 构造First集def getFirst(): global NonTermSet, TermSet, First, Follow, FirstA for * in NonTermSet: First* = set() # 初始化非终结符First集为空for * in TermSet: First* = set(*) # 初始化终结符First集为自己Change = True while Change: # 当First集没有更新则算法完毕Change = False for * in NonTermSet: for Y in GramaDict*: k =
14、0 Continue = True while Continue and k len(Y): if not FirstYk - set(Epsilon) 0: # Y1到Yi候选式都有存在Continue = False else: First* |= FirstYk - set(Epsilon) Change = True if Epsilon not in FirstYk: Continue = False k += 1 if Continue: # *-或者Y1到Yk均有产生式First* |= set(Epsilon) # FirstAY |= set(Epsilon)# 构造Foll
15、ow集def getFollow(): global NonTermSet, TermSet, First, Follow, StartSym for A in NonTermSet: FollowA = set() FollowStartSym.add(EndSym) # 将完毕符号参加Follow开场符号中Change = True while Change: # 当Follow集没有更新算法完毕Change = False for * in NonTermSet: for Y in GramaDict*: for i in range(len(Y): if Yiin TermSet: c
16、ontinue Flag = True for j in range(i + 1, len(Y): # continue if not FirstYj - set(Epsilon) = FollowYi: FollowYi |= FirstYj - set(Epsilon) # 步骤2 FIRST()/ 参加到FOLLOW(B)中。Change = True if Epsilon not in FirstYj: Flag = False break if Flag: if not Follow* ,把FOLLOW(A)加到FOLLOW(B)中FollowYi |= Follow* Change
17、 = True# 构造分析表def getAnalysisList(): for non* in NonTermSet: AnalysisListnon* = dict() row = AnalysisListnon* flag = True for Y in GramaDictnon*: for term in TermSet: if term in FirstY0 and term in Firstnon*: rowterm = non*+-+Y if Epsilon in Firstnon* and flag: flag = False for tmp in Follownon*: ro
18、wtmp = non*+-+Epsilon print(分析表:) for non* in NonTermSet: print( , non*, AnalysisListnon*)# 查询分析表def findAnalysisList(non, ter): try: tmp = AnalysisListnonter *, Y = tmp.split(-) e*cept E*ception as e: print(find error ) # MA,a为空,发现语法错误print(e) pass return Y# 显示格式def display(show_list): for item in
19、show_list: print( %-25s % item, end=) print()# LL(1)分析器def analyzer(): head = Stack, StackTop, NowStr, InputStr, Action # inputStr = i+i*i + EndSym inputStr = input(请输入表达式:) + EndSym print(分析过程:) display(head) stack = location = 0 stack.append(EndSym) stack.append(StartSym) stack_top = stack.pop() w
20、hile stack_top != EndSym and location ,只将A弹出mess = 弹出栈顶符号 + stack_top + 因M + stack_top + , + inputStrlocation + 中为 + stack_top mess = mess + -,故不压栈 else: # MA,a中的产生式右部符号串按逆序逐一压入栈中mess = 弹出栈顶符号 + stack_top + ,将M + stack_top + , + inputStr location + 中的 + stack_top + - + result + 的 + result mess = mes
21、s + 逆序压栈 tmp_list = for char in result: tmp_list.append(char) tmp_list.reverse() stack.e*tend(tmp_list) display(stack, stack_top, inputStrlocation, inputStrlocation + 1: len(inputStr), mess) stack_top = stack.pop() else: break if stack_top = EndSym and inputStrlocation = EndSym: # * = a = # 分析成功,分析器
22、停顿工作display(, #, #, , 匹配,分析成功) print() print(*) print(* Analysis Success *) print(*) else: print(Analysis Error)# 读取文法defreadGrammar(): try: file = open(grammar.t*t, r) for line in file: line = line.replace(n, ) Code.append(line) e*cept IOError as e: print(e) e*it() finally: file.close() return Code
23、# 初始化def init(): global NonTermSet, TermSet, First, Follow, StartSym, Code Code = readGrammar() n = int(len(Code) print(产生式个数:, n) StartSym = Code00 print(开场符号:, StartSym) print(产生式:G, StartSym, :) for i in range(n): *, Y = Codei.split(-) print( , Codei) NonTermSet.add(*) Y = Y.split(|) for Yi in Y:
24、 TermSet |= set(Yi) if * not in GramaDict: GramaDict* = set() GramaDict* |= set(Y) # 生成产生式集TermSet -= NonTermSet print(非终结符:, NonTermSet) print(终结符:, TermSet) getFirst() getFollow() print(FIRST集:) for k in NonTermSet: print( FIRST, k, : , Firstk) print(FOLLOW集:) for k, v in Follow.items(): print( FO
25、LLOW, k, : , v) TermSet -= set(Epsilon) TermSet |= set(EndSym) getAnalysisList() analyzer()init()运行结果:LR(0)分析器program.t*t 中存放要分析的文法:*-SS-BBB-aBB-b输入串:abab代码:VN = # 非终结符VT = # 终结符NFA = # NFA表DFA = # DFA表grammar = # 读入的文法doted_grammar = # 加点后的文法VN2Int = # 非终结符映射VT2Int = # 终结符映射action = # action表goto =
26、 # goto表DFA_node = # DFA节点表status_stack = # 状态栈symbol_stack = # 符号栈now_state = # 栈顶状态input_ch = # 栈顶字符input_str = # 输入串location = 0 # 输入位置now_step = 0 # 当前步骤# 读取文法def read_grammar(file_name): global grammar with open(file_name, r) as file: for line in file: line = line.replace(n, ) grammar.append(li
27、ne) file.close()# 找到终结符和非终结符def find_term_non(): global grammar n = int(len(grammar) temp_vt = l = 0 for i in range(n): *, Y = grammari.split(-) if * not in VN: VN.append(*) VN2Int.update(*: l) l += 1 for Yi in Y: temp_vt.append(Yi) m = 0 for i in temp_vt: if i not in VN and i not in VT: VT.append(i
28、) VT2Int.update(i: m) m += 1 VT.append(#) VT2Int.update(#: m)# 在字符串*个位置加点def add_char2str(grammar_i, i): grammar_i = grammar_i0:i + . + grammar_ii:len(grammar_i) return grammar_i# 给文法加点def add_dot(): global doted_grammar j = 0 n = 0 for i in grammar: for k in range(len(i) - 2): doted_grammar.append(
29、) doted_grammarn.append(add_char2str(i, k + 3) doted_grammarn.append(false) n += 1 j += 1# 显示加点后的文法def print_doted_grammar(): print(加点后的文法) j = 1for i in doted_grammar: print(%d.%s % (j, i0) j += 1# 显示读入文法def print_read_grammar(): print(读入的文法) j = 0 for i in grammar: print(%d)%s % (j, i) j += 1# 初始化
30、NFAdef init_NFA(): global NFA for row in range(len(doted_grammar): NFA.append() for col in range(len(doted_grammar): NFArow.append()# 找到点的位置def find_pos_point(one_grammar): return one_grammar.find(.)# 文法是否以start开头,以.开场defis_start(grammar_i, start): if grammar_i0.find(start, 0, 1) + grammar_i0.find(.
31、, 3, 4) = 3: return True else: return False# 查找以start开头,以.开场的文法,返回个数def find_node(start, grammar_id): num = 0 for i in doted_grammar: if is_start(i, start): grammar_idnum = doted_grammar.inde*(i) num += 1 return num# 构造NFAdef make_NFA(): global NFA grammar_id = for i in range(len(doted_grammar): gra
32、mmar_id.append() init_NFA() i = 0 for grammar_i in doted_grammar: pos_point = find_pos_point(grammar_i0) # 找到点的位置if not pos_point + 1 = len(grammar_i0): NFAii + 1 = grammar_i0pos_point + 1 if grammar_i0pos_point + 1 in VN: # 点后面跟着非终结符j = find_node(grammar_i0pos_point + 1, grammar_id) for k in range(
33、j): NFAigrammar_idk = * add_more(i, grammar_idk) i += 1# 查找关联def add_more(i, j): global NFA grammar_id = for k in range(len(doted_grammar): grammar_id.append() pos_point = find_pos_point(doted_grammarj0) if not pos_point + 1 = len(doted_grammarj0): if doted_grammarj0pos_point + 1 in VN: j = find_nod
34、e(doted_grammarj0pos_point + 1, grammar_id) for k in range(j): NFAigrammar_idk = * add_more(i, grammar_idk)# 显示NFAdef print_NFA(): global NFA, doted_grammar print(NFA邻接矩阵) print(end= ) for i in range(len(doted_grammar): print(%4d % (i + 1), end=) print() for i in range(len(doted_grammar): print(, en
35、d=) print() for i in range(len(doted_grammar): print(%3d| % (i + 1), end=) for j in range(len(doted_grammar): print(%4s % NFAij, end=) print() for l in range(len(doted_grammar): print(, end=) print()# 初始化DFAdef init_DFA(): global DFA for row in range(len(doted_grammar): DFA.append() for col in range
36、(len(doted_grammar): DFArow.append()# 连接def add_state(to, fro): for i in range(len(doted_grammar): if not NFAtoi = and not NFAtoi = *: DFAtoi = NFAtoi if not NFAfroi = and not NFAfroi = *: # from可连接的点DFAtoi = NFAfroi# 构造DFAdef make_DFA(): global NFA, doted_grammar, DFA_node init_DFA() for i in range
37、(len(doted_grammar): DFA_node.append() for j in range(len(doted_grammar): DFA_nodei.append() for i in range(len(doted_grammar): if doted_grammari1 = false: k = 0 DFA_nodeik = doted_grammari0 k += 1 doted_grammari1 = true for j in range(len(doted_grammar): if NFAij = *: # 有弧DFA_nodeik = doted_grammar
38、j0 k += 1 doted_grammarj1 = true add_state(i, j)# 显示DFAdef print_DFA(): global DFA, doted_grammar print(DFA邻接矩阵) print(end= ) for i in range(len(doted_grammar): print(%4d % (i + 1), end=) print() for i in range(len(doted_grammar): print(, end=) print() for i in range(len(doted_grammar): print(%3d| %
39、 (i + 1), end=) for j in range(len(doted_grammar): print(%4s % DFAij, end=) print() for l in range(len(doted_grammar): print(, end=) print()# 初始化LR分析表def init_LR_table(): global doted_grammar, action, goto for i in range(len(doted_grammar): action.append() goto.append() for j in range(len(VT): actio
40、ni.append() for j in range(len(VN): gotoi.append(-1)# 有无规约项def need_protocol(point): global DFA_node if not DFA_nodepoint0 = : for i in range(len(doted_grammar): if DFA_nodepointi.endswith(.): return DFA_nodepointi else: return None else: return None# 根据文法内容找到文法编号def find_grammar(string): global gra
41、mmar tmp = string0: len(string) - 1 for i in range(len(grammar): if tmp = grammari: return i# 填充LR分析表def fill_LR_table(): global doted_grammar, VT2Int, VN2Int, VN init_LR_table() for i in range(len(doted_grammar): if need_protocol(i): num = find_grammar(need_protocol(i) tmp = r + str(num) for j in r
42、ange(len(VT): if i = 1: actioniVT2Int# = acc else: actionij = tmp else: for j in range(len(doted_grammar): if not DFAij = : if DFAij in VN: gotoiVN2Int.get(DFAij, -1) = j else: tmp = s + str(j) actioniVT2Int.get(DFAij, -1) = tmp# 显示LR分析表def print_LR_table(): global VT, VN, doted_grammar, action, got
43、o # 表头print(LR分析表) print(tt|t, end=) print(%3s % ) * (len(VT) - 2), end=) print(Action, end=) print(%3s % ) * (len(VT) - 2), end=) print(t|t, end=) print(%3s % ) * (len(VN) - 2), end=) print(GOTO, end=) print(%3s % ) * (len(VN) - 2), end=) print(t|) print(ttt, end=) for i in VT: print(%3st % i, end=
44、) print(t|t, end=) k = 0 for i in VN: if not k = 0: print(%3st % i, end=) k += 1 print(t|) for i in range(len(doted_grammar): print(, end=) print() # 表体for i in range(len(doted_grammar): print(%5dt|t % i, end=) for j in range(len(VT): print(%4s % actionij, end=) print(t|t, end=) for j in range(len(V
45、N): if not j = 0: if not gotoij = -1: print(%4s % gotoij, end=) else: print(t, end=) print(t|) for i in range(len(doted_grammar): print(, end=) print()# 判断分析是否完成def is_end(): if input_strlocation:len(input_str) = #: if symbol_stack-1 = * and symbol_stack-2 = #: return True else: return False else: r
46、eturn False# 读入输入串def read_input(): global input_str input_str = input(输入串:) + # 输出def output(): global now_step, status_stack, symbol_stack, input_str, now_state print(%dtt % now_step, end=) now_step += 1 print(%-20s % status_stack, end=) print(%-25s % symbol_stack, end=) print(%-22s % input_strloc
47、ation:len(input_str), end=)# 统计产生式右部的个数def count_right_num(grammar_i): return len(grammar_i) - 3# 规约def do_stipulations(): global status_stack, input_str, symbol_stack, location, now_state, input_ch print(分析过程) print(步骤tt, end=) print(%-17s % 状态栈, end=) print(%-22s % 符号栈, end=) print(%-20s % 输入串, end=) print(动作说明) for i in range(len(doted_grammar): print(, end=) print() symbol_sta
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 银行员工业务培训规范制度
- 银行内部调查与处理制度
- 清华大学物理学课件-牛顿和力学的成熟
- 【大学课件】通信技术入门
- 突发环境事件应急预案十三篇
- 酒店实习报告1000字左右(30篇)
- 八年级轴对称图形复习课课件
- 车企电商化之路-构建一站式汽车生活服务平台案例报告
- 关于扶不扶问题的道德讨论
- 《认识工作世界》课件
- 期末测试卷(一)2024-2025学年 人教版PEP英语五年级上册(含答案含听力原文无听力音频)
- 2023-2024学年广东省深圳市南山区八年级(上)期末英语试卷
- 2024广西专业技术人员继续教育公需科目参考答案(100分)
- 2024年上海市中考语文备考之150个文言实词刷题表格及答案
- 2024年汉口银行股份有限公司招聘笔试冲刺题(带答案解析)
- 中医跨文化传播智慧树知到期末考试答案章节答案2024年浙江中医药大学
- 2024年日历表(空白)(一月一张-可编辑做工作日历)
- 广东省中山市2023-2024学年四年级上学期期末数学试卷
- 2022-2024年国际经济与贸易专业人才培养调研报告
- 剪刀式升降车专项施工方案
- 慢性肾衰中医护理方案
评论
0/150
提交评论