编译原理复习题

完成的。LL(1)文法的TOC\o"1-5"\h\z1•把汇编语言程序翻译成机器可执行的目标程序的工作是由 完成的。LL(1)文法的A、编译器 C、解释器D、预处理器2•编译程序生成的目标程序 B 是机器语言的程序。A、一定B、不一定3•下面关于解释程序的描述正确的是 B。解释程序的特点是处理程序时不产生目标代码。解释程序适用于COBOL和FORTRAN语言。解释程序是为打开编译程序技术得僵局而开发的。 {A、①②B、① C、①②③D、②③4•设有文法G[l]:Z11|10|la|IcIa|b|c下列符号串中是该文法的句子有 __B 。①ab0 ②a0c01 ③aaa④bc10可选项有： A、① B、②③④C③④D、①②③④5•—个上下文无关文法消除了左递归，提取了左公共因子后是满足A 。A、必要条件 B、充分必要条件1•一个语言的文法是 B 。A、唯一的 B、不唯一的 C、个数有限的2.设有文法G[S]:S::=S*S|S+S|(S)|a该文法B 二义性文法A是 B不是 C无法判断。3•给定文法AtbAIcc,下面的符号串中，为该文法句子的是 AA、cc B、bcbc C、bccbcc D、bbbcc4•编译过程中，语法分析器的任务是 B 。分析单词是怎样构成的 ②分析单词串是如何构成语句和说明的③分析语句和说明是如何构成程序的 ④分析程序的结构A、②③B、②③④C①②③D、①②③④5•一个句型中的最左_B 成为该句型的句柄。A、短语B、简单短语 C、素短语D、终结符号面向机器语言指的是 C__。A、 用于解决机器硬件设计问题的语言B、 特定计算机系统所固有的语言C各种计算机系统都通用的语言D、只能在一台计算机上使用的语言如果文法G是无二义的，则下面 成立。A、 文法中的句子对应两棵不同的语法树；B、 文法中某个句子有两个不同的最左推导；C文法中某个句子有两个不同的最右推导；D、文法中任一句子，它的最左或最右推导对应的语法树相同。运行阶段的存储组织与管理的目的是 ____C__。提高编译程序的运行速度。提高目标程序的运行速度。为运行阶段的存储分配做准备。A、①② B、①③ C②③D、①②③4・设有文法G[l]:l-I1|l0|la|lc|a|b|c' 下列符号串中是该文法的句子的是 C__1ab02a0c01 3aaa4bc10可选项有A1 B234 C34 D1234TOC\o"1-5"\h\z下面说法正确的是 A。A、一个SLR(1)文法一定也是LALR(1)文法B、一个LR(1)文法一定也是LALR(1)文法/1.动态存储分配时，可以采用的分配方法有 _C 。以过程为单位的栈式动态存储分配堆式存储分配 ③最佳分配方法A、① B、② C、①② D、①②③面向机器语言的特点是 D 。A、 程序的执行效率低，编制效率低，可读性差B、 程序的执行效率咼，编制效率咼，可读性强C程序的执行效率低，编制效率咼，可读性强D、程序的执行效率咼，编制效率低，可读性差TOC\o"1-5"\h\z下面关于解释程序的描述正确的是 B。解释程序的特点是处理程序时不产生目标代码。解释程序适用于COBOL和FORTRAN语言。解释程序是为打开编译程序技术得僵局而开发的。A、①②B① C、①②③ D、②③编译过程中，语法分析器的任务是 B。分析单词是怎样构成的 ②分析单词串是如何构成语句和说明的分析语句和说明是如何构成程序的 ④分析程序的结构A、②③B②③④ C、①②③D、①②③④一个句型中的最左 B成为该句型的句柄。A、短语B简单短语 C素短语 D、终结符号编译程序众的语法分析器接受以 C 为单位的输入，并产生有关信息工以后各阶段适用。A、表达式 B、产生式C、单词 D、语句经过编译所得到的目标程序是 D。A、四元式序列 B、二元式序列C 间接三元式序列 D、机器语言程序或汇编语言程序编译程序是将高级语言程序翻译成 B。A、 机器语言程序B、 汇编语言程序或机器语言程序C汇编语言程序或高级语言程序D、机器语言程序或高级语言程序设有文法G[l]:2I1|I0|la|lc|a|b|c下列符号串中是该文法的句子有 B 。①abO ②a0c01 ③aaa④bc10可选项有：A、①B、②③④ C、③④ D、①②③④\5.巴科斯-诺尔范式(BNF)是一种广泛采用的 C的工具。A、描述规则 B、描述语言 C描述文法 D、描述句子/1.编译程序众的语法分析器接受以 _C 为单位的输入，并产生有关信息工以后各阶段适用。A、表达式 B、产生式C、单词 D、语句如果文法G是无二义的，则下面 D 成立。A、 文法中的句子对应两棵不同的语法树；B、 文法中某个句子有两个不同的最左推导;C文法中某个句子有两个不同的最右推导;D、文法中任一句子，它的最左或最右推导对应的语法树相同。TOC\o"1-5"\h\z编译过程中，语法分析器的任务是 B。（1）分析单词是怎样构成的 （2）分析单词串是如何构成语句和说明的（3）分析语句和说明是如何构成程序的 （4）分析程序的结构A、（2）（3） B、（2）（3）（4） C、⑴（2）（3） D、⑴（2）（3）（4）动态存储分配时，可以采用的分配方法有 C。以过程为单位的栈式动态存储分配。堆式存储分配。最佳分派方法A、 ① B、 ② C①② D、 ①②③一个编译程序中，不仅包含词法分析，语法分析，中间代码生成，代码优化，目标代码生成等五个部分，还应包含 CA、 模拟执行器B、 解释器C表格处理和出错处理D、符号执行器1•一个LR（1）文法合并同心集后若不是 LALR（1）文法B。A、则可能存在移进/归约冲突B则可能存在归约/归约冲突C则可能存在移进/归约冲突和归约/归约冲突（k）文法B 二义性的。A、都是 B、都不是 C、不一定与PASCALS言存储分配方式相识的语言是 A。A、 C语言B、 BASIC语言CFORTRAN-77D、C++语言B 这样一些语言，它们能够被确定的有穷自动机识别， 但不能用正规表达式表示。A、存在 B、不存在 C无法判定TOC\o"1-5"\h\z编译程序在其工作过程中使用最多的数据结构是 D 。A、 线性表B、 链表C、 表D、 符号表程序语言的语言处理程序是一种 一A 。A、系统软件 B、应用软件 C、实时软件D、分布式系统一个正规语言只能对应 B。A、 一个正规文法B、一个最小有限状态自动机下列关于标识符和名字的叙述中，正确的为 D 。A、 标识符有一定的含义B、 名字是一个没有意义的字符序列C、 名字有确切的属性D、 都不对4•文法G[A]:A^sAtaB B~Ab B~a是B。A、正规文法 B、二型文法5.返填技术指的是 A。A、生成跳转、调用等指令时，不能获得转向地址，需要等到获得该转向地址后再回来

填写。B、符号表中过程或函数标识符的地址部分要填上入口地址，在扫描到过程或函数标识符的说明时这些地址是无法知道的，只有等到开始生成过程或函数的指令部分时才能填都不确切BC、A和B入。1.I三个方面。④程序基本符号的确定

C②③④只有等到开始生成过程或函数的指令部分时才能填都不确切BC、A和B入。1.I三个方面。④程序基本符号的确定

C②③④D、①③④2.3.4.5.1.2.A、B、

C

D、④LL（K分析法⑦LALR（K方法A、①②③⑧D、③④⑧般程序设计语言的定义都涉及

①语法②语义③语用A、①②③B、①②④TOC\o"1-5"\h\zF面说法正确的是 B。A、 一个正规式只能对应一个确定的有限状态自动机；B、 一个正规语言可能对应多个正规文法；程序基本块是指 D。一个子程序一个仅有一个入口和一个出口的语句一个没有嵌套的程序段一组顺序执行的程序段，仅有一个入口和一个出口。词法分析的常用方法有 A。A、有穷自动机理论B、图灵机C、图论D、无穷自动机理论编译方法中自顶向下的语法分析算法有 D。①简单优先分析方法②算符优先分析方法 ③递归子程序法⑤SLR分析法⑥LR（K方法⑧预测分析方法B、④⑤⑥⑦ C①②⑤⑥⑦E、①②③⑤⑥二、填空题 （15分）A 。语法分析 ③语义分析中间代码生成⑥代码优化C①②③④⑤⑥B、C①②③④⑤⑥E、①②③⑤⑥D编译程序必须完成的工作有①词法分析④代码生成A、①②③④D编译程序必须完成的工作有①词法分析④代码生成A、①②③④D、①②③④⑥语法分析的常用方法有 D。A、自顶向下匹配B、自底向上归约在编译程序采用的优化方法中， .（1）合并已知常量（2）删除多余运算（3）删除归纳变量（4）强度削弱（5）代码外提A、（1）（4）B、（1）（5）C（1）（4）（5）D、（3）（4）（5）过程调用时，参数的传递方法通常有 D（1）传值（2）传地址（3）传结果（4）传名A、（1）（2） B（1）（2）（3） C（1）（2）（4） D、（1）（2）（3）（4）编译方法中自底向上的语法分析算法有 C。①简单优先分析方法②算符优先分析方法 ③递归子程序法⑤SLR分析法 ⑥LR（K方法 ⑦LALR（K方法⑧预测分析方法B、④⑤⑥⑦ C①②⑤⑥⑦E、①②③⑤⑥D④LL（K分析法A、④LL（K分析法A、B、CD、D、③④⑧文法G所描述的语言是 D—集合。文法G的字汇表V中所有符号组成的符号串文法G的字汇表V的闭包V*中的所有符号串由文法的识别符号推出的所有符号串由文法的识别符号推出的所有终结符号串下面说法正确的是 B。A、 一个正规式只能对应一个确定的有限状态自动机；B、 一个正规语言可能对应多个正规文法；代码生成应着重考虑的问题是 B_。①每一个语法成分的语义 ②目标程序运行所占用的空间目标程序的运行速度 ④目标代码中需要那些信息，怎样截取这些信息A、①② B、①②③C①②④D、①④4•编译程序在优化时， B 用到源程序中的注释。A、可能要 B、不可能5.下面说法正确的是 A 。A、一个正规文法也一定是二型文法 B、一个二型文法也一定能有一个等价的正规文法文法的二义性和语言的二义性是两个 A的概念。A、不同B、相同 C、不一定下面说法正确的是 B。A、 一个正规式只能对应一个确定的有限状态自动机；B、 一个正规语言可能对应多个正规文法；LR语法分析栈中存放的状态是识别的 BDFA状态。A、前缀 B、可归前缀C项目D、句柄正规文法 A二义性的。A、可以是 B、一定不是 C、--定是高级语言编译程序常用的语法分析方法中，递归下降分析法属于 _B_分析方法。V A、自左向右 B、自顶向下C、自底向上D、自右向左TOC\o"1-5"\h\z一个语言的文法是 B。（ A、唯一的 B、不唯一的 C、个数有限的代码生成应着重考虑的问题是 D。每一个语法成分的语义②目标程序运行所站用的空间③目标程序的运行速度④目标代码中需要那些信息，这样截取这些信息。A、①②B、①②③C、①②④D①④运行阶段的存储组织与管理的目的是 C。提高编译程序的运行速度。提高目标程序的运行速度。为运行阶段的存储分配做准备。A、①② B、①③ C②③D、①②③编译过程中，比较常见的中间语言有 D。①波兰表示②逆波兰表示③三元式④四元式⑤树形表示A、①②④B、②③④C、①③④⑤D、②③④⑤过程信息表中至少应该包括有 。①过程名②过程的静态层次③过程的入口地址过程首部在源程序中的行号⑤有关过程的参数信息。A、①②③B①③④C①②③④D、①③⑤二、填空题（15分）如果在一个文法中存在某个句子，它有二个以上的最左（最右）推导，也就是说，若该句子对应两棵不同的语法树 ，则这个文法是二义性文法。假设G是一个文法，S是文法的开始符号，如果S*x，则称x是句型。（2分）（K）分析法中，L的含义是自左向右讲行分析， R含义是采用最右推导的逆过程最左归约，“K”的含义是至多向前查看K个输入符号。自顶向下语法分析方法会遇到的主要问题有 左涕归和回溯。编译过程中，常见的中间语言形式有三元—逆波兰式和四元式。在编译程序中安排中间代码生成的目的是便于代码优化和便于目标程序的移植。程序的翻译方式有两种，分别是_编译方式_和_解释方式_。字的前缀是指该字的 任意首咅B 。（2分）⑴分析法中，L的含义是自左向右进行分析， R含义是采用最右推导的逆过程 -最左归约,“1”的含义是向貌似句柄的符号串后查看一个输入符号。4•编译过程中，常见的中间语言形式有 三元式、逆波兰式和四元式 。5•程序的可再入性指的是：当程序在执行时，可以_随时中断__它的执行，也可随时一执行进程—恢复其原来的_执行进程_;而且可以在_中断时间里_，又从该程序的_头上开始一个新的执行过程。1•编译程序与具体的机器 无关，与具体的语言 有关。（1）分析法中，L的含义是 ，R含义是采用最右推导的逆过程 ，S含义是简单的 ，“1”的含义是向貌似句TOC\o"1-5"\h\z柄的符号串的查看一个输入符号 。确定的有穷自动机是一个 ,通常表示为M（Q，刀，t,qo,F） 。在大部分现有编译中采用的方案主要有两种： 动态 分配方案和 静态 分配方案。6.假定G是一个文法，S是它的 开始符号 ，如果S*a,则称_a__是一个句型，仅含终结符号的句型是一个 句子 。文法G所产生的 的全体是一个语言 ，将它记为L（G）。如果在一个文法中存在某个句子，它有 二个以上得最左（最右）推导，也就是说,若该句子对应两棵不同的 语法树，则这个文法是 二义性文法。对编译程序而言，输入数据是源程序，输出结果是 目标程序 。LR（1）分析法中，L的含义是 自左向右进行分析 ，R含义是采用最右推导的逆过程最左归约，“1”的含义是 至多向前查看一个输入符号。语法分析是依据语言的语法 规则进行的，中间代码产生是依据语言的语 义规则进行的。编译过程中，常见的中间语言形式有 三元式、逆波兰式和四元式。编译过程中扫描器所完成的任务是从 源程序 中识别岀一个一个具有独立 语法意义的单词。1.如果在一个文法中存在某个句子，它有 二个以上得最左（最右）推导，也就是说，若该句子对应两棵不同的 语法树 ，则这个文法是 二义性文法。编译方式与解释方式的根本区别在于 是否生成目标代码。（2分）LL（1）分析法中，第一个L的含义是从左往右，第二个L含义是每次进行最左推导，“1”的含义是向输入串中查看一个输入符号 。自顶向下语法分析方法会遇到的主要问题有左递归和回溯。_符号表的数据结构可以是 线性符号表、 树结构、散列表。一个字集是正规的，当且仅当它可由 DFA（NFA）所识别。假定G是一个文法，S是它的开始符号，如果S*a，则称a 是一个句型，仅含终结符号的句型是一个句子。文法G所产生的句子的全体是一个语言，将它记为L（G）。乔姆斯基定义的四种形式语言文法分别为： 0型文法（又称短语结构 文法）、1型文法（又称上下文有关文法）、2型文法（又称上下文无关 文法）、3型文法（又称正则文法）。自顶向下语法分析方法的基本思想是: 从识别符号出发,利用文法的规则不断建立 直接推导推导，试图构造一个推导序列，最终由它推导岀与输入符号串 的符号串。编译程序的工作过程一般可以划分为 _词法分析_、_语法分析_、_语义分析、_中间代码生成、代码优化等几个基本阶段，同时还会伴有 表格处理 和出错处理。文法G产生的所有句子的全体是该文法描述的语言。来自中间代码的代码生成涉及了两个标准技术：宏扩展和静态模 _宏扩展_涉及到

用一系列等效 的目标代码指令代替每一种中间代码指令。4•为文法的每一个规则配备的计算属性的计算规则，称为 语义规则。1•中间代码有逆波兰式 、三元式样、四元式、树形表示等形式，生成中间代码主要是为了使代码优化及目标程序便于移植 。（6分）。文法G产生的句子的全体是该文法描述的语言（2分）。在一个基本块内，可实行3种优化方法，即合并已知量、删除无用赋值 、删除多余运算。确定的有穷自动机是一个五 ，通常表示为 M（Q,刀，t,qo,F） 。活前缀是指规范句型的一个前缀，这种前缀不含句柄之后的任何符号。编译程序的工作过程一般可以划分为词法分析_、_语法分析_、一语义分析、_中间代码生成、_代码优化_等几个基本阶段，同时还会伴有 和出错处理（6分）。在目标代码生成阶段，符号 的依据。（2分）。符号表的数据结构可以是无序符号表、有序符号表 、栈式符号表 。4•词法分析阶段的错误主要是 单词拼写错误，可通过最小距离匹配的办法纠正错误。5.在大部分现有编译中采用的方案主要有两种： 动态 分配方案和_静态 分配方案。编译程序工作过程中，第一段输入是 源程序，最后阶段的输出为 目标 程序。若二个正规式所表示的正规集相同，则认为二者是等价的（ 2分）。符号表中名字的有关信息在 词法分析和语法语义分析过程中陆续填入。自顶向下语法分析方法的基本思想是：从识别符号出发，利用文法的规则不断建立直接推导，试图构造一个推导序列，最终由它推导出与输入符号串 的符号串。堆式动态分配策略允许用户动态的 申请和释放存储空间存储。。语法树代表推导过程，分析树代表归约过程。在优化中，可把循环中的不变运算提到循环外面去，这种方法称为 代码外提。1最左推导是指每次都对句型中的 最左 非终结符进行扩展。确定有限自动机DFA是NFA 的一个特例。（2分）。TOC\o"1-5"\h\z自顶向下语法分析方法的基本思想是: 从识别符号岀发,利用文法的规则不断建立 直接推导，试图构造一个推导序列，最终由它推导出与输入符号串 的符号串。确定的有穷自动机是一个 五元组，通常表示为 M（Q，刀，t,qo,F） 。一个字集是正规的，当且仅当它可由 DFA（NFA） 所识别。文法中的终结符和非终结符的交集是空集 。词法分析器交给语法分析器的文法符号一定是终结符 ，它一定只出现在产生式的右 部。7目标程序运行的动态分配策略中，含有栈式 和堆式分配策略。自底向上语法分析方法的基本思想是：从待输入的符号串开始，利用文法的规则步步向上进行归约，试图 归约 到文法的 识别符号。若源程序使用高级语言编写的，目标程序是 机器语言程序 ，则其翻译程序称为编译程序（2分）。编译程序是指将源程序程序翻译成目标程序的程序。自顶向下语法分析方法的基本思想是: 从识别符号出发,利用文法的规则不断建立直—接推导推导，试图构造一个推导序列，最终由它推导出与输入符号串 的符号串。编译过程通常可分为5个阶段，分别是词法分析、语法分析、 语义分析、代码优化和目标代码生成。优化就是对程序进行各种等价变换，使之能生成更有效的目标代码。 -自下而上分析法采用 移进、归约、错误处理、 接受等四种操作。采用自上而下语法分析时，必须消除文法的左递归（ 2分）。已知文法G[E]:iT|E+T|E-T F|T*F|T/F （E）|i该文法的开始符号是_L，终结符号集合VT是+、-、*、/、（、）、i，非终结符号集合Vn是E、T、F。

具有独立语扫描器的任务是从左到右一个一个地对源程序进行扫描，产生一个一个的法意义的单词。具有独立语优化就是对程序进行各种 等价变换，使之能生成更有效的 目标代码。A^a・称为归约项目；对文法开始符S'fa・为接受项目；若 a为终结符，则称ATa・aB为移进项目;若B为非终结符，则称A^a・aB为待约项目。三、简答题。(30分)1•什么是算符优先文法给出一个非教材上提供的算符优先文法的例子， 并给出算符优先表(6分)设文法G，如果它的产生式右部不包含相邻非终结符号， 则称文法G为算符文法，如果算符文法的终结符号集中任意两个符号之间至多存在一种优先关系， 则称该算符文法为算符优先文法。例如：E->E+T|TT->T*F|FF->(E)|i+*()i+><<><*>><><(<<<=<)>>>i>>>2•设有文法G[S]: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))编译程序的实现应考虑的问题有那些( 4分)编译程序的实现 应考虑：开发周期、目标程序的效率、可移植性、可调试性、可维护性、可扩充性等。4•什么是二义性文法请用例说明文法 G[E]：Ei|(E)|EAE A+|-|*|/是二义性文法。(6分)一个文法如果它的一个句子有两棵或两棵以上的语法树， 则称该句子具有二义性， 如果一个文法含有二义性的句子，则该文法是二义性文法。如句子：i+i+i5•在编译过程中为什么要建立符号表简述符号表的组织，即它一般分成几部分，含有那些域(6分)在编译过程中，始终涉及到对一些语法符号的处理， 需要用到这些语法符号的相关属性。

必须使用一些表格保存这些语法成分为了在需要的时候能找到这些语法成分及其相关属性，及其属性，这些表格就是符号表。必须使用一些表格保存这些语法成分符号表应包括语法符号的名字和相关属性， 不同语法符号在符号表中存放的信息不同。符号表的条目一般由两部分组成，即名字栏和信息栏。符号表域包括标识符名、其他信息、地址等。对名字栏，为节省空间，可另外设立一个存放标识符的字符数组。对信息栏中的类型等信息可以用数值或向量来表示，以节省空间1..设有文法G[E]:T|E+T F|T*F Ft（E）|i请给出句型（T*F+i）的最右推导及画出语法树。 （5分）最右推导： EtTtFt（E）t（e+T）t（e+F）t（e+i）t（t+i）t（t*F+i）EITF(E)E+TF(E)E+TTzT*FTOC\o"1-5"\h\z2对于上题，消除左递归和回溯，给出递归下降算法。 （6分）3•对于第1小题，给出句型（T*F+i）的短语、简单短语及句柄。 （5分）短语：（T*F+i）,T*F+i,T*F,i素短语：T*F,i适合采用静态存储分配的程序设计语言应有哪些限制（ 6分）数据实体所需空间在编译时能确定运行时每个数据对象只能有一个实例数组的上下界是常量过程调用不允许递归不能动态建立数据实体5•分离连表法是如何解决冲突的如杂凑表的尺寸是 5,有4个变量，x,y,temp,z,其中y和temp的杂凑值相等，请给出分离链接的杂凑表。 （8）1•设有文法G[S]:SaAcB|BdAAaB|cBbScA|b请给出句子acabcbbdcc的最左推导及语法树。（6分）s->aAcB->aAaBcB->aCaBcB->acabcB->acabcbScA->acabcbBCCA->acabcbbdcc2•判断上题是否是算符优先文法如是，请给出算符优先关系表。 （7分）是算符优先关系。因为产生式右部不包含相邻非终结符号firstvt(s)={a,b,d}lastvt(s)={a,b,c,d}firstvt(s)={a,c}lastvt(s)={a,b,c}firstvt(s)={b}lastvt(s)={a,b,c}abcda><=>b>>=>c<<>d>3•对于第1小题给定的文法，句型aAaBScAcB的短语、简单短语及句柄是什么( 6分)SaACBAaBbscA短语：bScAAabScAaAabScAcB简单短语：bScA句柄：bScA4•什么是二义性文法请用例说明文法 G[E]:Ei(E)|EAEA+|-|*/是二义性文法。(6分)一个文法如果它的一个句子有两棵或两棵以上的语法树， 则称此句子具有二义性， 如果一个文法含有二义性的句子，则称此文法具有二义性。例：i+i+i5•符号表的作用是什么一般有哪几种结构( 5分)在编译过程中，始终涉及对一些语法符号的处理。 要用到这些符号的相关属性。符号表的作用就是保存这些成份及其相关属性，以便在用时能找到。无序符号表 有序符号表 栈符号表1、 简述自顶向下分析法。从识别符号出发，不断建立直接推导，试图构造一个推导序列，最终由它推导出与输入符号串相同的符号串。从语法树的角度看，自顶向下分析过程是以识别符号为根结点， 试图向下构造一棵语法树，使其末端结点符号串正好与输入符号串相同。2、 设有文法G[A]的产生式集为：AtBaC|CbBBtAc|cCtBb|b试消除G[A]的左递归。提示：不妨以A、B、C排序•先将A代入B中，然后消除B中左递归；再将A、B代入C中。再消除C中左递归。最后结果为:G[A]:AtBaC|CbB BtCbBcB'|cB' B'taCcB'|£CtcB'bC'|bC' CtbBcB'bC'l£3、写出表达式a+b*(c-d)+e/(c-d)*n的三元式序列或P代码表示。(_,c,d) ⑵(*,b,(1)) (3)(+,a,(2)) ⑷(_,c,d)⑸(/,e,(4)) (6)(*,n,(5)) (7)(+,(3),(6))4、什么样的文法是算符优先文法，请举个算符优先文法的例子。设文法G,如果它的产生式右部不包含相邻非终结符号， 则称文法G为算符文法，如果算符文法的终结符号集中任意两个符号之间至多存在一种优先关系， 则称该算符文法为算符优先文法。例如：E->E+T|TT->T*F|F F->(E)|i+*()i+><<><*>><><(<<<=<)>>>i>>>5、解释什么是归约我们称％丫賣接归约出aA3仅当Aty是一个产生式， 且a氏(VNUVT)*。归约过程就是从输入串开始，反复用产生式右部的符号替换成产生式左部符号，直至文法开始符。1、 DFA和NFA有何区别DFA和NFA的区别表现在三个方面。一是 NFA可有若干个开始状态，而 DFA仅有一个。二是DFA的映像M是从KX"到K,而的映象M是从KX"到K的子集，即映像M将产生个状态集合(可能为空集)，而不单个状态。三是NFA在没有扫描输入符号的情况下，也可以进行空移。2、 已知文法G为：S——aAcB|BdA——kAaB|cB-bScA|b写出句子acabcbbdcc得最左推导及语法树s->aAcB->aAaBcB->aCaBcB->acabcB->acabcbScA->acabcbBCCA->acabcbbdccCbB.'dCbB.'dbb3、写出表达式A=(x+y)*(c+d)+(x+y+c)的四元式序列或 P代码表示。⑴(+,x,y)⑵(+,c,d)⑶(*,(1),(2))⑷(+,x,y)⑸(+,(4),c)⑹(+,(3),(5))1、 语法分析的主要(功能)任务是什么有哪二种分析分方法语法分析的主要任务是对词法分析的输出结果 -----单词序列进行分析，识别合法的 语法单位。若给定的输入符号是该文法所产生的语言中的句子， 就给出它的语法树，否则就报告出错信息。自上而下语法分析和自下而上语法分析。2、 令文法G为Sta|&|(T)—T,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代码表示。(+,a,b) ⑷(+,(3),c)⑵(+,c,d) (5) (*,(2),(4))⑶(+,x,y) ⑹(+,(1),(5))4、什么是二义性文法请举例说明。 以上的语法树，则称此句子具有二义性，如一个文法如果它的一个句子有两棵或两棵 果一个文法含有二义性的句子，则称此文法具有二义性。例：Ei|(E)|EAE A+|-I*I/i+i+i5、在一个基本块内通常可实现哪些优化①合并已知量②删除公共子表达式 ③删除无用代码④复写传播4、什么是语法树满足下面4个条件的树称之为文法 G[S]的一棵语法树。每一终结均有一标记，此标记为 VNUVT中的一个符号；树的根结点以文法G[S]的开始符S标记；若一结点至少有一个直接后继，则此结点上的标记为 VN中的一个符号；若一个以A为标记的结点有K个直接后继，且按从左至右的顺序，这些结点的标记分别为Xi,X2,…必则A~Xi,X2,…必必然是G的一个产生式。5、在编译过程中为什么要建立符号表，简述符号表的组织，即它一般分成几部分，含有那些域在编译过程中，始终涉及到对一些语法符号的处理，需要用到这些语法符号的相关属性。为了在需要的时候能找到这些语法成分及其相关属性，必须使用一些表格保存这些语法成分及其属性，这些表格就是符号表。符号表应包括语法符号的名字和相关属性，不同语法符号在符号表中存放的信息不同。符号表的条目一般由两部分组成，即名字栏和信息栏。符号表域包括标识符名、其他信息、地址等。对名字栏，为节省空间，可另外设立一个存放标识符的字符数组。对信息栏中的类型等信息可以用数值或向量来表示，以节省空间对如下文法：G[S]：SabS|aaB|ad BbbB|b分别给出句子abaabbb和ad的句柄(6分)句子abaabbb的句柄是b;句子ad的句柄是ad什么是可规约活前缀举一例说明。 (6分)若活前缀是含句柄的活前缀，即有 a=a',nn是句柄，则活前缀 a为可归约活前缀。例Sa|bCd Ce则be为一个可归约活前缀3•写出表达式(a+b*c)/(a+b)—d的逆波兰表示及三元式序列或 P代码。(6分)(*,b,c)(+,a,(1))(+,a,b)(/,(2),(3))(-,(4),d)TOC\o"1-5"\h\z4•词法分析和语法分析都是对字符串进行识别，二者有何区别( 4分)在词法分析和语法分析中，都是对输入符号串进行识别。但词法分析的输入符号串是一个单词，而语法分析的输入符号串是一个句子或者说是一个程序。 为了讨论方便，我们都是用小写字母来表示终结符号，但一定要明白在词法分析中小写字母表示组成单词的字符， 而在语法分析中小写字母表示组成程序的的一个单词， 识别方式来说，词法分析和语法分析都是对输入符号串结构的识别， 但由于单词和程序的结构有所区别， 所以具体的识别方式不一样。5•已知文法G[S]为：StaF|(T) T,S|S判断该文法是否是算符优先文法如是，请给出算符优先关系表。 (8分)(1)FIRSTVT和LASTVTFIRSTVTLASTVTSa、A、(a、a、)T八a、A、(,、a、A、)(2)算符优先关系a()5A#a>>>(<<三<)>>><<>><A>>>#<<<1、 计算机执行用高级语言编写的程序有那些途径它们之间的主要区别是什么计算机执行用于高级语言编写的程序主要有两种途径：解释和编译。在解释方式下，翻译程序并不对高级语言进行彻底的翻译， 而是读入一条语句，就解释其含义并执行，然后再读入下一条语句，再执行。在编译方式下，翻译程序先对高级语言进行彻底的翻译并生成目标代码， 然后再对目标代码进行优化，即对源程序的处理是先翻译后执行。从速度上看，编译方式下，源程序的执行比解释方式下快，但在解释方式下，有利于程序的调试。2、 编译程序的实现途径有那些编译程序的实现途径可有：-手工构造：用机器语言、汇编语言或咼级程序设计语言书写。-自动构造工具：Lex,Yac。Lex,Yac(分别是词法和语法分析器的生成器。-移植方式：目标程序用中间语言-自展方式：用T型图表示3、文法G[E]为：EtE+T|T TtT*F|F Ft(E)|i试给出句型(E+F)*i的短语，简单(直接)短语,句柄和最左素短语。短语有：(E+F)*i,(E+F),E+F,F,i简单(直接)短语有：F,i句柄是：F 最左素短语是:E+F4、有人认为：“1型文法对规则的限制比2型文法对规则的限制要多一些”，这种说法对吗文法是严格按照规则的形式来分类的1型文法的规则是：+*xUy->xuyu€Vnu€Vx,y€V要求将U替换为u时，U的前后一定要有x和y。而2型文法的规则形式为U->u u€Vn u€V没有什么要求，似乎1型的规则限制要多一些。 但仔细看看1型规则中的条件x和y时，就不难发现当x和y为空时，正好是2型文法。从0型文法到3型文法，是依次增加对文法的限制，所以描述的语言集合越来越小。5、简述自底向上分析法。基本思想是：从待输入的符号串开始，利用文法的规则步步向上归约， 试图归约到文法的识别符号。从语法树的角度看，自底向上分析的过程是以输入符号串作为末端结点符号串， 向着根结点方向往上构造语法树，使识别符号正好是该语法树的根结点。 如果最终根结点是识别符号，则输入符号串被识别是相应语言的一个句子；否则不是。自底向上分析过程实际上是一个不断进行直接归约的过程。1、什么是规范推导每个句型都有规范推导吗规范推导就是最右推导每一个句子都有一个规范推导，而每一个句型则不一定都有规范推导，比如说采用非规范推导得到的句型。2、 已知文法G[E]:iET+|TjTF*|FiFa|a试证：FFaa*是文法的句型，指出该句型的短语、简单短语和句柄。该句型对应的语法树如下：该句型相对于E的短语有FFaa*；相对于T的短语有FFaa*,F;相对于F的短语有Fa；Faa；简单短语有F;Fa向柄为F.3、 写出表达式w+(a+b)*(c+d/(e-10)+8)的逆波兰表示及三元式序列。(+,a,b)(-,e,10)(/,d,(2))(+,c,(3))(+,(4),8)(*,(1),(5))(+,w,(6))4、何谓优化按所涉及的程序范围可分为哪几级优化所谓优化，一般是指为提高目标程序的质量而进行的各项工作，即对程序或中间代码进行各种等价变换，使得从变换后的程序出发，能生成更有效的目标代码。在源程序级在语义动作的设计上在中间代码级在目标代码级5、简述自顶向下分析法。从识别符号出发，不断建立直接推导，试图构造一个推导序列，最终由它推导出与输入符号串相同的符号串。从语法树角度看，自顶向下分析过程是以识别符号为根结点，试图向下构造一棵语法树，使其末端结点符号串正好与输入符号串相同。1、实现高级语言程序的途径有哪几种它们之间的区别计算机执行用于高级语言编写的程序主要有两种途径：解释和编译。在解释方式下，翻译程序并不对高级语言进行彻底的翻译，而是读入一条语句，就解释其含义并执行，然后再读入下一条语句，再执行。在编译方式下，翻译程序先对高级语言进行彻底的翻译并生成目标代码，然后再对目标代码进行优化，即对源程序的处理是先翻译后执行。从速度上看，编译方式下，源程序的执行比解释方式下快，但在解释方式下，有利于程序的调试。2、 文法G[S]为：S->Ac|aBA->abB->bc该文法是否为二义的为什么对于串abcS=>Ac=>abcS=>aB=>abc即存在两不同的最右推导所以，该文法是二义的。3、将文法G[S]改写为等价的G'[S],使G'[S]不含左递归和左公共因子。G[S]:StSAe|AeA^dAbA|dA|d文法G[S]改写为等价的不含左递归和左公共因子的 G'[S]为：StAeS'S'tAeS'|&AtdA'A'tAB|&BtbA|&4、 证明LL(1)文法是无二义性文法证明：LL(1)文法中任意两个产生式 Pi,Pj,(R,P具有相同的左部非终极符)Predict(Pi)nPredicjR为空设Pi：Afa2-aaRj：Afa1211aaml(A€Vn,a1aan,i1a2l-•(m1€VnUVt)因为Predict(Pi)nPredictfiP为空，因此Pi,Pj中的A经一步推导，最左的终极符肯定不同，因此，对于一个字符串，不可能有两种方法推导。5、 文法G[S]为：S->Ac|aB A->ab B->bc写出L(G[S])的全部元素S=>Ac=>abc或S=>aB=>abc所以L(G[S])={abc}1、给出算符优先文法的定义，算符优先表是否都存在对应的优先函数给出优先函数的定义。设有一不含&产生式的算符文法 G,如果对任意两个终结符对 a,b之间至多只有存|、-和次三种关系的一种成立，则称 G一个算符优先文法。算符优先关系表不一定存在对应的优先函数优先函数为文法字汇表中2、考虑文法G[T]:TfT*F|F FfFfP|P Pf(T)|i证明T*Pf(T*F)是该文法的一个句型，并指出直接短语和句柄。句型T*Pf(T*F)的语法树由图可知，T*Pf(T*F)是文法G[T]的一个句型。直接短语有两个，即P和T*F;句柄为P。3、文法G[S]为：SfSdT|T TfT<G|G Gf(S)|a试给出句型(SdG)<a的短语、简单(直接)短语、句柄和最左素短语。句型(SdG)<a的 短语：(SdG)<a、(SdG) 、SdG、G、a简单(直接)短语：G、a 句柄：G 最左素短语：SdG4、 目标代码有哪几种形式生成目标代码时通常应考虑哪几个问题三种形式：可立刻执行的机器语言代码；汇编语言程序；待装配的机器语言代码模块考虑的问题包括：每一个语法成分的语义；目标代码中需要哪些信息，怎样截取这些信息。5、 符号表的作用是什么符号表的查找的整理技术有哪几种作用：登记源程序中出现的各种名字及其信息，以及编译各阶段的进展状况。主要技术：线性表，对折查找与二叉树，杂凑技术。1、 解释什么是推导我们称aAB直接推出ocy3,即aA3TayB,仅当Af丫是一个产生式，且a、(VnUVt)*。如果a1二a2二…an,则我们称这个序列是从a 1至a2的一个推导。若存在一个从a1an的推导，则称a1可推导出an。推导是归约的逆过程。2、 将文法G[S]改写为等价的G'[S]，使G'[S]不含左递归和左公共因子。G[S]:SfbSAe|bA AfAb|d文法G[S]改写为等价的不含左递归和左公共因子的 G'[S]为：44bB BtSAe|A AtdA' A'tbA'| £3、 写出Pascal或C语言的字母表。pascal语言的字母表是：{03、 写出Pascal或C语言的字母表。pascal语言的字母表是：{0,1,……,9}U{a,……,z}U{A,……,Z}U{+,-,*,/,,T,,,_,=,<,>,',",Enter,Space,Tab}C语言的字母表是：_,0……9,a……z,A……乙+,-,*,/,\,%,(,), &,I，!,=,#,{,},'，”,Space,Tab4、 有文法G[Z]:ZtaZbZ|aZ|a该文法是否是二义的，试证明之。(,),[,],;,:,<,>，Enter.画出二棵不同的语法树，因而是二义的。1)分析法对文法有哪些要求G的每个非终结符A的任何两个不同产生式5、LL(A->a|A->a|3,First(a)AFirst(3)=◎若3=*>£,则First(a)Follow(A)=①1、 解释编译程序中“遍”的概念，何谓“单遍扫描”遍指编译程序对源程序或中间代码程序从头到尾扫描一次对于源程序或中间代码程序，从头到尾扫描一次并完成所规定的工作称为一遍。单遍扫描是编译程序的一种极端情形。 在这种情形下，整个编译程序同时驻留在内存中， 编译程序的各部门之间采用“调用转接”方式连接在一起。2、设有文法G[S]为： 4a|b|(A) AtSdA|S给出句型(SdSdS的短语、简单短语、句柄、素短语和最左素短语。短语：S,SdS,SdSdS(SdSdS 简单短语(即直接短语)：S句柄(即最左直接短语)：S素短语：SdSi>它同时也是该句型的最左素短语。3、写出表达式A+B*(C-D)+E/(C-D)*N的逆波兰表示及三元式序列。⑴(_,CQ ⑺(+,(3),(6))⑵(*，B，(1))⑶(+，A,(2))(_,C,D)(/,E,(4))(*,N,(5))4、画出编译程序的总体结构图。编译程序的总框图 见下图5、给出0,1,2,3型文法的定义。乔姆斯基(Chomsky)把文法分成类型，即0型，1型，2型和3型，0型强于1型，1型强于2型，2型强于3型。如果它的每个产生式a->3的结构是a€(VnUVt)*且至少含有一个非终结符 ，而(VnUVt)*，我们说G=(Vt,Vn,S,3)是一个0型文法。0型文法也称短语文法。一个非常重要的理论结果是， 0型文法的能力相当于图灵(Tunring)机。或者说，任何0型语言都是递归可枚举的；反之，递归可枚举集必定是一个 0型语言。如果把0型文法分别加上以下的第 i条限制，则我们就得i型文法为：G的任何产生式a->3均满足|a|<=|3；仅仅S->£例外，但S不得出现在任何产生式的右部。G的任何产生式为A->3,A€Vn,3€(VnUVt)*G的任何产生式为A->aB或A->a，其中A,B€Vn1型文法也称上下文有关文法。这种文法意味着，对非终结符进行替换时务必考虑上下文，而且，一般不允许替换成空串。2型文法对非终结符进行替换时无须考虑上下文，3型文法也称线性文法。四、词法分析一一构造确定性有穷自动机。为以下字符集编写正规表达式， 并构造其Thompson结构图以及与之等价的最简 DFA(写出详细的具体过程)：在字母表｛0,1｝上的且不以0开头但以11结尾的所有字符串。(15分)正规表达式：11|1(0|1)*11最简DFA五、语法分析 自顶向下分析法。已知文法G:ETE E'+E| £ TFT' T'| £FPF F'*F'I £ P(E)|A|a |b求文法G中每个非终结符的 First集和Follow集。证明该文法G是LL(1文法。构造文法G的预测分析表。(20分)First(E)=First(T)=First(F)=First(P)+{(,A,a,b)First(T)={(,A,a,b,&)First(E)={+,£}First(F')={*, £}Follow(P)={(,A,a,b,#,),+}Follow(F)={(,A,a,b,#,),+}Follow(F)={(,A,a,b,#,),+}Follow(E)={#,}}Follow(E'={#,}}Follow(T)={#,),+}Follow(T'={#,},+}判定该文法是否是 LL(1)文法的充要条件是对于 G的每个非终结符A的任何两个不同产生式A->a| 有下述条件成立：First(a)AFirst(3)=◎若3=*>£,则First(a)Follow(A)=①显然，(1)所求的First集合和Follow集合满足要求，因此该文法为 LL(1)文法。+*()abA#EE->TEE->TE'E->TEE->TEE'E'->+EE'->£E->£Tt->ftT->FTT->FT'T->FT'T'T->£T'->TT'->£T'->TT->TT'->TT->£FF->PFF->PF'F->PFF->PFF'F'->£F'->*F'F'->£F'->£F'->£F'->£F'->£F->£PP->(E)P->aP->bP->a六、语句翻译把语句Whilea>0Vbv0doBeginX：=X+1;ifa>0thena:=a—1elseb：=b+1End;翻译成四元式序列。 (10分)100(j>,a,0,104)101(j,亠102)102(j<,b,0,104)103(j,_,_,111)104(+,x,1,x)105(j>,a,0,107)106(j,_,_,109)跳过else后的语句107(-,a,1,a)108(j,_,_,110)109(+,b,1,b)110(j,_,_,100) while循环111四、词法分析一一确定性有穷自动机为以下字符集编写正规表达式，并构造与之等价的最简 DFA（写出详细的具体过程）在字母表｛a,b｝上的且以a开头且以bb结尾的所有字符串。（15分）正规表达式： a（a|b）*bb最简DFA五、语法分析 自底向上分析法已知文法G：EE+TETTT*FTFF(E)Fi求文法G中每个非终结符的First集和Follow集构造文法G的SLR(1预测分析表。(20分)首先构造增广文法：SE EE+TET TT*FTF F(E)FiFirst(S)=First(E)=First(T)=First(F)={(,l)Follow(S)={#}Follow(E)={+,#,}}Follow(T)={+,},#,*} Follow(F)={+,},#,*}状态ActionGotoi+*()#ETF0S5S41231S6Acc2r2Sr2r23r4r4r444S4823 5 r6r66937S5 108S6S119r1St r1r110r3r3r3r311r5r5r5r5注：识别可归前缀的 DFA共12项。六、目标代码生成把下面程序段：Whilea>0Vbv0doBeginX：=X+1;ifa>0thena:=a—1elseb：=b+1End;翻译成四元式序列。 (10分)1OO(j>,a,O,1O4)101(j,_,_,102)102(j<,b,0,104)103(j,_,_,111)104(+,x,1,x)105(j>,a,0,107)106(j,_,_,109) 跳过else后的语句107(-,a,1,a)108(j,_,_,110)109(+,b,1,b)110(j,_,_,100) while循环111四、词法分析一一确定性有穷自动机为以下字符集编写正规表达式，并构造与之等价的最简 DFA(写出详细的具体过程)在字母表｛a,b｝上的包含偶数个a且含有任意数目b的所有字符串。(15分)(b*ab*ab*)*状态ActionGOTOabdef$SRT0S311acc2r2:S3r2r253S6S424r4r4r4r45S109677S88r3—r3r3r39r1r1r110r6S6S4r6r61111S1212r5r5r5五、语法分析 自底向上分析法已知文法G: S' SbRSTSbRRdSaReTfRaTf求文法G中每个非终结符的 First集和Follow集。构造文法G的SLR(1预测分析表。(20分)frist(s)={b}follow(s')={$} frist(s)={b}follow(s)={f,a,$}frist(R)={d,e}follow(R)={a,b,f,$}frist(T)={t}follow(T)={a,f,#}六、目标代码生成把下面程序段：WhileA<BAC>DdoWhileMVB<NdoifM=NthenX：=X+1；ElseX:=X-1;翻译成四元式序列或P代码。100(j<,A,B,102)101(j,-,-,115)102(j>,C,D,104)103(j,-,-,115)104(jND,M,-,108)105(j,-,-,106)106(j<,B,N,108)107(j,-,-,1114)108(j=,M,N,110)109(j,-,-,112)110(+,X,1,X)111(j,-,-,104)112(-,X,1,X)113(j,-,-,114)114(j,-,-,100) 115四、为以下字符集编写正规表达式， 并构造其Thompson结构图以及与之等价的最简 DFA(写出详细的具体过程）：在字母表｛0,1｝上的包含偶数个0且含有任意数目1的所有字符串。（15分）正规表达式： （1*01*01*）*最简DFAabc#SLR1S6S2532Acc3R24R4R45S7R56「S3s8P97S12S1311108R5R59R3R310R111R512S12S13111413R414R3五、 已知文法G：SLaR|RLbR|cRL判断该文法是否为LR(1文法。若是则构造文法G的LR(1项目集规范族。3)若是则构造文法G的LR(1预测分析表。 (15分)因为状态机中没有冲突，所以是 LR(1)文法。LR(1)分析表如下：(1)SLaR (2)SR (3)LbR⑷Lc (5)RL六、 把下面程序段：forl:=1setp1untilNdowhileA<BifC>Dthenx:=CelseX:=D翻译成四元式序列。(写上注释， 15分)100(:=,1_,i)101(j,_,_,103)102(+,I,1,I)103(j<,l,N,105)104(j,_,_,114)105(j<,A,B,107)106(j,_,_,113)107(j>,C,D,109)108(j,_,_,111)1：1：109(:=,C,_x)110(j,亠112)111(:=,D,_,x)112(j,_,_,105)113(j,_,_,102)114,四、构造一个DFA,它接受刀={a,b}上的所有满足下述条件的字符串，其条件是:字符串中的每个b后面都有a直接跟在右边。要求：(1)写出正则表达式；(2)由NFA构造DFA;(3)D正则表达式：)FA状态最小化(写出详细的具体过程)( 15分)z***(abaa)最简DFA四、构造一个DFA它接受刀={0,1}上的所有满足下述条件的字符串，其条件是:字符串中的每个0后面都有1直接跟在右边。要求:(1)写出正则表达式;(2)由NFA构造DFA;(3)DFA犬态最小化(写出详细的具体过程)( 15分)正则表达式：(1*011正则表达式：(1*011*)*1五、考虑以下的文法:4A4B4A4BAtaAbBtaBbBtd试构造相应的LR(0)项目集规范族及相应的分析表。解答:Io：出〜*S£亠*BA•AB-*•aBbA-*-*aAb•dA-*-*cII-GO(4S)-CLOSURE((Sd-*S+h=GOCl0,A>=CLOSURE(S-*A*)sh：S^*•As1尸GC%B)=C4URE{—E，},h；S^B•I尸GO(Io>a)=CLOSURE((A-*a*Ab, *Bb}),U：A-*-a*Ab* B~*a*Bb?A—*aAJbr 沪•aBbrA“•u， B-**d；l产GOCl”c)=CLOSURE({A^c•}),I5:A^c•1Ie-GO(I沪d)^CLOSUREC{B^ci*}hS：Efd*b=GO<IoA)=CLOSURE{ •b}> •b}I9=GO(I,B)=CLOSURE(B^aB*b})={ b)GO(I,a)=【斗，GO(Ioc)二bGO(I*sd)ifa>0thena：=a—1elsels-GO(I“b)=CLOSURE{A-^aAb•})=(A-^aAb*},Iio=GO<1^b>=C*LOSUE<E{B-aBloifa>0thena：=a—1elseACTIONGOTOabCdSAB0s<迅s61131acc2nT1nIIri3口耳Ta辽51■+丸6坏命78巧与9Sio10乌巧六、把语句WhileaWhilea>0Vbv0doBeginX：=X+1；End;End;翻译成四元式序列。(15分)DFA(写出详细的具体过程)：0或两个连续的DFA(写出详细的具体过程)：0或两个连续的1o(15分)(0|1)*1,0100(j>,a,0,102)101(j,亠104)102(-,a,1,a)103(j,_,_,110)104(j>,a,0,108)105(j,_,_,106)106(j<,b,0,108)107(j,_,_,110)108(+,x,1,x)109(j,_,_,104)while循环110四、词法分析一一确定性有穷自动机为以下字符集编写正规表达式，并构造与之等价的最简在字母表{0,1}上的串，串中至少要包含两个连续的五、语法分析 自顶向下分析法 (20分)说明如下文法是否是 LL(1)文法，若不是，将其转换为 LL(1)文法。最后给出该文法的LL(1)分析表。G[A]：ABeBBb|a文法中有左递归，不是 LL(1文法。转换为G':ABeBaB' B'bB'|入Predict(ABe)={a}Predict(BaB')={a}Predict(BbB\={b}Predict(B'入)={e}LL(1)分析表：abeABeBaB'B'bB'入六、构造运行时环境有如下一段C语言程序：(计算两个非负整数的最大公约数 )#inelude<>intx,y;intged(intu,intv){if(v==0)returnu;elsereturnged(v,u%v)}main(){scanf(%d%d”,&x,&y);printf(%d\n",gcd(x,y));return0;}当输入x,y分别为20,10时，最后一次调用 gcd()时的运行时环境。(10分)gdc当输入20和10时，main就初始化调用gdc(20，10)。这个调用导致了另一个递归调用(10，0)，它将返回值10。运行时环境示意图如下：gdc沽动记录吗卜金局■/静态区城第二次渥用輕計沽动记录吗卜金局■/静态区城第二次渥用輕計时旳活站记录abbbaaa五、已知文法G:（15分）ETET'T|£E'+E|£FPF'TFT'F'*F'|£P(E)|A|a|b求文法G中每个非终结符的First集和Follow集。证明该文法G是LL(1)文法。构造文法G的预测分析表。(15分)2)First(E)=First(T)=First(F)=First(P)+{(],a,b)First(T'={(】,a,b,&)First(E'={+,£}First(F')={*, £}Follow(P)={(,A,a,b,#,),+}Follow(F'={(,A,a,b,#,),+}Follow(F)={(,A,a,b,#,),+}Follow(E)={#,}}Follow(E'={#,}}Follow(T)={#,),+}Follow(T'={#,},+}2)判定该文法是否是 LL(1)文法的充要条件是对于 G的每个非终结符A的任何两个不同产生式A->a| 有下述条件成立：First(a)AFirst(3)=◎若3=*>£,则First(a)Follow(A)=①显然，(1)所求的First集合和Follow集合满足要求，因此该文法为 LL(1)文法。+*()abA#EE->TEE->TE'E->TEE->TEE，「E，->+EE'->£E->£Tt->ftT->FTT->FT'T->FT'T，「T->£T'->TT'->£T'->TT->TT'->TT->£FF->PFF->PFF->PFF->PFF，F'->£F'->*F'F'->£F'->£F'->£F->£F->£F->£PP->(E)P->aP->bP->A六、把语句ifa>0thenWhile a>0Vbv0doBeginX：=X+1;End;elseb：=b+1翻译成四元式序列。 (15分)100(j>,a,0,102)101(j,_,_,108)102(j>,a,0,106)103(j,_,_,104)104(j<,b,0,106)105(j,_,_,108)106(+,x,1,x)107(j,_,_,102) while循环108(j,_,_,110)109(+,b,1,b)110四、词法分析一一确定性有穷自动机为以下字符集编写正规表达式，并构造与之等价的最简 DFA(写出详细的具体过程)：在字母表{0,1}上的串，串中至少要包含两个连续的 0或两个连续的1。(15分)(0|1)*(00|11)(0|1)*0 00 01,1,0五、语法分析 自顶向下分析法 (20分)说明如下文法是否是 LL(1)文法，若不是，将其转换为LL(1)文法。最后给出该文法的LL(1)分析表。G[A]：ABeBBb|a文法中有左递归，不是 LL(1文法。转换为G':ABeBaB' B'bB'|入Predict(ABe)={a}Predict(BaB')={a}Predict(BbB\={b}Predict(B'入)={e}LL(1)分析表：abeABeBaB'B'bB'入六、构造运行时环境有如下一段C语言程序：(计算两个非负整数的最大公约数 )#include<>intx,y;intgcd(intu,intv){if(v==0)returnu;elsereturngcd(v,u%v)}main(){scanf(%d%d”,&x,&y);printf(%d\n",gcd(x,y));return0;}当输入x,y分别为20,10时，最后一次调用gcd()时的运行时环境。(10分)当输入20和10时，main就初始化调用gdc(20,10)。这个调用导致了另一个递归调用 gdc(10,0),它将返回值10。运行时环境示意图如下：v>io—込制脏返冋地址Ui10v>io—込制脏返冋地址Ui10控制融返阿地址全/静态区域main的活■动记录第一次JI•用feed时的活动记录却二次澜用輕讨时的活站记录性牛长方向四、构造正规式1(011)*101相应的DFA(15分)先构造NFADFA五、判断下面文法是否为D^TLTtint|real先构造NFADFA五、判断下面文法是否为D^TLTtint|realLL(1)文法,右是，请构造相应的LL(1)分析表。(15分)LtidRFT,idR| £FIRST(D)FIRST(D)=FIRST(T)={int,real}FOLLOW(D)=FOLLOW(L)={#}FOLLOW(T)={id}FOLLOW(R)={#}FIRST集合，填分析表时要计算一个产生式右部aFOLLOW(T)={id}FOLLOW(R)={#}FIRST集合，填分析表时要计算一个产生式右部a的FIRSTa)有了上面每个非终结符的就不是件难事了。填表时唯一要小心的时，&是产生式RT&右部的一个开始符号，而#在FOLLOW(R)中,所以RT&填在输入符号#的栏目中。郭终结符-輪入符号intrealidTDD—^TLkTLTTTjntT—*realLL^ldRRRfidR六、把语句

a:=1;whilea<=10dobeginifa<>bthenb:=b+2;elsea:=a+1;end;翻译成四元式序列。(15分)1OO(j:=,1,_,a)101(j<=,a,10,103)102(j,_,_,109)103(j<>,a,b,105)104(j,亠107)105(+,b,2,b)106(j,_,_,108)107(+,a,1,a)108(j,_,_,101)while循环109四、已知： (15分)正规式(1)((a|b)*|aa)*b正规式(2)(a|b)*b试用有限自动机的等价性证明正规式( 1)和(2)是等价的。两者化简后的DFA都为：G(S):(15分)SA ABA| £BaB|bG(S):(15分)SA ABA| £BaB|b(1)证明它是LR(1文法;(2)构造它的LR(1)分析表;(3)给出输入符号串abab的分析过程。1)拓广文法G':(0)S'S(1)SA (2)ABA⑶A£ ⑷BaB(5)BbFIRST(A)={ £,a,b}FIRST(B)={a,b}构造的DFA如下：由项目集规范族看出，不存在冲突动作。•••该文法是LR⑴文法。⑵LR(1分析表状态ActionGotoaB#SAB0S4S5r31231acc2r13S4S5r3634S4S575r5r5r56r27r4r4r4⑶输入串abab的分析过程为:步骤状态栈符号栈当前字符剩余字符串动作⑴0#abab#移进(2)04#abab#移进⑶045#abab#归约Bb(4)047#aBab#归约BaB(5)03#Bab#移进(6)034#Bab#移进(7)0345#Bab#归约Bb(8)0347#BaB#归约BaB(9)033#BB#归约As(10)0336#BBA#归约ABA

(11)036#BA#归约ABA(12)02#A#归约SA(13)01#S#acc六、把语句Whilea>0Vbv0doBeginX：=X+1;ifa>0thena: