编译原理与技术课程语法分析器设计文档.doc

语法分析实验报告一、语法分析器功能描述1. 算数表达式消除左递归之后的文法E - TEE - +TE| -TE | T - FTT - *FT | /FT| F - id | (E) | num 文法1其中： id: a-f, A-F num:0-92. 本语法分析器采用LL(1)分析方法对上述文法进行语法分析3. 功能如下： (1)存入FIRST集与FOLLOW集后，为算术表达式文法构造预测分析表并输出； (2)构造LL(1)预测分析程序，可以根据预测分析表对输入的表达式进行语法分析，输出产生式； (3)可以处理两类语法错误：a.如果栈顶终结符号，但却与当前输入符号不匹配；b.如果栈顶是非终结符号A，当前输入符号为a，但分析表中A,a为空。二、运行环境 windows 8.1操作系统 三、输入输出设计1. 输入设计输入算数表达式，以“回车键”结束。算数表达式的组成为：+、*、/、(、)、af、AF、09、2.输出设计输出分为三部分：a.输出预测分析表。表项为产生式的序号(文法1中的顺序)，0表示空白，表示同步信息synch，用于出错处理；b.输出最左推导用到的产生式，均为文法1(消左递归后的文法)中的产生式，产生式中的 用 表示；c.若在分析过程中发现错误，输出对错误的应急式处理。四、主要数据结构设计0. FIRST集与FOLLOW集FIRST集FOLLOW集SId，（，num$，）S，+，$，）TId，（，num$，），+，T，*，/$，），+，PId，（，num$，），+，*，/1. 预测分析表：char analyze_table59; 2. FIRST集：char FIRST74=x,(,y, , +,-, , x,(,y, , *,/, , x,(,y, , x, , y, ; 注：依次为E、E、T、T、F的FIRST集。 表示终结，x 表示 id，y 表示num， 表示 。3. FOLLOW集：char FOLLOW57=$,), , $,), , $,),+,-, , $,),+,-, , $,),+,-,*,/, ;注：依次为E、E、T、T、F的FOLLOW集。 表示终结，x 表示 id，y 表示num， 表示 。4. 产生式集：char production116=STR#, R+TR#,R-TR#, R#, TPZ#, Z*PZ#,Z/PZ#, Z#, Px#, P(S)#,Py#; 注：x表示id，y表示num， 表示 。5. 输入缓冲区：char in_buffer100;6. 分析栈char stack100; 7. 栈顶指针top；指向当前符号的指针ip。五、核心算法描述核心算法主要分为两部分：构造预测分析表，预测分析程序1. 构造预测分析表子函数：void make_table(void);/构造预测分析表int locate_nontmn(char);/定位非终结符，即在分析表的第几行 int locate_tmn(char);/定位终结符，即在分析表的第几列 void print_table(void);/格式化输出预测分析表算法描述： for(文法1的每个产生式A-) for(每个终结符号aFIRST() 把A-放入MA,a中； if (FIRST() for(任何bFOLLOW(A) 把A-放入MA,b中； for(每个非终结符A) /添加同步信息synch,表项0为空白, -1为synch for(每个终结符cFOLLOW(A) if (MA,c=0) 令MA,c = -1; 构造分析表的流程图：开始初始化预测分析表，且i=1注：i表示产生式的序号，共有11条产生式iY1Y2YK 从栈顶弹出X； 依次将Yk、Yk-1.Y2、Y1压入栈； 输出产生式X-Y1 Y2. Yk ; else /出错处理，/-1表示synch表项，0表示空白表项 if (MX,a = 0) 跳过输入符号a； if (MX,a = -1) 将栈顶非