华北电力大学编译实验报告

PAGEPAGE2课程设计报告(2013--2014年度第1学期)名称：编译技术课程设计题目：词法分析器设计算符优先分析程序设计基于算符优先分析方法的语法制导翻译程序设计院系：计算机系班级：学号：学生姓名：指导教师：设计周数：1周成绩：日期：2014年1月3日PAGE1一、课程设计的目的与要求1．词法分析器设计的目的与要求1.1词法分析器设计的实验目的本实验是为计算机科学与技术专业、网络工程专业、信息安全专业的学生在学习《编译技术》课程后，为加深对课堂教学内容的理解，培养解决实际问题能力而设置的实践环节。通过这个实验，使学生应用编译程序设计的原理和技术设计出词法分析器，了解扫描器的组成结构，不同种类单词的识别方法。能使得学生在设计和调试编译程序的能力方面有所提高。为将来设计、分析编译程序打下良好的基础。1.2词法分析器设计的实验要求设计一个扫描器，该扫描器是一个子程序，其输入是源程序字符串，每调用一次识别并输出一个单词符号。为了避免超前搜索，提高运行效率，简化扫描器的设计，假设该程序设计语言中，基本字（也称关键词）不能做一般标识符用，如果基本字、标识符和常数之间没有确定的运算符或界符作间隔，则用空白作间隔。单词符号及其内部表示如表1-1所示，单词符号中标识符由一个字母后跟多个字母、数字组成，常数由多个十进制数字组成。单词符号的内部表示，即单词的输出形式为二元式：（种别编码,单词的属性值）。表1-1单词符号及其内部表示单词符号种别编码单词的属性值BEGINIFTHENELSEEND标识符整型常数+***（）123456789101112—————在名字表中的地址十进制整数—————2．算符优先分析程序设计的目的和要求2.1算符优先分析程序设计的实验目的本实验是为计算机科学与技术等专业的学生在学习《编译技术》课程后，为加深对课堂教学内容的理解，培养解决实际问题能力而设置的实践环节。通过这个实验，使学生应用编译程序设计的原理和技术,设计、编写和调试算符优先分析程序，了解算符优先分析程序的组成结构，掌握实现通用算符优先分析算法的方法。能使得学生在设计和调试编译程序的能力方面有所提高。为将来设计、分析编译程序打下良好的基础。2.2算符优先分析程序设计的实验要求算符优先分析属于自下而上的分析方法，该语法分析程序的输入是终结符号串（即单词符号串，以一个“”结尾），如果输入串是句子则输出“YES”，否则输出“NO”和错误信息。算符优先分析过程与非终结符号无关，当由文法产生了优先关系之后文法也就失去了作用,本题目给出文法的目的是为了便于对语法分析结果进行验证。(1)文法设算符优先文法为：说明：i为整型常数或者为标识符表示整型变量；使用中↑用**表示。(2)优先关系表设优先关系表如表1-2所示。表1-2优先关系表+*↑i()#+*↑i()#3．基于算符优先分析方法的语法制导翻译程序设计的目的和要求3.1基于算符优先分析方法的语法制导翻译程序设计的实验目的本实验是为计算机科学与技术等专业的学生在学习《编译技术》课程后，为加深对课堂教学内容的理解，培养解决实际问题能力而设置的实践环节。通过这个实验，使学生应用编译程序设计的原理和技术,通过设计、编写和调试语法制导翻译程序，掌握从一种语句的语法和语义出发，构造相应的语义子程序，实现基于算符优先分析方法的语法制导翻译的方法。能使得学生在设计和调试编译程序的能力方面有所提高。为将来设计、分析编译程序打下良好的基础。3.2基于算符优先分析方法的语法制导翻译程序设计的实验要求算符优先分析方法是通过反复把输入符号移进分析栈，使用优先关系表在分析栈顶寻找最左素短语，将其归约为一个非终结符号而实现的。这个分析过程与非终结符号无关，当由文法产生了优先关系之后文法也就失去了作用（所以本题目无需给出文法）。基于算符优先分析方法的语法制导翻译是在算符优先语法分析的基础上进行翻译工作（即语义分析），每当将一个最左素短语归约为一个非终结符号时，就调用对应产生式的语义子程序，去完成相应的语义翻译工作，这步归约使用的产生式对非终结符号不加区分（即将所有的非终结符号用一个通用的非终结符号表示）。语法制导翻译程序的输入是终结符号串（即单词符号串，以一个“”结尾），如果输入符号串是句子,则按照其语义进行翻译,输出等价的四元式序列（作为练习应显示输出）。二、课程设计正文词法分析器设计1．1以键盘输入的方式输入句子。(1)标识符和常数的属性值（a）标识符和常数的属性值为该单词在名次表或常数表中登记项的相对地址；（b）当识别出一个标识符或常数时，要查名字表或常数表，若表中有其登记项，则把得到的登记项地址作为其属性值；（c）若表中没有其登记项，则建立一个新登记项，该记录项地址作为其属性值，此处的地址为在表中的下标。1．2实验分析实验分析：对于输入的句子，使用cin.get函数转换为数组。分析过程首先要进行对空格、回车、Tab的判断，若为之一则指针向后移动。如果是字母，继续判断后面的是否为字母或者数字，如果是，则加入arr中，继续判断arr是否为关键字，对于已经存入的关键字，需要通过查表操作来完成；若不是关键字，则构成标识符，将其存入地址记录表。如果开始是数字，则判断它后边紧接着的是否为数字或者小数点加数字，若满足之一，则为实数，将其存入地址记录表；若两条均不满足，则表明为常数的单词已经结束，进行下一步单词的分析。对于界符和运算符的的分析，只需判断单个字符即可，对于双目运算符，要在当前位置的基础上指针后移，再进行判断。算法简要概述：关键字表、输出串用string数组存储。采用一个字符串arr来存储分析的单词，若未分析完，则将正在处理的字符连接到arr后面，若当前单词分析完，则重新对arr进行赋值，直至整个句子全部分析完成。数组remember[]，类型为int，为变量的地址记录表；re为remember的指针；jjj()函数用于将变量或常量存入地址记录表，iii()函数用于读取输入串中的下一个字符。2.算符优先分析程序设计2.1以键盘输入的方式输入句子。2.2实验分析实验分析：优先关系表用一个数组chart[]表示，是一个8*8的二维矩阵；分析栈用数组stacks[]表示，表示的元素为终结符号、“#”、非终结符N，；数组record[]，用于存放输入字符串。算符优先分析属于自下而上的分析方法，在分析的过程中需要借助于优先关系表，在分析过程中通过查找优先关系表和分析栈的共同作用来进行分析。算法简要概述：算法首先将分析栈压入“#”，然后对字符串进行遍历。算法使用两个while嵌套循环，外层为当前字符a不为#则继续，内层循环当发现栈顶终结符的优先级的低于或等于正在考察的字符时，字符入栈，执行移入操作；当前字符与其后一个终结符的相对优先关系为大于时，则进行规约，规约的具体方法是从栈顶往栈底方向查，当发现第一个优先级低于栈顶终结符时查找结束，记录当前位置，然后从栈顶到该终结符的上一个位置规约为一个“N”，依次类推，当分析栈最终出现“#N#”，则证明输入串是句子，分析结束。若分析栈的栈顶元素与当前输入符号没有优先关系，则说明输入串有语法错误，即输入的不是句子，输出错误提示，分析结束。基于算符优先分析方法的语法制导翻译程序的设计3.1该实验算法是在第二个实验的基础上进行的，在上一个实验中只是简单的将需要规约的部分规约为“N”，而实验三中的规约是在原来的基础上进行数字的改变。在产生式的产生时，需要判断是使用的那个规约文法，在教材给出的五个产生式中，当采用前三个时才会有产生式生成。将规约后产生的N变为中间变量Ti，当遇到产生中间变量时，需要输出该四元式。三、课程设计总结或结论1．词法分析器设计通过词法分析器的设计，、更加加深了对词法分析原理的理解，明确了运算符、界符、标识符、常数的定义，实验需要注意的问题是对空格的过滤，以及对双目运算符的处理。另外，对小数的处理也要加以注意，注意判断“.”是做为界符还是小数点。对于关键字的判断，直接使用.compare(ch)函数，可以大大减少代码的行数，更可避免编写逐字比较程序时产生错误。2．算符优先分析程序设计算符优先分析的设计，主要是把优先关系表和分析栈结合起来，通过优先级的判断来决定进行规约、入栈还是错误判断的操作。规约时应注意使用哪个产生式进行规约，注意栈内内容的变化。实验另外需要注意的是对于“i+”一类非句子输入的判断。通过本次实验更加深刻的理解了优先关系表的相关概念，也体会到了优先关系表对于编译过程的意义。3．基于算符优先分析方法的语法制导翻译程序的设计在算符优先分析的基础上进行本次实验，我对于基于算符优先分析方法的语法制导翻译我有了更深一步的认识。处理的难点就是将规约与上面的实验区别开来，在产生式的产生时，需要判断是使用的那个规约文法，将规约后产生的N变为中间变量Ti，当遇到产生中间变量时，需要输出该四元式。这次实验基本达到了实验目的，由于所学知识不够全面，在试验中也遇到了很多编程上的困难，在很多方面还有待完善，在以后的学习过程中，力争掌握更多知识，在以后学习中要更加努力。四、参考文献[1]陈火旺，刘春林.程序设计语言编译原理.北京：国防工业出版社，第三版.2008，9[2]宋雨，程晓荣，黄志强.计算机综合实践指导.北京：清华大学出版社，第一版.2004附录（设计流程图、程序、运行结果等）主函数流程图主函数Initscanner

