编译原理实验文档.doc

编译原理
实验报告

学生姓名：
学 号：
学　 院： 计算机与信息工程学院
专业年级：
指导教师：
开始时间： 2012年6月25日

目 录

实验一 词法分析 3
1 实验目的 3
2 实验内容 3
3 实验步骤 3
4 实验结果 6
5 实验心得 6
实验二 LL（1）分析 6
1 实验目的 6
2 实验内容 7
3 实验步骤 7
4 实验结果 7
5 实验心得 8
实验三 逆波兰式的产生及计算 8
1 实验目的 8
2 实验内容 8
3 实验步骤 8
4 实验结果 9
5 实验心得 9
实验四 算符优先分析算法 10
1 实验目的 10
2 实验内容 10
3 实验步骤 10
4 实验结果 11
5 实验心得 11
实验五 LR（1）分析法 12
1 实验目的 12
2 实验内容 12
2 实验步骤 12
4 实验结果 13
5 实验心得 14
附录： 14

实验一 词法分析
1 实验目的
通过设计、调试词法分析程序，实现从源程序中分出 各种单词的方法；熟悉词法分析程序所用的工具自动机，进一步理解自动机理论。掌握文法转换成自动机的技术及有穷自动机实现的方法。确定词法分析器的输出形式及标识符与关键字的区分方法。加深对课堂教学的理解；提高词法分析方法的实践能力。通过本实验，应达到以下目标：
1、掌握从源程序文件中读取有效字符的方法和产生源程序的内部表示文件的方法。
2、掌握词法分析的实现方法。
3、上机调试编出的词法分析程序。
2 实验内容
词法分析是编译程序的第一个阶段，主要任务是对于字符串流的输入，根据词表，将关键字、变量等转化成自定义逻辑结构，就是输入源程序，去除空白符等无意义字符，然后按照各自的分类，转换成一个变量表。
3 实验步骤
1.词法分析的基本状态转换图

图1. 词法分析状态转换图

2.程序流程图如下图所示：
开始

是特殊符号
数字
掠过空格和回车符
error
N N N

Y Y
取数
是字母

Y

换成属性字
换成属性字
读标识符

查保留字表

查保留字表
N

换成属性字
换成属性字
Y

结束

图2 词法分析流程图

3.程序设计可按照状态转换图来设计，将关键字，界符，运算符保存在数组里。编写函数判断是否数组里有符合的字符串。
4程序分析过程可以为一下几个步骤：
（1）字符串的输入采用读取文件方式，然后将文件中的数据读入数组中。

String[] strs = null;
public void actionPerformed(ActionEvent arg0) {
if(strBuffer!=null){
strs = strBuffer.toString().split("###@@@");

}else{
strBuffer = new StringBuffer(getContentArea().getText());
strs = strBuffer.toString().split("\r\n");
}
for(String str :strs){
analysis.analyse(str);
}
getAnalysisArea().setText("");
getAnalysisArea().setText("分析结果如下:"+"\r\n"+
"源程序共有"+strs.length+"行\r\n"+
analysis.getBuffer().toString());

}
（2）对标识符和关键字的判断
int x=0;
for(int i=0;i<str.length;i++){
int flag=0;
String str1="";
char chars[]=str[i].toCharArray();
for(int j=0;j<chars.length;j++){
String str2="";
str2+=chars[j];
if(ReadFile.equalsChar("util/operator.txt", str2)){
if(str1.length()!=0){
map.put(x, str1);
x++;
}
str1="";
map.put(x, str2);
x++;
}else{
str1+=chars[j];
if(j==chars.length-1){
map.put(x, str1);
x++;
}
}
}
}
return map;
（3） 以（具体输入词 ，类型）形式输出

