编译原理课程设计教案.doc

黄冈师范学院编译原理课程设计教案（2011春）授 课 教 师： 张 瑞 红 授 课 班 级： 计科2008级授 课 时 间： 2010-2011 二课题一 有限自动机的运行一、设计题目：有限自动机的运行 二、设计目的：1、理解有限自动机的作用 2、利用转态图和状态表表示有限自动机 3、以程序实现有限自动机的运行过程 三、设计内容：（注：题目详细要求） 利用状态表和有限自动机的运行原理编制程序，使得程序能够识别一个输入串是否为一个有效的符号串，具体可以选择下面之一：无符号定点实数、自然数、整数、十六进制数或其它自己定义的符号串。 四、设计思想：（注：算法思想、程序流程图、不要写代码） 本程序实现对无符号定点实数的判断，正确接受，否则不接受。 本程序的关键在状态表和缓冲区的运用。首先定义了一个布尔型函数ReadALine把输入的字符串送到缓冲区中；然后定义了布尔型函数Run和Getchar实现对输入字符串的正确性判断，更改Run函数可以改变程序功能：如可将状态表改变成识别“偶数”的有限自动机的状态表。 程序流程图如下：（学生自己画） 五、运行结果与数据分析：六、设计总结体会： （学生自己写，此处可参考）通过这次课程设计，我对程序的编译和运行过程有了更进一步的了解，对程序的底层设计、代码优化也有了初步的认识，而且知道了如何从根本上来提高程序运行的速度。 附录：（完整代码） #include#include/状态表相关存储信息：#defineSTATE_NUMBER4/状态数目#defineCHAR_NUMBER2/输入字符的种类:d和.#defineDIGIT0/输入数字在状态表中位于第0列/State为状态表，以整数组形式存放，0,1,2,3表示状态，-1表示没有此状态intStateSTATE_NUMBERCHAR_NUMBER=1,-1,1,2,3,-1,3,-1;intQSTATE_NUMBER=0,1,0,1;/终态标志：0非终态，1终态。/缓冲区：/输入缓冲区：由专门函数操作（ReadALine(),GetChar()）#defineBUFFER_SIZE1000/表达式缓冲区大小charBufferBUFFER_SIZE;/表达式缓冲区，以0表示结束intipBuffer=0;/表达式缓冲区当前位置序号charch;/存放取得的一个字符/函数声明：boolRun();/对存储在缓冲区的一行字符串（以#结束）进行运行voidInit();/全局初始化boolReadALine();/从键盘读一行（没有空格），存于表达式缓冲区Buffer中charGetChar();/从缓冲区取一个字符，返回该字符的同时将它存于全局变量ch中/主程序：voidmain()Init();while(ReadALine()/读一行成功，对它进行判断if(Run() /对该行进行运行，看是否能被接受？printf(接受nn);elseprintf(不接受nn);/对存储在缓冲区的一行字符串（以#结束）进行运行/返回：如果是无符号定点实数，返回true；否则返回：falseboolRun()intS=0;/S存放运行时的当前状态，目前为初态while(GetChar()!=#)if(ch=0&ch=1 dobeginread (x);if x=0then sum1 := sum1 + x;sum2 := sum2 + x;k := k-1;end;write (sum1, times*sum2/ num);end.四、设计思想：（注：算法思想、程序流程图、不要写代码） 利用单词的构成规则，对输入的字符串进行分析再归类即可。（流程图学生自己画）五、运行结果与数据分析：六、设计总结体会： 课题三：语法分析器的设计一、设计题目：语法分析器的设计二、设计目的要求：通过设计、编程、调试出一个具体语法分析程序，能调用词法分析程序为其提供单词符号串，进行语法分析，掌握语法分析方法和程序设计方法。三、设计内容：任选一种语法分析方法进行程序设计，语法分析程序能通过实例数据的测试。写出设计报告，内容为：所选的语法分析方法、算法、改写的文法、符号表、出错处理、编程方法等。SPL语言的文法 := := program ;* := * := ab y z* := * := 0* := 1 8 9 := var :int;const ;var :int;const ; := , := = = ,* := * := := 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集合用一个整型二维数组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栈； 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 在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),否则返回。3 将该产生式加入该闭包。4 递归调用闭包算法对新加入产生式进行闭包运算。求解Go集合算法 ch赋值为吸收字符 遍历该项目集的所有项目，对行如E-a.bB的项目，b=ch,创建新项目集并将该项目加入新项目集。 如若该新项目集已存在，撤消，否则返回新项目集下标。求项目集算法 对零项目求解求解闭包,得出项目集. 对项目集求解Go集,得出新产生项目集的最大下标i;从项目集到项目集依次编历各项目集,求解该项目集闭包和该项目集Go集,在此步中i值可能发生变化.构表算法对项目集的每个项目圆点后的字符如果为空，判断是否为结束产生式，则将相应数组元素赋值abc否则为规约项目，赋相应如果为大写字母，则为移进项目,通过判断Go()求得I,赋相应I;否则，通过判断Go()求得I,赋相应。（OPG）主要算法和数据结构:算符优先分析法是一种简单且直观的自下而上分析方法，特别适合于分析程序语言中的各类表达式，并且宜于手工实现。 算术优先分析，是依照算术表达式的四则运算过程来进行语法分析。通常在算术表达式求值过程中，运算次序是先乘除后加减，这说明了乘除运算的优先级高于加减运算的优先级，乘除为同一优先级但运算符在前边的先做，这称为左结合，同样加减运算也是如此，这也说明了运算的次序只与运算符有关，而与运算对象无关，因而直观算符优先分析法的关键是对一个给定文法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为字符型,表示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 () ( | ) := (|） (|) := (|) := | | = := （) := =( | ) ( | ) := + | - | * | / := = | 2、递归文法：S - while (B) S | i=EB - E relop Erelop - E - (E)F | iF | nFF - +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不是数字是，就返回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) Sre=Getsymbol(); /取下一个字符的机内码If(re=左括号)调用B()；re=Getsymbol(); /取下一个字符的机内码if(re=右括号)调用S();Else if(re=变量) /执行S-i = E re=Getsymbol(); /取下一个