编译原理课程设计报告_算符优先分析法.doc

编译原理课程设计报告_算符优先分析法 编译原理课程设计报告选题名称: 算符优先分析法 系（院）: 计算机工程学院 专 业: 计算机科学与技术 班 级: 姓 名: 学 号: 指导教师: 学年学期: 72012 2013 学年 第 1 学期2012年 12 月 04 日设计任务书课题 名称算符优先分析法设计目的通过一周的课程设计，对算符优先分析法有深刻的理解，达到巩固理论知识、锻炼实践能力、构建合理知识结构的目的。实验环境Windows2000以上操作系统，Visual C+6.0编译环境任务要求1.判断文法是否为算符优先文法，对相应文法字符串进行算符优先分析；2.编写代码，实现算符优先文法判断和相应文法字符串的算符优先分析；3.撰写课程设计报告；4提交报告。工作进度计划序号起止日期工 作 内 容1理论辅导，搜集资料2编写代码，上机调试3撰写课程设计报告4提交报告指导教师（签章）： 年 月 日摘要：编译原理是计算机专业重要的一门专业基础课程，内容庞大，涉及面广，知识点多。本次课程设计的目的正是基于此，力求为学生提供一个理论联系实际的机会，通过布置一定难度的课题，要求学生独立完成。我们这次课程设计的主要任务是编程实现对输入合法的算符优先文法的相应的字符串进行算符优先分析，并输出算符优先分析的过程。算符优先分析法特别有利于表达式的处理，宜于手工实现。算符优先分析过程是自下而上的归约过程，但这种归约未必是严格的规范归约。而在整个归约过程中，起决定作用的是相继连个终结符之间的优先关系。因此，所谓算符优先分析法就是定义算符之间的某种优先关系，并借助这种关系寻找句型的最左素短语进行归约。通过实践，建立系统设计的整体思想，锻炼编写程序、调试程序的能力，学习文档编写规范，培养独立学习、吸取他人经验、探索前言知识的习惯，树立团队协作精神。同时，课程设计可以充分弥补课堂教学及普通实验中知识深度与广度有限的缺陷。关键字： 编译原理；归约；算符优先分析；最左素短语；目 录1 课题综述11.1 课题来源11.2课题意义11.3 预期目标11.4 面对的问题12 系统分析22.1 基础知识22.2 解决问题的基本思路52.3 总体方案53 系统设计63.1 算法实现63.2 流程图74 代码编写85 程序调试116 运行与测试12总 结13致 谢14参考文献151 课题综述 1.1 课题来源算符文法：即它的任一产生式的右部都不含两个相继的非终结符的文法。如果G是一个不含空字符的算法文法，那么只要它的任一对终结符都只满足 ， ， 的关系的一种，则称G是一个算符优先文法。1.2课题意义算符优先文法在规约过程中只考虑终结符之间的优先关系确定句柄，而与非终结符无关，只需知道把当前句柄规约为某一非终结符，不必知道该非终结符的名字是什么，这样也就去掉了单非终结符的规约，因为若只有一个非终结符时无法与句型中该非终结符的左部及右部的串比较优先关系。也就无法确定该非终结符为句柄。1.3 预期目标编写程序，实现文法的算符优先判断，并对输入的符合算符优先文法的字符串进行算符优先分析。首先对输入的表达式求FIRSTVT集和LASTVT集，然后根据优先级关系构造算符优先关系表，最后进行算符优先分析的过程。过实践，建立系统设计的整体思想，锻炼编写程序、调试程序的能力，学习文档编写规范，培养独立学习、吸取他人经验、探索知识的习惯。1.4 面对的问题如何通过自底向上的方法分析表达式，构造文法的优先矩阵，以及如何运用该优先矩阵完成移入和归约的过程，从而完成整个文法的分析。1.5 需解决的关键技术本次课程设计中的关键是：扫描和语法分析函数，它使用一个用于存放文法符号的先进后出栈，并利用有限关系可以确定最左素短语是否已形成来决定分析器的动作。如果当前栈顶的终结符号和带输入符号之间优先关系是 或 则表示栈顶符号串未形成最左素短语，此时分析器将移进输入符号。如果当前栈顶的终结符号和待输入符号之间的优先关系是 ，则表示已找到最左素短语的尾，在从栈顶开始，按优先关系在栈内向左寻找最左素短语的头，然后分析器将归约最左素短语。如果出现两个终结符号之间不存在优先关系，则表示存在语法错误。以及如何编写、调试、修改代码。还要了解一个题目有许多种解决方法。锻炼我们的思维能力。 2 系统分析2.1 基础知识 算符优先分析法的基本思想仿照算术表达式的四则运算过程算符优先分析的基本思想是只规定算符 广义为终结符 之间的优先关系，也就是只考虑终结符之间的优先关系，不考虑非终结符之间的优先关系。在归约过程中只要找到可归约串就归约，并不考虑归约到那个非终结符名，算符优先分析的可归约串不一定是规范句型的句柄，所以算符优先归约不是规范归约。算符优先分析的可归约串是当前符号栈中的符号和剩余的输入符号构成句型的最左素短语。先关系的定义设G是一个不含产生式的算符文法，a和b是任意两个终结符，A、B、C是非终结符，算符优先关系、定义如下 ： ab 当且仅当G中含有形如Aab或AaBb的产生式 ab 当且仅当G中含有形如AaB 的产生式，且Bb 或BCb ab当且仅当G中含有形如ABb 的产生式，且Ba 或BaC以上三种关系也可由下列语法树来说明： a b 则存在语法子树如图2.1 a 其中为或为B，这样a, b在同一句柄中同时归约所以优先级相同。 a b 则存在语法子树如图2.1 b 其中为或为C。a,b不在同一句柄中，b先归约，所以a的优先级低于b。 a b 则存在语法子树如图2.1 c 。图2.1 由语法树结构决定优先性先文法的定义设有一文法G，如果G中没有形如ABC的 产生式，其中B和C为非终结符，则称G为算符文法 Operater Grammar 也称OG文法。例如：表达式文法EE+E|E*E| E |i其中任何一个产生式中都不包含两个非终结符相邻的情况，因此该文法是算符文法。设有一不含产生式的算符文法G，如果对任意两个终结符对a，b之间至多只有 、 和 三种关系中的一种成立，则称G是一个算符优先文法。 Operator Precedence Grammar 即OPG文法。由以上内容我们可计算出给定的算符文法中任何两个终结符对 a,b 之间的优先关系，其算法如下：首先定义如下两个集合：FIRSTVT B b|B b 或 B Cb LASTVT B a|Ba 或 B aC 三种优先关系的计算为a 关系: 可直接查看产生式的右部，对如下形式的产生式Aab , AaBb有a b 成 立。b 关系:求出每个非终结符B的FIRSTVT B ，在如下形式的产生式AaB 中，对每一 bFIRSTVT B ,有ab成立。c 关系:计算每个非终结符B的LASTVT B ，在如下形式的产生式ABb 中，对每一aLASTVT B ，有ab成立。 最左素短语的定义设有文法GS,其句型的素短语是一个短语,它至少包含一个终结符，并除自身外不包含其它素短语，最左边的素短语称最左素短语。例如,若表达式文法GE为：EE+T|TTT*F|FFPF|PP E |i图2.2 句型T+T*F+i的语法树若有句型#T+T*F+i#，它的语法树如图2.2。其短语有：T+T*F+i 相对于非终结符E的短语T+T*F 相对于非终结符E的短语T 相对于非终结符E的短语T*F 相对于非终结符T的短语i 相对于非终结符P,F,T的短语由以上内容知i和T*F为素短语，T*F为最左素短语。也为算符优先分析的可归约串。由算符优先分析算法可知一个算符优先文法的最左素短语满足如下条件：ai-1 ai ai+1 . aj aj+1上述句型#T+T*F+i#写成算符分析过程的形式为：#N1a1N2a2N3a3a4#其中a1 +, a2 *, a3 +, a4 ia1 a2 因+ * a2 a3 因* + 由此 N2a2N3 即T*F为可归约串，也就是前面分析的最左素短语。2.2 解决问题的基本思路根据课程设计的要求，程序应具有如下功能：对输入的文法进行分析并判断是否为算符优先文法。如果是算符优先分析文法则再进一步输入符合该算符优先文法的字符串，并对该字符串进行算符优先分析，同时输出算符优先分析的过程。2.3 总体方案启动VC+，新建源程序并进行编程，程序的功能模块图如图2-1所示。图2-1系统功能结构图函数功能：Main 函数：调用主函数，运行程序；FIRSTVT 函数：构造FIRSTVT表；LASTVT 函数：构造LASTVT表；OpPrioTable 函数：构造算符优先关系表；InputAnalyse 函数：分析输入串是否为文法中的句子，并给出规约过程。3 系统设计3.1 算法实现算符优先分析法的具体过程如下：1、首先先输入文件的路径，在readfile char sencol 函数中，将需要分析的文法通过输入流文件打开函数open 复制到senrowcol中。2、然后利用FIRSTVT 构造产生式senrowcol的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.2 流程图图3-1 程序流程图4 代码编写在这次课程设计过程中，我主要负责的是FIRSTVT、 LASTVT集的构造部分，代码如下。/FIRSTVT表和LASTVT表中表项（非终结符）的初始化void ItemInit char sencol,char firstcol,char lastcol,int sen_len,int &frist_len int i;frist_len 1;first00 sen00;last00 sen00;for i 1;i sen_len;i+ if TerminalJud seni0 false & ItemJud first,frist_len,seni0 false /k是当前first和last表的长度 firstfrist_len0 seni0;lastfrist_len0 seni0;frist_len+; void FirstVt char sencol,char firstcol,int sen_len,int frist_len / frist_len 是 first 表的行数 sen_len是产生式的个数 StackElement DFS,recordSIZE;stack Operator; /创建存放（A，a）的栈InitStack Operator ; int i,j,r 0;for i 0;i sen_len;i+ /第一次扫描，将能直接得出的first（A，a）放进栈中 for j 3;senij! 0;j+ if TerminalJud senij true /遇到的第一个终结符压入 int exist 0;DFS.nonterm seni0;DFS.term senij;for int i1 0;i r;i+ if recordi1.nonterm seni0&recordi1.term senij exist 1;break; recordr.nonterm seni0;recordr.term senij;if exist 0 Insert Operator,DFS ;/A-aB A-aC A,a 压栈两次?recordr.nonterm seni0;recordr.term senij;r+; break; int locationcol; /辅助数组，用来记录first表中放入终结符的位置for i 0;i frist_len;i+ locationi 1;while !ifEmpty Operator int exist 0; /标志位，记录即将入栈的元素是否已经存在StackElement IDElement,DElement;DElement Pop Operator ; /弹出栈顶元素for i 0;i frist_len;i+ if firsti0 DElement.nonterm int n locationi;firstin DElement.term; /将终结符填入相应的first表中locationi+;break; for j 0;j sen_len;j+ if senj3 DElement.nonterm /找出能推出当前非终结符的产生式的左部 IDElement.nonterm senj0;IDElement.term DElement.term;/判断将要放进栈里的元素曾经是否出现过，若没有，才压入栈for int r0 0;r0 r;r0+ /r记录record数组中的元素个数 if recordr0.nonterm IDElement.nonterm & recordr0.term IDElement.term exist 1;break; if exist 0 Insert Operator,IDElement ;recordr.nonterm IDElement.nonterm;recordr.term IDElement.term;r+; /if /for /while void LastVt char sencol,char lastcol,int sen_len,int frist_len /firstvt表与lastvt表行数一样 first_len表示last 表的行数 int i,j,i1,j1;char c,recordrowcol 0 ;for i 0;i sen_len;i+ for j 0;senij! 0;j+ recordij senij; j j-1; for i1 3,j1 j;i1 j1;i1+,j1- /做翻转，就可以用求first的方法求last c recordii1;recordii1 recordij1;recordij1 c; /forFirstVt record,last,sen_len,frist_len ; 5 程序调