编译原理实验指导书

目 录
相关问题说明 1
实验题 2
实验1 词法分析（2课时） 3
实验2 语法分析（2课时） 5
实验3 语义分析（2课时） 7
实验4 代码生成（2课时） 9
参考书目 11


相关问题说明
课程4实验
课程中实现程序普通CC++程序Windows环境属控制台应程序
提交实验成果：
1 实验成果包括：
n 源程序学号加姓名方式命名项目源程序目录例学号：090510xxx姓名：某某目录名：090510xxx某某源程序编译文件
n 实验报告
2 实验报告班干部收齐实验次课时交（实验外）源程序发邮箱
实验成果评价标准：
1 时提交实验成果期交计成绩
2 实验成果雷者计成绩
3 实验报告采手写方式书写格式计算机信息工程系求执行求办事计成绩
4 实验成果完整缺源程序实验报告者计成绩
5 实验报告容充实够真实反映实验情况酌情加分
6 实验报告字迹工整酌情加分
7 存加分性
实验时间点：
班级
周次
星期
节次
实验室
信051
79111316
1
12
东7405
软件工程062
14
1
12
东7405
软件工程071
18
1
12
东7405
计算机062
791112141617
1
12
东7406
信息理071
18
1
12
东7406
信息理061
16
1
12
东7408
信息理071
4711131517
1
12
东7408
软件工程061
914
1
12
东7408
信息理062
16
1
12
东7412
软件工程071
1112131415
1
12
东7412
软件工程062
9
1
12
东7412
计算机051
13141516
1
12
东7413
物流理082
78910111213141516
1
12
东8405
广告学081
78910111213141516
1
12
东8409
信息理051
131415161718
1
34
东7405
计算机052
13141516
1
34
东7406
信061
11121718
1
34
东7406
网络工程091
891112
2
56
东8413
信052
79111316
1
34
东7412
信061
15
1
34
东7412
计科051
4681012141618
1
34
东7413
计算机应081
17
1
34
东7413
艺术设计084
14
1
34
东8405
计算机应081
45678910111213141516
1
34
东8409
信息计算科学061
11121314
1
中午
东7405
软件工程081
89101112131415
1
中午
东7406
软件工程061
91011121314
1
中午
东7408
软件工程062
91011121314
1
中午
东7412
软件工程071
13141516
1
中午
东7413
计算机063
791112141617
1
中午
东8405
计算机应082
4567891011121314151617
1
中午
东8409
艺术设计084
1315
1
56
东7405
计算机061
10121416
1
57
东7405
电信科学082
78910111213141516
1
56
东7406
计算机053
13141516
1
56
东7408
艺术设计084
789101112
1
56
东7408
信息计算081
89101112131415
1
56
东7412
艺术设计084
16
1
56
东7412
信息理052
131415161718
1
56
东7413
艺术设计081
78910111213141516
1
56
东8405
国际贸易081
78910111213141516
1
56
东8409
信062
1112151718
1
78
东7406
电信科学081
1314
1
78
东7406
电信科学081
1516
1
78
东7408
信息计算科学062
11121314
1
78
东7408
艺术设计083
78910111213141516
1
78
东7412
软件工程072
13141516
1
78
东7413
电信科学081
789101112
1
78
东7413
艺术设计082
78910111213141516
1
78
东8405
金融学081
78910111213141516
1
78
东8409
信051
18
2
12
东7405
计算机应081
17
2
12
东7408
计算机应081
5678910111213141516
2
12
东7412
计科052
4681012141618
2
12
东7413
计算机051
1415
2
12
东8405
计算机科学081
89101112131415
2
12
东8409
计算机应082
567891011121314151617
2
34
东7405
计算机061
17
2
34
东7406
网络工程081
89101112131415
2
34
东7406
软件工程061
141516
2
34
东7408
计科051
17
2
34
东7408
计科051
141516
2
34
东7412
计科051
89111213
2
34
东7413
计算机052
1415
2
34
东7413
计算机061
7911121416
2
34
东8405
计科(成)
68101214
2
34
东8409
信052
18
2
中午
东7405
软件工程062
141516
2
中午
东7412
信051
568101213141516
2
56
东7405
信息理061
89101112131415
2
56
东7406
软件工程072
18
2
56
东7406
软件工程072
1112131415
2
56
东7408
信051
17
2
56
东7413
计科052
89111213
2
56
东7413
信息理082
89101112131415
2
56
东8405
理类0807
78910111213141516
2
56
东8409
信052
568101213141516
2
78
东7405
信息理062
89101112131415
2
78
东7406
信052
17
2
78
东7413
计科053
89111213
2
78
东7413
电气类0806
89101112131415
2
78
东8405
艺术设计086
78910111213141516
2
78
东8409
公选
6789101112
2
911
东740812
信息理051
89141516
3
12
东7405
信息理061
1116
3
12
东7408
软件工程061
691314
3
12
东7408
信息理062
1116
3
12
东7412
软件工程062
691314
3
12
东7412
计科053
4681012141618
3
12
东7413
广告051
37
3
12
东7413
广告学082
78910111213141516
3
12
东8409
信052
1011131618
3
34
东7405
计算机071
18
3
34
东7406
计算机071
1112131415
3
34
东7408
计科052
17
3
34
东7408
计科052
141516
3
34
东7412
广告052
37
3
34
东7413
信息理072
17
3
34
东7413
计算机053
1415
3
34
东8405
信息理071
151617
3
中午
东7405
信051
18
3
中午
东7405
汉语言061
57111315
3
中午
东7406
网络工程071
111213141518
3
中午
东7408
计算机063
1011121314
3
中午
东7409
计算机061
131517
3
中午
东7412
计算机063
151617
3
中午
东7413
软件工程061
4681012141516
3
中午
东8405
软件工程082
89101112131415
3
中午
东8409
信051
10111316
3
56
东7405
行政理071
57111315
3
56
东7406
信息理052
78
3
56
东7413
行政理061
10111213
3
57
东7413
信息理072
151617
3
57
东7413
电气类0807
89101112131415
3
56
东8405
行政理081
78910111213141516
3
56
东8409
计算机062
17
3
68
东7408
计算机062
1315
3
68
东7412
汉语言062
57111315
3
78
东7406
软件工程062
4681012141516
3
78
东7408
信息理052
789
3
78
东7413
行政理062
10111213
3
810
东7413
校公选
789101112
3
911
东740812
计算机063
131517
3
911
东7412
软件工程061
678910111213
4
12
东7405
信息理072
1718
4
12
东7405
计算机061
1011121314
4
12
东7409
信息理072
47111315
4
12
东7412
计算机061
151617
4
12
东7413
信息理081
89101112131415
4
12
东8405
电气类083
89101112131415
4
12
东8409
网络工程092
891112
2
56
东8415


