1、编译原理课程设计报告课题名称:C- Minus 词法分析和语法分析设计提交文档学生姓名: X X X 提交文档学生学号: XXXXXXXXXX 同 组 成 员 名 单 : X X X 指 导 教 师 姓 名 : X X 指导教师评阅成绩: 指导教师评阅意见: .提交报告时间:2015 年 6 月 10 日1. 课程设计目标实验建立 C-编译器。只含有扫描程序(scanner)和语法分析(parser)部分。2. 分析与设计C-编译器设计的整体框架,本实验实现扫描处理和语法分析程序(图中粗黑部分)。打开源代码文件source.txt扫描处理(词法分析)记号语法分析程序语法树语义分析程序注释树源代
2、码优化程序中间代码代码生成器目标代码目标代码优化程序目标代码文字表记号表错误处理器2.1 、扫描程序 scanner 部分2.1.1 系统设计思想设计思想:根据 DFA 图用 switch-case 结构实现状态转换。惯用词法:1语言的关键字:elseifintreturnvoidwhile2专用符号:+-*/=!=;,()/*/3 其他标记是 ID 和 NUM,通过下列正则表达式定义:ID = letter letter* NUM = digit digit* letter = a|.|z|A|.|Z digit = 0|.|9大写和小写字母是有区别的4 空格由空白、换行符和制表符组成。空格
3、通常被忽略,除了它必须分开ID、NUM 关键字。5 注释用通常的 C 语言符号/ * . . . * /围起来。注释可以放在任何空白出现的位置(即注释不能放在标记内)上,且可以超过一行。注释不能嵌套scanner的DFA+ - * = = != ; , ( ) INASSIGNWhite space t n,=,!digit=NUMotherdigitotherSTARTletterDONEletterother/INIDSLAHother*other*INCOMMENTRETURN_INCOENDCOMMENT/MMENTother说明:当输入的字符使 DFA 到达接受状态的时候,则可以确定
4、一个单词了。初始状态设置为 START,当需要得到下一个 token 时,取得次 token 的第一个字符,并且按照DFA 与对此字符的类型分析,转换状态。重复此步骤,直到 DONE 为止,输出 token 类型。当字符为“/”时,状态转换为 SLAH 再判断下一个字符,如果为“*”则继续转到 INCOMMENT,最后以“*”时转到 ENDCOMMENT 状态,表明是注释,如果其他的则是字符停滞于当前字符,并且输出“/”。2.1.2 程序流程图源文件读取源文件一行输出读取一个字符否是否到达终态是赋值token输出token2.1.3 各文件或函数的设计说明扫描程序用到:scanner.h,sc
5、anner.cpp scanner.h:声明词法状态,词法分析/DFA 中的状态typedef enumSTART = 1, INNUM, INID, INDBSYM, DONE DFAState;/定义的 Token 的类型(31 种),分别对应于else、if、int、return、void、while、+、-、*、/、=、=、!=、=、;、,、(、)、/*、*/、num、id、错误、结束typedef enumELSE = 1,IF,INT,RETURN,VOID,WHILE, PLUS,MINUS,TIMES,OVER,LT,LEQ,GT,GEQ,EQ,NEQ,ASSIGN,SEMI,
6、COMMA,LPAREN,RP AREN,LMBRACKET,RMBRACKET,LBBRACKET,RBBRACKET,LCOMMENT,RCOMMENT, NUM,ID,ERROR,ENDFILE TokenType;/定义的 Token 结构体,包括类型、对应的串、所在代码的行号struct TokenTokenType tokenType; string tokenString; int lineNo;/每种 TokenType 对应的串,如 tokenTypeStringELSE=ELSEconststringtokenTypeString32=OTHER,ELSE,IF,INT,
7、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:定义 scanner.cpp 中函数 scanner.cpp 文件函数说明void Scanner : scan():设置输出结果界面以及设置各种输出状态。if(scanSuccess=fa
8、lse)cout词法分析出错!endl; elsecout词法分析成功了!endl;printToken();/*输出 Token 到文件 Token.txt 中*/正在删除注释void Scanner : deleteComments()TokenType Scanner :returnTokenType(string s)/返回 Token 的类型DFAState Scanner :charType(char c)/返回字符的类型typedef enum ENDFILE,ERROR, IF,ELSE,INT,RETURN,VOID,WHILE,/关键字ID,NUM,ASSIGN,PLUS,
9、MINUS,TIMES,OVER,EQ,UEQ,LT,LPAREN,RPAREN,SEMI,BT,LQ,BQ,DOU,LZGH,RZGH,LDGH,RDGH,/特殊字符:= + - * / = != declaration-list2. declaration-list-declaration-list declaration | declaration 3.declaration-var-declaration|fun-declaration4.var-declaration-type-specifier ID;|type-specfier IDNUM 5.type-specifier-in
10、t|void6.fun-specifier ID(parans) compound-stmt 7.params-params-list|void8.param-list-param-list,param|param9.param-type-specifier ID|type-specifier ID pound-stmt-local-declarations statement-list11.local-declarations-local-declarations var-declaration|empty 12.statement-list-statement-list statement
11、|empty13.statement-expression-stmt|compound-stmt|selection-stmt|iteration- stmt|return-stmt14.expression-stmt-expression;|;15.selection-stmt-if(expression)statement|if(expression)statement else statement16.iteration-stmt-while(expression)statement 17.return-stmt-return ;|return expression; 18.expres
12、sion-var=expression|simple-expression 19.var-ID|IDexpression20.simple-expression-additive-expressionrelopadditive- expression|additive-expression21.relop-=|=|=|!=22.additive-expression-additive-expression addop term|term 23.addop-+|-24.term-term mulop factor|factor 25.mulop-*|/26.factor-(expression)
13、|var|call|NUM 27.call-ID(args)28.args-arg-list|empty29.arg-list-arg-list,expression|expression2.1.2 语法分析程序流程图符号表文件获取终结符和非终结符构造文法分析表分析句型句子输出结果2.1.3 各文件或函数的设计说明语法分析程序包括:parser.cpp,parser.h parser.cpp:Parser : Parser()/界面设计TokenParser:getToken()/获取 scanner 中保存在 TokenList 数组中的Token,并且每次获取完之后数组下标指向下一个voi
14、d Parser : syntaxError(string s)/出错处理void Parser : match(TokenType ex)/匹配出错TreeNode * Parser : declaration(void)/类型匹配错误TreeNode*Parser:param_list(TreeNode*k)/k 可能是已经被取出来的VoidK,但又不是(void)类型的参数列表,所以一直传到 param 中去,作为其一个子节点 parse.h:对 parse.c 的函数声明/19 种节点类型,分别表示 int、id、void、数值、变量声明、数组声明、函数声明、函数声明参数列表、函数声明
15、参数、复合语句体、if、while、return、赋值、运算、数组元素、函数调用、函数调用参数列表、未知节点typedef enum IntK, IdK, VoidK, ConstK, Var_DeclK, Arry_DeclK, FunK, ParamsK, ParamK, CompK, Selection_StmtK, Iteration_StmtK, Return_StmtK, AssignK, OpK, Arry_ElemK, CallK, ArgsK, UnkownK Nodekind;typedef enum Void,Integer ExpType;ofstream fout_T
16、ree(tokenTree.txt);/输出语法树到文件/treeNode 定义包括子节点、兄弟节点、所处行号、节点类型、属性、表达式返回类型typedef struct treeNodeTreeNode * newNode(Nodekind k);/根据节点类型新建节点TreeNode * declaration_list(void);TreeNode * declaration(void); TreeNode * params(void);TreeNode * param_list(TreeNode * k); TreeNode * param(TreeNode * k); TreeNod
17、e * 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)
18、;TreeNode * simple_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.txt。/* A program to perform Eucilds Al
19、gorithm to compute gcd. */intgcd (int u, int v)if (v=0)return u; else returngcd(v,u-u/v*v); /* u-u/v*v= u mod v */void main(void)int x; int y;x=input(); y=input(); output(gcd(x,y);3. 程序代码实现按文件列出主要程序代码, 添加必要的注释.Scanner.cpp: #include #include #include #include #include scanner.h #include using namespa
20、ce std;/*Name: 词法分析器Copyright:Author: XXXDate: 19-05-14 12:00Description: 提取出 token*/Scanner : Scanner()scanSuccess = true; charIndex = 0;str = ; commentFlag = true; sourseString = ; lineCount = 0;void Scanner : scan()cout开始词法分析.endl; bool doubleSym = false;getSourseStringFromFile(sourseFile.txt); i
21、nt state = START;lineCount = 0; char ch; while(state6)ch = getNextChar(); if(0=ch)Token t;t.lineNo = lineCount; t.tokenString = ; t.tokenType = ENDFILE; tokenList.push_back(t); break;if(START=state)/初始状态和空格state = charType(ch); if(state!=START)str += ch;else if(INNUM=state)/digitstate = charType(ch)
22、; if(state!=INNUM)state = DONE;elsestr += ch;else if(INID=state)/letterstate = charType(ch); if(state!=INID)state = DONE;elsestr += ch;else if(INDBSYM=state)/除了=!之外的各种符号if(=ch)elsestr += ch; doubleSym = true;doubleSym = false;state = DONE;if(DONE=state)/接收状态int tp = 0;if(n=ch)tp = 1; Token t;t.lineN
23、o = lineCount-tp; t.tokenString = str;t.tokenType = returnTokenType(str); tokenList.push_back(t); if(ERROR=t.tokenType)scanSuccess = false;int lastState = charType(strstr.length()-1);if(lastState=INNUM|lastState=INID|(lastState=INDBSYM& doubleSym=false)backToLastChar(); str = ;state = START; if(doub
24、leSym=true)doubleSym = false;if(scanSuccess=false)cout词法分析出错!endl;elsecout词法分析成功了!endl;printToken();/输出 Token 到文件 Token.txt 中Token Scanner : getTokenAt(int tokenIndex)Token token; token.lineNo = lineCount; token.tokenString = ;token.tokenType = ENDFILE; if(tokenIndextokenList.size()token = tokenList
25、.at(tokenIndex+);return token;void Scanner : getSourseStringFromFile(string path)ifstream fin(path.c_str(); string temp;sourseString = ;while(getline(fin,temp)sourseString += temp; sourseString += n;fin.close(); charIndex = 0;void Scanner : deleteComments()cout正在删除注释.endl; ofstream fout_Sourse(sours
26、eFile.txt); int state = 1;char ch; while(state6)ch = getNextChar();if(0=ch)/文件结束break;if(1=state)if(/=ch)state = 2;elsestate = 1; fout_Soursech;else if(2=state)if(*=ch)elsestate = 3; commentFlag = false;state = 1; fout_Sourse/ch;else if(3=state)if(*=ch)state = 4;elsestate = 3;else if(4=state)if(*=ch)state = 4; else if(/=ch)state = 5;elsestate = 3;if(5=state)/结束状态,处理commentFlag = true; state = 1;if(!commentFlag)elsecout注释错误,没有结束符!endl; scanSuccess = false;cout注释已经成功删除!endl;TokenType Scanner :returnTo