编译原理实验报告-语法分析

编译原理课程实验报告 实验2：语法分析

姓名 软件学院三楼机房 出勤、表现得分 操作结果得分 院系 软件学院 指导教师 实验时间 实验报告 得分 2016/10/30/星期日 实验总分 得分 学号 任课教师 实验地点 实验课表现 一、需求分析 要求：采用至少一种句法分析技术（LL(1)、SLR(1)、LR(1)或LALR(1)）对类高级语言中的基本语句进行句法分析。阐述句法分析系统所要完成的功能。 本语法分析器是在词法分析器的基础上实现对类高级语言中的基本语句进行句法分析，基本功能如下： （1）能识别以下几类语句： 声明语句（包括变量声明、数组声明、记录声明和过程声明） 表达式及赋值语句（包括数组元素的引用和赋值） 分支语句：if_then_else 循环语句：do_while 过程调用语句 （2）本语法分析器采用自顶向下的分析技术，能根据导入的文法，自动计算first集和follow集，能够生成每个产生式的select集，并自动生成预测分析表。 （3）本语法分析器具备语法错误处理能力，可以进行错误检测，如果检测到在出错时，采用恐慌模式，能够给出错误提示信息，格式：错误项 错误原因 行号 a)忽略输入中的一些符号，直到输入中出现选定的同步词法单元集合中的某个词法单元，同步集合的选取是非终结符的follow集； b)如果终结符在栈顶而不能匹配，弹出此终结符。 c)输入栈中缺少某些应有的符号，比如只有右括号没有左括号等，会给出相应的提示。 （4）系统的输入形式多样：可以通过文件导入文法和测试用例，可以通过用户界面显示并编辑测试用例。测试用例涵盖了第（1）条中列出的各种类型的语句，并设置了一些语法错误。 （5）系统的输出分为两部分：一部分是打印输出语法分析器的FIRST集、FOLLOW集、select集和LL(1)分析表。另一部分是打印输出语法分析结果。 （6）本系统还实现了输出语法分析树的功能，让语法分析的过程更清晰。 二、文法设计 要求：给出如下语言成分的文法描述。 得分 声明语句（包括变量声明、数组声明、记录声明和过程声明） 表达式及赋值语句（包括数组元素的引用和赋值） 分支语句：if_then_else 循环语句：do_while 过程调用语句 本语法分析器主要针对C语言进行文法设计，下面给出各语言成分的文法描述。 程序入口： Program->P P->D P //支持连续声明 P ->S P P->ε 1） 声明语句： D proc id ; D S| T id; //支持过程声明和变量声明 T → X C | record D //支持结构体声明 X → short|int | long|float|double|char|string //支持多种基本类型的声明 C → [num]C | ε //支持数组的声明 2)表达式及赋值语句: S id = E ;| L = E ; E E + E | E * E | E | (E) | id | digit | L L id[E] | L[E] //支持数组元素的引用和赋值 3) 控制流语句: S if B then S1 else S2 | while B do S1 B → B || B | B && B | ! B //或语句 //且语句 //非语句 | (B) //使用括号 | E relop E //关系语句 | true //bool型 | false //bool型 relop → < | <= | == | != | > | >= //关系符号 4）过程调用语句 S call id (Elist) Elist Elist, E Elist E 下面给出整个程序的无二义性，无左递归的LL（1）文法： Program->P P->D P|S P|empty D->proc T id ( M ) { P }|T id A ;|record id { P } M->X id M' M'->, X id M'|empty A->= F|empty|, id A F->digit|id|char|{ G }|string G->H G' G'->, H G'|empty H->digit|char T->X C X->short|int|long|float|double|char|void|string|boolean C->[ digit ] C|empty S->L = E ;|if B then S else S|while B do S|call id ( Elist ) ;|return E ;E->- E E'|( E ) E'|digit E'|L E'|string E’ E'->+ E E'|* E E'|empty L->id L' L'->[ digit ] L'|empty B->! B B'|( B ) B'|E relop E B'|true B'|false B' B'->or B B'|and B B'|empty relop-><|<=|==|!=|>|>= Elist->E Elist' Elist'->, E Elist'|empty 注：此处用empty代表空 三、系统设计 得分 要求：分为系统概要设计和系统详细设计。 （1） 系统概要设计：给出必要的系统宏观层面设计图，如系统框架图、数据流图、功能模块结构图等以及相应的文字说明。 1）系统的数据流图： 说明 说明：本语法分析器是基于上一个实验词法分析器的基础上，通过在界面写或者是导入源程序，词法分析器将源程序识别的词法单元传递给语法分析器，语法分析器验证这个词法单元组成的串是否可以由源语言的文法生成，能够输出语法分析的结果，文法的first集、follow集和预测分析表，当然也可以以易于理解的方式报告语法错误。 2） 系统框架图 本系统框架主要是三部分，一部分是词法分析，负责识别源程序的词法单元识别，并将其存储，以供语法分析时读取；第二部分是文法分析部分，负责将导入的文法进行分析，得出文法的first集和follow集，以及自动构造出预测分析表，在语法分析时进行查询；第三部分是用户界面，提供源程序输入功能，以及语法分析结果的显示，显示语法分析树，还有first集、follow集和预测分析表的展示。 （2）系统详细设计：对如下工作进行展开描述 核心数据结构的设计 核心数据结构主要有两种: 1) Tuple三元组 为了存储预测分析表，我使用Tuple三元组的数据结构，分别存储产生式的头部，产生式体，输入符号。 2) Stack栈 为了能够在语法分析时根据预测分析表来进行分析，我写了一个CStack的类用来实现栈的数据结构，在进行语法分析时，一个栈用来存储文法符号，一个栈用来存储输入符号，然后根据预测分析表进行语法分析。 主要功能函数说明 主要功能函数: 1) IDContent类： 功能：充当符号表的角色，主要是用来保存关键字，运算符，界符，转义字符等各类单词。 主要函数：bool isConstCh(string str)//判断是否转义字符 bool isLetter_(char c)//判断是否字母或下划线 bool isDigit(char c)//判断是否数字 bool isBlank(char c)// 判断是否是空格、制表符、换行、回车 bool isKeyWord(string str)//判断是否关键字 bool isBoundary(char c)// 判断是否是边界符号 bool isOperator(string ch)//判断是否运算符 2）Identifier类 功能：识别单词的核心类 主要函数：string isID(string str, ref int i)//是否是标识符 string isSixteen(string str, ref int i,out bool right)//是否16进制数 string isEight(string str,ref int i,out bool right)//是否8进制数 string isNumber(string str, ref int i, out bool right)//是否是常数 string isOperator(string str, ref int i, out bool right)//是否是运算符 string isNote(string str, ref int i, out bool right)//是否注释 string isBoundary(string str, ref int i,out bool right)//是否界符 string isChar(string str, ref int i, out bool right)//是否字符常数 3） FirstAndFollow类 功能：得到first集、follow集、select集、预测分析表 public void getFirstCollection()//得到first集合 public void getFollowCollection()//得到follow集合 public void getSelectCollection()//得到预测分析表 public void getAnalysisTable(string str1, string str2, string str3)//得到预测分析表 public void errorHandle()//加入同步词法单元 4） CStack类