编译原理实验报告.doc

编译原理实验报告姓名： 余同庆 班级： 软件1005班 学号： 3902100509 日期： 2012-6-7 中南大学软件学院2012年06月20第一部分 词法分析词法分析程序设计与实现一、实验目的加深对词法分析器的工作过程的理解；加强对词法分析方法的掌握；能够采用一种编程语言实现简单的词法分析程序；能够使用自己编写的分析程序对简单的程序段进行词法分析。二、实验内容自定义一种程序设计语言，或者选择已有的一种高级语言，编制它的词法分析程序。词法分析程序的实现可以采用任何一种编程语言和编程工具。从输入的源程序中，识别出各个具有独立意义的单词，即关键字、标识符、常数、运算符、界符。并依次输出各个单词的内部编码及单词符号自身值。（遇到错误时可显示“Error”，然后跳过错误部分继续显示）三、实验要求1. 对单词的构词规则有明确的定义；2. 编写的分析程序能够正确识别源程序中的单词符号；3. 识别出的单词以的形式保存在符号表中，正确设计和维护符号表；4. 对于源程序中的词法错误，能够做出简单的错误处理，给出简单的错误提示，保证顺利完成整个源程序的词法分析；四、程序设计思路这里以开始定义的C语言子集的源程序作为词法分析程序的输入数据。在词法分析中，自文件头开始扫描源程序字符，一旦发现符合“单词”定义的源程序字符串时，将它翻译成固定长度的单词内部表示，并查、填适当的信息表。经过词法分析后，源程序字符串（源程序的外部表示）被翻译成具有等长信息的单词串（源程序的内部表示），并产生两个表格：常数表和标识符表，它们分别包含了源程序中的所有常数和所有标识符。1. 定义部分：定义常量、变量、数据结构。2. 初始化：从文件将源程序全部输入到字符缓冲区中。3. 取单词前：去掉多余空白。4. 取单词：利用实验一的成果读出单词的每一个字符，组成单词，分析类型。5. 显示结果。五、实验步骤1. 定义目标语言的可用符号表和构词规则；2. 依次读入源程序符号，对源程序进行单词切分和识别，直到源程序结束；3. 对正确的单词，按照它的种别以的形式保存在符号表中；4. 对不正确的单词，做出错误处理。六、实验代码Lexer.javapackage lexer;import java.io.BufferedReader;import java.io.FileReader;import java.io.FileWriter;import java.io.IOException;public class Lexer / 关键字列表private String keyWords = if, int, for, while, do, return, break, continue ;/ 分隔符列表private char separators = , ;, , , (, ), ,;/ 运算符列表private char operators = =, +, -, *, /, %;/ 关系运算符列表private char relelationOpts = , , !, =;private String fileName;/ 文件名private StringBuffer buffer = new StringBuffer();/ 动态Buffer数组，用于存储从文件中读取的字符串private static int index = 0;private FileWriter writer = null;/ 选择带分析文件public void OpenFile(String fileName) this.fileName = fileName;/ 从文件中读取要分析的C语言程序public void readFile() try / 读取文件流BufferedReader fileReader = new BufferedReader(new FileReader(this.fileName);String temp = null;/ 定义一个临时字符串,用于暂时存放读取的文件内容while (temp = fileReader.readLine() != null) buffer.append(temp);/ 将读取的文件内容追价至动态buffer数组中 catch (Exception e) System.out.println(文件操作错误: + e.toString();public void writeFile(String fileName) try writer = new FileWriter(fileName); catch (IOException e) System.out.println(文件操作错误: + e.toString();public void closeStream() try writer.flush();writer.close(); catch (IOException e) e.printStackTrace();/ 判断是否为关键字boolean isKeyWord(String ch) / 依次匹配关键字表for (int i = 0; i = 48 & ch = 65 & ch = 97 & ch = 122) | (ch = 95)return true;elsereturn false;/ 判断是否为标识符或关键字boolean isToken(char ch) if (isLetter(ch)StringBuffer temp = new StringBuffer();temp.append(ch);ch = buffer.charAt(+index);while (isLetter(ch) | isDigit(ch) temp.append(ch);ch = buffer.charAt(+index);if (isKeyWord(temp.toString() translate(1, temp.toString();return true; else translate(2, temp.toString();return true;elsereturn false;/ 判断是否是分隔符boolean isSeparator(char ch) / 依次匹配关键字表for (int i = 0; i separators.length; i+)if (separatorsi = ch)translate(5, String.valueOf(ch);index+;return true;return false;/ 判断是否是常数boolean isConstant(char ch)if(isDigit(ch)StringBuffer temp = new StringBuffer();while (isDigit(ch) temp.append(ch);ch = buffer.charAt(+index);translate(3, temp.toString();return true;return false;/ 判断是否是运算符boolean isOperator(char ch) / 依次匹配运算符表for (int i = 0; i operators.length; i+)if (operatorsi = ch)translate(4, String.valueOf(ch);index+;return true;/ 依次匹配关系运算符表for (int i = 0; i relelationOpts.length; i+)if (relelationOptsi = ch)translate(4, String.valueOf(ch);index+;return true;return false;/ 输出格式void translate(int num, String ch)try / 输出到文件writer.write( + num + , + ch + );writer.write(rn); / 换行writer.flush(); catch (IOException e) e.printStackTrace();System.out.println( + num + , + ch + );/ 词法分析过程public void analyze() char ch;while (index buffer.length() ch = buffer.charAt(index);/ 利用短路运算if (isToken(ch) | isSeparator(ch) | isConstant(ch) | isOperator(ch) else index+; / 字符指针前移TestLexer.javapackage testCompiler;import lexer.Lexer;public class TestLexer public static void main(String args) Lexer lexer = new Lexer();lexer.OpenFile(F:/test.txt);lexer.writeFile(F:/words.txt);lexer.readFile();lexer.analyze();lexer.closeStream();七、实验结果对于这一段程序：其运行结果如图所示：第二部分 语法分析预测分析法设计与实现一、实验目的加深对语法分析器工作过程的理解；加强对预测分析法实现语法分析程序的掌握；能够采用一种编程语言实现简单的语法分析程序；能够使用自己编写的分析程序对简单的程序段进行语法翻译。二、实验内容在实验1的基础上，用预测分析法编制语法分析程序，语法分析程序的实现可以采用任何一种编程语言和工具。三、实验要求1. 对语法规则有明确的定义；2. 编写的分析程序能够对实验一的结果进行正确的语法分析；3. 对于遇到的语法错误，能够做出简单的错误处理，给出简单的错误提示，保证顺利完成语法分析过程；4. 实验报告要求用文法的形式对语法定义做出详细说明，说明语法分析程序的工作过程，说明错误处理的实现。四、程序设计思路所谓LL（1）分析法，就是指从左到右扫描输入串（源程序），同时采用最左推导，且对每次直接推导只需向前看一个输入符号，便可确定当前所应当选择的规则。实现LL（1）分析的程序又称为LL（1）分析程序或LL（1）分析器。我们知道一个文法要能进行LL（1）分析，那么这个文法应该满足：无二义性，无左递归，无左公因子。当文法满足条件后，再分别构造文法每个非终结符的FIRST和FOLLOW集合，然后根据FIRST和FOLLOW集合构造LL（1）分析表，最后利用分析表，根据LL(1)语法分析构造一个分析器。LL（1）的语法分析程序包含了三个部分，总控程序，预测分析表函数，先进先出的语法分析栈，本程序也是采用了同样的方法进行语法分析，该程序是采用了C+语言来编写，其逻辑结构图如下：STACK分析栈输出a1 a2 a3 aian#输入串（源程序）总控程序预测分析表MX1Xn-1Xn#LL（1）预测分析程序的总控程序在任何时候都是按STACK栈顶符号X和当前的输入符号a做哪种过程的。对于任何（X，a），总控程序每次都执行下述三种可能的动作之一：（）若X = a =#，则宣布分析成功，停止分析过程。（）若X = a#，则把X从STACK栈顶弹出，让a指向下一个输入符号。（）若X是一个非终结符，则查看预测分析表M。若MA，a中存放着关于X的一个产生式，那么，首先把X弹出STACK栈顶，然后，把产生式的右部符号串按反序一一弹出STACK栈（若右部符号为，则不推什么东西进STACK栈）。若MA，a中存放着“出错标志”，则调用出错诊断程序ERROR。事实上，LL（1）的分析是根据文法构造的，它反映了相应文法所定义的语言的固定特征，因此在LL（1）分析器中，实际上是以LL（1）分析表代替相应方法来进行分析的。五、实验步骤1. 定义目标语言的语法规则；2. 求解预测分析方法需要的符号集和分析表；3. 依次读入实验一的分析结果，根据预测分析的方法进行语法分析，直到源程序结束；4. 对遇到的语法错误做出错误处理。六、实验代码LL1_Analysis.java import java.io.*;import java.util.Stack;public class LL1_Analysis String terminator;/ 终结符 String nonTerminator;/ 非终结符 String analysisTable;/ 分析表 public Stack stack = null; StringBuffer strArray; / 字符数组 int index = 0;/ 字符数组索引值 / 匹配结果：无效输入， 成功（均为#）， 两字符相等（且不等于#）， 弹栈（产生式为）， 压栈（将产生式反序入栈）， 错误（栈值为null） enum Type INVALID_STR, SUCCESS, EQUAL, POP_STACK, PUSH_STR, ERROR FileWriter writer = null; void temp() try writer = new FileWriter(F:/result.txt, true); catch (IOException e) e.printStackTrace(); /* * 执行预测分析法 */ public void run() initialization(); analysis(); /* * 查找分析表的元素 * param str1 * param str2 * return */ public String find (String str1, String str2) /* * 对于输入的字符，不能确定是终结符还是非终结符 * 根据index若无匹配则返回-1，而匹配成功返回正数，大数为匹配结果 * 因为分析表头存在一空位，故 row 与 column 各 + 1 */ int row = Math.max(nonTerminator.indexOf(str1), terminator.indexOf(str1) + 1; int column = Math.max(nonTerminator.indexOf(str2), terminator.indexOf(str2) + 1; return analysisTablerowcolumn; void analysis() System.out.println(分析栈tt输入串tt产生式); while (isIndexInStrArray() Type result = match(stack.peek(), String.valueOf(strArray.charAt(index); if (result = Type.INVALID_STR | result = Type.SUCCESS | result = Type.ERROR) break; else continue; / 从输入串数组读一个String String readFromStrArray(StringBuffer strArray) String tmp = String.valueOf(strArray.charAt(index); return tmp; / 输入串指针前移void indexForward() index +;/ 返回当前输入串索引int getIndex() return index;/ 判断输入串指针是否在合理范围boolean isIndexInStrArray() if (index = 0 & index + result); stack.pop(); for (int i = result.length() - 1; i = 0 ; i-) stack.push(String.valueOf(result.charAt(i); return Type.PUSH_STR; else / 不存在对应产生式，报错 printState(error); return Type.ERROR; boolean isTerminator(String str) return (terminator.indexOf(str) = 0); boolean isNonTerminator(String str) return (nonTerminator.indexOf(str) = 0); boolean isValidStr(String str) return (isTerminator(str) | isNonTerminator(str); void printState(String production) String str = printStack() + tt + printStrArray() + tt + production; try writer.write(str + rn);writer.flush(); catch (IOException e) e.printStackTrace(); System.out.println(str); String printStrArray() String str = strArray.substring(index, strArray.length();return str;String printStack() StringBuffer stringBuffer = new StringBuffer();StringBuffer returnBuffer = new StringBuffer();/ 获取栈中元素while (!stack.empty() stringBuffer.append(stack.pop();/ 还原栈for (int i = stringBuffer.length() - 1; i = 0; i-) stack.push(String.valueOf(stringBuffer.charAt(i);/ 将字符串反向排列for (int i = stringBuffer.length() - 1; i = 0; i-) returnBuffer.append(stringBuffer.charAt(i);return returnBuffer.toString();/* * 全局初始化 */public void initialization() initTerminator(); initNonTerminator();initAnalysisTable();initStack();temp();try strArray = new StringBuffer(readFromConsole();System.out.println