编译原理课程设计___c语言编译器实现.docx
《编译原理课程设计___c语言编译器实现.docx》由会员分享,可在线阅读,更多相关《编译原理课程设计___c语言编译器实现.docx(46页珍藏版)》请在冰点文库上搜索。
扬州大学
编译原理课程设计
学 号:
091202122 姓 名:
专 业:
计算机科学与技术 课 程:
编译原理 指导教师:
陈宏建
目录
一.程序简介与分析---------------------------------------------------------
3
二.程序适用范围-----------------------------------------------------------
3
三.词法分析---------------------------------------------------------------
3
四.语法分析---------------------------------------------------------------
4
五.语义分析和中间代码生成------------------------------------------------
10
六.代码生成--------------------------------------------------------------
12
七.流程图----------------------------------------------------------------
13
八.实现------------------------------------------------------------------
14
九.程序运行结果----------------------------------------------------------
14
十.总结------------------------------------------------------------------
18
十一.附录(源程序)--------------------------------------------------------
18
简单的编译程序设计
一.程序简介与分析
本程序由四个部分组成:
词法分析子程序,语法分析子程序,语义分析子程序,目标代码生成程序。
本程序输入一个叫libo.txt的c语言源程序,然后对它进行词法,语法,语义分析,并输出汇编代码。
词法分析输入的是c语言源程序,输出的3是具有独立语法意义的单词符号。
语法分析以词法分析产生的编码流为输入,按照SLR
(1)分析方法进行语法分析,产生语法树,输出移进和归约的动作,如果源程序不符合文法,则有“语法分析出错”的提示。
语义分析阶段,在语法分析的同时,在归约的时候,给出相应的语义动作,最后输出中间代码四元式和新的符号表,如果有未声明的变量出现,则会提示出出错,并显示出此变量的名称。
代码生成阶段,将语义分析得到的中间代码四元式转化为汇编语言的目标代码并输出。
二.程序适用范围
本程序的使用范围为:
整型常量,四则运算(为了简化问题,本程序只考虑加法运算和乘法运算)和布尔表达式以及相应的赋值语句,条件转移语句和循环语句。
三.词法分析
根据词法分析的需要,我将源程序中的单词符号分为:
保留字,字母(标识符),界符三类,统一用一张表表示如下:
界符,保留字表
空格换行结束符
Y
单词
=
+
*
>
:
;
{
}
(
)
and
if
then
while
do
int
标志
符
编
码
1
2
3
4
5
6
7
8
9
10
31
32
33
35
36
37
25
程序从源程序文件libo.txt中一次读入一个字符,并判断它是不是字母,界符,保留字,空格,换行,结束符号或者非法字符。
流程图如下:
判断字符ch
判断是否要写入文
件
子程序结束
写入到磁盘文件
显示错误信息
出错处理
编号并输出
关闭文件
编号并输出
子程序继续
程序读入一个字符
ch
子程序开始
NN
词法分析流程图
四.语法分析
○1.源程序中涉及的文法G[P]定义如下表:
说明语句
表达式
布尔表达式
句法
0、P’→P
5、E→E+
11、B→B and
13、M→id=E
1、P→id()L;R
2、L→L;D
3、L→D
4、D→id:
int
T
6、E→T
7、T→T*
F
8、T→F
B
12、B→id>id
14、S→ifBthenM
15、S→whileBdoM
16、S→M
17、N→N;S
9、F→(E
18、N→S
)
10、F→i
19、R→{N}
d
○2.上述文法的每个非终结符的FIRST集和FOLLOW集如下表:
FIRST集
FOLLOW集
P
{id
}
{#}
L
{id
}
{;}
D
{id
}
{;}
E
{(,id
}
{},;,+,),#}
T
{(,id
}
{},;,+,),*,#}
F
{(,id
}
{},;,+,),*,#}
B
{id }
{then,do,and}
M
{id }
{},;}
S
{id,while,if}
{},;}
N
{id,while,if}
{},;}
R
{{ }
{#}
○3.文法G[P]的项目集部分如下:
0.P’→.P
1.P’→P.
2.P→.id()L;R
3.P→id.()L;R
4.
P→id(.)L;R
5.P→id().L;R
6.P→id()L.;R
7.
P→id()L;.R
8.P→id()L;R.
9.L→.L;D
10.L→L.;D
11.L→L;.D
12.
L→L;D.
13.D→.id:
int
14.D→id.:
int
15.
D→id:
.int
16.D→id:
int.
17.E→.E+T
18.
E→E.+T
19.E→E+.T
20.E→E+T.
21.
E→.T
22.
E→T.
23.
T→.T*F
24.
T→T.*F
25.
T→T*.F
26.
T→T*F.
27.
T→.F
28.
T→F.
29.
F→(E)
30.
F→(.E)
31.
F→(E.)
32.
F→(E).
33.
F→.id
34.
F→id.
○4.再由项目集构造文法的DFA活前缀。
为了方便,省去了项目族集的每个状态的项
有归约动作
12
8
5
:
6
int
7
说明语句
D
id
D
id
接受状态
11
R 10
;
9
L 4
)
3
(
2
id
0
P
1
{
if
23
B
24
then
25
M
26
18
id
and
id
句法
21
S 13 id 14
=
} if id
M
N
17
;
19
S
20
id
22
M
while
while
27 B 28 do 29 M 30
id
and
31
id
34
B
35
布尔表达式
>
and
32 id 33
目,直接在状态转换的箭头上标明终结符或非终结符。
对于有规约动作和接受的状态,将其特别标明。
文法G[P]的DFA图如下:
T
15
id
id
38
(
F
E
36
*
(
37
16
40
F
39
(
41
id
F
id +
E
(
表达式
42
+
43
)
T
45
44
*
G[P]:
SLR
(1)分析表
Action
goto
id
(
)
;
:
*
+
>
=
{
}
int
and
if
the
n
whil
e
do
$
P
D
R
E
T
F
B
M
S
L
N
0
1
2
3
4
5
6
7
8
9
1
0
1
1
1
2
1
3
1
4
1
5
1
6
17
0
1
2
3
4
5
6
7
8
9
1
0
0
s
2
1
1
acc
2
s
3
3
s
4
4
s
5
8
9
5
s
6
6
s
7
7
r
4
8
r
3
9
s
1
0
1
0
s5
s1
3
1
2
1
1
1
1
r1
1
2
r
2
1
3
s1
4
s2
3
s2
7
2
2
2
1
1
7
1
4
s1
5
1
5
s3
6
s4
1
1
6
3
8
3
7
1
6
r1
3
s4
3
r1
3
1
7
s1
9
s1
8
1
8
r19
1
9
s1
4
s2
3
s2
7
2
2
2
0
G[P]:
SLR
(1)分析表
Action
goto
id
(
)
;
:
*
+
>
=
{
}
int
and
if
the
n
whil
e
do
$
P
D
R
E
T
F
B
M
S
L
N
0
1
2
3
4
5
6
7
8
9
1
0
1
1
1
2
1
3
1
4
1
5
1
6
17
0
1
2
3
4
5
6
7
8
9
1
0
2
0
r1
7
r1
7
2
1
r1
8
r1
8
2
2
r
1
r
1
6
6
2
3
s3
1
2
4
2
4
s3
4
s2
5
2
5
s1
4
2
6
2
6
r1
4
r1
4
2
7
s3
1
2
8
2
8
s3
4
2
9
s1
4
s2
9
3
0
3
0
r1
5
r1
5
3
1
s3
2
3
2
s3
3
3
3
r1
2
r1
2
r1
2
3
4
s3
1
3
5
3
5
r1
1
r1
1
r1
1
3
6
r1
0
r1
0
r1
0
r1
0
r1
0
3
r
r
r
r
r
7
8
8
8
8
8
3
8
r6
r6
s3
9
r6
r6
3
9
s3
6
s4
1
4
0
G[P]:
SLR
(1)分析表
action
goto
id
(
)
;
:
*
+
>
=
{
}
int
and
if
the
n
whil
e
do
$
P
D
R
E
T
F
B
M
S
L
N
0
1
2
3
4
5
6
7
8
9
1
0
1
1
1
2
1
3
1
4
1
5
1
6
17
0
1
2
3
4
5
6
7
8
9
1
0
4
0
r
7
r
7
r
7
r
7
r
7
4
1
s3
6
s4
1
4
2
3
8
3
7
4
2
s4
5
s4
3
4
3
s3
6
s4
1
4
4
3
7
4
4
r5
r5
s3
9
r5
r5
4
5
r
9
r
9
r
9
r
9
r
9
五. 语义分析和中间代码生成
载语法分析过程中,随着分析的步步进展,根据每个产生式所对应的语义子程序(或语义规则描述的语义动作)进行翻译的办法称作语法制导翻译。
归约动作
语法制导翻译
翻译方案
E→E+T
E→E1+T
{E.place=newtemp;Emit(E.place’:
=’E1.place’+’T.place);}
E→T
E→T
{E.place:
=T.place;}
T→T*F
T→T1*F
{T.place=newtemp;
Emit(T.place’:
=’T1.place’+’F.place);}
T→F
T→F
{T.place:
=F.place;}
F→(E)
F→(E)
{F.place:
=E.place;}
F→id
F→id
{p:
=lookup(id.name);
ifp<>nilthenF.place:
=p
elseerror;}
B→BandB
B→B1andAB2
{backpatch(B1.truelist,A.quad);B.truelist:
=B2.truelist;B.falselist:
=merge(B1.falselist,B2.falselist);}A→∈{A.quad:
=nextquad}
B→id>id
B→id1>id2
{B.truelist:
=makelist(nextquad);B.falselist:
=makelist(nextquad+1);
emit(ifid1.place’>’id2.place’goto__’);
emit(’goto__’);}
M→id=E
M→id=E
{p:
=lookup(id.name);
ifp<>nilthenemit(p’:
=’E.place)elseerror;}
S→ifBthenM
S→ifBthenAM
{backpatch(B.truelist,A.quad)backpatch(B.falselist,nextquad)}A→∈{A.quad:
=nextquad}
S→whileBdoM
S→whileA1BdoA2M
{backpatch(B.truelist,A2.quad)backpatch(B.falselist,nextquad+1)emit(’goto’A1.quad)}A1→∈{A1.quad:
=nextquad}A2→∈{A2.quad:
=nextquad}
语法翻译生成的四元式如下:
六.代码生成
目标代码生成阶段的任务是把中间代码变换成特定机器上的绝对指令代码或可重定位的指令代码或汇编指令代码。
这是编译的最后阶段,它的工作与硬件系统结构和指令含义有关,这个阶段的工作很复杂,涉及到硬件系统功能部件的运用、机器指令的选择、各种数据类型变量的存储空间分配以及寄存器和后缓寄存器的调度等。
本程序生成的目标代码与0x8086微处理器兼容。
下面列举几个简单的四元式与汇编代码的转化列子:
○1.(+,A,B,T)→
MOV R,A;ADD R,B;ST R,T
○2. (*, A,B,T)→
MOV R,A;MUL R,B;ST R,T
○3.(J,_,_,L)→
JMP L
○4. (J>, A,B,L)→MOV R,A
CMP R,B
JB L
○5.(=,A,_,T)→
LD R,A
ST R,T
本程序生成的目标代码如下:
七.程序流程图
出错处理
编译程序结束
错误处理
目标代码生成程序
语义分析子程序
语法分析子程序
词法分析子程序
编译程序开始
编译程序流程图
八.实现
本程序运行的硬件环境为CPU1.66HZ,内存为768M.软件环境为windowsxp
系统,VisualC++环境。
九.程序运行结果
1.输入源文件路径:
2.输出保留字
3.输出符