LR語法分析概述
一．計算識別活前綴
二．計算LR項目集合識別活前綴的DFA
三．判斷是不是合法LR(0)文法
四．構(gòu)造SLR分析表
五．LR分析
采用的技術(shù)及平臺安裝
使用python語言，IDE為PyCharm，部署過程只需安裝python對應(yīng)版本，安裝IDE即可。
算法分析
一．計算識別活前綴
數(shù)據(jù)結(jié)構(gòu)：list數(shù)據(jù)結(jié)構(gòu)，用來存儲LR項目
算法：采用for循環(huán)遍歷的方法，對于每一個產(chǎn)生式添加‘.’，將結(jié)果添加到用于存儲LR項目的list數(shù)據(jù)結(jié)構(gòu)中。
二．計算LR項目集合識別活前綴的DFA
數(shù)據(jù)結(jié)構(gòu)：定義了兩個字典數(shù)據(jù)結(jié)構(gòu)C和DTran，分別用來存儲產(chǎn)生的DFA項目和狀態(tài)轉(zhuǎn)移關(guān)系，其中C，key為數(shù)字，代表狀態(tài)編號，value為list，表示LR項目的集合；DTran中key為數(shù)字，表示狀態(tài)編號，valu為一個list，而list中記錄了多個key-value值，表示經(jīng)過那個文法符號到達哪一個狀態(tài)。
算法：
1. 對所有未標記的狀態(tài)（這里采用比較的方法確定是否標記），求出當前狀態(tài)可以接受的字符有哪些，比如E->.E-T的可接受字符為非終結(jié)符E，再有可以接受字符的情況下，調(diào)用求下一狀態(tài)轉(zhuǎn)移的函數(shù)closure和goto，類似詞法分析中的最小子集法的步驟，得出狀態(tài)轉(zhuǎn)移。
2. 然后對求得的項目集與已標記的狀態(tài)集比較，看是否是新的狀態(tài)，若是，則加入狀態(tài)集C，若不是，則標記為舊狀態(tài)
3.在求完后記錄狀態(tài)轉(zhuǎn)移。
三．構(gòu)造first集合
數(shù)據(jù)結(jié)構(gòu)：，first集合和follow集合用字典來存儲，比如F作為key值，{+，-}作為value值,它是一個list集合表示F的first集合。
算法：
1.提取產(chǎn)生式左部和右部，倒序?qū)Ξa(chǎn)生式進行循環(huán)，在循環(huán)時進行三個條件的判斷，有一點要說明，比如條件三，要將已經(jīng)求得的first（A）加入到first（B）時，由于采用字典來表示，所以要訪問A的fist集合直接通過A這個key值就可以獲取。
2.在這一過程中，由于存在id和num這樣，由多個小寫字母構(gòu)成的終結(jié)符，需要特別的對他們進行識別，這里采用預(yù)先定義的方法，在Note.txt文件中表明了這類終結(jié)符，通過文件流提取他們，作為string，在程序中進行判斷。
3. 現(xiàn)在說明三個條件，條件一和條件二，簡單的將相應(yīng)內(nèi)容加入即可，對于條件三，首先需要在字符串頭部尾部加上ε，由于采用字典方法存儲first集合，所以在取文法的first集合時直接按key值取即可，然后進行相應(yīng)判斷。
四．構(gòu)造follow集合
數(shù)據(jù)結(jié)構(gòu)：follow集合用字典來存儲，比如F作為key值，{+，-}作為value值,它是一個list集合表示F的follow集合
算法：
1. 求follow集合的過程類似于求first集合，定義好字典follow后，求每個非終結(jié)符的follow集合元素集fl（list數(shù)據(jù)類型）。
2. 對非終結(jié)符正序循環(huán)，再循環(huán)體中，對三個條件進行判斷。對于條件一，簡單處理即可。對于條件二，找到A->aBb，后，因為這一步和條件三的判斷條件有重合之處，所以先判斷有沒有ε，若有，則取follow（A）加入fl，然后直接取first（b）,對first（b）循環(huán)加入fl，跳過ε，這就完成條件二和條件三一部分內(nèi)容的判斷。
3. 對于條件三，找到A->aB，follow（A）加入fl。最后在三個條件都判斷完成后，建立非終結(jié)符和fl的key-value聯(lián)系，即將其以字典形式存儲起來。
五．判斷是不是合法LR(0)文法
數(shù)據(jù)結(jié)構(gòu)：使用先前定義的字典結(jié)構(gòu)C，以及l(fā)ist類型的文法，字典類型的follow集合。
算法：對C中的所有的LR項目，采用循環(huán)比較的方法，即第一個和第二個，第三個，第n個比較，觀察兩兩之間是移進/歸約沖突還是歸約/歸約沖突，如果是第一種沖突，則比較’.’后的第一個字符和follow(B)（B是第二個LR項目的文法左部）是否有交集，若是第二種沖突，比較follow(A) ，follow(B)是否有交集。在沒有交集的情況下，才能說明該文法是合法的LR文法，否則不是。
六．構(gòu)造SLR分析表
數(shù)據(jù)結(jié)構(gòu)：使用字典C，字典DTran。Arow 和 grow表示action和goto一行的內(nèi)容集合list。
算法：
1.構(gòu)造一個方便進行坐標訪問的文法，用list，為后續(xù)計算服務(wù)。因為后續(xù)構(gòu)造需要用到使用坐標來定位產(chǎn)生式的文法。
2. 對每一個狀態(tài)轉(zhuǎn)移，如果縱坐標是非終結(jié)符，action[I,x]=Sj,如果不是，goto[I,x]=j
3.對于每個屬于本狀態(tài)的可規(guī)約項目，如果是初態(tài)的產(chǎn)生式，則action[I,#]=acc，如果不是，則按照規(guī)則對action和goto進行填寫，即添加相應(yīng)的內(nèi)容到arow和grow中。
4. 將arow和grow作為本狀態(tài)的有意義的內(nèi)容
七．LR分析
數(shù)據(jù)結(jié)構(gòu)：定義一個list表示stack棧，存儲三大格局中的棧內(nèi)容。使用action和go。
算法：
1. #判斷w的當前輸入是否是特殊字符，這是因為存在id，mod，num等多個字符表示一個終結(jié)符的情況。
2. 通過設(shè)定根據(jù)w的當前字符和棧頂元素查找action表的情況，將情況分為4種，分別是移進，歸約，成功，出錯。
3.在歸約條件中，注意計算棧頂元素時考慮id，num這種終結(jié)符。
4. 按照相應(yīng)條件設(shè)置操作，各部分操作不復(fù)雜，在移進時，將下一狀態(tài)當前輸入字符進棧；在歸約時，彈出棧頂相應(yīng)個數(shù)的字符，暴露出當前棧的棧頂狀態(tài)，將產(chǎn)生式左部符號進棧
，新棧頂元素進棧。
流程圖（繪制并說明算法流程）
程序運行截圖（根據(jù)實驗指導(dǎo)書第3節(jié)提供的內(nèi)容及要求顯示輸出結(jié)果，并提供對應(yīng)交互信息）
測試用例1：輸入abbcde
測試用例2：輸入abcde
測試用例3：id+id*id
程序模塊說明
程序分析（主要介紹編程中出現(xiàn)的錯誤以及修改的說明以及實驗心得）
1.由于first和follow集合與自上而下文法分析中的用法一樣，所以直接遷移代碼，體會到函數(shù)接口的重要性，因為要想使用上一個實驗的first和follow集合，要保證函數(shù)參數(shù)的一致。
2.經(jīng)過三次實驗的鍛煉，對于數(shù)據(jù)結(jié)構(gòu)的設(shè)計，算法流程的設(shè)計，以及結(jié)合編程語言自身的特點進行編程上，更加的靈活和得心應(yīng)手了，舉個例子，first和follow采用字典是非常合適的存儲方式，對于后續(xù)直接根據(jù)文法的非終結(jié)符取其first集合，非常方便。還有，action和goto表，采用字典方式存儲，可以達到只存儲有意義的數(shù)據(jù)，不浪費空間。
3. python函數(shù)的返回值可以是多個，按照下標來取即可，比如構(gòu)造移進歸約分析表時，函數(shù)返回action和goto兩個字典，可以通過下標0,1來取。
4．加深了對于上述各個算法的理解。
