福建工程学院《编译原理实验指导》文档格式.docx
《福建工程学院《编译原理实验指导》文档格式.docx》由会员分享,可在线阅读,更多相关《福建工程学院《编译原理实验指导》文档格式.docx(13页珍藏版)》请在冰点文库上搜索。
实验内容:
1.删除注释
2.删除续行符以及后续换行符
3.将换行符和TAB统一替换为空格
4.将大写字母变换为小写字母,或者相反,以实现不区分大小写
5.识别标号区,识别续行标志。
实验步骤:
(1)熟悉教材关于词法分析中预处理的原理。
(2)依照教材关于源程序预处理的算法,使用C/C++语言或其它语言实现该算法。
(3)调试、编译、运行程序。
实验要求:
在下次实验时提交本次实验的实验报告(实验报告包括实验目的、实验内容、实验实现过程、源程序、实验结果、实验体会)。
实现代码:
#include<
fstream.h>
iostream.h>
#include<
conio.h>
voidpro_process(char*);
voidmain(){//定义扫描缓冲区charbuf[4048]={'
\0'
};
//缓冲区清0//调用预处理程序pro_process(buf);
//在屏幕上显示扫描缓冲区的内容cout<
<
buf<
endl;
}voidpro_process(char*buf){ifstreamcinf("
source.txt"
ios:
:
in);
inti=0;
//计数器charold_c='
cur_c;
//前一个字符,当前字符boolin_comment=false;
//false表示当前字符未处于注释中while(cinf.read(&
cur_c,sizeof(char)))//从文件读一个字符{switch(in_comment){casefalse:
if(old_c=='
/'
&
&
cur_c=='
*'
)//进入注释{i--;
//去除已存入扫描缓冲区的字符’/’in_comment=true;
}else{if(old_c=='
\\'
\n'
)//发现续行i--;
//去除已存入扫描缓冲区的字符’\’else{if(cur_c>
='
A'
cur_c<
Z'
)//大写变小写cur_c+=32;
if(cur_c=='
\t'
||cur_c=='
)//空格取代tab换行cur_c+='
'
;
buf[i++]=cur_c;
}}break;
casetrue:
)//离开注释in_comment=false;
}//endofswitchold_c=cur_c;
//保留前一个字符}//endofwhilebuf[i++]='
#'
//在源程序词尾加字符#}
实验二简单程序设计语言的词法分析器
掌握词法分析器的原理
将源程序预处理、状态图转换等结合,建立简单的程序设计语言词法分析器
要求能对简单程序设计语言进行词法分析,具体内容如下:
字符集
{‘a’..’z’,‘0’..’9’,’+’,’=’,’*’,’,’,’;
’,’(‘,’)’,’#’}
若发现字符集之外的字符,即为非法字符,当出现非法字符时终止词法分析器的运行。
单词集
基本字:
begin、end、integer、real
标识符:
以字母开始的数字字母串
无符号整常数
无符号实常数
运算符:
+、*、++、=
界符:
、;
、(、)、#
错误词形:
.(前后无数字字符的小数点)
单词编码
begin(‘{‘,“NUL”}、end(‘)‘,“NUL”}、integer(‘a‘,“NUL”}、real(‘c‘,“NUL”}
(‘i’,字符串)
无符号整常数:
(‘x’,字符串)
无符号实常数:
(‘y’,字符串)
运算符;
=(‘=’,“NUL”)、+(‘+’,“NUL”)、*(‘*’,“NUL”)、++(‘$’,“NUL”)
(‘,’,“NUL”)、;
(‘;
’,“NUL”)、((,C‘,’,“NUL”)、)’)’,‘NUL’)、#(‘#’,“NUL”)
状态转换图
单词分为单字符单词或多字符单词。
(1)熟悉习教材关于词法分析的原理。
(2)依照教材关于词法分析的算法,使用C/C++语言实现该算法。
词法分析有5个函数构成,即预处理函数pro_process、扫描函数scanner、拼接函数concat、查基本字表函数reserve和主函数main。
#include<
string.h>
stdlib.h>
constshortWORDLEN=20;
structcode_val{
charcode;
charval[WORDLEN];
}
voidconcat(char[],char);
charreserve(char[]);
code_valscanner(char*);
voidmain()
{
charbuf[4048]={‘\0’};
pro_process(buf);
cout<
ofstreamcoutf(“Lex_r.txt”,ios:
out);
code_valt;
do{
t=scanner(buf);
//调用一次scanner函数,获得一个单词二元式
coutf<
t.code<
’\t’<
t.val<
}while(t.code!
=’#’
cout<
”endoflexicalanalysis”<
实验三递归下降分析法
掌握递归下降语法分析的原理
利用高级语言的递归过程为给定文法的每个非终结符构造对应的递归函数
若文法不含左递归,并且每个非终结符的所有候选式的首符集都两两不相交,就有可能构造一个不带回溯的自上而下的语法分析程序。
这个分析程序是由一组递归过程(函数)组成的,每个过程(函数)对应文法的一个非终结符。
如果用某种高级语言写出所有递归过程(函数),那就可以用这个高级语言的编译系统产生整个分析程序。
这个分析程序称为递归下降分析器。
用类C语言为文法G的每个非终结符构造对应的递归函数。
文法G如下所示:
E→TE’
E’→+TE’|ε
T→FT’
T’→*FT’|ε
F→(E)|i|x|y
(1)熟悉习教材关于语法分析的原理。
(2)依照教材关于基于递归下降分析的算法,使用C/C++语言实现该算法。
假设源程序为“(a+b)*c”,经词法分析,单词二元式序列存放于文件lex_r.txt中。
递归下降分析器从文件lex_r.txt读入数据进行处理。
每次读入的是单词二元式,即单词的种别(code)和单词的值(val),而分析器仅使用单词的种别。
charcode;
charval[20];
}t;
ifstreamcinf(“lex_r.txt”,ios:
voidE()
T;
E’;
voidE’()
if(t.code==’+’){
cinf>
>
t.code>
t.val;
}
voidT()
F;
T’;
voidT’()
if(t.code==’*’){
voidF()
if(t.code==’(‘){
E;
If(t.code==’)’)cinf>
elseif(t.code==’i’||t.code==’x’||t.code==’y’)
实验四预测分析析法
4学时
本实验为综合性实验,综合了栈、表等内容,其目的是在掌握栈、表以及预测分析法原理的基础上,实现预测分析表的建立和控制程序。
用类C语言为文法G进行语法分析。
预测分析法是一种不使用递归的语法分析方法,由一张分析表和一个控制程序构成的。
一、预测分析表的构造
产生式的一般形式为:
A→α1|α2|…|αn|ε
若当前输入符号t.code∈first(αi),则用A→αi推导;
若当前输入符号t.code∈follow(A),则用A→ε推导;
除此以外均为错误。
候选式的选取是由两个要素决定的:
一个是句型中的非终结符A,从它出发进行最左推导;
另一个是当前输入符号t.code。
可以把上述非终结符A的产生式映射成矩阵M的一行,矩阵M以文法的非终结符为纵坐标(行),以文法的终结符为横坐标(列)。
矩阵元素M[A][x]存放着一条关于A的产生式,指出当A面临输入符号x所应采用的候选。
若a∈first(αi),则M[A][a]=“A→αi”;
若b∈follow(A),则M[A][b]=“A→ε”。
M[A][c]中也可能存放一个“出错标志”,指出A根本不该面临输入符号c,在矩阵M中“出错标志”用空白表示。
预测分析表M的构造方法:
1构造所有候选式的first集,构造所有的非终结符的follow集;
2对于文法G的每个产生式A→α,执行③和④;
3对于每个终结符a∈first(α),把A→α加至M[A][a];
4若ε∈first(α),则对于每个终结符b∈follow(A),把A→α加至M[A][b];
5把所有未定义的M[A][c]标上“出错标志”。
二、预测分析控制程序
设置一个栈stack,用于存放文法符号。
初始时,栈底先放一个‘#’,然后放进文法开始符号S。
预测分析控制程序任何时刻的动作,都按照栈顶符号X和当前输入符号t.code进行,控制程序每次执行下述3种可能的动作之一:
1若X和t.code均为‘#’,则分析成功,输入串为合法句子,终止分析过程。
2若X是终结符,并且X和t.code相等,表示期望的终结符号和输入符号相等。
让X出stack栈,并输入下一个单词二元式。
3若X是非终结符,则查预测分析表。
若M[X][t.code]存放着关于X的一个产生式,那么,让X出stack栈,然后把产生式右部符号串按反序一一推进stack栈。
若右部符号串为空字ε,则意味着无任何文法符号进栈。
(1)熟悉习教材关于预测分析法的原理。
(2)依照教材关于基于预测分析的语法分析算法,使用C/C++语言实现该算法。
voidLL1()
structcode_val{
Charcode;
charvar[20];
}t;
charstack[20]={‘#’,’S’};
charX;
inttop=1;
cinf>
while
(1)do{
x=stack[top--];
switch(X)of{
case‘#’:
if(x==t.code){
cout>
”Acc”;
break;
caseX∈VT:
if(X==t.code){
caseX∈VN:
if(M[X][t.code]=X→X1X2…Xk){
X1X2…Xk按反序进栈;
top=top+k;
实验五LR语法分析
掌握LR语法分析的基本原理
基本原理:
把每个句柄的识别(产生式右部的符号串)过程划分为若干状态,每个状态只识别句柄的一个符号,若干个状态就可识别句柄左端的一部分符号。
利用高级语言实现LR语法分析器
文法:
(0)S→E
(1)E→E+T
(2)E→T
(3)T→T*F
(4)T→F
(5)F→(E)
(6)F→i
假设分析表用二维数组M存储,栈顶状态用Stop表示,当前输入符号用t.code表示,控制程序的算法可归纳如下:
(1)移进。
若M[Stop][t.code]=sj,说明句柄尚未完成,应执行移进操作。
S表示移进,j为状态号,将j移入状态栈,将t.code移入符号栈,j成为新的栈顶状态Stop。
读下一个单词。
(2)归约。
若M[Stop][t.code]=rk,说明句柄已出现在栈顶,应该用编号为k的产生式A→B进行归约。
假设LEN(β)=r,M[Stop-r][t.code]=j。
首先将栈顶r个元素出栈,然后将j和A分别移入状态栈和符号栈,j成为新的栈顶状态Stop。
当前处理单词不变。
(3)接受。
M[Stop][t.code]=Acc,表示输入串是一个合法句子,程序终止运行。
(4)出错。
M[Stop][t.code]=空白,表示出错,最简单处理为程序终止运行。