public class Analysis {
private String word=""; //分析得到的字符串
private String keyWord[]={"main","extends","implement","import","pakage","this","throw","throws","new","implements","try",//一般关键字
"int","char","float","boolean","byte","class","long","short",//数据类型关键字
"void","const","abstract","final","private","protected","public","static","super",//修饰关键字
"switch","default","for","continue","if","else","then","while","switch","break","begin","end","case","catch","return"};//语句控制关键字

private String id[]=new String[1000];
private int idLength=0;//记录标志符表中存放的标志符的个数
private String num[]=new String[1000];
private int numLength=0;//记录常数表中存放的常数的个数
private int line=0;//当前读到的行数
private StringBuffer buffer = new StringBuffer();

/**
* 判断是否为数字
*
* */

public boolean isDigit(char ch){
if((ch>='0')&&(ch<='9'))
return true;
else
return false;
}

/**
* 判断是否为字母
*
* */
public boolean isLetter(char ch){
if(((ch>='A')&&(ch<='Z'))||((ch>='a')&&(ch<='z')))
return true;
else
return false;
}

/**
* 判断是否为关键字
*
* */
public void isKeyword(String str){
int i=0;
for(;i<keyWord.length;i++){
if(str.equals(keyWord[i])) //是关键字
{
System.out.println("关键字："+str);
buffer.append("关键字："+str).append("\r\n");
i=keyWord.length;//结束循环，i等于keyWord.length+1

}
}//结束循环,i等于keyWord.length

if(i==keyWord.length){//普通标志符
int j=0;
for(;j<idLength;j++){//在标志符表中查找是否有该标志符
if(str.equals(id[j]))//标志符表中已经有该标志符
{
System.out.println("标识符："+str);//输出该标志符在标志符表中的位置
buffer.append("标识符："+str).append("\r\n");
j=idLength;//结束循环，j等于idLength+1
}
}
if(j==idLength){//标志符表中没有该标志符，将该标志符存入标志符表中，并返回其在符号表中的位置
idLength++;//标志符新增一个
id[idLength-1]=str;//将新标志符存放到标志符表中，索引从0开始
System.out.println("标识符："+str);
buffer.append("标识符："+str).append("\r\n");
}
}
}

//是否为数字
public void isNumber(String str){
int i=0;
for(;i<numLength;i++){
if(str.equals(num[i])){
System.out.println("常量："+str);
buffer.append("常量："+str).append("\r\n");
i=numLength;
}
}
if(i==numLength){
numLength++;
num[numLength-1]=str;
System.out.println("常量："+str);
buffer.append("常量："+str).append("\r\n");
}
}

public void analyse(String str){
char ch;//存放当前字符
char ch2;//存放下一个字符
for(int i=0;i<str.length();i++,word=""){
ch=str.charAt(i);//从0索引
if(ch=='\n'||ch=='\t'||ch==' ');//忽略回车、Tab、空格字符
else if(isDigit(ch)){
word=word+ch;
for(int j=1;j<=str.length()-i;j++){
int k=i+j;
if(k==(str.length()+1)){//错误语句，没有;界符
isNumber(word);
j=str.length();//跳出循环
i=i+j-1;
}
else{
ch2=str.charAt(k);
if(isDigit(ch2)||ch2=='.'){
word=word+ch2;
}
else{
isNumber(word);
i=i+j-1;//跳过j-1个字符
j=str.length();//跳出循环
}
}
}
}
else if(isLetter(ch)||ch=='_'){//变量以字符或者下划线开头
word=word+ch;
for(int j=1;j<=str.length()-i;j++){
int k=i+j;
if(k==str.length()){
isKeyword(word);
i=i+j-1;
j=str.length();//识别到行尾，跳出循环
}
else{
ch2=str.charAt(k);
if(isLetter(ch2)||isDigit(ch2)||ch2=='_'){//变量由字母、数字或下划线组成
word=word+ch2;
}
else{
isKeyword(word);
i=i+j-1;//跳过j-1个字符
j=str.length();//跳出循环，识别下一个单词
}
}
}
}
else if(ch=='+'){
word=word+ch;
ch2=str.charAt(i+1);
if(ch2=='='){
System.out.println("符号： "+ch+ch2);
buffer.append("符号： "+ch+ch2).append("\r\n");
i++;
}
else{
System.out.println("符号："+ch);
buffer.append("符号："+ch).append("\r\n");
}
}
else if(ch=='-'){
word=word+ch;
ch2=str.charAt(i+1);
if(ch2=='='){
System.out.println("符号： "+ch+ch2);
buffer.append("符号： "+ch+ch2).append("\r\n");
i++;
}
else{
System.out.println("符号："+ch);
buffer.append("符号："+ch).append("\r\n");
}
}

else if(ch=='*'){
word=word+ch;
ch2=str.charAt(i+1);
if(ch2=='='){
System.out.println("符号： "+ch+ch2);
buffer.append("符号： "+ch+ch2).append("\r\n");
i++;
}else{
System.out.println("符号："+ch);
buffer.append("符号："+ch).append("\r\n");
}
}
else if(ch=='/'){
word=word+ch;
ch2=str.charAt(i+1);
if(ch2=='='){
System.out.println("符号： "+ch+ch2);//除等/=
buffer.append("符号： "+ch+ch2).append("\r\n");
i++;
}
else if(ch2=='/'){
System.out.print("单行注释\t");
buffer.append("单行注释\t").append("\r\n");
System.out.print("注释内容为：");
buffer.append("注释内容为：").append("\r\n");
for(int m=i;m<str.length();m++){
System.out.print(str.charAt(m));
buffer.append(str.charAt(m));

}
System.out.println();
buffer.append("\r\n");
i=str.length();//注释行//，读取下一行
}
else{
System.out.println("符号："+ch);
buffer.append("符号："+ch).append("\r\n");

}
}
else if(ch=='%'){
word=word+ch;
ch2=str.charAt(i+1);
if(ch2=='='){
System.out.println("符号： "+ch+ch2);
buffer.append("符号： "+ch+ch2).append("\r\n");
i++;
}
else{
System.out.println("符号："+ch);
buffer.append("符号："+ch).append("\r\n");
}
}
else if(ch=='<'){
word=word+ch;
ch2=str.charAt(i+1);
if(ch2=='='){
System.out.println("符号： "+ch+ch2);
buffer.append("符号： "+ch+ch2).append("\r\n");
i++;
}
else{
System.out.println("符号："+ch);
buffer.append("符号："+ch).append("\r\n");
}
}
else if(ch=='>'){
word=word+ch;
ch2=str.charAt(i+1);
if(ch2=='='){
System.out.println("符号： "+ch+ch2);
buffer.append("符号： "+ch+ch2).append("\r\n");
i++;
}
else{
System.out.println("符号："+ch);
buffer.append("符号："+ch).append("\r\n");
}
}
else if(ch=='='){
word=word+ch;
ch2=str.charAt(i+1);
if(ch2=='='){
System.out.println("符号： "+ch+ch2);
buffer.append("符号： "+ch+ch2).append("\r\n");
i++;
}
else{
System.out.println("符号："+ch);
buffer.append("符号："+ch).append("\r\n");
}
}
else if(ch=='!'){
word=word+ch;
ch2=str.charAt(i+1);
if(ch2=='='){
System.out.println("符号： "+ch+ch2);
buffer.append("符号： "+ch+ch2).append("\r\n");
i++;
}
else{
System.out.println("符号："+ch);
buffer.append("符号："+ch).append("\r\n");
}
}
else if(ch=='&'){
word=word+ch;
ch2=str.charAt(i+1);
if(ch2=='&'){
System.out.println("符号： "+ch+ch2);
buffer.append("符号： "+ch+ch2).append("\r\n");
i++;
}
else{
System.out.println("非法字符&");
buffer.append("非法字符&");
System.out.println("位置："+line+"行"+i+"字符");
buffer.append("位置："+line+"行"+i+"字符").append("\r\n");
}
}
else if(ch=='|'){
word=word+ch;
ch2=str.charAt(i+1);
if(ch2=='|'){
System.out.println("符号： "+ch+ch2);
buffer.append("符号： "+ch+ch2).append("\r\n");
i++;
}
else{
System.out.println("非法字符|");
buffer.append("非法字符|");
System.out.println("位置："+line+"行"+i+"字符");
buffer.append("位置："+line+"行"+i+"字符").append("\r\n");
}
}
else if(ch=='('){
word=word+ch;
System.out.println("符号："+ch);
buffer.append("符号："+ch).append("\r\n");
}
else if(ch==')'){
word=word+ch;
System.out.println("符号："+ch);
buffer.append("符号："+ch).append("\r\n");
}
else if(ch=='['){
word=word+ch;
System.out.println("符号："+ch);
buffer.append("符号："+ch).append("\r\n");
}
else if(ch==']'){
word=word+ch;
System.out.println("符号："+ch);
buffer.append("符号："+ch).append("\r\n");
}
else if(ch=='{'){
word=word+ch;
System.out.println("符号："+ch);
buffer.append("符号："+ch).append("\r\n");
}
else if(ch=='}'){
word=word+ch;
System.out.println("符号："+ch);
buffer.append("符号："+ch).append("\r\n");
}
else if(ch==','){
word=word+ch;
System.out.println("符号："+ch);
buffer.append("符号："+ch).append("\r\n");
}
else if(ch==';'){
word=word+ch;
System.out.println("符号："+ch);
buffer.append("符号："+ch).append("\r\n");
}
else if(ch=='"'){
word=word+ch;
System.out.println("符号："+ch);
buffer.append("符号："+ch).append("\r\n");
}
else if(ch=='\''){
word=word+ch;
System.out.println("符号："+ch);
buffer.append("符号："+ch).append("\r\n");
}
else if(ch=='.'){
word=word+ch;
System.out.println("符号："+ch);
buffer.append("符号："+ch).append("\r\n");
}
else{
System.out.println("非法字符："+ch);
buffer.append("非法字符："+ch);
System.out.println("位置："+(line+1)+"行"+(i+1)+"字符");
buffer.append("位置："+(line+1)+"行"+(i+1)+"字符").append("\r\n");
}
}
}

4 实验结果

图3 实验结果
实验二 LL（1）分析
1 实验目的
根据某一文法编制调试LL（1）分析程序，以便对任意输入的符号串进行分析。本次实验的目的主要是加深对预测分析LL（1）分析法的理解。

2 实验内容
对下列文法，用LL（1）分析法对任意输入的符号串进行分析：
（1）E->TE’
（2）E’->+T E’
（3）E’->ε
（4）T->F T’
（5）T’->*F T’
（6）T’->ε
（7）F->(E)
（8）F->i
程序要求为该文法构造预测分析表，并按照预测分析算法对输入串进行语法分析，判别程序是否符合已知的语法规则，如果不符合则输出错误信息。
3 实验步骤
1.定义部分：定义变量，常量；
2. 根据已由的文法规则建立LL（1）分析表；
3.控制部分：从键盘输入表达式符号串
4.利用LL（1）分析算法对表达式进行处理：根据LL（1）分析表对表达式符号串进行堆栈或其他操作，输出分析结果。若分析遇到错误，输出错误信息。
4 实验结果
对输入串i+i*i#进行分析：

图1 实验结果

实验三 逆波兰式的产生及计算
1 实验目的
将用中缀式表示的算术表达式转换为用逆波兰式表示的算术表达式，并计算用逆波兰式来表示的算术表达式的值。
2 实验内容
编写程序将输入的中缀表达式转化为后缀表达式，并计算结果。
例如，输入为：12+(33-2)*8+4-15
输出如下：

后缀表达式：12&33&2&-&8&*&+&4&+&15&-
计算结果:249.0
3 实验步骤
逆波兰式定义将运算对象写在前面，而把运算符号写在后面。用这种表示法表示的表达式也称做后缀式。逆波兰式的特点在于运算对象顺序不变，运算符号位置反映运算 顺序。
1.逆波兰式生成的算法
(1)首先构造一个运算符栈，此运算符在栈内遵循越往栈顶优先级越高的原则。
(2)读入一个用中缀表示的简单算术表达式，为方便起见,设该简单算术表达式的右端多加上了优先级最低的特殊符号“#”。
(3)从左至右扫描该算术表达式，从第一个字符开始判断，如果该字符是数字， 则分析到该数字串的结束并将该数字串直接输出。
(4)如果不是数字，该字符则是运算符，此时需比较优先关系。 做法如下：将该字符与运算符栈顶的运算符的优先关系相比较。如果，该字符优 先关系高于此运算符栈顶的运算符，则将该运算符入栈。倘若不是的话，则将此 运算符栈顶的运算符从栈中弹出，将该字符入栈。
(5)重复上述操作(1)-(2)直至扫描完整个简单算术表达式， 确定所有字符都得到正 确处理， 我们便可以将中缀式表示的简单算术表达式转化为逆波兰表示的简单算术表达式。

2.逆波兰表达式求值的算法步骤
(1)构造一个栈，存放运算对象。
(2)读入一个用逆波兰式表示的简单算术表达式。
(3)自左至右扫描该简单算术表达式并判断该字符，如果该字符是运算对象，则 将该字符入栈。若是运算符，如果此运算符是二目运算符，则将对栈顶部的两个 运算对象进行该运算， 将运算结果入栈，并且将执行该运算的两个运算对象从栈 顶弹出。如果该字符是一目运算符，则对栈顶部的元素实施该运算，将该栈顶部 的元素弹出，将运算结果入栈。
(4)重复上述操作直至扫描完整个简单算术表达式的逆波兰式，确定所有字符都 得到正确处理，我们便可以求出该简单算术表达式的值。
4 实验结果
对输入串(4+7)*6/5#进行分析及计算：
后缀表达式：4&7&+&6&*&5&/
计算结果:13.2
对输入串4.5*10-(1+80)#进行分析及计算：

后缀表达式：4.5&10&*&1&80&+&-
计算结果:-36.0

实验四 算符优先分析算法
1 实验目的
设计、编制并调试一个算符优先分析算法，加深对此分析法的理解
2 实验内容
完成一个交互式面向对象的算符优先分析程序，而一个交互式面向对象的算符优先分析程序基本功能是：
（1） 输入文法规则
（2） 对文法进行转换
（3） 生成每个非终结符的FirstVT和LastVT
（4） 生成算符优先分析表
（5） 再输入文法符号
（6） 生成移进规约步骤

3 实验步骤
1.设计相关数据结构
char lable[20]; 文法终极符集
char first[10][10]; 文法非终结符FIRSTVT集
char last[10][10]; 文法非终结符LASTVT集
char st[10][30]; 用来存储文法规则
2. 算符优先分析法的分析过程及其构成
（1）规定运算符之间的优先关系（终结符）和结合性
（2）比较相邻运算符之间的关系以确定句型的可归约串
3.分析步骤
（1）判断文法是否是算符优先文法
（2）构造优先关系表
（3）算符优先程序寻找可归约串
4 实验结果

图1 实验结果

实验五 LR（1）分析法
1 实验目的
构造LR(1)分析程序，利用它进行语法分析，判断给出的符号串是否为该文法识别的句子，了解LR（K）分析方法是严格的从左向右扫描，和自底向上的语法分析方法。

2 实验内容
实验规定对下列文法，用LR（1）分析法对任意输入的符号串进行分析：
（0）E->S
（1）S->BB
（2）B->aB
（3）B->b
(1)输入一以#结束的符号串(包括a，b#)：在此位置输入符号串
(2)输出过程如下：
步骤
状态栈
符号栈
输入串
ACTION
GOTO
1
0
#
Abb#
S3

2 实验步骤
2.1程序结构描述
（1）定义部分：定义常量、变量、数据结构。
（2）初始化：设立LR(1)分析表、初始化变量空间（包括堆栈、结构体、数组、临时变量等）；
（3）控制部分：从键盘输入一个表达式符号串；
（4）利用LR(1)分析算法进行表达式处理：根据LR(1)分析表对表达式符号串进行堆栈（或其他）操作，输出分析结果，如果遇到错误则显示错误信息。
2.2 LR（1）分析器结构由三部分组成：

输入串XXX…#

输出
Xn
。
。
。
X1
#
n1
。
。
。
1
0
总控程序

ACTION
表
GOTO
表

图1 LR（1）分析器构成
（1）其中:SP为栈指针，S[i]为状态栈，X[i]为文法符号栈。状态转换表用GOTO[i，X]=j表示，规定当栈顶状态为i，遇到当前文法符号为X时应转向状态j，X为终结符或非终结符。
（2） ACTION[i，a