编译原理课程实验报告(词法分析器及语法分析器).doc

编译原理实验报告 班级：软件0501班 学号：1303050121 姓名：张慧娟 词法分析器与语法分析器I. 问题描述 设计、编制并调试一个词法分析子程序，完成识别语言单词的任务； 设计、编制、调试一个语法分析程序，并用它对词法分析程序所提供的单词序列进行语法检查和结构分析。 ii. 设计简要描述 界面需求： 为了更加形象的模拟过程，此实验使用图形界面。要求从图形界面上输入输入串，点击词法分析，可以将词法分析后识别的单词符号显示，点击语法分析，可以将语法分析的堆栈过程显示，并且显示结果（是否是符合文法的句子），清空则可以将所有置空。功能分析：1、 由用户输入输入串；2、 用户点击“词法分析”，可以将词法分析后识别的单词符号显示。3、 用户点击语法分析，可以将语法分析的堆栈过程显示，并且显示结果（是否是符合文法的句子）4、 用户点击清空，则将界面所有组件置为空思路描述： 一、设计构想：本实验决定编写一个简易C语言的词法分析器和语法分析器。使其能够识别while，if等关键字，可以判断赋值语句、条件语句、循环语句。2、 文法分析 1、需要识别的关键字及其识别码有： 关键字 识别码 关键字 识别码 关键字 识别码main 0 - 11 ； 22int 1 * 12 23char 2 / 13 = 25else 4 ) 15 = 26for 5 16 = 27while 6 17 != 28ID 7 18 ERROR -1NUM 8 19 = 9 , 20 + 10 : 21 2、 文法 程序 main()语句块语句块语句串语句串语句；语句串|语句；语句赋值语句|条件语句|循环语句赋值语句 ID =表达式;条件语句 if条件语句块循环语句 while条件语句块条件（表达式关系符表达式）表达式表达式运算符表达式|（表达式）|ID|NUM运算符+|-|*|/关系符|！ 转化为符号表示： S main() K|空 K C CY；C |空 YF | 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：关系符3、 LL（1）分析表 （1），求出first集及follow集： FIRST(S)=mianFIRST(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() K2、K C 3、 CY；C 4、 C空5、Y F6、Y T 7、Y X8、F ID = B9、 T if J K10、X while J K11、 J（ B G B ）12、 B （ B ）B13、B ID B14、B NUM B15、B BZB B16、B 空17、 Z + 18、 Z -19、 Z * 20、 Z /21、 G 22、 G 24、 G =25、 G =26、 G != （3）构造LL（1）分析表 （注：在表中用上一步的编号表示所需要的产生式）main空();=ifwhileIDnum+-*/=!=#S 10K2C44333Y675F8T9X10J11B121314B16151616151516161616161616161616Z17181920G212223242526iii. 详细设计描述 项目构架： 各函数功能介绍： 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 空 的情况，在文法产生式的存储过程中就用空格代替了空，但是当需要用这样的产生式移进的时候，如果跟其他的产生式一样处理，则会在堆栈中将空格压栈，因此使语法分析不能继续进行下去。因此，我们在压栈之前要先进行判断，若是这种情况，则只是弹出栈顶，而不对其进行压栈。 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 word30; public WordList() w0 = new word();w0.setID(1);w0.setValue(main); w1 = new word();w1.setID(2);w1.setValue(int); w2 = new word();w2.setID(3);w2.setValue(char); ./省略 w27 = new word();w27.setID(28);w27.setValue(!=); w28 = new word();w28.setID(29);w28.setValue(ERROR);public int Reserve(String value)for(int i = 0 ; i=a & ch=A & ch=0 & ch1) 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 word1000;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.indexlo)wordi = new word();bf.GetChar();bf.Concat();if(bf.IsLetter()int f = 0;if(bf.indexlo)bf.GetChar();bf.Concat();while(bf.IsLetter()|bf.IsDigit()if(bf.indexlo)bf.GetChar();bf.Concat();elsebf.ch= ;f=1;if(f!=1)bf.Retract();int m = bf.Reserve();if(m=0)wordi.setValue(bf.strToken);wordi.setID(7);elsewordi.setValue(bf.strToken);wordi.setID(m);i+;bf.RetractStr();else if(bf.IsDigit()int f = 0;if(bf.indexlo)bf.GetChar();bf.Concat();while(bf.IsDigit()if(bf.index|bf.ch=|bf.ch=|bf.ch=!)int f = 0;if(bf.indexlo)bf.GetChar();bf.Concat();elsebf.index+;bf.ch= ;f=1;if(bf.ch!=&f!=1)bf.Retract();int m = bf.Reserve();if(m=0)wordi.setValue(bf.strToken);elsewordi.setValue(bf.strToken);wordi.setID(m);i+;bf.RetractStr();else if(bf.ch= |bf.ch=n|bf.ch=r)bf.RetractStr();return i;*package stack;* /file: StringListElement .java; /public class StringListElement public String data;public StringListElement next = null;StringListElement(String value)data = value;StringListElement(String value,StringListElement next)data = value;this.next = next; /file: StringStack .java; /public class StringStack public StringListElement top = new StringListElement(); public int lo = 0;public String top()if(top!=null)return top.data;elsereturn ERROR!;public String pop()String result = top();if(top!=null)top = top.next;lo-;return result;public void push(String value)if(top=null)top = new StringListElement(value);lo+;elseStringListElement temp = new StringListElement(value);temp.next= top;top = temp;lo+;*package sentence;* /file: juzi .java; /public class juzi public String key;public int lo;public String content = ,; /file: grammar .java; /public class grammar public juzi gram = new juzi27; public grammar() gram0 = new juzi(); gram0.key = S;gram0.lo = 1;gram0.content0=; gram1 = new juzi(); gram1.key = S;gram1.lo = 4;gram1.content0=main; gram1.content1=(;gram1.content2=);gram1.content3=K; .省略 gram26 = new juzi(); gram26.key = G;gram26.lo = 1;gram26.content0=!=; public static void main(String args) grammar g = new grammar(); System.out.println(g.gram0.key); /file: AnalysisFB .java; /public class AnalysisFB /此类定义了分析表中的每一个单元的数据结构public String key;public String input;public int index; /file: AnalysisF .java; /public class AnalysisF public AnalysisFB A = new AnalysisFB43;public AnalysisF()A0 = new AnalysisFB();A0.key = S; A0.input = #; A0.index = 0;A1 = new AnalysisFB();A1.key = S; A1.input = main; A1.index = 1;A2 = new AnalysisFB();A2.key = K; A2.input = ; A2.index = 2;./省略A42 = new AnalysisFB();A42.key = G; A42.input = !=; A42.index = 26; /file: SentenceAnalysis .java; /import stack.StringStack;import word.wordList.word;/* *此类中是用于语法分析 */public class SentenceAnalysis public StringStack ss = new StringStack();/此堆栈是符号栈public grammar gg = new grammar();public AnalysisF af = new AnalysisF();/初始化堆栈public SentenceAnalysis()ss.push(#);ss.push(S);/* *此函数是用来判断在当前栈与输入串的情况下，用哪一个产生式,返回产生式在数组中的下标 *若输入串的第一个字符与栈顶字符相同则表示可以规约，则返回-1； *若不能过用产生式，则返回-2； */public int JuProduction(word w)int f = -2;String top = ss.top();System.out.println(+ss.top();String input=;if(w.getID() = 7)input = ID;else if(w.getID()=8)input = NUM;else input = w.getValue();if(top.equals(input)f = -1;for(int i = 0 ; i =0&pro=0 ; j-)ss.push(gg.grampro.contentj);f=1;return f;*packet main*此图形界面代码不再黏贴了，只是将词法分析的函数及语法分析的函数黏贴private JButton getJButton() if (jButton = null) jButton = new JButton();jButton.setBounds(new java.awt.Rectangle