南信大编译原理考题

《南信大编译原理考题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、注：加粗表示可能考简答题简答题(每小题5分，共20分)论述题(每小题10分，共20分)计算(每小题12分，共60分)1、编译程序的构成：源程序à词法分析à语法分析à语义分析和优化à目标代码生成第二章文法与语言1、一些概念性的东西（1）推导：句型à句子，自顶向下。（2）归约：句子à句型，自底向上。（2）句型：一个文法经过N（N>=1）步推导后得到的结果（含有非终结符号）（3）句子：一个文法经过N（N>=1）步推导后得到的结果（仅含有终结符号）（4）句柄：一个句型的最左简单短语。（树的最下面）（5）VN：文

2、法的非终结符号集合（6）VT：文法的终结符号集合（7）P：文法的规则的集合（8）S：文法的识别符号或开始符号（9）短语：由树的各个树叶节点组成的符号组，有相对于XX的区别。（10）简单短语：也叫直接短语，有非终结符一步退出的短语。2、Chomsky文法分类0型文法：短语结构文法à图灵机（TM，TuringMachine）1型文法（CSG）：上下文有关文法à线性界限自动机（LBA，Linearboundedautomata）2型文法（CFG）：上下文无关文法à下推自动机（PDA，PushDownautom

3、ata）3型文法（RG）：正则文法à有穷状态自动机（FA，Finiteautomata）文法的判断：3型文法：①左边必须只有一个字符，且必须是非终结符；②其右边最多只能有两个字符，且当有两个字符时必须有一个为终结符而另一个为非终结符。当右边只有一个字符时，此字符必须为终结符。③对于3型文法中的所有产生式，其右边有两个字符的产生式，这些产生式右边两个字符中终结符和非终结符的相对位置一定要固定，也就是说如果一个产生式右边的两个字符的排列是：终结符＋非终结符，那么所有产生式右边只要有两个字符的，都必须前面是终

4、结符而后面是非终结符。2型文法：①左边必须有且仅有一个非终结符。②2型文法所有产生式的右边可以含有若干个终结符和非终结符（只要是有限的就行，没有个数限制）。1型文法：①1型文法所有产生式左边可以含有一个、两个或两个以上的字符，但其中必须至少有一个非终结符。②与2型文法第二点相同。3、文法压缩，消除左递归4、已知文法，证明某符号串是该文法的句子5、文法压缩：P506、消除文法左递归：P537、文法四要素：VN（非终结符），VT（终结符），P（重写规则），Z（识别符号）第三章词法分析1、词法分析的任务（1）

5、读入源程序，（2）识别开单词（符号）并转换为内部表示,（3）做力所能及的工作（删除无效字符、预处理）。2、正则表达式。3、对简单的正则表达式，能画出状态转换图（自动机）4、NFA确定化为DFA（难），二者的异同。5、正则表达式引进的必要性①易理解正被定义的是什么符号集合。②更容易构造高效识别程序③有利于自动地构造识别程序④可用于其他各种信息流的处理6、文法压缩的基本思想①若一个符号不能出现在文法的任何句型中，则该符号是无用的②若一个非终结符号不能推导出终结符号串，该非终结符号是无用的第四章语法分析——自

6、顶向下分析技术1、递归下降分析技术是无回溯的自顶向下分析技术。2、递归下降分析器是一个不带回溯的自顶向下分析程序，该程序是由一组递归函数或过程组成的。其函数名应该是终结符，函数体是根据重写规则右部符号串的结构编写。3、求First，Follow集合。第一步，压缩文法，消除左递归，消除回溯。第二步，求First集合第三步，求Follow集合4、递归下降分析程序构造的基本思想：①每个函数名应该是非终结符号②当遇到终结符时，读入下一个符号③当遇到非终结符号时，调用该终结符的相应函数④当遇到空时，返回第五章语法

7、分析——自底向上分析技术1、移进-归约技术2、算符优先分析基本思想，优先函数的构造3、求文法的LR(0)项集规范族，绘制对应自动机4、题型可见以前布置的练习题5、算符文法：没有连续2个非终结符同时出现的情况，即两个非终结符中间必然有一个或几个终结符（算符）。6、质短语：句型中至少包含一个终结符号，且除它自身外不再包含其他质短语的短语。7、求算符优先矩阵（P151-153）：①等于号（=）：形如Z：：=aXb，则a=b②小于号（<）：第一步，求各个非终结符的FirstTeam集合（非终结符推导出的第一个终

8、结符，可能为空）；第二步，若有X：：=Yxxx的情况，则将Y的FirstTeam放入X的FirstTeam里；第三步，根据文法，若存在X：：=A+B，则+小于B的FirstTeam的每一个元素。③大于号（>）：第一步，求各个非终结符的LastTeam集合（非终结符推导出的最后一个终结符，可能为空）；；第二步，若有X：：=xxxY的情况，则将Y的LastTeam放入X的LastTeam里；第三步：根据文法，若存在X：：=A+B，则A的Last