合肥工业大学编译原理课程设计

第一篇：合肥工业大学编译原理课程设计

关于《编译原理》课程设计的有关说明

《编译原理》是计算机专业的一门重要的专业课程，其中包含大量软件设计思想。大家通过课程设计，实现一些重要的算法，或设计一个完整的编译程序模型，能够进一步加深理解和掌握所学知识，对提高自己的软件设计水平具有十分重要的意义。大家在进行课程设计时，可从所学内容中选择某个主题，抽象成一个模型，可适当进行简化。也可按提供给大家的一些参考选题进行设计。软件开发选择C/C++语言（也可以是你熟悉的任何语言）。最后每位同学都要认真撰写设计报告，格式要规范，内容要详尽，包括：设计题目，设计目的，设计内容，设计要求，问题的描述及解决的方法、原理、思想、算法（流程图），设计的输入和输出形式，测试、模拟的结果（屏幕拷贝、生成结果的打印输出），总结（体会），源程序清单，等等。

大家应把该门课的课程设计当成对自己学习效果的一次检验，当成是为在大四能够顺利完成毕业设计的一次基本功训练。希望每个同学尽可能不要都选择完全一样的题目。大家可以自主选题，或选择我提供的题目，也可以把几个题目合起来做（如开发一个小的编译器）。鼓励选择有一定技术难度、有一定工作量、综合性较强的题目，在评定成绩时将会给予好的成绩。

编译原理课程设计部分参考选题： 1． 题目： FORTRAN语言实型常数识别程序设计

设计内容及要求： 将教材P.41的图3.2(d)识别FORTRAN实型常数的状态转换图用程序实现。程序能够从用户输入的任意一个字符串中识别出FORTRAN实型常数，显示输出。

2． 题目： 简化的FORTRAN语言词法分析程序设计

设计内容及要求：将教材P.42上的表3.1的词法分析器构造出来，限制条件如教材所述。保留字的识别按标识符一样识别，通过查找保留字表区分是保留字还是标识符。程序能够从用户输入的源程序中，识别出的单词符号，并用二元式表示，显示输出或输出到文件中。

3． 题目： ε-CLOSURE(I)构造算法的程序实现

设计内容及要求：将ε-CLOSURE(I)构造算法用程序实现。要求：对任意

第1页 给定的一个NFA M(其状态转换矩阵及初态、终态信息保存在指定文件中)的某一个状态子集I，显示输出构造出的ε-CLOSURE(I)。

4． 题目： 从右线性文法构造与之等价的有限自动机的程序实现

设计内容及要求：构造一转换程序，实现将用户任意给定的右线性文法，转换为与之等价的有限自动机FA M，输出其状态转换矩阵（显示输出或输出到文件中）。

5． 题目： 从有限自动机构造与之等价的右线性文法的程序实现

设计内容及要求：构造一转换程序，实现将用户任意给定的有限自动机FA M，转换为与之等价的右线性文法，显示输出或输出到文件中。6． 题目： 有限自动机的状态转换图显示程序的实现

设计内容及要求：构造一程序，实现：将任一给定的有限自动机M(其状态转换矩阵及初态、终态信息保存在指定文件中)，在屏幕上显示输出M的状态转换图。程序应具有通用性，状态节点在屏幕上的分布应合理、美观。7． 题目： 从NFA构造与之等价的正规式r的程序实现

设计内容及要求：对给定的任意NFA M(其状态转换矩阵及初态、终态信息分别保存在指定文件中)。构造一程序，从NFA构造与之等价的正规式r，并显示输出。

8． 题目： 构造正规式r1|r2（或运算）的NFA的程序实现

设计内容及要求：对给定的正规式r1、r2，已知它们的NFA分别为M1、M2(其状态转换矩阵及初态、终态信息分别保存在指定文件中)。构造一程序，由此程序构造正规式r1|r2（或运算）的NFA(将其状态转换矩阵及初态、终态信息保存在指定文件中)。

9． 题目： 构造正规式r1r2（连接运算）的NFA的程序实现

设计内容及要求：对给定的正规式r1、r2，已知它们的NFA分别为M1、M2(其状态转换矩阵及初态、终态信息分别保存在指定文件中)。构造一程序，由此程序构造正规式r1r2（连接运算）的NFA(将其状态转换矩阵及初态、终态信息保存在指定文件中)。10． 题目： 构造正规式r*（闭包运算）的NFA的程序实现

设计内容及要求：对给定的正规式r，已知其NFA为M(其状态转换矩阵及初态、终态信息保存在指定文件中)。构造一程序，由此程序构造正规式r*（闭包运算）的NFA(将其状态转换矩阵及初态、终态信息保存在指定文件中)。11．

题目： 基于语法制导构造正规式的NFA

第2页 设计内容及要求：首先构造一个语法分析程序，实现对任意正规式的语法分析。语法分析方法采用自下而上的分析方法（如算符优先分析，或LR分析）。在此语法分析器的基础上，按照语法制导的思想，增加构造NFA的功能。生成的NFA将其状态转换矩阵及初态、终态信息保存在指定文件中。进一步实现把NFA确定化为DFA 的算法(其状态转换矩阵及初态、终态信息保存在指定文件中)。12． 题目： DFA M状态最少化的程序实现

设计内容及要求：构造一程序，实现：将给定的DFA M(其状态转换矩阵及初态、终态信息保存在指定文件中)的有限状态集S划分成若干互不相交的子集，使得：任何不同的两个子集中的状态都是可区别的，而同一子集中的任何两个状态都是等价的（要利用Ia函数，但并不需要构造ε-CLOSURE函数，因这是DFA）。输出化简后的DFA M’(其状态转换矩阵及初态、终态信息保存在指定文件中)。13． 题目： 把NFA确定化为DFA 的算法实现

设计内容及要求：构造一程序，实现：将给定的NFA M(其状态转换矩阵及初态、终态信息保存在指定文件中)，确定化为DFA M’。（要先实现ε-CLOSURE函数和Ia函数）。输出DFA M’(其状态转换矩阵及初态、终态信息保存在指定文件中)。14． 题目： 基于贪心算法的DFA 的程序实现

设计内容及要求：采用贪心算法实现教材P.62表3.5的DFA，要求从输入串中匹配最长的子串。输出所有识别出的符号串及其词形。15． 题目： 根据句型的推导构造其语法分析树的程序实现

设计内容及要求：构造一程序，实现：接受用户任意输入的一个句型的推导序列，生成该句型的语法分析树并显示输出。程序应具有通用性，语法分析树的节点在屏幕上的分布要合理、美观。16． 题目： 从语法分析树构造句型所有的推导的程序实现

设计内容及要求：构造一程序，实现：接受用户任意输入的一个句型的语法分析树（其表示存于指定文件中），生成该语法分析树中包含的该句型的所有推导（显示输出）。17． 题目： 递归下降分析程序的实现 设计内容及要求：

对文法 G: E→E+T|T 构造出G的递归下降分析程序。程序显示输出

T→T*F|F 匹配过程（即自上而下生成语法分析树的步骤，F→（E）|i 输出各匹配产生式序号即可）。

18．题目： 集合FIRST(X)构造算法的程序实现

第3页 设计内容及要求：构造一程序，实现教材P.78的FIRST(X)集合的构造算法。对任一给定的文法G，程序输出所有非终结符P的FIRST(P)。19． 题目： 集合FOLLOW(A)构造算法的程序实现

设计内容及要求：首先，构造一程序，实现教材P.78的FIRST(X)集合的构造算法。对任一给定的文法G，程序输出所有非终结符P的FIRST(P)。在此基础上，构造一程序，实现教材P.79的FOLLOW(A)集合的构造算法。对任一给定的文法G，程序输出所有非终结符A的FOLLOW(A)。20． 题目： 预测分析表构造算法的程序实现

设计内容及要求：对于给定的一个LL(1)文法，假定所有非终结符号P的集合FIRST(P)和集合FOLLOW(P)都已知，构造其预测分析表（实现教材P.79给出的预测分析表构造算法）。对教材P.79给出的例4.7构造出预测分析表。程序显示输出预测分析表或输出到指定文件中。21． 题目： 预测分析表自动构造程序的实现

设计内容及要求：对于任意输入的一个LL(1)文法，构造其预测分析表。要求：首先实现集合FIRST(X)构造算法和集合FOLLOW(A)构造算法，再实现教材P.79给出的预测分析表构造算法。程序显示输出预测分析表或输出到指定文件中。22． 题目： 预测分析程序的实现 设计内容及要求：

对文法 G: E→E+T|T 按教材P.76表4.1构造出G的预测分析程序，T→T*F|F 程序显示输出如P.78那样的匹配过程。

F→（E）|i 23． 题目： 集合FIRSTVT(P)构造算法的程序实现

设计内容及要求：构造一程序，实现教材P.91的FIRSTVT(P)集合的构造算法。对任一给定的算符文法G，程序输出所有非终结符P的FIRSTVT(P)。24． 题目： 集合LASTVT(P)构造算法的程序实现

设计内容及要求：构造一程序，实现教材P.91的LASTVT(P)集合的构造算法。对任一给定的算符文法G，程序输出所有非终结符P的LASTVT(P)。25． 题目： 算符优先分析算法的程序实现 设计内容及要求：

对文法 G: E→E+T|T 采用教材P.90表5.1，实现P.93描述的算符优先

T→T*F|F 分析算法。程序显示输出“移进-归约”的步骤。F→P↑F|P

第4页 P→（E）|i 26． 题目： 带出错处理的算符优先分析算法的程序实现 设计内容及要求：

对文法 G: E→E+T|T 采用教材P.98表5.3，实现P.93描述的算符优先

T→T*F|F 分析算法。程序显示输出“移进-归约”的步骤。

F→(E)|i 要编制各出错处理子程序。

27． 题目： 优先表构造算法的程序实现

设计内容及要求： 实现教材P.92优先表构造算法。对任一给定的算符优先文法G，假定所有非终结符P的FIRSTVT(P)、LASTVT(P)均已知。以教材P.90例5.4文法为例，程序生成表5.1优先表。28． 题目： 优先表自动构造程序的实现

设计内容及要求：对任一给定的算符优先文法G，构造其优先表。要求：首先实现对于非终结符P的FIRSTVT(P)构造算法和LASTVT(P)构造算法，再实现教材P.92给出的优先表构造算法。以教材P.90例5.4文法为例，程序生成表5.1优先表。29． 题目： 优先函数构造程序的实现

设计内容及要求：构造一程序，实现：根据优先关系表构造优先函数。输入的优先表假定保存在指定文件中，构造出的优先函数可显示输出，或输出到指定文件中。30． 题目： 消除左递归算法的程序实现

设计内容及要求：构造一程序，实现教材P.70消除左递归算法。对于用户任意输入的文法G，输出一个无左递归的等价文法，可显示输出，或输出到指定文件中。31． 题目： 消除回溯算法的程序实现

设计内容及要求：构造一程序，实现：消除文法每一条产生式候选式的公共左因子。对于用户任意输入的文法G，输出一个无回溯的等价文法，可显示输出，或输出到指定文件中。32． 题目： LR分析器总控程序的实现

设计内容及要求：对P.101中的文法，按图5.5LR分析表构造LR分析器。要求程序按P.102例5.7那样，对于输入串i*i+i，输出LR分析器的工作过程。33． 题目： 识别文法活前缀的NFA构造程序的实现

设计内容及要求：构造一程序，对任意给定的文法G：①构造并输出G的所有LR(0)项目；②用这些LR(0)项目构造并输出识别文法活前缀的NFA(输出其

第5页 状态转换矩阵)。34． 题目： LR(0)项目集规范族构造程序的实现

设计内容及要求：构造一程序，对任意给定的文法G，构造识别文法活前缀的DFA，输出DFA的状态转化矩阵及LR(0)项目集规范族。要求按教材P.107所给的ITEMSETS(G’)构造，要实现CLOSURE(I)、GO(I,X)函数。按P.105例5.8给出测试结果，可输出到指定文件中。35． 题目： LR(0)分析表构造算法的程序实现

设计内容及要求： 构造一程序，实现LR(0)分析表构造算法。根据教材P.106图5.7的识别文法活前缀的DFA，输出如P.109表5.4的LR(0)分析表，可输出到指定文件中。36． 题目： LR(0)分析器自动构造程序的实现

设计内容及要求：对任意给定的文法G，构造识别文法活前缀的DFA，输出DFA的状态转化矩阵及LR(0)项目集规范族；实现LR(0)分析表构造算法；实现LR分析器总控程序。程序输出一个完整的LR(0)分析器源程序，可输出到指定文件中。37． 题目： SLR(1)分析表构造算法的程序实现

设计内容及要求：构造一程序，实现SLR(1)分析表构造算法(假定所给文法识别文法活前缀的DFA、LR(0)项目集族、所有非终结符FOLLOW集合均已构造出来了)。根据教材P.111例5.11文法为输入，构造其SLR(1)分析表。38． 题目： LR(1)项目集规范族构造程序的实现

设计内容及要求：构造一程序，对任意给定的文法G构造LR(1)项目集规范族（按教材P.115所述方法构造，要实现CLOSURE(I)、GO(I,X)，集合FIRST的构造方法参见教材P.78）。39． 题目： LR(1)分析表构造算法的程序实现

设计内容及要求：构造一程序，实现LR(1)分析表构造算法(假定所给文法识别文法活前缀的DFA、LR(1)项目集族已构造出来了)。根据教材P.116图5.10的LR(1)项目集族和GO函数为输入，构造并输出其LR(1)分析表5.5。40． 题目： LR(1)分析表自动构造程序的实现

设计内容及要求：对任意给定的文法G构造LR(1)项目集规范族（按教材P.115所述方法构造，要求实现CLOSURE(I)、GO(I,X)、FIRST（集合FIRST的构造方法参见教材P.78）；然后实现LR(1)分析表构造算法。以教材P.115例5.13为输入，构造并输出其LR(1)分析表5.5。

第6页 41． 题目： LALR(1)项目集规范族构造程序的实现

设计内容及要求：假设对于给定文法，识别文法活前缀的DFA、LR(1)项目集族已构造出来了。构造一程序，检查两个LR(1)项目集是否为同心集（可任意输入），若是，则输出合并后的同心集，并检查合并后的集合是否含有冲突项目（指出存在何种冲突），输出合并同心集后的识别文法活前缀的DFA，及LALR(1)项目集规范族。42． 题目： LALR(1)分析表自动构造程序的实现

设计内容及要求：对任意给定的文法G构造LR(1)项目集规范族（按教材P.115所述方法构造，要求实现CLOSURE(I)、GO(I,X)、FIRST（集合FIRST的构造方法参见教材P.78）；然后构造LALR(1)项目集规范族；再实现LALR(1)分析表构造算法。以教材P.115例5.13为输入，构造并输出其LALR(1)分析表5.6。43． 题目： 带出错处理的LR分析器总控程序的实现

设计内容及要求：按教材P.127表5.9分析表构造一LR分析器，输出语法分析过程（如P.128所述），要构造各出错处理子程序。44． 题目： 算术表达式从中缀式翻译成后缀式的程序实现

设计内容及要求：设计一个语法制导翻译器，将算术表达式从中缀式翻译成后缀式。要求：先确定一个定义算术表达式的文法，为其设计一个语法分析程序，为每条产生式配备一个语义子程序，按照一遍扫描的语法制导翻译方法，实现翻译程序。对用户输入的任意一个正确的算术表达式，程序将其转换成后缀式输出。45． 题目：将算术表达式转换成抽象语法树的程序实现

设计内容及要求：设计一个语法制导翻译器，将算术表达式转换成抽象语法树。要求：先确定一个定义算术表达式的文法，为其设计一个语法分析程序，为每条产生式配备一个语义子程序，按照一遍扫描的语法制导翻译方法，实现翻译程序。对用户输入的任意一个正确的算术表达式，程序将其转换成抽象语法树输出(可按一定格式输出到指定文件中)。46． 题目：将算术表达式转换成DAG的程序实现

设计内容及要求：设计一个语法制导翻译器，将算术表达式转换成DAG。要求：先确定一个定义算术表达式的文法，为其设计一个语法分析程序，为每条产生式配备一个语义子程序，按照一遍扫描的语法制导翻译方法，实现翻译程序。对用户输入的任意一个正确的算术表达式，程序将其转换成DAG输出(可按一定格式输出到指定文件中)。

第7页 47． 题目：将算术表达式转换成三元式的程序实现

设计内容及要求：设计一个语法制导翻译器，将算术表达式翻译成三元式。要求：先确定一个定义算术表达式的文法，为其设计一个语法分析程序，为每条产生式配备一个语义子程序，按照一遍扫描的语法制导翻译方法，实现翻译程序。对用户输入的任意一个正确的算术表达式，程序将其转换成三元式输出(可按一定格式输出到指定文件中)。48． 题目：将算术表达式转换成间接三元式的程序实现

设计内容及要求：设计一个语法制导翻译器，将算术表达式翻译成间接三元式。要求：先确定一个定义算术表达式的文法，为其设计一个语法分析程序，为每条产生式配备一个语义子程序，按照一遍扫描的语法制导翻译方法，实现翻译程序。对用户输入的任意一个正确的算术表达式，程序将其转换成间接三元式输出(可按一定格式输出到指定文件中)。49． 题目：将算术表达式转换成四元式的程序实现

设计内容及要求：设计一个语法制导翻译器，将算术表达式翻译成四元式。要求：先确定一个定义算术表达式的文法，为其设计一个语法分析程序，为每条产生式配备一个语义子程序，按照一遍扫描的语法制导翻译方法，实现翻译程序。对用户输入的任意一个正确的算术表达式，程序将其转换成四元式输出(可按一定格式输出到指定文件中)。50． 题目：将布尔表达式转换成四元式的程序实现

设计内容及要求：设计一个语法制导翻译器，将布尔表达式翻译成四元式。要求：先确定一个定义布尔表达式的文法，为其设计一个语法分析程序，为每条产生式配备一个语义子程序，按照一遍扫描的语法制导翻译方法，实现翻译程序。对用户输入的任意一个正确的布尔表达式，程序将其转换成四元式输出(可按一定格式输出到指定文件中)。51． 题目：将条件语句转换成四元式的程序实现

设计内容及要求：设计一个语法制导翻译器，将条件语句翻译成四元式。要求：先确定一个定义条件语句的文法，为其设计一个语法分析程序，为每条产生式配备一个语义子程序，按照一遍扫描的语法制导翻译方法，实现翻译程序。对用户输入的任意一个正确的条件语句，程序将其转换成四元式输出(可按一定格式输出到指定文件中)。52． 题目：将WHILE语句转换成四元式的程序实现

设计内容及要求：设计一个语法制导翻译器，将WHILE语句翻译成四元式。

第8页 要求：先确定一个定义WHILE语句的文法，为其设计一个语法分析程序，为每条产生式配备一个语义子程序，按照一遍扫描的语法制导翻译方法，实现翻译程序。对用户输入的任意一个正确的WHILE语句，程序将其转换成四元式输出(可按一定格式输出到指定文件中)。53． 题目：将FOR语句转换成四元式的程序实现

设计内容及要求：设计一个语法制导翻译器，将FOR语句翻译成四元式。要求：先确定一个定义FOR语句的文法，为其设计一个语法分析程序，为每条产生式配备一个语义子程序，按照一遍扫描的语法制导翻译方法，实现翻译程序。对用户输入的任意一个正确的FOR语句，程序将其转换成四元式输出(可按一定格式输出到指定文件中)。54． 题目：将SWITCH语句转换成四元式的程序实现

设计内容及要求：设计一个语法制导翻译器，将SWITCH语句翻译成四元式。要求：先确定一个定义SWITCH语句的文法，为其设计一个语法分析程序，为每条产生式配备一个语义子程序，按照一遍扫描的语法制导翻译方法，实现翻译程序。对用户输入的任意一个正确的SWITCH语句，程序将其转换成四元式输出(可按一定格式输出到指定文件中)。55． 题目：将包含数组引用的赋值语句转换成四元式的程序实现

