编译原理 试题及答案.docx

课程测试试题(04A卷)I、命题院(部)：数学与计算机科学学院n、课程名称：编译原理 n、I测试学期：20222022学年度第1学期IV、测试对象：数计、国交学院计科专业2004级1、2、国交班V、问卷页数(A4)：3页VI、答卷页数(A4)：4人VIL考试方式：闭卷(开卷、闭卷或者课程小论文，请填写清晰)VIIL问卷内容：(请老师在出题时安排紧凑，填空题象征性的留出一点空格， 学生将所有的答案做在答题纸上的规定位置，并写清晰大题、小题的题号)一、填空题(共3()分，3()个空，每空1分)1、典型高级程序设计语言编译系统的工作过程普通分为六个阶段，即词法分析、语法 分析、语义分析、中间代码生成、目标代码生成。编译阶段的两种组合方式是 组合法和按遍组合法，这两种组合方式的主要参考因素都是的特征。2、Chomsky将文法按其所表示语言的表达能力，由高往低分为四类：0型，1型，2型，3型文法。其中，2型文法也称,它的所有规则a一储份茜足：ae,阵(VUV)* N丁 且,仅当忏时例外。3、现代编译系统多采用 方法，即在语法分析过程中根据各个规则所相联的 或 者所对应的语义子程序进行翻译的办法。该方法使用 为工具来说明程序设计语言的语义。4、构造与NFAM等价的正规文法G的方法如下：(1)对转换函数f(A, a)=B或者f(A, 8)=B,改成形如 或者 的产生式；(2)对可识别终态Z,增加一个产生式：o5、代码生成要考虑的主要问题：充分利用 的问题、选择 的问题、选择 的问题。6、设有穷自动机M=(K, , f, S, Z),若当M为时，满足zOKS, a且)zO£Z,或者当M为 时，满足RS, ahPez,则称符号串可被M所。7、符号表中每一项对应一个多元组。符号表项的组织可分为组织、组织、组 织等。8、对于A £V 义 A 的后续符号集：FOLLOy(A)=a|S= >uAp, aev,且 , u£V1 0£V+;若,则#£田11/)¥c)。也可以定义为：FOLLOW(A)=a|S= *>.Aa .,a evjo 若有,则规定# £FOLLOW(A)。9、基本块的定义：一个基本块是指程序中一个 执行的语句序列，其中惟独一个入口和一个出口。入口是程序第一个语句或者转移语句的目标语句，或者转移语句的后继第一 个语句。出口是程序 或者转移语句。在基本块范围内的优化称为 o10、预测分析器由预测分析表、先进后出栈(用来存放分析过程的语法符号)和 三部份组成。其中预测分析表是一个二维矩阵，其形式为MA, a,其中A£ V,日£丫或者#。 若有产生式A-a,使得,则将A-母真入MA, a中。(书写时，通常省略规则左部， 只填一(X。)对所有的M-A, a标记为出错。二、简述题(共20分，4个小题，每小题5分)1、简述将NFA转换为最小化DFA的步骤。2、简述静态存储分配、栈式存储分配和堆式存储分配的特点和主要用途。3、以表达式a:二b*(-c)+b/(-d)为例，简述常用的三种中间代码表示形式。4、简述判别文法G是否为LL(1)文法的步骤和将一个非LL(1)文法转换为LL(1)文法的 方法。三、应用题(共50分)1、有文法GS：(12分)5) B bBd6)B->b5、构造GS的LR(O)项目集规范族DFA,并据此判断GS是否为LR(O)文法。 (6分)6、进一步判断GS是否为SLR文法，并给出对应的SLR分析表。(6分)3、给出输入串bbd#的SLR分析过程。(4分)4、判断GS是否为LR(1)文法和LALR(l)文法。(2分)编译原理课程测试试卷评分标准（数计学院04计科A卷）一、填空题参考答案（共30分，30个空，每空1分）题号1234参考 答案代码优化、先后端、 源语言与目标机器上下文无关文法、V、| N加二IM语法制导翻译、语 义动作、属性文法AaB、A-B、Z>£题号5678参考 答案寄存器、计算机指令 系统、计算次序NFA、DFA、接受（识别 ）线性、排序、散列F1RS1S、)户>£、 S=*>.A题号91()参考 答案顺序、最后一个语句、 局部优化预测分析程序、NFTPEA 一2、沿有值说明：各个答案可有不同表达方式，只要意思相同即可。二、简述题参考答案（共20分，4个小题，每小题5分）1、第一步：将NFA确定化。用造表法将NFA确定化过程如下：（0）表的第0行和第0列作标识行列的值。将占closure（作D为表中第1行第1列。假定=al, a2,an, 设第i行第一列已确定状态集为I,则置该行第i列为la, i 如lai未曾经在任何行第一列浮现过，则将lai加入下一空行i+1的第一列，并在第（）列标记为 Ti+lo（3）反复重复第步，直至无新状态浮现为止。重新命名新状态。（3分）第二步：将DFA最小化。DFA最小化具体过程：用子集分割法将不含多余状态的DFA 分成一些不相交的子集，使得任何两个不同的子集中的状态都是可区别的，而相同子集中状 态是等价的。分割时，首先将DFA状态分成终态子集和非终态子集，再根据输出弧所达到 状态的性质逐步细分。（2分）2、（1）静态存储分配的特点：编译时刻确定存储位置；访问效率高。主要用途：子程 序的目标代码段、全局数据目标（全局变量）。（2分）（2）栈（Stack）式存储分配的特点：嵌套调用次序、先进后出、生存期限于本次调用、 自动释放。用途：过程的局部环境、活动记录。（1分）（3）堆（Heap）式存储分配的特点：将内存空间分为若干块，根据用户要求分配；无法 满足时，调用无用单元采集程序将被释放的块采集起来重新分配。主要用途：用于动态数 据结构：存储空间的动态分配和释放。（2分）3、（1）逆波兰式：abc-*bd-/+:=。（ 1 分）（2）三元式:（*,b,）"d,_）竺为,）（+,，）（:=，,a）。（2分）（3）四元式:G,d,_,t3）®（/,b,t3 ,t4）（+,t2,t4,t5） （:= ,t5 ,_,a）o （2 分）4、（1）判别步骤：先画出各非终结符能否推导出£的情况表；然后，用定义法或者关系 图法计算FIRST、FOLLOW集；再计算各规则的SELECT集；最后，根据同一个左部的规 则其SELECT集是否相交来判断给定文法是否为LL（1）文法。（3分）（2）将非LL（1）文法转换成LL（1）文法的两种主要方法：提取左公共因子、消除左递 归。（2分）三、应用题参考答案（共50分）1、（ 1 ）证明（3分）：因为存在推导序列 S=>aAS=>aSbAS=>aabAS=>aabbaS=>aabbaa , 即有S=*>aabbaa成立，所以，是文法的一个句子。（2）语法树（3分）：S /1 a1AsS bl A a4I /（3）句型分析（6分）：将句型改点% ala2P示2a篇，则：该句型相对于S的短语： ala2blb2a3a4Ha4；相对于A的短语：a2blb2a3和b2a3；对于S>a的直接短语：a2, a4；相对于A-ba的直接短语：b2a3；句柄：a2。2、计算GE*1的FIRSTVT和LASTVT集如下：（5分）构造GE的算符优先关系表如下：（4分）< + + + 才 * * +平才才才平方平,才才才才干才卡* 才=、力才才才=才由上表可知G旧是算符优先文法（1分）。输入串w=i+i#的算符优先分析过程如下：（5分）步骤I栈 I关系 多除虾k 祠作1 #2 #i3 #P4 #P+§#P+i6 #P+P7 #E栈约栈栈约约功入归入入!11归成3、（1）基本块的DAG图如下：（3分）根据DAG结点原来的构造顺序重写四元式如下：（2分）A： =5Tl=10T3=10B：=R+rTO：=A+BT2： =TOXI：=T0+T1X2：=TO*T1(3)假设基本块出口后惟独XI, X2还被引用，则通过重新命名暂时变量的基本块保结 构变换，可将基本块的四元式代码进一步优化为：(3分)C ：=R+r D： =5+C XI：=D+10X2：二D*104、0)S'S4)A 一a1)S 一A5)B -bBd2)S 一B6)B b3)A aAeGS的LR(O)项目集规范族DFA如下：(4分)，得GS的SLR分析表如下:状态ACTIONGOTOabed#SAB0S4S51231acc2ri3r24S4r4r465S51,6r676ss7S9813r39r5(2)由于步骤状态栈符号栈输入串JACTIONGOTO10aae#S4204#a#S43044痴ic#r464(146#aAe#S85(I46S#r326(12#A#rl1701#S#acc(3分)由上左表可知GS是SLR文法(1分)。用SLR (1 )方法分析输入串aae#过程如上右表所示：(4分)(4)由于GSLR(O)项目集规范族DFA中I、T中都包含有移进一归约冲突，所以GS>5 不是LR(O)文法，由于GS1是SLR文法故一定是LR和LALR文法。(3分)编译原理课程测试试卷评分标准(数计学院04计科B卷)一、填空题参考答案(共30分，30个空，每空1分)题号1234参考 答案中间代码生成、单词、 语义分析句子、非终结符号集和 终结符集、左部移进项目、AccB0、接受项目不惟一、优先矩 阵、优先函数题号5678参考 答案标识符、类型、作用 域和可视性、算符文法、多、算符优 先文法目标代码、已定位、 可重定位强连通、有且惟独 一个入口结点题号910参考答案符号a、状态j、归约得到的非终结符A、gotoS,a的值j全局变量、形参和实参说明：各个答案可有不同表达方式，只要意思相同即可。二、简述题参考答案（共20分，4个小题，每小题5分）1、运行目标程序时所需空间分为两种容纳目标代码的空间和目标代码运行时的数据 空间。（2分）目标代码运行时的数据空间中某些部份无法在编译时确定存储位置，它主要包括： 用户所定义的变量和常量所需空间、中间结果及参数传递所需的暂时单元、调用过程时的连 接单元、I/O操作所需缓冲区。（3分）2、（ 1）算符优先分析算法的步骤：（3分）设单元a中存放当前输入符，S为一个符号栈，则：1）将当前输入符存放到a中，将#入符号栈。2）将栈顶第一个终结符b与a比较。如果ga,而b=#且栈中只剩一个非终结符时，则成 功；否则a入栈；如果bta,则a入栈；如果ba,在栈顶寻觅最左素短语，并将最左素短语归约 为一个非终结符；如果文法中找不到相应规则，则出错；3）重复至成功或者失败。（2）算符优先分析方法的优、缺点：（2分）由于只考虑终结符之间的优先关系确定句柄，所以效率高；由于去掉了单非终结符之间的归 约，有可能将错误的句子识别为正确的，只合用于表达式的语法分析。3、所谓优化实质上是对代码进行等价变换，使得变换后的代码运行结果与变换前的代 码运行结果相同，但运行速度或者占用的存储空间加大。（1分）代码优化按阶段分中间代码优化和目标代码优化，按程序范围分为局部基本块优化、循 环优化、全局优化。（2分）常用的优化技术有删除多余运算、代码外提、强度削弱、变换循环控制条件、合并已知 变量与复写传播等。（2分）4、判别任意给定的一个上下文无关文法GS是否为LALR（l）文法的过程：（1）WG加入一条规则：S，SGS拓广为G此，然后构造G此的LR（0）项目集规范族DFA。 检查DFA的项目集中有无移进一归约冲突或者归约一归约冲突，若无，则GS是LR（）文法， 也是LALR文法。（1分）（2）如果DFA的项目集中有无移进一归约冲突或者归约一归约冲突，通过考虑归约项 目左部非终结符的FOLLOW集能够解决这两类冲突，则GS，是SLR文法，也是LALR（l） 文法。（2分）（3）如果通过考虑归约项目左部非终结符的FOLLOW 集还有不能够解决的移进一归 约冲突，通过考虑后跟符号来构造GS，的LR（1）项目集规范族DFA。如果冲突可以解决，则 GS，是LR（1）文法。进一步合并LR（1）项目集规范族中同心集，如果依然不产生归约一归约冲突， 则G是LALR（1）文法。（3分）三、应用题参考答案（共5（）分）1、（ 1 ）证明（3分）：因为存在推导序列：E=>T+E=>T+T+E=>T+T*F+E=>T+T*F+T =>T+T*F+F=>T+T*F+i ,即有 E=*>T+T*F+i 成立，所以，T+T*F+i 是文法的一个句型。（2）语法树（3分）：E(3)句型分析(7分)：该句型相对牙E的短语:+T*F+i、T*F+i和i ；相对于T的短语有:T*F和i,相对于F的短语有i。相对于 接短语：i。句柄：T*F。F的直接短语：T*F,相对于F - i的直(4)该句型的所有素短语：T*F和I； T*F为隈左素短悟。(3分)2、if a<b or c<d and e>f then s 1(1) if a < bgoto (7)goto (3)(3) if c < dgoto (5)(4) goto (p+1)(5) if e > fgoto (7)(6) goto (p+1)式序列如下：(6分)S1对应的四元式序列(p) goto (q)(p+1) s2对应的四元式序列(q)3、(1)弋入后有S的规则右部(bS|b)|b(aS|aAa(bS|£)|ba(S|£)=(ab|ba)(S|£),故对应的正规式 R=(ab|ba)(ab|b*a)。(3 分)bbA总化为DFA状态P11=S,P12=A , P13=B；A右图所示:和终态集已是最小化对应的NFA状态图如下左图所示：(3分)将丽亳技(4)将所得 P2=Z；然后对1 的 DFA o (3 分)4、计算GE的SELECT集如下：(2分)SELECT(E - E T)=, (a) SELECT(E - T)=(, aSELECT(T ->TA F)=, ( a SELECT(T 一 F)=(, aSELECT(F->(E =)( SELECT(F 一 a=)a 由于SELECT(E - E T)n SELECT(E一T)=, (a，； (pSELECT(T - T7 nSELECT(T-F尸(, a，； cpSELECT (F 一( E )0SELECT (F 一a) = (Aa =(p故GE不是LL(文法。(1分)对GE的E - E T和T 一 T八F两条规则消除左递归后变为：(2分) E一TE' E'一TEKT - FT，T' FT'怛 F (E)|a计算消除左递归后GE的SELECT集如下：(2分)SELECT(ETE>, (a SELECT(E，一 T E')=SELECT(E，一£户, #)SELECT(T一FT'尸(aSELECT(T,->AFT,)=A SELECT(F一(E )=(SELECT(T,->>, #, )SELECT(F - a尸a由于 SELECT(E'TE')nSELECT(E'>£)彳pSELECT （T 一八 F T） ASELECT （T 一 & =（pSELECT （F 一（ E ）ASELECT （F 一a） = =（p故消除左递归后的GE是LL（文法。（1分）（2）根据消除左递归后的G闾的SELECT集构造预测分析表如下：（3分）步费分析板利输入申I 所用规则1a-aAa#I ETE'2*E*Ta-a Aa#TTT*3#ETFa-aAa#Fa4#ETaa-aAa# |匹配a5*GT-aAa#T* -* 6#E-aAa#E-TT7#ET-aAa#匹8#EtTaAa#T-*PT*9*ETFaAa#F -*a10#ETaaAa#匹配a11#ETT 一什12#ETFAAa#匹配.13#ETtFa#F-*a14#ETaa*匹配a意k规则存部以浮序入栈户（5分)T-16#e,E* i s17*#成功接受S 一 aAS|aA - SbA|SS|ba（1）证明aabbaa是文法的一个句子。（3分）构造句子aabbaa的语法树。（3分）指出该句子的所有短语、直接短语和句柄。（6分）2、对文法GE：（15分）E'TE# E 一E+T|T T 一T*F|F F ->PAF|P P 一 （E）|i计算 GE的 FIRSTVT 和 LASTVT。（5 分）构造GE的算符优先关系表,并说明G旧是否为算符优先文法。（5分）（3）给出输入串w=i+i#的算符优先分析过程。（5分）3、对以下基本块：（8分）A：=5 B： =R+r TO：=A+BTl： =2*AT2：=B+AT3： =A+A XI： =T1+T2X2： =T0*T3（1）画出基本块的DAG图。（3分）（2）根据DAG结点原来的构造顺序重写四元式。（2分）（3）假设基本块出口后惟独XI, X2还被引用，试写出优化后的四元式序列。（3分）4、对文法（15分）O）S'-S1）S-A2）S-B 3）AaAe4）A -a5）B -bBd 6）B b试构造GS的LR（0）项目集规范族DFA。（4分）试构造GS的SLR分析表，并判断它是否为SLR（l）文法。（4分）（3）试用SLR （1）方法分析输入串aae#o（4分）（4）GS是否为LR（0）、LR和LALR文法?为什么？ （3分）课程测试试题（04B卷）I、命题院（部）：数学与计算机科学学院n、课程名称：编译原理n、I测试学期：20222022学年度第1学期IV、测试对象：数计、国交学院计科专业2004级1、2、国交班V、问卷页数（A4）：3页VI、答卷页数（A4）：4页VIL考试方式：闭卷（开卷、闭卷或者课程小论文，请填写清晰）VIIL问卷内容：（请老师在出题时安排紧凑，填空题象征性的留出一点空格, 学生将所有的答案做在答题纸上的规定位置，并写清晰大题、小题的题号）一、填空题（共30分，30个空，每空1分）1、典型编译过程普通分为词法分析、语法分析、语义分析、（并非所有的编译程 序都包含此阶段）、代码优化、目标代码生成六个阶段，其中词法分析的任务是对构成源程 序的字符串进行扫描和分解，识别出一（如标识符等）符号；为代码生成阶段采集类型信息， 并进行类型审查和违背语言规范的报错处理是一的任务。2、文法是一些规则的有穷集合，它是以有穷规则集来刻划无穷 集合的工具。文法的四元组表示G = （V，nP，S）中n平素V, V分别是非空有限的 o且二者交集为（P； P为产生式/规则集，是文法的核心部份；S £ V ,最文法的开始符号（或者识别符）， 它是一个非终结符，至少要在一条规则中作为 浮现。3、构造LR（0）项目集规范族的项目类型分为四种：形如A-a.a的、形如的待约项目、形如A-卿的归约项目、形如S郝1o4、一个优先关系矩阵对应的优先函数 ；所表示优先关系惟一的矩阵不一定存在优 先函数；当两个终结符对之间无优先关系时，可以将相应元素置出错信息，而使用 却 无法识别这种情况，不能准确指出出错位置。5、在编译程序中用符号表来存放语言中浮现的有关的语义特征属性信息。程序设计语言中通用的标识符属性主要有如下几种：符号名、符号的、符号的存储类别、符 号的、符号变量的存储分配信息及数组的内情向量等其它属性。6、如果文法G=（V，nV、P，S）中不存在形如A 一BC.的产生式，其中B、C 为非终结符，则称之为 o在此基础上，如果a,b£VT,a三b,4ab,a才b至 有一个成立，则称之为 o7、分为三类：的机器语言代码；的机器语言代码；汇编语言（宏汇编）。8、在程序流中，一个循环必须具有以下性质：1），即序列中任意两点都可达， 若惟独一个结点，则有一条返回本身的回边；2）,即从序列外某结点，有一条有向边 指向它，或者它为图中首结点。9、LR分析步骤：1）置输入指针ip指向输入串的第一个符号；令S是栈顶状态，a是ip所 指向的符号;将#压入符号栈，将开始状态0压入状态栈；2）根据分析表重复执行如下过程：如 果action, Sa=Sj,则把入符号栈，把入状态栈，并使ip指向下一个输入符号；如果 actionSap, I则从，戋顶弹出第j条规则右部串长下个|符号，把压入符号栈，将压入状态栈，并输出规则A 一仇如果actionS,a=a, cc则分析成功，否则报错。10、过程（函数）是结构化程序设计的主要手段。调用与被调用过程两者之间的信息主要 通过 或者参数来传递。参数分为，常用的参数传递方式有传地址、传值、传名等。二、简述题（共2（）分，4个小题，每小题5分）1、简述运行目标程序时所需空间的种类。2、简述算符优先分析算法的步骤和算符优先分析方法的优、缺点。3、简述代码优化的概念和分类，并列举出四种以上常用的代码优化技术。4、简述判别任意给定的一个上下文无关文法GS是否为LALR（l）文法的过程。三、应用题（共50分）1、有文法GE：（16分）E T + E|T T一T*F|F F - （E|）i证明T+T*F+i是文法的一个句型。（3分）构造型T+T*F+i的语法树。（3分）指出该句型的所有短语、直接短语和句柄。（7分）（4）指出该句型的所有素短语和最左素短语。（3分）2、将下列条件语句翻译成四元式的中间代码形式：（6分）if a<b or c<d and e>f then si else s23、有正规文法GS： （12分）S 一 aA|bB A bS|b B 一 aS|a构造对应的正规式R,使得L（R）=L（G）。（3分）（2）构造对应的NFA状态图，使得L（M）=L（R）o （3分）将所得NFA确定化为DFA o（3分）将所得DFA最小化。（3分）4、对表达式文法GE：（16分）E -> E- T| T T -> T A F| F F 一（E |）a判断GfE是否为LL文法。若不是，改造为LL文法。（8分）构造预测分析表，并对输入串w=a-a八a#进行预测分析。（8分）课程测试试题（03A卷）以-下为教师填写I、命题院（部）：数学与计算机科学学院n、课程名称：编译原理h、I测试学期：2005- 2022学年度第1学期IV、测试对象：数计学院计算机科学技术专业2003级1、2、3班V、问卷页数（A4）：4页_VI、答卷页数（A4）：61VIL考试方式： 闭卷（开卷、闭卷或者课程小论文，请填写清晰）VIIL问卷内容：（请老师在出题时安排紧凑，填空题象征性的留出一点空格， 学生将所有的答案做在答题纸上的规定位置，并写清晰大题、小题的题号）一、填空（30分）1、将编译过程的各阶段划分为前端或者后端和将编译程序分遍的主要参考因 素都是（）和（）的特征。2、（）是一种语法分析程序的自动构造工具，用它可以直接构造各种语言 的语法分析器；而（）是一种词法分析程序的自动构造工具，用它可以直接构造 各种语言的词法分析器。3、假设G网是一个文法，如有S*x,则称x是该文法G的（）；文法G产生的（）的全体称为该文法所描述的语言。4、所谓2型文法就是指（）文法，若用G = （V, V, P, S）表示它，则n t 它要求G中的所有规则a-0都满足：a是（），而|3属于（VUV）*。N T5、文法中形如U-U的规则称为（）规则；由不可达的非终结符或者不可终 止的非终结符作为左部的规则称为（）规则。在实用文法中普通不允许含有这两 类规则。6、在用五元组表示的确定的有穷自动机DFAM=（K, V, F, S, Z）中，元素V 表示字母表；元素S表示惟一的初态，它是状态集K的一个元素；元素F表示（）；元素 Z表示终态集，它是状态集K的一个（）07、语法分析方法分为自上而下与自下而上两类，自上而下的分析方法方要有 递归子程序分析法和（）；而自下而上的分析方法主要有（）和LR分析方法。8、LR（0）项目集规范族中的项目可分为四类，它们是移进项目、（）、归约项目和接受项目。其中，接受项目是（）的一种特例。9、将非LL文法转换为等价的LL文法所采用的两种方法是（）和（）。但这 两种方法并不能保证所有的非LL（1）文法都能转换为等价的LL（1）文法。10、通常局部优化是指基本块内的优化，所谓基本块是指程序中一顺序执行 的语句序列，其中惟独一个（）语句和一个（）语句。11、算符优先分析时，在句型NaNaNaNaaNaN中，寻觅的2i-l i i i+1 i+1 j j+l j+1 j+2最左素短语NaNaaN中的终结符应满足下优先关系：（）、（）、（）。i i i+1 i+1 j j+l12、在编译程序中符号表用来存放语言程序中浮现的有关标识符的属性信息， 这些信息集中反映了标识符的语义特征属性。符号表的功能可以归结为三个主要 方面，即（）、作为上下文语义合法性检查的依据和作为（）的依据。13、根据优先关系矩阵计算优先函数可用迭代法或者优先关系图法，但先关 系图方法计算出来的优先函数不一定有效，当（）时，所得的优先函数无效，这 时也说明该优先关系矩阵不存在优先函数。14、当一个过程调用其他过程时，调用过程和被调用过程之间的通信经由非 局部变量或者经由参数传递，常用的参数传递方式有（）、（）等。15、现代不少编译程序都采用（）翻译方法，它是指在语法分析过程中，随 着分析的步步发展，根据每一个规则所对应的语义子程序或者语义动作进行翻译 的办法。这种方法使用（）为工具来说明程序设计语言的语义。二、结合你所熟悉的一门高级语言的编译系统，简述典型编译程序在各个工作 阶段的任务。（共7分）三、给定正规式R401110）（01|10）*,要求：（10分）1、构造对应的正规文法G,使得L（G）=L（R）。（4分）2、构造对应的NFAM状态图，使得L（M）=L（R）。（3分）3、将所得NFA M确定化为DFAo （3分）四、现有文法GE：（共10分）EE+T|E-T|TT 一 T*F|T/F|FF-i|（E）1、证明：E-F*是文法的一个句型。（3分）2、构造句型E-F*的语法推导树。（2分）3、指出该句型所有短语、直接短语和句柄。（5分）五、任意给定一个文法GS：（10分）1、给出判断GS是否为LL（1）文法的步骤。（4分）2、如果GS是LL（1）文法，怎样构造它的预测分析表？（3分）3、怎样根据预测分析表对给定的某个输入串进行预测分析？（3分）六、现有文法GE：（共15分）E 一 E;D|DD->D（T）|HHa|（E）TtT*E|E1、计算 GE的 FIRSTVT 和 LASTVT； （4 分）2、构造GE的算符优先关系表,并说明GE是否为算符优先文法；（5分）3、给出输入串（a*a）#的算符优先分析过程，并据此说明算符优先分析方法的优点 和缺点。（6分）七、现有文法GS"（共18分）0） S' - S1） S 一 L = R2） S ->R3） L 一* R4） L ->i5） R - L1、构造GS的LR（0）项目集规范族DFA,并据此判断GS是否为LR（0）文法或 者SLR文法。（6分）2、构造GS的LR（1）项目集规范族DFA,并据此判断GS是否为LR文法或者LALR（l）文法。（6分）3、给出相应的LALR分析表。（3分）4、简述LR分析算法。（3分）课程测试试题（03B卷）以-下为教师填写I、命题院（部）：数学与计算机科学学院n、课程名称： 编译原理口、I测试学期：2005- 2022学年度第1学期IV、测试对象：数计学院 计算机科学技术专业2003级1、2、3班V 、问卷页数（A4）：4V I、答卷页数（A4）：6页V IL考试方式：闭卷（开卷、闭卷或者课程小论文，请填写清晰）VIIL问卷内容：（请老师在出题时安排紧凑，填空题象征性的留出一点空格， 学生将所有的答案做在答题纸上的规定位置，并写清晰大题、小题的题号）一、判断（15分）1、编译程序是一种语言翻译程序，它将源语言程序翻译成功能等价的目标 语言程序。2、所谓规则或者产生式是指形如aP或者oc呻的（a,隔序对，其中a是字母表V的正闭包元素，而B是字母表V的闭包元素。3、设文法G=（V, V, P, S）,若P中的每一个规则都是A-aB或者A-a, nT其中A和B是非终结符，而a是终结符，则称此文法G为正规文法或者3型文法。4、实用文法中不得含有形如U-U的有害规则，也不得含有由不可达或者不可终止的非终结符所构成的多余规则。5、对任意给定的一个正规式R,都可以将它转换为与之功能等价的正规文法，或者与之功能等价的有穷自动机。6、LEX是一个用于构造各种各样语言的词法分析程序；YACC是一个用于 构造各种各样语言的语法分析程序。7、假设现有五元组表示的有穷自动机M= （ K, V, F, S, Z）,若M是NFA, 则S表示初态，且S具有惟一性，它是状态集K的一个元素。8、算符优先分析方法和LR分析方法都是自下而上的分析方法，它们的分析 过程实际上就是规范归约过程。9、LR（O）项目集规范族中的项目由两部份构成，一部份是心，即原来的LR（1） 项目，另一部份是向前搜索符号集。10、所谓优化实质上是对代码进行等价变换，使得变换后的代码运行结果与 变换前的代码运行结果相同，但运行速度或者占用的存储空间加大。常用的优化 技术有删除多余运算、代码外提、强度削弱、变换循环控制条件、合并已知变量 与复写传播等。11、对一个不包含空规则的算符文法，如果文法中的任意两个终结符构成的 符号对之间最多惟独大于、小于和等于三种优先关系中的一种成立，则称该算符 文法为算符优先文法。12、目标程序运行时的动态数据存储区分为堆区和栈区，它用于存放可变数 据以及管理过程活动的控制信息。13、在语法分析过程中，随着分析的步步发展，根据每一个规则所对应的语 义子程序或者语义动作进行翻译的办法，称为语法制导翻译，它被现代不少编译 程序所采用。14、可归前缀本身就是活前缀，它是包含句柄在内的活前缀。15、符号表用来存放语言程序中浮现的有关标识符的属性信息，这些信息集 中反映了标识符的语义特征属性。二、将表达式A:=B*（C-D）/D：（共9分）3、翻译成逆波兰式的中间代码形式。（2分）4、翻译成四元式的中间代码形式。（4分）5、将译成的四元式用DAG表示。（3分）三、现有文法GE：（共12分）E 一 E+T|E-T|TT 一 T*F|T/F|FF-i|（E）6、证明：F+T*（E）是文法的一个句型。（3分）7、构造句型F+T*（E）的语法推导树。（3分）8、指出该句型所有短语、直接短语和句柄。（6分）四、给定正规式R=d（a|bc）d要求：（12分）4、构造对应的NFAM状态图，使得L（M）=L（R）。（4分）5、将所得NFAM确定化和最小化。（8分）五、现有文法GS：（共16分）S ->S;D|DD 一D（T）|HHm|（S）T 一 T*S|S1、计算 GS的 FIRSTVT 和 LASTVT；（4 分）2、构造GS的算符优先关系表,并说明G网是否为算符优先文法；（6分）3、给出输入串（m*m）#的算符优先分析过程。（4分）4、根据分析过程总结算符优先分析方法的优缺点。（2分）六、已知GS：（18分）S（A）间 bA 一 A,S|S1、给出a（b,b）的最左推导。（3分）2、判断该文法是否为LL（1）文法。若是，直接给出它的预测分析表；若不是, 先将其改写为LL（1）文法，再给出它的预测分析表；（10分）3、给出输入串（b,b）#的分析过程，并说明该串是否为GS的句子。（5分）七、对给定文法GS：（共18分）0）S，-S1）S-A2）SB3） A >aAc4） A 一a