算符优先词法分析器编译原理完整课程设计.doc

算符优先词法分析器 目 录一、 设计目的 ………………………………………………1二、 设计原理 ………………………………………………1三、 设计思想 ………………………………………………2四、 设计要求……………………………………………… 3五、 设计流程图及程序…………………………………… 4六、 运行结果及分析………………………………………14七、 设计总结………………………………………………16八、 参考文献………………………………………………16- 2 -算符优先词法分析器 一、设计目的 算符优先算法是自底而上分析方法的一种所谓自底向上分析，也称移进—规约分析，粗略地说他的实现思想是对输入符号串自左向右进行扫描，并将输入符逐个移入一个后进先出的栈中，边移进边分析，一旦栈顶符号串形成某个句型的句柄或可规约串是，就用该产生式的左部非终结符代替相应右部的文法符号串，这称为一部规约重复这一过程直到规约到栈中只剩文法的开始符号是则为分析成功，也就确认输入串是文法的句子。

而算符优先分析的基本思想是只规定算符之间的优先关系，也就是只考虑终结符之间的优先关系 本课程设计的主要目的： 1、通过本次课程设计，全面系统的了解编译原理程序构造的一般原理和基本实现方法，尤其是对自底向上的优先分析方法的认识和理解； 2、提高对编译程序工作基本过程及其各阶段基本任务的分析技能； 3、加强对编译程序的生成过程、构造工具及编译程序总流程框图的理解，巩固所学的课本知识 二、设计原理 算符优先分析法是一种有效的自底向上的分析方法自底向上分析方法面临的主要问题是如何确定可归约串，而算符优先分析法根据两个终结符号之间的优先关系比较，成功的解决了可归约串的问题算符优先分析法是采用最左素短语进行归约的，严格来讲不属于规范规约的范畴因此，在设计以前我们必须要知道什么是素短语和最左素短语所谓素短语就是指句型中具有这样性质的短语：至少含有一个终结符，且除了自身之外，不再含有任何更小的素短语的短语最左素短语，是指在句型的所有素短语中，处于句型最左边的素短语了解了素短语和最左素短语，那么如何构造这种算法呢？首先，根据非终结符的FIRSTVT集和LASTVT集找出它们之间的优先关系，构造算符优先矩阵。

然后，由此矩阵构造相应符号串的算符优先分析表并编写程序 三、设计思想 在算符优先算法中，存在定理： 一个算符优先文法G的任何句型 # N1 a1 N2 a2 … Nn an Nn+1 #（a∈VT,Nj∈VN,i=1, 2, …，n, n+1,Nj可有可无）的最左素短语是满足下列条件的最左子串： Nj aj Nj+1 aj+1 … Ni ai Ni+1其中，aj-1 < aj aj = aj+1, …,ai-1 = ai ai > ai+1由该定理可以看出，在算符优先文法的句型中，任何素短语中最相近的两个终结符的优先级相等，且素短语中位于最前面的终结符的优先级高于在句型中紧临其前的终结符的优先级，而素短语中处于最后面的终结符的优先级高于在句型中紧随其后的终结符的优先级设有算符优先文法G[S]=（VN, VT, P, S），则得出如下步骤： 1、根据G[S]文法构造优先关系矩阵；2、设置一个符号栈S，存放已经归约的或待形成最左素短语的符号串，另设一个工作单元R，存放当前的待输入符号；3、采用移进归约的方法，当符号栈S的栈顶形成可归约串——最左素短语时，进行归约。

