计算机编译原理小抄

《计算机编译原理小抄》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、编译原理名词解释1.局部优化：局限于基本块范围的优化称。2.二义性文法：如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义性文法。3.DISPLAY表：过程的嵌套层次显示表，记录该过程的各外层过程的最新活动记录的起始地址。由于过程嵌套允许内层过程引用外层过程定义的数据，因此，当一个过程运行时必须跟踪它的所有外层过程的最新活动记录起始地址，display表就是用于登记每个外层过程的最新活动记录起始地址。5.最左推导：任何一步α=>β都是对α中的最右非终结符替换。6.语法：一组规则，用它可形成和产生一组合式的程序。7.文法：描述语

2、言的语法结构的形式规则。8.基本块：指程序中一顺序执行的语句序列，其中只有一个入口和一个出口，入口就是其中的第一个语句，出口就是其中的最后一个语句。9.语法制导翻译：在语法分析过程中，根据每个产生式所对应的语义子程序进行翻译的办法叫做语法制导翻译。10.短语：令G是一个文法，S划文法的开始符号，假定αβδ是文法G的一个句型，如果有SαAδ且Aβ，则称β是句型αβδ相对非终结符A的短语。11.待用信息：如果在一个基本块中，四元式i对A定值，四元式j要引用A值，而从i到j之间没有A的其它定值，则称j是四元式i的变量A的待用信息。12.规范句型：

3、由规范推导所得到的句型。13.扫描器：执行词法分析的程序。14.超前搜索：在词法分析过程中，有时为了确定词性，需超前扫描若干个字符。15.句柄：一个句型的最左直接短语。16.语法制导翻译：在语法分析过程中，根据每个产生式所对应的语义程序进行翻译的方法叫做语法制导翻译。17.规范句型：由规范推导所得到的句型。18.素短语：素短语是指这样一个短语，至少含有一个终结符，并且，除它自身外不再含任何更小的素短语。19.语法：是组规则，用它可形成和产生一个合式的程序。20.语义：定义程序的意义的一组规则。21.优化：对程序进行各种等价变换，使得从变换后

4、的程序出发，能产生更有效的目标代码。三种级别：局部优化、循环优化、全局优化21．词法分析词法分析的主要任务是从左向右扫描每行源程序的符号，按照词法规则从构成源程序的字符串中识别出一个个具有独立意义的最小语法单位，并转换成统一的内部表示(token)，送给语法分析程序。22．LL(1)文法若文法的任何两个产生式A®a

5、b都满足下面两个条件：（1）FIRST(a)ÇFIRST(b)=f；（2）若bÞ*e，那么FIRST(a)ÇFOLLOW(A)=f。我们把满足这两个条件的文法叫做LL(1)文法，其中的第一个L代表从左向右扫描输入，第二个L表示产

6、生最左推导，1代表在决定分析器的每步动作时向前看一个输入符号。除了没有公共左因子外，LL(1)文法还有一些明显的性质，它不是二义的，也不含左递归。23．语法树句子的树结构表示法称为语法树(语法分析树或语法推导树)。给定文法G=(VN，VT，P，S)，对于G的任何句型都能构造与之关联的语法树。这棵树具有下列特征：(1)根节点的标记是开始符号S。(2)每个节点的标记都是V中的一个符号。(3)若一棵子树的根节点为A，且其所有直接子孙的标记从左向右的排列次序为A1A2…AR，那么A®A1A2…AR一定是P中的一条产生式。(4)若一标记为A的节点至少

7、有一个除它以外的子孙，则AVN。(5)若树的所有叶节点上的标记从左到右排列为字符串w，则w是文法G的句型；若w中仅含终结符号，则w为文法G所产生的句子。24．LR(0)分析器所谓LR(0)分析，是指从左至右扫描和自底向上的语法分析，且在分析的每一步，只须根据分析栈当前已移进和归约出的全部文法符号，并至多再向前查看0个输入符号，就能确定相对于某一产生式左部符号的句柄是否已在分析栈的顶部形成，从而也就可以确定当前所应采取的分析动作(是移进还是按某一产生式进行归约等)。25．语言和文法文法就是语言结构的定义和描述，是有穷非空的产生式集合。文法G定

8、义为四元组的形式：G=(VN，VT，P，S)其中：VN是非空有穷集合，称为非终结符号集合；VT是非空有穷集合，称为终结符号集合；P是产生式的集合(非空)；S是开始符号(或识别符号)。这里，VN∩VT=Æ，SVN。V=VN∪VT，称为文法G的字母表，它是出现文法产生式中的一切符号的集合。文法G所描述的语言用L(G)表示，它由文法G所产生的全部句子组成，即L(G)={x

9、SÞ*x，其中S为文法开始符号，且}简单的说，文法描述的语言是该文法一切句子的集合。26．词法分析词法分析的主要任务是从左向右扫描每行源程序的符号，按照词法规则从构成源程序的字

10、符串中识别出一个个具有独立意义的最小语法单位，并转换成统一的内部表示(token)，送给语法分析程序。27．LL(1)文法若文法的任何两个产生式A®a

11、b都满足下面两个条件：（1