




版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、計(jì)算機(jī)科學(xué)與通信工程學(xué)院編譯原理實(shí)驗(yàn)報(bào)告題目: 1.詞法分析器2. LL(1)分析器 3. LR(0)分析器班級(jí): 姓名: 學(xué)號(hào): 指導(dǎo)老師: 2017年 月 目錄一、實(shí)驗(yàn)題目1二、實(shí)驗(yàn)?zāi)康暮鸵?三、代碼實(shí)現(xiàn)2四、總結(jié)27一、 實(shí)驗(yàn)題目1. 詞法分析器分析一段程序代碼,將代碼中的單詞符號(hào)分解出來(lái),并對(duì)其進(jìn)行檢查,輸出token表和error表2. LL(1)文法分析器分析給定文法。求出文法的FIRST集,F(xiàn)OLLOW集,并構(gòu)建分析表,對(duì)給定輸入串進(jìn)行分析。3. LR(0)文法分析器分析給定文法。用_CLOSURE方法構(gòu)造文法的LR(0)項(xiàng)目集規(guī)范族,根據(jù)狀態(tài)轉(zhuǎn)換函數(shù)GO構(gòu)造出文法的DFA,并
2、轉(zhuǎn)換為分析表,對(duì)給定輸入串進(jìn)行分析。二、 實(shí)驗(yàn)?zāi)康暮鸵?. 學(xué)會(huì)詞法分析器的實(shí)現(xiàn)思路。2. 學(xué)會(huì)求解FIRST集, FOLLOW集,構(gòu)造LL(1)分析表。3. 學(xué)會(huì)_CLOSURE方法, 狀態(tài)轉(zhuǎn)換函數(shù)GO, 構(gòu)造LR(0)分析表。三、 代碼實(shí)現(xiàn)1. 詞法分析器program.txt 中存放要分析的文法:E->TRR->+TR|-TR|T->FGG->*FG|/FG|F->(E)|i代碼:KEYWORD_LIST = 'while', 'if', 'else', 'switch', 'case
3、'SEPARATOR_LIST = '', ':', ',', '(', ')', '', '', '', ''OPERATOR_LIST1 = '+', '-', '*'OPERATOR_LIST2 = '<=', '<', '=', '=', '>', '>='CATEGOR
4、Y_DICT = # KEYWORD "while": "while": "", "if": "if": "", "else": "else": "", "switch": "switch": "", "case": "case": "", # OPERATOR "+": &qu
5、ot;+": "", "-": "-": "", "*": "*": "", "<=": "relop": "LE", "<": "relop": "LT", ">=": "relop": "GE", ">": "r
6、elop": "GT", "=": "relop": "EQ", "=": "=": "", # SEPARATOR "": "": "", ":": ":": "", ",": ",": "", "(": "(": "
7、", ")": ")": "", "": "": "", "": "": "", "": "": "", "": "": "",CONSTANTTABLE = TOKENTABLE = OPERATORTABLE = KEYWORDTABLE = SEPARATORTABLE = UNDE
8、FINEDTABLE = # READ FILEdef read_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) except IOError as e: print(e) exit() finally: file.close() return temp_str.strip() +
9、 " "# GETBEdef getbe(): global token getchar() token = "" return# GETCHARdef getchar(): global character global location while all_stringlocation = " ": location = location + 1 character = all_stringlocation return character# LINK TOKENdef concatenation(): global token
10、global character token = token + character# IS NUMBERdef digit(): if '0' <= character <= '9': return True return False# IS ALPHABETdef letter(): if 'A' <= character <= 'Z' or 'a' <= character <= 'z': return True return False# IS IDENT
11、IFIERdef reserve(): if token in KEYWORD_LIST: return CATEGORY_DICTtoken else: return 0# RETRACTdef retract(): global location global character # location = location - 1 character = "" return# MAIN FUNCTIONdef main(): global token global character global location s = getchar() getbe() if
12、39;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("這是標(biāo)識(shí)符:'", token, "':'", TO
13、KENTABLE.index(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("
14、;這是常數(shù):'", token, "':'", CONSTANTTABLE.index(token), "'") elif s in OPERATOR_LIST1: location = location + 1 OPERATORTABLE.append(s) print("這是單操作符:", CATEGORY_DICTs) elif s in OPERATOR_LIST2: location = location + 1 character = all_stringlocation if c
15、haracter = '=': OPERATORTABLE.append(s + character) print("這是雙操作符:", CATEGORY_DICTs + character) else: retract() location = location + 1 OPERATORTABLE.append(s) print("這是單操作符:", CATEGORY_DICTs) elif s in SEPARATOR_LIST: location = location + 1 SEPARATORTABLE.append(s) pri
16、nt("這是分隔符:", CATEGORY_DICTs) else: location += 1 UNDEFINEDTABLE.append(s) print("error:undefined identity :'", s, "'")if _name_ = '_main_': character = "" token = "" all_string = read_file("program.txt", "r") locat
17、ion = 0 while location + 1 < len(all_string): main() print('KEYWORDTABLE:', KEYWORDTABLE) print('TOKENTABLE:', TOKENTABLE) print('CONSTANTTABLE:', CONSTANTTABLE) print('OPERATORTABLE:', OPERATORTABLE) print('SEPARATORTABLE:', SEPARATORTABLE)運(yùn)行結(jié)果:2. LL(1)分析器
18、program.txt 中存放要分析的文法:E->TRR->+TR|-TR|T->FGG->*FG|/FG|F->(E)|i輸入串:i+i*i代碼:NonTermSet = set() # 非終結(jié)符集合TermSet = set() # 終結(jié)符集合First = # First集Follow = # Follow集GramaDict = # 處理過的產(chǎn)生式Code = # 讀入的產(chǎn)生式AnalysisList = # 分析表StartSym = "" # 開始符號(hào)EndSym = '#' # 結(jié)束符號(hào)為“#“Epsilon =
19、"" # 由于沒有epsilon符號(hào)用“”代替# 構(gòu)造First集def getFirst(): global NonTermSet, TermSet, First, Follow, FirstA for X in NonTermSet: FirstX = set() # 初始化非終結(jié)符First集為空 for X in TermSet: FirstX = set(X) # 初始化終結(jié)符First集為自己 Change = True while Change: # 當(dāng)First集沒有更新則算法結(jié)束 Change = False for X in NonTermSet: fo
20、r Y in GramaDictX: k = 0 Continue = True while Continue and k < len(Y): if not FirstYk - set(Epsilon) <= FirstX: # 沒有一樣的就添加,并且改變標(biāo)志 if Epsilon not in FirstYk and Yk in NonTermSet and k > 0: # Y1到Y(jié)i候選式都有存在 Continue = False else: FirstX |= FirstYk - set(Epsilon) Change = True if Epsilon not in
21、 FirstYk: Continue = False k += 1 if Continue: # X->或者Y1到Y(jié)k均有產(chǎn)生式 FirstX |= set(Epsilon) # FirstAY |= set(Epsilon)# 構(gòu)造Follow集def getFollow(): global NonTermSet, TermSet, First, Follow, StartSym for A in NonTermSet: FollowA = set() FollowStartSym.add(EndSym) # 將結(jié)束符號(hào)加入Follow開始符號(hào)中 Change = True while
22、 Change: # 當(dāng)Follow集沒有更新算法結(jié)束 Change = False for X in NonTermSet: for Y in GramaDictX: for i in range(len(Y): if Yi in TermSet: continue 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)中。 C
23、hange = True if Epsilon not in FirstYj: Flag = False break if Flag: if not FollowX <= FollowYi: # 步驟3 ->,把FOLLOW(A)加到FOLLOW(B)中 FollowYi |= FollowX Change = True# 構(gòu)造分析表def getAnalysisList(): for nonX in NonTermSet: AnalysisListnonX = dict() row = AnalysisListnonX flag = True for Y in GramaDict
24、nonX: for term in TermSet: if term in FirstY0 and term in FirstnonX: rowterm = nonX+'->'+Y if Epsilon in FirstnonX and flag: flag = False for tmp in FollownonX: rowtmp = nonX+'->'+Epsilon print('分析表:') for nonX in NonTermSet: print(' ', nonX, AnalysisListnonX)#
25、查詢分析表def findAnalysisList(non, ter): try: tmp = AnalysisListnonter X, Y = tmp.split('->') except Exception as e: print('find error ') # MA,a為空,發(fā)現(xiàn)語(yǔ)法錯(cuò)誤 print(e) pass return Y# 顯示格式def display(show_list): for item in show_list: print(' %-25s' % item, end='') print()#
26、LL(1)分析器def analyzer(): head = "Stack", "StackTop", 'NowStr', "InputStr", "Action" # inputStr = 'i+i*i' + EndSym inputStr = input("請(qǐng)輸入表達(dá)式:") + EndSym print('分析過程:') display(head) stack = location = 0 stack.append(EndSym) stack
27、.append(StartSym) stack_top = stack.pop() while stack_top != EndSym and location < len(inputStr): if stack_top in TermSet and inputStrlocation = stack_top: # x = a != '#', mess = '匹配,彈出棧頂符號(hào)' + stack_top + '并讀入輸入串的下一符號(hào)' + inputStrlocation + 1 display(stack, stack_top, input
28、Strlocation, inputStrlocation + 1: len(inputStr), mess) location += 1 stack_top = stack.pop() elif stack_top in NonTermSet and inputStrlocation in TermSet: # x為一非終結(jié)符A,則查MA,a result = findAnalysisList(stack_top, inputStrlocation) if result = Epsilon: # MA,a中的產(chǎn)生式為A->,只將A彈出 mess = '彈出棧頂符號(hào)' +
29、 stack_top + '因M' + stack_top + ',' + inputStrlocation + '中為' + stack_top mess = mess + '->,故不壓棧' else: # MA,a中的產(chǎn)生式右部符號(hào)串按逆序逐一壓入棧中 mess = '彈出棧頂符號(hào)' + stack_top + ',將M' + stack_top + ',' + inputStr location + '中的' + stack_top + '-&g
30、t;' + result + '的' + result mess = mess + '逆序壓棧' tmp_list = for char in result: tmp_list.append(char) tmp_list.reverse() stack.extend(tmp_list) display(stack, stack_top, inputStrlocation, inputStrlocation + 1: len(inputStr), mess) stack_top = stack.pop() else: break if stack_top
31、= EndSym and inputStrlocation = EndSym: # x = a = '#' 分析成功,分析器停止工作 display(, '#', '#', '', '匹配,分析成功') print() print('*') print('* Analysis Success *') print('*') else: print('Analysis Error')# 讀取文法def readGrammar(): try: file =
32、open('grammar.txt', 'r') for line in file: line = line.replace('n', "") Code.append(line) except IOError as e: print(e) exit() finally: file.close() return Code# 初始化def init(): global NonTermSet, TermSet, First, Follow, StartSym, Code Code = readGrammar() n = int(le
33、n(Code) print('產(chǎn)生式個(gè)數(shù):', n) StartSym = Code00 print("開始符號(hào):", StartSym) print('產(chǎn)生式:G', StartSym, ':') for i in range(n): X, Y = Codei.split('->') print(' ', Codei) NonTermSet.add(X) Y = Y.split('|') for Yi in Y: TermSet |= set(Yi) if X not i
34、n GramaDict: GramaDictX = set() GramaDictX |= set(Y) # 生成產(chǎn)生式集 TermSet -= NonTermSet print('非終結(jié)符:', NonTermSet) print('終結(jié)符:', TermSet) getFirst() getFollow() print("FIRST集:") for k in NonTermSet: print(' FIRST', k, ': ', Firstk) print("FOLLOW集:") fo
35、r k, v in Follow.items(): print(' FOLLOW', k, ': ', v) TermSet -= set(Epsilon) TermSet |= set(EndSym) getAnalysisList() analyzer()init()運(yùn)行結(jié)果:3. LR(0)分析器program.txt 中存放要分析的文法:X->SS->BBB->aBB->b輸入串:abab代碼:VN = # 非終結(jié)符VT = # 終結(jié)符NFA = # NFA表DFA = # DFA表grammar = # 讀入的文法doted_g
36、rammar = # 加點(diǎn)后的文法VN2Int = # 非終結(jié)符映射VT2Int = # 終結(jié)符映射action = # action表goto = # goto表DFA_node = # DFA節(jié)點(diǎn)表status_stack = # 狀態(tài)棧symbol_stack = # 符號(hào)棧now_state = '' # 棧頂狀態(tài)input_ch = '' # 棧頂字符input_str = '' # 輸入串location = 0 # 輸入位置now_step = 0 # 當(dāng)前步驟# 讀取文法def read_grammar(file_name): g
37、lobal grammar with open(file_name, 'r') as file: for line in file: line = line.replace('n', "") grammar.append(line) file.close()# 找到終結(jié)符和非終結(jié)符def find_term_non(): global grammar n = int(len(grammar) temp_vt = l = 0 for i in range(n): X, Y = grammari.split('->') if
38、 X not in VN: VN.append(X) VN2Int.update(X: 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) VT2Int.update(i: m) m += 1 VT.append('#') VT2Int.update('#': m)# 在字符串某個(gè)位置加點(diǎn)def add_char2str(grammar_i, i): grammar_i = grammar_i0
39、:i + '.' + grammar_ii:len(grammar_i) return grammar_i# 給文法加點(diǎn)def add_dot(): global doted_grammar j = 0 n = 0 for i in grammar: for k in range(len(i) - 2): doted_grammar.append() doted_grammarn.append(add_char2str(i, k + 3) doted_grammarn.append('false') n += 1 j += 1# 顯示加點(diǎn)后的文法def prin
40、t_doted_grammar(): print('-加點(diǎn)后的文法-') j = 1 for 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# 初始化NFAdef init_NFA(): global NFA for row in range(len(doted_gram
41、mar): NFA.append() for col in range(len(doted_grammar): NFArow.append('')# 找到點(diǎn)的位置def find_pos_point(one_grammar): return one_grammar.find('.')# 文法是否以start開頭,以'.'開始def is_start(grammar_i, start): if grammar_i0.find(start, 0, 1) + grammar_i0.find('.', 3, 4) = 3: return
42、True else: return False# 查找以start開頭,以'.'開始的文法,返回個(gè)數(shù)def find_node(start, grammar_id): num = 0 for i in doted_grammar: if is_start(i, start): grammar_idnum = doted_grammar.index(i) num += 1 return num# 構(gòu)造NFAdef make_NFA(): global NFA grammar_id = for i in range(len(doted_grammar): grammar_id.ap
43、pend('') init_NFA() i = 0 for grammar_i in doted_grammar: pos_point = find_pos_point(grammar_i0) # 找到點(diǎn)的位置 if not pos_point + 1 = len(grammar_i0): NFAii + 1 = grammar_i0pos_point + 1 if grammar_i0pos_point + 1 in VN: # 點(diǎn)后面跟著非終結(jié)符 j = find_node(grammar_i0pos_point + 1, grammar_id) for k in rang
44、e(j): NFAigrammar_idk = '*' add_more(i, grammar_idk) i += 1# 查找關(guān)聯(lián)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 +
45、 1 in VN: j = find_node(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 +
46、 1), end='') print() for i in range(len(doted_grammar): print('-', end='') 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(dot
47、ed_grammar): print('-', end='') print()# 初始化DFAdef init_DFA(): global DFA for row in range(len(doted_grammar): DFA.append() for col in range(len(doted_grammar): DFArow.append('')# 連接def add_state(to, fro): for i in range(len(doted_grammar): if not NFAtoi = '' and not
48、NFAtoi = '*': DFAtoi = NFAtoi if not NFAfroi = '' and not NFAfroi = '*': # from可連接的點(diǎn) DFAtoi = NFAfroi# 構(gòu)造DFAdef make_DFA(): global NFA, doted_grammar, DFA_node init_DFA() for i in range(len(doted_grammar): DFA_node.append() for j in range(len(doted_grammar): DFA_nodei.append(
49、'') 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_grammarj0 k += 1 doted_grammarj1 = 'true' add_state(i, j)# 顯示DFAdef print_DFA(): global DFA, doted_g
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 山東省濟(jì)南市鋼城區(qū)實(shí)驗(yàn)學(xué)校2024年數(shù)學(xué)八年級(jí)第一學(xué)期期末經(jīng)典試題含解析
- 山東省龍口市蘭高鎮(zhèn)蘭高學(xué)校2024年八上數(shù)學(xué)期末調(diào)研模擬試題含解析
- 浙江省杭州市拱墅區(qū)2025屆物理八年級(jí)第一學(xué)期期末統(tǒng)考試題含解析
- 菜鳥驛站加盟店轉(zhuǎn)租合同模板解析
- 中小企業(yè)的創(chuàng)業(yè)環(huán)境與發(fā)展策略研究
- 產(chǎn)品特點(diǎn)與競(jìng)爭(zhēng)優(yōu)勢(shì)剖析
- 2025年《中華人民共和國(guó)藥品管理法》培訓(xùn)試卷含答案
- 2025至2030馬鈴薯全粉市場(chǎng)發(fā)展趨勢(shì)分析與未來(lái)投資戰(zhàn)略咨詢研究報(bào)告
- 我會(huì)表達(dá)愛-心理健康教育
- 2025至2030中國(guó)自卸汽車行業(yè)發(fā)展趨勢(shì)分析與未來(lái)投資戰(zhàn)略咨詢研究報(bào)告
- 初三化學(xué)上冊(cè)第一單元測(cè)試題(含答案)
- 移動(dòng)通信網(wǎng)絡(luò)優(yōu)化服務(wù)合同
- JBT 14449-2024 起重機(jī)械焊接工藝評(píng)定(正式版)
- DL-T5017-2007水電水利工程壓力鋼管制造安裝及驗(yàn)收規(guī)范
- 海上風(fēng)電場(chǎng)選址與環(huán)境影響評(píng)估
- 《陸上風(fēng)電場(chǎng)工程概算定額》(NB-T 31010-2019)
- 《早期教育概論》課程標(biāo)準(zhǔn)
- 藥物分析年終述職報(bào)告
- 農(nóng)發(fā)行信貸業(yè)務(wù)考試題庫(kù)題庫(kù)附答案
- 精神分裂癥護(hù)理查房
- 建筑物聯(lián)網(wǎng)工程綜合實(shí)訓(xùn) 課件 第1-3章 物聯(lián)網(wǎng)技術(shù)導(dǎo)論、物聯(lián)網(wǎng)領(lǐng)域的關(guān)鍵技術(shù)、智能建造工程場(chǎng)景中的物聯(lián)網(wǎng)
評(píng)論
0/150
提交評(píng)論