《编译原理课程设计教案》由会员分享，可在线阅读，更多相关《编译原理课程设计教案（16页珍藏版）》请在金锄头文库上搜索。
1、黄冈师范学院编译原理课程设计编译原理课程设计教案教案（20112011春）春）授 课 教 师： 张 瑞 红 授 课 班 级： 计科 2008 级授 课 时 间： 2010-2011 二课题一课题一 有限自动机的运行一、设计题目：一、设计题目：有限自动机的运行 二、设计目的：二、设计目的：1、理解有限自动机的作用 2、利用转态图和状态表表示有限自动机 3、以程序实现有限自动机的运行过程 三、设计内容：（注：题目详细要求）三、设计内容：（注：题目详细要求） 利用状态表和有限自动机的运行原理编制程序，使得程序能够识别一个输入串是否为一个有效的符号串，具体可以选择下面之一：无符号定点实数、自然数、整数
2、、十六进制数或其它自己定义的符号串。 四、设计思想：（注：算法思想、程序流程图、不要写代码）四、设计思想：（注：算法思想、程序流程图、不要写代码） 本程序实现对无符号定点实数的判断，正确接受，否则不接受。 本程序的关键在状态表和缓冲区的运用。首先定义了一个布尔型函数 ReadALine 把输入的字符串送到缓冲区中；然后定义了布尔型函数 Run 和 Getchar 实现对输入字符串的正确性判断，更改 Run 函数可以改变程序功能：如可将状态表改变成识别“偶数”的有限自动机的状态表。 程序流程图如下：（学生自己画） 五、运行结果与数据分析：五、运行结果与数据分析：六、设计总结体会：六、设计总结体会
3、： （学生自己写，此处可参考）（学生自己写，此处可参考）通过这次课程设计，我对程序的编译和运行过程有了更进一步的了解，对程序的底层设计、代码优化也有了初步的认识，而且知道了如何从根本上来提高程序运行的速度。 附录：（完整代码）附录：（完整代码） #include #include /状态表相关存储信息：#define STATE_NUMBER 4 /状态数目#define CHAR_NUMBER 2 /输入字符的种类: d 和 .#define DIGIT 0 /输入数字在状态表中位于第 0 列/State为状态表，以整数组形式存放，0,1,2,3 表示状态，-1 表示没有此状态int Sta
4、teSTATE_NUMBERCHAR_NUMBER= 1,-1,1,2, 3,-1, 3,-1;int QSTATE_NUMBER = 0,1,0,1; /终态标志：0 非终态，1 终态。/缓冲区：/输入缓冲区：由专门函数操作（ReadALine(),GetChar()）#define BUFFER_SIZE 1000 /表达式缓冲区大小char BufferBUFFER_SIZE; /表达式缓冲区，以0表示结束int ipBuffer = 0; /表达式缓冲区当前位置序号char ch; /存放取得的一个字符/函数声明：bool Run(); /对存储在缓冲区的一行字符串（以#结束）进行运行
5、void Init(); /全局初始化bool ReadALine(); /从键盘读一行（没有空格），存于表达式缓冲区 Buffer中char GetChar(); /从缓冲区取一个字符，返回该字符的同时将它存于全局变量 ch 中/主程序：void main() Init();while(ReadALine() /读一行成功，对它进行判断 if(Run() /对该行进行运行，看是否能被接受？printf(“接受nn“);else printf(“不接受nn“);/对存储在缓冲区的一行字符串（以#结束）进行运行/返回：如果是无符号定点实数，返回 true；否则返回：falsebool Run()
6、 int S=0; /S 存放运行时的当前状态，目前为初态while(GetChar()!=#) if(ch = 0if x=0then sum1 := sum1 + x;sum2 := sum2 + x;k := k-1;end;write (sum1, times*sum2/ num);end.四、设计思想：（注：算法思想、程序流程图、不要写代码）四、设计思想：（注：算法思想、程序流程图、不要写代码）利用单词的构成规则，对输入的字符串进行分析再归类即可。（流程图学生自己画）五、运行结果与数据分析：五、运行结果与数据分析：六、设计总结体会：六、设计总结体会： 课题三：课题三：语法分析器的设计
7、语法分析器的设计一、设计题目一、设计题目：语法分析器的设计二、设计目的要求二、设计目的要求：通过设计、编程、调试出一个具体语法分析程序，能调用词法分析程序为其提供单词符号串，进行语法分析，掌握语法分析方法和程序设计方法。三、设计内容：三、设计内容：任选任选一种语法分析方法进行程序设计，语法分析程序能通过实例数据的测试。写出设计报告，内容为：所选的语法分析方法、算法、改写的文法、符号表、出错处理、编程方法等。SPL 语言的文法:= := program ;* := * := ab y z* := * := 0* := 1 8 9:= var :int;const ;var :int;const
8、;:= ,:= = = ,* := * := := begin end.:= ; := := := := + - := * / := ():= if then * := =:= while do := read ():= write ():= ,:= begin end【备注】1. SPL 语言源程序格式自由；2. SPL 语言源程序中可以插入注解，用“” 、 “”括起来。测试用例同课题二四、设计思想：（注：算法思想、程序流程图、不要写代码）四、设计思想：（注：算法思想、程序流程图、不要写代码）根据自己选择语法分析方法（LL（1）、LR（0）、OPG），先设计分析表再设计主控程序。（LLLL（
9、1 1） ）主要算法）主要算法: :构造算符优先分析表的算法以下几个步骤：（1）构造文法 G 中非终结符号的 FIRSTVT 集合FIRSTVT 集合用一个整型二维数组 Fqf表示，其值为 0 或 1。F 是一个 q*f 的二维数组（q=文法 G 中非终结符号个数，f=文法 G 中终结符号个数） 。对于文法 G 的所有终结符，构造数组Fqf的算法（该算法使用一个 STACK 栈，用于存放含有一个非终结符和一个终结符对的结构体 X。 ）如下：BEGINfor 任何非终结符 P 和终结符 a 对（P，a）确定 P 在非终结符数组 VN中的位置 q1 和 a 在终结符数组 VT中的位置 f1Fq1f
10、1=0；for 任何形如 P-a或 P-Qa的产生式BEGINIF NOT Fq1f1 Fq1f1 =0；将（P，a）放入结构体 x；X 进 STACK 栈；ENDWHILE STACK 栈非空 BEGIN将 STACK 栈的栈顶元素出栈FOR 每个形如 Q-P的产生式 BEGIN确定 Q 在非终结符数组 VN中的位置 q2IF NOT Fq2f1 BEGIN Fq2f1=1；将（Q，a）放入结构体 X；X 进 STACK 栈；ENDENDEND.（2）构造文法 G 中非终结符号的 LASTVT 集合类似于构造 FIRSTVT 集合，LASTVT 集合用一个整型数组 LP，a表示，其值为 0
11、或 1。L是一个 q*f 的二维数组（q=文法 G 中非终结符号个数，f=文法 G 中终结符号个数） 。对于文法 G的所有终结符，构造数组 Lqf的算法（该算法法使用一个 STACK 栈，用于存放含有一个非终结符和一个终结符对的结构体 D。 ）如下：BEGINfor 任何非终结符 P 和终结符 a 对（P，a）确定 P 在非终结符数组 VN中的位置 q1 和 a 在终结符数组 VT中的位置 f1Lq1f1=0；for 任何形如 P-a 或 P-Qa 的产生式BEGINIF NOT Lq1f1 Lq1f1 =0；将（P，a）放入结构体 d；D 进 STACK 栈；ENDWHILE STACK 栈
12、非空 BEGIN将 STACK 栈的栈顶元素出栈FOR 每个形如 Q-P 的产生式 BEGIN确定 Q 在非终结符数组 VN中的位置 q2IF NOT Lq2f1 BEGIN Lq2f1=1；将（Q，a）放入结构体 D；D 进 STACK 栈；ENDENDEND.（3）构造文法 G 的优先关系表使用文法 G 中任何非终结符号的 FIRSTVT 集合和 LASTVT 集合，可以构造文法 G 的优先关系表。优先关系表用一个二维字符数组 Z表示，Z 是一个 f*f 的数组（f=文法 G 中终结符号个数） 。Z 表的值为0 、 、 或= 。构造优先关系表 Z的算法如下： FOR 每个形如产生式 P-Q
13、a或 P-Qa 在 lastvt 集的数组 L中确定 Q 对应的行元素值为 1 的下标 j 和 a 对应的列的下标l；在算符优先表的数组 Z中,将 Zjl的值置 ；FOR 每个形如产生式 P-aQ或 P-aQ 在 firstvt 集的数组 F中确定 Q 对应的行元素值为 1 的下标 j 和 a 对应的列的下标l；在算符优先表的数组 Z中,将 Zjl的值置；FOR 每个形如产生式 P-ab或 P-aQb在终结符号集合的数组中找到 a，b 所对应的下标 j，k；在算符优先表的数组 Z中,将 Zjl的值置=；（4）判别文法 G 是否为算符优先文法2.设计算符优先分析程序的算法（1）判别输入串是否为文
14、法 G 的句子根据查找最左子素短语的方法，得到算符优先分析算法如下：在算法中使用了一个符号栈B，用来存放终结符和非终结符，k 代表符号栈 S 的使用深度： WHILE 文法 G 为算符优先文法 DO 将字符串放入数组 string中；K=0,初始化栈 Bk=# ；把当前字符读入字符变量 a 中；IF Sk为终结符 J=kELSE J=K-1找出 Bk所对应的终结符及 a 所对应的终结符在 Z中的位置 q,q3 IF Zqq3= =或.a 的项目，E=ch，且原闭包集中不含此项目，执行(3),(4),否则返回。3将该产生式加入该闭包。4递归调用闭包算法对新加入产生式进行闭包运算。求解 Go 集合
15、算法ch 赋值为吸收字符遍历该项目集的所有项目，对行如 E-a.bB 的项目，b=ch,创建新项目集并将该项目加入新项目集。如若该新项目集已存在，撤消，否则返回新项目集下标。求项目集算法对零项目求解求解闭包,得出项目集.0I对项目集求解 Go 集,得出新产生项目集的最大下标 i;0I从项目集到项目集依次编历各项目集,求解该项目集闭包和该项目集 Go 集,1IiI在此步中 i 值可能发生变化.构表算法对项目集的每个项目圆点后的字符iI如果为空，判断是否为结束产生式，则将相应数组元素赋值 abc否则为规约项目，赋相应ir如果为大写字母，则为移进项目,通过判断 Go()求得 I,赋相应 I;否则，通过判断 Go()求得 I,赋相应。is（OPGOPG）
