《编译原理》课程设计题目 设计题一：正规式 r 与正规文法 G 相互转换的程序设计 任意给定一个正规式，求出其对应的正规文法；任意给定一个正规文法， 求出其对应的正规式。（参考教材 P53～55） 设计题二：布尔表达式的递归下降翻译器 针对布尔表达式的文法： 〈布尔表达式〉∷＝〈布尔项〉{〈与运算符〉〈布尔项〉} 〈与运算符〉∷＝and 〈布尔项〉∷＝ 〈布尔因子〉{〈或运算符〉〈布尔因子〉} 〈或运算符〉∷＝or 〈布尔因子〉∷＝ 〈非运算符〉〈布尔因子〉｜〈布尔量〉 〈非运算符〉∷＝not 〈布尔量〉∷＝（〈布尔表达式〉）｜〈标识符〉〈关系运算符〉〈标识符〉｜ true｜false 〈关系运算符〉∷＝ ＞｜＜｜≥｜≤｜＝｜≠ 〈标识符〉∷＝ 〈字母〉{〈字母〉｜〈数字〉} 利用递归下降分析法编制、调试其语法及语义分析程序，生成的中间代码 为逆波兰式。编制好分析程序后，设计若干用例，上机测试并通过所设计的分 析程序。（参考教材 P92～93） 设计题三：正规式 r 与有穷自动机 FA 相互转换的程序设计 任意给定一个正规式，求出其对应的有穷自动机；任意给定一个有穷自动 机，求出其对应的正规式。（参考教材 P61～64） 设计题四：赋值语句的 LR 翻译程序 对教材 P180 中的赋值语句文法，给出该文法的属性文法，同时实现赋值 语句的翻译，生成的中间代码为逆波兰式。（参考教材 P179～181） 设计题五：正规文法 G 与有穷自动机 FA 相互转换的程序设计 任意给定一个正规文法，求出其对应的有穷自动机；任意给定一个有穷自 

动机，求出其对应的正规文法。（参考教材 P65～66） 设计题六：条件语句的 LR 翻译程序 对教材 P187 中的条件语句文法，给出该文法的属性文法，同时实现条 件语句的翻译，生成的中间代码为四元式。（参考教材 P186～189） 设计题七：NFA 确定化为 DFA 及化简的程序设计 任意给定一个 NFA，将其确定化为 DFA，然后化简为最小的 DFA。（参 考教材 P57～61） 设计题八：布尔表达式的 LR 翻译器 针对布尔表达式的文法： B  B and T | T T  T or F | F F  not F |true｜false |（B）| i rop i 利用 LR 分析法编制、调试其语法及语义分析程序，生成的中间代码为四 元式。编制好分析程序后，设计若干用例，上机测试并通过所设计的分析程序。 （参考教材 P181～182） 设计题九：生成预测分析表的算法实现 任意给定一个 LL(1)文法，生成相应的 LL(1)分析表。（参考教材 P75 第 5 章） 设计题十： while 循环语句的 LR 翻译程序 对教材 P187 中的循环语句文法，给出该文法的属性文法，同时实现循环 语句的翻译，生成的中间代码为四元式。（参考教材 P186～189） 设计题十一：利用 LEX 自动生成词法分析程序 输入描述某种语言词法规则的正规式，利用 LEX 自动生成词法分析程序。 （参考教材 P66～68） 设计题十二：生成 LR 分析表的算法实现 任意给定一个 LR 文法，生成相应的 LR 分析表。（参考教材 P123 第 7 章） 设计题十三：布尔表达式翻译为逆波兰式的算法实现 针对布尔表达式的二义性文法： B  B and B | B or B | not B | 将文法拓广为G’[B’]： (0) B’  B ( B ) | true｜false | i rop i 

(1) (2) (3) (4) (5) (6) (7) B  B and B B  B or B B  not B B  ( B ) B  true B  false B  i rop i 利用 LR 分析法编制、调试其语法及语义分析程序，生成的中间代码为逆 波兰式。编制好分析程序后，设计若干用例，上机测试并通过所设计的分析程 序。 设计题十四：求解 FIRST 集和 FOLLOW 集的算法实现 任意给定一个上下文无关文法，求其所有的非终结符的 FIRST 集和 FOLLOW 集。（参考教材 P80～83） 设计题十五： for 循环语句的翻译程序 对教材 P191 中的循环语句文法，给出该文法的属性文法，同时实现循环 语句的翻译，生成的中间代码为四元式。（参考教材 P191～192） 设计题十六：简单说明语句的翻译程序 对教材 P196 中的简单说明语句文法，给出该文法的属性文法，同时实现 简单说明语句的翻译，即建立一个符号表，将简单说明语句所引入的名字 id 和性质登录在符号表中。（参考教材 P96～197） 设计题十七：基于 LR 分析法的计算器 对教材 P171 中的算术表达式文法，给出该文法的属性文法，同时实现算 术表达式的计算，给出算术表达式的计值过程。（参考教材 P171，P173～174） 设计题十八：预测分析程序的设计 对教材 P94 中的上下文无关文法，实现它的预测分析程序，给出符号串 i+i*i 的分析过程。（参考教材 P93～96） 或者：(选同一题的做下面一个) 对教材 P96 中的上下文无关文法，实现它的预测分析程序，给出符号串 aaabd 的分析过程。（参考教材 P96～97） 设计题十九： do-while 循环语句的翻译程序 对 C 语言中的 do-while 循环语句文法，给出该文法的属性文法，同时实 

现循环语句的翻译，生成的中间代码为四元式。（参考 while 循环语句的翻译， 教材 P186～189） 设计题二十：构造识别规范句型活前缀 DFA 的程序设计 对教材 P160 中的上下文无关文法，构造它的构造识别规范句型活前缀 DFA。（参考教材 P124～137，P160～161） 或者：(选同一题的做下面一个) 对教材 P162 中的上下文无关文法，构造它的构造识别规范句型活前缀 DFA。（参考教材 P124～137，P162～163） 设计题二十一：算符优先分析程序的设计 对教材 P110 中的上下文无关文法，实现它的算符优先分析程序，给出符 号串 i+i*i 的分析过程。（参考教材 P110～117） 设计题二十二：利用 YACC 自动生成语法分析程序 输入描述某种语言语法规则的 LALR（1）文法，利用 YACC 自动生成语 法分析程序。（参考教材 P147～153，P155～160） 设计题二十三：赋值语句的 LR 翻译程序 对教材 P180 中的赋值语句文法，给出该文法的属性文法，同时实现赋 值语句的翻译，生成的中间代码为四元式。（参考教材 P179～181） 设计题二十四：简单优先分析程序的设计 对教材 P104 中的上下文无关文法，实现它的简单优先分析程序，给出符 号串 b(aa)b 的分析过程。（参考教材 P103～106） 设计题二十五： DAG 优化过程的图形化设计 给出一系列四元式，用图形显示 DAG 的优化过程。（参考教材 P251～257） 设计题二十六： PL/0 编译程序的实现 对教材 P13 第二章中的讨论的 PL/0 编译程序，给出其程序实现，调试成 功。（参考教材 P13 第二章，P413 附录 A）