编译原理课程设计——算符优先分析法研究——附源程序

目    录 1  课程 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 的目的和要求    2 1.1  课程设计的目的    2 1.2  课程设计的要求    2 2  系统描述    2 2.1  自底向上分析方法的描述:    2 2.2  算符优先文法的描述：    2 3）输入符号串，进行移进-规约分析。    3 3  概要设计    3 3.1  设计思路    3 3.2  系统功能结构    4 3.3  技术路线或实现方法    5 3.4  开发环境    5 4  详细设计    5 4.1  模块划分    5 4.2    主要算法的流程图    7 4.3  数据分析与定义    8 4.4  系统界面设计    8 5  测试方法和测试结果    9 5.1  测试用例1    9 5.2  测试用例2    10 5.3    测试用例3    11 5.4  测试用例4    12 6  结论和展望    13 结论    13 展望    13 学习编译技术课程的体会和对本门课程的评价    13 7  参考文献    13 8  源代码    14 1  课程设计的目的和要求 1.1  课程设计的目的 本次设计的时间为1周，目的是通过使用高级语言实现部分算法加强对编译技术和理论的理解。设计的题目要求具有一定的规模，应涵盖本课程 内容 财务内部控制制度的内容财务内部控制制度的内容人员招聘与配置的内容项目成本控制的内容消防安全演练内容 和实际应用相关的主要技术。 1.2  课程设计的要求 1、文法使用产生式来定义； 2、用大写字母和小写字母分别表示非终结符和终结符；产生式使用->； 3、文法中的空字符串统一使用@表示； 4、分别给出每一个非终结符的FIRSTVT集和LASTVT集； 5、画出算符优先关系表 6、判定给定的文法是否是算符优先文法； 7、给定符号串判定是否是文法中的句子，分析过程用分析表格的方式打印出来。 2  系统描述 本次实验使用windows vista操作系统下visual C++6.0平台，使用C语言，利用读文件方式将待分析的文法读入到程序中，通过定义数组和结构体作为具有一定意义或关系的表或栈，存放FIRSTVT、LASTVT、算符优先关系表的元素。 系统能够对由文件读入的文法进行分析，构造出FIRSTVT表和LASTVT表以及算符优先关系表。可以根据构造的优先关系表对输入的任意符号串进行分析，判断是否为本文法的句子，若是则打印规约过程。结果显示到DOS界面上。 2.1  自底向上分析方法的描述: 对输入的符号串自左向右进行扫描，并将输入符逐个移入栈中，边移入边分析，一旦栈顶符号串形成某个句型的句柄时（该句柄对应某个产生式的右部），就用该产生式的左部非终结符代替相应右部的文法符号串，这一过程称为规约。重复这一过程，直到栈中只剩下文法的开始符则分析成功。 2.2  算符优先文法的描述： 只规定算符之间的优先关系，也就是说只考虑终结符之间的优先关系。由于算富有先分析不考虑非终结符之间的优先关系，在规约过程中只要找到最左素短语就可以规约。 如给定一个文法G[S]： S->#E# E->E+T E->T T->T*F T->F F->P/F F->P P->(E) P->i 利用算符优先文法分析过程处理如下： 1）计算给定文法中任意两个终结符对(a,b)之间的优先关系，首先计算两个集合 FIRSTVT(B)={b|B->b…或B->Cb…} LASTVT(B)={a|B->…a或B->…aC} 表2-1    FIRSTVT集和LASTVT集 S E　 T　 F　 P　 FIRSTVT # +*/i(　 */i(　 /i(　 i(　 LASTVT # +*/i)　 */i)　 /i)　 i)　             2）计算三种优先关系，求出算符优先关系表： 表2-2算符优先关系表   + * / i ( ) # + ﹒﹥ ﹤﹒ ﹤﹒ ﹤﹒ ﹤﹒ ﹒﹥ ﹒﹥ * ﹒﹥ ﹒﹥ ﹤﹒ ﹤﹒ ﹤﹒ ﹒﹥ ﹒﹥ / ﹒﹥ ﹒﹥ ﹤﹒ ﹤﹒ ﹤﹒ ﹒﹥ ﹒﹥ I ﹒﹥ ﹒﹥ ﹒﹥     ﹒﹥ ﹒﹥ ( ﹤﹒ ﹤﹒ ﹤﹒ ﹤﹒ ﹤﹒ ﹦﹒   ) ﹒﹥ ﹒﹥ ﹒﹥     ﹒﹥ ﹒﹥ # ﹤﹒ ﹤﹒ ﹤﹒ ﹤﹒ ﹤﹒   ﹦﹒                 3）输入符号串，进行移进-规约分析。 3  概要设计 3.1  设计思路 1）首先在源程序相同的目录下创建一个txt文档，并在文档中输入待分析的文法。然后定义一个输入流文件，调用这个流文件中的open函数打开该txt文件，再定义一个二维数组通过循环接收读入的产生式。 2）接着开始构造FIRSTVT、LASTVT、算符优先关系表。在构造表的时候首先定义了两个重要的结构体。一个结构体作为存放具有一定关系的一对非终结符和终结符，另一个结构体作为存放上述元素的栈，包括栈顶指针、栈底指针、栈的长度。既然定义了栈，就存在对栈的初始化、栈是否为空的判断、入栈、出栈操作，利用循环和指针的操作来定义这些函数，以完成元素的进栈和弹出。 定义了这两个结构体，就可以用来构造FIRSTVT、LASTVT、算符优先关系表。在构造FIRSTVT表时，通过循环找出每条产生式中的非终结符的FIRSTVT集，并把该非终结符和终结符压栈，设置标志位，标志一对非终结符和终结符具有对应关系。LASTVT表的构造则是将求FIRSTVT的过程翻转过来，可以仅仅将函数中的参数稍作修改就能够完成。 3）构造算符优先关系表。算符优先关系表是一个二维数组，用来存放任意两个终结符之间的优先关系。首先构造表头，通过扫描所有产生式将终结符不重复的存放在一个一维数组中并置为优先关系表的行和列，并将优先关系表其他内容全部初始化为空。接着遍历所有产生式，找出任意两个终结符之间存在的关系（可以没有关系），并判断任意两终结符是否至多存在一种优先关系，如发现优先关系表不为空，则证明该文法不是算符优先文法，否则，将相应的关系填入到相应的行列对应的单元中。 4）输入串分析过程的设计。首先将大于、小于、等于和无关系分别定义成一种类型的数据表示，通过查询符号栈栈顶以及当前符号之间的优先关系来判断移进和规约的操作。 3.2  系统功能结构 图3-1  系统功能结构图 函数功能： Main()函数：调用主函数，运行程序； FirstVt()函数：构造FIRSTVT表； LastVt()函数：构造LASTVT表； OpPrioTable()函数：构造算符优先关系表； InputAnalyse()函数：分析输入串是否为文法中的句子，并给出规约过程。 3.3  技术路线或实现方法 算符优先分析法的具体过程如下： 1、首先先输入文件的路径，在readfile(char sen[][col])函数中，将需要分析的文法通过输入流文件打开函数open()复制到sen[row][col]中。 2、然后利用FirstVt( )构造产生式sen[row][col]的FirstVt表。先找出形如A->…a…（a为第一个终结符）的产生式，把（A,a）压入Operator栈中。从Operator栈顶抛出项（A，a），填入first表相应位置。在找出形如B->A…的产生式，把（B,a）压入Operator栈中。循环直到Operator栈为空，此时FirstVt表构造完毕。 3、然后把产生式右部翻转，调用FirstVt函数求出LastVt表。 4、接着调用OpPriotable（）构造算符优先关系表opTable。先把产生式中所有终结符填入opTable表第一行和第一列，然后利用产生式和FirstVt表LastVt表分别找出满足=关系、<关系、>关系的算符填表。若相应位已有关系，说明两个终结符之间至少有两种优先关系，该文法不是算符优先文法。 5、最后调用InputAnalyse（）对输入串进行分析。初始化分析栈S，依次判断当前输入符a和分析栈中离栈顶最近的终结符S[ j ]的关系，若S[ j ]< a ，则a移近，若S[ j ]< a ，则往前找到第一个S[ j ]>a，将S[ j -1]到栈顶S[ k ]规约，若S[ j ]= a ，如果S[ j ]=#，则接受，如果S[ j ]！=#，则移进。直到接受或者出错，算符优先分析结束。 3.4  开发环境 实验使用windows vista操作系统下的Microsoft Visual C++ 6.0平台，用C语言完成。 4  详细设计 4.1  模块划分 实验分为五个模块，分别是： 1、文件的导入：                readfile（sen[][]）； 2、FirstVt、LastVt集的构造：    FirstVt（sen[][],first[][],sen_len,frist_len）； LastVt（sen[][],last[][]，sen_len,frist_len）； 3、算符优先关系表OpPriotable的构造： OpPriotable（sen,first,last,opTable,sen_len,first_len,&opTable_len）； 4、算符优先分析过程的实现： InputAnalyse（opTable[][col],string[col],opTable_len）； 5、主函数：main（）。 4.2 主要算法的流程图 图4-1  算符优先分析法程序流程图 4.3  数据分析与定义 1、文法（产生式）：文法使用产生式来定义 char sen[row][col]：用二维数组表示产生式； int sen_len：产生式的个数    ； 2、FIRSTVT集： char first[row][col]：用二维数组构造FIRSTVT表 int frist_len：FIRSTVT表的行数； 3、LASTVT集： char last[row][col]：用二维数组构造LASTVT表；