編譯技術(shù)課程設(shè)計A實驗報告(華北電力大學(xué)科技學(xué)院)

科技學(xué)院課程設(shè)計報告(2011--2012年度第1學(xué)期)名稱：編譯技術(shù)課程設(shè)計A院系：科技學(xué)院信息工程系班級：軟件09k2學(xué)號：091909020227學(xué)生姓名：閆雪峰指導(dǎo)教師：郭豐娟設(shè)計周數(shù)：2成績：日期：2011年12月6日《編譯技術(shù)課程設(shè)計A》任務(wù)書一、目的與要求1.理解和掌握編譯程序設(shè)計原理及常用的技術(shù)，建立編譯程序的整體概念；2.理解和掌握編譯程序詞法分析、語法分析、語義分析、中間代碼生成和目標(biāo)代碼生成等幾個關(guān)鍵環(huán)節(jié)原理和實現(xiàn)算法；3.掌握軟件模塊設(shè)計技能；熟悉并能較好地利用軟件開發(fā)環(huán)境獨立編程、調(diào)試和分析程序運行情況，逐漸形成創(chuàng)新思維和從事系統(tǒng)軟件的研究和開發(fā)能力。二、主要內(nèi)容定義一個簡化的類C語言—L語言作為源語言，重點針對詞法分析、語法分析、語義分析、中間代碼生成和目標(biāo)代碼生成等幾個關(guān)鍵環(huán)節(jié)進行編程和調(diào)試訓(xùn)練，最終設(shè)計實現(xiàn)L語言的編譯程序。通過調(diào)試L編譯程序，了解一般編譯程序的總體框架，掌握編譯各階段程序的構(gòu)造，理解和掌握錯誤處理方法及符號表的組織方式，理解和掌握語法制導(dǎo)翻譯方法。還可以適當(dāng)擴展L語言成分，并對相應(yīng)的編譯程序進行擴充?？墒褂肅、VC++等語言編程實現(xiàn)。具體內(nèi)容包括：由單詞的語法規(guī)則出發(fā)、畫出識別單詞的狀態(tài)轉(zhuǎn)換圖，然后用程序?qū)崿F(xiàn)掃描器設(shè)計。設(shè)計、編寫和調(diào)試算法優(yōu)先分析程序，了解算法優(yōu)先分析器的組成結(jié)構(gòu)以及對文法的要求，掌握實現(xiàn)通用算法優(yōu)先分析算法的方法。在算符優(yōu)先分析文法的基礎(chǔ)上進行翻譯工作，生成四元式表；設(shè)計一個簡單的代碼生成器，該代碼生成器以基本塊為單位，依次將每條中間代碼變換成相應(yīng)的目標(biāo)代碼。綜合以上實驗的結(jié)果，并進行集成與設(shè)計，開發(fā)出一個小型編譯程序。對于各項主要內(nèi)容的實現(xiàn)細(xì)節(jié)描述和指導(dǎo)，請參考《計算機綜合實踐指導(dǎo)》編譯技術(shù)的相關(guān)內(nèi)容。三、進度計劃序號設(shè)計(實驗)內(nèi)容完成時間備注1詞法分析器設(shè)計2天2算符優(yōu)先分析程序設(shè)計3天3語法制導(dǎo)翻譯程序設(shè)計3天4簡單代碼生成器設(shè)計2天四、設(shè)計（實驗）成果要求至少完成簡單變量定義語句及包含算術(shù)運算符的賦值語句的整個編譯過程，統(tǒng)一使用課程設(shè)計報告書，文字清楚、工整。五、考核方式實驗結(jié)果（60％）+實驗報告（30％）+實驗過程表現(xiàn)（10％）學(xué)生姓名：指導(dǎo)教師：年月日