设计内容及要求：设计一个语法制导翻译器，将包含数组引用的赋值语句翻译成四元式。要求：先确定一个定义包含数组引用的赋值语句的文法，为其设计一个语法分析程序，为每条产生式配备一个语义子程序，按照一遍扫描的语法制导翻译方法，实现翻译程序。对用户输入的任意一个正确的包含数组引用的赋值语句，程序将其转换成四元式输出(可按一定格式输出到指定文件中)。56． 题目：嵌套过程中的说明语句翻译的程序实现

设计内容及要求：设计一个语法制导翻译器，完成对说明语句的翻译，即构造每个过程的符号表，填写所有名字在符号表中的有关信息。要求：先确定一个定义允许嵌套过程的说明语句的文法，为其设计一个语法分析程序，为每条产生式配备一个语义子程序，按照一遍扫描的语法制导翻译方法，实现翻译程序。对用户输入的任意一组正确的说明语句，程序将输出相应的符号表(可按一定格式输出到指定文件中)。57． 题目：基本块划分算法的程序实现

设计内容及要求：根据基本块划分算法，构造一个基本块划分程序，实现：对于任意输入的一个四元式程序，将其划分为基本块，输出各基本块，并输出程

第9页 序流图。以P.279例10.1为输入，输出P.281图10.8.58． 题目：将基本块转换成DAG的算法的程序实现

设计内容及要求：根据将基本块转换成DAG的算法，实现：对于任意输入的一个基本块（四元式程序），将其转换成DAG并输出(可按一定格式输出到指定文件中)。以P.283例10.4为输入，输出P.284图10.10构造过程。59． 题目：由DAG重构基本块的程序实现

设计内容及要求：按照DAG节点构造顺序，重构基本块四元式代码。输入的DAG按一定格式存于指定文件中，输出的基本块四元式代码按一定格式输出到指定文件中。以P.284图10.10为输入，输出基本块四元式代码。60． 题目：局部优化程序的实现

设计内容及要求：根据将基本块转换成DAG的算法，实现：对于任意输入的一个基本块（四元式程序），将其转换成DAG；然后按照DAG节点构造顺序，重构基本块四元式代码。以P.283例10.4为输入，完成并输出局部优化。

（待续）

。。。(大家也可以自行设计一个设计题目)

第10页

第二篇：编译原理课程设计

课 程 设 计 报 告

设计题目：一个简单文法的编译器前端的设计与实现

班

级： 计算机1206 组长学号：201239 组长姓名：闫智宣 指导教师：李晓华 设计时间：2014年12月

[在此处键入]

设计分工

组长学号及姓名： 20123974

闫智宣

分工：

语法分析，四元式生成，目标代码优化及生成 组员1学号及姓名：20123977

廖峭 分工：

词法分析，错误处理 组员2学号及姓名：20123959

郭天龙

分工：

符号表生成，语义动作插入，操作界面[在此处键入]

摘要

编译原理课程设计是通过C语言编译器相关子系统的设计，进一步加深对编译器构造的理解；第一部分词法分析，设计各单词的状态转换图，并为不同的单词设计种别码，制作扫描器识别一个个单词，返回值为识别码的序号，返回Token序列。将词法分析器设计成供语法分析器调用的子程序。词法分析器具备预处理功能。将不翻译的注释等符号先滤掉，只保留要翻译的符号串，即要求设计一个供词法分析调用的预处理子程序；第二部分，语法分析，用递归下降法，实现对表达式、各种说明语句、控制语句进行语法分析。若语法正确，则用语法制导翻译法进行语义翻译；生成并打印出语法树；若语法错误，要求指出出错性质和出错位置（行号）。

我们还做了附加功能，即编译后端，有中间代码优化，生成目标代码汇编语言。通过此次课程设计，提高了我们的独立分析问题、解决问题的能力，以及系统软件设计的能力； 提高程序设计能力、程序调试能力，团结协作能力

关键词：词法分析，语法分析，四元式生成，错误处理，符号表生成，语义动作插入，中间代码优化，生成目标代码 [在此处键入]

目录

摘要

1.概述

2.课程设计任务及要求

2.1 设计任务

2.2 设计要求

3.算法及数据结构

3.1算法的总体思想（流程）

3.2 词法分析模块

3.2.1 功能

3.2.2 数据结构

3.2.3 算法

3.3 语法分析模块

3.3.1功能

3.3.2 数据结构

3.3.3算法

3.4 符号表模块

3.4.1功能

3.4.2 数据结构

3.4.3算法

3.5 四元式模块

3.5.1功能

[在此处键入]

3.5.2 数据结构

3.5.3算法

3.6 语义动作分析模块

3.6.1功能 3.6.2 数据结构

3.6.3算法

3.7 错误处理模块

3.7.1功能

3.7.2 数据结构

3.7.3算法

3.8 目标代码模块

3.8.1功能

3.8.2 数据结构

3.8.3算法

4.程序设计与实现

4.1 程序流程图

4.2 程序说明

4.3 实验结果

5.结论 6.参考文献。7.收获、体会和建议。

[在此处键入]

1.概述

编译器是将C语言翻译为汇编语言代码的计算机程序。编译器将源程序（source language）编写的程序作为输入，翻译产生目标语言（target language）机器代码的等价程序。通常地，源程序为高级语言（high-level language），C语言程序，而目标则是 机器语言的目标代码（object code），也就是可以在计算机硬件中运行的机器代码软件程序。这一过程可以表示为：

源程序→编译器 →目标机器代码程序

2.课程设计任务及要求

2.1设计任务

学生在学习《编译原理》课程过程中，结合各章节的构造编译程序的基本理论，要求用C#语言描述及上机调试，实现一个 C编译程序（包括词法分析，语法分析等重要子程序），使学生将理论与实际应用结合起来，受到软件设计等开发过程的全面训练，从而提高学生软件开发的能力。

2.2设计要求 要求：

（1）设计词法分析器

设计各单词的状态转换图，并为不同的单词设计种别码。将词法分析器设计成供语法分析器调用的子程序。功能包括：

a.具备预处理功能。将不翻译的注释等符号先滤掉，只保留要翻译的符号串，即要求设计一个供词法分析调用的预处理子程序；

b.能够拼出语言中的各个单词； [在此处键入]

c.返回（种别码，属性值，行号）。

（2）语法分析

要求用学习过的自底向上或自顶向下的分析方法等，实现对表达式、各种说明语句、控制语句进行语法分析。若语法正确，则用语法制导翻译法进行语义翻译；生成并打印出语法树；若语法错误，要求指出出错性质和出错位置（行号）。

3.算法及数据结构

3.1算法的总体思想（流程）

本节主要分析程序的代码结构和代码工程文件的划分。（程序由几个类组成: Token类和Variable类SymbolTable类ObjectCode类Lexical类Grammar类Four_Yuan类Action类ErrorItem类，分别为词法分析和语法分析类。工程分为几个文件：Form1.cs,Token.cs,Variable.cs,SymbolTable.cs,ObjectCode.cs,Lexical.cs,Grammar.cs,Four_Yuan,cs,Action.cs,ErrorItem.cs分别对应Token类和Variable类SymbolTable类ObjectCode类Lexical类Grammar类Four_Yuan类Action类ErrorItem类的声明和实现文件）。本程序采用C#语言以面向对象的思想编写，程序分为几部分：词法分析（Lexical），语法分析（Grammer），目标代码生成（ObjectCode）。Lexical类主要的工作是词法分析获取Token。Grammer类的主要工作是根据Lexical类词法分析之后的Token进行语法分析，生成语法树，最后并输出语法树。在处理过程中，Token类的对象作为Lexical类的一个成员变量，配合Grammer类进行语法分析。

工程文件总体上是按照九个类的格局分为十个文件，分别是九个类的声明文件和实现文件。十个文件为Form1.cs,Token.cs,Variable.cs,SymbolTable.cs,ObjectCode.cs,Lexical.cs,Grammar.cs,Four_Yuan,cs,Action.cs,ErrorItem.cs，他们分别是Lexical类声明文件、Lexical类实现文件、Grammer类声明文件、Grammer类实现文件。[在此处键入]

程序流程

在程序中，Lexical类的对象(Token)作为Grammer类中的一个成员变量，配合Grammer类进行语法分析。它们的关系是这样的：Grammer类的一个成员变量temp首先对源程序删除注释，然后进行词法分析获取所有Token，并将获取的Token存储在Token对象的tokenList（List类型）中。然后Grammer类的语法分析程序就根据tokenList中的Token进行语法分析，生成语法树，最后打印语法树。同时，这也是程序的流程。[在此处键入]

3.2 词法分析模块 3.2.1功能

Lexical类主要的工作是词法分析获取Token序列。

3.2.2数据结构

词法分析阶段的代码被封装成一个类——Lexical，Token中主要是Lexical类的声明代码，Lexical.cs中主要是Lexical类的实现代码。Lexical类对外提供的函数主要有：

static public int RecogId(string str, int i)，static public int RecogDig(string str,int i)，static public int RecogOperator(string str, int i)，static public int RecogBound(string str, int i)，以上几个函数构成了词法分析的骨架，在Lexical类中还有其他成员变量和函数，主要作为这三个函数处理过程的中间步骤，为这三个函数服务。Lexical类的代码结构和主要的成员变量和函数及其含义如下图所示：

3.2.3算法

算法的基本任务是从字符串表示的源程序中识别出具有独立意义的单词符号，其基本思想是[在此处键入]

根据扫描到单词符号的第一个字符的种类，拼出相应的单词符号。

主程序示意图：

主程序示意图如图3-1所示。

⑴ 关键字表的初值。

关键字作为特殊标识符处理，把它们预先安排在一张表格中（称为关键字表），当扫描程序识别出标识符时，查关键字表。如能查到匹配的单词，则该单词为关键字，否则为一般标识符。

（2）程序中需要用到的主要变量为type和number 扫描子程序的算法思想：