具体方法如下：①分析开始时，符号栈S中只有一个符号“#”，工作单元R中存放输入串的第一个终结符；②查优先关系矩阵，比较符号栈中最靠栈顶的终结符号（假设为a）与工作单元R中的终结符（假设为b）的优先关系； ⅰ）若a,b之间无优先关系，则出错并退出分析程序； ⅱ）若ab，则表明此时栈顶已经形成最左素短语，转③； ③从符号栈中最靠栈顶的终结符Xn开始，依次向前（向栈底方向）与最近的终结符比较,若Xn-1=Xn，则继续比较Xn-2和Xn-1如此反复，直至 Xi-1 < Xi （i=1, 2, … n, 设X0 = #）为止，于是最左素短语的左界也确定，此时最左素短语为从Ni开始（Ni为在Xi之前紧临Xi的非终结符，若为“空”，则从Xi开始）一直到栈顶的符号串： Ni Xi Ni+1 Xi+1 … Nn Xn Nn+1④在文法G[S]的产生式中，选择其右部具有Ni Xi Ni+1 Xn+1 … Nn Xn Nn+1形式的规则进行规约（注意：此时非终结符号不必完全相同）：弹出符号栈栈顶的最左素短语，相应规则的左部非终结符进栈。

若此时分析栈中只有#和文法的一个非终结符，且待分析符号串只剩下#（即工作单元R中符号为#），则表明分析成功，所分析的输入串（源程序）是文法G[S]的句子，退出分析程序；否则，重复②有了以上的思路，我们首先对已经给定的文法按其产生式构造算符优先关系表，有了算符优先关系表并满足算符优先文法时，我们就可以对任意给定的符号串进行归约分析，形成句柄时就归约，最后判定输入串是否为该文法的句子在分析过程中可以设置一个符号栈S，用以寄存归约或待形成最左素短语的符号串，用一个工作单元a存放当前读入的终结符号，归约成功的标志是当读到句子结束时，S栈中只剩#N，即只剩句子最左括号‘#’和一非终结符N四、设计要求使用算符优先分析算法分析下面的文法： E’ → #E# E → E+T | T T → T*F | F F → P^F | P P → (E) | i 其中i可以看作是一个终结符，无需作词法分析具体要求如下： 1、如果输入符号串为正确句子，显示分析步骤，包括分析栈中的内容、优先关系、输入符号串的变化情况；2、 如果输入符号串不是正确句子，则显示出错。

五、设计流程图及程序 1、分析 文法为： (0)E'→ #E# (1)E → E+T (2)E → T (3)T → T*F (4)T → F (5)F → P^F (6)F → P (7)P → (E) (8)P → i  根据算符优先文法的分析规则求得终结符优先矩阵+*^i()#+><<<<>>*>><<<>>^>><<<>>i>>>>>(<<<<<=)>>>>>#<<<<<=2、程序流程图 图1 算符优先算法流程图 3、程序： #include #include #include #include #include #include #include #define SIZE 128 char youxian[7][7];  //算符优先关系数组 char lexbuf[SIZE]; //存放输入的要进行分析的句子 char lex[SIZE];   //存放剩余串 char fenxizhan[SIZE]; //分析栈 void fenxi(); int panduanyou(char x); void shengyuchuan(); int k; void zengjia(); void main() { { //将算符优先关系存放在算符优先关系数组里 youxian[0][0]='>'; youxian[0][1]='<'; youxian[0][2]='<'; youxian[0][3]='<'; youxian[0][4]='<'; youxian[0][5]='>';  youxian[0][6]='>'; //______________________________________________________________ youxian[1][0]='>'; youxian[1][1]='>'; youxian[1][2]='<'; youxian[1][3]='<'; youxian[1][4]='<'; youxian[1][5]='>'; youxian[1][6]='>'; //_______________________________________________________________ youxian[2][0]='>'; youxian[2][1]='>'; youxian[2][2]='<'; youxian[2][3]='<'; youxian[2][4]='<'; youxian[2][5]='>'; youxian[2][6]='>'; //_______________________________________________________________ youxian[3][0]='>'; youxian[3][1]='>'; youxian[3][2]='>'; youxian[3][3]='$';//无优先关系的用$表示 youxian[3][4]='$'; youxian[3][5]='>'; youxian[3][6]='>';    //_________________________________________________________________ youxian[4][0]='<';    youxian[4][1]='<'; youxian[4][2]='<';   youxian[4][3]='<';   youxian[4][4]='<';   youxian[4][5]='=';。