编译原理-词法分析

编译原理实验报告 词法分析器与语法分析器 I. 问题描述 设计、编制并调试一个词法分析子程序，完成识别语言单词的任务； 设计、编制、调试一个语法分析程序，并用它对词法分析程序所提供的单词序列进行语法检查和结构分析。 ii. 设计简要描述 界面需求： 为了更加形象的模拟过程，此实验使用图形界面。要求从图形界面上输入输入串，点击词法分析，可以将词法分析后识别的单词符号显示，点击语法分析，可以将语法分析的堆栈过程显示，并且显示结果（是否是符合文法的句子），清空则可以将所有置空。 功能分析： 1、 由用户输入输入串； 2、 用户点击“词法分析”，可以将词法分析后识别的单词符号显示。 3、 用户点击语法分析，可以将语法分析的堆栈过程显示，并且显示结果（是否是符合文法的句子） 4、 用户点击清空，则将界面所有组件置为空 思路描述： 一、设计构想： 本实验决定编写一个简易C语言的词法分析器和语法分析器。使其能够识别while，if等关键字，可以判断赋值语句、条件语句、循环语句。 2、 文法分析 1、需要识别的关键字及其识别码有： 关键字 识别码 关键字 识别码 关键字 识别码 main 0 - 11 ； 22 int 1 * 12 > 23 char 2 / 13 < 24 if 3 ( 14 >= 25 else 4 ) 15 <= 26 for 5 [ 16 == 27 while 6 ] 17 != 28 ID 7 { 18 ERROR -1 NUM 8 } 19 = 9 , 20 2、 + 10 : 21 3、 文法 〈程序〉→ main()〈语句块〉 〈语句块〉→{〈语句串〉} 〈语句串〉→〈语句〉；〈语句串〉|〈语句〉； 〈语句〉→〈赋值语句〉|〈条件语句〉|〈循环语句〉 〈赋值语句〉→ ID =〈 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 达式〉; 〈条件语句〉→ if〈条件〉〈语句块〉 〈循环语句〉→ while〈条件〉〈语句块〉 〈条件〉→（〈表达式〉〈关系符〉〈表达式〉） 〈表达式〉→〈表达式〉〈运算符〉〈表达式〉|（〈表达式〉）|ID|NUM 〈运算符〉→+|-|*|/ 〈关系符〉→＜|＜＝|＞|＞＝|＝|！＞ 转化为符号表示： S→ main() K|空 K→ { C } C→Y；C |空 Y→F | T | X F→ ID = B T→ if J K X→ while J K J→（ B G B ） B→ B Z B |（ B ）| ID | NUM Z→ + | - | * | / G→＜ | ＜＝ | ＞ | ＞＝ | ＝＝ | ！＞ 表示含义： S：程序 K：语句块 C：语句串 Y：语句 F ：赋值语句 T：条件语句 X：循环语句 J：条件 B：表达式 I：项 Z ：运算符 G：关系符 4、 LL（1）分析表 （1），求出first集及follow集： FIRST(S)={mian} FIRST(K)={{} FIRST(C)= FIRST(Y)= {ID,if,while，空}； FIRST(Y)= FIRST(F)+ FIRST(T)+ FIRST(X)={ID,if,while}; FIRST(F)={ID}; FIRST(T)={if}; FIRST(X)={while}; FIRST(J)= FIRST(B)={}; FIRST(B)={(,ID,NUM }； FIRST(Z)={+，-，*，/} FIRST(G)={ ＜， ＜= ，＞，＞=，＝＝，！= }; FOLLOW（S）={#}； FOLLOW（K）={；}； FOLLOW（C）={}}； FOLLOW（Y）={；} FOLLOW（F）={；}; FOLLOW（T）={；}; FOLLOW（X）={；}; FOLLOW（J）={{，；}； FOLLOW（B）={+，-，*，/，），＜， ＜= ，＞，＞=，＝＝，！=,;}； FOLLOW（B’）={+，-，*，/，），＜， ＜= ，＞，＞=，＝＝，！=,;}； FOLLOW（Z）={(,ID,NUM }; FOLLOW（G）={(,ID,NUM }; （2）消除左递归，拆分文法关系并编号 0、S→ 空 1、S→ main() K 2、K→ { C } 3、 C→Y；C 4、 C→空 5、Y→ F 6、Y→ T 7、Y→ X 8、F→ ID = B 9、 T→ if J K 10、X→ while J K 11、 J→（ B G B ） 12、 B→ （ B ）B' 13、B→ ID B' 14、B→ NUM B' 15、B'→ BZB B' 16、B'→ 空 17、 Z→ + 18、 Z→ - 19、 Z→ * 20、 Z→ / 21、 G→ < 22、 G→ <= 23、 G→ > 24、 G→ >= 25、 G→ == 26、 G→ != （3）构造LL（1）分析表 （注：在表中用上一步的编号表示所需要的产生式） main 空 ( ) { } ; = if while ID num + - * / < <= > >= == != # S 1 0 K 2 C 4 4 3 3 3 Y 6 7 5 F 8 T 9 X 10 J 11 B 12 13 14 B' 16 15 16 16 15 15 16 16 16 16 16 16 16 16 16 16 Z 17 18 19 20 G 21 22 23 24 25 26 iii. 详细设计描述 项目构架： 各函数功能介绍： 1、word.wordList包（存储了关键字）： word:此类是定义了存储关键字的结构：包括String型的关键字,和int型的识别符。 wordList：此类存储了29个关键字，在构造函数中初始化。 2、word包（进行词法分析）中： basicFunction:此类定义了做词法分析的基本函数： GetChar()将下一输入字符读到ch中，搜索知识器前移一个字符位置 GetBC()；检查ch中的字符是否为空白。若是，则调用GetChar直至不 是字符为止 Concat()；将ch中的字符连接到strToken之后 IsLetter()；判断ch中的字符是否为字母 IsDigit()；判断ch中的字符是否为数字 Reserve()；对strToken中的字符创查找保留字表，若是则返回它的编码，否则返回0 Retract()；将搜索指示器回调一个字符位置 RetractStr()；将strToken置空 lexAnalysis：此类是用来进行词法分析，将分析后的单词存入word数组中，（注：在词法分析中，若是一串字母，则认为是ID，若是数字，则认为是NUM。存储的时候识别符分别存ID与NUM的识别符，但是内容仍然是自己的内容） 其中的wordAnalysis函数就是词法分析函数（具体实现请看后面的重要函数分析） 3、stack包（定义栈）中： 栈是通过链表来定义的，因此 StringListElement：次类定义了链表的每一个节点 StringStrack：此类定义了栈，其中有长度属性，有函数： Top();用来取得栈顶 Push（）；压栈 Pop（）；出栈 4、sentence包（语法分析）中： juzi ：定义了文法的句子的结构：key（左边部分） content[](右边推出的部分) lo（长度） grammar ：存储了文法的27个关系式 AnalysisFB ：定义了分析表的存储结构 AnalysisF ：存储分析表 SentenceAnalysis ：语法分析 JuProduction(word w)：此函数是用来判断在当前栈与输入串的情况下，用哪一个产生式,返回产生式在数组中的下标 若输入串的第一个字符与栈顶字符相同则表示可以规约，则返回-1； 若不能过用产生式，则返回-2； AnalysisBasic(word w)：此函数是分布进行语法分析，对栈操作 * 根据所需要的产生式对符号栈进行操作 * 返回0表示规约；返回1表示移进；否则表示输入串不是文法的句子 5. Main包（主界面）中 Main：此类定义了图形界面 重要函数分析： 一、词法分析函数： 当搜索指示器小于输入串长度是，就循环执行如下操作： 得到当前char，如果是字母，判断下一个，如是数字或字母，继续直至不是字母或者是数字，将此时的单词与关键字比较，获得识别符，存入word数组中 如果是数字，循环看下一个是否为数字，继续直至不是数字为止，将单词存入数组中 如果是+、-、*、/、（、）、[、]、{、}、，、：、；与关键字比较，直接存入数组中 如果是>、<、=、!时，要判断下一个，是否构成了>=、<=、==、!=。然后在存入数组中 如果下一个字符是空，换行，则跳过去下一个字符。 在做词法分析的时候，注意每一次判断结束之后要将strToken清空，而且要注意回退，即当输入串下一个不满足要求的时候，要回退一格。 2、 语法分析函数 利用词法分析已经分析出来的单词数组，循环进行每一步的语法分析，每当归并一个单词之后，index指示器加一，直至index等于单词数组长度，循环结束。 在每一次循环中，根据当前指示器指示的单词及堆栈的栈顶判断： 若相同，则表示要归并，将index++；栈顶弹出 若不相同，在分析表中查找所需要的产生式，并将栈顶弹出，将产生式逆向堆栈。 在查询的过程中，如果不能够移进也不能够归并，表示输入串不符合文法，在提示栏中提示。如果循环结束，直至栈中是由#，输入串中只剩#，表示分析完毕，输入串是符合文法的句子。 iv. 结果分析（原始图示） 图形界面： 输入句子：main() {} //空的main函数，运行结果 1、 点击词法分析之后，在右侧的词法分析结果中显示分析后的单词： 2、 点击语法分析之后，在中间的表中显示堆栈过程： 3、 语法分析结束，该语句是符合文法的句子，因此在提示栏中显示“该句子是符合文法的语句！ 输入复杂一点的句子： main(){ If(zhj= =zhj){ Zhj=good; }; } 则结果是： 则他输出的单词是：（1,main）( 14, ( ) (15 , ) ) ( 18 , { ) ( 4 , if ) ( 14 , ( ) ( 7 , zhj ) ( 27 , = = ) ( 7, zhj ) ( 15 , ) ) ( 18 , { ) ( 7 , zhj ) ( 9 , = ) ( 7 , good) ( 22 , ；) ( 19 , ｝) ( 22 , ；) ( 19 , ｝) 语法分析经过了从0到37 的38步，分析结束：（在下图中将语法分析的全过程拼合） 分析结束后的输出结果是： 下图为此次语法分析的堆栈全过程： 输出更加复杂的句子： Main() { While ( lsq <= zhj ){ If ( zhj = = zhj ){ Zhj = good; }; }; } 则结果是： 右侧的单词符号序列为： 语法分析过程为： 输入串是符合文法的句子，因此，正常结束 输入一个不符合文法的句子： Main(){ zhanghuijuan is a good student ; } // zhanghuijuan is a good student 语句即不是赋 值，条件，也不是循环，因此不符合文法 输出结果是： 词法分析仍然可以进行，但是语法分析中发现进行不下去了，因此输出错误提示： “此输入串不是一个语句，不符合文法！” iiv. 调试报告： 程序在编写的过程中有很多小的地方并没有注意，在不断的调试的过程当中逐渐发现： 1、在文法中有A-->空 的情况，在文法产生式的存储过程中就用空格代替了空，但是当需要用这样的产生式移进的时候，如果跟其他的产生式一样处理，则会在堆栈中将空格压栈，因此使语法分析不能继续进行下去。因此，我们在压栈之前要先进行判断，若是这种情况，则只是弹出栈顶，而不对其进行压栈。 2、由于在此程序中应用了多个数组，因此很容易出现数组越界的情况，所以这里就要多加注意才行。 3、在堆栈过程输出的时候，要输出当前栈中的元素，以及剩余的输入串，一定要注意要将输入串的输出放在index的增加之后，否则就是输出上一次的执行时的输入串了 附：程序原代码 ************************package word.wordList;********************************** //////////////////////////////////////file word.java///////////////////////////////////// public class word { String value; int ID; public int getID() { return ID; } public void setID(int id) { ID = id; } public String getValue() { return value; } public void setValue(String value) { this.value = value; } } //////////////////////////////////////file word.java///////////////////////////////////// public class WordList { //此类定义了语言单词符号种别码 word[] w = new word[30]; public WordList(){ w[0] = new word();w[0].setID(1);w[0].setValue("main"); w[1] = new word();w[1].setID(2);w[1].setValue("int"); w[2] = new word();w[2].setID(3);w[2].setValue("char"); .........................................................................//省略 w[27] = new word();w[27].setID(28);w[27].setValue("!="); w[28] = new word();w[28].setID(29);w[28].setValue("ERROR"); } public int Reserve(String value){ for(int i = 0 ; i<28 ; i++){ if(value.equals(w[i].getValue())){ return w[i].getID(); } } return 0; //返回0表示不在保留字之中。 } } ************************package word;;********************************** //////////////////////////////////////file basicFunction .java///////////////////////////////////// import word.wordList.WordList; //在此类中定义了一组全局变量和过程，将它们作为实现转换图的基本成分 public class basicFunction { public String input=""; //输入的源程序 public char ch; //存放最新读进的源程序的字符 public String strToken=""; //存放构成单词符号的字符串 public int index=0; //存放此时搜索指示器指向的字符位置 public int index_buf; //buffer中搜索指示器指向的字符位置 basicFunction(String input){ this.input = input; } public char getCh() { return ch; } public void setCh(char ch) { this.ch = ch; } public String getInput() { return input; } public void setInput(String input) { this.input = input; } public String getStrToken() { return strToken; } public void setStrToken(String strToken) { this.strToken = strToken; } //将下一输入字符读到ch中，搜索知识器前移一个字符位置 public int GetChar(){ this.ch = this.input.charAt(index); index++; return 0; } //检查ch中的字符是否为空白。若是，则调用GetChar直至不是字符为止 public char GetBC(){ while(ch==' '||ch=='\n'||ch=='\r'){ GetChar(); } return ch; } //将ch中的字符连接到strToken之后 public String Concat(){ strToken=strToken.concat(String.valueOf(ch)); return strToken; } //判断ch中的字符是否为字母 public boolean IsLetter(){ boolean flag=false; if(ch>='a' && ch<='z' || ch>='A' && ch<='Z' ){ flag=true; } return flag; } //判断ch中的字符是否为数字 public boolean IsDigit(){ boolean flag=false; if(ch>='0' && ch<='9' ){ flag=true; } return flag; } //对strToken中的字符创查找保留字表，若是则返回它的编码，否则返回0 //注：在编写保留字表的时候要从1开始编号，不能从0开始编号！ public int Reserve(){ WordList wl = new WordList(); int f = wl.Reserve(strToken); return f; //返回0表示不在保留字之中。 } //将搜索指示器回调一个字符位置 public void Retract(){ ch=' '; int l = strToken.length(); if(l>1){ strToken = strToken.substring(0,l-1); } index--; } //将strToken置空 public void RetractStr(){ strToken=""; } } //////////////////////////////////file: lexAnalysis .java; ////////////////////////////////// import word.wordList.word; public class lexAnalysis { String input; public word[] word = new word[1000]; public String getInput() { return input; } public void setInput(String input) { this.input = input; } public int wordAnalysis(){ int i = 0; basicFunction bf = new basicFunction(input); int lo = input.length(); while(bf.index'||bf.ch=='<'||bf.ch=='='||bf.ch=='!'){ int f = 0; if(bf.index=0&&pro<=26){ int l = gg.gram[pro].lo; ss.pop(); for(int j =l-1 ; j>=0 ; j--){ ss.push(gg.gram[pro].content[j]); } f=1; } return f; } } *********************************packet main********************************** 此图形界面代码不再黏贴了，只是将词法分析的函数及语法分析的函数黏贴 private JButton getJButton() { if (jButton == null) { jButton = new JButton(); jButton.setBounds(new java.awt.Rectangle(599,80,89,41)); jButton.setText("词法分析"); jButton.addActionListener(new ActionListener(){ public void actionPerformed(ActionEvent arg0) { String input = getJTextArea().getText().toString().trim(); System.out.print(input); TableModel model = getJTable().getModel(); DefaultTableModel tablemodel = (DefaultTableModel)model; int counts = tablemodel.getRowCount(); for(int k = counts-1;k>=0;k--){ tablemodel.removeRow(k); } lexAnalysis lex = new lexAnalysis(); lex.setInput(input); int i = lex.wordAnalysis(); for(int j = 0 ; j=0;k--){ tablemodel.removeRow(k); } SentenceAnalysis sa = new SentenceAnalysis(); lexAnalysis lex = new lexAnalysis(); lex.setInput(input); int i = lex.wordAnalysis(); // System.out.println(i); int index = 0; int b = 0; //用来求输入串 String inp0 =""; for (int j = index ; j=0&&gra<=26){ gram = sa.gg.gram[gra].key; gram = gram+"-->"; int lll = sa.gg.gram[gra].lo; for(int m = 0 ; m