编译原理复习题49274.doc

1.把汇编语言程序翻译成机器可执行的目标程序的工作是由 B 完成的。 A、编译器 C、解释器 D、预处理器2.编译程序生成的目标程序 B 是机器语言的程序。 A、一定 B、不一定 3.下面关于解释程序的描述正确的是 B 。 解释程序的特点是处理程序时不产生目标代码。 解释程序适用于COBOL和FORTRAN语言。 解释程序是为打开编译程序技术得僵局而开发的。A、 B、 C、 D、4.设有文法GI：II1I0IaIcabc下列符号串中是该文法的句子有 B 。 ab0 a0c01 aaa bc10可选项有： A、 B、 C、 D、5.一个上下文无关文法消除了左递归，提取了左公共因子后是满足LL（1）文法的 A 。 A、 必要条件 B、充分必要条件1.一个语言的文法是 B 。A、唯一的B、不唯一的C、个数有限的2. 设有文法GS:S:=S*S|S+S|(S)|a该文法 B 二义性文法A 是 B 不是 C无法判断。 3.给定文法AbAcc，下面的符号串中，为该文法句子的是 A 。A、cc B、bcbc C、bccbcc D、bbbcc4.编译过程中，语法分析器的任务是 B 。分析单词是怎样构成的分析单词串是如何构成语句和说明的分析语句和说明是如何构成程序的分析程序的结构A、 B、 C、 D、 5.一个句型中的最左 B 成为该句型的句柄。 A、短语 B、简单短语 C、素短语 D、终结符号1. 面向机器语言指的是_C_。 A、用于解决机器硬件设计问题的语言 B、特定计算机系统所固有的语言 C、各种计算机系统都通用的语言 D、只能在一台计算机上使用的语言2.如果文法G是无二义的，则下面 D 成立。A、文法中的句子对应两棵不同的语法树；B、文法中某个句子有两个不同的最左推导；C、文法中某个句子有两个不同的最右推导；D、文法中任一句子，它的最左或最右推导对应的语法树相同。 3.运行阶段的存储组织与管理的目的是_C_。 提高编译程序的运行速度。 提高目标程序的运行速度。 为运行阶段的存储分配做准备。 A、 B、 C、 D、4. 设有文法GI:I-I1|I0|Ia|Ic|a|b|c下列符号串中是该文法的句子的是_C_1 ab0 2 a0c01 3 aaa 4 bc10可选项有 A 1 B234 C 34 D12345.下面说法正确的是 A 。 A、一个SLR（1）文法一定也是LALR（1）文法 B、一个LR（1）文法一定也是LALR（1）文法1.动态存储分配时，可以采用的分配方法有_ C _。 以过程为单位的栈式动态存储分配 堆式存储分配 最佳分配方法 A、 B、 C、 D、2.面向机器语言的特点是_ D _。 A、程序的执行效率低，编制效率低，可读性差 B、程序的执行效率高，编制效率高，可读性强 C、程序的执行效率低，编制效率高，可读性强 D、程序的执行效率高，编制效率低，可读性差3. 下面关于解释程序的描述正确的是 B 。 解释程序的特点是处理程序时不产生目标代码。 解释程序适用于COBOL和FORTRAN语言。 解释程序是为打开编译程序技术得僵局而开发的。A、 B、 C、 D、 4. 编译过程中，语法分析器的任务是 B 。分析单词是怎样构成的分析单词串是如何构成语句和说明的分析语句和说明是如何构成程序的分析程序的结构A、 B、 C、 D、 5. 一个句型中的最左 B 成为该句型的句柄。 A、短语 B、简单短语 C、素短语 D、终结符号1. 编译程序众的语法分析器接受以 C 为单位的输入，并产生有关信息工以后各阶段适用。 A、表达式 B、 产生式 C、单词 D、语句2. 经过编译所得到的目标程序是 D 。 A、 四元式序列 B、 二元式序列 C、 间接三元式序列 D、 机器语言程序或汇编语言程序 3. 编译程序是将高级语言程序翻译成 B 。 A、机器语言程序 B、汇编语言程序或机器语言程序 C、汇编语言程序或高级语言程序 D、机器语言程序或高级语言程序4. 设有文法GI：II1I0IaIcabc下列符号串中是该文法的句子有 B 。 ab0 a0c01 aaa bc10可选项有： A、 B、 C、 D、 5. 巴科斯-诺尔范式（BNF）是一种广泛采用的 C 的工具。A、描述规则 B、描述语言 C、 描述文法 D、 描述句子1. 编译程序众的语法分析器接受以 C 为单位的输入，并产生有关信息工以后各阶段适用。 A、表达式 B、 产生式 C、单词 D、语句2. 如果文法G是无二义的，则下面 D 成立。A、文法中的句子对应两棵不同的语法树；B、文法中某个句子有两个不同的最左推导；C、文法中某个句子有两个不同的最右推导；D、文法中任一句子，它的最左或最右推导对应的语法树相同。 3. 编译过程中，语法分析器的任务是 B 。(1) 分析单词是怎样构成的（2）分析单词串是如何构成语句和说明的（3）分析语句和说明是如何构成程序的（4）分析程序的结构A、（2）（3） B、（2）（3）（4） C、(1)（2）（3） D、(1)（2）（3）（4）4. 动态存储分配时，可以采用的分配方法有 C 。 以过程为单位的栈式动态存储分配。 堆式存储分配。 最佳分派方法 A、 B、 C、 D、 5. 一个编译程序中，不仅包含词法分析，语法分析，中间代码生成，代码优化，目标代码生成等五个部分，还应包含 C 。 A、模拟执行器 B、解释器 C、表格处理和出错处理 D、符号执行器1.一个LR（1）文法合并同心集后若不是LALR（1）文法 B 。 A、则可能存在移进/归约冲突 B、则可能存在归约/归约冲突 C、则可能存在移进/归约冲突和归约/归约冲突2.LL(k)文法 B 二义性的。 A、都是B、都不是C、不一定3. 与PASCAL语言存储分配方式相识的语言是 A 。 A、C语言 B、BASIC语言 C、FORTRAN-77 D、C+语言4. B 这样一些语言，它们能够被确定的有穷自动机识别，但不能用正规表达式表示。A、存在B、不存在 C、无法判定5. 编译程序在其工作过程中使用最多的数据结构是 D 。 A、线性表 B、链表 C、表 D、符号表1. 程序语言的语言处理程序是一种 A 。 A、系统软件 B、应用软件 C、实时软件 D、分布式系统2. 一个正规语言只能对应 B 。 A、 一个正规文法 B、一个最小有限状态自动机3. 下列关于标识符和名字的叙述中，正确的为 D 。 A、标识符有一定的含义 B、名字是一个没有意义的字符序列 C、名字有确切的属性 D、都不对4.文法GA：A AaB BAb Ba是 B 。 A、正规文法 B、二型文法5. 返填技术指的是 A 。 A、生成跳转、调用等指令时，不能获得转向地址，需要等到获得该转向地址后再回来填写。 B、符号表中过程或函数标识符的地址部分要填上入口地址，在扫描到过程或函数标识符的说明时这些地址是无法知道的，只有等到开始生成过程或函数的指令部分时才能填入。 C、A和B D、都不确切1. 一般程序设计语言的定义都涉及 B 三个方面。语法 语义 语用 程序基本符号的确定A、 B、 C、 D、 2. 下面说法正确的是 B 。 A、一个正规式只能对应一个确定的有限状态自动机； B、一个正规语言可能对应多个正规文法；3. 程序基本块是指 D 。 A、一个子程序 B、一个仅有一个入口和一个出口的语句 C、一个没有嵌套的程序段 D、一组顺序执行的程序段，仅有一个入口和一个出口。4. 词法分析的常用方法有 A 。 A、有穷自动机理论 B、图灵机 C、图论 D、无穷自动机理论5. 编译方法中自顶向下的语法分析算法有 D 。简单优先分析方法算符优先分析方法 递归子程序法 LL(K)分析法 SLR分析法 LR(K)方法LALR(K)方法 预测分析方法A、 B、 C、 D、 E、二、填空题 （15分）1. 编译程序必须完成的工作有 A 。词法分析 语法分析 语义分析 代码生成 中间代码生成 代码优化A、 B、 C、 D、 E、2. 语法分析的常用方法有 D 。 A、自顶向下匹配 B、自底向上归约 C、回溯法 D、自顶向下匹配和自底向上归约3. 在编译程序采用的优化方法中， C 是在循环语句范围内进行的。（1）合并已知常量（2）删除多余运算（3）删除归纳变量（4）强度削弱（5）代码外提 A、（1）（4） B、（1）（5） C、（1）（4）（5） D、（3）（4）（5）4. 过程调用时，参数的传递方法通常有 D 。（1）传值（2）传地址（3）传结果（4）传名 A、（1）（2） B、（1）（2）（3） C、（1）（2）（4） D、（1）（2）（3）（4）5. 编译方法中自底向上的语法分析算法有 C 。简单优先分析方法算符优先分析方法 递归子程序法 LL(K)分析法 SLR分析法 LR(K)方法 LALR(K)方法 预测分析方法A、 B、 C、 D、 E、1. 文法G所描述的语言是 D 集合。A、 文法G的字汇表V中所有符号组成的符号串B、 文法G的字汇表V的闭包V*中的所有符号串C、 由文法的识别符号推出的所有符号串D、 由文法的识别符号推出的所有终结符号串2. 下面说法正确的是 B 。 A、一个正规式只能对应一个确定的有限状态自动机； B、一个正规语言可能对应多个正规文法；3. 代码生成应着重考虑的问题是 B 。 每一个语法成分的语义目标程序运行所占用的空间目标程序的运行速度目标代码中需要那些信息，怎样截取这些信息A、 B、 C、 D、 4.编译程序在优化时， B 用到源程序中的注释。A、可能要 B、不可能5. 下面说法正确的是 A 。 A、 一个正规文法也一定是二型文法B、一个二型文法也一定能有一个等价的正规文法1. 文法的二义性和语言的二义性是两个 A 的概念。 A、不同 B、相同 C、不一定2. 下面说法正确的是 B 。 A、一个正规式只能对应一个确定的有限状态自动机； B、一个正规语言可能对应多个正规文法；3. LR语法分析栈中存放的状态是识别的 B DFA状态。A、前缀 B、可归前缀 C、项目 D、句柄4. 正规文法 A 二义性的。A、可以是B、一定不是C、一定是5. 高级语言编译程序常用的语法分析方法中，递归下降分析法属于 B 分析方法。 A、 自左向右 B、自顶向下 C、自底向上 D、自右向左1. 一个语言的文法是 B 。A、唯一的B、不唯一的C、个数有限的2. 代码生成应着重考虑的问题是 D 。 每一个语法成分的语义目标程序运行所站用的空间目标程序的运行速度目标代码中需要那些信息，这样截取这些信息。 A、 B、 C、 D、3. 运行阶段的存储组织与管理的目的是 C 。 提高编译程序的运行速度。 提高目标程序的运行速度。 为运行阶段的存储分配做准备。 A、 B、 C、 D、 4. 编译过程中，比较常见的中间语言有 D 。 波兰表示逆波兰表示三元式四元式树形表示 A、B、C、 D、5. 过程信息表中至少应该包括有 D 。 过程名过程的静态层次过程的入口地址过程首部在源程序中的行号有关过程的参数信息。 A、 B、 C、 D、二、填空题 （15分）1.如果在一个文法中存在某个句子，它有二个以上的最左（最右）推导，也就是说，若该句子对应两棵不同的语法树 ，则这个文法是二义性文法。 2. 假设G是一个文法，S是文法的开始符号，如果S * x，则称x是 句型 。（2分）3.LR(K)分析法中， L的含义是自左向右进行分析，R含义是采用最右推导的逆过程最左归约，“K”的含义是至多向前查看K个输入符号。4.自顶向下语法分析方法会遇到的主要问题有 左递归 和 回溯 。5.编译过程中，常见的中间语言形式有三元式、 逆波兰式 和四元式。6.在编译程序中安排中间代码生成的目的是便于代码优化和便于目标程序的移植。1.程序的翻译方式有两种，分别是_编译方式_和_解释方式_。 2.字的前缀是指该字的 任意首部 。（2分）3.LR(1)分析法中，L的含义是自左向右进行分析，R含义是采用最右推导的逆过程-最左归约，“1”的含义是向貌似句柄的符号串后查看一个输入符号。4.编译过程中，常见的中间语言形式有 三元式 、逆波兰式和四元式 。5.程序的可再入性指的是：当程序在执行时，可以_随时中断_它的执行，也可随时_执行进程_恢复其原来的_执行进程_；而且可以在_中断时间里_，又从该程序的_头上 开始一个新的执行过程。1.编译程序与具体的机器 无关 ，与具体的语言 有关 。2.SLR(1)分析法中，L的含义是 自左向右进行分析 ，R含义是 采用最右推导的逆过程 ，S含义是 简单的 ，“1”的含义是 向貌似句柄的符号串的查看一个输入符号 。4.确定的有穷自动机是一个 五元组 ，通常表示为 M（Q，t,q0,F） 。5.在大部分现有编译中采用的方案主要有两种： 动态 分配方案和_静态_分配方案。6.假定G是一个文法，S是它的 开始符号 ，如果S * ，则称_是一个句型，仅含终结符号的句型是一个 句子 。文法G所产生的 句子的全体是一个 语言 ，将它记为L(G)。1. 如果在一个文法中存在某个句子，它有 二个以上 得最左（最右）推导，也就是说，若该句子对应两棵不同的 语法树 ，则这个文法是 二义性 文法。 2. 对编译程序而言，输入数据是源程序，输出结果是 目标程序 。3. LR(1)分析法中，L的含义是 自左向右进行分析 ，R含义是采用最右推导的逆过程最左归约，“1”的含义是 至多向前查看一个输入符号。4. 语法分析是依据语言的语法 规则进行的，中间代码产生是依据语言的语义 规则进行的。5. 编译过程中，常见的中间语言形式有 三元式 、逆波兰式和 四元式 。6. 编译过程中扫描器所完成的任务是从 源程序 中识别出一个一个具有独立 语法意义的单词 。1. 如果在一个文法中存在某个句子，它有 二个以上 得最左（最右）推导，也就是说，若该句子对应两棵不同的 语法树 ，则这个文法是 二义性 文法。 2. 编译方式与解释方式的根本区别在于 是否生成目标代码 。（2分）3. LL(1)分析法中，第一个L的含义是 从左往右 ，第二个L含义是 每次进行最左推导，“1”的含义是 向输入串中查看一个输入符号 。4. 自顶向下语法分析方法会遇到的主要问题有左递归和回溯。5. 符号表的数据结构可以是 线性符号表、 树结构 、 散列表。6. 一个字集是正规的，当且仅当它可由 DFA（NFA） 所识别。1. 假定G是一个文法，S是它的 开始符号 ，如果S * ，则称 是一个句型，仅含终结符号的句型是一个 句子 。文法G所产生的 句子 的全体是一个 语言 ，将它记为L(G)。 2. 乔姆斯基定义的四种形式语言文法分别为： 0型 文法（又称 短语结构 文法）、 1型 文法（又称 上下文有关文法）、 2型 文法（又称 上下文无关 文法）、 3型 文法（又称 正则文法）。3. 自顶向下 语法分析方法的基本思想是：从 识别符号 出发，利用文法的规则不断建立 直接推导推导，试图构造一个推导序列，最终由它推导出与输入符号串 相同的符号串。1.编译程序的工作过程一般可以划分为_词法分析_、_语法分析_、_语义分析、_中间代码生成、_代码优化_等几个基本阶段，同时还会伴有 表格处理 和 出错处理 。 2.文法G产生的 所有句子 的全体是该文法描述的语言。3.来自中间代码的代码生成涉及了两个标准技术：宏扩展和静态模拟。_宏扩展_涉及到用一系列等效 的目标代码指令代替每一种中间代码指令。4.为文法的每一个规则配备的计算属性的计算规则，称为 语义规则。1.中间代码有逆波兰式 、 三元式样 、 四元式、 树形表示 等形式，生成中间代码主要是为了使 代码优化及目标程序便于移植 。（6分）。 2. 文法G产生的 句子 的全体是该文法描述的语言（2分）。3. 在一个基本块内，可实行3种优化方法，即合并已知量、删除无用赋值 、删除多余运算。4. 确定的有穷自动机是一个五元组 ，通常表示为 M（Q，t,q0,F） 。5. 活前缀是指规范句型的一个前缀，这种前缀不含句柄之后的任何符号。1. 编译程序的工作过程一般可以划分为词法分析_、_语法分析_、_语义分析、_中间代码生成、_代码优化_等几个基本阶段，同时还会伴有表格处理 和 出错处理（6分）。 2. 在目标代码生成阶段，符号表是 地址分配 的依据。（2分）。3. 符号表的数据结构可以是无序符号表、有序符号表 、栈式符号表 。4. 词法分析阶段的错误主要是 单词拼写错误 ，可通过最小距离匹配的办法纠正错误。5. 在大部分现有编译中采用的方案主要有两种： 动态 分配方案和 静态 分配方案。1. 编译程序工作过程中，第一段输入是 源程序 ，最后阶段的输出为 目标 程序。2.若二个正规式所表示的正规集相同，则认为二者是等价的（2分）。 3. 符号表中名字的有关信息在 词法分析 和 语法语义分析 过程中陆续填入。4. 自顶向下 语法分析方法的基本思想是：从 识别符号 出发，利用文法的规则不断建立 直接 推导，试图构造一个推导序列，最终由它推导出与输入符号串 的符号串。5. 堆式动态分配策略允许用户动态的 申请 和 释放 存储空间存储。6. 语法树代表推导过程，分析树代表归约过程。7.在优化中，可把循环中的不变运算提到循环外面去，这种方法称为 代码外提。1 最左推导是指每次都对句型中的 最左 非终结符进行扩展。2. 确定有限自动机DFA是 NFA 的一个特例。（2分）。3. 自顶向下语法分析方法的基本思想是：从 识别符号出发，利用文法的规则不断建立 直接推导，试图构造一个推导序列，最终由它推导出与输入符号串 的符号串。4. 确定的有穷自动机是一个 五元组 ，通常表示为 M（Q，t,q0,F） 。5. 一个字集是正规的，当且仅当它可由 DFA（NFA） 所识别。6.文法中的终结符和非终结符的交集是空集 。词法分析器交给语法分析器的文法符号一定是终结符 ，它一定只出现在产生式的右 部。7 目标程序运行的动态分配策略中，含有栈式 和 堆式分配策略。1.自底向上语法分析方法的基本思想是：从待输入的符号串开始，利用文法的规则步步向上进行 归约 ，试图 归约 到文法的 识别符号 。2. 若源程序使用高级语言编写的，目标程序是 机器语言程序 ，则其翻译程序称为编译程序（2分）。 2. 编译程序是指将 源程序 程序翻译成 目标 程序的程序。3. 自顶向下 语法分析方法的基本思想是：从 识别符号 出发，利用文法的规则不断建立直接推导推导，试图构造一个推导序列，最终由它推导出与输入符号串 的符号串。4. 编译过程通常可分为5个阶段，分别是 词法分析 、语法分析、 语义分析 、代码优化和目标代码生成。5. 优化就是对程序进行各种等价变换，使之能生成更有效的目标代码。1. 自下而上分析法采用 移进 、归约、错误处理、 接受 等四种操作。 2. 采用 自上而下 语法分析时，必须消除文法的左递归（2分）。3. 已知文法GE：ETE+TE-TTFT*FT/FF(E)i该文法的开始符号是 E ，终结符号集合VT是 +、-、*、/、(、)、i ，非终结符号集合VN是 E、T、F。4. 扫描器 的任务是从左到右一个一个地对源程序进行扫描，产生一个一个的 具有独立语法意义的单词 。5. 优化就是对程序进行各种 等价 变换，使之能生成更有效的 目标代码 。6. A称为归约 项目；对文法开始符S为接受项目；若a为终结符，则称Aa为 移进 项目；若B为非终结符，则称Aa为待约 项目。三、简答题。（30分） 1.什么是算符优先文法？给出一个非教材上提供的算符优先文法的例子，并给出算符优先表？（6分）设文法G，如果它的产生式右部不包含相邻非终结符号，则称文法G为算符文法，如果算符文法的终结符号集中任意两个符号之间至多存在一种优先关系，则称该算符文法为算符优先文法。例如：E-E+T|TT-T*F|FF-(E)|i+*()i+(=i2.设有文法GS：Sa|(T)TT,S|S请给出句子(a,(a,a)的最左和最右推导，给出该句子的短语和句柄。（7分）最左推导：S=(T) =(T,S) =(a,S)=(a,(T,S) =(a,(S,S)=(a,(a,S)=(a,(a,a)最右推导：S=(T)=(T,S)=(T,(T)=(T,(T,S) =(T,(T,a)=(T,(S,a)=(T,(a,a) =(S,(a,a)=(a,(a,a)3. 编译程序的实现应考虑的问题有那些？（4分）编译程序的实现 应考虑：开发周期、目标程序的效率、可移植性、可调试性、可维护性、可扩充性等。4.什么是二义性文法？请用例说明文法GE：Ei|(E)|EAE A+|-|*|/是二义性文法。（6分）一个文法如果它的一个句子有两棵或两棵以上的语法树，则称该句子具有二义性，如果一个文法含有二义性的句子，则该文法是二义性文法。如句子：i+i+i5.在编译过程中为什么要建立符号表？简述符号表的组织，即它一般分成几部分，含有那些域？（6分）在编译过程中，始终涉及到对一些语法符号的处理，需要用到这些语法符号的相关属性。为了在需要的时候能找到这些语法成分及其相关属性，必须使用一些表格保存这些语法成分及其属性，这些表格就是符号表。符号表应包括语法符号的名字和相关属性，不同语法符号在符号表中存放的信息不同。符号表的条目一般由两部分组成，即名字栏和信息栏。符号表域包括标识符名、其他信息、地址等。对名字栏，为节省空间，可另外设立一个存放标识符的字符数组。对信息栏中的类型等信息可以用数值或向量来表示，以节省空间1. .设有文法GE： ET|ET TF|T * F F(E)|i 请给出句型(T * Fi)的最右推导及画出语法树。（5分）最右推导： ETF(E) (ET) (EF) (Ei)(Ti) (T*Fi)ETF( E ) E + T F i T T * F 2.对于上题，消除左递归和回溯，给出递归下降算法。（6分）3.对于第1小题，给出句型(T * Fi)的短语、简单短语及句柄。（5分）短语：(T*Fi)，T*Fi，T*F，i素短语：T*F,i4. 适合采用静态存储分配的程序设计语言应有哪些限制？（6分）数据实体所需空间在编译时能确定运行时每个数据对象只能有一个实例数组的上下界是常量过程调用不允许递归不能动态建立数据实体5.分离连表法是如何解决冲突的？如杂凑表的尺寸是5，有4个变量，x，y，temp，z，其中y和temp的杂凑值相等，请给出分离链接的杂凑表。（8）1.设有文法GS：SaAcB|BdAAaB|cBbScA|b请给出句子acabcbbdcc的最左推导及语法树。（6分）s-aAcB-aAaBcB-aCaBcB-acabcB-acabcbScA-acabcbBCCA-acabcbbdcc 2.判断上题是否是算符优先文法？如是，请给出算符优先关系表。（7分）是算符优先关系。因为产生式右部不包含相邻非终结符号firstvt(s)=a,b,d lastvt(s)=a,b,c,dfirstvt(s)=a,c lastvt(s)=a,b,cfirstvt(s)=b lastvt(s)=a,b,cabcdab=cd3.对于第1小题给定的文法，句型aAaBScAcB的短语、简单短语及句柄是什么？（6分）S a A C B A a B b s c A短语：bScA AabScA aAabScAcB简单短语：bScA句柄：bScA4.什么是二义性文法？请用例说明文法GE：Ei | (E) | EAE A + | - | * | /是二义性文法。（6分）一个文法如果它的一个句子有两棵或两棵以上的语法树，则称此句子具有二义性，如果一个文法含有二义性的句子，则称此文法具有二义性。例： i+i+i5.符号表的作用是什么？一般有哪几种结构？（5分）在编译过程中，始终涉及对一些语法符号的处理。要用到这些符号的相关属性。符号表的作用就是保存这些成份及其相关属性，以便在用时能找到。无序符号表有序符号表栈符号表1、简述自顶向下分析法。从识别符号出发，不断建立直接推导，试图构造一个推导序列，最终由它推导出与输入符号串相同的符号串。从语法树的角度看，自顶向下分析过程是以识别符号为根结点，试图向下构造一棵语法树，使其末端结点符号串正好与输入符号串相同。2、设有文法GA的产生式集为: ABaC|CbB BAc|c CBb|b 试消除GA的左递归。 提示：不妨以A、B、C排序.先将A代入B中，然后消除B中左递归；再将A、B代入C中。再消除C中左递归。 最后结果为:GA: ABaC|CbB BCbBcB|cB BaCcB| CcBbC|bC CbBcBbC|3、写出表达式a+b*(c-d)+e/(c-d)*n的三元式序列或P代码表示。(1)（_,c,d） (2) (*,b,(1) (3) (+,a,(2) (4) (_,c,d)(5) (/,e,(4) (6) (*,n,(5) (7)(+,(3),(6)4、什么样的文法是算符优先文法，请举个算符优先文法的例子。设文法G，如果它的产生式右部不包含相邻非终结符号，则称文法G为算符文法，如果算符文法的终结符号集中任意两个符号之间至多存在一种优先关系，则称该算符文法为算符优先文法。例如：E-E+T|TT-T*F|F F-(E)|i+*()i+(=i5、解释什么是归约？我们称直接归约出A，仅当A 是一个产生式， 且、(VNVT)*。归约过程就是从输入串开始，反复用产生式右部的符号替换成产生式左部符号，直至文法开始符。1、DFA和NFA有何区别？DFA和NFA的区别表现在三个方面。一是NFA可有若干个开始状态，而DFA仅有一个。二是DFA的映像M是从K到K，而的映象M是从K到K的子集，即映像M将产生一个状态集合（可能为空集），而不单个状态。三是NFA在没有扫描输入符号的情况下，也可以进行空移。2、已知文法G为：S aAcB|BdA AaB|cB bScA|b写出句子acabcbbdcc得最左推导及语法树s-aAcB-aAaBcB-aCaBcB-acabcB-acabcbScA-acabcbBCCA-acabcbbdcc Sa A c B A a B b S c A C b B d b3、写出表达式A=（x+y）*（c+d）+（x+y+c）的四元式序列或P代码表示。(1)（+,x,y）(2) (+,c,d)(3) (*,(1),(2)(4) (+,x,y)(5) (+,(4),c)(6) (+,(3),(5)1、语法分析的主要（功能）任务是什么？有哪二种分析分方法？语法分析的主要任务是对词法分析的输出结果-单词序列进行分析，识别合法的 语法单位。若给定的输入符号是该文法所产生的语言中的句子，就给出它的语法树，否则就报告出错信息。自上而下语法分析和自下而上语法分析。2、令文法G为Sa|(T)TT,S|S（1）给出(a,(a,a)的最右推导和最左推导。（2）画出语法分析树最左推导：S=(T) =(T,S) =(a,S)=(a,(T,S) =(a,(S,S)=(a,(a,S)=(a,(a,a)最右推导：S=(T)=(T,S)=(T,(T)=(T,(T,S) =(T,(T,a)=(T,(S,a)=(T,(a,a) =(S,(a,a)=(a,(a,a)3、写出表达式A=（a+b）+（c+d）*（x+y+c）的三元式序列或P代码表示。(1)（+,a,b）(2) (+,c,d)(3) (+,x,y)(4) (+,(3),c)(5) (*,(2),(4)(6) (+,(1),(5)4、什么是二义性文法？请举例说明。一个文法如果它的一个句子有两棵或两棵以上的语法树，则称此句子具有二义性，如果一个文法含有二义性的句子，则称此文法具有二义性。例： Ei | (E) | EAE A + | - | * | /i+i+iEEE A EE A EEA E t I i t E A Ei t i i t i5、在一个基本块内通常可实现哪些优化？合并已知量 删除公共子表达式 删除无用代码 复写传播4、什么是语法树?满足下面4个条件的树称之为文法GS的一棵语法树。每一终结均有一标记，此标记为VNVT中的一个符号；树的根结点以文法GS的开始符S标记；若一结点至少有一个直接后继，则此结点上的标记为VN中的一个符号；若一个以A为标记的结点有K个直接后继，且按从左至右的顺序，这些结点的标记分别为X1,X2,Xk，则AX1,X2,Xk， 必然是G的一个产生式。5、在编译过程中为什么要建立符号表，简述符号表的组织，即它一般分成几部分，含有那些域？在编译过程中，始终涉及到对一些语法符号的处理，需要用到这些语法符号的相关属性。为了在需要的时候能找到这些语法成分及其相关属性，必须使用一些表格保存这些语法成分及其属性，这些表格就是符号表。符号表应包括语法符号的名字和相关属性，不同语法符号在符号表中存放的信息不同。符号表的条目一般由两部分组成，即名字栏和信息栏。符号表域包括标识符名、其他信息、地址等。对名字栏，为节省空间，可另外设立一个存放标识符的字符数组。对信息栏中的类型等信息可以用数值或向量来表示，以节省空间1. 对如下文法：GS：SabS|aaB|adBbbB|b分别给出句子abaabbb和ad的句柄（6分）句子abaabbb的句柄是b；句子ad的句柄是ad2. 什么是可规约活前缀？举一例说明。（6分）若活前缀是含句柄的活前缀，即有 = ,且是句柄，则活前缀为可归约活前缀。例S a|bCdC e则be为一个可归约活前缀3.写出表达式(ab*c)/(ab)d的逆波兰表示及三元式序列或P代码。（6分）(1)（*,b,c）(2) (+,a,(1)(3) (+,a,b)(4) (/,(2),(3)(5) (-,(4),d)4.词法分析和语法分析都是对字符串进行识别，二者有何区别？（4分）在词法分析和语法分析中，都是对输入符号串进行识别。但词法分析的输入符号串是一个单词，而语法分析的输入符号串是一个句子或者说是一个程序。为了讨论方便，我们都是用小写字母来表示终结符号，但一定要明白在词法分析中小写字母表示组成单词的字符，而在语法分析中小写字母表示组成程序的的一个单词，识别方式来说，词法分析和语法分析都是对输入符号串结构的识别，但由于单词和程序的结构有所区别，所以具体的识别方式不一样。5.已知文法GS为：Sa|(T) TT,S|S判断该文法是否是算符优先文法？如是，请给出算符优先关系表。（8分）(1) FIRSTVT和LASTVT FIRSTVT LASTVT S a、（ a、） T ，、a、（ ，、a、) (2) 算符优先关系 a ( ) , # a ( ) , # 1、计算机执行用高级语言编写的程序有那些途径？它们之间的主要区别是什么？计算机执行用于高级语言编写的程序主要有两种途径：解释和编译。在解释方式下，翻译程序并不对高级语言进行彻底的翻译，而是读入一条语句，就解释其含义并执行，然后再读入下一条语句，再执行。在编译方式下，翻译程序先对高级语言进行彻底的翻译并生成目标代码，然后再对目标代码进行优化，即对源程序的处理是先翻译后执行。从速度上看，编译方式下，源程序的执行比解释方式下快，但在解释方式下，有利于程序的调试。2、编译程序的实现途径有那些？ 编译程序的实现途径可有：- 手工构造：用机器语言、汇编语言或高级程序设计语言书写。- 自动构造工具：Lex,Yacc。 Lex ,Yacc分别是词法和语法分析器的生成器。 - 移植方式：目标程序用中间语言 - 自展方式：用T型图表示 3、文法GE为： EE+T|T TT*F|F F(E)|i 试给出句型(E+F)*i的短语，简单(直接)短语,句柄和最左素短语。短语有: (E+F)*i ，(E+F) ，E+F ，F ，i 简单(直接)短语有: F ，i 句柄是: F 最左素短语是: E+F4、有人认为：“1型文法对规则的限制比2型文法对规则的限制要多一些”，这种说法对吗？文法是严格按照规则的形式来分类的1型文法的规则是：xUy-xuy uVn uV+ x,yV*要求将U替换为u时，U的前后一定要有x和y。而2型文法的规则形式为U-u uVn uV*没有什么要求，似乎1型的规则限制要多一些。但仔细看看1型规则中的条件x和y时，就不难发现当x和y为空时，正好是2型文法。从0型文法到3型文法，是依次增加对文法的限制，所以描述的语言集合越来越小。5、简述自底向上分析法。基本思想是：从待输入的符号串开始，利用文法的规则步步向上归约，试图归约到文法的识别符号。从语法树的角度看，自底向上分析的过程是以输入符号串作为末端结点符号串，向着根结点方向往上构造语法树，使识别符号正好是该语法树的根结点。如果最终根结点是识别符号，则输入符号串被识别是相应语言的一个句子；否则不是。 自底向上分析过程实际上是一个不断进行直接归约的过程。1、什么是规范推导？每个句型都有规范推导吗？规范推导就是最右推导每一个句子都有一个规范推导，而每一个句型则不一定都有规范推导，比如说采用非规范推导得到的句型。2、已知文法GE: EET+|T TTF* | F FF | a 试证：FF*是文法的句型，指出该句型的短语、简单短语和句柄。该句型对应的语法树如下：该句型相对于E的短语有FF*；相对于T的短语有FF*,F;相对于F的短语有F;F;简单短语有F;F;句柄为F. 3、写出表达式w+(a+b)*(c+d/(e-10)+8)的逆波兰表示及三元式序列。(1)（+,a,b）(2) (-,e,10)(3) (/,d,(2)(4) (+,c,(3)(5) (+,(4),8)(6) (*,(1),(5)(7) (+,w,(6)4、何谓优化？按所涉及的程序范围可分为哪几级优化？所谓优化，一般是指为提高目标程序的质量而进行的各项工作，即对程序或中间代码进行各种等价变换，使得从变换后的程序出发，能生成更有效的目标代码。 在源程序级 在语义动作的设计上 在中间代码级 在目标代码级5、简述自顶向下分析法。从识别符号出发，不断建立直接推导，试图构造一个推导序列，最终由它推导出与输入符号串相同的符号串。从语法树角度看，自顶向下分析过程是以识别符号为根结点，试图向下构造一棵语法树，使其末端结点符号串正好与输入符号串相同。1、实现高级语言程序的途径有哪几种？它们之间的区别？计算机执行用于高级语言编写的程序主要有两种途径：解