首先设置3个变量： [在此处键入]

①token用来存放构成单词符号的字符串； ②number用来整型单词；

③type用来存放单词符号的种别码。

Token定义

Token定义:

Token类型（TokenType）:

3.3 语法分析模块

3.3.1功能

语法分析是编译过程的一个逻辑阶段。语法分析的功能是在词法分析的基础上将单词序列组合成各类语法短语，如“程序”，“语句”，“表达式”等等.语法分析程序判断源程序在结构上是否正确.源程序的结构由上下文无关文法描述.3.3.2 数据结构

下图为实现语法分析的类Grammar，属性与方法的作用都已说明 在此处键入]

3.3.3算法

1.文法

下面终结符与非终结符意义

B程序开始

Z 数据类型，如int,char,float等

V 标识符

S 语句

P 语句块

E 加减算术表达式

D 逗号表达式

T 乘除算术表达式

C 关系表达式

L 逻辑表达式

Q 标识符或圆括号

e 表示空

i 表示标识符 a)函数文法

B----ZV()S

[

[在此处键入]

b)语句块文法

P----SP|e

S----{P} c)语句文法

表达式语句文法

S----V=E

goto语句文法

S----i:S

S----goto i

if语句文法

S----if(E)S[else S]

while语句文法

S----while(E)S

声明语句文法

S----ZVD

D----,VD|=ED|e d)表达式文法

E----T|E+T|E-T

T----F|T*F|T/F

C----C|CL|C==C|C<= L|C>=L

L----Q|L&&Q|L||Q

Q----i|(E)|!Q

2.递归下降程序流程图

对应于每个文法编写如下递归下降子程序

主程序（B）[在此处键入] [在此处键入]

3.4 符号表模块

3.4.1功能

进行符号表的储存，添加，更新，查找，保存标识符活跃信息以及输出。3.4.2 数据结构

在此处键入]

3.4.3算法

3.5 四元式模块

3.5.1功能

四元式为中间代码，编译程序进行完语义分析后，先生成中间代码作为过渡，此时中间代码与目标代码已经比较相似

3.5.2 数据结构

[ 在此处键入]

3.5.3算法

3.6语义动作分析模块

3.6.1功能

在语法分析中嵌入相应的语义动作，生成四元式 3.6.2 数据结构

[

[在此处键入]

3.6.3算法 GEQ(+)(-)(*)(/)

(+,i1,i2,t)PUSH(i)ASSI(=)

(=,t,_,POP)LABER(i)

(lb,_,_,i)GOTO(i)

(gt,_,_,i)IF(if)

(if,a,_,_)EL(el)

(el,_,_,_)IE(ie)

(ie,_,_,_)WH()

(wh,_,_,_)DO()

(do,a,_,_)WE(we)

(we,_,_,_)

3.7 错误处理模块

3.7.1功能 保存运行时发现的错误，储存行号已经详细信息并输出。

3.7.2 数据结构

3.7.3算法 [在此处键入]

public static void AddErrorMessage(int lineno,string content)函数用作在发现错误时保存错误信息以及行号。

public static string PrintErrorList()把所有发现的错误格式化后统一输出。

错误信息在语法分析，语义分析，符号表检错中添加。3.8 目标代码模块

3.8.1功能

目标代码生成把优化后的中间代码变换成目标代码，此处的目标代码为汇编代码，采用单寄存器生成目标代码 3.8.2 数据结构[在此处键入]

3.8.3算法

对于一个基本块有如下流程图

W：操作符，B：第一操作数，C：第二操作数，R：寄存器

5.结论

网上找一段话抄上 [在此处键入]

6.测试

测试打开文件

测试保存文件

如果没打开文件，直接敲代码，点保存时会弹出另存为窗口[在此处键入]

测试错误检测，程序缺少main函数的类型，错误列表中显示第一行函数缺少错误类型。

测试错误检测，程序缺少分号，错误列表中显示该行缺少语句结束标志';' 单击错误列表，会自动选定错误行

编译成功，生成并显示token串、符号表、四元式与目标代码 [在此处键入]

测试if与while语句，而且while嵌套在if当中

测试goto语句，结果正确。[在此处键入]

测试优化，输入课件中的代码，结果与课件一样

6.参考文献。

1、陈火旺.《程序设计语言编译原理》（第3版）.北京：国防工业出版社.2000.2、美 Alfred V.Aho Ravi Sethi Jeffrey D.Ullman著.李建中，姜守旭译.《编译原理》.24 [在此处键入]

北京：机械工业出版社.2003.3、美 Kenneth C.Louden著.冯博琴等译.《编译原理及实践》.北京：机械工业出版社.2002.4、金成植著.《编译程序构造原理和实现技术》.北京：高等教育出版社.2002.7.收获、体会和建议。

直接拷贝好歹也检查一下错误

对于编译原理的这次课程设计，自己经历了从刚开始的不懂明白任务的要求和内容理论知识的了解开始着手写代码完成基本功能根据DFA及自顶向下等理论修改完善代码等这些过程。

自己着手写词法分析的时候还不清楚词法分析的任务内容，还不知道词法分析的结果是什么，词法分析出错的情况和类型有哪些，也总是将词法分析和语法分析混在一起，不明白哪些错误在词法分析中报，哪些错误在语法分析中判断，后来经过查书、网上资料、请教同学等途径逐步清晰了词法分析的工作内容是从源代码文件中获取出Token，供语法分析使用。在充分了解了语法分析需要哪些信息时，我才真正了解了词法分析的工作内容和目标，才知道词法分析需要完成哪些任务获取到哪些信息。充分了解了词法分析的任务之后，就开始理论知识的学习。经过揣摩书上的例子，自己理解和掌握了怎么设计过滤注释和分析程序中Token的DFA，于是开始根据设计好的DFA进行编码，最后经过调试已经可以正确地完成词法阶段的任务了。这只是词法分析的原始代码，在之后还进行了两次彻底的改动。虽然之前写的词法分析的代码已经完成了词法分析的需求，也是根据DFA的原理编写的，但是在代码结构上却难以体现，在对书上的根据已知DFA写代码的例子进行了详细的研究之后，发现自己的代码并没有像书上那样完全按照所依据的DFA各状态转移的关系进行编写，所以对代码进行了重写，像书上一样严格按照状态之间转移的方式进行编写，将状态划分成11个状态，状态分别按1~11进行标注，程序也按照DFA来编写，也实现了词法分析的功能。再后来写报告的时候，发现分析出Token的那个DFA并不是最简的，有很多多余的状态，完全可以用一个flag标志来标识，从而简化代码结构，于是又重写了一次词法分析函数scan()的代码，将状态缩减为5个，且不再用1-5来表示，而是像书上那样分别取了名字（START、INNUM、INID、INDBSYM、DONE），同时为了简化代码将输出Token到文件的部分从scan()中剥离开来，而在Lexical类中加了一个printToken()的函数，使scan()函数逻辑更加清晰，使读者能够容易地将代码与DFA进行查看比照。

在写语法分析的时候，已经对编译器的语法分析的内容有了一定的了解，所以直接进行了理论的学习。首先自己对递归向下分析法进行了学习，将书上的几个递归向下分析的伪代码看过之后，自己对递归向下的分析方法的原理有了初步的认识，大概知道了根据文法怎么分析，但是对于如何编写代码却还在此处键入]

是难以下手，于是就对照TINY语言的文法看了几遍书后面的TINY语言的递归向下分析的语法分析程序，这样就基本知道了C-语言的语法分析程序怎么写。由于C-语言给出的文法有左递归存在，于是自己将存在左递归的文法改写成EBNF的形式，并据此进行代码编写。由于在编写代码的过程中需要确定分析是否正确或选择多个文法中的某一个文法进行分析，有时必须探测需要的或下一个Token的类型，在这种情况下需要求First集合，在推导中若存在empty，又需要求Follow集合，所以这样又需要我了解First集合和Follow集合，自己在程序中也根据求出的First集合和Follow集合进行判断，以确定程序的走向。在编写过程中，还有一类问题，就是存在公共左因子，如文法expression→ var = expression | simple-expression，左因子为ID，在分析过程中，由于已经取出了一个ID的Token，且生成了一个IdK的节点，但是在当前状态无法确定是哪一个推导，然而IdK节点已经生成，又无法回退，并且是使用自顶向下的分析方法，已经生成的IdK在程序上方无法使用，自己通过查阅资料等途径的学习确定了在这种情形下的处理方式：将已经生成的IdK节点传到下方的处理程序，所以TreeNode * simple_expression(TreeNode * k)、TreeNode * additive_expression(TreeNode * k)等函数都被设计成有节点类型参数的函数，目的就是将已经生成的节点传到下面的分析函数中去。

通过这次的编译原理课程的学习和实践，自己获益良多。首先最基本的成果是完成了课程设计的任务，实现了编译器的词法分析和语法分析阶段的功能，词法分析主要能过滤注释、分析出语法分析阶段需要的Token并满足语法阶段的所有要求，能够判别词法分析阶段是否出错和出错类型和位置。语法分析主要能根据递归向下的分析思想和C-文法对词法分析获取的Token进行语法分析，能够构造出语法树，能够判别语法分析过程中是否出错以及出错位置和错误类型。