实验题
编译整数四运算表达式整数四运算表达式翻译汇编语言代码
整数四运算文法：
+ | |
* | |
() | num
消左递

+ | |ε

* | | ε
() | num
中非终结符+*()num终结符
词法：
1． 运算符：+ *
2． 界符：( )
3． num非负整数
4． 空白包括空格换行符水制表符分开运算符界符num包括换行符时换行符成表达式终结标志


实验1 词法分析（2课时）
实验目：解词法分析器功输出形式掌握词法分析器设计原理方法
实验容：设计实现整数四运算表达式词法分析程序
实验求：编写程序机调试测试纪录调试测试情况结合程序进行分析
实验环境：Visual C++ 60版Windows 2000版汇编工具（Software子目录）
实现点提示：
需实现词法分析程序功接受表达式输出该表达式中类单词符号测试词法分析程序时定格式输出类单词符号
单词符号种类属类型定义
typedef enum Symbol { ERR 1 END NUM PLUS MINUS TIMES
SLASH LPAREN RPAREN } Symbol
运算符界符需处理种类编码num需处理应具体属性信息ERR表示词法分析错END表示表达式分析结束例1+2*(3+4)应单词符号序列
NUM 1
+
NUM 2
*
(
NUM 3
+
NUM 4
)
词法分析函数原型
Symbol gettoken()
实现具体方法参考文献[1]中4446页里涉ReserveInsertIdInsertConst实现程中会isdigitisspacegetcharungetcatoi等函数时注意包含相关头文件
状态转换图



