《编译原理》
实验报告
姓名: 余同庆
班级: 软件1005班
学号: 3902100509
日期: 20##-6-7
中南大学软件学院
20##年06月
第一部分 词法分析
词法分析程序设计与实现
一、实验目的
加深对词法分析器的工作过程的理解;加强对词法分析方法的掌握;能够采用一种编程语言实现简单的词法分析程序;能够使用自己编写的分析程序对简单的程序段进行词法分析。
二、实验内容
自定义一种程序设计语言,或者选择已有的一种高级语言,编制它的词法分析程序。词法分析程序的实现可以采用任何一种编程语言和编程工具。
从输入的源程序中,识别出各个具有独立意义的单词,即关键字、标识符、常数、运算符、界符。并依次输出各个单词的内部编码及单词符号自身值。(遇到错误时可显示“Error”,然后跳过错误部分继续显示)
三、实验要求
1. 对单词的构词规则有明确的定义;
2. 编写的分析程序能够正确识别源程序中的单词符号;
3. 识别出的单词以<种别码,值>的形式保存在符号表中,正确设计和维护符号表;
4. 对于源程序中的词法错误,能够做出简单的错误处理,给出简单的错误提示,保证顺利完成整个源程序的词法分析;
四、程序设计思路
这里以开始定义的C语言子集的源程序作为词法分析程序的输入数据。在词法分析中,自文件头开始扫描源程序字符,一旦发现符合“单词”定义的源程序字符串时,将它翻译成固定长度的单词内部表示,并查、填适当的信息表。经过词法分析后,源程序字符串(源程序的外部表示)被翻译成具有等长信息的单词串(源程序的内部表示),并产生两个表格:常数表和标识符表,它们分别包含了源程序中的所有常数和所有标识符。
1. 定义部分:定义常量、变量、数据结构。
2. 初始化:从文件将源程序全部输入到字符缓冲区中。
3. 取单词前:去掉多余空白。
4. 取单词:利用实验一的成果读出单词的每一个字符,组成单词,分析类型。
5. 显示结果。
五、实验步骤
1. 定义目标语言的可用符号表和构词规则;
2. 依次读入源程序符号,对源程序进行单词切分和识别,直到源程序结束;
3. 对正确的单词,按照它的种别以<种别码,值>的形式保存在符号表中;
4. 对不正确的单词,做出错误处理。
六、实验代码
Lexer.java
package 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 < keyWords.length; i++){
if (keyWords[i].equals(ch)){
return true;
}
}
return false;
}
// 判断是否为数字
boolean isDigit(char ch) {
if (ch >= 48 && ch <= 57)
return true;
else
return false;
}
// 判断是否为字母
boolean isLetter(char ch) {
// 分别对应大写字母,小写字母,下划线
if ((ch >= 65 && ch <= 90) || (ch >= 97 && ch <= 122) || (ch == 95))
return true;
else
return 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;
}
}
else
return false;
}
// 判断是否是分隔符
boolean isSeparator(char ch) {
// 依次匹配关键字表
for (int i = 0; i < separators.length; i++){
if (separators[i] == 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 (operators[i] == ch){
translate(4, String.valueOf(ch));
index++;
return true;
}
}
// 依次匹配关系运算符表
for (int i = 0; i < relelationOpts.length; i++){
if (relelationOpts[i] == ch){
translate(4, String.valueOf(ch));
index++;
return true;
}
}
return false;
}
// 输出格式
void translate(int num, String ch){
try {
// 输出到文件
writer.write("(" + num + ", \"" + ch + "\")");
writer.write("\r\n"); // 换行
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.java
package 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++语言来编写,其逻辑结构图如下:
LL(1)预测分析程序的总控程序在任何时候都是按STACK栈顶符号X和当前的输入符号a做哪种过程的。对于任何(X,a),总控程序每次都执行下述三种可能的动作之一:
(1)若X = a =‘#’,则宣布分析成功,停止分析过程。
(2)若X = a‘#’,则把X从STACK栈顶弹出,让a指向下一个输入符号。
(3)若X是一个非终结符,则查看预测分析表M。若M[A,a]中存放着关于X的一个产生式,那么,首先把X弹出STACK栈顶,然后,把产生式的右部符号串按反序一一弹出STACK栈(若右部符号为ε,则不推什么东西进STACK栈)。若M[A,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<String> 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 analysisTable[row][column];
}
void analysis() {
System.out.println("分析栈\t\t输入串\t\t产生式");
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 < strArray.length())
return true;
else
return false;
}
// 当前字符与栈顶元素匹配
public Type match(String pop, String str) {
// 判断输入的值是否有效
if ((isValidStr(pop) == false) || (isTerminator(str) == false)) {
printState("输入无效");
return Type.INVALID_STR;
}
// 栈顶元素与当前字符相等
if (pop.equals(str)) {
if (pop.equals("#")) { // 两者均等于#,分析结束
printState("成功");
return Type.SUCCESS;
} else { // 不等于#,栈弹栈,当前字符移向下一字符
printState("相等,弹栈,指针前移");
stack.pop();
indexForward();
return Type.EQUAL;
}
}
// 查找分析表,判断是否存在对应产生式
String result = find(pop, str);
if (result != null) {
if (result == "ε") { // 为ε,弹栈
printState("ε,弹栈");
stack.pop();
return Type.POP_STACK;
} else { // 存在对应产生式,将候选式反序压栈
printState(pop + "->" + 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() + "\t\t" + printStrArray() + "\t\t" + production;
try {
writer.write(str + "\r\n");
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("读入的字符串为 " + strArray.toString());
} catch (IOException e) {
System.out.println("输入串读取错误: " + e.toString());
}
}
// 初始化终结符
void initTerminator() {
terminator="i+*()#";
}
// 初始化非终结符
void initNonTerminator() {
nonTerminator="EDTSF";
}
// 初始化分析表
void initAnalysisTable() {
// 文法开始符号为E
analysisTable = new String[][]{
{" ", "i", "+", "*", "(", ")", "#" },
{"E", "TD", null, null, "TD", null, null},
{"D", null, "+TD", null, null, "ε", "ε" },
{"T", "FS", null, null, "FS", null, null},
{"S", null, "ε", "*FS", null, "ε", "ε" },
{"F", "i", null, null, "(E)", null, null},
};
}
// 初始化栈
void initStack() {
stack = new Stack<String>();
stack.push("#");
stack.push("E");
}
/**
* 从命令行读取输入串
* @throws IOException
*/
String readFromConsole() throws IOException {
System.out.println("请输入要分析的符号串:");
BufferedReader bufferReader = new BufferedReader(
new InputStreamReader(System.in));
return bufferReader.readLine();
}
}
Manager.java
public class Manager {
public static void main(String[] args) {
LL1_Analysis ll = new LL1_Analysis();
ll.run();
}
}
七、实验结果
正确输入下的结果:
非法输入下的结果:
ltlt编译原理gtgt上机实验报告编译原理上机实验报告一实验目的与要求目的在分析理解一个教学型编译程序如PL0的基础上对其词法分…
编译原理课程实验报告题目专业计算机指导教师签名华东理工大学信息学院计算机系20xx年4月10日一实验序号编译原理第一次实验二实验题…
编译原理词法分析一、实验目的设计、编制并调试一个词法分析程序,加深对词法分析原理的理解。二、实验要求2.1待分析的简单的词法(1)…
编译原理实验报告指导教师1一实验目的基本掌握计算机语言的词法分析程序的开发方法以及掌握计算机语言的语法分析程序设计与属性文法应用的…
编译原理实验报告班级姓名学号自我评定75实验一词法分析程序实现一实验目的与要求通过编写和调试一个词法分析程序掌握在对程序设计语言的…
编译技术上机实验题目实验一一题目编制C语言子集的词法分析程序二目的通过设计编制调试一个具体的词法分析程序加深对词法分析原理的理解并…
课程实验报告课程名称:编译原理(语法分析)专业班级:信息安全1001班学号:姓名:指导教师:报告日期:20XX/11/8计算机科学…
编译原理实验报告编译原理实验报告1编译原理实验报告一实验内容设计编制并调式一个语法分析程序加深对语法分析原理的理解二实验目的及要求…
武汉理工大学学生实验报告书实验课程名称编译原理开课学院计算机科学与技术学院指导老师姓名饶文碧学生姓名学生专业班级软件20xx20x…
武汉理工大学学生实验报告书实验课程名称编译原理开课学院计算机科学与技术学院指导老师姓名何九周学生姓名小灰灰的爸爸学生专业班级中国好…