一、課程設(shè)計(綜合實驗)的目的與要求實驗整體思想：a)詞法分析總體概述：由單詞的語法規(guī)則出發(fā)、畫出識別單詞的狀態(tài)轉(zhuǎn)換圖，然后用程序?qū)崿F(xiàn)掃描器設(shè)計。具體要求：設(shè)計一個掃描器，該掃描器是一個子程序，其輸入是源程序字符串，每調(diào)用一次，就輸出一個以內(nèi)部形式表示的單詞符號。（1）單詞符號及其內(nèi)部表示單詞符號種別編碼單詞的屬性值key0在變量表中的下標(biāo)var1變量名字的字符串const2常量的整型值operate3運算符在運算符表中的下標(biāo)//能識別單行注視并過濾注：其中關(guān)鍵字保留，不支持將關(guān)鍵字作為變量名。輸入預(yù)處理1.詞法分析器工作的第一步就是輸入源程序文本。2.預(yù)處理工作會剔除源程序中多余的空格（將多個空格換行符合并成一個）。3.能識別//***這樣的單行注視將其過濾掉。4.將固定字長的過濾過字節(jié)放到循環(huán)掃緩沖區(qū)，并記錄掃描位置，下次繼續(xù)從上次掃描結(jié)尾繼續(xù)掃描取固定字長。5.本程序設(shè)計為255個字節(jié)，最大單個標(biāo)識符長度不能超過255個字節(jié)。（3）輸入緩沖區(qū)設(shè)計掃描緩沖去一分為二。起點指示器 搜索指示器每半個緩沖區(qū)可容納256個字符，兩個半?yún)^(qū)互補。如果搜索指示器從單詞起點出發(fā)搜索到半?yún)^(qū)邊緣尚未到達(dá)單詞的終點，那么就調(diào)用預(yù)處理程序，另其把后序的256個字符裝進另半?yún)^(qū)緩沖區(qū)中字符的存放其中如下代碼在緩沖區(qū)里的存放a=b+c;Aa==Bb++cc;;\\n2（5）識別單詞符號的狀態(tài)裝換圖00空白數(shù)字=+*，（）其他1312111053字母1312111053761字母或數(shù)字761數(shù)字非字母與數(shù)字非數(shù)字**98429842b)語法分析總體概述： 采用自下而上規(guī)約過程，根據(jù)算符優(yōu)先文法。具體要求：設(shè)計、編寫和調(diào)試算法優(yōu)先分析程序，了解算法優(yōu)先分析器的組成結(jié)構(gòu)以及對文法的要求，掌握實現(xiàn)通用算法優(yōu)先分析算法的方法。算符優(yōu)先文法定義算符優(yōu)先文法是一種自下而上的分析方法，其文法的特點是文法的產(chǎn)生式中不含兩 個相鄰的非終結(jié)符。自上而下的分析方法，通常要求文法的產(chǎn)生式不含左遞歸，如 LL(I)文法就是一種可以自上而下分析的文法。假定G是不含ε-產(chǎn)生式的算符文法。對于任何一對終結(jié)符a、b，我們說：a等于b當(dāng)且僅當(dāng)文法G中含有形如P→···ab···或P→···aQb···的產(chǎn)生式； （2） a小于b當(dāng)且僅當(dāng)G中含有形如P→···aR···的產(chǎn)生式，而R(+=>)b···或R(+=>)Qb···；（3）a大于b當(dāng)且僅當(dāng)G中含有形如P→···Rb···的產(chǎn)生式，而R(+=>)···a或R(+=>)···aQ；如果一個算符文法G中的任何終結(jié)符對（a,b）之多滿足下述三個條件之一：a=b,a<b,a>b則稱G是一個算符優(yōu)先文法。(2)文法S->D;ED->TspeL;T->keyL->varE->Evar=F;|var=F;F->M+F|M|M-FM->M*T|M|M/T|TT->L|const優(yōu)先表程序采用遞歸方式求的優(yōu)先關(guān)系表先求FIRSTVT集和LASTVT集=+-*/;kevaco=+-*/;kevacosp#符號棧每次入站判斷棧頂終結(jié)符和棧外終結(jié)符的有限關(guān)系，小于等于就入棧，大于規(guī)約每次規(guī)約比較靠近棧頂?shù)牡诙€終結(jié)符和棧頂終結(jié)符的有限關(guān)系，若小于規(guī)約第二個終結(jié)符到棧頂。每次規(guī)約查找文發(fā)表進行規(guī)約。二、課程設(shè)計（綜合實驗）總結(jié)或結(jié)論通過實驗掌握了詞法分析和語法分析的設(shè)計以及制導(dǎo)過程如何生成四元式。了解了算符優(yōu)先文法的原理及具體過程。加深了c語言文件應(yīng)用，加深了編程能力，深入掌握了庫函數(shù)的用法。三、參考文獻(xiàn)[1]陳火旺,劉春林編譯原理.國防工業(yè)出版社,第三版.2009.6附錄（設(shè)計流程圖、程序、表格、數(shù)據(jù)等）頭文件MyHead.h#pragmaonce#defineSBUFSIZE256//定義掃描緩沖區(qū)的大小#defineARROPELEN9//定義運算符數(shù)組的長度#defineARRKEYLEN2//定義關(guān)鍵字?jǐn)?shù)組的長度structsBinaryRelation//返回值若為關(guān)鍵字或變量{ intiId;//區(qū)分是什么 intiSubScript;//存放操作符和關(guān)鍵字的偏移量，若是常量返回為常量的整型值 characTempValName[SBUFSIZE];//存放變量的值};char*apcKeyWords[]={"","int"};charapcOperator[]={'','=','+','-','*','/','(',')',';','#'};char*apcWordList[]={"key","var","const","operate","nonTerminalSymbol","special"};詞法分析器/*Lu語言詞法分析器顏海鏡11.12.30代碼已通過編譯，尚未優(yōu)化沒次調(diào)用正確返回一個符合詞法規(guī)則的單詞源文件保存在.lu文件支持形如變量定義（僅支持int類型），基本加減乘除法，不支持,支持單行注視支持()可擴展：支持N個關(guān)鍵字，單個標(biāo)識符最大支持256個字符，支持運算符擴展，支持函數(shù)名擴展inta=b+c;inta=100;//顏海鏡*/#include<stdio.h>#include<stdlib.h>#include<ctype.h>#include<string.h>#include"MyHeader.h"staticcharacScanBufL[SBUFSIZE]={0};//掃描緩沖區(qū)staticcharacScanBufR[SBUFSIZE]={0};staticlonglnOffset=0;//偏移量，記錄當(dāng)前文件指針距離開頭的距離charCheckChar(FILE*pfSubSourceFile,char**ppcSubCurrent,charcSubTemp,charfcSubBlank)//檢查字符功能，具有合并空格，去除回車{ if(cSubTemp==EOF) { return0x20; }//判斷是否到文件末尾，結(jié)束返回空格 if(cSubTemp!=10&&isspace(cSubTemp))//判斷是否為空格,合并多個空格為一個 { if(fcSubBlank=='N') { **ppcSubCurrent=0x20; (*ppcSubCurrent)++; fcSubBlank='Y';//修改空格標(biāo)志位 } cSubTemp=fgetc(pfSubSourceFile);//空格的話再讀入一個字符 cSubTemp=CheckChar(pfSubSourceFile,ppcSubCurrent,cSubTemp,fcSubBlank);//遞歸檢查 } if(cSubTemp=='/')//判斷注視 { charcTemp;//臨時變量，用于檢查下一個是否為'/' cTemp=fgetc(pfSubSourceFile);//再讀入一個字符 if(cTemp=='/')//若為注視一直讀入知道換行符，否則退回剛才讀入的字符 { while(fgetc(pfSubSourceFile)!='\n'); //遇到注視，在注視結(jié)尾返回空格 cSubTemp='\n'; } elseungetc(cTemp,pfSubSourceFile);//退回剛才讀入的字符 } returncSubTemp;//返回字符}intPreProcess(char*pcSubName)//預(yù)處理子程序，完成功能每次向ScanBuffer中裝入固定字長的源程序代碼{ staticcharfcFlag='L'; inti; //將源程序中讀入剔除空格注視等放到buffer char*pcCurrent=0;//只是當(dāng)前要賦值的字節(jié) char**ppcCurrent=&pcCurrent;//指向指針的指針 char*pcStart;//指向數(shù)組的開始，計算偏移量用 char*pcTemp;//臨時變量，初始化用 FILE*pfSourceFile;//指向要打開的源程序文件 //初始化pcCurrent確認(rèn)當(dāng)前要裝入的緩沖區(qū) if(fcFlag=='L') { pcCurrent=acScanBufL; pcStart=acScanBufL; } else { pcCurrent=acScanBufR; pcStart=acScanBufR; } //初始化當(dāng)前緩沖區(qū)為空字符 pcTemp=pcCurrent; for(i=0;i<SBUFSIZE;i++) { *pcTemp=0; pcTemp++; } //打開文件 pfSourceFile=fopen("test.txt","r"); if(pfSourceFile==NULL) { printf("Thefile%swasnotopened\n",pcSubName);//判斷文件打開是否成功 exit(0);//裝入失敗退出 } else//打開成功讀入 { if(fseek(pfSourceFile,lnOffset,SEEK_SET))//移動文件指針到應(yīng)該的位置 { perror("Fseekfailed"); exit(1);//移動光標(biāo)失敗退出 } while((pcCurrent-pcStart)!=SBUFSIZE)//循環(huán)讀入指定長度字符 { charcTemp;//臨時變量 cTemp=fgetc(pfSourceFile);//讀入一個字符 cTemp=CheckChar(pfSourceFile,ppcCurrent,cTemp,'N');//獲取一個合法的字符 if(cTemp==0x20) { *pcCurrent=cTemp; pcCurrent++; *pcCurrent='#';//程序結(jié)束 break;//判斷是否到文件末尾 } *pcCurrent=cTemp;//若剛才輸入的不為空格也沒結(jié)束則輸入到緩沖區(qū) pcCurrent++; } //修改偏移量為當(dāng)前偏移量，為下次讀入用 lnOffset=ftell(pfSourceFile); //關(guān)閉文件 fclose(pfSourceFile); //修改fcFlag為下次再次裝入，更改緩沖區(qū) if(fcFlag=='L')fcFlag='R'; elsefcFlag='L'; } return3;}intCheckOperate(charcCheck)//檢查是否運算符，返回在運算符數(shù)組中的偏移量{ inti; for(i=0;i<ARROPELEN;i++) { if(cCheck==apcOperator[i])returni;//返回在運算符數(shù)組中的偏移量 } return0;//不是運算符}intCheckNewLine(charcCheck,int*piSubLine)//檢測字符是否為回車{ if(cCheck=='\n') { (*piSubLine)++; return1; } return0;}intCheckKeyWords(characCheckWords[])//檢查單詞是否為關(guān)鍵字若是返回在關(guān)鍵字列表中的下標(biāo)，不是返回0{ inti; for(i=0;i<ARRKEYLEN;i++) { if(!strcmp(acCheckWords,apcKeyWords[i]))returni; } return0;}intError(intiSubLine)//錯誤處理函數(shù)，buffer質(zhì)控{ //打印錯誤信息 printf("第%d行",iSubLine); lnOffset=0;//初始化文件偏移量 return0;}intCheckEndBuffer(char**ppcCheckPoint,char*pcSubName)//檢測是否越界,并自動切換緩沖區(qū)，bufferL越界返回1，bufferR越界返回2，沒有越界返回0{ staticcharfcBuffer='L';//初始化第一次掃描bufferl intiTempOffset;//臨時偏移量變量 fcBuffer=='L'?(iTempOffset=*ppcCheckPoint-acScanBufL):(iTempOffset=*ppcCheckPoint-acScanBufR);//計算偏移量 if(iTempOffset>=SBUFSIZE-1)//越界 { if(fcBuffer=='L') { PreProcess(pcSubName);//裝入Buffer *ppcCheckPoint=acScanBufR;//修改當(dāng)前的指示器到下一個緩沖區(qū)的開始 fcBuffer='R';//修改buffer標(biāo)志，當(dāng)前指針在bufferR中 return1;//bufferL越界返回1 } else { PreProcess(pcSubName);//裝入Buffer *ppcCheckPoint=acScanBufL;//修改當(dāng)前的指示器到下一個緩沖區(qū)的開始 fcBuffer='L';//修改buffer標(biāo)志，當(dāng)前指針在bufferL中 return2;//bufferR越界返回2 } } return0;//沒有越界返回0}structsBinaryRelationLexicalAnalyzer(char*pcSubName)//詞法分析器{ staticcharfcFirst='Y'; //初始化掃描指示器為第一個元素 staticchar*fpcStart; char**fppcStart=&fpcStart;//取fpcstart的地址 staticchar*fpcSerching; char**fppcfpcSerching=&fpcSerching;//取fpcSerching的地址 staticintiLine=1;//記錄當(dāng)前的行數(shù) int*piLine=&iLine;//指向行數(shù)的指針 structsBinaryRelationsTempResult;//存放返回結(jié)果 if(fcFirst=='Y')//第一次調(diào)用裝入bufferl { PreProcess(pcSubName); fcFirst='N'; fpcStart=acScanBufL;//將start和serch都指向第一個地址 } while(*fpcStart==0x20) { if(!CheckEndBuffer(fppcStart,pcSubName))fpcStart++;//檢查是否越界,若沒越界將start指針指向一個不為空格的字符 } fpcSerching=fpcStart;//serching指向start //fpcSerching++;//serching指向start的下一個位置 while(*fpcSerching!=0x00) { if(CheckNewLine(*fpcStart,piLine))//檢查回車，記錄行數(shù)加一 { //待擴建是否將\n也算作標(biāo)識符 fpcStart++; fpcSerching=fpcStart;//serching指向start } elseif(isalpha(*fpcStart))//第一個字符是字母，為關(guān)鍵字 { charcTempResult[SBUFSIZE]={0}; char*pcCurrent=cTempResult; //檢查是否為變量或關(guān)鍵字 while(isalnum(*fpcSerching))//下一個是字符或數(shù)字 { //if(isspace(*fpcSerching))break;//若為空格結(jié)束 *(pcCurrent++)=*fpcSerching;//將字符保存到臨時數(shù)組，并且指針后移 if(!CheckEndBuffer(fppcfpcSerching,pcSubName))fpcSerching++;//檢查是否越界,若沒越界將serching++ }//循環(huán)完成時fpceSerching指向當(dāng)前標(biāo)識符的下一個位置 //將start和serching重合 fpcStart=fpcSerching; //返回當(dāng)前的標(biāo)識符放到結(jié)構(gòu)體中 intKeyWordScript;//關(guān)鍵字的下標(biāo) if((KeyWordScript=CheckKeyWords(cTempResult))!=0)//檢查是否為關(guān)鍵字還是普通變量 { sTempResult.iId=0;//標(biāo)志符置為0，關(guān)鍵字的下標(biāo) sTempResult.iSubScript=KeyWordScript; sTempResult.acTempValName[0]='\0';//賦值 } else//普通變量 { sTempResult.iId=1;//單詞為變量 inti=-1; while(cTempResult[++i]!='\0')//將變量的值賦給變量名字?jǐn)?shù)組 { sTempResult.acTempValName[i]=cTempResult[i]; } sTempResult.acTempValName[i]=cTempResult[i];//賦值個'\0' sTempResult.iSubScript=0;//賦值 } //返回結(jié)構(gòu)體 returnsTempResult; } elseif(isdigit(*fpcStart))//如果是數(shù)字常量 { intiTemp=0; while(*fpcSerching!=0x20)//下面字符都要是數(shù)字 { if((!isdigit(*fpcSerching))&&(isalpha(*fpcSerching)))//若后面是字幕或者不是操作符 { printf("詞法分析："); Error(iLine);//不是數(shù)字報錯 printf("%d%c非法字符\n",iTemp,*fpcSerching); } iTemp=iTemp*10+int(*fpcSerching-0x30);//將數(shù)字字符轉(zhuǎn)化為整形 if(!CheckEndBuffer(fppcfpcSerching,pcSubName))fpcSerching++;//檢查是否越界,若沒越界將serching++ //判斷是否是；若下一個字符是分號或者操作符就結(jié)束 if(*fpcSerching==';')break; if(CheckOperate(*fpcSerching))break; } //循環(huán)完成時fpceSerching指向當(dāng)前標(biāo)識符的下一個位置 fpcStart=fpcSerching;//將start和serching重合 //返回當(dāng)前的標(biāo)識符放到結(jié)構(gòu)體中 sTempResult.iId=2; sTempResult.iSubScript=iTemp; sTempResult.acTempValName[0]='\0';//賦值 returnsTempResult; } elseif(CheckOperate(*fpcStart))//判斷運算符 { intiTempOperateOffset;//記錄標(biāo)識符下標(biāo) iTempOperateOffset=CheckOperate(*fpcStart); //不需要因為serching本來就在start的下一個fpceSerching++; if(!CheckEndBuffer(fppcStart,pcSubName))fpcStart=++fpcSerching;//檢查serching是否越界,若沒越界將start和serching重合 //返回當(dāng)前的標(biāo)識符放到結(jié)構(gòu)體中 sTempResult.iId=3; sTempResult.iSubScript=iTempOperateOffset; sTempResult.acTempValName[0]='\0';//賦值 returnsTempResult; } else { printf("詞法分析："); Error(iLine);//不是數(shù)字報錯 printf("%c非法字符\n",*fpcSerching); exit(1);//退出程序 } } if(*fpcSerching!=0)printf("詞法分析：未知錯誤\n");//若不為結(jié)束符，顯示未知錯誤 exit(1);//失敗返回空}intDebugLexicalAnalyzer(char*pcSubName){ structsBinaryRelationsDebugResult;//存放返回結(jié)果 inti; for(i=0;i<500;i++) { sDebugResult=LexicalAnalyzer(pcSubName); printf("%d%d%d%s\n",i,sDebugResult.iId,sDebugResult.iSubScript,sDebugResult.acTempValName); } return0;}語法分析#include"MyHeader.h"#include<stdio.h>#include<string.h>#defineGRAMMARLEN14//定義問法表長度#defineFIRSTTABLELEN12//定義優(yōu)先表長度#defineVTLEN10//定義vp集的長度#defineSTACLSIZE100//第一堆棧大小#defineNULL{1000,1000,"end"}externstructsBinaryRelationLexicalAnalyzer(char*pcSubName);//來自lexicalanalyzer中的函數(shù)structsQuarternaryForm//四元式數(shù)組{ intiOperateScript;//操作符的下標(biāo) structsBinaryRelationsArgLeft; structsBinaryRelationsArgRight; structsBinaryRelationsArgResult; //next;//指向下一個};structsVp//vt集的結(jié)構(gòu)體{ structsBinaryRelationsHead;//標(biāo)識符 structsBinaryRelationasVt[VTLEN];//vp集};structsStack//棧結(jié)構(gòu)體{ charcType; structsBinaryRelationsPlace;};staticstructsBinaryRelationaasQuarternaryForm[GRAMMARLEN][10]={ {{4,0,"start"},{4,0,"define"},{3,8,""},{4,0,"operate"},NULL},//非終結(jié)符start開始符號全部歸結(jié)到start程序的開始符號start->define;operate; {{4,0,"type"},{5,0,"special"},{4,0,"name"},NULL},//define->typespecialname {{4,0,"type"},{0,0,""},NULL},//type->key {{4,0,"name"},{1,0,""},NULL},//name->var {{4,0,"operate"},{1,0,""},{3,1,""},{4,0,"operater"},{3,8,""},{4,0,"operate"},NULL},//operate->var=operater;operate {{4,0,"operate"},{1,0,""},{3,1,""},{4,0,"operater"},NULL},//operate->var=operater {{4,0,"operater"},{4,0,"left"},{3,2,""},{4,0,"right"},NULL},//operater->left+right {{4,0,"operater"},{4,0,"left"},NULL},//operater->left {{4,0,"operater"},{4,0,"left"},{3,3,""},{4,0,"right"},NULL},//operater->left-right {{4,0,"left"},{4,0,"left"},{3,4,""},{4,0,"other"},NULL},//left->left*other {{4,0,"left"},{4,0,"left"},{3,5,""},{4,0,"other"},NULL},//left->left/other {{4,0,"left"},{4,0,"other"},NULL},//left->other {{4,0,"other"},{4,0,"name"},NULL},//other->name {{4,0,"other"},{2,0,""},NULL}//other->const};//問法定義結(jié)束staticstructsBinaryRelationasFirstTableIndex[FIRSTTABLELEN]={ NULL,{3,1,"="},{3,2,"+"},{3,3,"-"},{3,4,"*"},{3,5,"/"},{3,8,";"},{0,0,"key"},{1,0,"var"},{2,0,"const"},{5,0,"spe"},{3,9,"#"}};//定義優(yōu)先表索引函數(shù)數(shù)組下標(biāo)即為在優(yōu)先表中的下標(biāo)staticcharacFirstTable[FIRSTTABLELEN][FIRSTTABLELEN]={ {'0','=','+','-','*','/',';','0','1','2','5','3'},// {'=',0},//= {'+',0},//+ {'-',0},//- {'*',0},//* {'/',0},/// {';',0},//; {'0',0},//key {'1',0},//var {'2',0},//const {'5',0},//spe {'3',0},//#};//第78存放var和const的優(yōu)先級charRequestVt(structsVpasVt[],intiIndex,intiVtIndex,charfcVt)//返回要求的vt集的{ asVt[iIndex].sHead=aasQuarternaryForm[iIndex][0];//賦值給是誰的vt值 if(fcVt=='F')//求firstvt { if(aasQuarternaryForm[iIndex][1].iId==4)//Q... { if(aasQuarternaryForm[iIndex][2]!=NULL)//Qa { asVt[iIndex].asVt[iVtIndex]=aasQuarternaryForm[iIndex][2];//將a付 RequestVt(asVt,iIndex,iVtIndex+1,'F');//遞歸調(diào)用求F（q） } else//Q { RequestVt(asVt,iIndex,iVtIndex,'F');//遞歸調(diào)用求F（q） } } else//a.... { asVt[iIndex].asVt[iVtIndex]=aasQuarternaryForm[iIndex][1];//賦值 asVt[iIndex].asVt[iVtIndex+1]=NULL;//將下一項賦值為空 } return'F'; } else//求lastvt { inti=0; while(aasQuarternaryForm[iIndex][i+1]!=NUll)i++;//結(jié)束是i=....Q的下標(biāo) if(aasQuarternaryForm[iIndex][i].iId==4)//...Q { if(i!=1)//...aQ { asVt[iIndex].asVt[iVtIndex]=aasQuarternaryForm[iIndex][i-1];//賦值a RequestVt(asVt,iIndex,iVtIndex+1,'L');//求lastvt } else//...Q { RequestVt(asVt,iIndex,iVtIndex,'L');//求lastvt } } else//.......a { asVt[iIndex].asVt[iVtIndex]=aasQuarternaryForm[iIndex][i];//賦值a asVt[iIndex].asVt[iVtIndex+1]=NULL;//賦值NULL } return'L'; } return'E';//出錯}intRequestFirstTableScript(staticstructsBinaryRelationRequestScript)//返回終結(jié)符在firsttable中的下標(biāo){ inti; for(i=1;i<FIRSTTABLELEN;i++)//循環(huán)查找firsttableindex表中的每一項 { if(asFirstTableIndex[i].iId==RequestScript.iId&&asFirstTableIndex[i].iSubScript==RequestScript.iSubScript)returni; } return0;//沒找到失敗}intMyRequestQuarternaryFormScript(staticstructsBinaryRelationRequestScript)//返回非終結(jié)符在文發(fā)表中的偏移量{ inti; for(i=0;i<GRAMMARLEN;i++)//循環(huán)查找文發(fā)表 { if(asFirstTableIndex[0][i]==RequestScript)returni; } return-1;//錯誤}intMyRequestVtLength(structsVpRequestVtItem)//返回vt級中一項的長度{ intiLength=0; while(RequestVtItem.asVt[iLength]!=NULL)iLength++; returniLength;//返回vt的長度}intCheckGrammar(charCheckChar,intiRowScript,intiLineScript)//檢查優(yōu)先表是否復(fù)過值從而判斷問法是否正確，若未賦值返回1付過值退出{ if(CheckChar==0)return1; printf("優(yōu)先表錯誤，非算符優(yōu)先文法%s%s以有關(guān)系不能再有有限關(guān)系\n",asFirstTableIndex[iRowScript].acTempValName,asFirstTableIndex[iLineScript].acTempValName,acFirstTable[iRowScript][iLineScript]); exit(0);//退出 return0;}intIniFirstTable()//初始化firsttable優(yōu)先表,每次規(guī)約前必須初始化{ structsVpasFirstVt[GRAMMARLEN];//firstvt的集合，每項代表一個開始符，下標(biāo)和文發(fā)表兼容 structsVpasLastVt[GRAMMARLEN];//lastvt的集合 inti; for(i=1;i<FIRSTTABLELEN;i++)//初始化firsttable表中的# { acFirstTable[i][FIRSTTABLELEN-1]='>'; acFirstTable[FIRSTTABLELEN-1][i]='<'; } acFirstTable[FIRSTTABLELEN-1][FIRSTTABLELEN-1]='=';//#和#的關(guān)系為等于 for(i=0;i<GRAMMARLEN;i++)//循環(huán)求firstvt和lastvt { RequestVt(asFirstVt,i,0,'F');//求firstvt RequestVt(asLastVt,i,0,'L');//求lastvt } for(i=0;i<GRAMMARLEN;i++)//循環(huán)求優(yōu)先表 { intiGrammarItemLen=0;//記錄每項表項長度 intj; while(aasQuarternaryForm[i][iGrammarItemLen]!=NULL)iGrammarItemLen++;//求的當(dāng)前表項的長度 for(j=0;j<iGrammarItemLen;j++)//循環(huán)求 { if(aasQuarternaryForm[i][j].iId!=4&&aasQuarternaryForm[i][j+1].iId!=4)//j和j+1都為終結(jié)符j==j+1 { intij;//j的下標(biāo) intij1;//j+1的下標(biāo) ij=RequestFirstTableScript(aasQuarternaryForm[i][j]); ij1=RequestFirstTableScript(aasQuarternaryForm[i][j+1]); if(CheckGrammar(acFirstTable[ij][ij1],ij,ij1))acFirstTable[ij][ij1]='=';//有限關(guān)系相等 } if((j<iGrammarItemLen-1)&&(aasQuarternaryForm[i][j].iId!=4&&aasQuarternaryForm[i][j+2].iId!=4))//xj和xj+2都為終結(jié)符 { if(aasQuarternaryForm[i][j+1]==4)//xj+1為為非終結(jié)符 { intij;//j的下標(biāo) intij2;//j+1的下標(biāo) ij=RequestFirstTableScript(aasQuarternaryForm[i][j]); ij2=RequestFirstTableScript(aasQuarternaryForm[i][j+2]); if(CheckGrammar(acFirstTable[ij][ij2],ij,ij2))acFirstTable[ij][ij2]='=';//有限關(guān)系相等 } } if(aasQuarternaryForm[i][j].iId!=4&&aasQuarternaryForm[i][j+1].iId==4)//xj為終結(jié)符xj+1為非終結(jié)符 { intiVtIdenx;//非終結(jié)符的下標(biāo) intiVtLength;//非終結(jié)符的firstvt的長度 inti; iIdenx=MyRequestQuarternaryFormScript(aasQuarternaryForm[i][j+1]);//返回非終結(jié)符的在問法表中的偏移量也就是在vt中的偏移量 iVtLength=MyRequestVtLength(asFirstVt[iIdenx]); for(i=0;i<iVtLength;i++)//firstvt(xj+1)的每個符號優(yōu)先級大于xj { intij;//j的下標(biāo) intij1;//j+1的下標(biāo) ij=RequestFirstTableScript(aasQuarternaryForm[i][j]);//返回xj終結(jié)符在優(yōu)先表中的下標(biāo) ij1=RequestFirstTableScript(asFirstVt[iIdenx].asVt[i]);//返回xj+1非終結(jié)符的first中的每項在優(yōu)先表中的下標(biāo) if(CheckGrammar(acFirstTable[ij][ij1],ij,ij1))//判斷是否優(yōu)先關(guān)系已經(jīng)存在 { acFirstTable[ij][ij1]='<';//優(yōu)先關(guān)系小于 } } } if(aasQuarternaryForm[i][j].iId==4&&aasQuarternaryForm[i][j+1].iId!=4)//xj為非終結(jié)符，xj+1為終結(jié)符 { intiVtIdenx; intiVtLength; inti; iIdenx=MyRequestQuarternaryFormScript(aasQuarternaryForm[i][j]);//返回非終結(jié)符的在問法表中的偏移量也就是在vt中的偏移量 iVtLength=MyRequestVtLength(asLastVt[iIdenx]); for(i=0;i<iVtLength;i++)//firstvt(xj+1)的每個符號優(yōu)先級大于xj { intij;//j的下標(biāo) intij1;//j+1的下標(biāo) ij=RequestFirstTableScript(asLastVt[iIdenx].asVt[i]);//返回xj終結(jié)符在優(yōu)先表中的下標(biāo) ij1=RequestFirstTableScript(aasQuarternaryForm[i][j+1]);//返回xj+1非終結(jié)符的first中的每項在優(yōu)先表中的下標(biāo) if(CheckGrammar(acFirstTable[ij][ij1],ij,ij1))//判斷是否優(yōu)先關(guān)系已經(jīng)存在 { acFirstTable[ij][ij1]='>';//優(yōu)先關(guān)系小于 } } } } } return1;//初始化成功}charCheckTerminalPriority(structsBinaryRelationsLeft,structsBinaryRelationsRight)//返回參數(shù)的有限關(guān)系<>=若為其他返回E{ intiLeftOfFirstScript; intiRightOfFirstScript; iLeftOfFirstScript=RequestFirstTableScript(sLeft); iRightOfFirstScript=RequestFirstTableScript(sRight); if(acFirstTable[iLeftOfFirstScript][iRightOfFirstScript]=='<')return'<'; if(acFirstTable[iLeftOfFirstScript][iRightOfFirstScript]=='>')return'>'; if(acFirstTable[iLeftOfFirstScript][iRightOfFirstScript]=='=')return'='; return'E';//返回錯誤標(biāo)志}intFindStackTopTerminal(structsStackasSubStack[],intiSubStackTop,intiSubStackBottom)//返回棧頂?shù)慕K結(jié)符，返回值為棧頂終結(jié)符的下標(biāo){ inti; for(i=iSubStackTop;i>=iSubStackBottom;i--)//從棧頂開始向棧底找 { if(asSubStack[i].cType=='T')returni; } printf("語法分析：未知錯誤，搜尋棧頂終結(jié)符出錯"); exit(0); return-1;}intFindTermHead(structsStackasSubStack[],intiSubTermTail,intiSubTempHead)//求規(guī)約中的規(guī)約頭的棧下標(biāo){ intiTempTermHead;//臨時變量存放termhead charcTempCheck;//臨時存放終結(jié)符的優(yōu)先關(guān)系 iTempTermHead=FindStackTopTerminal(asSubStack,iSubTempHead,0); cTempCheck=CheckTerminalPriority(asSubStack[iSubTermTail],asSubStack[iTempTermHead]);//求的當(dāng)前終結(jié)符和棧頂終結(jié)符的優(yōu)先關(guān)系 iSubTempHead=iTempTermHead-1; if(cTempCheck=='<')//若關(guān)系為小于 { iTempTermHead=FindTermHead(asSubStack,iSubTermTail,iSubTempHead);//遞歸求下一個終結(jié)符 } returniTempTermHead;}intMyFindGrammarTableHead(structsStackasSubStack[],intiSubTermHead,intiSubTermTail)//查找可歸約串若返回值小于grammar則查找成功若等于則失敗，成功i為文法在文法表中的下標(biāo){ inti; for(i=0;i<GRAMMARLEN;i++)//循環(huán)掃描整個文法表 { if(aasQuarternaryForm[i][1]==asSubStack[iSubTermHead])//找到可規(guī)約頭部 { intj; intk=2; charcFlag='Y'; for(j=iSubTermHead+1;j<=iSubTermTail;j++,k++)//循環(huán)查找后邊是否相等 { if(aasQuarternaryForm[i][k]==NULL)//若文法結(jié)束尚照完則錯誤 { cFlag='N'; break; } if(asSubStack[j].cType=='N'&&aasQuarternaryForm[i][k].iId==4)continue;//若當(dāng)前符號為非終結(jié)符且當(dāng)前文法表中文法符號也為非終結(jié)符號規(guī)約 if(asSubStack[j].sPlace==aasQuarternaryForm[i][k])continue//若為終結(jié)符，且相等 //執(zhí)行到此與本條文法不相等 cFlag='N'; break; } if(cFlag=='Y')returni;//找到了i為下標(biāo) } } returni;//失敗返回grammar}intSyntacticAnalyzer(char*pcSubName)//語法分析器{ structsStackasStack[STACLSIZE]={NULL}; structsStacksTempItem=NULL;//臨時存放可規(guī)約的字符 intiStackTop=0;//棧頂 intiStackBottom=0;//棧底 intiStackTopTerminal;//棧頂?shù)慕K結(jié)符 //intiStackNearTopTerminal=iStackBottom;//靠近棧頂?shù)姆墙K結(jié)符 //intiTopTerminalInFirstScript;//棧頂非終結(jié)符在firsttable中的下標(biāo) //intiOutTerminalInFirstScript;//棧外終結(jié)符在firsttable中的下標(biāo) //初始化符號棧棧底有個# asStack[0].cType='T';//終結(jié)符 asStack[0].