编译原理实验报告(共14页).doc

精选优质文档-倾情为你奉上编译方法实验报告实验1：扫描器的设计一、 实验目的熟悉并实现一个扫描器（词法分析程序）。二、 实验要求(1) 设计扫描器的有限自动机（识别器）；(2) 设计翻译、生成Token的算法（翻译器）；(3) 编写代码并上机调试运行通过。·输入源程序文件或源程序字符串；·输出相应的Token序列；关键字表和界符表；符号表和常数表；三、 实验步骤流程：初始化；打开用户源程序文件； while （文件未结束） 读入一行到wi，i=0;do /处理一行，每次处理一个单词 滤空格，直到第一个非空的wi；i-；s=1; /处理一个单词开始while （s!=0） /拼单词并生成相应Token act(s); /执行qs if （s>=11 && s<=14） /一个单词处理结束 break; i+; /getchar() s=find(s, wi);if （s=0） 词法错误； while （wi!=换行符）；关闭用户源程序文件；生成Token文件；输出关键字表；输出Token序列；输出符号表；输出常数表；有限自动机的状态转换图： e d d d +|- -1/+/-11+ d . d e d d - -1/+/- l/d -1/+/-12 -1l -13 -1 b b - 14 -1 - 15 -1 -其中：d为数字，l为字母，b为界符，-1代表其它符号（如在状态8处遇到了非字母或数字的其它符号，会变换到状态12）。关键字表和界符表： Program ; Begin : End ( Var ) While , Do := Repeat + Until - For * To / If > Then >= Else = < <=四、 主要数据结构状态转换矩阵：int aut107= 2, 0, 0, 0, 8, 9, 15, 2, 3, 5,11, 0, 0, 11, 4, 0, 0, 0, 0, 0, 0, 4, 0, 5,11, 0, 0, 11, 7, 0, 0, 6, 0, 0, 0, 7, 0, 0, 0, 0, 0, 0, 7, 0, 0,11, 0, 0, 11, 8, 0, 0, 0, 8, 0, 12, 0, 0, 0, 0, 0, 10, 14,0, 0, 0, 0, 0, 0, 13;关键字表：char keywords3012=“program”,”begin”,”end”,”var”,”while”,”do”, ”repeat”,”until”,”for”,”to”,”if”,”then”,”else”, “;”, ”:”, ”(“, ”)”, ”,”, ”:=”, ”+”, ”-“, ”*”, ”/”,”>”, ”>=”, ”=”, “<”, “<=”;符号表：char ID5012; /表中存有源程序中的标识符常数表：float C20;其它变量： struct token int code; int value; /Token结构 struct token tok100; /Token数组 int s; /当前状态 int n,p,m,e,t; /尾数值，指数值，小数位数，指数符号，类型 float num; /常数值char w50; /源程序缓冲区int i; /源程序指针,当前字符为wichar strTOKEN12; /当前已经识别出的单词五、 实验核心代码int main(int argc, char* argv) FILE *fp; int s; /当前状态 *有限自动机中的状态fp=fopen("exa.txt","r"); while (!feof(fp)fgets(w,50,fp);i=0;/*处理一行doprintf("%c ",wi); /测试 显示每个token的首字母/*处理一个tokenwhile (wi=' ') /滤空格i+;if (wi>='a' && wi<='z') /判定单词类别 *是字母（关键字或标识符）ptr=col2; num_map=2;else if (wi>='0' && wi<='9') /*是数字（常量的开头）ptr=col1; num_map=4;else if (strchr(col30.str,wi)=NULL) /*其他字符 算为非法字符printf("非法字符%cn",wi);i+;continue;else /界符ptr=col3; num_map=1;i-; /*向后退一个字符s=1; /开始处理一个单词while (s!=0) act(s); if (s>=11 && s<=14) /*判断是否是终止状态 *是终止状态，则形成一个tokenbreak;i+; /getchar() *读取下一个字符 s=find(s,wi); /状态转换if (s=0)strTOKENi_str='0'printf("词法错误：%sn",strTOKEN);while (wi!=10); printf("关键字表："); /输出结果for (i=0;i<30;i+)printf("%s ",keywordsi);printf("n"); printf("Token序列：");for (i=0;i<num_token;i+)printf("(%d,%d)",toki.code,toki.value);printf("n");printf("符号表：");for (i=0;i<num_ID;i+)printf("%s ",IDi);printf("n");printf("常数表：");for (i=0;i<num_C;i+)printf("%d ",Ci);printf("n");fclose(fp);printf("Hello World!n");return 0;/*状态转换后，达到新的状态之后，记录的变化void act(int s)int code;switch (s)case 1:n=0;m=0;p=0;t=0;e=1;num=0;i_str=0; strTOKENi_str='0' /其它变量初始化 break; case 2:n=10*n+wi-48; break; case 3:t=1; break; case 4:n=10*n+wi-48; m+; break; case 5:t=1; break; case 6:if (wi='-') e=-1; break; case 7:p=10*p+wi-48; break; case 8:strTOKENi_str+=wi; /将ch中的符号拼接到strTOKEN的尾部； break; case 9:strTOKENi_str+=wi; /将ch中的符号拼接到strTOKEN的尾部； break;case 10:strTOKENi_str+=wi; /将ch中的符号拼接到strTOKEN的尾部； break; case 11:num=n*pow(10,e*p-m); /计算常数值 toki_token.code=2; toki_token+.value=InsertConst(num); /生成常数Token num_token+;break;case 12:strTOKENi_str='0' code=Reserve(strTOKEN); /查关键字表 if (code) toki_token.code=code; toki_token+.value=0; /生成关键字Tokenelse toki_token.code=1; toki_token+.value=InsertID(strTOKEN); /生成标识符Token num_token+;break; case 13:strTOKENi_str='0' code=Reserve(strTOKEN); /查界符表 if (code) toki_token.code=code; toki_token+.value=0; /生成界符Token else strTOKENstrlen(strTOKEN)-1='0' /单界符 i-; code=Reserve(strTOKEN); /查界符表 toki_token.code=code; toki_token+.value=0; /生成界符Tokennum_token+;break; case 14:strTOKENi_str='0' code=Reserve(strTOKEN); /查界符表 toki_token.code=code; toki_token+.value=0; /生成界符Tokennum_token+;break;/*状态转换int find(int s,char ch)int i,col=7; struct map *p;p=ptr;for (i=0;i<num_map;i+)if (strchr(p+i)->str,ch)col=(p+i)->col;break;return autscol;/*向常量表中插入常量int InsertConst(double num)int i;for (i=0;i<num_C;i+)if (num=Ci)return i;Ci= (int)num;num_C+;return i;int Reserve(char *str)int i;for (i=0;i<num_key;i+)if (!strcmp(keywordsi,str)return (i+3);return 0;/*向符号表中插入新的符号int InsertID(char *str)int i; for (i=0;i<num_ID;i+)if (!strcmp(IDi,str) /*符号已经存在，则返回地址return i;strcpy(IDi,str);num_ID+;return i;六、 实验结果实验思考题：1.扫描器的任务是什么？答：词法分析程序又称扫描器，任务有：(1) 识别单词 从用户的源程序中把单词分离出来;(2) 翻译单词 把单词转换成机内表示，便于后续处理。2.扫描器、识别器、翻译器三者之间的关系是怎样的？答：扫描器、识别器、翻译器三者之间的关系是： 扫描器的实现要通过识别器和翻译器1. 为什么说有限自动机是词法分析的基础？答：因为词法分析的包括：识别- 识别单词的有限自动机。和翻译- 根据有限自动机所识别出的对象，完成从单词串到单词的TOKEN串的翻译。我们可以看出，不论是识别还是分析，都是应用有限自动机，所以可以说有限自动机是词法分析的基础。实验2：中间代码生成器的设计一、 实验目的熟悉算术表达式的语法分析与中间代码生成原理。二、 实验要求(1) 设计语法制导翻译生成表达式的四元式的算法；(2) 编写代码并上机调试运行通过。·输入算术表达式·输出语法分析结果相应的四元式序列(3) 本实验已给出递归子程序法的四元式属性翻译文法的设计，鼓励学生在此基础上进行创新，即设计LL(1)分析法或LR(0)分析法的属性翻译文法，并根据这些属性翻译文法，使用扩展的语法分析器实现语法制导翻译。三、 设计概要(1) 算术表达式文法 G(E)： E à E 0 T | T T à T 1 F | FF à i | (E)(2) 文法变换G(E) E à T 0 T T à F 1 FF à i | (E)(3) 属性翻译文法： E à T 0 “push(SYN, w)” T “QUAT” T à F 1 “push(SYN, w)” F “QUAT”F à i “push(SEM, entry(w)” | (E)其中：· push(SYN, w) 当前单词w入算符栈SYN; · push(SEM, entry(w) 当前w在符号表中的入口值压入语义栈SEM; · QUAT 生成四元式函数 iT = newtemp; iiQTj =( SYNk, SEMs-1, SEMs, T); j+; iiipop( SYN, _ ); pop( SEM, _ ); pop( SEM, _ ); push( SEM, T );(4) 递归下降子程序： ·数据结构：SYN 算符栈；SEM 语义栈； E: 入口 T: 入口 T F n 0? n 1? y y 出口 push(SYN, w) 出口 push(SYN, w) read(w) QUAT read(w) QUAT T F F: 入口 主程序：Z àE ( ? n i ? n err read(w) read(w) push(SEM, entry(w) E E err n # ?err n ) ? y y 输出四元式序列 read(w)结束开始出口四、 实验核心代码void main() /主函数 t = 1; cout<<"输入表达式，以#结束:"<<endl; Z();string its(int a) /整形变成字符串形函数string d;char b='0',c;int i;while(a!=0)i = a%10;a = a/10;c = (int)b + i;d = c + d;return d;char F(char w) /F自动机string theWord;if(w>='a'&&w<='z'|w>='A'&&w<='Z')theWord = w; /当前字符是字母markStack.push(theWord);/则压栈else if(w = '(')/是左括号cin>>w; /则读取下一字符w = E(w); if(w!=')') /不是右括号则输入有误，报错cerr<<"输入错误!"<<endl;exit(0);else /否则有误，报错cerr<<"输入错误!"<<endl;exit(0);cin>>w; /读取下一字符return w;char E(char w) /E自动机string operate,a,b,c;string state5;w = T(w); while(w='+'|w='-') /是加或减符号operate = w;cin>>w; /读入下一字符w = T(w); b = markStack.pop(); /字符栈弹出a = markStack.pop(); /两个操作字符cout<<"(""<<operate<<"","<<a<<","<<b<<",t"<<t<<")"<<endl;c = "t"+its(t); /输出四元式markStack.push(c); /新状态压栈t+; /状态计数加一return w;char T(char w)string operate,a,b,c;string state5;w = F(w); while(w='*'|w='/')operate = w;cin>>w; /读取下一字符w = F(w); b = markStack.pop(); /符号栈弹出a = markStack.pop(); /两个操作字符 cout<<"(""<<operate<<"","<<a<<","<<b<<",t"<<t<<")"<<endl;c = "t"+its(t); markStack.push(c); t+; return w;bool Z() /Z自动机char w;cin>>w;w = E(w); if(w='#') /遇到"#"则结束return true;elsereturn false;五、 实验结果实验思考题：1. 语法分析分为几类？其关键技术各是什么？答： 自顶向下法（推导法）从开始符号出发，采用推导运算，试图自顶向下构造语法树。 自底向上法（归约法） 从给定的符号串出发，采用归约运算，试图自底向上构造语法树。2. 什么是递归下降子程序法，什么是LL(1)分析法？二者对文法各有什么要求？答： 递归下降子程序法：递归子程序法属于自顶向下语法分析方法。故又名递归下降法。要求文法是LL(1)文法。 LL(1)分析法：LL(1)分析法是指从左到右扫描(第一个 L) 、最左推导(第二个 L)和只查看一个当前符号(括号中的 1)之意；LL(1)分析法又称预测分析法，属于自顶向下确定性语法分析方法。要求文法是LL(1)文法。3. 比较LL(1)分析法和递归下降子程序法的异同。答： 相同点：都要求文法是LL(1)文法；都是自顶向下的分析方法；都通过分析下个字符来判断该进入哪个状态或者调用哪个函数。 不同点：LL(1)分析法先建立起预测分析表，通过对分析栈的不断操作(出栈，入栈)来进行;递归下降子程序法是通过函数间的函数调用来实现不同状态间的转换，并简化了代码。4. 什么是语法制导翻译技术？其核心技术是什么？答：语法制导翻译是在语法分析过程中，随着分析(推导或归约)的逐步进展，每识别出一个语法结构，根据文法的每个规则所对应的语义子程序进行翻译的方法；核心技术是构造属性翻译文法。5. 表达式的四元式属性翻译文法如何设计？答： 假定：SEM(m)- 语义栈(属性传递、赋值场所)；QTq 四元式区；G(E)：E -> T | E+TGEQ(+) | E-TGEQ(-) T -> F | T*FGEQ(*) | T/FGEQ(/)F -> iPUSH(i) | ( E ) 其中： PUSH(i) 压栈函数(把当前 i 压入语义栈)； GEQ(w) 表达式四元式生成函数:生成一个四元式送QTq过程： t := NEWT; 申请临时变量函数； SEND(w,SEMm-1,SEMm,t) POP;POP;PUSH(t)专心-专注-专业