基于C++设计与实现算符优先语法分析【100013000】

# 算符优先语法分析设计原理与实现 ## 一、 理论传授 语法分析的设计方法和实现原理，算符优先文法、最左素短语、算符优先矩阵、优先函数的基本概念；算符优先文法句型最左素短语的确定；算符优先分析算法的实现； ## 二、 目标任务 ### 实验项目 实现算符优先分析算法，完成以下描述算术表达式的算符优先文法的算符优先分析过程。 G[E]:E→E+T∣E-T∣T T→T*F∣T/F∣F F→(E)∣i ### 设计说明 终结符号 i 为用户定义的简单变量,即标识符的定义。 ### 设计要求 （1）构造该算符优先文法的优先关系矩阵或优先函数； （2）输入串应是词法分析的输出二元式序列，即某算术表达式“专题 1”的输出结果。输出为输入串是否为该文 法定义的算术表达式的判断结果。 （3）算符优先分析过程应能发现输入串出错。 （4）设计两个测试用例（尽可能完备，正确和出错），并给出测试结果； （5）考虑编写程序根据算符优先文法构造算符优先关系矩阵，并添加到你的算符优先分析程序中。 ## 三. 任务分析 重点解决算符优先矩阵的构造方法和算符优先算法的实现。 ## 四、实验原理分析 1、构造 FirstVT 和 LastVT 集合 算法如下： ``` PROCEDURE insert(P,a); IF not F[P,a] then begin f[p,a] = true; (P,a)进栈 end; Procedure FirstVT; Begin for 对每个非终结符 P 和终结符 a do F[P,a] = false for 对每个形如 P→a…或 P→Qa…的产生式 do Insert(P,a) while stack 非空 begin 栈顶项出栈，记为(Q,a) for 对每条形如 P→Q…的产生式 do insert(P,a) end; end. ``` 2、构造算符优先分析表 依据文法和求出的相应 FirstVT 和 LastVT 集生成算符优先分析表。 算法描述如下： ``` for 每个形如 P->X1X2…Xn 的产生式 do for i =1 to n-1 do begin if Xi和 Xi+1都是终结符 then Xi = Xi+1 if i<= n-2, Xi和 Xi+2 是终结符, 但 Xi+1 为非终结符 then Xi = Xi+2 if Xi为终结符, Xi+1为非终结符 then for FirstVT 中的每个元素 a do Xi < a ; if Xi为非终结符, Xi+1为终结符 then for LastVT 中的每个元素 a do a > Xi+1 ; end; ``` ## 五、程序功能描述 1、手动输入文法语句，将二元式序列文件读入程序 2、依据文法求出的相应 FirstVT 和 LastVT 集，并生成算符优先分析表 3、进行算符优先分析，判断读入字符串是否是文法的句子 ## 六、程序结构描述 数据结构： GRAM 表示非终结符号的结构体，其中包含其 first 和 follow 集  进行移进归约分析时，使用 Stack 和 a 数组。  程序结构： 主函数包含三个子函数，analyze()作用是分析输入文法，依据文法求出的相应 FirstVT 和 LastVT 集，并生成算符优先分析表；init()的作用是读入字符串；parser 的作用是依据生成的算符优先分析表进行算符优先分析，判断输入串是否为文法的合法语句，如果出错则进行相应提示。  Norterminal()的作用是判断终结符和非终结符 返回 1 是非终结符 返回 0 是终结符。 IsReduce()的作用是寻找与最左素短语匹配的产生式 getVtNumber()的作用是获取终结符号 ch 的序号 Higher、Lower、Equal 均是对算符优先关系判断的函数 ## 七、实验结果及测试 1、测试样例 i+i*i  输入文法后，则打印优先关系矩阵，然后对读入串进行分析，得到结果是该输入串是算符优先分析的文法，见下图：   2、测试样例(i+i)/i-i  算符优先分析成功：  3、测试样例(i+i/i-i  该输入串不是文法的句子，所以分析失败