合肥工业大学编译原理课程设计Word格式.docx

合肥工业大学编译原理课程设计Word格式.docx

《合肥工业大学编译原理课程设计Word格式.docx》由会员分享，可在线阅读，更多相关《合肥工业大学编译原理课程设计Word格式.docx（12页珍藏版）》请在冰点文库上搜索。

要求：

对任意给定的一个NFAM（其状态转换矩阵及初态、终态信息保存在指定文件中）的某一个状态子集I，显示输出构造出的ε-CLOSURE（I）。

4．题目：

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

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

5．题目：

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

构造一转换程序，实现将用户任意给定的有限自动机FAM，转换为与之等价的右线性文法，显示输出或输出到文件中。

6．题目：

有限自动机的状态转换图显示程序的实现

构造一程序，实现：

将任一给定的有限自动机M（其状态转换矩阵及初态、终态信息保存在指定文件中），在屏幕上显示输出M的状态转换图。

程序应具有通用性，状态节点在屏幕上的分布应合理、美观。

7．题目：

从NFA构造与之等价的正规式r的程序实现

对给定的任意NFAM（其状态转换矩阵及初态、终态信息分别保存在指定文件中）。

构造一程序，从NFA构造与之等价的正规式r，并显示输出。

8．题目：

构造正规式r1|r2（或运算）的NFA的程序实现

对给定的正规式r1、r2，已知它们的NFA分别为M1、M2（其状态转换矩阵及初态、终态信息分别保存在指定文件中）。

构造一程序，由此程序构造正规式r1|r2（或运算）的NFA（将其状态转换矩阵及初态、终态信息保存在指定文件中）。

9．题目：

构造正规式r1r2（连接运算）的NFA的程序实现

构造一程序，由此程序构造正规式r1r2（连接运算）的NFA（将其状态转换矩阵及初态、终态信息保存在指定文件中）。

10．题目：

构造正规式r*（闭包运算）的NFA的程序实现

对给定的正规式r，已知其NFA为M（其状态转换矩阵及初态、终态信息保存在指定文件中）。

构造一程序，由此程序构造正规式r*（闭包运算）的NFA（将其状态转换矩阵及初态、终态信息保存在指定文件中）。

11．题目：

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

首先构造一个语法分析程序，实现对任意正规式的语法分析。

语法分析方法采用自下而上的分析方法（如算符优先分析，或LR分析）。

在此语法分析器的基础上，按照语法制导的思想，增加构造NFA的功能。

生成的NFA将其状态转换矩阵及初态、终态信息保存在指定文件中。

进一步实现把NFA确定化为DFA的算法（其状态转换矩阵及初态、终态信息保存在指定文件中）。

12．题目：

DFAM状态最少化的程序实现

将给定的DFAM（其状态转换矩阵及初态、终态信息保存在指定文件中）的有限状态集S划分成若干互不相交的子集，使得：

任何不同的两个子集中的状态都是可区别的，而同一子集中的任何两个状态都是等价的（要利用Ia函数，但并不需要构造ε-CLOSURE函数，因这是DFA）。

输出化简后的DFAM’（其状态转换矩阵及初态、终态信息保存在指定文件中）。

13．题目：

把NFA确定化为DFA的算法实现

将给定的NFAM（其状态转换矩阵及初态、终态信息保存在指定文件中），确定化为DFAM’。

（要先实现ε-CLOSURE函数和Ia函数）。

输出DFAM’（其状态转换矩阵及初态、终态信息保存在指定文件中）。

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）构造算法的程序实现

构造一程序，实现教材P.78的FIRST（X）集合的构造算法。

对任一给定的文法G，程序输出所有非终结符P的FIRST（P）。

19．题目：

集合FOLLOW（A）构造算法的程序实现

首先，构造一程序，实现教材P.78的FIRST（X）集合的构造算法。

在此基础上，构造一程序，实现教材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．题目：

预测分析程序的实现

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．题目：

算符优先分析算法的程序实现

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

T→T*F|F分析算法。

程序显示输出“移进-归约”的步骤。

F→P↑F|P

P→（E）|i

26．题目：

带出错处理的算符优先分析算法的程序实现

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

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给出的优先表构造算法。

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（输出其状态转换矩阵）。

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。

41．题目：

LALR

（1）项目集规范族构造程序的实现

假设对于给定文法，识别文法活前缀的DFA、LR

（1）项目集族已构造出来了。

构造一程序，检查两个LR

（1）项目集是否为同心集（可任意输入），若是，则输出合并后的同心集，并检查合并后的集合是否含有冲突项目（指出存在何种冲突），输出合并同心集后的识别文法活前缀的DFA，及LALR

