带出错处理的算符优先分析算法的程序实现.doc

目 录 第一章 概述.....................................................1 1.1设计内容....................................................1 1.2设计要求....................................................1 第二章 设计的基本原理............................................2 2.1算法分析..................................... ...............2 2.2错误处理....................................... .............3 第三章 程序设计..................................................4 3.1总体方案设计.................................................4 3.2各模块设计...................................................6 第四章 程序测试...................................................7 第五章 结论.......................................................11 附录 程序清单...................................................11 第一章 概述 1.1设计内容i # + * ( = e1 ) e2 e2 i e2 e2 # e3 e4 可以根据已知的文法G和优先关系表编写带出错处理的算符优先分析算法程序。对输入的符号串进行“移进—归约”，若有错误出现，则进行错误处理，指出错误原因。当归约到“#E#”时则分析完毕，实现了该算法。 1.2设计设计的基本原理 其中，每个都是终结符，是可有可无的非终结符。换言之，句型中含有n个终结符，任何两个终结符之间顶多只有一个非终结符。一个算法优先文法G的任何句型的最左素短语是满足如下条件的最左字串， 根据这个定理，可以构造算法优先算法。设使用一个符号栈S，既用它寄存终结符，也用它寄存非终结符。下面的分析算法是直接根据这个定理构造出来的，其中k代表符号栈S的使用深度。 k:=1; S[k]:= ‘#’; REPEAT 把下一个输入符号读进a中； IF S[k] THEN j:=k ELSE j:k-1; WHILE S[j] a DO BEGIN REPEAT Q:=S[j]; IF S[j-1] THEN j:j-1 ELSE j:j-2 UNTIL S[j] Q; 把S[j+1]…S[k]归约为某个N； k:=j+1; S[k]:=N; END OF WHILE; IF S[j] a OR s[j] = a THEN BEGIN k:=k+1; S[k]:=a END ELSE ERROR /* 调用出错诊察程序 */ UNTIL a = ‘#’ 在上述算法的工作过程中，若出现j减1后的值小于等于0时，则意味着输入串有错。在正确的情况下，算法工作完毕时，符号栈S应呈现：# N # 算法优先分析一般并不等价于规范归约。在算法优先归约过程中，我们无法用那些右部仅含一个一个非终结符的产生式进行归约。对该文法G的句子i+i，按算法优先分析法，归约过程是：先把第一个i归为F，然后把第二个i也归约为F，最后把F+F直接归约为E。在此过程中，单非产生式对归约没有发挥作用。 错误处理 算符优先分析中的出错处理： 如 + 或 * 被归约，则检查其两端是否出现非终结符。否则，打印错误信息：“缺表达式”。 如i被归约，则检查其左端或右端是否有非终结符。如果有，则给出信息：“表达式间无运算符联结”。 如()被归约，则检查是否在括号间有一非终结符。如果没有，则给出信息：“括号间无表达式”。 根据优先关系表中的e1，e2，e3，e4可以调用错误处理子程序。 e1： /*当表达式以左括号结尾时，调用此程序*/ 将‘(’从栈顶移去；给出错误信息：非法左括号。 e2： /*当i或)后跟i或(时，调用此程序*/ 在