编译作业答案

一、填空题 :1-01. 编译程序的工作过程一般能够区分为词法剖析 , 语法剖析 , 语义剖析，之间代码生成 , 代码优化等几个基本阶段 , 同时还会伴有表格办理和犯错办理 .1-02. 若源程序是用高级语言编写的, 目标程序是机器语言程序或汇编程序, 则其翻译程序称为编译程序 .1-03. 编译方式与解说方式的根本差异在于能否生成目标代码 .1-04. 翻译程序是这样一种程序, 它能够将用甲语言书写的程序变换成与其等价的用乙语言书写的程序 .1-05. 对编译程序而言 , 输入数据是源程序 , 输出结果是目标程序 .1-06. 假如编译程序生成的目标程序是机器代码程序, 则源程序的履行分为两大阶段 : 编译阶段和运行阶段 . 假如编译程序生成的目标程序是汇编语言程序, 则源程序的履行分为三个阶段: 编译阶段 ,汇编阶段和运转阶段 .1-07. 若源程序是用高级语言编写的，目标程序是机器语言程序或汇编程序，则其翻译程序称为编译程序。

1-08. 一个典型的编译程序中，不单包含词法剖析、语法剖析、中间代码生成、代码优化、目标代码生成等五个部分，还应包含表格办理和犯错办理。

此中，词法剖析器用于辨别单词。

1-09. 编译方式与解说方式的根本差异为能否生成目标代码。

2-01. 所谓最右推导是指：任何一步αβ 都是对α 中最右非终结符进行替代的。

2-02. 一个上下文没关文法所含四个构成部分是一组终结符号、一组非终结符号、一个开始符号、一组产生式。

2-03. 产生式是用于定义语法成分的一种书写规则。

2-04. 设 G[S] 是给定文法，则由文法G所定义的语言 L(G) 可描绘为： L(G) ＝ {x │ S*。

Tx,x ∈ V }2-05. 设 G是一个给定的文法， S 是文法的开始符号，假如 S*），则称 x 是文法的一个句型。

x（此中 x∈ V2-06. 设 G是一个给定的文法，S 是文法的开始符号，假如S*x( 此中 x∈ V T ), 则称 x 是文法的一个句子。

编译技术作业4单项选择题第1题程序基本块是指（）。

A、一个子程序B、一个仅有一个入口和一个出口的语句C、一个没有嵌套的程序段D、一组顺序执行的程序段，仅有一个入口和一个出口答案：D第2题规范规约中的可归约串都是（）。

A、句柄B、素短语C、最左素短语D、最左终结符答案：A第3题给定文法G如下：E→E+T T→T*F|F F→P↑F|P D→(E)|i，句型P*P+i的最左直接短语为（）。

A、P*PB、PC、P+iD、P*P+i答案：B第4题编译程序在优化时（）用到原程序中的注释。

A、可能要B、不可能答案：B第5题LR（K）文法（）。

A、都是无二义性的B、都是二义性的C、一部分是二义性的答案：A第6题与PASCAL语言存储分配方式相似的语言是（）。

A、C语言B、BASIC语言C、FORTRAN-77答案：A第7题表达式(A∨B)∧(C∨￢D∧E)的逆波兰表示为（）。

A、AB∨CD￢∨E∧∧B、AB∨CDE∧￢∨∧C、AB∨CD￢E∧∨∧D、AB∨CD∨￢E∧∧答案：A第8题对任何一个编译程序来说，产生中间代码是（）。

A、不可缺少的B、不一定必要的答案：B第9题数组的内情向量中肯定不含有数组的（）的信息。

A、维数B、类型C、维上下界D、各维的界差答案：A第10题合并表达式中常量运算的目的是（）。

A、合并常量，使表达式中的常量尽可能少B、合并常量，使表达式尽可能简短C、将可在编译时刻计算的常量运算在编译时刻计算出来，然后用所计算出来的值替换表达式中出现的所有这种常量运算，使得生成的代码指令尽可能少答案：C多项选择题第11题代码优化的主要目标是（）。

A、提高目标程序的运行速度B、减少目标程序运行所需的空间C、协调A和BD、使生成的目标代码尽可能简短答案：A|B|C第12题在编译程序采用的优化方法中，（）是在循环语句范围内进行的。

A、删除多余运算B、删除归纳变量C、强度削弱D、代码外提答案：B|C|D判断题第13题目标代码生成时，不应考虑如何充分利用计算机的寄存器的问题。

