1.名词解释：翻译程序、汇编程序、编译程序和解释程序。 翻译程序是指这样一种程序，它能将用甲语言（源语言）编写的程序（源程序）翻译成与之 等价的用乙语言（目标语言）书写的程序（目标程序）。 ·编译程序 目标程 编程序 汇程序 机言 解释程序将按源程序中语句的动态顺序，逐句地进行分析解释，并立即予以执行。 2.绘制编译程序组成图 3试写出V={0,1上下述集合的正则表达式，并将正规式转换为自动机。 1)所有以1开始和结束的符号串 2)恰好含有3个1的所有符号所组成的集合 3)集合{01,1： 4)所有以1结束的符号串 4.对于下列的状态转换表分别画出相应的状态转换图。 ab ab SIAS A A 1 BB1 BBB 5.名词解释： )文法、句型、句子、语言 2)短语、简单短语、句柄 文法是描述语言的语法结构的形式规则（即语法规则）。 句型：假定G是一个文法，S是它的开始符号。如果a,则称α是一个句型。 句子：仅含终结符号的句型是一个句子。 语言：文法G所产生的句子的全体是一个语言，将它记为LG) 短语： 如果有S Ay且有AB,则B是句型xBy相 于非终结符A的短语 简单短语：如果有S->xAy且有A>B,则B是句型xBy相对于A>B的直接短语 句柄：位于一个句型最左边的直接短语称为句板 6.设有文法G(S: g.31 N->DIND D->0川1249 试写出028和4321的最左推导和最右推导。 7.证明文法G(S)是二义性文法： S->if E then S else Slif E then S s E->011 &.设有文法GE):
1． 名词解释：翻译程序、汇编程序、编译程序和解释程序。 翻译程序是指这样一种程序，它能将用甲语言（源语言）编写的程序(源程序）翻译成与之 等价的用乙语言（目标语言）书写的程序（目标程序）。 解释程序将按源程序中语句的动态顺序，逐句地进行分析解释，并立即予以执行。 2． 绘制编译程序组成图。 3.试写出 V={0,1}上下述集合的正则表达式，并将正规式转换为自动机。 1）所有以 1 开始和结束的符号串 2）恰好含有 3 个 1 的所有符号所组成的集合 3）集合{01，1}； 4）所有以 111 结束的符号串 4．对于下列的状态转换表分别画出相应的状态转换图。 a b S A S A A B B B B 1 5. 名词解释： 1）文法、句型、句子、语言 2）短语、简单短语、句柄 文法是描述语言的语法结构的形式规则（即语法规则）。 句型：假定 G 是一个文法，S 是它的开始符号。如果 S α，则称α是一个句型。 句子：仅含终结符号的句型是一个句子。 语言：文法 G 所产生的句子的全体是一个语言，将它记为 L(G)。 短语：如果有 S=>xAy, 且有 A=>β,则β是句型 xβy 相对于非终结符 A 的短语 简单短语：如果有 S=>xAy, 且有 A=>β,则β是句型 xβy 相对于 A->β的直接短语 句柄：位于一个句型最左边的直接短语称为句柄. 6. 设有文法 G(S): S->N N->D|ND D->0|1|2|…|9 试写出 028 和 4321 的最左推导和最右推导。 7. 证明文法 G(S)是二义性文法： S->if E then S else S | if E then S | s E->0 | 1 8. 设有文法 G(E): a b S A S A B A 1 B B B ·编译程序 高级语言 源程序 汇编语言或机器语言 目标程序 编译程序 ·汇编程序 汇编语言 源程序 机器语言 目标程序 汇编程序
EeTIT T->T/PIP 2)试写出句型(D-)/心的短语、简单短语和句柄。 9.试述下列概念并举例予以说明： 1)素短语 2)最左素短语 素短语： 至少含有 一个终结符且除自身外，不再包含任何其它更小的素短语 最左素短语(leftmost prime phrase):是指位于句型最左边的那个素短语。 10.对文法G(E): E”->#E# E>ET E->T E->i T->(E) )构造该文法的优先关系表 2)判断该文法是否是算符优先文法 1.将下列 表达式改写为后表达 1)(a+b)*c ab+c 2)a+b*c abc+ 3)(a-b)+e/d ab-cd/t 12.写出赋值语句a:=b*c+b*d的四元式和三元式试。 四元式， b c 1 *b c 2*bdT2 2 3+T1T2T3 3+12 4=3 4=a3 13.简述符号表的内容 14.符号表的数据结构有哪些？ 1.符号表的每一项包含两部分，一部分是名字（标识符），另一部分是此名字的有关 信息 2.线性表、二叉树、散列表（杂凑技术） 15.考察下面程序段： procedure p(x,y,z) a+b,a,a begin a:-a+1 end; program file(input,output) begin a:=2
E->E-T | T T->T /P | P P->i | (E) 1) 试写出 i/(i-i-i) 的语法树 2）试写出句型 ( p-i)/p 的短语、简单短语和句柄。 9. 试述下列概念并举例予以说明： 1） 素短语 2） 最左素短语 素短语：至少含有一个终结符,且除自身外,不再包含任何其它更小的素短语。 最左素短语(leftmost prime phrase)：是指位于句型最左边的那个素短语。 10. 对文法 G(E)： E’->#E# E->E-T E->T E->i T->(E) 1) 构造该文法的优先关系表 2）判断该文法是否是算符优先文法 11. 将下列中缀表达式改写为后缀表达式 1）（a+b）*c ab+c* 2）a+b*c abc*+ 3）(a-b)+c/d ab-cd/+ 12. 写出赋值语句 a:=b*c+b*d 的四元式和三元式。 四元式： 1 * b c T1 2 * b d T2 3 + T1 T2 T3 4 := T3 a 13. 简述符号表的内容。 14. 符号表的数据结构有哪些？ 1．符号表的每一项包含两部分，一部分是名字（标识符），另一部分是此名字的有关 信息。 2．线性表、二叉树、散列表（杂凑技术） 15. 考察下面程序段： procedure p(x,y,z) a+b,a,a begin y:=y+1; a:=a+1; z:=z+x a:=a+a+b; end; program file(input,output) begin a:=2; b:=3; 1 * b c 2 * b d 3 + 1 2 4 := a 3
p(a+b,a,a片 write(a) end 若参数传递分别是(1)按名(2)按值方式，上述程序执行后，输出a的值分别时 多少？ (1)按名9 (2)按值2 16.简述代码优化原则。 等价：是指不改变程序的运行结果： 有效：主要指优化后的目标代码运行时间较短，以及占用的存储空间较小。 合算：应尽可能以较低的代价取得较好的优化效果。 17.目标代码的形式有哪些2 1)机器语言代码（绝对指令代码）：所有地址已定位，可立即执行 2)待装配的机器语言模块（可重定位的指令代码） 3)汇编语言代码（汇编指令代码）
p(a+b,a,a); write(a) end 若参数传递分别是（1）按名 （2）按值 方式，上述程序执行后，输出 a 的值分别时 多少？ （1）按名 9 （2）按值 2 16. 简述代码优化原则。 等价:是指不改变程序的运行结果； 有效:主要指优化后的目标代码运行时间较短,以及占用的存储空间较小。 合算:应尽可能以较低的代价取得较好的优化效果。 17. 目标代码的形式有哪些？ 1）机器语言代码（绝对指令代码）：所有地址已定位，可立即执行 2）待装配的机器语言模块（可重定位的指令代码） 3）汇编语言代码（汇编指令代码）