由于在编写程序过程中，涉及到了正则表达式、DFA、提取公共左因子、消除左递归、EBNF、求First集合和Follow集合、递归向下分析方法以及编程语言方面的知识，所以，通过本次的课程设计的实践，使得自己对编译原理这门课的许多知识点有了更加深刻和具体的理解，而不再只限制于做题。此外，对以前那些已掌握的知识有了温习和动手锻炼的机会。如：以前在编译原理课上虽然知道First集合和Follow集合怎么求的，却不知道First集合和Follow集合到底是干什么的，通过编写程序自己明白了他们的实际作用，使得自己不仅知其然还知其所以然，从而使得自己加深了对知识点的理解和掌握。由于以前编写代码都是使用JAVA语言，所以C/C++很多内容都忘记了，通过本次的实践，自己又重新拾起了以前的知识。此外，由于在做报告的时候，需要描绘DFA和程序流程图，使得自己初步掌握了使用visio和word画图的能力。此外，对于文档的编写和美化自己也获得了许多有用的经验。[

第三篇：编译原理课程设计报告

武 汉 纺 织 大 学

编译原理课程设计实验报告

学院：数学与计算机 专业：计算机 姓名： 班级： 学号： 编译原理

编译原理课设报告

一、实验目的

加强对编译程序的整体认识和了解，巩固《编译原理》课程所学知识。通过本次课程设计掌握编译程序调试技巧和设计编译程序一般的原则，加深对词法分析、语法分析、语义分析等编译阶段及实用编译系统的认识。使学生能将编译理论与实际应用结合起来，提高学生软件开发的能力。

二、实验内容

1）仔细阅读PL/0编译程序文本（编译原理(第二版)张素琴 吕映芝 蒋维杜 戴桂兰 主编

清华大学出版社），并上机调试通过。

2）对PL/0语言进行下列扩充（1）扩充一维整型数组。

扩充var数组：VAR <数组标识名>（<下界>：<上界>）〈下界〉和〈上界〉可用常量标识名。

（2）扩充条件语句的功能使其为：IF<条件>THEN<语句>[ELSE<语句>]（3）增加repeat重复语句: REPEAT<语句>{;<语句>}UNTIL<条件> 可根据自己具体情况从中选择2个以上题目进行扩充。

三、实验原理

PL/0语言可以看成PASCAL语言的子集，它的编译程序是一个编译解释执行系统。PL/0的目标程序为假想栈式计算机的汇编语言，与具体计算机无关。

PL/0的编译程序和目标程序的解释执行程序都是用PASCAL语言书写的，因此PL/0语言可在配备PASCAL语言的任何机器上实现。其编译过程采用一趟扫描方式，以语法分析程序为核心，词法分析和代码生成程序都作为一个独立的过程，当语法分析需要读单词时就调用词法分析程序，而当语法分析正确需要生成相应的目标代码时，则调用代码生成程序。

用表格管理程序建立变量、常量和过程表示符的说明与引用之间的信息联系。

当源程序编译正确时，PL/0编译程序自动调用解释执行程序，对目标代码进行解释执行，并按用户程序的要求输入数据和输出运行结果。

四、实验分析

PL/0语言编译程序采用以语法分析为核心、一遍扫描的编译方法。词法分析和代码生成作为独立的子程序供语法分析程序调用。语法分析的同时，提供了出错报告和出错恢复的功能。在源程序没有错误编译通过的情况下，调用类PCODE解释程序解释执行生成的类PCODE代码。

词法分析子程序分析：

词法分析子程序名为GETSYM，功能是从源程序中读出一个单词符号（TOTAKEN），把它的信息放入全局变量 SYM、ID和NUM中，字符变量放入CH中，语法分析器需要单词时，直接从这三个变量中获得。Getch过程通过反复调用Getch子过程从源程序过获取字符，并把它们拼成单词。GETCH过程中使用了行缓冲区技术以提高程序运行效率。

词法分析器的分析过程：调用GETSYM时，它通过GETCH过程从源程序中获得一个字符。如果这个字符是字母，则继续获取字符或数字，最终可以拼成一个单词，查保留字表，如果查到为保留字，则把SYM变量赋成相应的保留字类型值；如果没有查到，则这个单词应是一个用户自定义的标识符（可能是变量名、常量名或是过程的名字），把SYM置为IDENT，把这个单词存入ID变量。查保留字表时使用了二分法查找以提高效率。如果Getch获得的字符是数字，则继续用Getch获取数字，并把它们拼成一个整数或实数，然后把SYM置为 INTEGER或REAL，并把拼成的数值放入NUM变量。如果识别出其它合法的符号（比如：赋值号、大于号、小于等于号等），则把SYM则成相应的类型。如果遇到不合法的字符，把SYM置成NUL。

语法分析子程序分析：

语法分析子程序采用了自顶向下的递归子程序法，语法分析同时也根据程序的语义生成相应三元代码，并提供了出错处理的机制。语法分析主要由分程序分析过程（BLOCK）、参数变量分析过程（ParaDeclaration）、参数变量处理过程（ParaGetSub）、数组处理过程（ParaGetSub）、常量定义分析过程（ConstDeclaration）、变量定义分析过程（Vardeclaration）、语句分析过程（Statement）、表达式处理过程（Expression）、项处理过程（Term）、因子处理过程（Factor）和条件处理过程（Condition）构成。这些过程在结构上构成一个嵌套的层次结构。除此之外，还有出错报告过程（Error）、代码生成过程（Gen）、测试单词合法性及出错恢复过程（Test）、登录名字表过程（Enter）、查询名字表函数（Position）以及列出类 PCODE代码过程（Listcode）作过语法分析的辅助过程。

由PL/0的语法图可知：一个完整的PL/0程序是由分程序和句号构成的。因此，本编译程序在运行的时候，通过主程序中调用分程序处理过程block来分析分程序部分（分程序分析过程中还可能会递归调用block过程），然后，判断最后读入的符号是否为句号。如果是句号且分程序分析中未出错，则是一个合法的PL/0程序，可以运行生成的代码，否则就说明源PL/0程序是不合法的，输出出错提示即可。

if-then-else语句的处理：

按if语句的语法，首先调用逻辑表达式处理过程处理if语句的条件，把相应的真假值放到数据栈顶。接下去记录下代码段分配位置（即下面生成的jpc指令的位置），然后生成 条件转移jpc指令（遇0或遇假转移），转移地址未知暂时填0。然后调用语句处理过程处理 then语句后面的语句或语句块。then后的语句处理完后，如果遇到else，就调用语句处理过程处理else语句后面的语句或语句块，这时当前代码段分配指针的位置就应该是上面的jpc指令的转移位置。通过前面记录下的jpc指令的位置，把它的跳转位置改成当前的代码段指针位置，否则没遇到else，那么此时的当前代码段分配指针的位置也是上面jpc指令的转移位置，也是通过前面记录下的jpc位置指令的位置，把它的跳转到当前的代码段指针位置。

Repeat语句的处理：

首先用CX1变量记下当前代码段分配位置，作为循环的开始位置。然后通过递归调用语句分析过程分析，直到遇到until保留字，如果未对应until则出错。调用条件表达式处理过程生成相应代码把结果放在数据栈顶，再生成条件转移指令，转移位置为上面记录的CX1。

五、相关代码及运行结果

实验代码； PL0.h代码： #include #include #include #include #include #include

#ifndef WIRTH_ZYC_ #define WIRTH_ZYC_ using namespace std;

const int norw = 16;

// no.of reserved words 保留字的个数

const int txmax = 100;

// length of identifier table 标示符表的长度（容量）const int al = 10;

// length of identifiers 标示符的最大长度

const int nmax = 14;

// max.no.of digits in numbers 数字的最大长度 const int amax = 2047;

// maximum address 寻址空间

const int levmax = 3;

// maximum depth of block nesting 最大允许的块嵌套层数 const int cxmax = 200;

// size of code array 类PCODE目标代码数组长度（可容纳代码行数）

const int lineLength = 82;// 行缓冲区长度

typedef enum {NUL,IDENT,NUMBER,PLUS,MINUS,TIMES,SLASH,ODDSYM,EQL,NEQ,LSS,LEQ,GTR,GEQ,LPAREN，RPAREN,COMMA,SEMICOLON,PERIOD,BECOMES,BEGINSYM,ENDSYM,IFSYM,THENSYM,WHILESYM，WRITESYM,READSYM,DOSYM,CALLSYM,CONSTSYM,VARSYM,PROCSYM,ELSESYM,REPEATSYM,UNTILSYM} symbol;// symobl类型标识了不同类型的词汇

typedef char alfa[al+1];

// alfa类型用于标识符 typedef enum {CONSTANT,VARIABLE,PROCEDURE,ARRAY} obj0;

// 三种标识符的类型 typedef enum {LIT,OPR,LOD,STO,CAL,INT,JMP,JPC} fct;

// functions typedef set symset;

struct instruction{ fct f;// function code int l;// level,cann't big than levmax

int a;// displacement address,cann't big than amax };

// 类PCODE指令类型，包含三个字段：指令f、层差l和另一个操作数a

/******************************************* * lit 0,a: load constant a

* * opr 0,a: execute operation a

* * lod l,a: load variable l,a

* * sto l,a: store variable l,a

* * cal l,a: call procedure a at level l

* * int 0,a: increment t-register by a

* * jmp 0,a: jump to a

* * jpc 0,a: jump conditional to a

* *******************************************/

typedef struct{ alfa name;obj0 kind;union {

struct{int level,adr,size;}inOther;

int val;}other;} Table;

class PL0 {

protected:

bool listswitch,sourceEnd;char ch;

// last character read symbol sym;

// last symbol read alfa id;

// last identifier read int num;

// last number read

int cc;

// character count int ll;

// line length int kk,err;int cx;

// code allocation index int codeNo;

// code line no.static string errStr[];

// error string

char line[lineLength];

// code line vector errorString;

// error array alfa a;

// 词法分析器中用于临时存放正在分析的词

instruction code[cxmax+1];

// destination code array

alfa word[norw+1];

// 保留字表

symbol wsym[norw+1];

// 保留字表中每一个保留字对应的symbol类型

symbol ssym[100];

// 一些符号对应的symbol类型表

合 char mnemonic[8][6];

// 类PCODE指令助记符表

symset declbegsys,statbegsys,facbegsys;// 声明开始、表达式开始和项开始符号集 Table table[txmax+1];

// 符号表

FILE* fin,*fout;

public:

PL0(char* source,char*destination);

~PL0(){fclose(fin),fclose(fout);}

void error(int n);

位置和出错代码

void getsym();

个单词

void getch();

个字符

void gen(fct x,int y,int z);

程序区

void test(symset s1,symset s2,int n);

合法

void block(int lev,int tx,symset fsys);

void enter(obj0 k,int &tx,int &dx,int lev);

int position(alfa id,int tx);的位置

void constdeclaration(int&tx,int&dx,int lev);

void vardeclaration(int&tx,int&dx,int lev);

void listcode(int cx0);

void statement(symset fsys,int tx,int lev);

void expression(symset fsys,int tx,int lev);

void term(symset fsys,int tx,int lev);

void factor(symset fsys,int tx,int lev);

void condition(symset fsys,int tx,int lev);

void arraydeclaration(int& tx,int& dx,int lev);

void interpret();

执行程序

int base(int l,int b,int s[]);

基地址

void SaveCode();

// 构造函数

// 析构函数

// 出错处理，打印出错

// 词法分析，读取一

// 漏掉空格，读取一// 生成目标代码，并送入目标

// 测试当前单词符号是否

// 分程序分析处理过程

// 登入名字表

// 查找标示符在名字表中

// 常量定义处理

// 变量说明处理

// 列出目标代码清单

// 语句部分处理

// 表达式处理

// 项处理

// 因子处理

// 条件处理

// 数组说明处理

// 对目标代码的解释

// 通过静态链求出数据区的 // 保存代码

};#endif PL0.cpp代码： #include “pl0.h”

// 错误字符串数组

string PL0::errStr[]={“",”error 0001: 常数说明中“=”写成“：=”“, ”error 0002: 常数说明中的“=”后应为数字“, ”error 0003: 常数说明中的标识符后应是“=”“, ”error 0004: const,var,procedure后应为标识符“, ”error 0005: 漏掉了‘,’或‘;’“, ”error 0006: 过程说明后的符号不正确（应是语句开始符或过程开始符）“, ”error 0007: 应是语句开始符“, ”error 0008: 过程体内语句部分的后跟符不正确“, ”error 0009: 程序皆为丢了句号‘.’“, ”error 0010: 语句之间漏了‘;’“, ”error 0011: 标识符没说明“, ”error 0012: 赋值语句中，赋值号左部标识符属性应是变量“, ”error 0013: 赋值语句左部标识符应是赋值号:=“, ”error 0014: call后应为标识符“, ”error 0015: call后标识符属性应为过程“, ”error 0016: 条件语句中丢了then“, ”error 0017: 丢了end或;“, ”error 0018: while型循环语句中丢了do“, ”error 0019: 语句后的标识符不正确“, ”error 0020: 应为关系运算符“, ”error 0021: 表达式内标识符属性不能是过程“, ”error 0022: 表达式中漏掉了右括号‘)’“, ”error 0023: 因子后的非法符号“, ”error 0024: 表达式开始符不能是此符号“, ”error 0025: 文件在不该结束的地方结束了“, ”error 0026: 结束符出现在不该结束的地方“, ”error 0027: “,”error 0028: “,”error 0029: “,”error 0030: “, ”error 0031: 数越界“, ”error 0032: read语句括号中标识符不是变量“, ”error 0033: else附近错误“ , ”error 0034: repeat附近错误“};

// PL0构造函数

PL0::PL0(char* source,char*destination){ listswitch=true,sourceEnd=false;

strcpy(word[1],”begin“);

// 初始化存储保留字

strcpy(word[2],”call“);strcpy(word[3],”const“);

strcpy(word[4],”do“);strcpy(word[5],”else“);strcpy(word[6],”end“);strcpy(word[7],”if“);strcpy(word[8],”odd“);strcpy(word[9],”procedure“);strcpy(word[10],”read“);

strcpy(word[11],”repeat“);strcpy(word[12],”then“);strcpy(word[13],”until“);strcpy(word[14],”var“);

strcpy(word[15],”while“);strcpy(word[16],”write“);

wsym[1]= BEGINSYM;

wsym[2]= CALLSYM;留字对应的symbol类型

wsym[3]= CONSTSYM;

wsym[4]= DOSYM;wsym[5]= ELSESYM;

wsym[6]= ENDSYM;wsym[7]= IFSYM;

wsym[8]= ODDSYM;wsym[9]= PROCSYM;

wsym[10]= READSYM;

wsym[11]= REPEATSYM;wsym[12]= THENSYM;wsym[13]= UNTILSYM;wsym[14]= VARSYM;

wsym[15]= WHILESYM;wsym[16]= WRITESYM;

memset(code,0,sizeof(code));memset(ssym,0,100*sizeof(symbol));memset(table,0,sizeof(table));memset(line,0,sizeof(line));

ssym['+']= PLUS;

类型表

ssym['-']= MINUS;ssym['*']= TIMES;ssym['/']= SLASH;ssym['(']= LPAREN;ssym[')']= RPAREN;ssym['=']= EQL;ssym[',']= COMMA;ssym['.']= PERIOD;

// 初始化保留字表中每一个保

// 初始化一些符号对应的symbol

ssym['#']= NEQ;ssym['<']= LSS;ssym['>']= GTR;ssym[';']= SEMICOLON;

strcpy(mnemonic[LIT],” lit “);

// 初始化类PCODE指令助记符表

strcpy(mnemonic[OPR],” opr “);strcpy(mnemonic[LOD],” lod “);strcpy(mnemonic[STO],” sto “);strcpy(mnemonic[CAL],” cal “);strcpy(mnemonic[INT],” int “);strcpy(mnemonic[JMP],” jmp “);strcpy(mnemonic[JPC],” jpc “);

declbegsys.insert(CONSTSYM),declbegsys.insert(VARSYM),declbegsys.insert(PROCSYM);// 初始化声明开始符号集合 statbegsys.insert(BEGINSYM),statbegsys.insert(CALLSYM),statbegsys.insert(IFSYM),statbegsys.insert(WHILESYM);// 初始化表达式开始符号集合facbegsys.insert(IDENT),facbegsys.insert(NUMBER),facbegsys.insert(LPAREN);// 初始化项开始符号集合

err= 0;cc= 0;

// 行缓冲区指针

cx= 0;

// 代码分配指针，代码生成模块总在cx所指位置生成新的代码

ll= 0;

// 行缓冲区长度

ch= ' ';

// last character read

}

kk= al;

// 引入此变量是出于程序性能考虑 codeNo=0;

// code line no.fin=fopen(source,”r“);fout=fopen(destination,”w“);// 出错处理，打印出错位置和出错代码 void PL0::error(int n){ char s[10];sprintf(s,”第 %d 行:“,codeNo);errorString.push_back(s+errStr[n]);err= err+1;//error count }//error end // 词法分析，读取一个单词

void PL0::getsym(){ if(sourceEnd)

return;int i,j,k;while(ch ==' '||ch==9)

getch();

// cls space and tab if(isalpha(ch))// id or reserved word {

k=0;

memset(a,0,al+1);

// 检测一个单词长度 do{ if(k < al){

a[k]= ch;

k= k+1;} getch();if(sourceEnd)

return;}while(isalpha(ch)||isdigit(ch));if(k >= kk)kk = k;else { do{

a[kk]= ' ';

kk= kk-1;}while(kk > k);} strcpy(id,a);i= 1;j= norw;// 判断是否是关键字（二分搜索）do{ k=(i+j)/ 2;if(strcmp(id, word[k])<=0)

j= k-1;if(strcmp(id,word[k])>=0)

i= k+1;}while(i<=j);if(i-1 > j)

sym= wsym[k];else

sym= IDENT;} else if(isdigit(ch))// number { k= 0;num= 0;sym= NUMBER;do{

