编译原理考试核心.

1、三、填空题(每空1分，共10分)1计算机执行用高级语言编写的程序主要有两种途径：_解释_和_编译_。 2扫描器是_词法分析器_，它接受输入的_源程序_，对源程序进行_词法分析_并识别出一个个单词符号，其输出结果是单词符号，供语法分析器使用。3自上而下分析法采用_移进_、归约、错误处理、_接受_等四种操作。4一个LR分析器包括两部分：一个总控程序和_一张分析表_。5后缀式abc-/所代表的表达式是_a/(b-c)_。 6局部优化是在_基本块_范围内进行的一种优化。二、填空题：2.编译过程可分为 （ 词法分析） ，（语法分析），（语义分析与中间代码生成 ），（优化）和（目标代码生成 ）五个阶段。3

2、.如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是（ 二义性的 ）。 4.从功能上说，程序语言的语句大体可分为（ 执行性 ）语句和（说明性 ）语句两大类。5.语法分析器的输入是（ 单词符号 ），其输出是（ 语法单位 ）。6.扫描器的任务是从（ 源程序中 ）中识别出一个个（ 单词符号 ）。7.符号表中的信息栏中登记了每个名字的有关的性质，如(类型、种属、所占单元大小、地址）等等。8.一个过程相应的DISPLAY表的内容为(现行活动记录地址和所有外层最新活动记录的地址)10.常用的两种动态存贮分配办法是（栈式）动态分配和（堆式）动态分配。11.一个名字的属性包括( 类型)和(作用域 )

3、。12.常用的参数传递方式有(传地址），（传值），（传名）13.根据优化所涉及的程序范围，可将优化分成为(局部优化），（循环优化），（全局优化）三个级别。14.语法分析的方法大致可分为两类，一类是（ 自上而下 ）分析法，另一类是（ 自下而上 ）分析法。15.预测分析程序是使用一张（ 分析表 ）和一个（ 符号栈 ）进行联合控制的。17.一张转换图只包含有限个状态,其中有一个被认为是（初）态;而且实际上至少要有一个（终 ）态。19.语法分析是依据语言的（语法 ）规则进行。中间代码产生是依据语言的（语义）规则进行的。21.一个文法G，若它的预测分析表M不含多重定义，则该文法是（LL(1) 文法）文法

4、。22.对于数据空间的存贮分配， FORTRAN采用( 静态策略， PASCAL采用( 动态)策略。24.最右推导亦称为（规范推导），由此得到的句型称为（规范）句型。26.对于文法G，仅含终结符号的句型称为 ( 句子 )。27.所谓自上而下分析法是指(从开始符号出发，向下推导，推出句子）29.局限于基本块范围的优化称（ 局部优化 ）。31.2型文法又称为（上下文无关）文法；3型文法又称为（正则 ）文法。32.每条指令的执行代价定义为(指令访问主存次数加1）33.算符优先分析法每次都是对(最左素短语）进行归约。二、填空题（本大题共5小题，每小题2分，共10分）1编译程序首先要识别出源程序中每个(

5、单词)，然后再分析每个(句子)并翻译其意义。 2编译器常用的语法分析方法有(自底向上)和(自顶向下)两种。3通常把编译过程分为分析前端与综合后端两大阶段。词法、语法和语义分析是对源程序的(分析)，中间代码生成、代码优化与目标代码的生成则是对源程序的(综合)。4程序设计语言的发展带来了日渐多变的运行时存储管理方案，主要分为两大类，即(静态存储分配)方案和(动态存储分配)方案。5对编译程序而言，输入数据是(源程序)，输出结果是(目标程序)。二 填空题3对于文法G1和G2，若有L(G1)=L(G2) （或 G1和G2的语言相同），则称文法G1和G2是等价的。4对于文法GE：ET|E+T TF|T*F

6、 FPF|P P(E)|i，句型T+T*F+i的句柄是T ，最左素短语是 T*F。 5最右推导的逆过程称为规范归约 ，也称为 最左归约。6规范规约中的可规约串是句柄 ，算符优先分析中的可规约串是 最左素短语7（A B）（C ¬D E） 的逆波兰式是¬。8在属性文法中文法符号的两种属性分别称为继承属性 和综合属性（次序可换）。9符号表的每一项是由名字栏和 地址分配 两个栏目组成。在目标代码生成阶段，符号表是 地址分配 的依据。 10一个过程的DISPLAY表的内容是它的直接外层 的DISPLAY表的内容加上本过程的SP的地址二、填空题（每空1分，共15分）1、常见的程序设计语

7、言主要有（过程式语言）、（面向对象语言）、（应用式语言）、（ 基于规则的语言）4种类型。2、翻译过程中翻译的主要工作就是把高级语言翻译成（中间语言 ）。3、编译程序前端主要由与源语言有关而与目标语言无关的部分组成，这些部分包括词法分析、（语法分析）、语义分析和（中间代码生成）。4、编译程序后端主要由编译程序中与目标程序有关的部分组成，主要包括（代码优化）和（目标代码生成）。5、如果按语言结构的形式分类，可以把程序设计语言分为过程式语言、（面向对象语言）、应用式语言和（基于规则的语言）。6、编译程序首先要识别出源程序中每个单词，然后再分析每个句子并翻译其意义。7、编译器常用的语法分析方法有自底向

8、上和自顶向下两种。8、通常把编译过程分为分析前端与综合后端两大阶段，词法、语法和语义分析是对源程序的分析，中间代码生成、代码优化与目标代码的生成则是对源程序的综合。9、对编译程序而言，输入数据是源程序，输出结果是目标程序。10、从功能上说，程序语言的语句大体可分为执行性语句和说明性语句。11、所谓最右推导是指（任何一步都是对a中最右非终结符进行替换的）。12、一个上下文无关法所含四个组成部分是：一组终结符号、一组非终结符号、一个开始符号、一组产生式。13、产生式是用于定义语法范畴的一种书写规则。14、文法中的终结符和非终结符的交集是空集。词法分析器交给语法分析器的文法符号一定是 终结符 ，它一

9、定只出现在产生式的 右 部。15、最左推导是指每次都对句型中的最左非终结符进行扩展。16、语法树代表推导过程，分析树代表归约过程。17、计算机执行用高级语言编写的程序主要由两种途径解释和编译。18、后缀式abc-/所代表的表达式是a/（b-c）。19、编译过程可分为词法分析、语法分析、语义分析与中间代码生成、优化和目标代码生成五个阶段。20、如果一个文法存在某个句子对应两个不同的语法树，则称这个文法是二义性的。21、语法分析是依据语言的语法规则进行，中间代码的产生是依据语言的语义规则进行的。22、对一个文法G，仅含终结符号的句型称为句子。23、2型文法又称为上下文无关文法，3型文法又称为正则文

10、法。二、填空题1解释程序和编译程序的区别在于（是否生成目标代码）。2编译过程通常可分为5个阶段，分别是（词法分析）、（语法分析）、语义分析与中间代码产生、代码优化和目标代码生成。3编译程序工作过程中，第一阶段输入是（源程序），最后阶段的输出为（目标代码）程序。4把语法范畴翻译成中间代码所依据的是（语义规则）。5目标代码可以是（汇编）指令代码或（可重定位）指令代码或绝对机器指令代码。6词法分析的任务是：输入源程序，对构成源程序的（字符串）进行扫描和分解。7源程序中的错误通常分为（语法错误）和（语义错误）两大类。8（编译程序）是将源程序翻译成目标程序的程序。9一个上下文无关文法G包括四个部分：（终

11、结符号）、（非终结符号）、（开始符号）和一组（产生式）。10若，则称这个序列是从到的一个（推导）。11设文法G的开始符号为S，如果则称是L(G)的一个（句型）。12文法G所产生的句子的全体是文法G所定义的（语言）。13若一个文法存在某个句子对应的两棵不同的语法树，则称这个文法是（二义文法）。14程序语言的单词符号一般可分为五种：（关键字）、（标识符）、常数、（运算符）和界符。15（确定有限自动机DFA）是非确定有限自动机NFA的一个特例。16对于正规文法G和有限自动机M，若L(G)=L(M)，则称G和M是（等价）的。17若两个正规式所表示的正规集相等，则认为二者是（等价）的。18按照语法分析树

12、的建立方法，语法分析可分为两类：（自上而下分析）和（自下而上分析）。18规范归约中的可归约串是指（句柄）。19算符优先分析中的可归约串是指（最左素短语）。20（自下而上）语法分析的关键问题是精确定义可归约串的概念。21.自顶向下语法分析方法的基本思想是：从 识别符号 出发，不断建立 直接推导 ，试图构造一个推导序列，最终由它推导出与输入符号串相同的 符号串。22.把汇编语言程序翻译成机器可执行的目标程序的工作是由 汇编器 完成的。23.确定的有穷自动机是一个（1）五 元组，通常表示为（2）DFA=（K，M，S，Z）。24.若源程序是用高级语言编写的，目标程序是 机器语言程序或汇编语言 ，则其翻

13、译程序称为编译程序。25.一个上下文无关文法G包括四个组成部分依次为：一组终结符号，一组非终结符号，一个 开始符号 ，以及一组 产生式 。三、名词解释题：1.局部优化-局限于基本块范围的优化称。2.二义性文法-如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义性文法。3.DISPLAY表-过程的嵌套层次显示表，记录该过程的各外层过程的最新活动记录的起始地址。5.最左推导-任何一步=>都是对中的最右非终结符替换。6.语法-一组规则，用它可形成和产生一组合式的程序。7.文法-描述语言的语法结构的形式规则。8.基本块-指程序中一顺序执行的语句序列，其中只有一个入口和一个出口，入口

14、就是其中的第一个语句，出口就是其中的最后一个语句。9.语法制导翻译-在语法分析过程中，根据每个产生式所对应的语义子程序进行翻译的办法叫做语法制导翻译。10.短语-令G是一个文法，S划文法的开始符号，假定是文法G的一个句型，如果有SA且A，则称是句型相对非终结符A的短语。11.待用信息-如果在一个基本块中，四元式i对A定值，四元式j要引用A值，而从i到j之间没有A的其它定值，则称j是四元式i的变量A的待用信息。12.规范句型-由规范推导所得到的句型。13.扫描器-执行词法分析的程序。14.超前搜索-在词法分析过程中，有时为了确定词性，需超前扫描若干个字符。15.句柄-一个句型的最左直接短语。16

15、.语法制导翻译-在语法分析过程中，根据每个产生式所对应的语义程序进行翻译的方法 叫做语法制导翻译。17.规范句型-由规范推导所得到的句型。18.素短语-素短语是指这样一个短语，至少含有一个终结符，并且，除它自身外不再含任何更小的素短语。19.语法-是组规则，用它可形成和产生一个合式的程序。 20.待用信息-如果在一个基本块中，四元式i对A定值，四元式j要引用A值，而从i到j之间没有A的其它定值，则称j是四元式i的变量A的待用信息。21.语义-定义程序的意义的一组规则。三、名词解释题(共5小题，每小题4分，共20分)1词法分析词法分析的主要任务是从左向右扫描每行源程序的符号，按照词法规则从构成源

16、程序的字符串中识别出一个个具有独立意义的最小语法单位，并转换成统一的内部表示(token)，送给语法分析程序。2LL(1)文法 若文法的任何两个产生式A ® a | b都满足下面两个条件：（1）FIRST(a ) Ç FIRST(b ) = f；（2）若b Þ* e ，那么FIRST(a ) Ç FOLLOW( A ) = f。 我们把满足这两个条件的文法叫做LL(1)文法，其中的第一个L代表从左向右扫描输入，第二个L表示产生最左推导，1代表在决定分析器的每步动作时向前看一个输入符号。除了没有公共左因子外，LL(1)文法还有一些明显的性质，它不是二义的，

17、也不含左递归。3语法树 句子的树结构表示法称为语法树(语法分析树或语法推导树)。给定文法G=(VN，VT，P，S)，对于G的任何句型都能构造与之关联的语法树。这棵树具有下列特征：(1)根节点的标记是开始符号S。(2)每个节点的标记都是V中的一个符号。(3)若一棵子树的根节点为A，且其所有直接子孙的标记从左向右的排列次序为A1A2AR，那么A®A1A2AR一定是P中的一条产生式。(4)若一标记为A的节点至少有一个除它以外的子孙，则AVN。(5)若树的所有叶节点上的标记从左到右排列为字符串w，则w是文法G的句型；若w中仅含终结符号，则w为文法G所产生的句子。4LR(0)分析器 所谓LR(

18、0)分析，是指从左至右扫描和自底向上的语法分析，且在分析的每一步，只须根据分析栈当前已移进和归约出的全部文法符号，并至多再向前查看0个输入符号，就能确定相对于某一产生式左部符号的句柄是否已在分析栈的顶部形成，从而也就可以确定当前所应采取的分析动作 (是移进还是按某一产生式进行归约等)。四、简答题（20分）1. 简要说明语义分析的基本功能。答：语义分析的基本功能包括: 确定类型、类型检查、语义处理和某些静态语义检 查。2. 考虑文法 GS: S (T) | a+S | a T T,S | S 消除文法的左递归及提取公共左因子。解：消除文法GS的左递归： S(T) | a+S | a TST T,

19、ST| 提取公共左因子： S(T) | aS S+S | TST T,ST| 3. 试为表达式 w+(a+b)*(c+d/(e-10)+8) 写出相应的逆波兰表示。解： w a b + c d e 10 - / + 8 + * +4. 按照三种基本控制结构文法将下面的语句翻译成四元式序列：while (A<C B<D) if (A 1) C=C+1;else while (A D)A=A+2;。解：该语句的四元式序列如下(其中E1、E2和E3分别对应ACBD、A1和AD，并且关系运算符优先级高)： 100 (j<,A,C,102) 101 (j,_,_,113) 102 (j

20、<,B,D,104) 103 (j,_,_,113) 104 (j=,A,1,106) 105 (j,_,_,108) 106 (+, C, 1, C) 107 (j,_,_,112) 108 (j,A,D,110) 109 (j,_,_,112) 110 (+, A, 2, A) 111 (j,_,_,108) 112 (j,_,_,100) 1135. 已知文法 GS 为 S aSb|Sb|b ，试证明文法 GS 为二义文法。证明： 由文法GS：SaSb|Sb|b，对句子aabbbb对应的两棵语法树为： 因此，文法GS为二义文法。 三、名词解释1、词法分析：主要任务是是从左到右扫描每

21、行源程序的符号，按照词法规则从构成源程序的字符串中识别出一个个具有独立意义的最小语法单位，并转换成统一的内部表示，送给语法分析程序。2、语法树：句子的树结构表示法称为语法树。给定文法G=(Vn,Vt,P,S)，对于G的任何句型都能构造与之关联的语法树(推导树)。语法树具有如下特征： (1) 根节点的的标记是开始符S。 (2)每个节点的标记都是V中的一个符号。(3) 若一颗树的根节点为A，且其具有直接子孙的标记从左向右的排列次序为A1A2AR,那么A>A1A2AR一定是P中的一条产生式。(4) 若一标记为A的节点至少有一个除它以外的子孙，则AVn.（5）若树的所有叶节点上的标记从左到右排列

22、为字符串W，则W是文法G的句型；若W中仅含终结符号，则W为文法G所产生的句子。3、推导：我们称A直接推出，即AÞ，仅当A 是一个产生式，且、(VNVT)*。如果1Þ2ÞÞn，则我们称这个序列是从1至2的一个推导。若存在一个从1n的推导，则称1可推导出n。推导是归约的逆过程。4、语法：表示程序的结构或形式，亦即表示构成语言的各个记号之间的组合规律，但不涉及这些记号的特定含义，也不涉及使用者。语义：表示程序的含义，亦即表示按照各种方法所表示的各个记号的特定含义，但不涉及使用者。5、上下文无关法：一个上下文无关文法G是一个四元式（VT,VN,S, P），其中：

23、VT是一个非空有限集，它的每个元素称为终结符号；VN是一个非空有限集，它的每个元素称为非终结符号，VTVN=；S是一个非终结符号，称为开始符号；P是一个产生式集合（有限），每个产生式的形式是P，其中，PVN，(VTVN)*。开始符号S至少必须在某个产生式的左部出现一次。 6、翻译程序：把某一种语言程序(称为源语言程序)等价地转换成另一种语言程序(称为目标语言程序)的程序。7、编译程序(compiler)：把某一种高级语言程序等价地转换成另一种低级语言程序(如汇编语言或机器语言程序)的程序。8、解释程序：把源语言写的源程序作为输入，但不产生目标程序，而是边解释边执行源程序本身。9、源语言：被翻译

24、的语言。 目标语言：翻译后的语言。 中间语言：在编译过程中，把源语言首先转换为一种中间表示形式，然后再把这种中间表示形式翻译为最终的目标语言，这种中间表示形式就叫做中间语言。 编译方式：把一个高级语言的文本文件“翻译”成机器语言的可执行文件。 解释方式：将源语言文件放在一个被称为解释器的程序里执行，把源语言代码中的语句翻译成一小段及其代码并执行之，工作方式是翻译一句执行一句10、抽象语法树 或者语法树（syntax tree），是源代码的抽象语法结构的树状表现形式，这里特指编程语言的源代码。树上的每个节点都表示源代码中的一种结构。之所以说语法是“抽象”的，是因为这里的语法并不会表示出真实语法中

25、出现的每个细节。 11、 二义性定义：“若对于一个文法的某一句子存在两棵不同的语法树，则该文法是二义性文法。”12、语法：就是描述语言现象这种词汇间的并列关系与嵌套关系的规则。三、简答1给出上下文无关文法的定义。一个上下文无关文法G是一个四元式(VT，VN，S，P)，其中： VT是一个非空有限集，它的每个元素称为终结符号； VN是一个非空有限集，它的每个元素称为非终结符号，VTVN=； S是一个非终结符号，称为开始符号； P是一个产生式集合(有限)，每个产生式的形式是P，其中，PVN，(VTVN)*。开始符号S至少必须在某个产生式的左部出现一次。2、“符号就是字符”，这种说法对吗，为什么？解答

26、：不对。符号是字母表中的元素，不能把符号理解成字符。如4个保留字的字母表BEGIN，END，FOR，WHILE此时，BEGIN，END，FOR，WHILE都是一个符号，因为它们是字母表中的元素。3、DFA与NFA有何区别？解答：DFA与NFA的区别表现在两方面。一是NFA可有若干个开始状态，而DFA仅一个。另一方面，DFA的映像M是从K×到K，而NFA的映像M是从K×到K的子集，即映像M将产生一个状态集合（可能为空集），而不是单个状态。4、LL（1）分析法的名字中，第一个“L”的含义是什么？第二个“L”的含义是什么？“1”的含义是什么？六、计算题：1、写一个文法，使其语言是

27、奇数集，且每个奇数不以0开头。解：文法G（N）:NABB AACD B13579 DB2468 C0D2、写一个文法，使其语言是偶数集，且每个偶数不以0开头。解：所求文法是G（S）：SABB AO AADC B2468 C13579B D0C四、综合题：2、设文法G为： SaAcB|BdS ABaB|aBc|a BaScA|cAB|b 对于输入串aacabccb，给出最左推导。 S=>aAcB=>aaBccB=>aacABccB=>aacaBccB=>aacabccB=>aacabccb3、设文法G为： SBA ABS|d BaA|bS|c 对于输入串adc

28、cd，给出最左推导。 S=>BA=>aAA=>adA=>adBS=>adcS=>adcBA=>adccA=>adccd4、证明：文法G： PPaP|PbP|cP|Pe|f 为二义文法。对于文法G定义的句子fbfbf，有两棵不同的语法树：PPPbPPbfffPPPbPPfffb所以该文法是二义文法。5、证明：文法G： PS+S|S*S|i|(S) 为二义文法。对于文法G定义的句子i+i*i，有两棵不同的语法树：SSS*SS+iiiSSS+SSiii*所以该文法是二义文法。四、简答题：3. 已知文法G(S)SbAaA(B | aBAa)写出句子b(a

29、a)b的规范归约过程。3.句子b(aa)b的规范归约过程：步骤符号栈输入串动作0#b(aa)b#预备1#b(aa)b#移进2#b(aa)b#移进3 #b(a a)b# 移进4#b(Aa)b#归约5 #b(Ma)b#移进8. 写一个文法G, 使其语言为 L(G)=albmclanbn| l>=0, m>=1, n>=2 8.所求文法是GS: SAB AaAc | D DbD | bBaBb | aabb10. 何谓优化？按所涉及的程序范围可分为哪几级优化？11. 目标代码有哪几种形式？生成目标代码时通常应考虑哪几个问题？10.优化：对程序进行各种等价变换，使得从变换后的程序出发

30、，能产生更有效的目标代码。三种级别：局部优化、循环优化、全局优化11.目标代码通常采用三种形式：机器语言，汇编语言，待装配机器语言模块。应着重考虑的问题： (1)如何使生成的目标代码较短；(2)如何充分利用寄存器，以减少访问内存次数；(3)如何充分利用指令系统的特点。七 已知文法G为:（0） S S（1） S aAd（2） S bAc（3） S aec（4） S bed（5） A e 试构造它的LR（1）项目集、可归前缀图和LR（1）分析表。【】【答案：】ecAdI0:S· S , # S· aAd , # S · bAc , # S ·aec , #S

31、 · bed , #I2： Sa · Ad , #Sa · ec , # A· e , d aI1：SS · , #SI3: Sb · Ac , # Sb · ed , # A· e , cbI6: SbA·c,# AI7：Sbe · d , #Ae · , cI11：Sbed · , #dI10：SbAc · , # I4：SaA· d , #I5：Sae· c , # Ae · , deI8：SaAd · , #I9：Sa

32、ec · , #c构造LR(1)分析表 如下： r4 11S10 6r2 10 r3 9 r1 8S11r5 7r5S9 5S8 4 6S7 3 4S5 2acc 1A#S3bedc1S gotoaS2 action 0状态九、(9分) 设已构造出文法G(S)：(1) S ® BB(2) B ® aB(3) B® b的LR分析表如下ACTIONGOTO状态ab#SB0s3s4121acc2s6s753s3s484r3r35r16s6s797r38r2r29r2假定输入串为abab，请给出LR分析过程(即按照步骤给出状态，符号，输入串的变化过程)。答：步骤状态符号输入串00#abab#103#abab#2034#abab#3038#aBab#402#Bab#5026#Bab#60267#Bab#70269#BaB#8025#BB#901#S#acc1. 设文法（）为：求（）项目集族；构造识别文法（）的；构造文法（）的SLR（）的分析表；分析句子的识别过程。