（1）项目集规范族。

42．题目：

LALR

（1）分析表自动构造程序的实现

然后构造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输出（可按一定格式输出到指定文件中）。

47．题目：

将算术表达式转换成三元式的程序实现

设计一个语法制导翻译器，将算术表达式翻译成三元式。

对用户输入的任意一个正确的算术表达式，程序将其转换成三元式输出（可按一定格式输出到指定文件中）。

48．题目：

将算术表达式转换成间接三元式的程序实现

设计一个语法制导翻译器，将算术表达式翻译成间接三元式。

对用户输入的任意一个正确的算术表达式，程序将其转换成间接三元式输出（可按一定格式输出到指定文件中）。

49．题目：

将算术表达式转换成四元式的程序实现

设计一个语法制导翻译器，将算术表达式翻译成四元式。

对用户输入的任意一个正确的算术表达式，程序将其转换成四元式输出（可按一定格式输出到指定文件中）。

50．题目：

将布尔表达式转换成四元式的程序实现

设计一个语法制导翻译器，将布尔表达式翻译成四元式。

先确定一个定义布尔表达式的文法，为其设计一个语法分析程序，为每条产生式配备一个语义子程序，按照一遍扫描的语法制导翻译方法，实现翻译程序。

对用户输入的任意一个正确的布尔表达式，程序将其转换成四元式输出（可按一定格式输出到指定文件中）。

51．题目：

将条件语句转换成四元式的程序实现

设计一个语法制导翻译器，将条件语句翻译成四元式。

先确定一个定义条件语句的文法，为其设计一个语法分析程序，为每条产生式配备一个语义子程序，按照一遍扫描的语法制导翻译方法，实现翻译程序。

对用户输入的任意一个正确的条件语句，程序将其转换成四元式输出（可按一定格式输出到指定文件中）。

52．题目：

将WHILE语句转换成四元式的程序实现

设计一个语法制导翻译器，将WHILE语句翻译成四元式。

先确定一个定义WHILE语句的文法，为其设计一个语法分析程序，为每条产生式配备一个语义子程序，按照一遍扫描的语法制导翻译方法，实现翻译程序。

对用户输入的任意一个正确的WHILE语句，程序将其转换成四元式输出（可按一定格式输出到指定文件中）。

53．题目：

将FOR语句转换成四元式的程序实现

设计一个语法制导翻译器，将FOR语句翻译成四元式。

先确定一个定义FOR语句的文法，为其设计一个语法分析程序，为每条产生式配备一个语义子程序，按照一遍扫描的语法制导翻译方法，实现翻译程序。

对用户输入的任意一个正确的FOR语句，程序将其转换成四元式输出（可按一定格式输出到指定文件中）。

54．题目：

将SWITCH语句转换成四元式的程序实现

设计一个语法制导翻译器，将SWITCH语句翻译成四元式。

先确定一个定义SWITCH语句的文法，为其设计一个语法分析程序，为每条产生式配备一个语义子程序，按照一遍扫描的语法制导翻译方法，实现翻译程序。

对用户输入的任意一个正确的SWITCH语句，程序将其转换成四元式输出（可按一定格式输出到指定文件中）。

55．题目：

将包含数组引用的赋值语句转换成四元式的程序实现

设计一个语法制导翻译器，将包含数组引用的赋值语句翻译成四元式。

先确定一个定义包含数组引用的赋值语句的文法，为其设计一个语法分析程序，为每条产生式配备一个语义子程序，按照一遍扫描的语法制导翻译方法，实现翻译程序。

对用户输入的任意一个正确的包含数组引用的赋值语句，程序将其转换成四元式输出（可按一定格式输出到指定文件中）。

56．题目：

嵌套过程中的说明语句翻译的程序实现

设计一个语法制导翻译器，完成对说明语句的翻译，即构造每个过程的符号表，填写所有名字在符号表中的有关信息。

先确定一个定义允许嵌套过程的说明语句的文法，为其设计一个语法分析程序，为每条产生式配备一个语义子程序，按照一遍扫描的语法制导翻译方法，实现翻译程序。

对用户输入的任意一组正确的说明语句，程序将输出相应的符号表（可按一定格式输出到指定文件中）。

57．题目：

基本块划分算法的程序实现

根据基本块划分算法，构造一个基本块划分程序，实现：

对于任意输入的一个四元式程序，将其划分为基本块，输出各基本块，并输出程序流图。

以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节点构造顺序，重构基本块四元式代码。

以P.283例10.4为输入，完成并输出局部优化。

（待续）

。

（大家也可以自行设计一个设计题目）