、填空题:1-01.编译程序的工作过程一般可以划分为词法分析,语法分析,语义分析，中间代码生成,目标代码形成等几个基本阶段,同时还会伴有表格处理和出错处理 .其中，词法分析器用于识别单词。

语法分析器则可以发现源程序中的语法错误。

1-02.若源程序是用高级语言编写的,目标程序是机器语言程序或汇编程序 ,则其翻译程序称为编译程序.1-03.编译方式与解释方式的根本区别在于是否生成目标代码 .1-04.翻译程序是这样一种程序,它能够将用甲语言书写的程序转换成与其等价的用乙语言书写的程序 .1-05.对编译程序而言,输入数据是源程序 ,输出结果是目标程序 .1-06.如果编译程序生成的目标程序是机器代码程序,则源程序的执行分为两大阶段: 编译阶段和运行阶段 .如果编译程序生成的目标程序是汇编语言程序,则源程序的执行分为三个阶段: 编译阶段 ,汇编阶段和运行阶段 .1-07.编译方式与解释方式的根本区别为是否生成目标代码。

2-01.所谓最右推导是指：任何一步α β都是对α中最右非终结符进行替换的。

2-02.一个上下文无关文法G[S]=（V N，V T，P，S）所含四个组成部分是指终结符号集、非终结符号集、产生式集和一个文法的开始符合。

2-03.产生式是用于定义语法成分的一种书写规则。

2-04.设G[S]是给定文法，则由文法G所定义的语言L(G)可描述为： L(G)＝{x│S x,x∈V T*} 。

2-05.设G是一个给定的文法，S是文法的开始符号，如果S x（其中x∈V*），则称x是文法的一个句型。

2-06.设G是一个给定的文法，S是文法的开始符号，如果S x(其中x∈V T*),则称x是文法的一个句子。

3-01.扫描器的任务是从源程序中识别出一个个单词符号。

4-01.语法分析最常用的两类方法是自顶而下和自底而上分析法。

4-02.语法分析的任务是识别给定的终结符号串是否为给定文法的句子。

4-03.递归下降法不允许任一非终极符是直接左递归的。

编译原理_平时作业1 对于下列语言分别写出它们的正规表达式。

(1) 英文字母组成的所有符号串，要求符号串中顺序包含五个元音。

答：令Letter表示除这五个元音外的其它字母。

((letter)*A(letter)*E(letter)*I(letter)*O(letter)*U(letter))*(2) 英文字母组成的所有符号串，要求符号串中的字母依照词典顺序排列。

答：A*B*....Z*(3) Σ={0,1}上的含偶数个1的所有串。

答： (0|10*1)*(4) Σ={0,1}上的含奇数个1的所有串。

答：(0|10*1)*1(5) 具有偶数个0和奇数个1的有0和1组成的符号串的全体。

