编译原理报告(7).docx

华中科技大学计算机学院 编译原理实验报告课 程 实 验 报 告课程名称： 编译原理 专业班级： 信息安全1302 学 号： 姓 名： 指导教师： 报告日期： 2015年11月13日 计算机科学与技术学院目录目录21 实验一 词法分析31.1实验目的31.2实验要求31.3算法思想41.4实验方法与环境51.5词法分析实现61.6词法实验结果及结果分析92 实验二 语法分析112.1 实验目的112.2 实验要求112.3 算法思想112.4 实验程序设计说明142.5 语法分析实现144 实验中遇到的问题及解决21参考资料221 实验一 词法分析1.1 实验目的通过编写和调试一个词法分析程序，掌握在对程序设计语言的源程序进行扫描的过程中，将字符形式的源程序流转化为一个由各类单词符号组成的流的词法分析方法。1.2 实验要求1、待分析的简单的词法（1）关键字： begin if then while do end所有的关键字都是小写。（2）运算符和界符： = + - * / = = = ; ( ) #（3）其他单词是标识符（ID）和整型常数（SUM），通过以下正规式定义：ID = letter (letter | digit)*NUM = digit digit*（4）空格有空白、制表符和换行符组成。空格一般用来分隔ID、SUM、运算符、界符和关键字，词法分析阶段通常被忽略。2、 各种单词符号对应的种别码：表1 各种单词符号对应的种别码单词符号种别码 单词符号种别码bgin1：17If2：=18Then320wile421do523lettet（letter|digit）*10=24dight dight*11=25+13；2614(27*15)28/16#03、 词法分析程序的功能：输入：所给文法的源程序字符串。输出：二元组（syn,token或sum）构成的序列。其中：syn为单词种别码； token为存放的单词自身字符串； sum为整型常数。例如：对源程序begin x:=9: if x9 then x:=2*x+1/3; end #的源文件，经过词法分析后输出如下序列：(1,begin)(10,x)(18,:=)(11,9)(26,;)(2,if)1.3 算法思想算法的基本任务是从字符串表示的源程序中识别出具有独立意义的单词符号，其基本思想是根据扫描到单词符号的第一个字符的种类，拼出相应的单词符号。1、 主程序示意图：主程序示意图如图1所示。其中初始包括以下两个方面： 关键字表的初值。关键字作为特殊标识符处理，把它们预先安排在一张表格中（称为关键字表），当扫描程序识别出标识符时，查关键字表。如能查到匹配的单词，则该单词为关键字，否则为一般标识符。关键字表为一个字符串数组，其描述如下：Char *rwtab6 = “begin”, “if”, “then”, “while”, “do”, “end”,;开始置初值调用扫描子程序输出单词二元组输入串结束?否结束是图1 主程序示意图（2）程序中需要用到的主要变量为syn,token和sum2、 扫描子程序的算法思想：首先设置3个变量：token用来存放构成单词符号的字符串；sum用来整型单词；syn用来存放单词符号的种别码。扫描子程序主要部分流程如图2所示。开始变量初始化忽略空格是否文件结束?否返回是拼数拼字符串字母Syn=11关键字?Syn=10否是Syn为对应关键字的种别码对不同符给出相应的syn值报错其他符号运算符界符等返回数字图2 扫描子程序流程图1.4 实验方法与环境词法分析是编译程序的第一个处理阶段，可以通过两种途径来构造词法分析程序。其一是根据对语言中各类单词的某种描述或定义（如BNF），用手工的方式（例如可用C语言）构造词法分析程序。一般地，可以根据文法或状态转换图构造相应的状态矩阵，该状态矩阵同控制程序便组成了编译器的词法分析程序；也可以根据文法或状态转换图直接编写词法分析程序。构造词法分析程序的另外一种途径是所谓的词法分析程序的自动生成，即首先用正规式对语言中的各类单词符号进行词型描述，并分别指出在识别单词时，词法分析程序所应进行的语义处理工作，然后由一个所谓词法分析程序的构造程序对上述信息进行加工。如美国BELL实验室研制的LEX就是一个被广泛使用的词法分析程序的自动生成工具。总的来说，开发一种新语言时，由于它的单词符号在不停地修改，采用LEX等工具生成的词法分析程序比较易于修改和维护。一旦一种语言确定了，则采用手工编写词法分析程序效率更高。1.5 词法分析实现使用C语言实现：#include #include char prog80,token8,ch;int syn,p,m,n,sum;char *rwtab6=begin,if,then,while,do,end; scaner();main()p=0; printf(n please input a string(end with #):/n); do scanf(%c,&ch); progp+=ch; while(ch!=#); p=0; do scaner(); switch(syn) case 11:printf( %-10d%5d )n,sum,syn); break; case -1:printf(you have input a wrong stringn); getch(); exit(0); default: printf( %-10s%5d )n,token,syn); break; while(syn!=0); getch(); scaner() sum=0; for(m=0;m8;m+)tokenm+=NULL; ch=progp+; m=0; while(ch= )|(ch=n)ch=progp+; if(ch=a)|(ch=A) while(ch=a)|(ch=A)|(ch=0)&(ch=9) tokenm+=ch; ch=progp+; p-; syn=10; for(n=0;n=0)&(ch=0)&(ch=9) sum=sum*10+ch-0; ch=progp+; p-; syn=11; else switch(ch) case :tokenm+=ch; ch=progp+; if(ch=) syn=24; tokenm+=ch; else syn=23; p-; break; case -:tokenm+=ch; ch=progp+; if(ch=-) syn=29; tokenm+=ch; else syn=14; p-; break; case !:ch=progp+; if(ch=) syn=21; tokenm+=ch; else syn=31; p-; break; case =:tokenm+=ch; ch=progp+; if(ch=) syn=25; tokenm+=ch; else syn=18; p-; break; case +: tokenm+=ch; ch=progp+; if(ch=+) syn=17; tokenm+=ch; else syn=13; p-; break; case *: syn=15; tokenm+=ch; break; case /: syn=16; tokenm+=ch; break; case (: syn=27; tokenm+=ch; break; case ): syn=28; tokenm+=ch; break; case : syn=5; tokenm+=ch; break; case : syn=6; tokenm+=ch; break; case ;: syn=26; tokenm+=ch; break; case : syn=30; tokenm+=ch; break; case #: syn=0; tokenm+=ch; break; case :syn=17; tokenm+=ch; break; default: syn=-1; break; tokenm+=0; 1.6 词法实验结果及结果分析输入begin x:=9; if x9 then x:=2*x+1/3; end # 程序输出序列的结果如下图3所示：图3 程序运行结果2 实验二 语法分析2.1 实验目的通过设计、编制、调试一个典型的语法分析程序（任选有代表性的语法分析方法，如算符优先法、递归下降法、LL(1)、SLR(1)、LR(1)等，作为编制语法分析程序的依据），对扫描器所提供的单词序列进行语法检查和结构分析，实现并进一步掌握常用的语法分析方法。2.2 实验要求利用C语言编制递归下降分析程序，并对简单语言进行语法分析。1、 待分析的简单语言的语法用扩充的BNF表示如下：=beginend：=；：=：=ID：=：=+ | -：=* | /：=ID | NUM | （）2、 实验要求说明输入单词串，以“#”结束，如果是文法正确的句子，则输出成功信息，打印“success”，否则输出“error”。例如： 输入 begin a:=9; x:=2*3; b:=a+x end # 输出 success！ 输入 x:=a+b*c end # 输出 error2.3 算法思想（1）主程序示意图如图4所示。图4 语法分析主程序示意图（2）递归下降分析程序示意图如图5所示。（3）语句串分析过程示意图如图6所示。图5 递归下降分析程序示意图 图6语句串分析示意图（4）statement语句分析程序流程如图7,8,9,10所示。 图7 statement语句分析函数示意图 图8 expression表达分析函数示意图图9 term分析函数示意图 图10 factor分析过程示意图2.4 实验程序设计说明1、数据结构的设计本程序中主要功能是完成文法正确性的判断，因此没有特别的需要使用到结构体等数据结构。本程序中主要使用了一个数组rwtab用于存放语法关键字begin,if,then,while,do,end。2、算法设计首先程序读入用户输入的文法语句，然后使用scaner函数进行字符串的分离处理，即读出一个一个单独的字符串，然后使用递归下降的分析方式进行语法分析。2.5 语法分析实现使用C语言实现：#includeusing namespace std;#include#include#define MAX 150 /词法分析表的最大容量#define MAXBUF 255 /缓冲区的最大缓冲量void term();void lrparser();void statement();void yucu();void expression();void factor();char progMAXBUF,tokenMAX; char ch;int syn,p,m,n,sum,kk; char * rwtab6=begin,if,then,while,do,end;/*词法扫描程序：*/void scaner() for(m=0;mMAX;m+) tokenm=NULL; m=0;sum=0; ch=progp+; while(ch= )ch=progp+; if(ch=a)|(ch=A) while(ch=a)|(ch=A)|(ch=0) tokenm+=ch; ch=progp+; /读取下一个字符 tokenm+=0; ch=prog-p; syn=10; for(n=0;n6;n+) if(strcmp(token,rwtabn)=0) syn=n+1; /给出syn值 break; else if(ch=0) sum=0; while(ch=0) sum=sum*10+ch-0; ch=progp+; ch=prog-p; syn=11; else switch(ch) case ) syn=21; tokenm+=ch; else if(ch=) syn=22; tokenm+=ch; else syn=20; ch=prog-p; break; case :tokenm+=ch; ch=progp+; if(ch=) syn=24; tokenm+=ch; else syn=23; ch=prog-p; break; case :tokenm+=ch; ch=progp+; if(ch=) syn=18; tokenm+=ch; else syn=17; ch=prog-p; break; case +:syn=13;token0=ch;break; case -:syn=14;token0=ch;break; case *:syn=15;token0=ch;break; case /:syn=16;token0=ch;break; case :=:syn=18;token0=ch;break; case :syn=21;token0=ch;break; case =:syn=24;token0=ch;break; case =:syn=25;token0=ch;break; case ;:syn=26;token0=ch;break; case (:syn=27;token0=ch;break; case ):syn=28;token0=ch;break; case #:syn=0;token0=ch;break; default:syn=-1; break; /void statement()if (syn=10) scaner(); /读下一个单词符号 if (syn=18) scaner(); /读下一个单词符号expression(); /调用expression函数 else printf(error!); kk=1; else printf(error!); kk=1;return;/void expression()term();while(syn=13 | syn=14) scaner(); term();return;/void term()factor();while(syn=15 | syn=16) scaner(); factor();return;/void lrparser()if (syn=1) /begin scaner(); yucu(); if (syn=6) /end scaner(); if (syn=0 & kk=0) printf(success n); else if(kk!=1) printf(error,lose end ! n); kk=1; else printf(error,lose begin ! n); kk=1; return;/void yucu()statement();while(syn=26) /; scaner(); statement();return;/void factor()if(syn=10 | syn=11) scaner(); /为标识符或整常数时，读下一个单词符号else if(syn=27) scaner(); expression(); if(syn=28) scaner(); else printf( ) 错误n); kk