名师精编精品教案黄冈师范学院编译原理课程设计教案（2011春）授 课 教 师： 张瑞红授 课 班 级： 计科 20XX级授 课 时 间： 2010-2011 二精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 15 页名师精编精品教案课题一有限自动机的运行一、设计题目：有限自动机的运行二、设计目的：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 StateSTATE_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表示结束精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 15 页名师精编精品教案int ipBuffer = 0; / 表达式缓冲区当前位置序号char ch; / 存放取得的一个字符/ 函数声明：bool Run(); / 对存储在缓冲区的一行字符串（以# 结束）进行运行void Init(); / 全局初始化bool ReadALine(); / 从键盘读一行（没有空格），存于表达式缓冲区Buffer中char GetChar(); / 从缓冲区取一个字符，返回该字符的同时将它存于全局变量ch 中/ 主程序：void main() Init(); while(ReadALine() / 读一行成功，对它进行判断 if(Run() /对该行进行运行，看是否能被接受？printf(接受 nn); else printf(不接受 nn); / 对存储在缓冲区的一行字符串（以# 结束）进行运行/ 返回：如果是无符号定点实数，返回true ；否则返回：false bool Run() int S=0; /S 存放运行时的当前状态，目前为初态while(GetChar()!=#) if(ch = 0&ch=1 do begin read (x); if x=0 then sum1 := sum1 + x; sum2 := sum2 + x; k := k-1; end; write (sum1, times*sum2/ num); end. 四、设计思想：（注：算法思想、程序流程图、不要写代码）利用单词的构成规则，对输入的字符串进行分析再归类即可。（流程图学生自己画）五、运行结果与数据分析：六、设计总结体会：精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 15 页名师精编精品教案课题三：语法分析器的设计一、设计题目：语法分析器的设计二、设计目的要求：通过设计、 编程、 调试出一个具体语法分析程序，能调用词法分析程序为其提供单词符号串，进行语法分析，掌握语法分析方法和程序设计方法。三、设计内容：任选 一种语法分析方法进行程序设计，语法分析程序能通过实例数据的测试。写出设计报告，内容为：所选的语法分析方法、算法、改写的文法、符号表、出错处理、编程方法等。SPL语言的文法 := := program ; * := * := ab y z * := * := 0 * := 1 8 9 := var :int;const ; var :int;const ; := , := = = , * := * := := begin end. := ; := := := := + - := * / := () := if then * := = := while do := read () := write () := , 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页，共 15 页名师精编精品教案 := begin end 【备注】 1. SPL 语言源程序格式自由；2. SPL 语言源程序中可以插入注解，用“”、“ ”括起来。测试用例同课题二四、设计思想：（注：算法思想、程序流程图、不要写代码）根据自己选择语法分析方法（LL（1）、 LR（0）、 OPG ），先设计分析表再设计主控程序。（LL（1） ）主要算法 :构造算符优先分析表的算法以下几个步骤：（1）构造文法G中非终结符号的FIRSTVT集合 FIRSTVT 集合用一个整型二维数组Fqf表示，其值为0 或 1。F是一个 q*f 的二维数组（q=文法 G中非终结符号个数， f= 文法 G中终结符号个数） 。 对于文法 G的所有终结符， 构造数组 Fqf的算法（该算法使用一个STACK 栈，用于存放含有一个非终结符和一个终结符对的结构体X。 ）如下： BEGIN for 任何非终结符P和终结符a 对（ P，a）确定 P在非终结符数组VN 中的位置 q1 和 a 在终结符数组VT 中的位置f1 Fq1f1=0；for 任何形如P-a或 P-Qa 的产生式 BEGIN IF NOT Fq1f1 Fq1f1 =0；将（ P，a）放入结构体x； X进 STACK 栈； END WHILE STACK 栈非空 BEGIN 将 STACK 栈的栈顶元素出栈 FOR 每个形如Q-P的产生式 BEGIN 确定 Q在非终结符数组VN 中的位置q2 IF NOT Fq2f1 BEGIN Fq2f1=1；将（ Q，a）放入结构体X； X进 STACK 栈；精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页，共 15 页名师精编精品教案 END END END. （2）构造文法G中非终结符号的LASTVT集合类似于构造FIRSTVT 集合， LASTVT集合用一个整型数组LP ，a 表示，其值为0 或 1。L是一个q*f的二维数组（ q=文法 G 中非终结符号个数，f= 文法 G 中终结符号个数） 。对于文法G的所有终结符，构造数组Lqf的算法（该算法法使用一个STACK栈，用于存放含有一个非终结符和一个终结符对的结构体D 。 ）如下：BEGIN for 任何非终结符P和终结符a 对（ P， a）确定 P在非终结符数组VN 中的位置q1 和 a 在终结符数组VT 中的位置f1 Lq1f1=0； for任何形如P- a 或 P- Qa的产生式 BEGIN IF NOT Lq1f1 Lq1f1 =0；将（ P，a）放入结构体d； D进 STACK 栈； END WHILE STACK 栈非空 BEGIN 将 STACK 栈的栈顶元素出栈 FOR 每个形如Q- P的产生式 BEGIN 确定 Q在非终结符数组VN 中的位置q2 IF NOT Lq2f1 BEGIN Lq2f1=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 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 8 页，共 15 页名师精编精品教案 在 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）判别输入串是否为文法G的句子根据查找最左子素短语的方法，得到算符优先分析算法如下：在算法中使用了一个符号栈B，用来存放终结符和非终结符，k 代表符号栈S的使用深度： WHILE 文法 G为算符优先文法 DO 将字符串放入数组string中； K=0,初始化栈Bk= #；把当前字符读入字符变量a 中； IF Sk为终结符 J=k ELSE J=K-1 找出 Bk 所对应的终结符及a 所对应的终结符在Z中的位置q,q3 IF Zqq3= =或 .a 的项目， E=ch ，且原闭包集中不含此项目，执行(3),(4),否则返回。将该产生式加入该闭包。递归调用闭包算法对新加入产生式进行闭包运算。求解 Go集合算法ch 赋值为吸收字符遍历该项目集的所有项目，对行如E-a.bB 的项目， b=ch, 创建新项目集并将该项目加入新项目集。如若该新项目集已存在，撤消，否则返回新项目集下标。求项目集算法对零项目求解求解闭包,得出项目集0I. 对项目集0I求解 Go集, 得出新产生项目集的最大下标i; 从项目集1I到项目集iI依次编历各项目集, 求解该项目集闭包和该项目集Go集, 在此步中i 值可能发生变化. 构表算法对项目集iI的每个项目圆点后的字符如果为空，判断是否为结束产生式，则将相应数组元素赋值abc 否则为规约项目，赋相应ir如果为大写字母，则为移进项目, 通过判断 Go() 求得 I, 赋相应 I; 否则，通过判断Go() 求得 I, 赋相应is。（OPG ）主要算法和数据结构:算符优先分析法是一种简单且直观的自下而上分析方法，特别适合于分析程序语言中的各类表达式，并且宜于手工实现。算术优先分析，是依照算术表达式的四则运算过程来进行语法分析。通常在算术表达式求值过程中，运算次序是先乘除后加减，这说明了乘除运算的优先级高于加减运算的优先级，乘除为同一优先级但运算符在前边的先做，这称为左结合，同样加减运算也是如此，这也说明了精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 10 页，共 15 页名师精编精品教案运算的次序只与运算符有关，而与运算对象无关，因而直观算符优先分析法的关键是对一个给定文法 G ，人为地规定其算符的优先顺序，即给出优先级别和同一个级别中的结合性质，算符间的优先关系表示规定如下：ab 表示 a 的优先性低于b。ab 表示 a 的优先性等于b，即与 b 相同。ab 表示 a 的优先性高于b。但必须注意，这三个关系和数学中的，是不同的。当有关系 ab 时，却不一定有关系ba，当有关系ab 时，却不一定有ba，例 如：通常表达式中运算符的优先关系有 +- ，但没有 -+，有 ()，但没有 )(。即这种分析方法要预先规定运算符（确切地说是终结符）之间的优先关系和性质，然后借助于这种关系来比较相邻运算符的优先级，以确定句型的“可归约串”来进行归约。定义：设有一文法G ，如果 G中没有形如ABC 的产生式，其中B和 C为非终结符，则称 G为算符文法例如：表达式文法EE+E|E*E|(E)|i其中任何一个产生式中都不包含两个非终结符相邻的情况，因此该文法是算符文法1） 文法2） 算法： FIRSTVT ；LASTVT ；优先关系表；判断G是否是算符优先文法3） 构造算符优先表程序设计：G的产生式存储和输入，可以定义、 ；所涉及的主要数据结构（ FITSTVT和 LASTVT集合；优先关系表；STACK 栈主要数据结构1 算符文法G的产生式存储和输入定义一个二维数组p1010存储 G的产生式，h 为产生式的个数，其元素为字符数组，每行字符存放的字符串最长为10，每一行存放一个产生式，算符文法G的产生式可以通过键盘，以字符方式输入，每个产生式以“#”结束。2 所涉及的主要数据结构firstvt集合和 lastvt集合；用整形数组fp ，a 和 lp ，b 表示，都是 a*b 的二维数组， （a 为文法中非终结符的个数，b 为文法中终结符的个数），其中 p 属于 N,a 属于 T, 输出的第一行 T 表示所有终结符, 第一列 N表示所有的非终结符. 优先关系表用一个数组ka,b表示 ,k 是一个 b*b 的二维数组 (b 为文法的终结符的个数),其元素为二维字符数组, 每个字符数组所存的字符串的长度为1, 其中 a,b 属于终结符,ra,b=, ,或为空 ,数组 ra,b类型为字符型. 输出时 , 第一行 T表示所有的终结符 , 第二行 T 表示所有的终结符. 一维数组Tn 存放所有的终结符, 一维数组Na 存放所有的非终结符, 变量 a,b 分别表示非终结符 , 终结符 . 一维数组An 表示每个产生式的第一个字符在非终结符Nn 中的位置,Bn表示没一个产生式的个数,fp,a为字符型 , 表示 a是否是 p 的 firstvt,lp,a为字符型 ,精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 11 页，共 15 页名师精编精品教案表示 a 是否为 p 的 lastvt,ka,a表示终结符存在那种关系; =, , 或空 , 如果存在两种对应关系 , 则说明该文法不是算符优先文法。五、运行结果与数据分析：六、设计总结体会：课题四： WHILE循环语句的翻译程序设计一、设计题目：WHILE循环语句的翻译程序设计二、设计目的要求：通过设计、 编程、 调试出一个具体语法分析程序，能调用词法分析程序为其提供单词符号串，进行语法分析，掌握语法分析方法和程序设计方法。三、设计内容：1、写出符合题目要求的文法及属性文法。2、完成题目要求的中间代码三地址表示的描述。3、写出递归下降法的思想，完成语法分析和语义分析程序设计。4、编制好分析程序后，设计若干用例，上机测试并通过所设计的分析程序。5、设计报告格式按要求书写。课程设计报告书正文的内容应包括：1 系统描述（问题域描述）；2 文法及属性文法的描述；3 语法分析方法描述及语法分析表设计；4 给出中间代码形式的描述及中间代码序列的结构设计；5 简要的分析与概要设计；6 详细的算法描述（流程图或伪代码）；7 给出软件的测试方法和测试结果；8 研制报告（研制过程，本设计的评价、特点、不足、收获与体会等）；四、设计思想：（注：算法思想、程序流程图、不要写代码）按照课程设计的要求，写一个能识别while循环语句的文法，通过一定的变换使它符合递归下降法的要求，然后按照这个文法编写一个程序，该程序能识别输入的语句是否符合while 语句的文法，或者能不能通过文法的开始符号推导出该语句。该程序应该包括词法分析器，能对输入的语句进行词法分析，然后再对结果进行语法分析。词法分析器应能识别关键字，标示符，常量，操作符等。该程序的语法分析器能对输入的语法进行分析，判断输入语句能否满足while循环语句的文法。通过递归下降的方法对语句进行分析，看能否通过开始符号推导出来。该程序的语义分析器就是对分析结果进行输出，要求输出结果是三地址形式的。1、文法描述 := while () ( | ) 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 12 页，共 15 页名师精编精品教案 := (|） (|) := (|) := | | = := （) := =( | ) ( | ) := + | - | * | / := = | 2、递归文法：S - while (B) S | i=E B - E relop E relop - E - (E)F | iF | nF F - +EF | -EF | *EF | /EF | 3、语法分析方法描述：按照递归下降分析技术，递归下降识别程序是由一组子程序组成，每个子程序对应于一个非终结符号。该子程序处理相应句型中相对于此非终结符号的产生式。在定义文法时，是递归定义的，所以这些子程序也是递归的。当一个子程序调用另一个子程序时，总是先执行被调用的子程序，然后再执行后继的程序。4、三地址代码在本程序中用到了三地址语句的输出包括以下的种类：赋值语句： x:= y op z 复制语句： x:= y 条件转移语句：if x relop y goto L 例如：本程序中语句while (B) S ,可以输出三地址代码为：if B goto L else goto Lnext；而 E - (E)F可以输出三地址代码为：E1:= (E2) F。5、Getsymbol()子程序的算法描述Int Getsymbol() sym=fgetc(intput); /取当前文件指针指向的字符While(sym 不为空 ) if(sym是 a-z 的字符 ) 将该字符保存在token1 数组中；继续取下一个是a-z 的字符保存在数组中；当sym不是字符时，则判断该数组中的符号串是不是关键字，是就返回16（while 的机内码）；不是就返回13（变量的机内码） ； Else if（sym是 0-9 之间的数字）将该数字保存在token2 数组中；继续取下一为0-9 的数字，并保存到数组中去；当sym 不精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 13 页，共 15 页名师精编精品教案是数字是，就返回12（常数的机内码） ； Else if（sym是+）返回 4；Else if（sym是- ）返回 3；Else if（sym是* ）返回 2；Else if（sym是/ ）返回 1；Else if（sym是 ）返回 9；Else if（sym是； ）返回 20； 该程序就是对输入串进行分析，分析到不同的数据类型就相应返回它的机内码，这样方便在语法分析中进行分析。本程序还保存了变量和常量在结构数组中，方便在语义分析的时候使用。 S() 子程序的算法描述void S() re=Getsymbol(); /取下一个字符的机内码if(re=关键字 ) /执行 S-while (B) S re=Getsymbol(); /取下一个字符的机内码If(re=左括号 ) 调用 B() ；re=Getsymbol(); /取下一个字符的机内码if(re=右括号 ) 调用 S(); Else if(re=变量 ) /执行 S-i = E re=Getsymbol(); /取下一个字符的机内码If(re=等号 ) 调用 E() ； Else ERROR()； 该程序就是对通过Getsymbol() 词法分析程序得到的单词，进行不同的程序语句执行。当得到了while 是就分析下一个是不是(，是的话就调用B() ；否则就出错。 取下一个单词， 是) 就调用 S() ；否则也出错。当得到的是变量i 时，去下一个单词，如果是=就调用 E() 。 B() 和 relop()子程序的算法描述在B() 子程序中，不用判断任何的单词，就依次调用E() ，relop()，E() ，执行 B-E relop E Void relop() 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 14 页，共 15 页名师精编精品教案 re=Getsymbol(); /取下一个字符的机内码 If(sym=大于号 ) ； /执行 relop-= Else if(syn=小于号 ) ； /执行 relop- Else ERROR()； 在 relop程序中就主要上判断当前取得的单词是不是条件运算符。 E() 子程序的算法描述Void E() re=Getsymbol(); /取下一个字符的机内码if(re=左括号 ) /执行 E-(E)F E()；re=Getsymbol(); /取下一个字符的机内码if(re=右括号 ) F() ； Else if(re=变量 ) /执行 E-iF F()；Else if(re=常量 ) /执行 E-nF F()； F() 子程序算法描述Void F() re=Getsymbol(); /取下一个字符的机内码 If(re=加号 ) /执行 F-+EF E(); F(); Else if(re=减号 ) /执行 F-EF E(); F(); Else if(re=乘号 ) /执行 F-*EF E(); F(); Else if(re=除号 ) /执行 F-/EF E(); F(); 这个子程序和E() 合起来就是一个完整的可递归的算术操作运算，但由于递归下降分析方法不能含有左递归文法，所以消去左递归后就成了两个子程序。五、运行结果与数据分析：六、设计总结体会：精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 15 页，共 15 页