答：设S是符合要求的串，|S|=2k+1 (k≥0）。

则S→S10|S21，|S1|=2k (k>0），|S2|=2k (k≥0）。

且S1是{0,1}上的串，含有奇数个0和奇数个1。

S2是{0,1}上的串，含有偶数个0和偶数个1。

考虑有一个自动机M1接受S1，那么自动机M1如下：和L(M1)等价的正规表达式，即S1为：((00|11)|(01|10)(00|11)*(01|10))*(01|10)(00|11)*类似的考虑有一个自动机M2接受S2，那么自动机M2如下：和L(M2)等价的正规表达式，即S2为：((00|11)|(01|10)(00|11)*(01|10))*因此，S为：((00|11)|(01|10)(00|11)*(01|10))*(01|10)(00|11)*0|((00|11)|(01|10)(00|11)*(01|10))*1(6) 不包含子串011的由0和1组成的符号串的全体。

答：1*|1*0(0|10)*(1|ε)(7) 由0和1组成的符号串,把它看成二进制数，能被3整除的符号串的全体。

答：假设w的自动机如下：对应的正规表达式：(1(01*0)1|0)*2 给出接受下列在字母表{0,1}上的语言的DFA。

《编译原理》习题解答：第一次作业：P14 2、何谓源程序、目标程序、翻译程序、汇编程序、编译程序和解释程序？它们之间可能有何种关系？答：被翻译的程序称为源程序；翻译出来的程序称为目标程序或目标代码；将汇编语言和高级语言编写的程序翻译成等价的机器语言，实现此功能的程序称为翻译程序；把汇编语言写的源程序翻译成机器语言的目标程序称为汇编程序；解释程序不是直接将高级语言的源程序翻译成目标程序后再执行，而是一个个语句读入源程序，即边解释边执行；编译程序是将高级语言写的源程序翻译成目标语言的程序。

关系：汇编程序、解释程序和编译程序都是翻译程序，具体见P4 图 1.3。

P14 3、编译程序是由哪些部分组成？试述各部分的功能？答：编译程序主要由8个部分组成：（1）词法分析程序；（2）语法分析程序；（3）语义分析程序；（4）中间代码生成；（5）代码优化程序；（6）目标代码生成程序；（7）错误检查和处理程序；（8）信息表管理程序。

具体功能见P7-9。

P14 4、语法分析和语义分析有什么不同？试举例说明。

答：语法分析是将单词流分析如何组成句子而句子又如何组成程序，看句子乃至程序是否符合语法规则，例如：对变量x：= y 符合语法规则就通过。

语义分析是对语句意义进行检查，如赋值语句中x与y类型要一致，否则语法分析正确，语义分析则错误。

补充：为什么要对单词进行内部编码？其原则是什么？对标识符是如何进行内部编码的？答：内部编码从“源字符串”中识别单词并确定单词的类型和值；原则：长度统一，即刻画了单词本身，也刻画了它所具有的属性，以供其它部分分析使用。

对于标识符编码，先判断出该单词是标识符，然后在类别编码中写入相关信息，以表示为标识符，再根据具体标识符的含义编码该单词的值。

P38 1、设T1＝{11，010}，T2＝{0，01，1001}，计算：T2T1，T1*，T2+。

T2T1＝{011，0010，0111，01010，100111，1001010}T1*＝{ε，11，010，1111，11010，01011，010010……}T2+＝{0，01，1001，00，001，01001，010，0101……}P38-39 8、设有文法G[S]：S∷＝aAbA∷＝BcA | BB∷＝idt |ε试问下列符号串（1）aidtcBcAb （2）aidtccb（4）abidt是否为该文法的句型或句子。

《编译原理》第一次作业参考答案一、下列正则表达式定义了什么语言（用尽可能简短的自然语言描述）？1.b*(ab*ab*)*所有含有偶数个a的由a和b组成的字符串.2.c*a(a|c)*b(a|b|c)* | c*b(b|c)*a(a|b|c)*答案一：所有至少含有1个a和1个b的由a，b和c组成的字符串.答案二：所有含有子序列ab或子序列ba的由a，b和c组成的字符串.说明：答案一要比答案二更好，因为用自然语言描述是为了便于和非专业的人员交流，而非专业人员很可能不知道什么是“子序列”，所以相比较而言，答案一要更“自然”.二、设字母表∑={a,b}，用正则表达式（只使用a，b， ，|，*，+，？）描述下列语言：1.不包含子串ab的所有字符串.b*a*2.不包含子串abb的所有字符串.b*(ab?)*3.不包含子序列abb的所有字符串.b*a*b?a*注意：关于子串（substring）和子序列（subsequence）的区别可以参考课本第119页方框中的内容.~\(≧▽≦)/~ ~\(≧▽≦)/~ ~\(≧▽≦)/~ ~\(≧▽≦)/~ ~\(≧▽≦)/~ ~\(≧▽≦)/~ ~\(≧▽≦)/~ ~\(≧▽≦)/~《编译原理》第二次作业参考答案一、考虑以下NFA：1.这一NFA接受什么语言（用自然语言描述）？所有只含有字母a和b，并且a出现偶数次或b出现偶数次的字符串.2.构造接受同一语言的DFA.答案一（直接构造通常得到这一答案）：答案二（由NFA构造DFA得到这一答案）：二、正则语言补运算3.画出一个DFA，该DFA恰好识别所有不含011子串的所有二进制串.1.画出一个DFA，该DFA恰好识别所有不含011子串的所有二进制串.规律：构造语言L的补语言L’的DFA，可以先构造出接受L的DFA，再把这一DFA的接受状态改为非接受状态，非接受状态改为接受状态，就可以得到识别L’的DFA.说明：在上述两题中的D状态，无论输入什么符号，都不可能再到达接受状态，这样的状态称为“死状态”.在画DFA时，有时为了简明起见，“死状态”及其相应的弧（上图中的绿色部分）也可不画出.2.再证明：对任一正则表达式R，一定存在另一正则表达式R'，使得L(R')是L(R)的补集.证明：根据正则表达式与DFA的等价性，一定存在识别语言L(R)的DFA. 设这一DFA为M，则将M的所有接受状态改为非接受状态，所有非接受状态改为接受状态，得到新的DFA M’. 易知M’识别语言L(R)的补集. 再由正则表达式与DFA的等价性知必存在正则表达式R’，使得L(R’)是L(R)的补集.三、设有一门小小语言仅含z、o、/（斜杠）3个符号，该语言中的一个注释由/o开始、以o/结束，并且注释禁止嵌套.1.请给出单个正则表达式，它仅与一个完整的注释匹配，除此之外不匹配任何其他串. 书写正则表达式时，要求仅使用最基本的正则表达式算子（ ，|，*，+，？）.参考答案一：/o(o*z|/)*o+/思路：基本思路是除了最后一个o/，在注释中不能出现o后面紧跟着/的情况；还有需要考虑的是最后一个o/之前也可以出现若干个o.参考答案二（梁晓聪、梁劲、梁伟斌等人提供）：/o/*(z/*|o)*o/2.给出识别上述正则表达式所定义语言的确定有限自动机（DFA）. 你可根据问题直接构造DFA，不必运用机械的算法从上一小题的正则表达式转换得到DFA.~\(≧▽≦)/~ ~\(≧▽≦)/~ ~\(≧▽≦)/~ ~\(≧▽≦)/~ ~\(≧▽≦)/~ ~\(≧▽≦)/~ ~\(≧▽≦)/~ ~\(≧▽≦)/~《编译原理》第三次作业参考答案一、考虑以下DFA的状态迁移表，其中0，1为输入符号，A~H代表状态：01A B AB A CC D BD D AE D FF G EG F GH G D其中A为初始状态，D为接受状态，请画出与此DFA等价的最小DFA，并在新的DFA状态中标明它对应的原DFA状态的子集.说明：有些同学没有画出状态H，因为无法从初始状态到达状态H. 从实用上讲，这是没有问题的. 不过，如果根据算法的步骤执行，最后是应该有状态H的.二、考虑所有含有3个状态（设为p，q，r）的DFA. 设只有r是接受状态. 至于哪一个状态是初始状态与本问题无关. 输入符号只有0和1. 这样的DFA总共有729种不同的状态迁移函数，因为对于每一状态和每一输入符号，可能迁移到3个状态中的一个，所以总共有3^6=729种可能. 在这729个DFA中，有多少个p和q是不可区分的（indistinguishable）？解释你的答案.解：考虑对于p和q，在输入符号为0时的情况，在这种情况下有5种可能使p和q无法区分：p和q在输入0时同时迁移到r（1种可能），或者p和q在输入0时，都迁移到p或q（4种可能）.类似地，在输入符号为1时，也有5种可能使p和q无法区分.如果再考虑r的迁移，r的任何迁移对问题没有影响. 于是r在输入0和输入1时各有3种可能的迁移，总共有3*3=9种迁移.因此，总共有5*5*9=225个DFA，其中p和q是不可区分的.三、证明：所有仅含有字符a，且长度为素数的字符串组成的集合不是正则语言.证明：用反证法.假设含有素数个a的字符串组成的集合是正则语言，则必存在一个DFA接受这一语言，设此DFA为D. 由于D 的状态数有限，而素数有无限多个，所以必存在两个不同的素数p和q（设p<q），使得从D的初始状态出发，经过p个a和q个a后到达同一状态s，且s为接受状态. 由于DFA每一步的迁移都是确定的，所以从状态s 出发，经过(q-p)个a，只能到达状态s.考虑仅含有字母a，长度为p+p(q-p)的字符串T. T从初始状态出发，经过p个a到达状态s，再经过(q-p)个a仍然到达s；同样，经过p(q-p)个a后仍然到达s. 因此，从初始状态出发，经过p+p(q-p)个a后必然到达状态s. 由于p+p(q-p)=p(q-p+1)是合数，而s为接受状态，因而得出矛盾. 原命题得证.~\(≧▽≦)/~ ~\(≧▽≦)/~ ~\(≧▽≦)/~ ~\(≧▽≦)/~ ~\(≧▽≦)/~ ~\(≧▽≦)/~ ~\(≧▽≦)/~ ~\(≧▽≦)/~《编译原理》第四次作业参考答案一、用上下文无关文法描述下列语言：1.定义在字母表∑={a, b}上，所有首字符和尾字符相同的非空字符串.S → aTa | bTb | a | bT → aT | bT | є说明：1. 用T来产生定义在字母表∑={a, b}上的任意字符串；2. 注意不要漏了单个a和单个b的情况.2.L={0i1j|i≤j≤2i且i≥0}.S → 0S1 | 0S11 | є3.定义在字母表∑={0, 1}上，所有含有相同个数的0和1的字符串（包括空串）.S → 0S1 | 1S0 | SS | є思路：分两种情况考虑.1)如果首尾字母不同，那么这一字符串去掉首尾字母仍应该属于我们要定义的语言，因此有S → 0S1 | 1S0；2)如果首尾字母相同，那么这一字符串必定可以分成两部分，每一部分都属于我们要定义的语言，因此有S → SS.二、考虑以下文法：S → aABeA → Abc|bB → d1.用最左推导（leftmost derivation）推导出句子abbcde.S ==> aABe ==> aAbcBe ==> abbcBe ==> abbcde2.用最右推导（rightmost derivation）推导出句子abbcde.S ==> aABe ==> aAde ==> aAbcde ==> abbcde3.画出句子abbcde对应的分析树（parse tree）.三、考虑以下文法：S → aSbS → aSS →1.这一文法产生什么语言（用自然语言描述）？所有n个a后紧接m个b，且n>=m的字符串.2.证明这一文法是二义的.对于输入串aab，有如下两棵不同的分析树3.写出一个新的文法，要求新文法无二义且和上述文法产生相同的语言.答案一：S → aSb | TT → aT | ε答案二：S → TS’T → aT | εS’ → aS’b | ε~\(≧▽≦)/~ ~\(≧▽≦)/~ ~\(≧▽≦)/~ ~\(≧▽≦)/~ ~\(≧▽≦)/~ ~\(≧▽≦)/~ ~\(≧▽≦)/~《编译原理》第五次作业参考答案一、考虑以下文法：S → aTUV | bVT → U | UUU →ε | bVV →ε | cV写出每个非终端符号的FIRST集和FOLLOW集.FIRST(S)={a, b} FIRST(T)={є, b} FIRST(U)={ є, b} FIRST(V)={є, c}FOLLOW(S)={$} FOLLOW(T)={ b, c, $} FOLLOW(U)={ b, c, $} FOLLOW(V)={b, c , $}二、考虑以下文法：S → (L) | aL → L, S | S1.消除文法的左递归.S → (L) | aL → SL’L’ → ,SL’ | ε2.构造文法的LL(1)分析表.FIRST(S) = {‘(‘, ‘a’} FIRST(L) = {‘(‘, ‘a’} FIRST(L’) = {‘,’, ε}FOLLOW(S) = {‘$’, ‘,’, ‘)’} FOLLOW(L) = {‘)’ } FOLLOW(L’) = {‘)’}3.三、考虑以下文法：S → aSbS | bSaS | ε这一文法是否是LL(1)文法？给出理由.这一文法不是LL(1)文法，因为S有产生式S →ε，但FIRST(S) = {a, b, ε}，FOLLOW(S) = {a, b}，因而FIRST(S)∩FOLLOW(S)≠∅. 根据LL(1)文法的定义知这一文法不是LL(1)文法.~\(≧▽≦)/~ ~\(≧▽≦)/~ ~\(≧▽≦)/~ ~\(≧▽≦)/~ ~\(≧▽≦)/~ ~\(≧▽≦)/~ ~\(≧▽≦)/~ ~\(≧▽≦)/~《编译原理》第六次作业参考答案一、考虑以下文法：(0) E’ → E(1) E → E+T(2) E → T(3) T → TF(4) T → F(5) F → F*(6) F → a(7) F → b1.写出每个非终端符号的FIRST集和FOLLOW集.FIRST(E’)= FIRST(E)= FIRST(T)= FIRST(F)={a, b}FOLLOW(E’)={$} FOLLOW(E)={+, $} FOLLOW(T)={+, $, a, b} FOLLOW(F)= {+, *, $, a, b}2.构造识别这一文法所有活前缀（viable prefixes）的LR(0)自动机（参照课本4.6.2节图4.31）.STATE ACTION GOTOa b+*$E T F0s4s5123 1s6accept2s4s5r2r27 3r4r4r4s8r44r6r6r6r6r65r7r7r7r7r76s4s593 7r3r3r3s8r38r5r5r5r5r59s4s5r1r17STACK SYMBOLS INPUT ACTION(1)0a+ab*$shift(2)04a+ab*$reduce by F→a(3)03F+ab*$reduce by T→F(4)02T+ab*$reduce by E→T(5)01E+ab*$shift(6)016E+ab*$shift~\(≧▽≦)/~ ~\(≧▽≦)/~ ~\(≧▽≦)/~ ~\(≧▽≦)/~ ~\(≧▽≦)/~ ~\(≧▽≦)/~ ~\(≧▽≦)/~ ~\(≧▽≦)/~《编译原理》第八次作业参考答案一、考虑以下语法制导定义（Syntax Directed Definition）：对于输入串gbbabbccd构造带注释的分析树（annotated parse tree）.最终答案：34二、以下文法定义了二进制浮点数常量的语法规则：S → L.L | LL → LB | BB → 0 | 1试给出一个S属性的语法制导定义，其作用是求出该二进制浮点数的十进制值，并存放在开始符号S相关联的一个综合属性value中。

第二章 文法和语言p48 4、6（6）、11、 12（2）（6）、18（2）4 证明文法G=（{E,O}，{(，)，+，*，v ，d}，P ，E ）是二义的,其中P 为 E → EOE | (E) | v | d O → + | * 证明：因为E=〉 EOE =〉EOEOE =〉EOEOv =〉EOE+v=〉EOv+v =〉E*v+v =〉v*v+v ， 句子v*v+v 有两棵不同的语法树所以文法G 是二义的。

问题：1）只有文字说明，比如v*v+v 有两棵语法树，但没有画出语法树或者最左（最右）推导过程2）给出的是不同句子（v*v+d v+v*d ）的语法树 6、已知文法G ：EEEE OO v*v+ vE EE E O O v+v* v〈表达式〉∷=〈项〉|〈表达式〉+〈项〉〈项〉∷=〈因子〉|〈项〉*〈因子〉〈因子〉∷=（〈表达式〉）| i试给出下述表达式的推导及语法树（6）i+i*i推导过程：〈表达式〉=〉〈表达式〉+〈项〉E=〉E+T =〉〈表达式〉+〈项〉*〈因子〉=〉E+ T*F=〉〈表达式〉+〈项〉* i =〉E+ T*i=〉〈表达式〉+ 〈因子〉* i =〉E+F*i=〉〈表达式〉+ i* i =〉E+i*i=〉〈项〉+ i* i =〉T +i*i=〉〈因子〉+ i* i =〉F +i*i=〉i +i*i =〉i +i*i 共8步推导语法树：〈表达式〉+〈因子〉〈项〉i 〈因子〉i〈项〉〈项〉〈因子〉i*11、一个上下文无关文法生成句子abbaa的推导树如下：（1）给出该句子相应的最左推导和最右推导（2）该文法的产生式集合P可能有哪些元素？（3）找出该句子的所有短语、简单短语、句柄。

（1）最左推导：S=〉ABS=〉aBS=〉aSBBS=〉aBBS=〉abBS=〉abbS =〉abbAa=〉abbaa最右推导：S =〉ABS=〉ABAa=〉ABaa=〉ASBBaa=〉ASBbaa=〉ASbbaa=〉Abbaa=〉abbaa（2）该文法的产生式集合P可能有下列元素：S→ABS | Aa|εA→a B→SBB|b（3）因为字符串中的各字符有相对的位置关系，为了能相互区别，给相同的字符标上不同的数字。

第3章文法和语言习题参考答案1. L(G)={abc}2. L(G[N])是无符号整数。

3.G3: E→D+E | D-E | DD→0|1|2|3|4|5|6|7|8|94. L(G[Z])={a n b n | n>0}5.(1) G5: N→DN | EE→0|2|4|6|8D→E|1|3|5|7|9(2) G5: N→AB|EB→DB|EA→1|2|3|4|5|6|7|8|9E→0|2|4|6|8D→A|06.(1) E⇒T E (5) E⇒ E+T E (6) E⇒ E+T E⇒F T ⇒⇒⇒i F ⇒ F+T T F ⇒ F+T T T * Fi ⇒ i+T F ( E ) ⇒ i+T F F i⇒ i+F i E + T ⇒ i+T*F i i⇒ i+(E) T F ⇒ i+F*F⇒ i+(E+T) F i ⇒ i+i*F⇒ i+(T+T) i ⇒ i+i*i⇒ i+(F+T)⇒ i+(i+T)⇒ i+(i+F)⇒ i+(i+i)7. E E i+i*i的两棵语法树不同，E O E E O E 故文法是二义的。

i + E O E E O E * ii * i i + i8. S S abc的两棵语法树不同，A c aB 故文法是二义的。

a b b c9. (1) S (2) 该文法生成的语言是后缀表达式，S S * 或称为逆波兰式。

S aa a10. （1）该文法生成的语言是“可并列或嵌套的配对的括号串”。

（2）文法是二义的，因为句子“()()”有两棵不同的语法树。

S SS ( S ) S S ( S ) SS ( S ) S εεεε S ( S ) Sεεεεεε11. 可构造E+T*F的语法树如右所示： E 短语：E+T*F T*F故为文法的句型。

+ T 其中，T*F是直接短语和句柄T * F13. （1）最左推导最右推导(2) 文法规则可有：(3) 短语直接短语句柄S⇒ABS S⇒ABS S→ABS | Aa |εabbaa⇒aBS ⇒ABAa A→a a a a⇒aSBBS ⇒ABaa B→SBB | b εε⇒aBBS ⇒ASBBaa b b⇒abBS ⇒ASBbaa b b⇒abbS ⇒ASbbaa bb⇒abbAa ⇒Abbaa a a⇒abbaa ⇒abbaa aa14. (1) G1: S→CD (2) G2: S→1S0|AC→aCb|ε A→0A1|εD→aDb|ε(3) G3: S→0S0|aSa|a15．{WaW}上下文无关，W对应编程语言中的各种括号；{a n b m c n d m}上下文有关。

编译技术作业1单项选择题第1题使用解释程序时，在程序未执行完的情况下，（）重新执行已执行过的部分。

A、也能B、不可能答案：A第2题编译程序中的语法分析器接受以（）为单位的输入，并产生有关信息供以后各阶段使用。

A、表达式B、产生式C、单词D、语句答案：C第3题文法G所描述的语言是（）的集合。

A、文法G的字汇表V中所有符号组成的符号串B、文法G的字汇表V的闭包V*中的所有符号串C、由文法的识别符号推出的所有符号串D、由文法的识别符号推出的所有终结符号串答案：B第4题给定文法如下：S→AB A→aA|a B→bB|b 句型aAB相对于A的短语是（）。

A、aB、AC、aAD、AB答案：C第5题（）不是编译程序的组成部分。

A、词法分析器B、设备管理程序C、语法分析程序D、代码生成程序答案：B第6题编译程序是将（）翻译成（）。

A、汇编语言程序机器语言程序B、高级语言程序汇编语言程序或机器语言程序C、汇编语言程序或高级语言程序机器语言程序或高级语言程序D、高级语言程序机器语言程序或高级语言程序答案：B第7题一个正规语言只能对应（）。

A、一个正规文法B、一个最小有限状态自动机答案：B第8题（）这样一些语言，它们能被确定的有穷自动机识别，但不能用正规表达式表示。

A、存在B、不存在C、无法判定是否存在答案：B第9题程序语言一般分为（）和（）两大类。

A、高级语言低级语言B、低级语言通用程序语言C、高级语言专用程序语言D、低级语言专用程序语言答案：D第10题由于受到具体机器主存容量的限制，编译程序几个不同阶段的工作往往被组合成（）。

A、过程B、程序C、批量D、遍答案：D多项选择题第11题编译过程中扫描器的任务包括（）。

A、组织原程序的输入B、识别单词属性，并输出C、删除注解D、行计数、列计数E、建立符号表答案：A|B|C|D|E第12题编译过程中，语法分析器的任务是（）。

A、分析单词是怎样构成的B、分析单词串是如何构成语句和说明的C、分析语句和说明是如何构成程序的D、分析程序的结构答案：B|C|D第13题(ab|b)*c 与下面的那些串匹配？（）A、ababbcB、ababC、cD、babcE、aaabc答案：A|C|D第14题指出哪些串是自动机可接受的（）。