©2010-2026 宁波自信网络信息技术有限公司 版权所有
客服电话：0574-28810668 投诉电话：18658249818
浙ICP备2021020529号-1 | 浙B2-20240490
关注我们 ：
1、1.课程设计目标实验建立C-编译器。只含有扫描程序（scanner）和语法分析（parser）部分。2.分析与设计c-编译器设计的整体框架，本实验实现扫描处理和语法分析程序（图中粗黑部分）。2.1 扫描程序scanner部分2.1.1 系统设计思想设计思想：根据DFA图用switch-case结构实现状态转换。惯用词法：语言的关键字：else if int return void while专用符号：+-*/=!=;,()/*/其他标记是ID和NUM,通过下列正则表达式定义：ID=letter letter*NUM=digit digit*letter=a|.|z|A|.|Zdigit=0|.
2、9大写和小写字母是有区别的 空格由空白、换行符和制表符组成。空格通常被忽略，除了它必须分开ID、NUM 关键字。注释用通常的C语言符号/./围起来。注释可以放在任何空白出现的位置(即注 释不能放在标记内)上，且可以超过一行。注释不能嵌套*scanner的DFAZZHU一*说明：当输入的字符使DFA到达接受状态的时候，则可以确定一个单词了。初始状态设置 为START,当需要得到下一个token时，取得次token的第一个字符，并且按照DFA与对 此字符的类型分析，转换状态。重复此步骤，直到DONE为止，输出token类型。当字符 为时，状态转换为SLAH再判断下一个字符，如果为”则继续转到IN
3、COMMENT,最后 以“*”时转至ij ENDCOMMENT状态,表明是注释，如果其他的则是字符停滞于当前字符，并 且输出名2L灌序流程图赋值token输出token2.1.3 各文件或函数的设计说明扫描程序用到 scanner.h,scanner.cpp scanner.h:声明词法状态，词法分析/DFA中的状态typedef enumSTART=1,INNUM,INID,INDBSYM,DONE DFAState;/定义的 Token 的类型(31 种)，分别对应于 else、if、int、returnvoid、while、+、-、*、/、v、=、=、！=、=、；、，、(、)、/*、*/
4、num、id、错误、结束 typedef enum(ELSE=1JFJNT,RETURN VOID,WHILE,PLUS,MINUS,TIMESQVERLT,LEQ,GT,GEQ,EQ,NEQ,ASSIGN,SEMI,COMMA,LP AREN,RPAREN,LMBRACKET,RMBRACKET,LBBRACKET,RBBRACKET,LCOMME NT,RCOMMENT,NUMJD,ERRORENDFILEJTokenType;/定义的Token结构体，包括类型、对应的串、所在代码的行号 struct Token(TokenType tokenType;string tokenstrin
5、g;int lineNo;)；每种 TokenType 对应的串,如 tokenTypeStringELSE二=ELSE”const string tokenTypeString32=OTHER,ELSE,IF,INT,RETURN,VOID,WHILE,PLUS,MINUS,TIMES,OVER,LT,LEQ,GT,GEQ,EQ,NEQ,ASSIGN,SEMI,COMMA,LPAREN,RPAREN,LMBRACKET,RMBRACKET,LBBRACKET,RBBRACKET,LCOMMENT,RCOMMENT,NUM,ID,ERROR,ENDFILE;class Scanner:定义 s
6、canner.cpp 中函数scanner.cpp文件函数说明void Scanner:scan():设置输出结果界面以及设置各种输出状态。if(scanSuccess=false)coutvv”词法分析出错!endl;elsecoutvv”词法分析成功了!endl;printToken。;/*输出 Token 到文件 Token.txt 中*/正在删除注释void Scanner:deleteComments()TokenTypeScanner:returnTokenType(strings)/返回Token 的类型 DFAStateScanner:charType(charc)/返回字符的
7、类型typedef enum ENDFILEERRORIF,ELSE,INTRETURNVOID,WHILE,/关键字ID,NUM,ASSIGN,PLUS,MINUS,TIMESQVER,EQ,UEQ,LT,LPARENRPAREN,SEMI,BT,LQ,BQ,DOU,LZGH,RZGH,LDGH,RDGH,特殊字符：=+-*/二二!二 v 等 TokenType;2.1.4 测雌序说明根据附录A后面的例子，程序输入两个整数，计算并打印出它们的最大公因子，保存为 a txtA A program to perfomEucilcF sAlgorithn to carpute gcd*/int g
8、cd(int u int v)if(v=0)return 14 else returngcd&/*lmi/vAv=u mod v*/void main(yoicD int耳 int y Input 0；尸input 0；output(gcd&。)；22语法分析parse部分2.2.1 系统设计思想设计思想：parser用递归下降分析方法实现，通过调用词法分析函数getfoken实现语法分析。根据C-语言的规则，得出BNF语法如下：1.program-declaration-list2.declaration-list-declaration-list declaration|declarati
9、on3.declaration-var-declaration|fun-declaration4.var-declaration-type-specifier ID;|type-specfier IDNUM5.type-specifier-int|void6.fun-specifier ID(parans)compound-stmt7.params-params-list|voidS.param-listparam-listparamlparam9.param-type-specifier ID|type-specifier ID pound-stmt-local-declarations s
10、tatement-list11.local-declarations-local-declarations var-declaration|empty12.statement-list-statement-list statement|empty13.statement-expression-stmt|compound-stmt|selection-stmt|iteration-stmt|return-stmt14.expression-stmt-expression;|;15.selection-stmt-if(expression)statement|if(expression)state
11、ment elsestatement16.iteration-stmt-while(expression)statement17.return-stmt-return;|return expression;18.expression-var=expression|simple-expression19.var-l D|I Dexpression2 0.simple-expression-additive-expression relopadditive-expression|additive-expression21.relop-=|=|=|!=22.additive-expression-a
12、dditive-expression addop term|term23.addop-+|-24.term-term mulop factor|factor25.mulop-|/*26.factor-(expression)|var|call|NUM27.call-ID(args)28.args-arg-list|empty29.arg-list-arg-list,expression|expression21嘴法分析程序流程图213各文件或函数的设计说明语法分析程序包括：parser.cpp,parser.h parser.cpp:Parser:Parser。/界面设计Token Parse
13、r:getToken。/获取scanner 中保存在TokenList数组中的 Token,并且每 次获取完之后数组下标指向下一个void Parser:syntaxError(string s)/出错处理void Parser:match(TokenType ex)匹酉己出错TreeNode*Parser:declaration(void)类型匹酉己错误TreeNode*Parser:paramJist(TreeNode*k)/k 可能是已经被取出来的 VoidK，但又不是(void)类型的参数列表，所以一直传到param中去，作为其一个子节点 parse.h:对parse.c的函数声明19
14、种节点类型，分别表示int、id、void、数值、变量声明、数组声明、函数声明、函数 声明参数列表、函数声明参数、复合语句体、if、while,return,赋值、运算、数组元素、函数调用、函数调用参数列表、未知节点typedef enum IntK,IdK,VoidK,ConstK,Var_DeclK,Arry_DeclK,FunK,ParamsK,ParamK,CompK,Selection_StmtK,lteration_StmtK,Return_StmtK,AssignK,OpK,Arry_ElemK,CallK,ArgsK,UnkownK Nodekind;typedef enum
15、Void,Integer ExpType;ofstream fout_T ree(”tokenTree.txt”);/输出语法树到文件/treeNode定义包括子节点、兄弟节点、所处行号、节点类型、属性、表达式返回类型 typedef struct treeNodeTreeNode*newNode(Nodekind k);根据节点类型新建节点TreeNode*declarationjist(void);TreeNode*declaration(void);TreeNode*params(void);TreeNode*paramJist(TreeNode*k);TreeNode*param(Tr
16、eeNode*k);TreeNode*compound_stmt(void);TreeNode*local_declaration(void);TreeNode*statement_list(void);TreeNode*statement(void);TreeNode*expression_stmt(void);TreeNode*selection_stmt(void);TreeNode*iteration_stmt(void);TreeNode*return_stmt(void);TreeNode*expression(void);TreeNode*var(void);TreeNode*s
17、imple_expression(TreeNode*k);TreeNode*additive_expression(TreeNode*k);TreeNode*term(TreeNode*k);TreeNode*factor(TreeNode*k);TreeNode*call(TreeNode*k);TreeNode*args(void);2.1.4测试程序说明根据附录A后面的例子，程序输入两个整数，计算并打印出它们的最大公因子，保存为 a txtA A program to perfomEucilcf sAlgori thn to ccnpute gcd*/int gcd(int u int
18、v)(if=0)return 14else returngcd&irWv；/*u irod v*/void main&oid)(int可int工Input 0；Unput 0；output(gcd&D)；3.程序代码实现按文件列出主要程序代码，添加必要的注释.Scannencpp:include include include include#include scanner.h#include using namespace std;/*Name:词法分析器Copyright:Author:XXXDate:19-05-14 12:00Description:提取出 token*/Scanner
19、Scanner()scanSuccess=true;charindex=0;str=m,;commentFlag=true;sourseString=nn;lineCount=0;)void Scanner:scan()(coutv”开始词法分析endl;bool doubleSym=false;getSourseStringFromFile(nsourseFile.txtn);int state=START;lineCount=0;char ch;while(state6)(ch=getNextChar();if()(y=ch)(Token t;LlineNo=lineCount;t.to
20、kenString=nn;t.tokenlype=ENDFILE;tokenList.push_back(t);break;)if(START=state)初始状态和空格state=charlype(ch);if(state!=SIART)str+=ch;else if(INNUM=state)/digit(state=charlype(ch);if(state!=INNUM)state=DONE;elsestr+=ch;)else if(INID=state)/letter(state=charlype(ch);if(state!=INID)state=DONE;elsestr+=ch;)e
21、lse if(INDBSYM=state)/除了 o二!之外的各种符号(if(2=ch)(str+=ch;doubleSym=true;)elsedoubleSym=false;state=DONE;)if(DONE=state)接收状态(int tp=0;if(=ch)tp=l；Token t;tlineNo=lineCount-tp;ttokenString=str;ttokenlype=retumlbkenlype(str);tokenList.push_back(t);if(ERROR=t.tokenType)scanSuccess=false;int lastState=charly
22、pe(strstr.length()-1);if(lastState=INNUM II lastState=INID II(lastState=INDBSYM&doubleSym=false)backlbLastCharQ;str=nn;state=START;if(doubleSym=true)doubleSym=false;)if(scanSuccess=false)cout”词法分析出错！”endl;elsecout词法分析成功了！Nvendl;printToken();/检出 Token 到文件 Token.txt 中)Token Scanner:getIbkenAt(int toke
23、nindex)(Token token;token.lineNo=lineCount;token.tokenString=nn;token.tokenlype=ENDFILE;if(tokenIndextokenList.size()token=tokenList.at(tokenIndex+);)return token;)void Scanner:getSourseStringFromFile(string path)(ifstream fin(path.c_str();string temp;sourseString=nn;while(getline(fin,temp)(sourseSt
24、ring+=temp;sourseString+=n;)fin.close();charindex=0;)void Scanner:deleteComments()(coutvv”正在删除注释.Jvvendl;ofstream fout_Sourse(nsourseFile.txtH);int state=1;char ch;while(state6)(ch=getNextChar();if()(y=ch)/文件结束break;if(l=state)(if(/=ch)state=2;elsestate=1;)fout_Soursech;else if(2=state)(if(*=ch)(sta
25、te=3;commentFlag=false;)else(state=1;fbut_Sourse,7ch;)else if(3=state)(if(，*=ch)state=4;else(state=3;)else if(4=state)(if(*=ch)state=4;elseif(7!=ch)state=5;elsestate=3;)if(5=state)结束状态，处理(commentFlag=true;state=1;)if(!commentFlag)(cout注释错误，没有结束符！vvendl;scanSuccess=false;)elsecout”注释已经成功删除！”endl;)Tok
26、enTypeScanner:retumTokenType(strings)返回Token 的类型(TokenType t;if(s=nelseH)(t=ELSE;)elseif(s=Hif,)(t=IF;)elseif(s=nintn)(t=INT;)else if(s=retumn)t=RETURN;)else if(s=voidn)|t 二 VOID;)else if(s=nwhile)(t=WHILE;)elseif(s=n+n)(t=PLUS;)elseif(s=H-n)(t=MINUS;)elseif(s二士*)(t=TIMES;)elseif(s=H/n)(t=OVER;)else
27、if(s=nn)|t=ET;)elseif(s=Hn)t=GT;)elseif(s=n=n)(t=GEQ;)elseif(s=n=n)(t=EQ;)elseif(s=n!=n)(t=NEQ;)elseif(s=n=n)(t=ASSIGN;)elseif(s=n;n)(t 二 SEMI;)elseif(s=n,H)|t=COMMA;)elseif(s=(n)(t=LBXREN;)elseif(s=n)n)t=RBREN;)elseif(s=nH)(t=LMBRACKET;)elseif(s=nH)(t=RMBRACKET;)elseif(s=nn)(t=LBBRACKET;)elseif(s=n
28、n)(t=RBBRACKET;)elseif(s=,7*n)(t=LCOMMENT;)elseif(s=*/)(t=RCOMMENT;)else if(2=charlype(ss.length()-1)|t 二 NUM;)else if(3=charlype(ss.length()-1)t=ID;)elset=ERROR;)return t;)DFAState Scanner:charType(char c)返回字符的类型(if=cn=c II V=c IIY=c)return START;elseif(c=V&c=W&c=,a,&c II c=II c=T)return INDBSYM;el
29、sereturn DONE;)char Scanner:getNextChar()(if(charIndex0)char ch=sourseStringcharIndex-1;charindex-;if(n，=ch)lineCount-;)void Scanner:printlbkenQofstream fout_Ibken(nTbken.txtH);ifstream fin(nsourseFile.txtn);string temp;int lineCount=0;int index=0;while(getline(fin,temp)fout_TbkenlineCountn:fout_Ibk
30、entempendl;while(index=l&t.tokenTypev=6)关键字string tp=nn;for(int i=0;i=7&t.tokenTypev=27)符号(string tp=for(int i=0;iwidth-t.tokenString.length();i+)tp+=n n；fout_lbkennsymbols：nheadSt.tokenStringnHtpH HtokenTypeStringt.tokenTypeH Hendl;)else if(t!okenType=28)/NUM(string tp=nn;for(int i=0;iwidth-t.token
31、String.length();i+)tp+=n n；fout_Tokenn NUM：nheadSt.tokenStringnntpH HtokenTypeStringt.tokenTypeH endl;)else if(t.tokenType=29)/ID(string tp=for(int i=0;iwidth-t.tokenString.length();i+)tp+二”；fout_Tokenn ID：nheadSt.tokenStringntp HtokenTypeStringt.tokenTypeH endl;)else if(t.tokenType=30)错误(string tp=
32、nn;for(int i=0;iwidth-t.tokenString.length();i+)tp+=n n；fout_lbkenn error：nheadSt.tokenStringnntp HtokenTypeStringt.tokenTypeH endl;else if(t.tokenType=ENDFILE)/结束(fout_Tokenn HlineCountH:fout_Ibkent.tokenStringHHn HtokenTypeStringt.tokenIypeH nendl;)if(lineCountt.lineNo)break;)lineCount+;)fin.close
33、);fout_Ibken.close();)scannenh:#include#includeusing namespace std;定义的 Token 的类型(31 种)，分别对应于 else、if、int return、void、while、+、-、*、/、=、=、！=、二、；、，、(、)、卜、/*、*/、num、id、错误、结束 typedef enum(ELSE=1,IF,INT,RETURN,VOID,WHILE,PLUS,MINUS,TIMES,OVER,ET,LEQ,GT,GEQ,EQ,NEQ,ASSIGN,SEMI,COMMA,LPARE N,RBREN,LMBRACKET,
34、RMBRACKET,LBBRACKET,RBBRACKET,LCOMMENT,RC OMMENT,NUM,ID,ERROR,ENDFILE IbkenType;typedef enum(START=1,INNUM,INID,INDBSYM,DONE DFAState;定义的Token结构体，包括类型、对应的串、所在代码的行号struct Token(IbkenType tokenlype;string tokenString;int lineNo;)；/每种 TokenType 对应的串，如 tokeniypeStringELSE二=ELSE”const string token!ypeStr
35、ing32=OTHER，“ELSE“，“IF“，“INT,“RETURN，“VOID”,“WHILE，PLUS，“MINUS，“TIMES，OVER，ET,“LEQ“，“GT“，“GEQ“，“EQ”,NEQ,“ASSIGN,nSEMIn,“COMMA,LPAREN,HRPARENH,HLMBRACKET,HRMBRACKETH,HLBBRACKETn,RBBRACKET,LCOMMENT,HRCOMMENTH,“NUM”,“ID,ERROR,ENDFILE”;class Scanner(public:bool scanSuccess;/词法分析是否成功的标志void getSourseStri
36、ngFromFile(string s);通过提供的文件名获取源代码void deleteComments。;/删除注释void scan。;/词法分析，将分析的Token放在tokenList数组中 Scanner();Token getlbkenAt(int);/根据下标从 tokenList 数组中获取 Tokenprivate:DEStatecharType(char);返回字符的类型，如：空格2：数字3：字母等char getNextChar。;/获取到下一个字符void backIoLastChar();TokenType retumTokenType(string s);/根据字
37、符串返回 Token 类型void printToken。;/将词法分析好的Token输出到文件Token.txt中string sourseString;/获取源代码的字符串int charindex;/配合getNextChar(),指定要取的字符位置string str在分析过程中保存Token对应的串bool commentFlag;/标注注释开始的标志int lineCount;/对行号计数，每次获取到7理就自增 vector tokenList;/保存的 Token 序列)；Parsencpp:include scanner.h include parser.h include i
38、nclude using namespace std;Parser:Parser()(step=0;tokenindex=0;Error=false;string path=na.txtn;cout”请输入文件名：”；cinpath;scanner.getSourseStringFromFile(path);scanner.deleteCommentsQ;if(scanner.scanSuccess)|scannerscanQ;if(scanner.scanSuccess)(coutvv”开始语法分析.kvendl;syntaxTree=parse();printlree(syntaxlree
39、);if(Error)cout语法分析过程出错!nendl;elsecoutvv”语法分析成功！Syntax error at line nlastIbken.lineNoH 出错附近Token:HlastToken.tokenStringn Token 类 型：ntokenIypeStringlastToken.tokenTypeendl;Error=true;)void Parser:match(TbkenType ex)(if(currentlbken.tokenlype=ex)(getlbkenQ;)else(syntaxError(匹配+tokenTypeStringex+出错)；)
40、void Parser:printSpace(mt n)for(int i=0;inodekind)(case VbidK:fout_TreenVDidKHendl;break;case IntK:fout_TreeIntKHendl;break;case IdK:fout_TreenIdK:Ht-attr.nameendl;break;case ConstK:fout_TreeHConstK:nt-attr.valendl;break;case Var_DeclK:fout_TreenVar_DeclKHendl;break;case Arry_DeclK:fout_TreeHArry_De
41、clKnendl;break;case FunK:fout_TreenFuncKHendl;break;case ParamsK:fout_TreeHParamsKendl;break;case ParamK:fout_TreeHParamKnendl;break;case CompK:fout_TreeHCompKendl;break;case Selection_StmtK:fout_TreeHIf,endl;break;case Iteration_StmtK:fout_TreeHWhilenendl;break;case Retum_StmtK:fout_TreeHRetumHendl
42、break;caseAssignK:fout_TreenAssignHendl;break;case OpK:fout_TreeHOp:fout_TreetokenIypeStringt-attr.opendl;break;case Arry_ElemK:fout_TreenArry_ElemKendl;break;case CallK:fout_TreeHCaUKHendl;break;caseArgsK:fout_TreeArgsKHendl;break;default:fout_TreenUnknownK：Unknown exp kindendl;break;)step+;进入子节点多
43、输出空格 for(i=O;ichildi!=NULL)printTree(t-childi);)step-;/进入兄弟节点时，由于进入子节点时n+了，所以要n-回来，从而输出一样 的空格空格t=t-sibling;)TreeNode*Parser:newNode(Nodekind kind)(TreeNode*p=(TreeNode*)malloc(sizeof(TreeNode);intk;if(p=NULL)|cout”内存分配出错！endl;)else(for(k=O;kchildk=NULL;)p-sibling=NULL;p-nodekind=kind;p-lineno=curren
44、tlbken.lineNo;if(kind=OpK II kind=IntK II kind=IdK)p-type=Integer;if(kind=IdK)p-attr.name=nn;if(kind=ConstK)p-attr.val=0;)return p;)TreeNode*Parser:parse(void)(TreeNode*t;currentlbken=getlbkenQ;lastlbken=currentlbken;t=declaration_list();if(currentlbken.tokenlype!=ENDFILE)(syntaxError(结束错误”)；)return
45、 t;)TreeNode*Parser:declaration_list()(TreeNode*t=declaration();TreeNode*p=t;/在开始语法分析出错的情况下找到int和void型,过滤掉int和void之前的所有Token,防止在开始时出错后面一错百错while(currentToken!okenType!=INT)&(currentToken.tokenType!=VOID)&(currentToke n.tokenType!二ENDFILE)syntaxError(nn);getlbkenQ;if(currentIbken.tokenlype=ENDFILE)br
46、eak;)寻找语法分析的入口，即找至Uint和voidwhile(currentToken.tokenType=INT)ll(currentToken.tokenType=VOID)(TreeNode*q;q=declarationQ;if(q!=NULL)(if(t=NULL)(t=p=q;)else(p-sibling=q;p=q;)match(ENDFILE);return t;)TreeNode*Parser:declaration(void)(TreeNode*t=NULL;TreeNode*p=NULL;TreeNode*q=NULL;TreeNode*s=NULL;if(curr
47、entIbken.tokenIype=INT)(p=newNode(IntK);match(INT);)else if(currentToken.token!ype=VOID)|p=newNode(VbidK);match(VOID);)else(syntaxError(类型匹配错误”)；)if(p!=NULL)&(currentToken.tokenIype=ID)(q=newNode(IdK);q-attr.name=currentIbken.tokenString.c_str();match(ID);if(currentToken.tokenlype=LPAREN)/,(,：函数情况(t
48、newNode(FunK);t-childO=p;t-childl=q;match(LPAREN);t-child2=paramsQ;match(RBXREN);t-child3=compound_stmt();)else if(currentToken.tokeniype二二LMBRACKET)：数组声明(t=newNode(Var_DeclK);TreeNode*m=newNode(Arry_DeclK);match(LMBRACKET);match(NUM);s=newNode(ConstK);s-attr.val=atoi(lastToken.tokenString.c_str();
49、m-child0=q;m-childl=s;t-childO=p;t-childl=m;match(RMBRACKET);match(SEMI);)else if(currentToken.tokeniype=SEMD；结尾：普通变量声明(t=newNode(Var_DeclK);t-childO=p;t-childl=q;match(SEMI);)else(syntaxError(HH);)else(syntaxError(,n,);)return t;)TreeNode*Parser:params(void)(TreeNode*t=newNode(ParamsK);TreeNode*p=NULL;if(currentToken.tokenType=VOID)/开头为 void,参数列表可能是(void)和(void id,.)两种情况p=newNode(VbidK);match(VOID);if(currentToken.tokenType=RPAREN)参数列表为(void)(if(t!=NULL)t-childO=p;)else/参数列表为(void id,)-void类型的变量(t-childO=param_list(p);)else if(currentToken.tokeniype=INT)/参数列表为(int id,.)(t-childO=param_l
©2010-2026 宁波自信网络信息技术有限公司 版权所有
客服电话：0574-28810668 投诉电话：18658249818
浙ICP备2021020529号-1 | 浙B2-20240490
关注我们 ：