实验2 语法分析（2课时）
实验目：理解分析法基思想理解递降分析法基思路掌握构造递降子程序方法
实验容：运递降子程序法实现整数四运算表达式语法分析程序
实验求：编写程序机调试测试纪录调试测试情况结合程序进行分析
实验环境：Visual C++ 60版Windows 2000版汇编工具（Software子目录）
实现点提示：
需实现语法分析程序功接受表达式分析该表达式根输入正确否出相应信息测试时果输入表达式分析正确输出表示分析正确信息否输出表示分析错误信息
分析程序组递程组成文法中非终结符应程分析程中语法分析程序需调实验1实现词法分析程序
全局程变量：
ADVANCE输入串指示器IP指输入符号读入单字符号
SYMIP前指输入符号
ERROR出错处理子程序
非终结符应子程序定义分析程中需某非终结符出发进行展开(推导)时调非终结符应子程序
例：定文法G(E)：
E→TE＇
E＇→+TE＇ |ε
T→FT＇
T＇→*FT＇ |ε
F→(E) | i
应递子程序
PROCEDURE E
BEGIN
TE＇
END
PROCEDURE E＇
IF SYM+’ THEN
BEGIN
ADVANCE
TE＇
END
PROCEDURE T
BEGIN
FT＇¢
END
PROCEDURE T＇
IF SYM*’ THEN
BEGIN
ADVANCE
FT＇¢
END
PROCEDURE F
IF SYMi’ THEN ADVANCE
ELSE IF SYM(’ THEN
BEGIN
ADVANCE
E
IF SYM)’ THEN ADVANCE
ELSE ERROR
END ELSE ERROR
程序：
PROGRAM PARSER
BEGIN
ADVANCE
E
IF SYM <>’#’ THEN
ERROR
END
者应递子程序：

PROCEDURE E
BEGIN
TE＇
END
PROCEDURE T
BEGIN
FT＇
END
PROCEDURE E＇
IF SYM+’ THEN
BEGIN
ADVANCE
TE＇
END ELSE IF SYM<>#’ AND
SYM<>’)’ THEN ERROR
PROCEDURE T＇
IF SYM*’ THEN
BEGIN
ADVANCE
FT¢
END ELSE IF SYM<>#’ AND
SYM<>’)’AND SYM<>’+’ THEN ERROR
PROCEDURE F
IF SYMi’ THEN ADVANCE
ELSE IF SYM(’ THEN
BEGIN
ADVANCE
E
IF SYM)’ THEN ADVANCE
ELSE ERROR
END ELSE ERROR
程序：
PROGRAM PARSER
BEGIN
ADVANCE
E
END
具体实现语法分析程序时ADVANCE功实验1中gettoken实现程序中设置全局变量nexttokenSYM应保存调gettoken时返回结果ERROR种简单实现输出错误提示然调exit程序立终止执行
实现整数四运算表达式语法分析程序时面例子基础修改扩充

实验3 语义分析（2课时）
实验目：理解属性文法理解语法制导翻译基思想方法
实验容：设计实现实现整数四运算递降翻译器
实验求：编写程序机调试测试纪录调试测试情况结合程序进行分析
实验环境：Visual C++ 60版Windows 2000版汇编工具（Software子目录）
实现点提示：
需实现语义分析程序功接受表达式分析该表达式分析程中建立该表达式抽象语法树四运算表达式抽象语法树基作二叉树中序遍历序列应该输入表达式样——没括号外输出中序遍历序列检测程序功否正确果分支节点时变量标记四运算表达式抽象语法树进行序遍历输入表达式应四元式序列（实验4样四元式序列）例输入1+2*(3+4)应抽象语法树中序遍历序列四元式序列分
1 + 2 * 3 + 4

