软件设计综合实践实验报告
报告仓库:dekrt/Reports: HUST SSE Courses Reports | 华科软件学院课程报告 (github.com)
软件设计综合实践实验报告
1. 实验内容和要求
本实验通过一个类 C 语言的 C--(C Minus Minus,CMM)语言编译器的设计和实现来熟悉编译器的基本原理和概念,了解计算系统基本架构(机器硬件层抽象、 目标语言、语言编译和汇编语言等),熟练掌握 C 语言开发,并为后续课程的学习打下基础。
2. 斐波拉契数代码
1 | int fibonacci(int n) |
3. 词法分析程序
3.1 主要设计和实现思路
采用enum
进行状态码的描述,具体如下:
1 | typedef enum |
struct reservedWords
结构用来存储预置词
1 | static struct |
static int getNextChar(void)
与
static int ungetNextChar(void)
函数用于读取下个字符与回溯下个字符
TokenType getToken(void)
函数用于获取当前的token:
- 如果状态码是
START
,进行一次getNextChar()
:- 对于一元操作符,如
'+', '-', '*', '(', ')', ';', '{', '}'
等字符,直接给出currentToken - 对于可能存在的二元(多元)操作符,如
"= || ==", "< || <=", "> || >=", "! || !=", "/ || /*"
等状态,给定对应的状态码,进行进行进一步的判断 - break;
- 对于一元操作符,如
- 如果状态码是
INEQ
,则读取字符并判断是=
还是==
- 如果状态码是
INLT
,则读取字符并判断是<
还是<=
- 如果状态码是
INGT
,则读取字符并判断是>
还是>=
- 如果状态码是
INNE
,则读取字符并判断是!
还是!=
- 如果状态码是
INDIV
,则读取字符并判断是/*
还是/*
- 为了防止注释中可能的
*
进行干扰,采用INCOMMENT
和ENDCOMMENT
两种状态进行判断
- 为了防止注释中可能的
- 如果状态码是
INNUM
或者INID
,则进行读取 - 否则,输出错误信息
- 随后,对新的ID进行存储。
- 如果
TraceScan == true
,则调用UTIL.c
中的printToken()
函数,输出词法分析的结果 - 返回当前的Token
调用printToken()
函数进行token的打印,函数如下:
1 | void printToken(TokenType token, const char* lexeme) |
3.2 词法分析程序代码
1 |
|
3.3 实验演示
- 求三个整数中的最大值
1 | in Line: 2: get reserved word "int" |
- 给定 N,求 1 到 N 之和
1 | in Line: 1: get reserved word "int" |
- 计算第n个斐波那契数
1 | in Line: 1: get reserved word "int" |
4. Lex文件
4.1 Lex输入文件代码
1 | %{ |
4.2 实验演示
使用
flex cmm.l
命令生成lex.yy.c
将
main.c lex.yy.c util.c globals.h util.h scan.h
放入一个项目中,编译生成lexScanner.exe
使用
lexScanner .\fibonacci.cmm
命令进行词法分析,结果如下:
1 | in Line: 1: get reserved word "int" |
5. BNF语法描述
1 | 1 . program → declaration-list |
6. 语法分析程序
6.1 主要设计和实现思路
定义结点类型:
1
2
3
4
5
6
7
8
9
10typedef enum { StmtK, ExpK, DecK } NodeKind;
/* statement kind, expression kind, declaration kind */
typedef enum { IfK, WhileK, ReturnK, CallK, CompoundK } StmtKind;
/* if kind, while kind, return kind, call kind, compound kind */
typedef enum { OpK, IdK, ConstK, AssignK } ExpKind;
/* oprator kind, identifier kind, const(num) kind, assign kind */
typedef enum { ScalarDecK, FuncDecK } DecKind;
/* scalar declaration kind, function declaration kind */
typedef enum { Void, Integer, Function } ExpType;定义数据结构TreeNode:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26typedef struct treeNode
{
struct treeNode * child[MAXCHILDREN];
struct treeNode * sibling;
int lineno;
NodeKind nodekind;
union
{
StmtKind stmt;
ExpKind exp;
DecKind dec;
} kind;
TokenType op;
int val;
char *name;
ExpType functionReturnType;
ExpType variableDataType;
ExpType expressionType;
int isParameter;
struct treeNode *declaration;
} TreeNode;采用递归下降进行语法分析,参照C--语言的BNF语法,每个非终结符定义为一个函数,返回类型为TreeNode
下降过程中,如果根据BNF范式,如果后一语句不为空,则将前一语句作为后一语句的树根,将他们全部连接起来,然后依次向下进行递归调用,根据相应的函数进行分析。
分析结束后,调用
util.c
中的printTree()
函数进行语法树的输出,函数如下:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
static void printSpaces(void)
{
for (int i=0; i<indentno; ++i)
fprintf(listing, " ");
}
char *typeName(ExpType type)
{
static char i[] = "integer";
static char v[] = "void";
static char invalid[] = "<<invalid type>>";
switch (type)
{
case Integer: return i; break;
case Void: return v; break;
default: return invalid;
}
}
void printTree(TreeNode *tree)
{
int i;
INDENT;
while (tree != NULL)
{
printSpaces();
if (tree->nodekind == DecK)
{
switch(tree->kind.dec)
{
case ScalarDecK:
fprintf(listing,"[Scalar declaration \"%s\" of type \"%s\"]\n"
, tree->name, typeName(tree->variableDataType));
break;
case ArrayDecK:
fprintf(listing, "[Array declaration \"%s\" of size %d"
" and type \"%s\"]\n",
tree->name, tree->val, typeName(tree->variableDataType));
break;
case FuncDecK:
fprintf(listing, "[Function declaration \"%s()\""
" of return type \"%s\"]\n",
tree->name, typeName(tree->functionReturnType));
break;
default:
fprintf(listing, "<<<unknown declaration type>>>\n");
break;
}
}
else if (tree->nodekind == ExpK)
{
switch(tree->kind.exp)
{
case OpK:
fprintf(listing, "[Operator \"");
printToken(tree->op, "");
fprintf(listing, "\"]\n");
break;
case IdK:
fprintf(listing, "[Identifier \"%s", tree->name);
if (tree->val != 0) /* array indexing */
fprintf(listing, "[%d]", tree->val);
fprintf(listing, "\"]\n");
break;
case ConstK:
fprintf(listing, "[Literal constant \"%d\"]\n", tree->val);
break;
case AssignK:
fprintf(listing, "[Assignment]\n");
break;
default:
fprintf(listing, "<<<unknown expression type>>>\n");
break;
}
}
else if (tree->nodekind == StmtK)
{
switch(tree->kind.stmt)
{
case CompoundK:
fprintf(listing, "[Compound statement]\n");
break;
case IfK:
fprintf(listing, "[IF statement]\n");
break;
case WhileK:
fprintf(listing, "[WHILE statement]\n");
break;
case ReturnK:
fprintf(listing, "[RETURN statement]\n");
break;
case CallK:
fprintf(listing, "[Call to function \"%s()\"]\n",
tree->name);
break;
default:
fprintf(listing, "<<<unknown statement type>>>\n");
break;
}
}
else
fprintf(listing, "<<<unknown node kind>>>\n");
for (i=0; i<MAXCHILDREN; ++i)
printTree(tree->child[i]);
tree = tree->sibling;
}
UNINDENT;
}
6.2 递归下降语法分析程序代码
1 |
|
6.3 实验演示
求三个整数中的最大值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48[Function declaration "max()" of return type "integer"]
[Scalar declaration "x" of type "integer"]
[Scalar declaration "y" of type "integer"]
[Scalar declaration "z" of type "integer"]
[Compound statement]
[Scalar declaration "biggest" of type "integer"]
[Assignment]
[Identifier "biggest"]
[Identifier "x"]
[IF statement]
[Operator ">"]
[Identifier "y"]
[Identifier "biggest"]
[Assignment]
[Identifier "biggest"]
[Identifier "y"]
[IF statement]
[Operator ">"]
[Identifier "z]"]
[Identifier "biggest"]
[Assignment]
[Identifier "biggest"]
[Identifier "z"]
[RETURN statement]
[Identifier "biggest"]
[Function declaration "main()" of return type "void"]
[Compound statement]
[Scalar declaration "x" of type "integer"]
[Scalar declaration "y" of type "integer"]
[Scalar declaration "z" of type "integer"]
[Scalar declaration "biggest" of type "integer"]
[Assignment]
[Identifier "x"]
[Call to function "input()"]
[Assignment]
[Identifier "y"]
[Call to function "input()"]
[Assignment]
[Identifier "z"]
[Call to function "input()"]
[Assignment]
[Identifier "biggest"]
[Call to function "max()"]
[Identifier "x"]
[Identifier "y"]
[Identifier "z"]
[Call to function "output()"]
[Identifier "biggest"]给定 N,求 1 到 N 之和
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41[Function declaration "sum()" of return type "integer"]
[Scalar declaration "n" of type "integer"]
[Compound statement]
[Scalar declaration "result" of type "integer"]
[Scalar declaration "i" of type "integer"]
[Assignment]
[Identifier "i"]
[Literal constant "1"]
[Assignment]
[Identifier "result"]
[Literal constant "0"]
[WHILE statement]
[Operator "<="]
[Identifier "i"]
[Identifier "n"]
[Compound statement]
[Assignment]
[Identifier "result"]
[Operator "+"]
[Identifier "result"]
[Identifier "i"]
[Assignment]
[Identifier "i"]
[Operator "+"]
[Identifier "i"]
[Literal constant "1"]
[RETURN statement]
[Identifier "result"]
[Function declaration "main()" of return type "void"]
[Compound statement]
[Scalar declaration "n" of type "integer"]
[Scalar declaration "s" of type "integer"]
[Assignment]
[Identifier "n"]
[Call to function "intput()"]
[Assignment]
[Identifier "s"]
[Call to function "sum()"]
[Identifier "n"]
[Call to function "output()"]
[Identifier "s"]计算第n个斐波那契数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61[Function declaration "fibonacci()" of return type "integer"]
[Scalar declaration "n" of type "integer"]
[Compound statement]
[Scalar declaration "cnt" of type "integer"]
[Scalar declaration "firstFib" of type "integer"]
[Scalar declaration "secondFib" of type "integer"]
[Scalar declaration "fib" of type "integer"]
[Assignment]
[Identifier "firstFib"]
[Literal constant "1"]
[Assignment]
[Identifier "secondFib"]
[Literal constant "1"]
[Assignment]
[Identifier "cnt"]
[Literal constant "2"]
[IF statement]
[Operator "=="]
[Identifier "n"]
[Literal constant "1"]
[RETURN statement]
[Literal constant "1"]
[IF statement]
[Operator "=="]
[Identifier "n"]
[Literal constant "2"]
[RETURN statement]
[Literal constant "1"]
[Compound statement]
[WHILE statement]
[Operator "<"]
[Identifier "cnt"]
[Identifier "n"]
[Compound statement]
[Assignment]
[Identifier "fib"]
[Operator "+"]
[Identifier "firstFib"]
[Identifier "secondFib"]
[Assignment]
[Identifier "firstFib"]
[Identifier "secondFib"]
[Assignment]
[Identifier "secondFib"]
[Identifier "fib"]
[Assignment]
[Identifier "cnt"]
[Operator "+"]
[Identifier "cnt"]
[Literal constant "1"]
[RETURN statement]
[Identifier "fib"]
[Function declaration "main()" of return type "void"]
[Compound statement]
[Scalar declaration "n" of type "integer"]
[Assignment]
[Identifier "n"]
[Call to function "input()"]
[Call to function "output()"]
[Call to function "fibonacci()"]
[Identifier "n"]
7. 语义分析程序
7.1 主要设计和实现思路
7.1.1 符号表构造
首先通过void buildSymbolTable(TreeNode *syntaxTree)
函数进行符号表构造
static void drawRuler(FILE *output, char *string)
函数,用于确定符号表的格式,打印分割线static void declarePredefines(void)
函数,用来将C--语言内置的input()
和output()
函数添加进符号表static void startBuildSymbolTable(TreeNode *syntaxTree)
函数开始构造符号表:- 该函数的参数为语法树根结点,通过遍历整个语法树,来寻找结点类型为DECK(声明结点)的结点,并将他们插入到符号表中,插入的过程中将进行检测。
- 声明也分为两种:变量的声明与函数的声明:变量的声明可直接插入到符号表;而函数的声明中可能有变量声明,此时,将会调用之前提到过的
drawruler()
函数,增加一张符号表,用于处理该函数内部的变量声明。 - 对于非声明类结点,只需进行错误检测,即在既有的符号表中查询其是否进行过声明。
7.1.2 类型检查
首先通过traverse(syntaxTree, nullProc, checkNode)
函数,检查相邻语法树结点的词法属性来判断是否出错。
static void nullProc(TreeNode *syntaxTree)
函数直接返回(即遇到叶子结点),不进行其他操作static void checkNode(TreeNode *syntaxTree)
函数通过遍历语法树,遍历到当前的一个结点之后,检查该结点的相邻结点是否符合语法规则,如果不符合就报错,如果符合就可以继续遍历。
7.2 类型检查语义分析程序代码
7.2.1 symtab.c
1 |
|
7.2.2 analyse.c
1 |
|
7.3 实验演示
1 | Scope Identifier Line Is a Symbol type |