num= 10 * num + ch-'0';

k= k+1;

getch();}while(isdigit(ch));if(k > nmax)

error(30);} else if(ch == ':'){ getch();if(ch == '='){

sym= BECOMES;

getch();} else

sym= NUL;} else if(ch == '<')

// extra stuff added to support <= { getch();if(ch== '='){

sym= LEQ;

getch();} else

sym= LSS;} else if(ch == '>'){ getch();if(ch == '='){

sym= GEQ;

getch();} else

sym= GTR;} else

// end of extra stuff { sym= ssym[ch];// 其它符号的赋值

getch();} }

// 漏掉空格，读取一个字符

void PL0::getch(){ if(cc == ll){

if(feof(fin))

{

if(sym!=PERIOD)

error(25);

sourceEnd=true;

return;

}

cc= 0;

fgets(line,lineLength,fin);

codeNo++;

ll=strlen(line);

if(line[ll-1]==10)ll--;} ch= line[cc];cc= cc+1;}

// 生成目标代码，并送入目标程序区void PL0::gen(fct x,int y,int z){ if(cx > cxmax){

cout<<”Program too longn“;

return;}

code[cx].f= x;code[cx].l= y;code[cx].a= z;

cx= cx+1;}//gen end

// 测试当前单词符号是否合法

void PL0::test(symset s1,symset s2,int n){ if(sourceEnd)

return;if(s1.find(sym)==s1.end()){

error(n);

symset::iterator it;

for(it=s2.begin();it!=s2.end();it++)

s1.insert(*it);//s1=s1+s2

while(s1.find(sym)==s1.end())

getsym();} }//test end

// 分程序分析处理过程

void PL0::block(int lev,int tx,symset fsys){ if(sourceEnd)

return;int dx;// data allocation index int tx0;// initial table index int cx0;// initial code index

dx= 3;

// 变量的个数 tx0= tx;// 表指针

table[tx].other.inOther.adr= cx;gen(JMP,0,0);if(lev>levmax)error(32);do{

if(sym == CONSTSYM)

// 处理常量声明

{

getsym();

do{

constdeclaration(tx,dx,lev);

while(sym == COMMA)

{

}

getsym();

constdeclaration(tx,dx,lev);} if(sym ==SEMICOLON)

getsym();else

error(5);}while(sym==IDENT);if(sym == VARSYM)

// 处理变量声明 { getsym();do{

vardeclaration(tx,dx,lev);

while(sym == COMMA){

getsym();

vardeclaration(tx,dx,lev);

}

if(sym ==SEMICOLON)

getsym();

else

error(5);}while(sym==IDENT);} while(sym ==PROCSYM)

// 处理过程的声明 { getsym();if(sym ==IDENT){

enter(PROCEDURE,tx,dx,lev);

