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

编译原理实验报告二、 语法分析(一) 实验题目编写程序，实现对词法分析程序所提供的单词序列进行语法检查和结构分析。(二) 实验内容和要求1. 要求程序至少能分析的语言的内容有：1) 变量说明语句2) 赋值语句3) 条件转移语句4) 表达式（算术表达式和逻辑表达式）5) 循环语句6) 过程调用语句2. 此外要处理：包括依据文法对句子进行分析;出错处理;输出结果的构造。3. 输入输出的格式：输入：单词文件（词法分析的结果）输出：语法成分列表或语法树（都用文件表示），错误文件（对于不合文法的句子）。4. 实现方法：可以采用递归下降分析法，LL（1）分析法，算符优先法或LR分析法的任何一种，也可以针对不同的句子采用不同的分析方法。(三) 实验分析与设计过程1. 待分析的C语言子集的语法：该语法为一个缩减了的C语言文法，估计是整个C语言所有文法的60%（各种关键字的定义都和词法分析中的一样），具体的文法如下：语法:100: program - declaration_list101: declaration_list - declaration_list declaration | declaration102: declaration - var_declaration|fun_declaration103: var_declaration - type_specifier ID;|type_specifier IDNUM;104: type_specifier - int|void|float|char|long|double|105: fun_declaration - type_specifier ID (params)|compound_stmt106: params - params_list|void107: param_list -param_list,param|param108: param - type-spectifier ID|type_specifier ID109: compound_stmt - local_declarations statement_list110: local_declarations - local_declarations var_declaration|empty111: statement_list - statement_list statement|empty112: statement - epresion_stmt|compound_stmt|selection_stmt|iteration_stmt|return_stmt113: expression_stmt - expression;|;114: selection_stmt - ifexpression)statement|if(expression)statement else statement115: iteration_stmt - whileexpression)statement116: return_stmt - return;|return expression;117: expression - var = expression|simple-expression118: var - ID |IDexpression119: simple_expression - additive_expression relop additive_expression|additive_expression120: relop - =|=|= =|!=121: additive_expression - additive_expression addop term | term122: addop - + | -123: term - term mulop factor | factor124: mulop - *|/125: factor - (expression)|var|call|NUM126: call - ID(args)127: args - arg_list|empty128: arg_list - arg_list,expression|expression该文法满足了实验的要求，而且多了很多的内容，相当于一个小型的文法说明：把文法标号从100到128是为了程序中便于找到原来的文法。2. 实现方法的选择：因为时间的问题，我选择了递归下降的方法进行开发。3. 消除左递归 因为递归下降要求文法中不能出现有左递归的产生式，因此必须把待分析的C语言子集的语法中带有左递归的都消除左递归。其中产生式101、110、111、121、123、128均为左递归文法。 这些产生式消除左递归后的文法如下：1）101消除左递归后的产生式分别为：101: declaration_list - declaration declaration_list_zdg135: declaration_list_zdg- declaration declaration_list_zdg|empty2）110消除左递归后的产生式分别为：110: local_declarations - empty local_declarations_zdg 133: local_declarations_zdg- var_declarationlocal_declarations_zdg|empty3）111消除左递归后的产生式分别为：111: statement_list- empty statement_list_zdg134: statement_list_zdg-statement statement_list_zdg|empty4）121消除左递归后的产生式分别为：121: additive_expression - term additive_expression_zdg131: additive_expression_zdg- addop term additive_expression_zdg|empty5）123消除左递归后的产生式分别为：123: term - factor term_zdg132: term_zdg- mulop factor term_zdg|empy6）128消除左递归后的产生式分别为：128:arg_list-expression arg_list_zdg129:arg_list_zdg-,expression arg_list_zdg|empty说明：empty代表可以为空。4. 词法分析和语法分析的关系由于语法分析要用到词法分析的结果，在词法分析中，我逐个得到单词，而语法分析的整个过程中都必须利用从词法分析中得到的每一个单词，因此从语法分析的入口点开始就必须利用token读取源C程序的第一个词，然后再语法分析的过程中，采取相关的措施，在匹配当前单词后继续利用token读取下一个单词。5. 递归下降的思想 递归下降的思想在于“递归”二字，对于每一个消除了左递归的产生式，通过为每一个产生式建立一个函数，函数名为相应的产生式的左部，然后对产生式的每一项进行展开，如果产生式的右部碰到一个非终结符，则调用这个非终结符的函数（该非终结符肯定是一个产生式的左部，为之建立一个函数），如果遇到的是一个非终结符，则调用match（）方法（见下文），match方法除了匹配当前的非终结符之外，还调用了词法分析的token方法，读取下一个单词。这里举一个例子来说明：下面的产生式是一个关于变量定义的产生式：var_declaration - type_specifier ID;来说，编写的函数名为var_declaration的方法：简单的表达如下：public void var_declaration（）type_specifier（）；ID（）；match（SEMICOLON）；/ SEMICOLON表示分号其他的产生式的函数编写都跟这个var_declaration函数类似。只是，但是还有的产生式有比这复杂的地方，在后面继续说明。6. 结果输出形式和错误处理 1)结果的输出形式当碰到一个单词，我首先输出这个单词的类型，因为用到的是递归函数，对于每个产生式，当展开到产生式的末尾的时候，我就把反映该产生式的源代码（规约）都输出，当最后到达产生是式program(即分析出了是一个程序)，便输出整个程序，因此这种方法是一个反映了我语法分析过程的结果输出。当遇到一个单词或者遇到了一个产生式的规约，便输出结果，方法为：public void syntaxPrint(String message, String blk, int n)其中参数 message为：当当前的输出为当前单词时，message为当前的词类型，当当前的输出为一个产生式的规约时，message为当前用于规约的产生式。参数 blk是为了方便结果输出的时候，在程序中间加上必要的空格。参数n表示当前用于规约的产生式的项的个数，当知道个数后，便与把保存在栈顶的n个元素连接起来并且输出。2）错误处理因为语法分析的时候，源程序有很多的不符合语法的地方，因此就需要处理，更重要的是需要进行错误恢复，以便语法分析输出当前的错误后继续正确地进行分析。这里我采用了栈的形式来进行错误恢复（见数据结构设计与建立）7. 数据结构（栈）这里用到了栈，栈的运用在这里主要就是用于结果的输出和错误处理。当分析一个产生式的时候，如果发现当前的字符匹配，则把当前的字符压入栈中，或者当前的不是一个字符，而是一个非终结符（一个函数），则因为该函数也进行了相应的处理，当函数结束的时候把一个字符串压在栈中，因此直接调用这个函数的时候已经实现了压栈的动作，然后在输出该非终结符所表示的源程序的时候，把在该非终结符的函数中压入栈中的内容合并成一个字符串输出后再压回栈顶。实现了递归调用。如果在该非终结符的函数展开过程中，出现的错误，也即当前的字符并不是产生式所需要的，那么便往栈中压入一个空字符，即做了错误恢复，从而继续进行分析。个人感觉利用栈让我很好地解决了分析结果的输出和错误处理恢复。8. 产生式函数的流程图这个问题是我在语法分析中遇到的比较棘手的几个问题之一，主要分成以下的几种情况。1）产生式的右部只有一种情况，如产生式102、126等 以126: call - ID(args)为例，说明我处理这种情况的处理方法：因为产生式有右部的First集为ID（即标识符），的程序流程图，见下面的流程图（3） 流程图（3）2） 产生式的右部有两个或者两个以上的规约产生式，但是右部的这两个或者两个以上的产生式的First集并不相同，如产生式112、113等，其中还有复杂一点的情况，因为有的产生式的右部的First有很多，或者是First集的寻找比较困难，需要找到很多的产生式，这个属于First集的寻找，在这里就不详细描述了。 我以产生式112 statement -expression_stmt|compound_stmt|selection_stmt |iteration_stmt|return_stmt为例来说明处理这种情况的产生式的方法，其中iteration_stmt的First集为WHILE，selection_stmt的First集为if，return_stmt的First集为RETURN，compound_stmt 的First集为LH，expression_stmt|的First集为LB、SEMICOLON和ID，详细的流程图见下图 流程图（4）流程图（4）3）产生式的右部有两个或者两个以上的规约产生式，但是右部的这两个或者两个以上的产生式的First集的第一个或者前几个都相同，如产生式103、108、116等，则在这种情况下，就不像前两种情况那么简单了，因为知道了当前的单词并不能知道到底使用哪个产生式来进行规约，因此当当前字符相同的时候，需要读下一个字符，如果下一个字符仍然相等，则继续往下读取，一直到遇到的字符可以区分是使用哪个产生式为止。在这种情况下，就需要在第一个字符的时候，记住当前的字符的位置，以便在判断知道是使用哪个产生式的时候可以回退到函数刚开始的字符的位置，进而用正确的产生式进行展开。下面以产生式116116: return_stmt - return;|return expression;为例来说明这种情况的产生式的处理方法，因为产生式右部的两个产生式的First集都为return，因此先记录当前的状态，判断下一个词，如果为分号，则用左边的产生式，如果为ID、NUMBER 或LB（expression的First集为ID、NUMBER 或LB）则回退到当前字符为return的状态，用产生式：return_stmt -return expression;详细的分析见流程图（5）流程图（5） 4）关于产生式中的empty的处理消除了左递归之后的那些产生式中都有empty的现，empty代表可以为空。因此在这种情况下，就往栈中压入一个空字符：this.mystack.push();5）其他的各种情况都在上述的几种情况之中，大同小异因此这里不再赘述。9. 语法分析的流程图 在把所有的产生式的函数都写好后，语法分析的过程就变得很简单了，因为程序的入口点就是函数program(),只要用token为其读取第一个单词即可进行以后的分析，以后的分析中在其他的各个函数中实现了单词的读取和结果的输出以及错误的恢复处理等。流程图见流程图（6）。流程图（6）(四) 实验编写代码和测试1. 代码的编写，由于递归的实现就是为每个函数建立一个函数，对不同的产生式类型用不同的方法进行编写，但由于逻辑的判断和转换比较多，因此很容易出错和导致思维的混乱。 由于用到的栈处理比较多，因此对栈的使用前先做了不少的测试。2. 程序的测试用例和结果输出，以及相应的错误恢复与错误显示。1) 正确的测试用例以及结果测试用例：void main(void)/*主函数*/ int ss32; if(a = b) return a; else return b; while (a = b) a=b+a;结果显示：分析结果显示type_specifiervoidvoidparams-voidvoidtype_specifierintintvar_declaration -type_specifier IDNUM;int ss 32 ; local_declarations_zdg- var_declaration local_declarations_zdg|emptyint ss 32 ; factor-varaterm - factor term_zdga additive_expression - term additive_expression_zdga factor-varbterm - factor term_zdgb additive_expression - term additive_expression_zdgb simple_expression - additive_expression relop additive_expressiona = b expression -simple_expressiona = b factor-varaterm - factor term_zdga additive_expression - term additive_expression_zdga simple_expression - additive_expressiona expression -simple_expressiona return_stmt - return expression;return a ; statement - return_stmt return a ; selection_stmt - if(expression)statementif(a = b )return a; statement - selection_stmt if(a= b)return a ; factor-varaterm - factor term_zdga additive_expression - term additive_expression_zdga factor-varbterm - factor term_zdgb additive_expression - term additive_expression_zdgb simple_expression - additive_expression relop additive_expressiona = b expression -simple_expressiona = b factor-varbterm - factor term_zdgb addop-+factor-varaterm - factor term_zdga additive_expression_zdg- addop term additive_expression_zdg|empty+a additive_expression - term additive_expression_zdgb + a simple_expression - additive_expressionb + a expression -simple_expressionb + a expression - var = expressiona=b + a expression_stmt - expression;a=b + a ;statement - epresion_stmt a=b + a ;iteration_stmt - while(expression)statementwhile ( a = b ) a=b + a ; statement - iteration_stmt while ( a = b ) a=b + a ; statement_list_zdg-statement statement_list_zdg|emptywhile ( a = b ) a=b + a ; statement_list_zdg-statement statement_list_zdg|emptyif(a = b )return a ; while ( a = b ) a=b + a ; statement_list- statement_list_zdgif(a = b )return a ; while ( a = b ) a=b + a ; compound_stmt - local_declarations statement_list int ss 32 ; if(a = b )return a ; while ( a = b ) a=b + a ; declaration - fun_declarationvoid main ( ) ) int ss 32 ; if(a = b )return a ; while ( a = b ) a=b + a ; declaration_list -declarations declaration_list_zdgvoid main ( ) ) int ss 32 ; if(a = b )return a ; while ( a = b ) a=b + a ; program - declaration_listvoid main ( ) ) int ss 32 ; if(a = b )return a ; while ( a = b ) a=b + a ; expression_stmt - expression;a=b + a ;statement - epresion_stmt a=b + a ;iteration_stmt - while(expression)statementwhile (a= b) a=b + a ; statement - iteration_stmt while ( a= b) a=b + a; statement_list_zdg-statement statement_list_zdg|empty while(a = b ) a=b + a ; statement_list_zdg-statement statement_list_zdg|emptyif(a=b)return a;while ( a= b) a=b+ a ; statement_list- statement_list_zdgif(a=b)return a; while(a= b) a=b+ a; compound_stmt - local_declarations statement_list int ss 32 ; if(a= b)r