编译原理课程设计教案.docx
《编译原理课程设计教案.docx》由会员分享，可在线阅读，更多相关《编译原理课程设计教案.docx（22页珍藏版）》请在冰点文库上搜索。
编译原理课程设计教案
黄冈师范学院
《编译原理课程设计》教案
（2011·春）
授课教师：
张瑞红
授课班级：
计科2008级
授课时间：
2010-2011二
课题一有限自动机的运行
一、设计题目：
有限自动机的运行
二、设计目的：
1、理解有限自动机的作用
2、利用转态图和状态表表示有限自动机
3、以程序实现有限自动机的运行过程
三、设计内容：
（注：
题目详细要求）
利用状态表和有限自动机的运行原理编制程序，使得程序能够识别一个输入串是否为一个有效的符号串，具体可以选择下面之一：
无符号定点实数、自然数、整数、十六进制数或其它自己定义的符号串。
四、设计思想：
（注：
算法思想、程序流程图、不要写代码）
本程序实现对无符号定点实数的判断，正确接受，否则不接受。
本程序的关键在状态表和缓冲区的运用。
首先定义了一个布尔型函数ReadALine把输入的字符串送到缓冲区中；然后定义了布尔型函数Run 和Getchar实现对输入字符串的正确性判断，更改Run函数可以改变程序功能：
如可将状态表改变成识别“偶数”的有限自动机的状态表。
程序流程图如下：
（学生自己画）
五、运行结果与数据分析：
六、设计总结体会：
（学生自己写，此处可参考）
通过这次课程设计，我对程序的编译和运行过程有了更进一步的了解，对程序的底层设计、代码优化也有了初步的认识，而且知道了如何从根本上来提高程序运行的速度。
附录：
（完整代码）
#include
#include
//状态表相关存储信息：
#define STATE_NUMBER 4 //状态数目
#define CHAR_NUMBER 2 //输入字符的种类:
d 和 .
#define DIGIT 0 //输入数字在状态表中位于第0列
//State[][]为状态表，以整数组形式存放，0,1,2,3表示状态，-1表示没有此状态
int State[STATE_NUMBER][CHAR_NUMBER]= {{1,-1},{1,2}, {3,-1}, {3,-1}};
int Q[STATE_NUMBER] = {0,1,0,1}; //终态标志：
0非终态，1终态。
//缓冲区：
//输入缓冲区：
由专门函数操作（ReadALine（）,GetChar（））
#define BUFFER_SIZE 1000 //表达式缓冲区大小
char Buffer[BUFFER_SIZE]; //表达式缓冲区，以'\0'表示结束
int ipBuffer = 0; //表达式缓冲区当前位置序号
char ch; //存放取得的一个字符
//函数声明：
bool Run（）; //对存储在缓冲区的一行字符串（以'#'结束）进行运行
void Init（）; //全局初始化
bool ReadALine（）; //从键盘读一行（没有空格），存于表达式缓冲区Buffer[]中
char GetChar（）; //从缓冲区取一个字符，返回该字符的同时将它存于全局变量ch中
//主程序：
void main（）
{ Init（）;
while（ReadALine（）） //读一行成功，对它进行判断
{ if（Run（）） //对该行进行运行，看是否能被接受？
printf（"接受\n\n"）;
else printf（"不接受\n\n"）;
}
}
//对存储在缓冲区的一行字符串（以'#'结束）进行运行
//返回：
如果是无符号定点实数，返回true；否则返回：
false
bool Run（）
{ int S=0; //S存放运行时的当前状态，目前为初态
while（GetChar（）!
='#'）
{ if（ch >= '0'&&ch<='9'）
S = State[S][DIGIT]; //将状态转换成输入后的状态
else //其他都为非法字符
return false;
if（S == -1） //处于非法状态
return false;
}
//运行结束，判断S是否为终态
if（Q[S] == 1） //终态
return true;
else //非终态
return false;
}
//全局初始化
void Init（）
{ //好像无需初始化
printf（"程序功能：
输入一个字符串，判断它是否是a。
\n"）;
printf（"======================================================\n\n"）;
}
//从键盘读一行（没有空格），存于表达式缓冲区Buffer[]中，以'#'结束，并置ipBuffer=0；
//读到非空字符串：
返回 true；读到单独的“#”：
返回 false
bool ReadALine（）
{ int l;
printf（"请输入以\"#\"号结束的无空格字符串：
"）;
scanf（"%s",Buffer）;
l = strlen（Buffer）; //读入的字符串的长度
if（l == 0） return ReadALine（）; //输入了空字符串，重新输入
if（Buffer[0] == '#'） return false; //输入单独的'#'表示不再输入
Buffer[l] = '#'; //最后一个字符用结束标记'#'代替（本来是'\0'）
ipBuffer = 0; //初始化缓冲区指针
return true;
}
//从缓冲区取一个字符，返回该字符的同时将它存于全局变量ch中
//成功：
返回字符；不成功：
返回'#'
char GetChar（）
{ if（（ch = Buffer[ipBuffer]） !
= '#'）
ipBuffer ++;
return ch;
}
五、运行结果与数据分析：
六、设计总结体会：
课题二：
简单词法分析器设计（C或C++）
一、设计题目：
简单词法分析器设计（C或C++）
二、设计目的要求：
1、目的：
通过设计、编程、调试出一个具体词法分析程序，加深对词法分析原理的理解，掌握其设计方法。
2、要求：
1）整理出所有单词符号及内部表示
分类：
各关键字、标识符、运算符、分界符、常数
2）画出状态转换图
3）编程。
要求用自动机的方法进行编程。
①预处理，去除注释、多余空格、回车换行符等。
②词法分析程序能通过实例数据的测试。
备注：
设计词法分析程序时，应考虑能为语法分析程序调用。
4）写出设计报告，内容为：
状态转换图、单词符号及内部表示、符号表、出错处理、编程方法等。
三、实验内容：
选择一个词法分析方法，编写一个的词法分析器，对下面的实例进行测试。
测试用例：
programtestexample;
{读入一组整数，统计并输出：
其中非负整数之和，整组数的10倍平均值}
vark,sum1,sum2,x:
int;
constnum=20,times=10;
begin
sum1:
=0;sum2:
=0;
k:
=num;
whilek>=1do
begin
read（x）;
ifx>=0
thensum1:
=sum1+x;
sum2:
=sum2+x;
k:
=k-1;
end;
write（sum1,times*sum2/num）;
end.
四、设计思想：
（注：
算法思想、程序流程图、不要写代码）
利用单词的构成规则，对输入的字符串进行分析再归类即可。
（流程图学生自己画）
五、运行结果与数据分析：
六、设计总结体会：
课题三：
语法分析器的设计
一、设计题目：
语法分析器的设计
二、设计目的要求：
通过设计、编程、调试出一个具体语法分析程序，能调用词法分析程序为其提供单词符号串，进行语法分析，掌握语法分析方法和程序设计方法。
三、设计内容：
任选一种语法分析方法进行程序设计，语法分析程序能通过实例数据的测试。
写出设计报告，内容为：
所选的语法分析方法、算法、改写的文法、符号表、出错处理、编程方法等。
SPL语言的文法
<程序>:
:
=<程序首部><说明部分><程序主体>
<程序首部>:
:
=program<标识符>;
<标识符>*:
:
=<字母>┃<字母><字母数字串>
<字母>*:
:
=a┃b┃┅┃y┃z
<字母数字串>*:
:
=<字母>┃<数字>┃<字母><字母数字串>┃<数字><字母数字串>
<数字>*:
:
=0┃<非0数字>
<非0数字>*:
:
=1┃┅┃8┃9
<说明部分>:
:
=var<变量组>:
int;┃const<常量组>;┃var<变量组>:
int;const<常量组>;
<变量组>:
:
=<标识符>┃<标识符>,<变量组>
<常量组>:
:
=<标识符>=<整数>┃<标识符>=<整数>,<常量组>
<整数>*:
:
=<数字>┃<非0数字><数字串>
<数字串>*:
:
=<数字>┃<数字><数字串>
<程序主体>:
:
=begin<执行语句>end.
<执行语句>:
:
=<语句>┃<语句>;<执行语句>
<语句>:
:
=<赋值语句>┃<条件语句>┃<循环语句>┃<读语句>┃<写语句>┃<复合语句>
<赋值语句>:
:
=<标识符>:
=<表达式>
<表达式>:
:
=<表达式>+<项>┃<表达式>-<项>┃<项>
<项>:
:
=<项>*<因子>┃<项>/<因子>┃<因子>
<因子>:
:
=（<表达式>）┃<标识符>┃<整数>
<条件语句>:
:
=if<表达式><关系符><表达式>then<语句>
<关系符>*:
:
==┃>┃<┃>=┃<=┃<>
<循环语句>:
:
=while<表达式><关系符><表达式>do<语句>
<读语句>:
:
=read（<变量组>）
<写语句>:
:
=write（<表达式组>）
<表达式组>:
:
=<表达式>┃<表达式>,<表达式组>
<复合语句>:
:
=begin<执行语句>end
【备注】1.SPL语言源程序格式自由；
2.SPL语言源程序中可以插入注解，用“{”、“}”括起来。
测试用例同课题二
四、设计思想：
（注：
算法思想、程序流程图、不要写代码）
根据自己选择语法分析方法（LL
（1）、LR（0）、OPG），先设计分析表再设计主控程序。
（LL
（1））主要算法:
构造算符优先分析表的算法以下几个步骤：
（1）构造文法G中非终结符号的FIRSTVT集合
FIRSTVT集合用一个整型二维数组F[q][f]表示，其值为0或1。
F是一个q*f的二维数组（q=文法G中非终结符号个数，f=文法G中终结符号个数）。
对于文法G的所有终结符，构造数组F[q][f]的算法（该算法使用一个STACK栈，用于存放含有一个非终结符和一个终结符对的结构体X。
）如下：
BEGIN
for任何非终结符P和终结符a对（P，a）
确定P在非终结符数组VN[]中的位置q1和a在终结符数组VT[]中的位置f1
F[q1][f1]=0；
for任何形如P-》a…或P-》Qa…的产生式
BEGIN
IFNOTF[q1][f1]F[q1][f1]=0；
将（P，a）放入结构体x；
X进STACK栈；
END
WHILESTACK栈非空
BEGIN
将STACK栈的栈顶元素出栈
FOR每个形如Q-》P…的产生式
BEGIN
确定Q在非终结符数组VN[]中的位置q2
IFNOTF[q2][f1]
BEGIN
F[q2][f1]=1；
将（Q，a）放入结构体X；
X进STACK栈；
END
END
END.
（2）构造文法G中非终结符号的LASTVT集合
类似于构造FIRSTVT集合，LASTVT集合用一个整型数组L[P，a]表示，其值为0或1。
L是一个q*f的二维数组（q=文法G中非终结符号个数，f=文法G中终结符号个数）。
对于文法G的所有终结符，构造数组L[q][f]的算法（该算法法使用一个STACK栈，用于存放含有一个非终结符和一个终结符对的结构体D。
）如下：
BEGIN
for任何非终结符P和终结符a对（P，a）
确定P在非终结符数组VN[]中的位置q1和a在终结符数组VT[]中的位置f1
L[q1][f1]=0；
for任何形如P-》…a或P-》…Qa的产生式
BEGIN
IFNOTL[q1][f1]L[q1][f1]=0；
将（P，a）放入结构体d；
D进STACK栈；
END
WHILESTACK栈非空
BEGIN
将STACK栈的栈顶元素出栈
FOR每个形如Q-》…P的产生式
BEGIN
确定Q在非终结符数组VN[]中的位置q2
IFNOTL[q2][f1]
BEGIN
L[q2][f1]=1；
将（Q，a）放入结构体D；
D进STACK栈；
END
END
END.
（3）构造文法G的优先关系表
使用文法G中任何非终结符号的FIRSTVT集合和LASTVT集合，可以构造文法G的优先关系表。
优先关系表用一个二维字符数组Z[][]表示，Z是一个f*f的数组（f=文法G中终结符号个数）。
Z表的值为‘0’、‘》’、‘《’或‘=’。
构造优先关系表Z[][]的算法如下：
{FOR每个形如产生式P-》Qa…或P-》…Qa
{在lastvt集的数组L[][]中确定Q对应的行元素值为1的下标j和a对应的列的下标l；
在算符优先表的数组Z[][]中,将Z[j][l]的值置‘》‘；}
FOR每个形如产生式P-》aQ…或P-》…aQ
{在firstvt集的数组F[][]中确定Q对应的行元素值为1的下标j和a对应的列的下标l；}
在算符优先表的数组Z[][]中,将Z[j][l]的值置‘《‘；
FOR每个形如产生式P-》…ab…或P-》…aQb…
{在终结符号集合的数组中找到a，b所对应的下标j，k；
在算符优先表的数组Z[][]中,将Z[j][l]的值置‘=‘；}
}
（4）判别文法G是否为算符优先文法
2.设计算符优先分析程序的算法
（1）判别输入串是否为文法G的句子
根据查找最左子素短语的方法，得到算符优先分析算法如下：
在算法中使用了一个符号栈B，用来存放终结符和非终结符，k代表符号栈S的使用深度：
{WHILE文法G为算符优先文法
DO{
将字符串放入数组string[]中；
K=0,初始化栈B[k]=’#’；
把当前字符读入字符变量a中；
IFS[k]为终结符J=k
ELSEJ=K-1
找出B[k]所对应的终结符及a所对应的终结符在Z[][]中的位置q,q3
IFZ[q][q3]==’=’或’<’K=k+1,B[k]=a入栈
ELSE打印“出错”
WHILEZ[q][q3]==‘》’
{DO{
R3=B[j]并找出r3在VT[]中的位置q5；
IFB[j-1]属于VT[]J=J-1；
ELSEJ=J-2；
找出B[j]在VT[]中的位置q6；}
WHILE（Z[q6][q5]==‘=’）
{将B[j+1]…B[k]归约为N
k=j-1；
B[k]=N；}
}
WHILE（a!
=’#’）
IF（a==’#’）输出“YES”
ELSE输出“NO”
}
（LR（0））主要算法：
·求解闭包算法：
⑴ch赋值为所求产生式圆点后的字符。
⑵从第一个产生式开始，遍历所有文法产生式，对行如E->.a的项目，
E==ch，且原闭包集中不含此项目，执行（3）,（4）,否则返回。
3将该产生式加入该闭包。
4递归调用闭包算法对新加入产生式进行闭包运算。
·求解Go集合算法
1ch赋值为吸收字符
2遍历该项目集的所有项目，对行如E->a.bB的项目，b==ch,创建新项目集并将该项目加入新项目集。
3如若该新项目集已存在，撤消，否则返回新项目集下标。
·求项目集算法
4对零项目求解求解闭包,得出项目集
.
5对项目集
求解Go集,得出新产生项目集的最大下标i;
⑸从项目集
到项目集
依次编历各项目集,求解该项目集闭包和该项目集Go集,
在此步中i值可能发生变化.
·构表算法
①对项目集
的每个项目圆点后的字符
②如果为空，判断是否为结束产生式，则将相应数组元素赋值abc
③否则为规约项目，赋相应
④如果为大写字母，则为移进项目,通过判断Go（）求得I,赋相应I;
⑤否则，通过判断Go（）求得I,赋相应
。
（OPG）主要算法和数据结构:
算符优先分析法是一种简单且直观的自下而上分析方法，特别适合于分析程序语言中的各类表达式，并且宜于手工实现。
算术优先分析，是依照算术表达式的四则运算过程来进行语法分析。
通常在算术表达式求值过程中，运算次序是先乘除后加减，这说明了乘除运算的优先级高于加减运算的优先级，乘除为同一优先级但运算符在前边的先做，这称为左结合，同样加减运算也是如此，这也说明了运算的次序只与运算符有关，而与运算对象无关，因而直观算符优先分析法的关键是对一个给定文法G，人为地规定其算符的优先顺序，即给出优先级别和同一个级别中的结合性质，算符间的优先关系表示规定如下：
a
b表示a的优先性低于b。
a
b表示a的优先性等于b，即与b相同。
a
b表示a的优先性高于b。
但必须注意，这三个关系和数学中的＜，＝，＞是不同的。
当有关系a
b时，却不一定有关系b
a，当有关系a
b时，却不一定有b
a，例如：
通常表达式中运算符的优先关系有+
-，但没有-
+，有'（'
'）'，但没有'）'
'（'。
即这种分析方法要预先规定运算符（确切地说是终结符）之间的优先关系和性质，然后借助于这种关系来比较相邻运算符的优先级，以确定句型的“可归约串”来进行归约。
定义：
设有一文法G，如果G中没有形如A→…BC…的产生式，其中B和C为非终结符，则称G为算符文法例如：
表达式文法E→E+E|E*E|（E）|i
其中任何一个产生式中都不包含两个非终结符相邻的情况，因此该文法是算符文法
1）文法
2）算法：
FIRSTVT；LASTVT；优先关系表；判断G是否是算符优先文法
3）构造算符优先表程序设计：
G的产生式存储和输入，可以定义、、；所涉及的主要数据结构（FITSTVT和LASTVT集合；优先关系表；STACK栈
·主要数据结构
1算符文法G的产生式存储和输入
定义一个二维数组p[10][10]存储G的产生式，h为产生式的个数，其元素为字符数组，每行字符存放的字符串最长为10，每一行存放一个产生式，算符文法G的产生式可以通过键盘，以字符方式输入，每个产生式以“#”结束。
2所涉及的主要数据结构
①firstvt集合和lastvt集合；用整形数组f[p，a]和l[p，b]表示，都是a*b的二维数组，（a为文法中非终结符的个数，b为文法中终结符的个数），其中p属于N,a属于T,输出的第一行T表示所有终结符,第一列N表示所有的非终结符.
②优先关系表用一个数组k[a,b]表示,k是一个b*b的二维数组（b为文法的终结符的个数）,其元素为二维字符数组,每个字符数组所存的字符串的长度为1,其中a,b属于终结符,r[a,b]=’=’,’<’,’>’,或为空,数组r[a,b]类型为字符型.输出时,第一行T表示所有的终结符,第二行T表示所有的终结符.
③一维数组T[n]存放所有的终结符,一维数组N[a]存放所有的非终结符,变量a,b分别表示非终结符,终结符.一维数组A[n]表示每个产生式的第一个字符在非终结符N[n]中的位置,B[n]表示没一个产生式的个数,f[p,a]为字符型,表示a是否是p的firstvt,l[p,a]为字符型,表示a是否为p的lastvt,k[a,a]表示终结符存在那种关系;’=’,,’<’,’>’或空,如果存在两种对应关系,则说明该文法不是算符优先文法。
五、运行结果与数据分析：
六、设计总结体会：
课题四：
WHILE循环语句的翻译程序设计
一、设计题目：
WHILE循环语句的翻译程序设计
二、设计目的要求：
通过设计、编程、调试出一个具体语法分析程序，能调用词法分析程序为其提供单词符号串，进行语法分析，掌握语法分析方法和程序设计方法。
三、设计内容：
1、写出符合题目要求的文法及属性文法。
2、完成题目要求的中间代码三地址表示的描述。
3、写出递归下降法的思想，完成语法分析和语义分析程序设计。
4、编制好分析程序后，设计若干用例，上机测试并通过所设计的分析程序。
5、设计报告格式按要求书写。
课程设计报告书正文的内容应包括：
1系统描述（问题域描述）；
2文法及属性文法的描述；
3语法分析方法描述及语法分析表设计；
4给出中间代码形式的描述及中间代码序列的结构设计；
5简要的分析与概要设计；
6详细的算法描述（流程图或伪代码）；
7给出软件的测试方法和测试结果；
8研制报告（研制过程，本设计的评价、特点、不足、收获与体会等）；
四、设计思想：
（注：
算法思想、程序流程图、不要写代码）
按照课程设计的要求，写一个能识别while循环语句的文法，通过一定的变换使它符合递归下降法的要求，然后按照这个文法编写一个程序，该程序能识别输入的语句是否符合while语句的文法，或者能不能通过文法的开始符号推导出该语句。
该程序应该包括词法分析器，能对输入的语句进行词法分析，然后再对结果进行语法分析。
词法分析器应能识别关键字，标示符，常量，操作符等。
该程序的语法分析器能对输入的语法进行分析，判断输入语句能否满足while循环语句的文法。
通过递归下降的方法对语句进行分析，看能否通过开始符号推导出来。
该程序的语义分析器就是对分析结果进行输出，要求输出结果是三地址形式的。
1、文法描述
:
:
=while（<条件表达式>）（<赋值语句>|）
<条件表达式>:
:
=（<标识符>|<无符号整数>）<条件运算符>（<标识符>|<无符号整数>）
<标识符>:
:
=<字母>（<字母>|<数字>）
<条件运算符>:
:
=>|<|=
<无符号整数>:
:
=<数字>（<数字>）
<赋值语句>:
:
=<标识符>=（<标识符>|<数字>）<算术运算符>（<标识符>|<数字>）
<算术运算符>:
:
=+|-|*|/
<
升级会员 