語(yǔ)法分析器的設(shè)計(jì)

1、 編譯原理 語(yǔ)法分析器的設(shè)計(jì)u 根據(jù)某一文法編制調(diào)試 LL （ 1 ）分析程序，以便對(duì)任意輸入的符號(hào)串進(jìn)行分析。u 構(gòu)造預(yù)測(cè)分析表，并利用分析表和一個(gè)棧來(lái)實(shí)現(xiàn)對(duì)上述程序設(shè)計(jì)語(yǔ)言的分析程序。u 分析法的功能是利用LL（1）控制程序根據(jù)顯示棧棧頂內(nèi)容、向前看符號(hào)以及LL（1）分析表，對(duì)輸入符號(hào)串自上而下的分析過(guò)程。 實(shí)驗(yàn)設(shè)計(jì)方案 1、設(shè)計(jì)思想（1）、LL（1）文法的定義LL(1)分析法屬于確定的自頂向下分析方法。LL(1)的含義是：第一個(gè)L表明自頂向下分析是從左向右掃描輸入串，第2個(gè)L表明分析過(guò)程中將使用最左推導(dǎo)，1表明只需向右看一個(gè)符號(hào)便可決定如何推導(dǎo)，即選擇哪個(gè)產(chǎn)生式(規(guī)則)進(jìn)行推導(dǎo)。LL(1

2、)文法的判別需要依次計(jì)算FIRST集、FOLLOW集和SELLECT集,然后判斷是否為L(zhǎng)L(1)文法,最后再進(jìn)行句子分析。需要預(yù)測(cè)分析器對(duì)所給句型進(jìn)行識(shí)別。即在LL(1)分析法中，每當(dāng)在符號(hào)棧的棧頂出現(xiàn)非終極符時(shí)，要預(yù)測(cè)用哪個(gè)產(chǎn)生式的右部去替換該非終極符；當(dāng)出現(xiàn)終結(jié)符時(shí)，判斷其與剩余輸入串的第一個(gè)字符是否匹配，如果匹配，則繼續(xù)分析，否則報(bào)錯(cuò)。LL(1)分析方法要求文法滿足如下條件：對(duì)于任一非終極符A的兩個(gè)不同產(chǎn)生式Aàa,Aàb，都要滿足下面條件：SELECT(Aàa)SELECT(Aàb)=Æ（2）、預(yù)測(cè)分析表構(gòu)造LL(1)分析表的作用是對(duì)當(dāng)

3、前非終極符和輸入符號(hào)確定應(yīng)該選擇用哪個(gè)產(chǎn)生式進(jìn)行推導(dǎo)。它的行對(duì)應(yīng)文法的非終極符，列對(duì)應(yīng)終極符，表中的值有兩種：一是產(chǎn)生式的右部的字符串，一是null。若用M表示LL(1)分析表，則M可表示如下：M: VN×VTàPErrorM(A, t) = Aà，當(dāng)tÎselect(Aà) ，否則M(A, t) = Error其中P表示所有產(chǎn)生式的集合。（3） 、語(yǔ)法分析程序構(gòu)造LL(1)分析中X為符號(hào)棧棧頂元素，a為輸入流當(dāng)前字符，E為給定測(cè)試數(shù)據(jù)的開(kāi)始符號(hào)，#為句子括號(hào)即輸入串的括號(hào)。分析表用一個(gè)二位數(shù)組M表示，數(shù)組元素MA，a中的下標(biāo)A表示非終結(jié)符，a

4、為終結(jié)符或句子括號(hào)#，二維數(shù)組中存放的是一條關(guān)于A 的產(chǎn)生式，表明當(dāng)非終結(jié)符A向下推導(dǎo)時(shí)，面臨輸入符a時(shí)，所采用的候選產(chǎn)生式，當(dāng)元素內(nèi)容無(wú)產(chǎn)生式時(shí)，則表明用A 的左部向下推導(dǎo)時(shí)出現(xiàn)了不該出現(xiàn)的符號(hào)，因此元素內(nèi)容轉(zhuǎn)向出錯(cuò)處理的信息。LL(1)分析過(guò)程主要包括以下四個(gè)動(dòng)作：替換：當(dāng)XÎVN時(shí)選相應(yīng)產(chǎn)生式的右部b去替換X。此時(shí)X出棧，b逆序入棧。匹配：當(dāng)XÎVT時(shí)它與a進(jìn)行匹配，其結(jié)果可能成功，也可能失敗，如果成功則符號(hào)棧中將X退棧并將輸入流指針向前移動(dòng)一位，否則報(bào)錯(cuò)。接受：當(dāng)格局為（#，空#）時(shí)報(bào)告分析成功。報(bào)錯(cuò)：出錯(cuò)后，停止分析。并給出相應(yīng)的錯(cuò)誤提示信息。2.程序流程圖：3、

5、實(shí)驗(yàn)程序（1）分析棧類：public class stack private char s;private int top;public stack() s = new char200;s0 = '#'top = 0;char getTop() return stop;void push(String str) for (int i = str.length() - 1; i >= 0; i-) s+top = str.charAt(i);void clear() top = 0;char pop() if (top != 0) top-;return stop;publ

6、ic String toString() String tmp = ""for (int i = 0; i <= top; i+) tmp += si;return tmp;（2）語(yǔ)法分析器類：public class anlysis /分析表private String tab = "$", "+", "-", "*", "/", "(", ")", "i", "#" , "E&

7、quot;, "$", "$", "$", "$", "TG", "$", "TG", "$" , "G", "+TG", "-TG", "$", "$", "$", "", "$", "" , "T", "$", &q

