编译原理报告(9).doc

课 程 设 计 报 告课程名称： 编译原理 专业班级： 信息安全 1302 班 学 号： 姓 名： 指导教师： 报告日期： 2015年11月8日 计算机科学与技术学院目录1实验一 词法分析11.1实验目的11.2实验要求11.3实验原理11.4算法实现11.5测试结果12实验二 语法分析12.1实验目的12.2实验要求12.3实验原理12.4算法实现13总结与体会1I1 实验一 词法分析1.1 实验目的设计、编制并调试一个词法分析程序，加深对词法分析原理的理解。1.2 实验要求1. 待分析的简单语言的词法(1) 关键字begin if then while do end所有的关键字都是小写。(2) 运算符和界符：:= + - * / = = = ； ( ) #(3) 其他单词是标识符（ID）和整形常数（NUM），通过以下正规式定义：ID = letter(letter | digit)*NUM = digit digit*(4) 空格由空白、制表符和换行符组成。空格一般用来分隔ID、NUM、运算符、界符和关键字，词法分析阶段通常被忽略。2. 各种单词符号对应的种别码。单词符号种别码单词符号种别码begin1:17if2:=18then320while421do523letter (letter | digit)*10=24digit digit*11=25+13;26-14(27*15)28/16#03. 词法分析程序的功能输入：所给文法的源程序字符串。输出：二元组（syn, token 或 sum）构成的序列其中：syn为单词种别码；token为存放的单词自身字符串；sum为整形常数。例如：对源程序begin x:=9; if x0 then x:= 2 * x + 1 / 3 ; end #的源文件，经词法分析后输出如下序列：(1,begin)(10,x)(18,:=)(11,9)(26,;)(2,if)1.3 实验原理算法的基本任务是从字符串表示的源程序中识别出具有独立意义的单词符号，其基本思想是根据扫描到单词符号的第一个字符的种类，拼出相应的单词符号。1. 主程序示意图主程序示意图如图 11所示。其中初值包括如下两个方面：（1） 关键字表的初值。关键字作为特殊标识符处理，把他们预先安排在一张表格中（成为关键字表），当扫描程序识别出标识符时，查关键字表。如能查到匹配的单词，则该单词为关键字，否则为一般标识符。关键字表为一个字符串数组，其描述如下。char * rwtab6 = “begin”,”if”,”then”,”while”,”do”,”end”;（2） 程序中需要用到的主变量为syn,token和sum。2. 扫描子程序的算法思想首先设置三个变量：token用来存放构成单词符号的字符串；sum用来存放整形单词；syn用来存放单词符号的种别码。扫描子程序主要部分流程如图 12所示。图 11 此法分析主程序示意图图 12 词法分析程序流程1.4 算法实现在我的程序使用C+语言编制，在其中我使用了类这个工具来封装整个词法分析代码，并且把所有的全局变量都封装到类或者类的功能函数中，这样可以使得程序代码更加有序，简化后续的调试和改进工作。同时，我的词法分析程序将处理的结果放在一个链表中，并且在程序结束后返回链条头。这样设计可以减少后续语法分析程序的编写难度。同时，我的程序还可以检测数字输入错误。如果输入了非法的数字，程序就会提示错误。我的源程序如下：complie_common.h:#ifndef COMPILE_COMMON_H_INCLUDED#define COMPILE_COMMON_H_INCLUDED/词法分析返回的结果链表节点结构typedef struct WORD_ANALY_RESULT_ int syn; char * word; int sum; struct WORD_ANALY_RESULT_ * next, * prev; WORD_ANALY_RESULT;#endif / COMPILE_COMMON_H_INCLUDEDword_analy.h:#ifndef WORD_ANALY_H_INCLUDED#define WORD_ANALY_H_INCLUDED#includecompile_common.h/输入一个以0结尾的源程序字符缓冲区/输出它的词法分析结果，就是一个二元组链表class WordAnalypublic: WordAnaly()=default; WordAnaly();/词法分析功能函数 WORD_ANALY_RESULT * scanner( char * source_buffer );private: char * key_word_map6 = begin, if, then, while, do, end;/可以直接接在数字之后的符号char after_num15 = ; ,-,+,=,/, ,n,r,t,!,:,*,) ;/关键字的个数 int key_word_num = sizeof(this-key_word_map)/sizeof(char *);/为链表节点分配空间 WORD_ANALY_RESULT * AllocMem();/检查字符是否是字母 inline int is_letter( char ch );/检查字符是否是数字 inline int is_number( char ch );/检查字符是否是空白字符 inline int is_blank( char ch );/检查字符串是否是空格 inline int is_space( char ch );#endif / WORD_ANALY_H_INCLUDEDword_analy.cpp:#include#include#include#includeword_analy.hWORD_ANALY_RESULT * WordAnaly:scanner( char * source_buffer)/字符 char token33; /当前处理的源程序的位置int source_buffer_pointer = 0;/当前token字符串的位置 int token_pointer = 0; char temp_ch;/返回的结果链表头及其临时指针 WORD_ANALY_RESULT * pWAR_head, * pWAR_p, * pWAR_q, * pWAR_r; pWAR_head = this-AllocMem(); pWAR_p = pWAR_head; while( 1 ) token_pointer = 0; temp_ch = source_buffersource_buffer_pointer+; while( this-is_blank(temp_ch) temp_ch = source_buffersource_buffer_pointer+; if( this-is_letter(temp_ch) ) while( this-is_letter(temp_ch) | this-is_number(temp_ch) tokentoken_pointer+ = temp_ch; if( token_pointer 32 ) printf(Identifer overflow!n); return NULL; temp_ch = source_buffersource_buffer_pointer+; tokentoken_pointer+ = 0;source_buffer_pointer-; pWAR_p-syn = 10; for( int i = 0;i key_word_num - 1; i +) if( strcmp(key_word_mapi,token) = 0) pWAR_p-syn = i + 1; break; else if( this-is_number(temp_ch) ) while( this-is_number(temp_ch) ) pWAR_p-sum = pWAR_p-sum*10 + temp_ch - 0; temp_ch = source_buffersource_buffer_pointer+; pWAR_p-syn = -22; for( int i = 0;i after_numi) pWAR_p-syn = 11; break; /如果数字后面跟了非法字符，就报错 if(pWAR_p-syn = -22 ) printf(Identifier error!n); return NULL; source_buffer_pointer -; else switch(temp_ch) case ) pWAR_p-syn = 21; tokentoken_pointer+ = temp_ch;tokentoken_pointer+ = 0; else if( temp_ch = = ) pWAR_p-syn = 22; tokentoken_pointer+ = temp_ch;tokentoken_pointer+ = 0; else pWAR_p-syn = 20; source_buffer_pointer-; break; case : tokentoken_pointer+ = temp_ch; temp_ch = source_buffersource_buffer_pointer+; if( temp_ch= = ) pWAR_p-syn = 24; tokentoken_pointer+ = temp_ch;tokentoken_pointer+ = 0; else pWAR_p-syn = 23; source_buffer_pointer-; break; case : tokentoken_pointer+ = temp_ch; temp_ch = source_buffersource_buffer_pointer+; if( temp_ch = = ) pWAR_p-syn = 18; tokentoken_pointer+ = temp_ch;tokentoken_pointer+ = 0; else pWAR_p-syn = 17; source_buffer_pointer-; break; case +: pWAR_p-syn = 13; token0 = temp_ch;token1 = 0; break; case -: pWAR_p-syn = 14; token0 = temp_ch;token1 = 0; break; case *: pWAR_p-syn = 15; token0 = temp_ch;token1 = 0; break; case /: pWAR_p-syn = 16; token0 = temp_ch;token1 = 0; break; case ;: pWAR_p-syn = 26; token0 = temp_ch;token1 = 0; break; case (: pWAR_p-syn = 27; token0 = temp_ch;token1 = 0; break; case ): pWAR_p-syn = 28; token0 = temp_ch;token1 = 0; break; case #: pWAR_p-syn = 0; token0 = temp_ch;token1 = 0; break; default: pWAR_p-syn = -1; pWAR_p-word = (char*)calloc(sizeof(char), token_pointer + 4); strcpy(pWAR_p-word, token); pWAR_q = this-AllocMem(); pWAR_p-next = pWAR_q; pWAR_q-prev = pWAR_p; pWAR_p = pWAR_q;/遇到结束符#就退出 if ( pWAR_p-prev-syn = 0) break; pWAR_p-prev-next = NULL; free(pWAR_p); return pWAR_head;WORD_ANALY_RESULT * WordAnaly:AllocMem() return (WORD_ANALY_RESULT *)calloc(sizeof(WORD_ANALY_RESULT),1);int WordAnaly:is_letter( char ch ) return (ch = a & ch = A & ch = 0) & (ch = 9);int WordAnaly:is_blank( char ch ) return (ch = ) | (ch = n) | (ch = r);int WordAnaly:is_space( char ch) return (ch = );main.cpp:#include#includeword_analy.hint main() char buffer300; int p = 0; char ch; WORD_ANALY_RESULT * result; WordAnaly * pWordAnaly = new WordAnaly(); printf(n please input string : n);/读入源程序 do bufferp+ = ch = getchar(); while( ch != # );/获取结果链表 result = pWordAnaly-scanner(buffer); /输出结果while( result ) if( result-syn = 11) printf(%d, %d)n, result-syn, result-sum); else if( result-syn = -1) printf(Errorn);else if (result-syn = -2)printf(Identifier errorn);result = result-next; else printf(%d, %s)n, result-syn, result-word); result = result-next; return 0;1.5 测试结果首先我输入书上的测试用例，其结果如图所示：图 13 书上的测试用例运行结果接着我故意将数字后面直接与字母相连，测试一下程序的错误处理能力。图 14 输错数字后程序的操作可见程序可以正确处理标识符错误的情况。此时，我再输入一些非法字符，看一看程序的处理能力。图 15 输入非法字符后程序的操作由上述示例可以看到，程序实现了预定的功能，也可以对一些特定的错误进行处理，可以说这个程序的编制是成功的。2 实验二 语法分析2.1 实验目的编制一个递归下降分析程序，实现对词法分析程序所提供的单词序列的语法检查和结构分析。2.2 实验要求利用C语言编制递归下降分析程序，并对简单语言进行语法分析。1. 待分析的简单语言的语法用扩充的BNF表示如下：（1） := begin end（2） := ; （3） := （4） := ID := （5） := + | -（6） := * | /（7） := ID | NUM | ()2. 实验要求说明输入单词串，以“#”结束，如果是文法正确的句子，则输出成功信息，打印“success”，否则输出“error”。例如：输入 begin a:=9; x:=2*3; b:=a+x end #输出 success输入 x:=a+b*c end #输出 error2.3 实验原理 (1) 主程序示意图如图 21所示。(2) 递归下降分析程序示意图如所示。(3) 语句串分析过程示意图如所示。(4) 表达式语句分析函数流程如所示。图 21语法分析主程序示意图图 22 递归下降分析程序示意图图 23 语句串分析示意图图 24 statement语句分析函数示意图图 25 expression表达式分析函数示意图图 26 term分析函数示意图图 27 factor分析过程示意图2.4 算法实现同词法分析程序一样，本程序也是使用C+语言，并借助了类这个工具来编写的。并且，它的输入就是我的词法分析程序输出的链表。同时，我在实际的编程工作中，对于出错的判断并没有使用变量kk，而是直接通过各个函数的返回值来进行判断。一旦某个函数返回0，就说明语法分析过程出错，则工作停止并输出错误。并且，由于本次实验所用的词法分析函数就是在前面介绍的，而且前面也已经展示了代码，因此，下面我将仅展示我的语法分析函数的代码。grammar_analy.h:#includeword_analy.h#includecompile_common.hclass GrammerAnalypublic:GrammerAnaly() = default;int grammer_analy(WORD_ANALY_RESULT * head) this-pWordAnalyResult = head; return lrparser(); private:WORD_ANALY_RESULT * pWordAnalyResult;int scanner();int lrparser();/语句串分析int word_string();/赋值语句分析int statement();/表达式分析int expression();/项分析int term();/因子分析int factor();#endifgrammar_analy.cpp:#include#includegrammer_analy.hint GrammerAnaly:scanner()this-pWordAnalyResult = this-pWordAnalyResult-next;if (this-pWordAnalyResult = NULL)return 0;return 1;int GrammerAnaly:lrparser()if (this-pWordAnalyResult = NULL)return 0;/当前符号是否为beginif (this-pWordAnalyResult-syn = 1)if (!this-scanner()return 0;if (this-word_string() = 0)return 0;/当前符号是否为endif (this-pWordAnalyResult-syn = 6)if (!this-scanner()return 0;/当前符号是否为#if (this-pWordAnalyResult-syn = 0)return 1;elseprintf(缺少endn);elseprintf(缺少beginn);return 0;int GrammerAnaly:word_string()if (this-statement() = 0)return 0;/当前符号是否为；while (this-pWordAnalyResult-syn = 26)if (!this-scanner()return 0;if (this-statement() = 0)return 0;return 1;int GrammerAnaly:statement()/当前符号是否为变量名if (this-pWordAnalyResult-syn = 10)if (!this-scanner()return 0;/当前符号是否为赋值号if (this-pWordAnalyResult-syn = 18)if (!this-scanner()return 0;if (this-expression() = 0)return 0;elseprintf(语句错误n);return 0;return 1;int GrammerAnaly:expression()if (this-term() = 0)return 0;/当前符号是否为加号或减号while (this-pWordAnalyResult-syn = 13 | this-pWordAnalyResult-syn = 14)if (!this-scanner()return 0;if (this-term() = 0)return 0;return 1;int GrammerAnaly:term()if (this-factor() = 0)return 0;/当前符号是否为乘号或除号while (this-pWordAnalyResult-syn = 15 | this-pWordAnalyResult-syn = 16)if (!this-scanner()return 0;if (this-factor() = 0)return 0;return 1;int GrammerAnaly:factor()/当前符号是否为变量名或整形数字if (this-pWordAnalyResult-syn = 10 | this-pWordAnalyResult-syn = 11)if (!this-scanner()return 0;/当前符号是否为左括号else if (this-pWordAnalyResult-syn = 27)if (!this-scanner()return 0;if (this-expression() = 0)return 0;/当前符号是否为右括号if (this-pWordAnalyResult-syn = 28)if (!this-scanner()return 0;elseprintf(缺少)错误n);return 0;elseprintf(表达式错误n);return 0;return 1;main.cpp:#include#includeword_analy.h#includegrammer_analy.hint main() char buffer300; int p = 0; char ch; WORD_ANALY_RESULT * result; WordAnaly * pWordAnaly = new WordAnaly();GrammerAnaly * pGrammerAnaly = new GrammerAnaly(); printf(n please input string : n); do bufferp+ = ch = getchar(); while( ch != # );/获取此法分析结果 result = pWordAnaly-scanner(buffer);if (pGrammerAnaly-grammer_analy(result) = 1)printf(Success!n);elseprintf(Error!n);return 0;2.5 测试结果我先用书上的两个例子源程序进行了测试，结果如下：图 28 书上测试用例1运行结果图 29 书上测试用例2运行结果由书上的两个例子的运行结果可以看出来，程序目前可以对正