编译原理课程设计报告_算符优先分析法编译原理课程设计报告选题名称: 算符优先分析法系（院）: 计算机工程学院专业: 计算机科学与技术班级:姓名: 学号:指导教师:学年学期: 7>2012 ~ 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中含有形如A→…ab…或A→…aBb…的产生式② ab 当且仅当G中含有形如A→…aB …的产生式，且Bb…或BCb…③ ab当且仅当G中含有形如A→…Bb …的产生式，且B…a 或B…aC以上三种关系也可由下列语法树来说明：① 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中没有形如A→…BC…的产生式，其中B和C为非终结符，则称G为算符文法 Operater Grammar 也称OG文法。
例如：表达式文法E→E+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|B…a 或 B …aC三种优先关系的计算为a 关系:可直接查看产生式的右部，对如下形式的产生式A→…ab… , A→…aBb…有a b 成立。
b 关系:求出每个非终结符B的FIRSTVT B ，在如下形式的产生式A→…aB…中，对每一 b∈FIRSTVT B ,有ab成立。
c 关系:计算每个非终结符B的LASTVT B ，在如下形式的产生式A→…Bb…中，对每一a∈LASTVT B ，有ab成立。
最左素短语的定义设有文法G[S],其句型的素短语是一个短语,它至少包含一个终结符，并除自身外不包含其它素短语，最左边的素短语称最左素短语。
例如,若表达式文法G[E]为：E→E+T|TT→T*F|FF→P↑F|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 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.2 流程图图3-1 程序流程图4 代码编写在这次课程设计过程中，我主要负责的是FIRSTVT、 LASTVT集的构造部分，代码如下。
//FIRSTVT表和LASTVT表中表项（非终结符）的初始化void ItemInit char sen[][col],char first[][col],char last[][col],int sen_len,int &frist_lenint i;frist_len 1;first[0][0] sen[0][0];last[0][0] sen[0][0];for i 1;i sen_len;i++if TerminalJud sen[i][0] false && ItemJud first,frist_len,sen[i][0] false //k是当前first和last表的长度first[frist_len][0] sen[i][0];last[frist_len][0] sen[i][0];frist_len++;void FirstVt char sen[][col],char first[][col],int sen_len,int frist_len // frist_len 是 first 表的行数 sen_len是产生式的个数StackElement DFS,record[SIZE];stack Operator; //创建存放（A，a）的栈InitStack Operator ;int i,j,r 0;for i 0;i sen_len;i++ //第一次扫描，将能直接得出的first （A，a）放进栈中for j 3;sen[i][j]! '\0';j++if TerminalJud sen[i][j] true //遇到的第一个终结符压入int exist 0;DFS.nonterm sen[i][0];DFS.term sen[i][j];for int i1 0;i r;i++if record[i1].nonterm sen[i][0]&&record[i1].term sen[i][j]exist 1;break;record[r].nonterm sen[i][0];record[r].term sen[i][j];if exist 0Insert Operator,DFS ;//A-aB A-aC A,a 压栈两次?record[r].nonterm sen[i][0];record[r].term sen[i][j];r++;break;int location[col]; //辅助数组，用来记录first表中放入终结符的位置for i 0;i frist_len;i++location[i] 1;while !ifEmpty Operatorint exist 0; //标志位，记录即将入栈的元素是否已经存在StackElement IDElement,DElement;DElement Pop Operator ; //弹出栈顶元素for i 0;i frist_len;i++if first[i][0] DElement.nontermint n location[i];first[i][n] DElement.term; //将终结符填入相应的first表中location[i]++;break;for j 0;j sen_len;j++if sen[j][3] DElement.nonterm //找出能推出当前非终结符的产生式的左部IDElement.nonterm sen[j][0];IDElement.term DElement.term;//判断将要放进栈里的元素曾经是否出现过，若没有，才压入栈for int r0 0;r0 r;r0++ //r记录record数组中的元素个数if record[r0].nonterm IDElement.nonterm && record[r0].term IDElement.termexist 1;break;if exist 0Insert Operator,IDElement ;record[r].nonterm IDElement.nonterm;record[r].term IDElement.term;r++;//if//for//whilevoid LastVt char sen[][col],char last[][col],int sen_len,int frist_len //firstvt表与lastvt表行数一样 first_len表示last 表的行数int i,j,i1,j1;char c,record[row][col] '\0' ;for i 0;i sen_len;i++for j 0;sen[i][j]! '\0';j++record[i][j] sen[i][j];j j-1;for i1 3,j1 j;i1 j1;i1++,j1-- //做翻转，就可以用求first的方法求lastc record[i][i1];record[i][i1] record[i][j1];record[i][j1] c;//forFirstVt record,last,sen_len,frist_len ;5 程序调试程序中调用了许多函数，编写代码时会出现调用的错误，使在程序运行时无法正确判断以致程序运行出错。