资源描述
一、填空（每题2分，共20分）1从功能上说，程序语言的语句大体可分为（ 执行性 ）语句和（ 说明性 ）语句两大类。2扫描器的任务是从（ 源程序 ）中识别出一个个（ 单词符号 ）。3所谓最左派生是指（ 任何一歩都是对中最左非终结符进行替换的 ）。4语法分析最常用的两类方法是（ 自顶向下 ）和（ 自底向上 ）分析法。5一个上下文无关文法所含的四个组成部分是（一组终结符号，一组非终结符号、一个开始符号、一组产生式 ）。6所谓语法制导翻译方法是（ 为每个产生式配上一个翻译子程序，并在语法分析的同时执行这些子程序 ）。7LR分析法中的两种冲突是（ 移入归约 ）和（ 归约归约 ）。8产生式是用于定义（ 语法范畴 ）的一种书写规则。9属性定义中有两种性质的属性，分别是（ 继承属性 ）和（ 综合属性 ）。10常用的两种动态存储分配方法是（ 栈式动态分配 ）和（ 堆式动态分配 ）。11. 所谓最右推导是指：任何一步都是对中最右非终结符进行替换的。12. 一个过程相应的DISPLAY表的内容为 （现行活动记录地址和所有外层最新活动记录的地址。）13. 符号表中的信息栏中登记了每个名字的有关的性质，如（ 类型、种属、所占单元大小、地址 ）等等。14运行时的DISPLAY表的内容是什么？它的作用是什么？答：DISPLAY表是嵌套层次显示表。每当进入一个过程后，在建立它的活动记录区的同时建立一张嵌套层次显示表diaplay.假定现在进入的过程层次为i，则它的diaplay表含有i+1个单元，自顶向下每个单元依次存放着现行层、直接外层、直至最外层(主程序，0层)等每层过程的最新活动记录的起始地址。通过DISPLAY表可以访问其外层过程的变量。二、名词解释（每题3分，共15分）1 编译器预处理：对于一个编译器，如果要处理的输入是对原编译器的输入的扩充，就把输入中的扩充部分转换成原输入的形式，然后把其结果交给原编译器处理，也就是把扩展的部分转换成标准形式，这就是编译器预处理2 LL（K）文法（P89）3 歧义文法(p71)正则表达式(P47) ：每个正则表达式定义一个正则集。若用RE表示上的正则表达式，并用L(RE)所表示的正则集，则RE的语法定义和相应正则集如下面所述，其中A和B表示正则表达式，并且表示字母表中的任一符号。 4 属性文法(P260)三、简答题（每题5分，共15分）1 设有L（G）a2n+1b2m+1c2p | n=1, m1, p=11) 给出它的正则表达式。2) 构造识别该语言的DFA。2 生成语言L（G）apbmcpanbn | p=0, m=1, n=2的文法G是什么？它是chomsky的哪型文法。解：G(3)文法为S-ACA-aAc|BB-bB|bC-aCb|ab它是乔姆斯基2型文法3 已知文法G（S）： Sa|b|(T) TT,S|S 写出句子（a,b）,b）的规范规约过程及每一步的句柄。解：句型 规约 句柄（a,b）,b） （S,b）,b） S-a a(T,b),b)T-S S(T,S),b)S-bb(T),b)T-T,ST,S(S,b)S-(T)(T)(T,b)T-SS(T,S)S-bb(T)T-T,ST,SS S-(T) (T)四、计算题（每题10分，共20分）1 已知文法G（E）ET|E+TTF|T*FF(E)|i给出句型（T*F+i）的最右派生及画出语法树。解：1. (4分)ETF(E) (E+T) (E+F) (E+i) (T+i) (T*F+i) 2. (4分) 短语：(T*F+i), T*F+i, T*F, i直接短语：T*F, i句柄：T*F素短语：T*F, i 2说明下面的文法不是SLR(1)文法，并重写一个等价的SLR(1)文法。S M a | b M c | d c | b d aM d解：S S S M a | b M c | d c | b d aM dS .SS .M aS .b M cS . d cS . b d aM .dS b .M cS b .d aM .dS b d .aM d .bd因为a是M的后继符号之一，因此在上面最右边一个项目集中有移进-归约冲突。等价的SLR(1)文法是S d a | b d c | d c | b d a五、设计题（每题15分，共30分）1下面的文法定义语言L = anbncm | m, n 1。写一个语法制导定义，其语义规则的作用是：对不属于语言L的子集L1= anbncn | n 1的句子，打印出错信息。S D CD a D b | a bC C c | c解：语法制导的定义如下：S D Cif D.length C.length then print (“error”)D a bD.length := 1D a D1 bD.length := D1.length + 1C cC.length := 1C C1 cC.length := C1.length + 12. 给出文法G（L）的翻译模式，它分别计算字符串中0与1的个数。（要求ANTLR代码）SL.L| LLBLLB0|1Grammer L01members int n0; int n1;Start: n0=0; n1=0; jsystem.out.println(n0);system.out.println(n1);j: 0jn0 +=1; |1 jn1 +=1; | a;ws:( | t| n| r)+skip();名词解释1遍指编译程序对源程序或中间代码程序从头到尾扫描一次。 2无环路有向图(DAG)如果有向图中任一通路都不是环路，则称庐有向图为无环路有向图，简称DAG。 3语法分析按文法的产生式识别输入的符号串是否为一个句子的分析过程。 4短语令G是一个文法。S划文法的开始符号，假定是文法G的一个句型，如果有SA且AB，则称是句型相对非终结符A的短语。 5后缀式一种把运算量写在前面，把算符写在后面的表示表达式的方法。简述题 1、写出表达式(ab*c)/(ab)d的逆波兰表示及三元式序列。2、已知文法G(S)Sa|(T)TT，S|S 写出句子(a，a)，a)的规范归约过程及每一步的句柄。3、何谓优化？按所涉及的程序范围可分为哪几级优化？4、目标代码有哪几种形式？生成目标代码时通常应考虑哪几个问题？答案： 1、逆波兰表示： abc*ab/d 三元式序列： (*，b，c) (，a，) (，a，b) (/，) (，d)3、优化：对程序进行各种等价变换，使得从变换后的程序出发，能产生更有效的目标代码。 三种级别：局部优化、循环优化、全局优化。4、目标代码通常采用三种形式：机器语言，汇编语言，待装配机器语言模块。 应着重考虑的问题： (1)如何使生成的目标代码较短； (2)如何充分利用寄存器，以减少访问内存次数； (3)如何充分利用指仅系统的的特点。计算题： 1、写一个文法，使其语言是奇数集，且每个奇数不以0开头。(5分) 解：文法G(N)： NAB|B AAC|D B1|3|5|7|9 DB|2|4|6|8 C0|D(5分) 2、设文法G(S)： S(L)|a S|a LL，S|S (1) 消除左递归和回溯； (2) 计算每个非终结符的FIRST和FOLLOW； (3) 构造预测分析表。 解： (1) S(L)|aS SS| LSL LSL| 评分细则：消除左递归2分，提公共因子2分。 (2) FIRST)S)(，aFOLLOW(S)#，) FIRST(S)，a,FOLLOW(S)#，) FIRST(L)(，aFOLLOW(L) ) FIRST(L)，FOLLOW(L ) 3、Whilea0 b0do Begin X：X1； if a0 then a：a1 else b：b1 End； 翻译成四元式序列。(7分) 解： (1) (j，a，0，5) (2) (j，3) (3) (j，b，0，5) (4) (j，15) (5) (，1，T1) (6) (：，T1，) (7) (j，a，0，9) (8) (j，12) (9) (，a，1，T2) (10) (：，T2，a) (11) (j，1) (12) (，b，1， T3) (13) (：，T3，b) (14) (j，1) (15) 评分细则：控制结构4分，其它3分。 4、已知文法G(E) ET|ET TF|T * F F(E)|i (1) 给出句型(T * Fi)的最右推导及画出语法树； (2) 给出句型(T * Fi)的短语、素短语。(7分) 解：(1) 最右推导： ETF(E)(ET)(EF)(Ei) (Ti)(T*Fi) (2) 短语：(T*Fi)，T*Fi，T*F，i(2分) 素短语：T*F,i (1分) 5、设布尔表达式的文法为 E E(1)E(2) E E(1) E(2) E i 假定它们将用于条件控制语句中，请 (1) 改写文法，使之适合进行语法制导翻译和实现回填； (2) 写出改写后的短个产生式的语义动作。(6分) 解：(1) E0E(1) EE0E(2) EAE(1) EEAE(2) Ei(3分) (2) EE(1) BACKPATCH(E(1)FC，NXQ)； E0TC：E(1)TC EE0E(2) EFC：E(2)FC； ETC：MERG(E0TC，E(2)TC) EAE(1) BACKPATCH(E(1)TC，NXQ)； E0FC：E(1)FC EEAE(2) ETC：E(2)TC； EFC：MERG(EAFC，E(2)FC Ei ETC：NXQ；EFC：NXQ1； GEN(jn2，entry(i)，0)； GEN(j，0)(3分) 6、设有基本块 T1：2 T2：10/T T3：SR T4：SR A：T2 * T4 B：A T5：SR T6：T3 * T5 B：T6 (1) 画出DAG图； (2) 假设基本块出口时只有A，B还被引用，请写出优化后的四元序列。(6分) 解：(1)DAG： (2) 优化后的四元式 T3：SR T4：SR A：5*T4 B：T3T4(3分)例题3若正规表达式r=(a|b|c)(0|1)*，则L(r)中有_D_个元素。（12）A12 B18C6D无穷解析：本题考察的是程序的语言的组成句子与文法之间的关系；正规表达式r=(a|b|c)(0|1)*表示的是a,b,c中的任意一个与0、1串的连接，由于0、1串的长度和组成是不固定的，所以整个句子的数据就是不固定的，也就是说语言L(r)的组成元素是无穷的。试题4：编译器和解释器是两种高级语言处理程序，与编译器相比， B 。编译器对高级语言源程序的处理过程可以划分为词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成等几个阶段：其中，代码优化和 C 并不是每种编译器都必需的。词法分析的作用是识别源程序中的 B ；语法分析中的预测分析法是 B 的一种语法分析方法；编译器在 C 阶段进行表达式的类型检查及类型转换。（13） A、解释器不参与运行控制，程序执行的速度慢 B、解释器参与运行控制，程序执行的速度慢 C、解释器参与运行控制，程序执行的速度快 D、解释器不参与运行控制，程序执行的速度快（14）A、词法分析 B、语法分析 C、中间代码生成 D、语义分析(15) A、字符串 B、单词 C、标识符 D、语句(16) A、自左至右 B、自顶向下 C、自底向上 D、自右至左(17) A、词法分析 B、语法分析 C、语义分析 D、目标代码生成例题5：假设某程序语言的文法如下：Sa | b | (T)TTdS | S其中，VT=a,b,d,(,)，VN=S,T，S是开始符号。考查该文法，称句型(Sd(T)db)是S的一个A 。其中B是句柄；C是素短语；D是该句型的直接短语；E是短语。A： 最左推导 最右推导 规范推导 推导B： S b (T) Sd(T)C： S b (T) Sd(T)D： S S,(T),bS,(T),TdS,b(Sd(T)db)E： (Sd(T)db)d(T)Td Sd(T)d此句型的语法树如下所示：S (T) （T d S）（T d S b）（S （T） 从语法树我们可以看出，短语就是位于同一个非终端结点的所有叶子结点，比如S、Sd(T)、Sd(T)db就是是相对于T的短语，b、(T)、(Sd(T)db)是相对于S的短语。而直接短语则进一步要求这些叶子结点的非终端结点是它们的直接父结点。因此可以S、(T)、b都是该句型的直接短语。语法树上最左的直接短语就是句柄，本题中是S。所谓素短语是指这样一个短语，它至少含有一个终结符，并且除它自身之外不再含任何更小的素短语。最左素短语则指处于句型最左边的那个素短语。最左推导是指任何一步推导过程，都是对中的最左非终结符进行替换。因此，在语法树中也很容易看出，如果语法树中的只有最左的非终结符结点（包括各级结点）具有其子树，则它就是最左推导。最右推导与之类似，最右推导也称规范推导。本题从语法推导树可以看出，既不是最左推导也不是最右推导，就是一般的推导。A： B： C： D： E：1、算符优先关系表不一定存在对应的优先函数。 正确2、数组元素的地址计算与数组的存储方式有关。 正确3、仅考虑一个基本块，不能确定一个赋值是否真是无用的。 正确4、每个文法都能改写为LL(1)文法。 不正确5、对于数据空间的存贮分配，FORTRAN采用动态贮存分配策略。 不正确一、回答下列问题：(30分)1什么是S-属性文法？什么是L-属性文法？它们之间有什么关系？解答：S-属性文法是只含有综合属性的属性文法。 （2分）L-属性文法要求对于每个产生式AX1X2Xn，其每个语义规则中的每个属性或者是综合属性，或者是Xj的一个继承属性，且该属性仅依赖于：（1） 产生式Xj的左边符号X1,X2Xj-1的属性；（2） A的继承属性。 （2分）S-属性文法是L-属性文法的特例。 （2分）2什么是句柄？什么是素短语？一个句型的最左直接短语称为该句型的句柄。（3分）素短语是这样的一个短语，它至少包含一个终结符并且不包含更小的素短语。（3分）3划分程序的基本块时，确定基本块的入口语句的条件是什么？解答：（1）程序第一个语句，或（2）能由条件转移语句或无条件转移语句转移到的语句，或（3）紧跟在条件转移语句后面的语句。4(6分)运行时的DISPLAY表的内容是什么？它的作用是什么？答：DISPLAY表是嵌套层次显示表。每当进入一个过程后，在建立它的活动记录区的同时建立一张嵌套层次显示表diaplay.假定现在进入的过程层次为i，则它的diaplay表含有i+1个单元，自顶向下每个单元依次存放着现行层、直接外层、直至最外层(主程序，0层)等每层过程的最新活动记录的起始地址。通过DISPLAY表可以访问其外层过程的变量。5(6分)对下列四元式序列生成目标代码： A:=B*CD:=E+FG:=A+DH:=G*2其中，H是基本块出口的活跃变量， R0和R1是可用寄存器答：LD R0， BMUL R0， CLD R1， EADD R1， FADD R0， R1MUL R0， 2ST R0， H二、设S=0，1上的正规集S由倒数第二个字符为1的所有字符串组成，请给出该字集对应的正规式，并构造一个识别该正规集的DFA。(8分)答：构造相应的正规式：(0|1)*1(0|1) (3分)NFA: (2分) 1 110432 e e e e 1 0 0确定化：(3分)I0,1,21,21,2,31,21,21,2,31,2,31,2,41,2,3,41,2,41,21,2,31,2,3,41,2,41,2,3,4 0 143210 0 1 0 0 0 1 1 三、(6分)写一个文法使其语言为L(G)= anbmambn | m,n1。答：文法G(S):S aSb | BB bBa | ba四、对于文法G(E): (8分)ET|E+TTF|T*FF(E)|iETF(E)E+TFiTT*F1. 写出句型(T*F+i)的最右推导并画出语法树。2. 写出上述句型的短语，直接短语、句柄和素短语。答：1. (4分)ETF(E) (E+T) (E+F) (E+i) (T+i) (T*F+i) 2. (4分)短语：(T*F+i), T*F+i, T*F, i 直接短语：T*F, i句柄：T*F 素短语：T*F, i五、设文法G(S)：(12分)1 构造各非终结符的FIRSTVT和LASTVT集合；2 构造优先关系表和优先函数。(12分)答：(6分)FIRSTVT(S)= i，+，)，( FIRSTVT(A)= +，)，( FIRSTVT(B)= )，( LASTVT(S)= i，+，*，( LASTVT(A)= +，*，( LASTVT(B)= *，( 优先关系表: (3分)i+()*i()优先函数: (3分)i+()*f26616g14661六、设某语言的do-while语句的语法形式为 (9分) S do S(1) While E其语义解释为：真假S(1)的代码E的代码针对自下而上的语法分析器，按如下要求构造该语句的翻译模式：(1) 写出适合语法制导翻译的产生式；(2) 写出每个产生式对应的语义动作。答：(1). 适合语法制导翻译的文法(3分) G(S): R do UR S(1) While SU E (2). (6分) R do R.QUAD:=NXQ UR S(1) While U.QUAD:=R.QUAD; BACKPATCH(S.CHAIN, NXQ) SU E BACKPATCH(E.TC, U.QUAD); S.CHAIN:=E.FC 答案二：(1) S do M1 S(1) While M2 E M (3分)(2) M M.QUAD := NXQ (6分)S do M1 S(1) While M2 EBACKPATCH(S(1).CHAIN, M2.QUAD);BACKPATCH(E.TC, M1.QUAD); S.CHAIN:=E. FC七、(8分)将语句 if (A0) then while C0 do C:=C+D翻译成四元式。答：100 (j， B， 0， 104)103 (j， -， -， 109)104 (j， C， 0， 106)105 (j， -， -， 109)106 (+， C， D， T1)107 (:=， T1， -， C)108 (j， -， -， 104)109八、(10分) 设有基本块如下：T1:=S+RT2:= 3T3:= 12/T2T4:=S/RA:=T1-T4T5:=S+RB:=T5T6:=T5*T3B:=T6(1)画出DAG图；T1,T5, B3T24SR+/*_T3T4AT6,Bn4n5n1n2n3n6n8n7(2)设A,B是出基本块后的活跃变量，请给出优化后的四元式序列。答：(1) DAG如右图：(6分)(2) 四元式序列：(4分)T1:=S+RT4:=S/RA:=T1-T4B:=T1*4九、(9分) 设已构造出文法G(S)：(1) S BB(2) B aB(3) B b的LR分析表如下ACTIONGOTO状态ab#SB0s3s4121acc2s6s753s3s484r3r35r16s6s797r38r2r29r2假定输入串为abab，请给出LR分析过程(即按照步骤给出状态，符号，输入串的变化过程)。答：步骤状态符号输入串00#abab#103#abab#2034#abab#3038#aBab#402#Bab#5026#Bab#60267#Bab#70269#BaB#8025#BB#901#S#acc二、（10分）设有文法GA: A iB*e B SB|e S eC|.i C eC|e 判定该文法是否为LL(1)文法？若是则给出它的LL(1)分析表，否则说明理由。解：先计算各个产生式的Predict集： Predict (A- iB*e)= i ; Predict (B- SB) = , . Predict (B-e ) = * Predict (S-eC) = Predict (S-. i) = . Predict (C- eC) = e Predict (C-e ) = 因为Predict集没有冲突，所以是LL(1)文法。 LL(1)分析表如下： i * e . A - iB*e - e B -S B -S B S -e C -. i C -eC - e 三、（15分）设有文法GS: S LaR|R L bR|c R L判断该文法是否为LR(1)文法。若是则给出它的LR(1)状态机以及LR分析表。5已知文法GS： S S；GG G G(T) H H a (S) T T+S S 找出句型：a(T+S)；H；(S)的短语、简单短语和句柄。解：短语共有7个：a(T + S) ; H ; (S)a(T + S) ; Ha(T + S)T + S(S)Ha简单短语个：a , T + S , H , (S)句柄：a。6已知文法GS为： SAB | bC Ab | BaD | CAD | b DaS | c 对其每一个非终级符求First集和Follow集。解： First (S)= b , a , First (A) = b , First (B) = a , First (C) = b , a , c First (D) = a , c Follow (S)= # Follow (A) = a , c , # Follow (B) = # Follow (C) = # Follow (D) = # 1 编译程序在逻辑上由哪几部分组成？答：六个阶段: 词法分析,语法分析,语义分析,中间代码生成,中间代码优化和目标代码生成。2. 文法G的产生式为：a|b|()c|1）构造句型（bcc）的推导树，并指出该句型的所有短语、简单短语、句柄。2）若句柄存在，求下述符号串的句柄。a)(c(b) b)() c)(a) d)c e) f)b分析：符号串的某一部分符号要成为句柄，必须满足：a）该符号串必须是该文法的句型（句子）。b）是最左简单短语，所以文法的开始符号不是句柄。因此只要给出句型(句子)对应的推导树就容易求出短语、简单短语和句柄。解答：1）句型（bcc）的推导树如图2.1所示： 图2.1 句型（bcc）的推导树短语：b;bcc;c;(bcc)简单短语：b;c句柄：b2) a）句型(c(b)的推导树如图2.2所示：图2.2 句型(c(b)的推导树句柄为b。b) 句型()的推导树如图2.3所示：图2.3 句型()的推导树句柄为。c) 句子(a)的推导树如图2.4所示：图2.4 句子(a)的推导树句柄为a。d）c不是文法G的句型，句柄不存在。e）是开始符号，句柄不存在。f）句子b的推导树如图2.5所示：图2.5 句子b的推导树句柄为b。3. 试证具有直接左递归产生式的文法不是LL(k)文法。证明：考察文法G：ab即= a=a b=b，考虑最左推导iai aai与最左推导iai bai，i0表示i次直接推导，当ik时 FIRSTk(aai)FIRSTk(bai)=bak-1 ，G不是LL(k)文法。由于文法G是有直接左递归产生式的文法，所以命题得证。4. 考察如下文法G：abadefga) 试证文法G是LL(1)文法。解答：a)G各个产生式的选择集合为：Select(a)=FIRST(a)=a,f,gSelect(b)=FIRST(b)=d,e,bSelect(a)=FIRST(a)=aSelect()=FIRST()=f,gSelect(d)=FIRST()=dSelect(e)=FIRST()=eSelect()=FOLLOW()=b,Select(f)= FIRST(f)=f Select(g)= FIRST(g)=g 显然，具有相同左部的产生式的选择集合不相交G是LL(1)文法。5.试判定下述文法G是否是LR（1）文法？为什么？aa解答：a）对文法G存在的句子aaa，有二棵不同的推导树（图5.1）：该文法是二义性文法，G不是LR（1）文法。4.132001年编译原理试题1（10分）处于/* 和 */之间的串构成注解，注解中间没有*/。画出接受这种注解的DFA的状态转换图。2（10分）为语言L ambn | 0 m 2n（即a的个数不超过b的个数的两倍）写一个LR（1）文法，不准超过6个产生式。（若超过6个产生式，不给分。若所写文法不是LR（1）文法，最多给5分。）3（10分）构造下面文法的LL（1）分析表。D TLT int | realL id RR , id R | e4（15分）就下面文法S ( L) | aL L , S | S 给出一个语法制导定义，它输出配对括号的个数。 给出一个翻译方案，它输出每个a的嵌套深度。如句子(a, (a, a) )，第一小题的输出是2，第二小题的输出是1 2 2。9（10分）如果在A机器上我们有C语言编译器CCA，也有它的源码SA（用C语言写成）。如何利用它通过尽量少的工作来得到B机器的C语言编译器CCB。10（5分）表达式(lx.(lyz.(x + y) + z) 3) 4 5和(lx.(lyz.(x + y) + z) 3 5) 4有同样的结果。在抽象机FAM上，哪一个表达式对应的目标代码的执行效率高？为什么？2001年编译原理试题参考答案1124start52othersothers/*/2LR（1）文法LR（1）文法二义文法S AB | aABbS ABS AASb | eA aaAb | eA aaAb | ab | eA a | e B Bb | eB Bb | e3int realid,$DDTLDTLTTintTrealLLid RRR , id RR e4S S print(S.num)S (L)S.num := L.num +1S aS.num := 0L L1,SL.num := L1.num + S.num L SL.num := S.numS S.depth := 0 SS L.depth := S.depth +1 (L)S a print(S.depth)L L1.depth := L.depth L1, S.depth := L.depth SL S.depth := L.depth S9 修改源码SA 的代码生成部分，让它产生B机器的代码，称结果程序为SB。 将SB提交给CCA进行编译，得到一个可执行程序。 将SB提交给上述可执行程序进行编译，得到所需的编译器CCB。10第一个表达式在执行lyz.(x + y) + z) 3时出现参数个数不足的情况，因此有FUNVAL的值进入栈顶，然后发现参数个数不足，又把它做成FANVAL的情况。而第二个表达式执行的是(lyz.(x + y) + z) 3 5，不会出现参数个数不足的情况。因此第二个表达式的执行效率比第一个表达式的高。2003年编译原理试题1（20分）写出字母表S = a, b上语言L = w | w中a的个数是偶数的正规式，并画出接受该语言的最简DFA。2（15分）考虑下面的表达式文法，它包括数组访问、加和赋值：E EE | E + E | E = E | (E) | id该文法是二义的。请写一个接受同样语言的LR(1)文法，其优先级从高到低依次是数组访问、加和赋值，并且加运算是左结合，赋值是右结合。3（10分）下面是产生字母表S = 0, 1, 2上数字串的一个文法：S D S D | 2D 0 | 1写一个语法制导定义，它打印一个句子是否为回文数（一个数字串，从左向右读和从右向左读都一样时，称它为回文数）。4（10分）教材上7.2.1节的翻译方案P offset := 0 DD D ; D D id : T enter(id.name, T.type, offset); offset := offset + T.width T integerT.type := integer; T.width := 4 T realT.type := real; T.width := 8 使用了变量offset。请重写该翻译方案，它完成同样的事情，但只使用文法符号的属性，而不使用变量。2003年编译原理试题参考答案1语言L的正规式是：(a b*a | b)* 或 b*(a b*a b*)* 2start1aabb接受该语言的最简DFA是：2E T = E | TT T + F | FF FE | (E) | id3S Sprint(S.val)S D1 S1 D2S.val =(D1.val = D2.val) and S1.val S 2S.val = trueD 0D.val = 0D 1D.val = 14文法符号D的属性offset1是继承属性，代表在分析D前原来使用的变量offset的大小；属性offset2是综合属性，代表在分析D后原来使用的变量offset的大小。P的属性offset是综合属性，记录该过程所分配的空间。P D.offset1 := 0 D P.offset := D.offset2 D D1.offset1 := D.offset1 D1 ; D2.offset1 := D1.offset2 D2 D.offset2 := D2.offset2 D id : T enter ( id.name, T.type, D.offset1); D.offset2 := D.offset1 + T.width T integer T.type := integer; T.width := 4 T realT.type := real; T.width := 8 1（15分）(a) 字母表S = ( , ) 上的语言 ( ), ( )( ), ( ), ( )( )( )( )( )是不是正规语言？为什么？(b) 正规式 (0 | 1)* 和( (e | 0) 1* )*是否等价，说明理由。2（15分）接受文法S A a | b A c | d c | b d aA dS .SS .A aS .b A cS .d cS .b d aA .dI0S b .A cS b .d aA .dI3daS d .cA d .I4AS S .I1SS A .aI2AS A a .I5bS b A .cI6dS d c .I8S b d .aA d .I7cS b A c .I9S b d a .I10ca活前缀的DFA见下图。请根据这个DFA来构造该文法的SLR(1)分析表，并说明该文法为什么不是SLR(1)文法。3（10分）现有字母表S= a ，写一个和正规式a*等价的上下文无关文法，要求所写的文法既不是LR文法，也不是二义文法。4（20分）(a) 下面的文法定义语言L = anbncm | m, n 1。写一个语法制导定义，其语义规则的作用是：对不属于语言L的子集L1= anbncn | n 1的句子，打印出错信息。S D CD a D b | a bC C c | c(b) 语句的文法如下：S id := E | if E then S | while E do S | begin S ; S end | break写一个翻译方案，其语义动作的作用是：若发现break不是出现在循环语句中，及时报告错误。2005年编译原理和技术试题参考答案1(a) 语言 ( ), ( ) ( ), ( ), ( ) ( ) ( ) ( ) ( )是正规语言，因为该语言只包括有限个句子，它可以用正规式定义如下：( ) | ( )( ) | ( ) | ( ) ( ) ( ) ( ) ( )(b) 我们分析正规式( (e | 0) 1* )*表示的语言。可以看出正规式(e | 0) 1*描述的语言是集合e, 1, 11, 111, , 0, 01, 011, 0111, ，它含长度为1的两个串0和1。那么，(0 | 1)* 所描述的语言是( (e | 0) 1* )* 所描述的语言的子集，因为(0 | 1)* 表示字母表0, 1上所有串的集合，因此( (e | 0) 1* )* 所描述的语言不可能再有更多的句子，因而也是表示字母表0, 1上所有串的集合。2分析表如下。因为有两处有移进归约冲突，所以该文法不是SLR(1)文法。注：Fallow(A) = a, c状态 动作转移 a b c d $ S A 0 s3 s4 1 2 1 acc 2 s5 3 s7 6 4 r5 s8, r5 5 r1 6 s9 7 s10, r5 8 r3 9
展开阅读全文