C-Minus词法分析和语法分析设计编译器编译原理课程设计

编译原理课程设计报告

课题名称： C- Minus词法分析和语法分析设计

1. 课程设计目标

实验建立C-编译器。只含有扫描程序（scanner）和语法分析（parser）部分。

2. 分析与设计

C-编译器设计的整体框架，本实验实现扫描处理和语法分析程序（图中粗黑部分）。

打开源代码文件source.txt扫描处理（词法分析）记号语法分析程序语法树语义分析程序错误处理器注释树记号表源代码优化程序文字表中间代码代码生成器目标代码目标代码优化程序目标代码

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|..|Z digit = 0|..|9

大写和小写字母是有区别的

④ 空格由空白、换行符和制表符组成。空格通常被忽略，除了它必须分开ID、NUM关键字。

⑤ 注释用通常的C语言符号/ * . . . * /围起来。注释可以放在任何空白出现的位置(即注释不能放在标记内)上，且可以超过一行。注释不能嵌套

scanner的DFA+ - * <= >= == != ; , ( ) [] { }INASSIGNWhite space \\t \\n>,<,=,!digitNUM[other]=digitSTARTletter/INIDletter[other]DONE[other]ZHU*/INCOMMENT[other][other][other]*ZZHU*

说明：当输入的字符使DFA到达接受状态的时候，则可以确定一个单词了。初始状态设置为START，当需要得到下一个token时，取得次token的第一个字符，并且按照DFA与对此字符的类型分析，转换状态。重复此步骤，直到DONE为止，输出token类型。当字符为“/”时，状态转换为SLAH再判断下一个字符，如果为“*”则继续转到INCOMMENT，最后以“*”时转到ENDCOMMENT状态，表明是注释，如果其他的则是字符停滞于当前字符，并且输出“/”。 2.1.2程序流程图

源文件读取源文件一行输出读取一个字符否是否到达终态是赋值token输出token

2.1.3 各文件或函数的设计说明

扫描程序用到:scanner.h,scanner.cpp ? scanner.h：声明词法状态，词法分析 //DFA中的状态 typedef enum {

START = 1, INNUM, INID, INDBSYM, DONE

} DFAState;

//定义的Token的类型(31种)，分别对应于else、if、int、return、void、while、+、-、*、/、<、<=、>、>=、==、!=、=、;、,、(、)、[、]、{、}、/*、*/、num、id、错误、结束 typedef enum {

ELSE = 1,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 } TokenType;

//定义的Token结构体，包括类型、对应的串、所在代码的行号 struct Token {

TokenType tokenType; string tokenString; int lineNo; };

//每种TokenType对应的串，如tokenTypeString[ELSE]==\

const string tokenTypeString[32] = {\\\\\\\\\\\\\\\\\\\\\\\\\\\\

class Scanner:定义scanner.cpp中函数 ? scanner.cpp文件函数说明

void Scanner :: scan()：设置输出结果界面以及设置各种输出状态。

if(scanSuccess==false)

cout<<\词法分析出错！\cout<<\词法分析成功了！\else

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,MINUS,TIMES,OVER,EQ,UEQ,LT,LPAREN,RPAREN,SEMI,BT,LQ,BQ, DOU,LZGH,RZGH,LDGH,RDGH,//特殊字符：= + - * / == != < 等 } TokenType;

2.1.4 测试程序说明

根据附录A后面的例子，程序输入两个整数，计算并打印出它们的最大公因子，保存为a.txt。

/* A program to perform Eucild's Algorithm to compute gcd. */ int gcd (int u, int v) {

if (v==0) return u; else return

gcd(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)); }

2.2、语法分析parse部分

2.2.1系统设计思想

设计思想：parser用递归下降分析方法实现,通过调用词法分析函数getToken实现语法分析。

根据C-语言的规则，得出BNF语法如下：

1.program->declaration-list

2.declaration-list->declaration-list declaration | declaration 3.declaration->var-declaration|fun-declaration

4.var-declaration->type-specifier ID;|type-specfier ID[NUM] 5.type-specifier->int|void

6.fun-specifier ID(parans) compound-stmt 7.params->params-list|void

8.param-list->param-list,param|param

9.param->type-specifier ID|type-specifier ID [] 10.compound-stmt->{local-declarations statement-list}

11.local-declarations->local-declarations var-declaration|empty 12.statement-list->statement-list statement|empty

13.statement->expression-stmt|compound-stmt|selection-stmt|iteration-stmt|return-stmt

14.expression-stmt->expression;|;

15.selection-stmt->if(expression)statement|if(expression)statement else

statement

16.iteration-stmt->while(expression)statement 17.return-stmt->return ;|return expression; 18.expression->var=expression|simple-expression 19.var->ID|ID[expression]

20.simple-expression->additive-expression

additive-expression|additive-expression

21.relop-><=|<|>|>=|==|!=

22.additive-expression->additive-expression addop term|term 23.addop->+|-

24.term->term mulop factor|factor 25.mulop->*|/

26.factor->(expression)|var|call|NUM 27.call->ID(args) 28.args->arg-list|empty

29.arg-list->arg-list,expression|expression 2.1.2语法分析程序流程图

relop

符号表文件获取终结符和非终结符构造文法分析表分析句型句子输出结果 2.1.3 各文件或函数的设计说明

语法分析程序包括：parser.cpp,parser.h ? parser.cpp：

Parser :: Parser()//界面设计

Token Parser :: getToken()//获取scanner中保存在TokenList数组中的Token，并且每次获取完之后数组下标指向下一个

void 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、数值、变量声明、数组声明、函数声明、函数声明参数列表、函数声明参数、复合语句体、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_Tree(\输出语法树到文件

//treeNode定义 包括子节点、兄弟节点、所处行号、节点类型、属性、表达式返回类型 typedef struct treeNode

TreeNode * newNode(Nodekind k);//根据节点类型新建节点

TreeNode * declaration_list(void); TreeNode * declaration(void); TreeNode * params(void);

TreeNode * param_list(TreeNode * k); TreeNode * param(TreeNode * 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 * 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 Eucild's

本文来源：https://www.bwwdw.com/article/1rgt.html