Scanner

ScannerInitscanner

Scanner

ScannerScannercloseLexscanLexscanIsAlphaIsDelimiterIsDightIsAlphaIsDelimiterIsDightOutputErrorOutputError（词法分析）主函数主函数Trans函数writeLeft函数checkAll函数Trans函数writeLeft函数checkAll函数调用Morphology结果开始开始输入待判断语句输入待判断语句进行词法分析进行词法分析分析成功？分析成功？进行规约分析进行规约分析打印规约结果打印规约结果结束结束（算符优先分析）（语法制导翻译程序）源代码（1）Morphology.cs……#region定义机内码privatevoidNewKeyWord(){machineCodes[0]="";machineCodes[1]="BEGIN";machineCodes[2]="IF";machineCodes[3]="THEN";machineCodes[4]="ELSE";machineCodes[5]="END";machineCodes[6]="标识符";machineCodes[7]="整形常数";machineCodes[8]="+";machineCodes[9]="*";machineCodes[10]="!";machineCodes[11]="(";machineCodes[12]=")";machineCodes[13]="#";}#endregion#region处理输入的代码publicvoidDispose(){while(i<input.Length)//只要不超出字符串长度就继续执行{if(IsAlpha(input[i])){RecogId();}elseif(IsDight(input[i])){RecogCons();}elseif(input[i]=='\r'&&input[i+1]=='\n'){rowNum++;i++;i++;//跳过去}elseif(IsDelimiter(input[i])){RecogSym();}elseif(input[i]==''){i++;}else{Errore=newError(rowNum,input[i].ToString(),"(1)非法字符");errors.Add(e);i++;}}}#endregion#region判断是标识符还是关键字并处理privatevoidRecogId(){stringstr="";intcode;do{str=str+input[i];i++;}while(IsAlpha(input[i])||IsDight(input[i]));//判断是不是字母或数字，是的话继续执行code=Reserve(str);//看是否为关键字tokent=newtoken();//存入token文件t.Label=tokens.Count;t.Name=str;if(code==0){t.Code=6;//标示符t.Addr=symbles.Count;symbles=newsymble();//存入符号表s.Number=t.Addr;s.Name=str;s.Type=6;symbles.Add(s);}else{t.Code=code;t.Addr=-1;}tokens.Add(t);}#endregion#region判断是不是常数并处理privatevoidRecogCons(){stringstr=input[i].ToString();boolflag=true;boolpoint=false;while(flag){i++;if(IsDight(input[i])){str+=input[i];}elseif(IsAlpha(input[i])||input[i]=='.'){Errore=newError(rowNum,str,"非整数");errors.Add(e);flag=false;ignore();}else{flag=false;//结束不再查找}}tokent=newtoken();//写入表t.Label=tokens.Count;t.Name=str;t.Code=7;//整数t.Addr=symbles.Count;symbles=newsymble();s.Number=t.Addr;s.Name=str;s.Type=7;symbles.Add(s);tokens.Add(t);}#endregion#region判断是否是符号并处理privatevoidRecogSym(){stringstr=""+input[i];for(intj=8;j<=13;j++){if(str==machineCodes[j]){tokent=newtoken();t.Label=tokens.Count;t.Name=str;t.Code=j;t.Addr=-1;tokens.Add(t);i++;}}}#endregion#region判断是不是字母privateboolIsAlpha(charc){if((c>='a'&&c<='z')||(c>='A'&&c<='Z')){returntrue;}else{returnfalse;}}#endregion#region判断是不是数字privateboolIsDight(charc){if(c>='0'&&c<='9'){returntrue;}else{returnfalse;}}#endregion#region判断是不是其他界符privateboolIsDelimiter(charc){switch(c){case'(':returntrue;case')':returntrue;case'+':returntrue;case'!':returntrue;case'*':returntrue;case'#':returntrue;default:returnfalse;}}#endregion#region匹配机内码privateintReserve(stringstr){for(inti=1;i<=5;i++){if(str==machineCodes[i]){returni;//返回机内码编号}}return0;//标识符}#endregion#region忽略多余字符privatevoidignore(){stringstr="";while(input[i]=='.'||IsAlpha(input[i])||IsDight(input[i])){str+=input[i];i++;}errors.Add(newError(rowNum,str,"忽略字符"));}#endregion}}（2）OperatorPrecedence.cs……staticList<List<char>>Precedence=newList<List<char>>{newList<char>(){'','+','*','!','i','(',')','#'}, newList<char>(){'+','>','<','<','<','<','>','>'}, newList<char>(){'*','>','>','<','<','<','>','>'}, newList<char>(){'!','>','>','<','<','<','>','>'}, newList<char>(){'i','>','>','>','','','>','>'}, newList<char>(){'(','<','<','<','<','<','=',''}, newList<char>(){')','>','>','>','','','>','>'}, newList<char>(){'#','<','<','<','<','<','','='}};intTCount=0;Morphologymor;///<summary>///能够使用的运算符///</summary>List<string>OpetatorList=newList<string>(){"+","*","!","i","(",")","#"};publicList<FourPart>fourPartResult=newList<FourPart>();……publicOperatorPrecedence(strings){Soures="#"+s;mor=newMorphology(Soures);}publicvoidbegin(){inta=1;if(checkAll()){PushToTarget();while(a==1||a==2||a==3)//直到规约结束或出错{a=compare1();if(a==1){if(trans()!=0){break;}}if(a==2||a==3){if(!PushToTarget()){}}}if(place<mor.tokens.Count-1){result="NO出错了";}}else{result="NO出错了";}}///<summary>///把左边栈内每一个元素的name写入结果的下一行///</summary>publicvoidwriteLeft(){for(inti=1;i<=LeftList.Count;i++){result+=LeftList[LeftList.Count-i].name;}result+="\n";}///<summary>///规约///</summary>publicinttrans(){intresult=0;try{targettoTrans=LeftList.Find(//查找终结符delegate(targett){returnt.isTransed==false;//返回非终结符});intnum;//非终结符在栈中序号if(toTrans!=null){num=LeftList.IndexOf(toTrans);if(toTrans.isSymble){ECount++;toT="E"+ECount;toTrans.isTransed=true;LeftList.Insert(num,toTrans);LeftList.RemoveAt(num+1);writeLeft();}else{if(toTrans.flag==')'){if(LeftList[num+1].isSymble&&LeftList[num+2].flag=='('){ECount++;targett=newtarget("E"+ECount,'i',LeftList[num+1].numInTokens,true,true);LeftList.Insert(num,t);LeftList.RemoveAt(num+1);LeftList.RemoveAt(num+1);LeftList.RemoveAt(num+1);writeLeft();}}else//是其他元素和两边的元素归约{ECount++;TCount++;targett=newtarget("E"+ECount,'i',0-TCount,true,true);targett1=newtarget("T"+TCount,'i',-1,true,true);//运算结果FourPartfp=newFourPart();fp.Op=toTrans.flag.ToString();if(LeftList[num-1].numInTokens>-1){fp.StrRight=mor.tokens[LeftList[num-1].numInTokens].Name;}else{fp.StrRight=OpResult[0-(LeftList[num-1].numInTokens+1)].name;}if(LeftList[num+1].numInTokens>-1){fp.StrLeft=mor.tokens[LeftList[num+1].numInTokens].Name;}else{fp.StrLeft=OpResult[0-(LeftList[num+1].numInTokens+1)].name;}fp.JumpNum="T"+TCount;OpResult.Add(t1);fourPartResult.Add(fp);LeftList.Insert(num-1,t);LeftList.RemoveAt(num);LeftList.RemoveAt(num);LeftList.RemoveAt(num);writeLeft();}}}return0;}catch(Exceptionx){return1;}}///<summary>///检测所有词法分析的单词，保证能够被分析///</summary>///<returns>是否通过检测</returns>boolcheckAll(){foreach(tokentinmor.tokens){if(mor.tokens[place].Addr==-1){if(!OpetatorList.Contains(mor.tokens[place].Name)){returnfalse;}}}if(mor.tokens[mor.tokens.Count-1].Name!="#"){returnfalse;}returntrue;}///<summary>///把缓冲区顶部元素压入左边的栈///</summary>///<returns></returns>boolPushToTarget(){if(place<mor.tokens.Count){if(mor.tokens[place].Addr==-1)//是关键字{LeftList.Insert(0,newtarget(mor.tokens[place].Name,mor.tokens[place].Name[0],place,false,false));if(place==0||(mor.tokens[place].Name!="#")){place++;writeLeft();}else{place++;returnfalse;}}else{LeftList.Insert(0,newtarget(mor.tokens[place].Name,'i',place,false,true));writeLeft();place++;}returntrue;}else{returnfalse;}}///<summary>///求优先级///</summary>///<returns></returns>intcompare1(){intresult=0;charrightHead;targetleftHead;if(place>=mor.tokens.Count){returnresult;}#region取缓冲区栈顶代表的算符if(mor.tokens[place].Addr==-1){rightHead=mor.tokens[place].Name[0];}else{rightHead='i';}#endregionleftHead=LeftList.Find(delegate(targett)//查找体，找到左边栈内第一个非终结符{returnt.isTransed==false;});if(leftHead==null){return2;}else{foreach(List<char>listinPrecedence)//遍历优先级信息表中的每一个行元素{if(list[0]==leftHead.flag){intn=Precedence[0].IndexOf(rightHead);//非终结符和右面的第一个元素比较查表switch(list[n]){case'>':result=1;//后边进行归约操作break;case'<':result=2;//后边进行入栈操作break;case'=':result=3;//后边进行入栈操作break;case'':result=4;//出错break;…………（3）Semantic.cs…………namespacebianyi{publicclassSemantic{publicList<FourPart>fps=newList<FourPart>();publicList<E>es=newList<E>();List<token>tokens;publicList<symble>symbles=newList<symble>();publicstringerror="";inti=0;intti=1;stringtt="";publicSemantic(Morphologym){tokens=m.tokens;symbles=m.symbles;Dispose();}privatevoidNext(){if(i<tokens.Count-1){i++;}}privatevoidBefore(){if(i>0){i--;}}#region创建临时变量privatestringNewTemp(){stringtemp="T"+ti.ToString();ti++;symbles=newsymble();s.Name=temp;symbles.Add(s);returntemp;}#endregion#region回填函数privatevoidBackPatch(intaddr,intaddr2){fps[addr].JumpNum=addr2.ToString();}#endregion#region产生四元式privatevoidEmit(stringop,stringstrLeft,stringstrRight,stringjumpNum){FourPartfp=newFourPart(op,strLeft,strRight,jumpNum);fps.Add(fp);}#endregion#region主要函数privatevoidDispose(){if(tokens[i].Code==12)//含有program{Next();if(tokens[i].Code==18)//是标识符{Emit("program",tokens[i].Name,"_","_");//执行程序体Next();ProBody();}else{error="该程序program缺少方法名";}}else{error="该程序缺少关键字：program";}}#endregion#region程序体privatevoidProBody(){if(tokens[i].Code==16){Next();VarDef();}elseif(tokens[i].Code==2){Next();ComSent();}else{error="程序体缺少var或begin";}}#endregion#region变量定义privatevoidVarDef(){if(IsIdlist()){Next();if(tokens[i].Code==29)//：{Next();if(tokens[i].Code==9||tokens[i].Code==3||tokens[i].Code==13)//integer,bool,real{intj=i;j=j-2;symbles[tokens[j].Addr].Type=tokens[i].Code;j--;while(tokens[j].Code==28){j--;symbles[tokens[j].Addr].Type=tokens[i].Code;}Next();if(tokens[i].Code==30){Next();if(tokens[i].Code==2){Next();ComSent();}else{VarDef();}}else{error="变量定义后面缺少；";}}else{error="变量定义缺少类型或类型定义错误";return;}}else{error="var后面缺少冒号";}}else{error="变量定义标识符出错";}}#endregion#region判断是不是标识符表privateboolIsIdlist(){if(tokens[i].Code==18){Next();if(tokens[i].Code==28)//,{Next();returnIsIdlist();}else{Before();returntrue;}}else{returnfalse;}}#endregion#region复合句privatevoidComSent(){SentList();if(error==""){if(tokens[i].Code==6){Emit("sys","_","_","_");}else{error="复合句末尾缺少end";}}}#endregion#region语句表privatevoidSentList(){Ss=newS();ExecSent(refs);if(error==""){Next();if(tokens[i].Code==30){Next();SentList();}}}#endregion#region执行句privatevoidExecSent(refSs){if(tokens[i].Code==18){Next();AssiSent();}elseif(tokens[i].Code==2||tokens[i].Code==8||tokens[i].Code==17){StructSent(refs);}else{Before();}}#endregion#region赋值句privatevoidAssiSent(){if(tokens[i].Code==31)//:={stringtemp=tokens[i-1].Name;Next();Expression();Emit(":=",tt,"_",temp);}else{error="赋值句变量后缺少：=";}}#endregion#region表达式privatevoidExpression(){if(tokens[i].Code==7||tokens[i].Code==15||(tokens[i].Addr!=-1&&symbles[tokens[i].Addr].Type==3)){Ee=newE();BoolExp(refe);}else{AritExp();}}#endregion#region布尔表达式privatevoidBoolExp(refEe){Ee1=newE();BoolItem(refe1);if(error==""){Next();if(tokens[i].Code==11){intm=fps.Count;Ee2=newE();Next();BoolExp(refe2);e.t.Concat(e1.t);e.t.Concat(e2.t);e.f=e2.f;foreach(intkine.t){BackPatch(k,m);}}else{e=e1;Before();}}else{e=e1;}}#endregion#region布尔项privatevoidBoolItem(refEe){Ee1=newE();BoolFactor(refe1);if(error==""){Next();if(tokens[i].Code==1){Next();