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

编译原理实验报告实验名称：编写语法分析程序实验类型：设计性实验指导教师：蒋勇专业班级：软件工程1401姓名：****学号：**********实验地点：东六E座301实验成绩：_________________日期：2016年5月17日实验一编写词法分析程序一、实验目的：1.设计、编写、调试一个递归下降分析程序，实现对词法分析程序提供的单词序列进行语法检查和结构分析。2.掌握递归下降语法分析方法。3.巩固理论知识。二、实验设计：1.设计原理：1)对于文法的每一个非终结符U的文法规则是一个识别U的过程定义，为每一个非终结符构造子程序。2)如果U的右部符号串只有一个候选式则从左到右依次构造U的识别代码。3)如果U的右部符号串有终结符号，则判断输入的符号是否匹配终结符号，如果相等，则读入下一个符号；如果不相等，则有语法错误，应当报错。4)如果是非终结符号，则调用非终结符号的子程序即可。5)如果U的右部有多个候选式，应该根据每个候选式的第一个符号来确定该分支。6)对于含有ε表达式的文法规则需要判断输入的符号是否在U的FOLLOW集里面。2.设计方法：(1)文法改造，消除二义性；(2)对含有左递归或者左公因子的文法消除左递归，提取左公因子；(3)求每一个右部符号串的FIRST集合，如果右部含有ε，则需要求出其产生式左部非终结符的FOLLOW集。判断文法是否是LL（1）文法，若不是LL(1)文法，说明文法的复杂性超过自顶向下方法的分析能力。(4)根据改写后的文法设计程序，依据设计原理构造每一个非终结符的子程序。3.设计过程：(1)改写文法、消除左递归（将左递归改为右递归）、提取左公因子；(2)求出相应的First集和Follow集；(3)设计程序流程图，设计程序；(4)编写程序；4.框架思路，错误信息输出：对每一个非终结符构造其子程序，设定一个返回值。如果语法分析有错则返回1，没有错误就返回0；对于错误，在程序的相应行数报错。各个非终结符之间依据文法规则调用。每次遇到终结符函数都判断是否匹配当前终结符号，如果不匹配则报错，返回1。如果匹配，则读入下一个符号。三、实验过程(一)本次实验的TEST语言语法规则：1)program→{declaration_liststatement_list}2)declaration_list→declaration_listdeclaration_stat|ε3)declaration_stat→intID;4)statement_list→statement_liststatement|ε5)statement→if_stat|while_stat|for_stat|read_stat|write_stat|compound_stat|expression_stat6)if_stat→if(expr)statement|if(expr)statementelsestatement7)while_stat→while(expression)statement8)for_stat→for(expression;expression;expression)statement9)write_stat→writeexpression;10)read_stat→readID;11)compound_stat→{statement_list}12)expression_stat→expression;|;13)expression→ID=bool_expr|bool_expr14)bool_expr→additive_expr|additive_expr(||=|=|==|!=)additive_expr15)additive_expr→additive_expr+term|additive_expr-term|term16)term→term*factor|term/factor|factor17)factor→(expression)|ID|NUM1.将左递归改为右递归：2)declaration_list→declaration_listdeclaration_stat|ε改写后：declaration_list::=declaration_list1declaration_list1:=declaration_statdeclaration_list1|ε4)statement_list→statement_liststatement|ε改写后：statement_list::=statement_list1statement_list1::=statementstatement_list1|ε15)additive_expr→additive_expr+term|additive_expr-term|term改写后：additive_expr::=termadditive_expr1additive_expr::=+termadditive_expr1|-termadditive_expr1|ε16)term→term*factor|term/factor|factor改写后：term::=factorterm1term1::=*factorterm1|/factorterm1|ε2.提取公因式：14)bool_expr→additive_expr|additive_expr(||=|=|==|!=)additive_expr改写后：bool_expr::=additive_exprbool_expr1bool_expr1::=ε|(||=|=|==|!=)additive_expr3.是否可以提取公因式6)if_stat→if(expr)statement|if(expr)statementelsestatement不可以提取公因式，if语句和if…else语句是相互独立的,并没有必然的联系。4．规则13超前读入符号解决方案：如果识别出标识符的符号ID后，在读入一个符号，如果这个符号时=，说明选择的是赋值表达式，如果不是=，则说明选择是布尔表达式。(二)、求出右部符号串的FIRST集和含有ε产生式的左部非终结符的FOLLOW集1)program→{declaration_liststatement_list}FIRST({declaration_liststatement_list})={{};2)declaration_list::=declaration_list1declaration_list1:=declaration_statdeclaration_list1|εFIRST(declaration_list1)={int,ε};FIRST(declaration_statdeclaration_list1)={int};FOLLOW(declaration_list1)={if,while,for,read,write,{,},;,ID,(,NUM};3)declaration_stat→intID;FIRST(intID;)={int};4)statement_list::=statement_list1statement_list1::=statementstatement_list1|εFIRST(statement_list1)={if,while,for,read,write,{,;,ID,NUM,(};FIRST(statementstatement_list1)={if,while,for,read,write,{,;,ID,NUM,(};FOLLOW(statement_list1)={}};5)statement→if_stat|while_stat|for_stat|read_stat|write_stat|compound_stat|expression_statFIRST(if_stat)={if};FIRST(while_stat)={while}FIRST(for_stat)={for}FIRST(read_stat)={read};FIRST(write_stat)={write}FIRST(compound_stat)={{}FIRST(expression_stat)={ID,NUM,;,(}6)if_stat→if(expr)statement|if(expr)statementelsestatementFIRST(if(expr)statement)={if}FIRST(if(expr)statementelsestatement)={if}7)while_stat→while(expression)statementFIRST(while(expression)statement)={while}8)for_stat→for(expression;expression;expression)statementFIRST(for(expression;expression;expression)statement={for}9)write_stat→writeexpression;FIRST(writeexpression;)={write}10)read_stat→readID;FIRST(readID;)={read}11)compound_stat→{statement_list}FIRST({statement_list})={{}12)expression_stat→expression;|;FIRST(expression;)={(,ID,NUM};FIRST(;)={;};13)expression→ID=bool_expr|bool_exprFIRST(ID=bool_expr)={ID};FIRST(bool_expr)={ID,NUM,(};14)bool_expr→additive_expr|additive_expr(||=|=|==|!=)additive_exprbool_expr::=additive_exprbool_expr1bool_expr1::=ε|(||=|=|==|!=)additive_exprFIRST(additive_exprbool_expr1)={（，ID，NUM}FIRST((||=|=|==|!=)additive_expr)={,,=,=,==,!=}FOLLOW(bool_expr1)={),;}15)additive_expr→additive_expr+term|additive_expr-term|termadditive_expr::=termadditive_expr1additive_expr1::=+termadditive_expr1|-termadditive_expr1|εFIRST(termadditive_e