+ 3 4 T1
* 2 T1 T2
+ 1 T2 T3
抽象语法树种类型定义
typedef int ValType
typedef struct ASTNode {
Symbol sym
ValType val
struct ASTNode * arg1 *arg2
} ASTNode *AST
创建节点操作
ASTNode *mknode(Symbol op ASTNode *arg1 ASTNode *arg2)
返回新创建运算节点标号op域arg1arg2分指棵子树
ASTNode *mkleaf(Symbol sym ValType val)
返回新创建数节点标号num域val存放数值
建立抽象语法树语义规
E E1 + T Enptr mknode( +’ E1nptr Tnptr )
E E1 – T Enptr mknode( ’ E1nptr Tnptr )
E T Enptr Tnptr
T T1 * F Tnptr mknode( *’ T1nptr Fnptr )
T T1 F Tnptr mknode( ’ T1nptr Fnptr )
T F Tnptr Fnptr
F (E) Fnptr Enptr
F num Fnptr mkleaf(num numval )
消左递翻译模式
E T {E＇iTnptr}
E＇ {EnptrE＇s}
E＇ + T {E＇1imknode(+’E＇iTnptr)}
E＇1 {E＇sE1s}
E＇ T {E＇1imknode(’E＇iTnptr)}
E＇1 {E＇sE1s}
E＇ ε {E＇s E＇i}
T F {T＇iFnptr}
T＇ {TnptrT＇s}
T＇ * F {T＇1imknode(*’T＇iFnptr)}
T＇1 {T＇sT1s}
T＇ F {T＇1imknode(’T＇iFnptr)}
T＇1 {T＇sT1s}
T＇ ε {T＇s T＇i}
F (E) {FnptrEnptr}
F num {Fnptrmkleaf(numnumval)}
递降翻译器设计参考文献[1]中156158页具体实现时实验2中实现语法分析程序基础进行修改实现表达式递降翻译器


实验4 代码生成（2课时）
实验目：理解代码生成程中基问题
实验容：设计实现表达式代码生成程序
实验求：编写程序机调试测试纪录调试测试情况结合程序进行分析
实验环境：Visual C++ 60版Windows 2000版汇编工具（Software子目录）
实现点提示：
需代码生成程序功实验3语义分析程序四元式输出作输入输出汇编语言程序例1+2*(3+4)应输出
386
MODEL FLAT

ExitProcess PROTO NEAR32 stdcall dwExitCodeDWORD

INCLUDE ioh header file for inputoutput

cr EQU 0dh carriage return character
Lf EQU 0ah line feed

STACK 4096 reserve 4096byte stack

DATA reserve storage for data
t DWORD 40 DUP ()
label1 BYTE cr Lf The result is
result BYTE 11 DUP ()
BYTE cr Lf 0
CODE start of main program code
_start

mov eax 3
add eax 4
mov t+0 eax

mov eax 2
mov ebx t+0
mul ebx
mov t+4 eax

mov eax 1
add eax t+4
mov t+8 eax

mov eax t+8
dtoa result eax convert to ASCII characters
output label1 output label and sum
INVOKE ExitProcess 0 exit with return code 0
PUBLIC _start make entry point public
END end of source code
输出汇编代码鉴文献[2]中格式假定面汇编程序保存文expressionasm中expressionasm复制汇编器目录然命令提示符汇编器目录次执行
ml c coff expressionasm
link debug subsystemconsole entrystart out expressionexe expressionobj
ioobj kernel32lib
expression
会
The result is 15
注意面link行应该连续输入方便起见汇编器目录批处理文件compilebat执行
compile expression
完成面三步完成务
生成汇编代码中
t DWORD 40 DUP ()
定义40双字（占4字节）作时变量根需调整更方法栈中分配时变量
生成代码时需考虑生成_startdtoa result eax间汇编码开头_start部分dtoa result eax结尾部分汇编码例子原样输出
通分析1+2*(3+4)四元式序列汇编码应关系考虑四元式翻译汇编码需特注意寻址方式问题法法翻译
汇编程序例子中成分含义参考文献[2]目录中文献[2]英文版电子书


参考书目
[1] 陈火旺等 程序设计语言编译原理（第3版） 北京：国防工业出版社20091
[2] Richard C Detmer 80x86汇编语言计算机体系结构（英文版） 北京：机械工业出版社200411

文档香网(httpswwwxiangdangnet)户传

《香当网》用户分享的内容，不代表《香当网》观点或立场，请自行判断内容的真实性和可靠性！
该内容是文档的文本内容，更好的格式请下载文档