期末复习填空题

第1页共5页填空题第一章1．解释程序和编译程序的区别在于（是否生成目标代码）。2．编译过程通常可分为5个阶段，分别是词法分析、语法分析、语义分析与中间代码产生、代码优化和目标代码生成。3．编译程序工作过程中，第一阶段输入是（源程序），最后阶段的输出为（目标代码）程序。4．源程序中的错误通常分为（语法错误）和（语义错误）两大类。5．（编译程序）是将源程序翻译成目标程序的程序。6．高级程序设计语言的翻译主要有两种方式：编译和解释，二者的根本区别在于是否生成目标代码。7.编译过程的各阶段都需要进行（表格）管理和（出错）处理，所以在典型编译程序框图中，各阶段对应的程序都和上述管理或处理操作程序相联系。8.若将A语言的源程序翻译成B语言的程序，翻译的实现语言为Y语言，则称A语言是翻译的源语言,B语言是目标语言，Y语言是宿主语言9.编译程序从源语言类型或实现机制不同角度一般可分为汇编程序、编译程序、解释程序10.构造一个编译程序的三要素是源语言、目标语言与目标机和编译方法与工具第二章1、产生式是用于定义_语法范畴____的一种书写规则。2．一个上下文无关文法G包括四个部分：（终结符号）、（非终结符号）、（开始符号）和一组（产生式）。3．若n21，则称这个序列是从1到n的一个（推导）。4．对于正规文法G和有限自动机M，若L(G)=L(M)，则称G和M是（等价）的。5．若两个正规式所表示的正规集相等，则认为二者是（等价）的。6.假设G[S]是一个文法,如有Sx,则称x是该文法G的（句型）；文法G产生的（句子）的全体称为该文法所描述的语言。7.用四元组G=（VN，VT，P，S）表示文法，则其元素VN表示（非终结符）集；元素VT表示（终结符）集；元素P表示规则集；元素S表示开始符号，它必须是一个（非终结）符号.8.规范推导是指最右推导，其逆过程即最左规约，称为规范归约。9．所谓最右推导是指任何一步都是对最右非终结符进行替换。10．设G是一个给定的文法，S是文法的开始符号，如果S-x(其中x∈VT*),则称x是文法的一个_句子____。11.语言的核心皆由语法和语义两部分构成，其中语法是语言的形式，语义是语言的内容。语言的实质是以语法为媒介来说明语义。12.设有字母表Σ={xy,a,b},字母表Σ上的符号串=xyabbaxyaa，则|ω|=8。13.设有字母表Σ={0,1}上的符号串集合为A={01，0，101}，则A2={0101,010,01101,001,00,0101,10101,1010,101101}14.目前最常用的文法表示方法为BNF表示法。15．文法G所产生的句子的全体是文法G所定义的（语言）。16．若一个文法存在某个句子对应的两棵不同的语法树，则称这个文法是（二义文法）。17．设文法G的开始符号为S，如果*S则称是L(G)的一个（句型）。第2页共5页18.设有字母表Σ={a,bb,c},字母表Σ上的符号串ω=abbc、，则|ω3|=919.一个确定有穷自动机可以通过消除无关状态和合并等价状态而转换成一个最小的与之等价的有穷自动机。20.Chomsky把文法分为四种形式，它们分别是0型文法、1型文法、2型文法和3型文法（正则文法）第三章1、扫描器的任务是从___源程序_____中识别出一个个__单词符号_____。2．扫描器是_词法分析器____，它接受输入的_源程序____，对源程序进行_词法分析____并识别出一个个单词符号，其输出结果是单词符号，供语法分析器使用。3．词法分析基于__正则___文法进行，即识别的单词是该类文法的句子。4.单词语言中具有独立意义的最小语法单位。5.属性字式扫描器对源程序中各单词处理后的输出形式，其中，单词属性表示单词的类别6.词法分析的单词可以分为常量、运算符、界限符、关键字和标识符7.系统的关键字和系统定义的运算符、分隔符都各自单独定义为一个词类，那么词类定义中除了常量和标识符以外，别的词类就一般不需附加信息。第四章1、语法分析最常用的两类方法是_自上而下_______和__自下而上______分析法。2.自顶向下语法分析方法会遇到的主要问题有左递归和回溯。3.LL（1）分析法中，第一个L的含义是__指输入字符串从左向右扫描___________，第二个L的含义是___最左推导________________，“1”的含义是__最多只向左看一个输入字符__________________。4.将非LL(1)文法转换为等价的LL(1)文法所采用的两种方法是（提取左公共因子）和（消除左递归）。但这两种方法并不能保证所有的非LL(1)文法都能转换为等价的LL(1)文法。5．进行确定的自上而下语法分析要求语言的文法是无左递归和无公共左因子的。6．递归下降法不允许任一非终极符是直接_左____递归的。7．自顶向下的语法分析方法的基本思想是：从文法的_开始符号_____开始，根据给定的输入串并按照文法的产生式一步一步的向下进行__直接推导____，试图推导出文法的_句子_____，使之与给定的输入串__匹配____。8．语法分析基于_上下文无关____文法进行，即识别的是该类文法的句子。语法分析的有效工具是_语法树____。9.设有文法G(S)：S→Pab|bPP→b|ε根据文法G(S)，填写如下LL(1)分析表的内容。ab$PP→εP→bP→ε10.设有文法G[S]为：S→AB|BcA→ε|bB→ε|aDC→AD|b第3页共5页D→aS|c则FOLLOW(A)={a，$，c}，FIRST(S)={b，a，ε，c}；。第五章1．LR分析法是一种自下而上的语法分析方法。2、LR（0）分析法的名字中，“L”的含义是_指输入字符串从左向右扫描_________，“R”的含义是__最右推导的逆过程——最左规约________,“0”的含义是__最多向前查看0个字符_____________。3．自底向上的语法分析方法的基本思想是：从输入串入手，利用文法的产生式一步一步地向上进行__直接归约___，力求归约到文法的_开始符号____。4．规范归约中的可归约串是指（句柄）。5．自下而上分析法采用_移进____、归约、错误处理、_接受____等四种操作。6.已知文法G[S]：S→*A，A→*∣0A1。则FIRSTVT(A)={0，*}，LASTVT(A)={1，*}7.LR(K)方法可以分为LR(0)、SLR(1)、LR(1)和LALR(1)四种。8.自底向上语法分析方法的基本思想是：由输入的符号串出发，利用文法的规则一步步进行规约，试图归约到文法的开始符号。9.LR分析器有三个部份组成，它们总控程序、LR分析表和分析栈。10.LR分析表包括Action表和goto表两部分第六章1、从功能上说，程序语言的语句大体可分为_执行性______语句和_说明性_____语句两大类。2、所谓语法制导翻译方法是__为每个产生式配上一个翻译子程序，并在语法分析的同时执行这些子程序_。3．把语法范畴翻译成中间代码所依据的是（语义规则）。4.编译过程中，每当扫描识别出一个名字后，编译程序就查阅符号表，看该名字是否在其中，如果该名字是一个新名字就将它填进符号表里。5．过程调用时，参数的传递方法通常有_传值_________、____传址______和传名。6.现代编译系统多采用语法制导翻译方法，即在语法分析过程中根据各个规则所相联的语义动作或所对应的语义子程序进行翻译的办法。该方法使用属性文法为工具来说明程序设计语言的语义。7.过程(函数)是结构化程序设计的主要手段。调用与被调用过程两者之间的信息主要通过全局变量或参数来传递。参数分为形参和实参，常用的参数传递方式有传地址、传值、传名等。8．（YACC）是一种语法分析程序的自动构造工具，用它可以直接构造各种语言的语法分析器；而（LEX）是一种词法分析程序的自动构造工具，用它可以直接构造各种语言的词法分析器。9.在语法分析过程中，随着分析的步步进展，根据每个规则所对应的语义子程序或语义动作进行翻译的办法，称为（语法制导）翻译方法，它被现代很多编译程序所采用。10、编译过程中，常见的中间语言形式有三元式、四元式、间接三元式和逆波兰式等11．语法分析是依据语言的_语法____规则进行的，中间代码产生是依据语言的_语义____规进行的。12．逆波兰式ab+c+d*e-所表达的表达式为_（a+b+c)*d-e____。13．后缀式abc-/所代表的表达式是_a/(b-c)____。14.从功能上说，程序语言的语句大体可分为执行性语句和说明性语句两大类15.可用属性文法来说明源语言语义。属性文法由一个文法和一系列附加在文法上的语义规则构成。16.引入中间语言的目的是便于目标代码的生成和代码优化第4页共5页17.符号表表的内容包括两部份：标识符的名字和信息18.在目标代码生成阶段，符号表是地址分配___的依据。19.在语义分析阶段的语义检查包括静态语义检查和静态语义检查20.静态语义检查实在编译时进行的，动态语义检查是在运行时进行的21.文法符号的属性有两种，一种称为继承属性__，另一种称为__综合属性____第七章1、常用的两种动态存贮分配办法是_栈式____动态分配和_堆式____动态分配。2.编译程序中常用的存储分配策略包括静态存储分配、栈式动态存储分配和堆式动态存储分配策略。3.编译时能确定其所需占用空间的数据存放在静态数据区；对在程序运行时才能确定所需占用空间大小的可变数据及管理过程的控制信息，其空间分配一般采用堆式或栈式动态存储分配方式。4.存储分配的基本单元是过程的活动记录5.数据空间的分配，实质上是将源程序中的名字与相应的存储位置关联起来，这种关联具有两种属性，即环境和状态，环境表示了从名字到存储位置的映射函数，状态表示了存储位置到值的映射第八章1.在循环中可采用代码外提、强度削弱和删除归纳变量三种优化措施。2.基本块的定义：一个基本块是指程序中一个顺序执行的语句序列，其中只有一个入口和一个出口。入口是程序第一个语句或转移语句的目标语句，或转移语句的后继第一个语句。出口是程序最后一个语句或转移语句。3.在基本块范围内的优化称为局部优化4.通常局部优化是指基本块内的优化，所谓基本块是指程序中一顺序执行的语句序列，其中只有一个（入口）语句和一个（出口）语句。5.所谓优化实质上是对代码进行等价变换，使得变换后的代码运行结果与变换前的代码运行结果相同，但运行速度加大或占用的（空间）减少。常用的优化技术有删除多余运算、（代码外提）、强度削弱、变换循环控制条件、合并已知变量与复写传播及删除无用赋值。6．根据优化对象所涉及的程序范围，代码优化分为局部优化、全局优化和循环优化等。7．局部优化是在_基本块____范围内进行的一种优化。8.局部优化采用的工具是DAG9.有代码为a=5;a=7;可以采用的优化方法是无用复制的删除10.所谓优化是指缩短运行时间和减少存储空间11.全局优化是指：在整个程序范围内的优化第九章1．目标代码可以是（汇编）指令代码或（可重定位）指令代码或绝对机器指令代码。2.代码生成要考虑的主要问题：充分利用寄存器的问题、选择计算机指令系统的问题、选择计算次序的问题。3.在目标代码生成阶段，符号表是地址分配___的依据。第5页共5页4.与机器有关的优化包括控制流优化、无用代码优化、寄存器优化和特殊指令优化。