武汉理工大学《编译原理》课程设计
学 号：
0120610340420
课 程 设 计
题 目
DO-WHILE 循环语句的翻译程序
设计（LL（1）法、输出四元
式）
学 院 计算机科学与技术学院
专 业 计算机科学与技术
班 级
0604
姓 名 魏哲
指导教师 林泓
2009
年
6
月
21
日
1
武汉理工大学《编译原理》课程设计
课程设计任务书
学生姓名： 魏 哲 专业班级： 计算机
0604
班
指导教师： 林 泓 工作单位：计算机科学与技术学院
题目: DO-WHILE 循环语句的翻译程序设计（LL（1）法、输出四元
式）
初始条件：
理论：学完编译课程，掌握一种计算机高级语言的使用。
实践：计算机实验室提供计算机及软件环境。如果自己有计算机可以在其上进
行设计。
要求完成的主要任务: （包括课程设计工作量及其技术要求，以及说明书撰写等具体要
求）
（1） 写出符合给定的语法分析方法的文法及属性文法。
（2） 完成题目要求的中间代码四元式的描述。
（3） 写出给定的语法分析方法的思想，完成语法分析和语义分析程序设计。
（4） 编制好分析程序后，设计若干用例，上机测试并通过所设计的分析程序。
（5） 设计报告格式按附件要求书写。课程设计报告书正文的内容应包括：
1 系统描述（问题域描述）；
2 文法及属性文法的描述；
3 语法分析方法描述及语法分析表设计；
4 按给定的题目给出中间代码形式的描述及中间代码序列的结构设计；
5 编译系统的概要设计；
6 详细的算法描述（流程图或伪代码）；
7 软件的测试方法和测试结果；
8 研制报告（研制过程，本设计的评价、特点、不足、收获与体会等）；
9 参考文献（按公开发表的规范书写）。
时间安排：
设计安排一周：周 1、周 2：完成系统分析及设计。
周 3、周 4：完成程序调试及测试。
周 5：撰写课程设计报告。
设计验收安排：设计周的星期五第 1 节课开始到实验室进行上机验收。
设计报告书收取时间：设计周的次周星期一上午 10 点。
2
武汉理工大学《编译原理》课程设计
指导教师签名： 2009 年 5 月 23 日
系主任（或责任教师）签名： 2009 年 5 月 23 日
DO-WHILE 循环语句的翻译程序设
计
（LL（1）法、输出四元式）
1 问题描述
要求用 LL(1)自顶向下分析方法及四元式中间代码，对 DO-WHILE 循环语句完成编译
各阶段过程，包括词法、语法、语义等分析。
2 问题分析
编译过程一般分为六个阶段的过程，可以由六个模块完成，它们称为词法分析程序、
语法分析程序、语义分析程序、中间代码生成程序、代码优化程序、目标代码生成程序，
此外，一个完整编译程序还必须包括“表格管理程序”和“出错处理程序”。
此实验涉及到词法分析、语法分析、语义分析及表格管理和出错处理。其中，词法分
析要能识别关键字“do”和“while”，标示符（这里只指变量）等；语法分析要能分析程序
结构的合法性，即是否为文法的句子；语义分析要能语法制导翻译出中间代码（四元
式）；表格管理是指符号表；出错处理是指在语法分析时，所有非文法句子的错误类型
处理。
3 系统设计
3.1 数据结构
词法分析扫描键盘敲入的字符串，接收到数组 var[MAX]，得到单词序列的同时，将
变量都替换成“i”，并保存副本于字符数组 arr_i[MAX] ；将“do”和“while”换成文法里的
“d”和“w”；最后存放符合文法格式的单词序列于队列 queue[MAX]。
语法分 析所用到的文法 事 先存在二维数组 p[MAX][MAX],VT[MAX]存储终结符，
3
武汉理工大学《编译原理》课程设计
VN[MAX]存储非终结符；LL(1)分析过程是一栈一流，要用到堆栈 stack[MAX]和队列
queue[MAX]，其中 sp 和 front 分别指向栈顶和队首；每次分析以栈顶 X= stack[sp]
和队首 a= queue[front]作为预测分析表 M[MAX][MAX]的下标元素，去检索非终结符
X 遇到终结符 a 所选的产生式，其中 M[MAX][MAX]的值就是产生式序号；最后将推导
过程中所有产生式序列存于 td[MAX]。
语义分析用 opr 和 opd 分别代表当前已匹配好的算符和操作数，用 arr[MAX][4]存
放待输出的四元式。
3.2 初始内容
3.2.1 堆栈和队列
stack[MAX]= "#K"；
待 键 盘 输 入 "do{m=m+i;i=i+1}while{i<4}#" ， 则
queue[MAX]="di=i+i;i=i+iwi<i#"；
sp=1；front=16；
3.2.2 文法产生式、非终结符集及终结符集
p[18][6]={"dLwS\0","SP\0",";SP\0","\0","iQE\0","TG\0","+TG\0","-TG\0","\0",
"FR\0","*FR\0","/FR\0","\0","(E)\0","i\0","=\0","<\0",">\0"}；
VN[11]={'K','L','P','S','E','G','T','R','F','Q','\0'}；
VT[15]={'i','=','<','>','+','-','*','/','(',')','d','w',';','#','\0'}；
3.2.3 LL(1)分析数组
M[10][14]={ {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,0,-1,-1,-1},
{1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},
{-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,3,2,-1},
{4,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},
{5,-1,-1,-1,-1,-1,-1,-1,5,-1,-1,-1,-1,-1},
{-1,-1,-1,-1,6,7,-1,-1,-1,-1,-1,8,8,8},
{9,-1,-1,-1,-1,-1,-1,-1,9,-1,-1,-1,-1,-1},
{-1,-1,-1,-1,12,12,10,11,-1,-1,-1,12,12,12},
{14,-1,-1,-1,-1,-1,-1,-1,13,-1,-1,-1,-1,-1},
{-1,15,16,17,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},
};
说明：M[0][0]=-1 表示 VN[0]“K”遇到 VT[0]“i”时没有找到合适的产生式来推导；
M[1][0]=1 表示 VN[1]“L”遇到 VT[0]“i”时用(1)号产生式 LSP。
3.3 文法相关构建
3.3.1 属性文法
一个属性文法包含一个上下文无关文法和一系列语义规则，这些语义规则附在文法的
每个产生式上，在语法分析过程中，完成附加在所使用的产生式上的语义规则描述的动
作，从而实现语义处理。
表-1 属性文法：
4
武汉理工大学《编译原理》课程设计
产生式 语义规则
(0) K->dLwS
“w”匹配，将当前操作数回填
(1) L->SP To be Continued
(2) P->;SP
“;”匹配，将当前操作数回填
(3) P->ε To be Continued
(4) S->iQE To be Continued
(5) E->TG To be Continued
(6) G->+TG
“+”输出当前操作数 1，算术算符“+”，等待操作数 2
(7) G->-TG
“-”输出当前操作数 1，算术算符“-”，等待操作数 2
(8) G->ε To be Continued
(9) T->FR To be Continued
(10)R->*FR
“*”输出当前操作数 1，算术算符“*”，等待操作数 2
(11)R->/FR
“/”输出当前操作数 1，算术算符“/”，等待操作数 2
(12)R->ε To be Continued
(13)F->(E) To be Continued
(14)F->i To be Continued
(15)Q->=
“=”输出当前要接受赋值的操作数和赋值号“=”，等待
(16)Q-><
“<”输出当前操作数 1，关系算符“<”，等待操作数 2
(17)Q->>
“>”输出当前操作数 1，关系算符“>”，等待操作数 2
3.3.2 预测分析表
LL(1)方法在实现时用到一个 LL(1)分析矩阵和一个分析栈以及预测分析总控程序。
分析矩阵的元素 M[X,a]中的下标 X 为非终结符，a 为终结符或句子结束标记"#"，矩
5