getsym();} else

error(4);if(sym ==SEMICOLON)

getsym();else

error(5);symset tmp = fsys;tmp.insert(SEMICOLON);block(lev+1,tx,tmp);if(sym == SEMICOLON){

getsym();

symset tmp = statbegsys;

for(int i= IDENT;i<=PROCSYM;i++)

tmp.insert((symbol)i);

test(tmp,fsys,6);

}

else

error(5);

}

symset tmp=statbegsys;

tmp.insert(IDENT);

test(tmp,declbegsys,7);}while(declbegsys.find(sym)!=declbegsys.end());

code[table[tx0].other.inOther.adr].a= cx;table[tx0].other.inOther.adr= cx;// start adr of code table[tx0].other.inOther.size=dx;

cx0= cx;gen(INT,0,dx);symset tmp=statbegsys;for(int i=SEMICOLON;i <= ENDSYM;i++)

tmp.insert((symbol)i);statement(tmp,tx,lev);gen(OPR,0,0);// return symset s2;test(fsys,s2,8);listcode(cx0);}// block end

// 登入名字表

void PL0::enter(obj0 k,int &tx,int &dx,int lev){ tx= tx+1;strcpy(table[tx].name,id);table[tx].kind=k;switch(k){ case CONSTANT:

if(num>amax)

{

error(31);

num=0;

}

table[tx].other.val=num;

break;case VARIABLE:

table[tx].other.inOther.level=lev;

table[tx].other.inOther.adr=dx;

dx++;

break;case PROCEDURE:

table[tx].other.inOther.level=lev;

break;case ARRAY:

table[tx].other.inOther.size = lev;

break;} }//enter end

// 查找标示符在名字表中的位置

int PL0::position(alfa id,int tx)//find identifier id in table { int i;strcpy(table[0].name, id);i= tx;while(strcmp(table[i].name,id)!=0)i--;return i;}//position end

// 常量定义处理

void PL0::constdeclaration(int&tx,int&dx,int lev){ if(sym == IDENT){

getsym();

if(sym>=EQL&&sym<=BECOMES)

{

if(sym ==BECOMES)

error(1);

getsym();

if(sym == NUMBER)

{

enter(CONSTANT,tx,dx,lev);

getsym();

}

else

error(2);

}

else

error(3);} else

error(4);}// constdeclaration end

// 变量说明处理

void PL0::vardeclaration(int&tx,int&dx,int lev){ if(sym == IDENT){

enter(VARIABLE,tx,dx,lev);

getsym();} else

error(4);}//vardeclaration end

// 数组说明处理

void PL0::arraydeclaration(int&tx,int&dx,int lev){

int upscript=0,downscript=0;getsym();if(sym == NUMBER || sym == CONSTSYM){

if(num == 0)

{

upscript = num;

getsym();

}

else

error(32);} if(sym == COMMA)

getsym();else

error(32);if(sym == NUMBER || sym == CONSTSYM){

downscript = num;

getsym();} if(sym!= RPAREN)

} error(32);else { enter(ARRAY,tx,dx,downscript+1);getsym();} // 列出目标代码清单

void PL0::listcode(int cx0)//list code generated for this block { int i;if(listswitch)

for(i= cx0;i

cout<<”“<

<<”“<

// 语句部分处理

void PL0::statement(symset fsys,int tx,int lev){ if(sourceEnd)

return;int i,cx1,cx2;if(sym ==IDENT){

i= position(id,tx);

if(i == 0)

error(11);

else if(table[i].kind!=VARIABLE)

{

error(12);

i= 0;

}

getsym();

if(sym ==BECOMES)

getsym();

else

error(13);

expression(fsys,tx,lev);

if(sym!= SEMICOLON)

error(10);

if(i!= 0)

gen(STO,lev-table[i].other.inOther.level,table[i].other.inOther.adr);

} else if(sym == READSYM){ getsym();if(sym!=LPAREN)

error(34);else

do{

getsym();

if(sym==IDENT)

i=position(id,tx);

else

i=0;

if(i==0)

error(35);

else

{

gen(OPR,0,16);

gen(STO,lev-table[i].other.inOther.level,table[i].other.inOther.adr);

}

getsym();

}while(sym == COMMA);

if(sym!= RPAREN)

{

error(33);

while(fsys.find(sym)!=fsys.end())getsym();

}

else

getsym();} else if(sym == WRITESYM){ getsym();if(sym==LPAREN){

do{

getsym();

symset tmp=fsys;

for(int t=RPAREN;t<=COMMA;t++)

tmp.insert((symbol)t);

expression(tmp,tx,lev);

gen(OPR,0,14);

}while(sym==COMMA);

if(sym!=RPAREN)

error(33);

else

getsym();} gen(OPR,0,15);} else if(sym ==CALLSYM){ getsym();if(sym!=IDENT)

error(14);else {

i= position(id,tx);

if(i == 0)

error(11);

else if(table[i].kind = PROCEDURE)

gen(CAL,lev-table[i].other.inOther.level,table[i].other.inOther.adr);

else

error(15);

getsym();} } else if(sym ==IFSYM){ getsym();symset tmp=fsys;for(int i = THENSYM;i<= DOSYM;i++)

tmp.insert((symbol)i);condition(tmp,tx,lev);if(sym == THENSYM)

getsym();else

error(16);cx1= cx;gen(JPC,0,0);tmp.insert(ELSESYM);statement(tmp,tx,lev);getsym();

code[cx1].a= cx;

if(sym == ELSESYM){

getsym();

cx2=cx;

gen(JMP,0,0);

code[cx1].a=cx;

statement(fsys,tx,lev);

code[cx2].a=cx;} } else if(sym ==BEGINSYM){ getsym();symset tmp=fsys;for(int i=SEMICOLON;i<=ENDSYM;i++)

tmp.insert((symbol)i);statement(tmp,tx,lev);tmp=statbegsys;tmp.insert(SEMICOLON);while(tmp.find(sym)!=tmp.end()){

if(sourceEnd)return;

if(sym ==SEMICOLON||sym ==ENDSYM)

getsym();

else if(sym=PERIOD)

{

error(26);

getsym();

}

else

error(10);

tmp=fsys;

for(i=SEMICOLON;i<=ENDSYM;i++)

tmp.insert((symbol)i);

if(sourceEnd)return;

if(sym==ENDSYM)

break;

statement(tmp,tx,lev);} if(sym ==ENDSYM)

getsym();else if(!sourceEnd)

error(17);} else if(sym ==WHILESYM){ cx1= cx;

// 记下当前代码分配位置，这是while循环的开始位置

getsym();symset tmp=fsys;tmp.insert(DOSYM);condition(tmp,tx,lev);

cx2= cx;

// 记下当前代码分配位置，这是while的do中的语句的开始位置

gen(JPC,0,0);

if(sym ==DOSYM)

getsym();

else

error(18);

statement(fsys,tx,lev);

gen(JMP,0,cx1);

code[cx2].a= cx;} else if(sym == REPEATSYM){

symset temp1, temp2;

temp1= fsys,temp1.insert(SEMICOLON),temp1.insert(UNTILSYM);

cx1= cx;

getsym();

statement(temp1,tx,lev);

temp2 = statbegsys;

temp2.insert(SEMICOLON);

while(temp2.find(sym)!= temp2.end())

{

if(sym == SEMICOLON)

getsym();

else

error(34);

statement(temp1,tx,lev);

}

if(sym == UNTILSYM)

{

getsym();

condition(fsys,tx,lev);

gen(JPC,0,cx1);

}

else

error(34);

} symset setT;test(fsys,setT,19);}//statement end

// 表达式处理

void PL0::expression(symset fsys,int tx,int lev){ symbol addop;symset tmp=fsys;for(int t=PLUS;t<=MINUS;t++)

tmp.insert((symbol)t);if(sym>=PLUS&&sym<=MINUS){

addop= sym;

getsym();

term(tmp,tx,lev);

if(addop ==MINUS)

gen(OPR,0,1);} else

term(tmp,tx,lev);while(sym >=PLUS&&sym<=MINUS){

addop= sym;

getsym();

term(tmp,tx,lev);

if(addop ==PLUS)

gen(OPR,0,2);

else

gen(OPR,0,3);} }// expression end

// 项处理

void PL0::term(symset fsys,int tx,int lev){ if(sourceEnd)

return;symbol mulop;symset tmp=fsys;for(int t=TIMES;t<=SLASH;t++)

tmp.insert((symbol)t);factor(tmp,tx,lev);while(sym>=TIMES && sym<=SLASH){

mulop= sym;

getsym();

factor(tmp,tx,lev);

if(mulop ==TIMES)

gen(OPR,0,4);

else

gen(OPR,0,5);} }// term end

// 因子处理

void PL0:: factor(symset fsys,int tx,int lev){ int i;test(facbegsys,fsys,24);while(facbegsys.find(sym)!=facbegsys.end()){

if(sym ==IDENT)

{

i= position(id,tx);

if(i == 0)

error(11);

else

switch(table[i].kind)

{

case CONSTANT:

gen(LIT,0,table[i].other.val);

break;

case VARIABLE:

gen(LOD,lev-table[i].other.inOther.level,table[i].other.inOther.adr);

break;

case PROCEDURE:

error(21);

break;

}

getsym();

}

else if(sym ==NUMBER)

{

if(num>amax)

{

error(31);

num= 0;

}

gen(LIT,0,num);

getsym();

}

else if(sym ==LPAREN)

{

getsym();

symset tmp=fsys;

tmp.insert(RPAREN);

expression(tmp,tx,lev);

if(sym == RPAREN)

getsym();

else

error(22);

}

test(fsys,facbegsys,23);} }//factor end

// 条件处理

void PL0::condition(symset fsys,int tx,int lev){ symbol relop;symset tmp=fsys;tmp.insert(EQL),tmp.insert(NEQ),tmp.insert(LSS),tmp.insert(LEQ),tmp.insert(GTR),tmp.insert(GEQ);

if(sym == ODDSYM){

getsym();

expression(fsys,tx,lev);

gen(OPR,0,6);} else {

expression(tmp,tx,lev);

if(tmp.find(sym)==tmp.end())

error(20);

else

{

relop= sym;

getsym();

expression(fsys,tx,lev);

switch(relop)

{

case EQL: gen(OPR,0,8);

break;

case NEQ: gen(OPR,0,9);

break;

case LSS: gen(OPR,0,10);

break;

case GEQ: gen(OPR,0,11);

break;

case GTR: gen(OPR,0,12);

break;

case LEQ: gen(OPR,0,13);

break;

}

} } }//condition end

// 对目标代码的解释执行程序

void PL0::interpret(){ int err1=errorString.size();if(err1>0){

cout<<”存在%d个错误:“<

cout<

t= t+1;

s[t]= i.a;

break;case OPR:

switch(i.a)//operator

{ case 0:// return t= b-1;

p= s[t+3];

b= s[t+2];break;case 1: s[t]=-s[t];break;case 2: t= t-1;s[t]= s[t]+s[t+1];break;case 3: t= t-1;s[t]= s[t]-s[t+1];break;case 4: t= t-1;s[t]= s[t]*s[t+1];break;case 5: t= t-1;s[t]= s[t] / s[t+1];break;case 6: if(s[t]%2)

s[t]=1;else

s[t]=0;break;case 8: t= t-1;if(s[t]==s[t+1])

s[t]=1;else

s[t]=0;break;case 9: t= t-1;if(s[t]==s[t+1])

s[t]=0;else

s[t]=1;break;

case 10: t= t-1;if(s[t]

s[t]=1;else

s[t]=0;break;case 11: t= t-1;if(s[t]>=s[t+1])

s[t]= 1;else

s[t]=0;break;case 12: t= t-1;if(s[t]>s[t+1])

s[t]= 1;else

s[t]=0;break;case 13: t= t-1;if(s[t]<=s[t+1])

s[t]= 1;else

s[t]=0;break;case 14: cout<<”“<>s[t];break;};break;case LOD:

t= t+1;

s[t]= s[base(i.l,b,s)+i.a];

break;

case STO:

s[base(i.l,b,s)+i.a]= s[t];

t= t-1;

break;

case CAL:// generate new block mark

s[t+1]= base(i.l,b,s);

s[t+2]= b;

s[t+3]= p;

b= t+1;

p=i.a;

break;

case INT:

t= t+i.a;

break;

case JMP:

p= i.a;

break;

case JPC:

if(s[t] == 0)

p= i.a;

t= t-1;

break;

}//switch end

}while(p!=0);

cout<<” End PL/0n“;} // interpret end

// 通过静态链求出数据区的基地址

int PL0::base(int l,int b,int s[]){ int b1;b1= b;//find base l levels down while(l>0){

b1= s[b1];

l= l-1;} return b1;}