8、uot;$", "$", "$", "FS", "$", "FS", "$" , "S", "", "", "*FS", "/FS", "$", "", "$", "" , "F", "$", "$", "$"

9、, "$", "(E)", "$", "i", "$" ;private String input; /input中存放輸入的表達(dá)式private StringBuffer tempBuffer; /存放要輸出的字符串private int ptr, row, col, step; /指針，預(yù)測(cè)表中的行，列，當(dāng)前步驟private boolean symbol;private stack stack;public anlysis()stack =new stack();tempBuffer =

10、new StringBuffer();symbol=true;input=""row=1;ptr=0;step=1;/methods./public int column(char c) /判斷預(yù)測(cè)表中的列switch (c) case '+':return 1;case '-':return 2;case '*':return 3;case '/':return 4;case '(':return 5;case ')':return 6;case 'i':ret

11、urn 7;case '#':return 8;default:return -1;public int line(char c) /判定預(yù)測(cè)表中的行switch (c) case 'E':return 1;case 'G':return 2;case 'T':return 3;case 'S':return 4;case 'F':return 5;default:return -1;public void pri(String str) tempBuffer.append(String.forma

12、t("%-8d%-20s%-20s%-20srn", step, stack.toString(), input.substring(ptr), str); step+;public void analyse() stack.push(tabrow0); /預(yù)測(cè)表中的第一個(gè)元素Epri("初始化");String tmp;char ctmp; /棧頂元素while (!(input.charAt(ptr) = '#' && stack.getTop() = '#') ctmp = stack.getTop(

13、);if (input.charAt(ptr) = ctmp) /與棧頂元素比較stack.pop();ptr+;pri("" + ctmp + "匹配");continue;col = column(input.charAt(ptr);if (col = -1) symbol = false;pri("未定義的字符");ptr+;continue;row = line(ctmp);if (row = -1) symbol = false;pri("出錯(cuò)");stack.pop();if (input.charAt

14、(ptr) != '#') ptr+;continue;tmp = tabrowcol;if (tmp.charAt(0) = '$') symbol = false;pri("出錯(cuò)");stack.pop();if (input.charAt(ptr) != '#') ptr+; else if (tmp.charAt(0) = '') stack.pop();pri("" + ctmp + "->" + ''); else stack.pop()

15、;stack.push(tmp);pri("" + ctmp + "->" + tmp);public String work(String ts) input = ts; input = input.trim()+ '#'symbol = true;stack.clear();tempBuffer.append("rn步驟 分析棧 剩余輸入棧 所用產(chǎn)生式rn");analyse();if (symbol) tempBuffer.append("r是正確的符號(hào)串r");return tempB

16、uffer.toString(); else tempBuffer.append("r不是正確的符號(hào)串r");return tempBuffer.toString();/gets and sets/public StringBuffer getTempBuffer() return tempBuffer;public void setTempBuffer(StringBuffer tempBuffer) this.tempBuffer = tempBuffer;public stack getStack() return stack;public void setStack

17、(stack stack) this.stack = stack;public String getTab() return tab;public void setTab(String tab) this.tab = tab;public String getInput() return input;public void setInput(String ns) this.input = ns;public int getPtr() return ptr;public void setPtr(int ptr) this.ptr = ptr;public int getRow() return

18、row;public void setRow(int row) this.row = row;public int getCol() return col;public void setCol(int col) this.col = col;public int getStep() return step;public void setStep(int step) this.step = step;public boolean isBoo() return symbol;public void setBoo(boolean boo) this.symbol = boo;（3）WINDOW窗體類

19、：import java.awt.BorderLayout;import java.awt.GridLayout;import java.awt.Panel;import javax.swing.JFrame;import javax.swing.JScrollPane;public class gui extends javax.swing.JFrame /* Creates new form gui */private javax.swing.JButton jButton1;private javax.swing.JLabel jLabel1;private javax.swing.JL

20、abel jLabel2;private javax.swing.JTextArea jTextArea1;private javax.swing.JTextField jTextField1;private Panel p1=new Panel();private Panel p2=new Panel();public gui() initComponents();private void initComponents() jLabel1 = new javax.swing.JLabel();jTextField1 = new javax.swing.JTextField();jLabel2

21、 = new javax.swing.JLabel();jTextArea1 = new javax.swing.JTextArea(20,30);jButton1 = new javax.swing.JButton();setDefaultCloseOperation(javax.swing.WindowConstants.EXIT_ON_CLOSE);jLabel1.setText("本程序只能對(duì)由'+','-','*','/','(',')','i'構(gòu)成的以'

22、#'結(jié)尾的字符串進(jìn)行分析。請(qǐng)輸入要翻譯的表達(dá)式:");jLabel2.setText("分析結(jié)果:");jButton1.setText("分析");jButton1.addActionListener(new java.awt.event.ActionListener() public void actionPerformed(java.awt.event.ActionEvent evt) jButton1ActionPerformed(evt););final GridLayout gridLayout = new GridLayo

23、ut(0, 1);/創(chuàng)建表格布局管理器gridLayout.setVgap(0);/設(shè)置組件之間垂直距離gridLayout.setHgap(0);/設(shè)置組件之間平行距離p1.setLayout(gridLayout);p1.add(jLabel1);p1.add(jTextField1);p2.add(jLabel2);p2.add(new JScrollPane(jTextArea1);getContentPane().add(p1, BorderLayout.NORTH);getContentPane().add(p2, BorderLayout.CENTER);getContentPane().add(jButton1, BorderLayo