2020年硕士研究生入学考试大纲

考试科目名称：编译原理    考试时间：120分钟，满分：100分

一、考试内容和要求

1、了解编译程序、汇编程序与解释程序的区别，理解编译程序的结构及各阶段的任务，了解编译阶段的组合等概念。

2、掌握形式化方法：

词法的描述——三型文法、正规式；

语法的描述——二型文法；

语义处理的描述——属性文法。

3、掌握文法的概念：形式定义（四元组）、文法分类、句子、句型、推导、语法树、句型分析、短语、句柄、文法的等价。

4、掌握语言的概念，能完成文法和语言的相互变换。

5、理解生成方式和识别方式的区别，掌握正规文法、正规式、自动机的互相转换方法、NFA的确定化、DFA的最小化。

6、理解自顶向下语法分析面临的问题、解决思路及主要技术路线，掌握非LL(1)文法改写方法、FIRST、FOLLOW集和SELECT集的定义与计算，LL(1)分析表的构造、LL(1)分析法的基本流程

7、理解自底向上语法分析面临的问题、解决思路及主要技术路线，理解算符优先分析基本思想，掌握算符文法(OG)的定义；算符优先关系的定义；算符优先文法的定义；算符优先关系表的构造，构造集合FIRSTVT、LASTVT 的算法，如何计算算符优先关系；算符优先分析算法，素短语、最左素短语的定义，最左素短语的判断；优先函数；算符优先分析的优缺点。

8、理解LR分析法要解决的问题，了解可归前缀与活前缀。

LR(0)分析法：构造LR(0)项目集规范族的方法、LR(0)分析表的构造及LR(0)分析算法。

SLR(1)分析法：LR(0)分析法的冲突及解决方法、SLR(1)分析表的构造及SLR(1)方法的局限性。

LR(1)分析方法：理解LR(1)方法的引入背景，掌握LR(1)项目集规范族的构造、LR(1)分析表的构造及LR(1)分析算法。

LALR(1)分析：理解LR(1)分析法的缺点及解决；掌握LALR(1)项目集规范族的构造、及合并同心集的方法，理解LR(0)、SLR(1)、LR(1)、LR(k)和LALR(1)的关系。

9、了解语法制导翻译的定义，理解语法制导翻译的思想，掌握常见中间代码的形式：逆波兰式、三元式、四元式。

二、参考书目

《编译原理》(第3版)，王生原，董渊，张素琴，吕映芝，蒋维杜编著，清华大学出版社，2015，普通高等教育十一五国家级规划教材