// 保存代码

void PL0::SaveCode(){ if(fout)

for(int i=0;i

fprintf(fout,”%d %s %d %dn “,i,mnemonic[code[i].f],code[i].l,code[i].a);} TestPL0.cpp代码： #include ”pl0.h“ void main(){ PL0 cp(”testPas2.txt“,”nasm.txt");

symset fsys;

fsys.insert(PERIOD);fsys.insert(CONSTSYM),fsys.insert(VARSYM),fsys.insert(PROCSYM);fsys.insert(BEGINSYM),fsys.insert(CALLSYM),fsys.insert(IFSYM),fsys.insert(WHILESYM);cp.getsym();

// 词法分析，分析一个词

cp.block(0,0,fsys);

// 分程序分析处理功能

cp.SaveCode();

// 保存代码

cp.interpret();

// 对目标代码的解释执行程序

} 实验运行结果：

运行的的文件见下图右侧：实验中我是固定了文件名的，可以是改写成动态输入，由于在测试中我把所有的测试语句都放在同一个文件中了，没有太多的必要。

六、心得体会

在编译程序实现的过程中反复使用了递归调用的思想，且也使用了模块化处理问题的思想，使用模块化的思想关键是在抽象阶段要抽象出对应的模块，且模块的层次必须是清晰的。

在实现此程序中，由于要实现关键字和符号表中字段的搜索，实现中就必须注意快速查找的方法，而在实现的过程中多次用到了二分搜索的方法，这是个比较快的搜索方法。

由于此程序的实现相对比较复杂，且不方便调试，改进时可以把此程序的词法分析，语法分析和执行原代码作为单独的测试程序来测试，这样也方便大家来调试。

通过本次的课设我知道了一个算法的设计是需要静下心来仔细的研究的，且实现中必须先了解程序的整个流程，也就是说在编程中首先必须看懂那些对应的UML图，只有在图的指导下，编程中才不会盲目，也有一定的方向性。同样在编程中必须注意代码的规范，多写一些对应的注释是很必要的，要时刻想这代码并不是给你自己看的，而是必须要给别人看，因此我觉得代码的规范是相当重要的。

第四篇：编译原理课程设计设计任务书

编译原理课程设计任务书

1、目的学生在学习《程序设计语言编译原理》课程过程中，结合各章节的构造编译程序的基本理论，总共用10个课时完成课程设计。在基本实验完成的基础上，逐步完成课程设计。要求用C或C++语言描述及上机调试，实现一个小编译器（词法分析，语法分析，中间代码产生，优化，目标代码生成等重要子程序，其中词法分析、语法分析及语义分析功能必须完成），使学生将理论与实际应用结合起来，受到软件设计等开发过程的全面训练，从而提高学生软件开发的能力。

2、课程设计的任务

（1）设计符号表

确定符号表的组织方式，一般应包括名字栏和信息栏，其中名字栏作为关键字。要考虑能够存储有关名字的信息，并可以高效地完成如下操作：

a.查找：根据给定的名字，在符号表中查找其信息。如果该名字在符号表中不存在，则将其加入到符号表中，否则返回指向该名字的指针；

b.删除：从符号表中删除给定名字的表项。

（2）设计词法分析器

设计各单词的状态转换图，并为不同的单词设计种别码。将词法分析器设计成供语法分析器调用的子程序。功能包括：

a.具备预处理功能。将不翻译的注释等符号先滤掉，只保留要翻译的符号串，即要求设计一个供词法分析调用的预处理子程序；

b.能够拼出语言中的各个单词；

c.将拼出的标识符填入符号表；

d.返回（种别码，属性值）。

（3）语法分析与中间代码产生器

要求用预测分析法、递归下降分析法、算符优先分析法、SLR分析法（几种方法任选），实现对表达式、各种说明语句、控制语句进行语法分析。

若语法正确，则用语法制导翻译法进行语义翻译：对说明语句，要求将说明的各符号记录到相应符号表中；对可执行语句，应产生出四元式中间代码并填写到三地址码表中；

若语法错误，要求指出出错性质和出错位置（行号）。出错处理应设计成一个出错处理子程序。

（4）优化器

a.局部优化：设计出划分基本块的算法，在每一个基本块中实现：合并已知量、删除多余运算和删除无用赋值三种局部优化。设计构造基本块的DAG图的算法，以及将DAG图还原实现基本块的优化的算法。

b.循环优化：只做一重循环优化，完成代码外提，强度削弱和删除归纳变量等三种优化。要求实现while循环和for循环语句的优化。

（5）目标代码生成器

能完成指定寄存器个数的情况下将一中间代码程序段翻译成汇编语言目标代码（汇编指令应包括加、减、乘、除），要求指令条数最少的情况下，尽量使用寄存器，尽量少访问内存，这样才能做到运行效率高。

3、样本语言

样本语言为C-语言(见附录)，其中基本的语句要求必须实现，其余部分可根据自己的实际情况选择实现。

4、要求

各函数和过程应有框图描述，有功能说明，有入口和出口参数说明。

5、参考资料

《程序设计语言编译原理》，陈火旺编著，国防工业出版社

《编译原理》，吕映芝、张素琴、蒋维杜编著，清华大学出版社

《编译原理》，Alfred V.Aho等，李建中译，机械工业出版社

6、考察方式

最终完成一个完整的编译程序。要求输入一小段完整的C-语言源程序，输出各编译阶段的运行结果。在课程设计结束时上机运行，展示运行效果。

7、作业提交

最晚在期末（第17周课程结束时）提交纸质作业及可运行程序，格式参考学院的规定课程设计任务书模板。

第五篇：编译原理课程设计心得体会

经过一个星期的编译原理课程设计，本人在刘贞老师的指导下，顺利完成该课程设计。通过该课程设计，收获颇多。

一、对实验原理有更深的理解

通过该课程设计，掌握了什么是编译程序，编译程序工作的基本过程及其各阶段的基本任务，熟悉了编译程序总流程框图，了解了编译程序的生成过程、构造工具及其相关的技术对课本上的知识有了更深的理解，课本上的知识师机械的，表面的。通过把该算法的内容，算法的执行顺序在计算机上实现，把原来以为很深奥的书本知识变的更为简单，对实验原理有更深的理解。

二、对该理论在实践中的应用有深刻的理解

通过把该算法的内容，算法的执行顺序在计算机上实现，知道和理解了该理论在计算机中是怎样执行的，对该理论在实践中的应用有深刻的理解。

三、激发了学习的积极性本文转载在www.xiexiebang.com代写之家

通过该课程设计，全面系统的理解了编译原理程序构造的一般原理和基本实现方法。把死板的课本知识变得生动有趣，激发了学习的积极性。把学过的计算机编译原理的知识强化，能够把课堂上学的知识通过自己设计的程序表示出来，加深了对理论知识的理解。以前对与计算机操

copyright

www.chazidian

作系统的认识是模糊的，概念上的，现在通过自己动手做实验，从实践上认识了操作系统是如何处理命令的，如何协调计算机内部各个部件运行，对计算机编译原理的认识更加深刻。课程设计中程序比较复杂，在调试时应该仔细，在程序调试时，注意指针，将不必要的命令去除。

在这次课程设计中，我就是按照实验指导的思想来完成。加深了理解文件系统的内部功能及内部实现，培养实践动手能力和程序开发能力的目的。